Good Mood

Dette er det første innlegget i et 3 del serien på det grunnleggende av kryptografi. Serien er skissert som følger:

1. Symmetrisk Kryptering
2. Data Integritet & Godkjent Kryptering
3. Asymmetrisk Kryptering med Offentlig/Privat nøkkelpar

Dykke inn i verden av informatikk kan være en skremmende oppgave. Spesielt ikke alene!, I denne bloggen serien, jeg ønsker å tilby en oversikt på høyt nivå på de grunnleggende kryptografi for de som ønsker å fordype videre inn på det emnet som ikke nødvendigvis vet hvor du skal begynne. Denne oversikten er basert spesielt på min viktigste takeaways fra Stanford er Kryptografi jeg kurs som undervises av Dan Boneh, tilgjengelig på Coursera.

jeg bestemte meg for å ta dette kurset siden jeg er en blockchain utvikler som ikke kommer fra en tradisjonell comp-sci bakgrunn. Jeg studerte økonomi i college men kom til å dreie mer mot programmering da jeg begynte min karriere., Helt siden jeg begynte koding, jeg har vært på et oppdrag for å få «nærmere datamaskinen» — å skrelle tilbake lag av abstraksjon jeg likte som en web-utvikler og forstå hva som skjer under panseret. Overgangen til cryptocurrency og distribuerte systemer fra web-utvikling har vært et vilt og vakkert skritt i riktig retning på mange måter, ikke minst som begynte å bli mer kjent med begrepene kryptografi. Men, jeg ville ha et mer solid fundament., Siden det er et ganske stort felt, tenkte jeg det var verdt det for å slippe $70 for å konsumere denne informasjonen i et forum spesielt kuratert fra Stanford University. Du kan også overvåke dette kurset uten å måtte levere oppgaver for gratis. Underverkene av internett!

La oss begynne.

Egentlig, kryptografi er å praktisere sikker kommunikasjon i nærvær av potensielle tredjepart motstandere. Begrepet sikker kommunikasjon består av 2 viktige punkter:

1. Sikkerhet mot avlytting: dette sikrer dataenes konfidensialitet.,
2. Sikkerhet mot data manipulasjon: dette sikrer dataenes integritet betyr at ingen kan manipulere dataene du har sendt til og lure mottakeren til å akseptere den manipulerte data som gyldig.

Data konfidensialitet er oppnådd gjennom kryptering, som kan ta to former: symmetrisk og asymmetrisk.

• Symmetrisk kryptering bruker én enkelt tast som må deles blant alle deltakerne som kommuniserer med hverandre.
• Asymmetrisk kryptering bruker personlige nøkler., Hver deltaker har sin egen offentlige nøkkel og en privat nøkkel-par for å kryptere og dekryptere meldinger når du kommuniserer.

(Merk: Dette innlegget vil snakke om kryptografi i sammenheng med symmetrisk kryptering. I en oppfølging post, vi vil dykke inn i asymmetrisk kryptering.)

Datakryptering: To typer Chiffer

Kryptering sikrer dataenes konfidensialitet og innebærer to viktige komponenter:

1. En hemmelig nøkkel: I sammenheng med symmetrisk kryptering, kan vi anta våre deltakere, Alice og Bob, har en delt hemmelig nøkkel.,
2. En cipher: et sett med algoritmer, ett for kryptering og en for dekryptering.

Det er viktig å merke seg at kryptering og dekryptering algoritmer er offentlig kjent. Det eneste bevarte hemmelighet er nøkkelen.

To typer chiffer er stream-chiffer og blokk chiffer. En mulig forutsetning for en adekvat forståelse både av disse chiffer er kunnskap om bitvis operasjoner (operasjoner utført på bits). Mer spesifikt, begrepet eksklusiv-eller (XOR). Jeg fant dette innlegget til å gi et meget tydelig forklaring av bitvis operasjoner., Eller du kan prøve å forstå konseptet av XOR bruke bildet nedenfor. I utgangspunktet to biter er satt sammen, og hvis de er forskjellige (en 0 og 1) de resultere i 1, og hvis de er det samme, (både 0 eller begge 1) de resultere i 0. Fra her på ut, vil jeg anta at leseren forstår konseptet med XOR og at universell notasjon for XOR er: ⊕

Stream Cipher

En stream cipher er en symmetrisk nøkkel cipher hvor ren tekst (i byte form) er XOR vil litt etter litt med tasten (også i byte form) til å produsere kryptert ciphertext., Den samme prosessen som brukes til å dekryptere ciphertext. Gitt natur XOR drift, hvis vi XOR den ciphertext med nøkkelen, dette resulterer tilbake med den opprinnelige ren tekst.

