Good Mood

Dette er det første indlæg i en 3-del serie om grundlæggende i kryptografi. Serien er skitseret som følger:

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

Dykning i verden af computer videnskab kan være en skræmmende opgave. Især alene!, I denne blogserie vil jeg gerne tilbyde et overblik på højt niveau om det grundlæggende i kryptografi for dem, der ønsker at dykke længere ind i emnet, som ikke nødvendigvis ved, hvor de skal starte. Denne oversigt er specifikt baseret på mine vigtigste takea .ays fra Stanfords kryptografi i kursus som undervist af Dan Boneh, tilgængelig på Coursera.

Jeg besluttede at tage dette kursus, da jeg er en blockchain-udvikler, der ikke kom fra en traditionel comp-sci-baggrund. Jeg studerede økonomi på college, men vendte mig mere mod computerprogrammering, da jeg begyndte min karriere., Lige siden jeg begyndte kodning, har jeg været på en mission for at komme “tættere på computeren” — for at skrælle de abstraktionslag, jeg nød som webebudvikler, tilbage og forstå, hvad der foregår under hætten. Overgang til cryptocurrency og distribuerede systemer fra webebudvikling har været et vildt og vidunderligt skridt i den retning på mange måder, ikke mindst som blev mere fortrolig med begreberne kryptografi. Jeg ønskede dog et mere solidt fundament., Da det er et ganske stort felt, troede jeg, det var værd at droppe $70 for at forbruge disse oplysninger i et forum, der er specielt kurateret fra Stanford University. Du kan også revidere dette kursus uden at aflevere opgaver Gratis. Vidundere af internettet!

lad os begynde.

i det væsentlige er kryptografi praksis med sikker kommunikation i nærværelse af potentielle tredjeparts modstandere. Begrebet Sikker kommunikation består af 2 hovedpunkter:

1. sikkerhed mod aflytning: dette sikrer datafortrolighed.,
2. sikkerhed mod datamanipulation: dette sikrer dataintegritet, hvilket betyder, at ingen kan manipulere data, du har sendt, og narre modtageren til at acceptere de manipulerede data som gyldige.

data fortrolighed opnås gennem kryptering, som kan antage to former: symmetrisk og asymmetrisk.

• symmetrisk kryptering bruger en enkelt nøgle, der skal deles mellem alle deltagere, der kommunikerer.
• asymmetrisk kryptering bruger personlige nøgler., Hver deltager har deres egen offentlige nøgle og private nøglepar til at kryptere og dekryptere meddelelser, når de kommunikerer.

(Bemærk: denne blogpost vil tale om kryptografi i forbindelse med symmetrisk kryptering. I et opfølgende indlæg dykker vi ned i asymmetrisk kryptering.)

Kryptering af Data: der er To typer af Kode

Kryptering sikrer fortrolighed og involverer to vigtige komponenter:

1. En hemmelig nøgle: I forbindelse med symmetrisk kryptering, kan vi antage, at vores deltagere, Alice og Bob, har en fælles hemmelige nøgle.,
2. en kryptering: et sæt algoritmer, en til kryptering og en til dekryptering.

det er vigtigt at bemærke, at krypterings-og dekrypteringsalgoritmerne er offentligt kendte. Det eneste, der holdes hemmeligt, er nøglen.

to typer af ciphers er stream ciphers og blokere ciphers. En potentiel forudsætning for tilstrækkelig forståelse af begge disse cifre er kendskab til bitvis operationer (operationer udført på bits). Mere specifikt begrebet eksklusiv – eller (oror). Jeg fandt denne blogpost til at give en meget klar forklaring på bitwiseise operationer., Eller du kan prøve at forstå begrebetoror ved hjælp af billedet nedenfor. Grundlæggende kombineres to bits, og hvis de er forskellige (en 0 og en 1) resulterer de i 1, og hvis de er ens, (begge 0 ‘er eller begge 1’ er) resulterer de i 0. Fra nu af, vil jeg antage at læseren forstår begrebet XOR, og at universal-notation for XOR er: ⊕

Stream Cipher

En stream cipher er en symmetrisk nøgle cipher, hvor alm (i bytes form) er XOR vil lidt efter lidt med nøglen (også i bytes) for at producere den krypterede maskine., Den samme proces bruges til at dekryptere cipherteksten. I betragtning af arten af operationor-operationen, hvis vi XOR cipherte .t med nøglen, resulterer dette tilbage med den originale klartekst.

En skarpsindige læser måske indse, fra denne beskrivelse, at nøglen (markeret i illustrationen ovenfor som “stream Cipher”) og alm skal have noget meget vigtigt til fælles. Det er rigtigt! Nøglen og klarteksten skal være af samme længde., Dette er selvfølgelig ikke ekstremt praktisk.

for at gøre en stream-chiffer mere praktisk introduceres ideen om en pseudorandomgenerator. En pseudorandom-generator er en deterministisk procedure, der tager et input og udsender et endnu længere pseudorandom-resultat. At være en deterministisk procedure betyder, at den altid vil returnere den samme nøjagtige output, hvis den gives den samme indgang (dvs. “abc123” resulterer i “8474f24e0d72e1b949ffd2…” hver gang)., Ordet pseudorandom betyder, at selvom output faktisk ikke er tilfældigt (da det bestemmes ud fra et bestemt input), kan det faktisk ikke skelnes fra en virkelig tilfældig streng. Med andre ord, givet en prøve af input og output, er der ingen spor om, hvilken udgang der svarer til en bestemt indgang og omvendt, derfor er det pseudorandom. Det er muligt at bruge den delte hemmelige nøgle som input til at producere en endnu længere pseudorandom-nøgle til at fungere som den lange nøgle, der skal XOR ‘ d med den lige så lange klartekst.,

denne specifikke implementering af en stream-cipher, vi hidtil har illustreret, kaldes “one-time-pad”. Et ekstremt vigtigt træk ved one-time-pad er, at one-time-pad-tasten kun kan bruges onen gang. Når det bruges en anden gang, sikkerheden af disse meddelelser er kompromitteret.

billedet nedenfor er et dias fra kurset. PRG (K) betegner pseudorandomsekvensen genereret fra vores delte nøgle K. Symbolet den betegner .or. c betegner cipherte .t. m angiver besked (eller klartekst).,

Dybest set, dette slide er at sige, at når nøglen er brugt to gange, kan vi XOR den ciphertexts sammen, og det er præcis svarer til XOR ‘ ing de to plaintexts sammen. Da der er nok redundans på engelsk, kan en kyndig angriber bruge disse oplysninger til at gendanne meddelelserne fuldstændigt.

for at opretholde en delt hemmelig nøgle kan begrebet en nonce bruges til at sikre, at vi aldrig gentager engangsnøglen., En nonce er et vilkårligt tal, der kun kan bruges Inn gang i en kryptografisk kommunikation. Når du sender cipherte .t, afsenderen kan også sende en nonce over til at blive kombineret med den hemmelige nøgle til derefter bruge som input til at producere en særskilt pseudorandom nøgle for hver kryptering.

(du har måske bemærket diaset ovenfor siger angreb 1., Som en sidebemærkning, for dem, der undrer dig over, hvad Attack 2 er, Attack 2 er det faktum, at mens stream cipher tilbyder fortrolighed, at det IKKE giver data integritet, som defineret i første afsnit)

Block Cipher

Den anden type af cipher er en Block Cipher. En blokcipher tager et input med fast længde og krypterer iterativt klarteksten igen og igen ved hjælp af en anden nøgle (en “rund nøgle”) for hver runde og udsender i sidste ende en ciphertekst af samme længde. 3DES og AES er to eksempler på blok ciphers, som tager en indgang på 48 bit og 128 bit henholdsvis.,

Slide ovenfor viser den grundlæggende arkitektur for en block cipher. Du kan se, at en nøgleudvidelsesmekanisme bruges til at have en ny nøgle til hver runde. Klarteksten, betegnet (m) for besked, bliver krypteret igen og igen, indtil endelig den tilsvarende ciphertekst (c) af samme længde returneres.

af hensyn til kortfattethed dækker jeg AES i denne blogpost., Selvom DES / 3DES er historisk signifikant, er AES i dag mere udbredt og accepteret.

AES er bygget som en Substitution, Permutation Netværk. AES opererer på en 128 bit blok, svarende til 16 byte. Som vist ovenfor øverst til venstre skriver vi 16 bytes som en 4 ved 4 Matri.. Denne Matri.fungerer som en datastruktur, der er god til at blande data rundt., I hver runde er processen som følger:

1. Vi XOR den runde nøgle, først (k0), med den aktuelle meddelelse
2. derefter gennemgår vi en substitutionsproces, hvor blokke af data erstattes med andre blokke baseret på en given substitutionstabel (afbildet ovenfor (1) ByteSub).
3. Vi går gennem et permutationslag, hvor bits permuteres og blandes rundt (billedet ovenfor (2) Shiftro. & (3) Mi .column).
4. så gentager vi denne proces i 10 runder.,