En ivrig leser kan forstå fra denne beskrivelsen at nøkkelen (merket i illustrasjonen ovenfor som «stream Cipher») og ren tekst må ha noe veldig viktig i vanlige. Det er riktig! Nøkkelen og ren tekst må ha samme lengde., Dette selvfølgelig ikke er svært praktisk.

for Å lage en stream cipher mer praktisk, ideen om en pseudotilfeldig generator er innført. En pseudotilfeldig generator er en deterministisk prosedyre som tar en input og output en enda lengre pseudotilfeldig resultat. Å være en deterministisk prosedyre betyr at det vil alltid returnere nøyaktig samme utgang hvis de får de samme inngang (dvs. «abc123» resultater i «8474f24e0d72e1b949ffd2…» hver gang)., Ordet pseudotilfeldig betyr at mens produksjonen er faktisk ikke tilfeldig (siden det er fastsatt basert på en bestemt inngang), det er faktisk umulig å skille fra en virkelig tilfeldig streng. Med andre ord, gitt en prøve av innganger og utganger, det er ingen ledetråder til hvilken utgang svarer til en bestemt inngang og omvendt, derfor er det pseudotilfeldig. Det er mulig å bruke felles hemmelig nøkkel som input for å produsere en enda lengre pseudotilfeldig-tasten for å fungere som den lange tasten for å være XOR vil med like lange ren tekst.,

Dette bestemte gjennomføring av en stream cipher vi har vist så langt er kalt «en-gang-pad». En svært viktig funksjon i det en-gang-pad er at en-gang-pad kan brukes bare ÉN GANG. En gang det er brukt en gang, den sikkerhet av disse meldingene er kompromittert.

Avbildet nedenfor er et lysbilde fra kurset. PRG(K) betegner pseudotilfeldig sekvensen genereres fra vår felles tasten K. symbolet ⊕ betegner XOR. c betegner ciphertext. m angir meldingen (eller ren tekst).,

i Utgangspunktet, dette dekselet er å si at når tasten er brukt to ganger, kan vi XOR den ciphertexts sammen, og det er akkurat lik XOR ‘ ing de to plaintexts sammen. Siden det er nok redundans på engelsk, er en dyktig angriper kan bruke denne informasjonen til å gjenopprette meldinger fullstendig.

for Å opprettholde en felles hemmelig nøkkel, konseptet av en nonce kan brukes til å sikre at vi aldri gjenta én-gang-pad-tasten., En nonce er et tilfeldig nummer som kan brukes bare én gang i en kryptografisk kommunikasjon. Når du sender ciphertext, avsenderen kan også sende en nonce over til å bli kombinert med den hemmelige nøkkelen for å så bruke som input for å produsere en tydelig pseudotilfeldig tast for hver kryptering.

(det kan hende Du har lagt merke til dekselet over sier Angrep 1., Som en side, for de som lurer på hva Angripe 2 er, Angrep 2 er det faktum at mens stream cipher tilbyr data konfidensialitet, vil det IKKE gi data integritet som definert i den første delen)

Block Cipher

Den andre typen av cipher er et Block Cipher. En block cipher tar i en fast lengde innspill og iterativt krypterer ren tekst igjen og igjen ved hjelp av en annen nøkkel (en «runde nøkkel») for hver runde, og til slutt sender en ciphertext av samme lengde. 3DES og AES er to eksempler på blokk chiffer som tar en inngang av 48 bits og 128 bits henholdsvis.,

Lysbilde over viser den grunnleggende arkitektur for et block cipher. Du kan se at en viktig utvidelse mekanismen brukes til å få en ny nøkkel for hver runde. Ren tekst, merket (m) for melding, blir kryptert igjen og igjen helt til slutt tilsvarende ciphertext (c) av samme lengde er returnert.

på grunn av kortfattethet, vil jeg dekke AES i dette innlegget., Selv DES/3DES er historisk viktig, i dag AES er mer utbredt og akseptert.

AES er bygget som en Erstatning Permutasjon Nettverk. AES-opererer på et 128-bits blokker, lik 16 bytes. Som bildet ovenfor øverst til venstre, vi skriver 16 byte som et 4 av 4 matrise. Denne matrisen fungerer som en datastruktur bra for sanering data rundt., I hver runde, prosessen er som følger:

1. Vi XOR runde tasten, første (k0), med dagens melding
2. Så går vi gjennom en substitusjon prosess der blokker av data er erstattet med andre blokker basert på en gitt erstatning tabell (bildet over (1) ByteSub).
3. Vi gå gjennom en permutasjon lag hvor biter er permuted og stokket rundt(bildet over (2) ShiftRow & (3) MixColumn).
4. Så vi gjenta denne prosessen for 10 runder.,

Avbildet ovenfor, vil du legge merke til at den siste runden hopper Blanding Kolonne trinn, XOR er resultatet med våre siste runde tasten og utganger våre resulterer ciphertext. For å dekryptere, vi bare reversere prosessen. Kurset gir en høy grad oversikt over dette krypteringsprosessen og oppfordrer elevene til å se dypere inn i det hvis det er av interesse for deg. Derfor vil jeg la AES indre arbeidet på dette. Jeg vil anbefale folk å se inn i Fiestel Nettverk prosedyre for 3DES for en morsom sammenligne forskjellige blokk chiffer.,

I form av maskinvare, siden lanseringen av Intel Westmere, Intel har utviklet sine prosessorer med spesielle instruksjoner for AES optimalisering innebygd i maskinvaren og AMD fulgt etter kort tid etterpå.

Block Cipher Moduser av Drift

i Motsetning til en stream cipher, en block cipher tar bare en fast lengde inngang. Selvsagt ønsker vi å håndtere data som er større enn 16 byte om gangen. Så neste det er viktig å forstå moduser av drift under som vi kan bruke blokk chiffer for å kryptere stort sett av data., For å bruke denne block cipher til en stor dataset, den første modus av drift som kan komme til sinn er kalt «Electronic Code Book» (ECB). ECB bare deler data inn i 16 byte blokker og utfører AES-kryptering jevnt. Det kan også gjøres i parallell. Veldig fort! Men det er faktisk ikke så veldig sikker.

Det er usikre fordi hvis en 16 byte melding gjentar seg selv, ciphertext vil også ha gjentatt data., Dette divulges informasjon om våre data til en potensiell angriper. Vi kan bruke denne sårbarheten til den saken som vi er kryptere et bilde med ECB. Som du kan se nedenfor, er det klart at vårt bilde er en headshot. I tungt svart området, kan vi se en silhuett via mørkt hår og skjorte.

Det er viktig at våre kryptering ordninger er semantisk sikker., Semantisk Security er den som sier at hvis vi har en ciphertext som svarer til en av to forskjellige plaintexts, en motstander kan ikke gjette seg frem med bedre sannsynlighet enn 1/2 som ren tekst i ciphertext tilsvarer. Klart, ECB er ikke semantisk sikker. Våre kryptert bilde gir oss nok informasjon til å gjette det tilsvarende vanlig bilde.

ECB er et eksempel på en en-gang-tasten modus av drift (det vil si, som en-gang-pad, en nøkkel kan bare brukes én gang). En annen som er mer sikre en-gang-tasten modus av drift er deterministisk counter-modus. Du er fri til å se på det på egen hånd., Jeg vil flytte til sikker modus av drift som gjør det mulig for mange-tid taster!

Cipher Block Sammenkjeding (CBC) er en modus av drift at kjedene hver 16-byte blokker av ren tekst sammen gjennom XOR ‘ ing den ciphertext av forrige ren tekst inn i våre nåværende ren tekst før du utfører block cipher-kryptering (dvs. AES). Bildet under klargjør dette konseptet:

Vi først starte med en tilfeldig IV., IV står for initialiseringsvektor som kan være definert som: den første verdien som brukes til å starte noen iterated prosessen. I tilfelle av CBC, IV må være tilfeldig (og dermed uforutsigbare) derav det må være unik for hver transaksjon. Første blokk av ciphertext er rett og slett ikke tilfeldig IV. For å produsere resten av ciphertext, for det første, tilfeldig IV er XOR vil med det første kvartalet av ren tekst (m). Resultatet deretter blir kryptert med rund k-tasten for å gå tilbake til den første kvartal av kryptert ciphertext (c)., Som ciphertext så blir XOR vil med neste blokk med ren tekst (m), resultatet er kryptert med runde tasten k og returnerer den andre blokka av kryptert ciphertext (c). Prosessen fortsetter inntil alle blokker har blitt kryptert.

for Å dekryptere, vi bare reversere prosessen.

En viktig komponent for å CBC kryptering er at den tilfeldige IV er uforutsigbar., Hvis IV blir forutsigbar, så vår kryptering ordningen blir utsatt for valgt ren tekst angrep. Valgt ren tekst Angrep (CPA) er et angrep modell som forutsetter at angriperen kan få ciphertexts for vilkårlig plaintexts, og bruke disse til å avsløre informasjon om krypterte meldinger. Derfor, en uforutsigbar IV er nødvendig for å sikre CPA-Sikkerhet.