Billedet ovenfor, vil du bemærke, at den sidste runde springer Mix Kolonne trin, XOR ‘ s resultat med vores afsluttende runde tast og udgange vores resulterer ciphertext. For at dekryptere, vi simpelthen vende processen. Kurset giver et højt niveau overblik over denne krypteringsproces og opfordrer studerende til at se dybere ind i det, hvis det er af interesse for dig. Derfor vil jeg forlade AES indre arbejde på dette. Jeg vil anbefale folk at se på Fiestel Net procedureork procedure af 3DES for en sjov sammenligning og kontrast af forskellige blok ciphers.,

med hensyn til Hard .are har Intel siden lanceringen af Intel .estmere designet deres processorer med specielle instruktioner til AES-optimering indbygget i deres hard .are, og AMD fulgte kort derefter.

Blokcipher driftsformer

i modsætning til en stream-kryptering tager en blokcipher kun et input med fast længde. Det er klart, at vi ønsker at håndtere data, der er større end 16 bytes ad gangen. Så næste er det vigtigt at forstå de driftsformer, hvorunder vi kan bruge blokcifre til at kryptere store sæt data., For at anvende denne blokcipher på et stort datasæt kaldes den første driftsform, der kan komme til at tænke på, “elektronisk kodebog” (ECB). ECB deler simpelthen dataene i 16 byte blokke og udfører AES-kryptering ensartet. Det kunne endda gøres parallelt. Meget hurtigt! Men det er faktisk ikke meget sikkert.

Det er usikker, fordi hvis en 16-byte message gentager sig selv, er det ciphertext vil også have gentagne data., Dette videregiver oplysninger om vores data til en potentiel angriber. Vi kan anvende denne sårbarhed i det tilfælde, hvor vi krypterer et billede med ECB. Som du kan se nedenfor, er det klart, at vores billede er et headshot. I det stærkt sorte område kan vi se en silhuet via det mørke hår og skjorte.

Det er vigtigt, at vores kryptering ordninger er semantisk sikkert., Semantiske Sikkerhed er konceptet, at hvis vi har en maskine, der svarer til en af to forskellige plaintexts, en modstander ikke kan gætte, med bedre sandsynlighed end 1/2 som alm maskine svarer til. Det er klart, at ECB ikke er semantisk sikker. Vores krypterede billede giver os masser af information til at gætte det tilsvarende almindelige billede.

ECB er et eksempel på en engangs-nøgle driftsform (hvilket betyder, Ligesom engangs-pad, en nøgle kan kun bruges )n gang). En anden mere sikker engangsnøgle driftstilstand er deterministisk modtilstand. Du er fri til at undersøge det på egen hånd., Jeg vil gå videre til de sikre driftsformer,der aktiverer mange taster!

Cipher Block Chaining (CBC) er en driftsform, der kæder hver 16-byte blok af klartekst sammen gennemoror ‘ ing cipherteksten af den forrige klartekst i vores nuværende klartekst, før du udfører block cipher-krypteringen (dvs.AES). Nedenstående billede præciserer dette koncept:

Vi starter med en tilfældig IV., IV står for initialisering vektor, som kan defineres som: den oprindelige værdi bruges til at starte nogle itereret proces. I tilfælde af CBC skal IV være tilfældig (dermed uforudsigelig), derfor skal den være unik for hver transaktion. Den første blok-maskine er simpelthen den ukrypterede tilfældig IV. At producere resten af ciphertext, for det første, tilfældige IV er XOR ville med den første blok af tekst (m). Resultatet bliver derefter krypteret med rund nøgle k for at returnere den første blok af krypteret cipherte .t (C)., Der ciphertext så bliver XOR ‘ d med den næste blok af tekst (m), resultatet er krypteret med runde nøgle k og returnerer den anden blok af krypterede ciphertext c). Processen fortsættes, indtil alle blokke er krypteret.

for At dekryptere, vi bare vende processen.

en vigtig komponent til CBC-kryptering er, at den tilfældige IV er uforudsigelig., Hvis IV bliver forudsigelig, så vores kryptering ordning bliver sårbar over for valgte klartekst angreb. Valgt Klartekst Angreb (CPA) er et angreb model, som antager, at angriberen kan få ciphertexts for vilkårlige plaintexts, og bruge disse til at afsløre oplysninger om, krypterede meddelelser. Derfor er en uforudsigelig IV nødvendig for at sikre CPA-sikkerhed.