Bære med meg her, så jeg prøver å forklare hvordan dette angrepet ville fungere: Det er mulig å utføre et valgt ren tekst angrep i nærvær av forutsigbar IV er på grunn av arten av XOR., Hvis du XOR samme verdi sammen (0101 ⊕ 0101) det vil alltid lik 0, derav det går ut. Så hvis du mistenker en observert ciphertext c svarer til en bestemt ren tekst m du kan teste hypotesen med en forutsigbar IV. Hvis ren tekst i spørsmålet ble kryptert med IV1 slik at c = E(k, m ⊕ IV1) du kan sende inn en ny, ren tekst til å være kryptert og se om du får et tilsvarende resultat: c. Siden du kan forutsi IV vil være IV2, som du sender m ⊕ IV1 ⊕ IV2., CBC prosessen vil XOR dette inngang med neste IV, IV2 slik som: c = E(k, m ⊕ IV1 ⊕ IV2 ⊕ IV2) derav IV2 går ut, og igjen vi er kryptere E(k, IV1 ⊕ m) som ville resultere i gang igjen med c og hvis dette skjer, vi var i stand til å gjette hva som tidligere var kryptert med IV1.

Virkelig fantastisk jobb hvis du fikk gjennom at — ^

Med det, jeg ønsker å gjennomgå en mer block cipher-modus av drift som vil konkludere med det første innlegget i denne 3 del serien. Hvis det har vært en stor innsats for å gjøre det så langt, nå kan være en god tid for en rask pause før du fortsetter!,

Ok, så vi har gjennomgått ECB, CBC, og sine svakheter, men til sist, og kanskje viktigst av alt vil jeg presentere Randomisert Counter-Modus (CTR). Dette er den nyeste, mest sikker modus av drift, og det er også mer effektivt enn CBC.

Randomisert Counter-Modus tar også en tilfeldig IV. IV tjener et annet formål her selv. Våre key får kombinert (f.eks., via AES) med en iterated versjon våre IV: over vi fortsette å legge 1 til våre IV for hver iterasjon, ellers ville vi få en gjentatt resultat. Dette gjør vi helt til vi har en pad så lenge vår ren tekst melding. Akkurat som en-gang-pad stream cipher, har vi nå XOR vår ren tekst melding med våre pseudotilfeldig pad til å resultere i en ciphertext. Hvis maskinvaren har flere AES motorer, dette er ultra effektiv fordi det er parallelizable. I CBC, hver ciphertext avhengig av forrige kvartal av ciphertext så det var umulig å parallelize.,

Vi ikke engang nødvendigvis trenger block cipher å kombinere våre IV og tast inn en pseudotilfeldig pad. Blokk chiffer må være reversible. Hvis du ser nøye på den tekniske siden av randomiserte counter-modus, vil du legge merke til at dekryptering ikke krever oss til å reversere F(k, IV) . Gitt arten av XOR, alt vi trenger å gjøre er å regenerere den samme pseudotilfeldig pad og XOR det med vår ciphertext. Derfor, for å dekryptere, må vi gjenta operasjonen, ikke reversere den.,

Abstrakt tale (så langt jeg har unngått abstrakte begreper), som betyr at den fremgangsmåten vi bruker for å kombinere våre hemmelige nøkkel og IV F(k, IV) må være en Pseudotilfeldig Funksjon (PRF) i motsetning til en Pseudotilfeldig Permutasjon (PRP). Vi har faktisk vært å anvende disse begrepene gjennom dette innlegget. Både PRPs og PRFs er deterministisk prosedyrer som, gitt en bestemt inngang, resultere i en pseudotilfeldig utgang. (dvs. AES, XOR). Men en PRP er strengere i den forstand at det må være reversible., Faktisk, vilkårene PRP og block cipher (for eksempel AES) er ofte brukt synonymt. En PRF men trenger IKKE å være reversible. Hvis du vil gå tilbake til forrige lysbilder som vises i dette innlegget, vil du nå forstå notasjon PRF og PRP.

Som konkluderer med min oversikt over Symmetrisk Kryptering! Vi dekket stream-chiffer og blokk chiffer. Så, siden blokk chiffer kan bare utføres på ca 16 byte om gangen, har vi dekket moduser av drift brukes til å utføre blokk chiffer på store plaintexts. Vi har også klarlagt begrepene PRPs vs PRFs.