bær med mig her, da jeg forsøger at forklare, hvordan dette angreb ville fungere: det er muligt at udføre et valgt klartekstangreb i nærværelse af forudsigelige IV ‘ er på grund af arten af .or., Hvis du XOR den samme værdi sammen (0101 ⊕ 0101) det vil altid lig 0, dermed det annullerer. Så hvis du har mistanke om en observeret ciphertext c svarer til en bestemt klartekst m du kan afprøve din hypotese med en forudsigelig IV. Hvis alm pågældende var krypteret med IV1 sådan, at c = E(k, m ⊕ IV1) du kan indsende en ny klartekst, der skal krypteres, og se hvis du kan få en matchende resultat: c. Da du kan forudsige IV vil være IV2, kan du indsende m ⊕ IV1 ⊕ IV2., CBC-processen viloror denne indgang med den næste IV, IV2 sådan, at: c = E(K, M IV IV1 ⊕ IV2.IV2) dermed annullerer IV2, og endnu en gang krypterer vi E(K, IV1 ⊕ m), hvilket igen ville resultere med c, og hvis dette sker, var vi i stand til at gætte, hvad der tidligere var krypteret med IV1.

virkelig fantastisk job, hvis du kom igennem det — ^

med det, vil jeg gerne gennemgå endnu en blokcipher-driftstilstand, som vil afslutte den første blogpost i denne 3 del serie. Hvis det har været en stor indsats for at gøre det så langt, nu kan være et godt tidspunkt for en hurtig pause, før du fortsætter!,

Ok, så vi har gennemgået ECB, CBC, og deres svagheder, men endelig, og nok vigtigst af alt vil jeg introducere Randomiseret Counter Mode (CTR). Dette er den seneste, mest sikre driftsform, og det er også mere effektivt end CBC.

Randomiseret Counter Mode også tager en tilfældig IV. IV tjener et andet formål med at være her selv. Vores nøgle bliver kombineret (f. eks, via AES) med en itereret version vores IV: ovenfor fortsætter vi med at tilføje 1 til vores IV for hver iteration, ellers får vi et gentaget resultat. Vi gør dette, indtil vi har en pude, så længe vores klartekst besked. Ligesom one-time-pad stream cipher, vi nu XOR vores klartekst besked med vores pseudorandom pad til at resultere i en cipherte .t. Hvis din hard .are har flere AES-motorer, er dette ultraeffektivt, fordi det kan paralleliseres. I CBC, hver cipherte .t afhang af den tidligere blok af cipherte .t, så det var umuligt at parallelisere.,

vi behøver ikke engang nødvendigvis en blokcipher for at kombinere vores IV og nøgle i en pseudorandom pad. Blok ciphers skal være reversible. Hvis du ser nøje på mekanikken i randomiseret tællertilstand, vil du bemærke, at dekryptering ikke kræver, at vi vender F(k, IV) . I betragtning af arten AFOROR er alt, hvad vi skal gøre, regenerere den samme pseudorandom pad og Andor det med vores cipherte .t. For at dekryptere skal vi derfor gentage operationen og ikke vende den.,

abstrakt set (indtil videre har jeg undgået abstrakte begreber), det betyder, at proceduren, vi bruger til at kombinere vores hemmelige nøgle og IVF(k, IV), skal være en Pseudorandom-funktion (PRF) i modsætning til en Pseudorandom-Permutation (PRP). Vi har faktisk anvendt disse begreber i hele denne blogpost. Både PRP ‘er og PRF’ er er deterministiske procedurer, der med et bestemt input resulterer i en pseudorandomudgang. (dvs. AES, ,OR). En PRP er dog strengere i den forstand, at den skal være reversibel., Faktisk bruges udtrykkene PRP og block cipher (såsom AES) ofte synonymt. En PRF behøver dog ikke at være reversibel. Hvis du vender tilbage til tidligere dias, der vises i dette indlæg, forstår du nu notationen PRF og PRP.

det afslutter mit overblik over symmetrisk kryptering! Vi dækkede stream ciphers og blokere ciphers. Da blokcifre kun kan udføres på omkring 16 byte ad gangen, dækkede vi de driftsformer, der blev brugt til at udføre blokcifre på store plainte .ts. Vi præciserede også begreberne PRPs vs PRFs.