Good Mood

det här är första inlägget i en 3 del serie om grunderna i kryptografi. Serien beskrivs enligt följande:

1. symmetrisk kryptering
2. dataintegritet & autentiserad kryptering
3. asymmetrisk kryptering med offentliga/privata nyckelpar

dykning i en värld av datavetenskap kan vara en skrämmande uppgift. Särskilt ensam!, I den här bloggserien vill jag erbjuda en högnivåöversikt om kryptografins grunder för dem som vill dyka längre in i ämnet som inte nödvändigtvis vet var de ska börja. Denna översikt är baserad specifikt på mina Huvud takeaways från Stanfords kryptografi i-kurs som lärs av Dan Boneh, tillgänglig på Coursera.

jag bestämde mig för att ta den här kursen eftersom jag är en blockchain-utvecklare som inte kom från en traditionell Comp-sci-bakgrund. Jag studerade ekonomi på college men veered mer mot datorprogrammering när jag började min karriär., Ända sedan jag började koda har jag varit på ett uppdrag att komma” närmare datorn ” — för att skala tillbaka lagren av abstraktion som jag tyckte om som webbutvecklare och förstå vad som händer under huven. Övergång till kryptovaluta och distribuerade system från webbutveckling har varit ett vildt och underbart steg i den riktningen på många sätt, inte minst som blev mer bekant med begreppen kryptografi. Men jag ville ha en mer solid grund., Eftersom det är ganska stort fält, tyckte jag att det var värt att släppa $70 för att konsumera denna information i ett forum speciellt curerat från Stanford University. Du kan också granska kursen utan att lämna in uppdrag gratis. Underverk av internet!

låt oss börja.

i huvudsak är kryptografi praxis för säker kommunikation i närvaro av potentiella tredjeparts motståndare. Begreppet Säker kommunikation består av 2 huvudpunkter:

1. säkerhet mot avlyssning: detta säkerställer datasekretess.,
2. säkerhet mot datamanipulation: detta säkerställer dataintegritet vilket innebär att ingen kan manipulera data du har skickat och lura mottagaren att acceptera de manipulerade data som giltiga.

datasekretess uppnås genom kryptering, som kan ta två former: symmetrisk och asymmetrisk.

• symmetrisk kryptering använder en enda nyckel som måste delas mellan alla deltagare som kommunicerar.
• asymmetrisk kryptering använder personliga nycklar., Varje deltagare har sin egen offentliga nyckel och privata nyckelpar för att kryptera och dekryptera meddelanden vid kommunikation.

(Obs! den här bloggposten kommer att prata om kryptografi i samband med symmetrisk kryptering. I en uppföljningspost dyker vi in i asymmetrisk kryptering.)

datakryptering: två typer av chiffer

kryptering säkerställer datasekretess och omfattar två viktiga komponenter:

1. en hemlig nyckel: i samband med symmetrisk kryptering kan vi anta att våra deltagare, Alice och Bob, har en delad hemlig nyckel.,
2. a cipher: en uppsättning algoritmer, en för kryptering och en för dekryptering.

det är viktigt att notera att krypterings-och dekrypteringsalgoritmerna är allmänt kända. Det enda som hålls hemligt är nyckeln.

två typer av chiffer är stream ciphers och block ciphers. En potentiell förutsättning för adekvat förståelse av båda dessa chiffer är kunskap om bitwise-operationer (operationer utförda på bitar). Mer specifikt begreppet exklusiv eller (XOR). Jag hittade den här blogposten för att ge en mycket tydlig förklaring av bitwise-operationer., Eller du kan försöka förstå begreppet XOR med bilden nedan. I grund och botten kombineras två bitar och om de är olika (en 0 och en 1) resulterar de i 1, och om de är desamma, (både 0 och båda 1) resulterar de i 0. Härifrån kommer jag att anta att läsaren förstår begreppet XOR och att den universella notationen för XOR är:

Stream Cipher

en stream cipher är en symmetrisk nyckelchiffer där plaintext (i bytesform) är xor ’ d bit för bit med nyckeln (även i bytesform) för att producera den krypterade ciphertext., Samma process används för att dekryptera chiffertexten. Med tanke på arten av XOR-operationen, om vi XOR ciphertext med nyckeln, resulterar detta tillbaka med den ursprungliga plaintext.

vanstående illustration som ”cipher Stream”) och plaintext måste ha något mycket viktigt gemensamt. Just det! Nyckeln och plaintext måste vara samma längd., Detta är naturligtvis inte extremt praktiskt.

för att göra en strömchiffer mer praktisk introduceras idén om en pseudorandom generator. En pseudorandom generator är ett deterministiskt förfarande som tar en ingång och matar ut ett ännu längre pseudorandom-resultat. Att vara ett deterministiskt förfarande innebär att det alltid kommer att returnera samma exakta utgång om det ges samma ingång (dvs ”abc123” resulterar i ”8474f24e0d72e1b949ffd2…” varje gång)., Ordet pseudorandom innebär att även om produktionen inte är faktiskt slumpmässigt (eftersom det bestäms baserat på en viss ingång), är det i själva verket oskiljbar från en verkligt slumpmässig sträng. Med andra ord, med tanke på ett urval av ingångar och utgångar, finns det inga ledtrådar om vilken utgång som motsvarar en viss ingång och vice versa, därför är det pseudorandom. Det är möjligt att använda den delade hemliga nyckeln som ingången för att producera en ännu längre pseudorandom-nyckel för att fungera som den långa nyckeln som ska vara XOR ’ d med den lika långa plaintext.,

denna specifika implementering av en strömchiffer som vi hittills har illustrerat kallas ”one-time-pad”. En extremt viktig egenskap hos engångsplattan är att engångsnyckeln endast kan användas en gång. När det används en andra gång äventyras säkerheten för dessa meddelanden.

bilden nedan är en bild från kursen. PRG (K) betecknar pseudorandom-sekvensen som genereras från vår delade nyckel K. Symbolen betecknar xor. C betecknar ciphertext. M betecknar meddelande (eller plaintext).,

i grund och botten säger den här bilden att när nyckeln används två gånger kan vi xor ciphertexts tillsammans, och det är exakt lika med xor ’ ing de två plaintexts tillsammans. Eftersom det finns tillräckligt med redundans på engelska kan en kunnig angripare använda denna information för att återställa meddelandena helt.

för att behålla en delad hemlig nyckel kan begreppet nonce användas för att säkerställa att vi aldrig upprepar engångstangenten., En nonce är ett godtyckligt tal som kan användas bara en gång i en kryptografisk kommunikation. När du skickar chiffertext, avsändaren kan också skicka en nonce över att kombineras med den hemliga nyckeln för att sedan använda som ingång för att producera en distinkt pseudorandom nyckel för varje kryptering.

(Du kanske har märkt bilden ovan säger Attack 1., Som en åt sidan, för dem som undrar vad Attack 2 är, Är Attack 2 det faktum att medan stream cipher erbjuder datasekretess, ger den inte dataintegritet enligt definitionen i första avsnittet)

Block Cipher

den andra typen av chiffer är ett Blockchiffer. En blockchiffer tar in en fast längd ingång och iterativt krypterar plaintext om och om igen med en annan nyckel (en ”rund nyckel”) för varje runda och slutligen matar ut en chiffertext av samma längd. 3DES och AES är två exempel på blockchiffer som tar en ingång på 48 bitar respektive 128 bitar.,

bilden ovan visar den grundläggande arkitekturen för ett block chiffer. Du kan se att en viktig expansionsmekanism används för att ha en ny nyckel för varje runda. Plaintext, betecknad (m) för meddelande, blir krypterad om och om igen tills slutligen motsvarande ciphertext (c) av samma längd returneras.

för korthetens skull täcker jag AES i den här bloggposten., Även om DES/3DES är historiskt signifikant, används idag AES mer allmänt och accepteras.

AES är byggt som ett substitutions Permutationsnätverk. AES fungerar på ett 128 BitBlock, lika med 16 byte. Som bilden ovan längst upp till vänster skriver vi 16 byte som en 4 av 4 matris. Denna matris fungerar som en datastruktur bra för att blanda data runt., I varje runda är processen följande:

1. vi XOR den runda nyckeln, först (k0), med det aktuella meddelandet
2. då går vi igenom en substitutionsprocess där datablock ersätts med andra block baserat på en given substitutionstabell (bilden ovan (1) ByteSub).
3. vi går igenom ett permutationslager där bitar permuteras och blandas runt(bilden ovan (2) ShiftRow & (3) MixColumn).
4. sedan upprepar vi denna process i 10 rundor.,

bilden ovan kommer du att märka att den sista omgången hoppar över Mix-Kolumnsteget, XOR är resultatet med vår sista runda nyckel och matar ut vår resulterande ciphertext. För att dekryptera vänder vi helt enkelt processen. Kursen erbjuder en hög nivå översikt över denna krypteringsprocess och uppmuntrar eleverna att titta djupare in i det om det är av intresse för dig. Därför kommer jag att lämna AES inre arbeten på detta. Jag skulle rekommendera människor att titta på Fiestel Nätverksproceduren av 3DES för en rolig jämförelse och kontrast av olika blockchiffer.,

När det gäller hårdvara, sedan lanseringen av Intel Westmere, Intel har utformat sina processorer med särskilda instruktioner för AES optimering inbyggd rätt i sin hårdvara och AMD följde efter kort därefter.

blockera chiffer lägen för Operation

Till skillnad från en ström chiffer, ett block chiffer tar bara en fast längd ingång. Självklart vill vi hantera data som är större än 16 byte åt gången. Så nästa är det viktigt att förstå de driftsätt som vi kan använda block ciphers för att kryptera stora uppsättningar data., För att tillämpa detta blockchiffer på en stor datauppsättning kallas det första driftsättet som kan komma att tänka på ”elektronisk kodbok” (ECB). ECB delar helt enkelt data i 16 byte block och utför AES-kryptering enhetligt. Det kan till och med göras parallellt. Mycket snabbt! Men det är faktiskt inte särskilt säkert.

det är osäkert eftersom om ett 16 byte-meddelande upprepar sig, ciphertext kommer också att ha upprepade data., Detta avslöjar information om våra data till en potentiell angripare. Vi kan tillämpa denna sårbarhet på det fall där vi krypterar en bild med ECB. Som du kan se nedan är det klart att vår bild är ett huvudskott. I det kraftigt svarta området kan vi se en silhuett via det mörka håret och skjortan.

det är viktigt att våra krypteringssystem är semantiskt säkra., Semantisk säkerhet är konceptet att om vi har en ciphertext som motsvarar en av två olika plaintexts, kan en motståndare inte gissa med bättre sannolikhet än 1/2 vilket klartext ciphertexten motsvarar. Det är uppenbart att ECB inte är semantiskt säker. Vår krypterade bild ger oss massor av information för att gissa dess motsvarande vanlig bild.

ECB är ett exempel på ett engångstangent arbetssätt (vilket betyder, som engångsplattan, att en nyckel endast kan användas en gång). Ett annat säkrare engångsnyckelläge är deterministiskt motläge. Du är fri att titta på det på egen hand., Jag kommer att gå vidare till de säkra driftsätt som möjliggör många tidstangenter!

chiffer Block Chaining (CBC) är ett arbetssätt som kedjar varje 16-byte block av plaintext tillsammans genom XOR ’ ining chiffer av föregående plaintext i vår nuvarande plaintext innan du utför block cipher kryptering (dvs. AES). Bilden nedan klargör detta koncept:

vi börjar först med en slumpmässig IV-bild.. – herr talman!, IV står för initialiseringsvektor som kan definieras som: det ursprungliga värdet som används för att starta en viss itererad process. När det gäller CBC måste IV vara slumpmässigt (därmed oförutsägbart), varför det måste vara unikt för varje transaktion. Det första blocket i ciphertext är helt enkelt den okrypterade slumpmässiga IV.för att producera resten av ciphertext, först är random IV XOR ’ d med det första blocket av plaintext (m). Resultatet blir då krypterat med rund nyckel k för att returnera det första blocket av krypterad ciphertext (C)., Den ciphertext får sedan XOR ’ d med nästa block av plaintext (m), resultatet krypteras med rund nyckel k och returnerar det andra blocket av krypterad ciphertext (C). Processen fortsätter tills alla block har krypterats.

för att dekryptera, vänder vi bara processen.

en viktig komponent för CBC-kryptering är att random IV är oförutsägbar., Om IV blir förutsägbart blir vårt krypteringssystem sårbart för valda plaintext-attacker. Utvalda Klartext Attack (CPA) är en attack modell som förutsätter att angriparen kan få ciphertexts för godtyckliga plaintexts, och använda dessa för att avslöja information om krypterade meddelanden. Därför behövs en oförutsägbar IV för att säkerställa CPA-säkerhet.

bär med mig här när jag försöker förklara hur denna attack skulle fungera: det är möjligt att utföra en vald plaintext attack i närvaro av förutsägbara IV på grund av xors natur., Om du XOR samma värde tillsammans (0101 rit 0101) det kommer alltid lika 0, därav det avbryter ut. Så om du misstänker att en observerad ciphertext C motsvarar en viss plaintext m kan du testa din hypotes med ett förutsägbart IV. om den aktuella plaintext krypterades med IV1 så att c = e(k, m IV1) kan du skicka in en ny plaintext som ska krypteras och se om du får ett matchande resultat: C. eftersom du kan förutsäga IV kommer att vara IV2, skickar du m IV1 IV2 . , CBC-processen kommer att XOR denna inmatning med nästa IV, IV2 så att: C = E(K, m IV1 IV2 IV2) därmed avbryter IV2, och än en gång krypterar Vi E(K, IV1 m) vilket skulle resultera än en gång med c och om det händer kunde vi gissa vad som tidigare krypterades med IV1.

riktigt fantastiskt jobb om du kom igenom det – ^

med det skulle jag vilja granska ytterligare ett block chiffer-driftsätt som kommer att avsluta den första blogposten i den här 3-delsserien. Om det har varit en stor insats för att göra det så här långt, nu kan vara en bra tid för en snabb paus innan du fortsätter!,

Ok, så vi har granskat ECB, CBC och deras sårbarheter, men slutligen, och förmodligen viktigast av allt kommer jag att introducera Randomized Counter Mode (CTR). Detta är det senaste, säkraste driftsättet, och det är också effektivare än CBC.

Randomized Counter Mode tar också en slumpmässig IV. IV tjänar en olika ändamål här dock. Vår nyckel kombineras (t. ex., via AES) med en itererad version vår IV: ovan fortsätter vi att lägga till 1 till vår IV för varje iteration, annars skulle vi få ett upprepat resultat. Vi gör detta tills vi har en pad så länge som vårt klartext meddelande. Precis som one-time-pad stream chiffer, vi nu XOR vår plaintext meddelande med vår pseudorandom pad att resultera i en chiffertext. Om din hårdvara har flera AES-motorer är detta extremt effektivt eftersom det är parallelliserbart. I CBC berodde varje ciphertext på det tidigare blocket av ciphertext så det var omöjligt att parallellisera.,

vi behöver inte ens nödvändigtvis ett blockchiffer för att kombinera vår IV och nyckel till en pseudorandom pad. Blockchiffer måste vara reversibla. Om du tittar noga på mekaniken i randomiserat motläge märker du att dekryptering inte kräver att vi reverserar F(k, IV). Med tanke på arten av XOR, allt vi behöver göra är att regenerera samma pseudorandom pad och XOR det med vår chiffer. Därför, för att dekryptera, måste vi upprepa operationen, inte vända den.,

Abstrakt talande (hittills har jag undvikit abstrakta begrepp), vilket innebär att det förfarande som vi använder för att kombinera vår hemliga nyckel och IVF(k, IV) måste vara en Pseudorandom funktion (PRF) i motsats till en Pseudorandom Permutation (PRP). Vi har faktiskt tillämpat dessa begrepp i hela denna blogpost. Både PRP och PRF är deterministiska förfaranden som, med tanke på en viss inmatning, resulterar i en pseudorandom-utgång. (dvs AES, XOR). En PRP är dock strängare i den meningen att den måste vara reversibel., Faktum är att termerna PRP och block chiffer (som AES) ofta används synonymt. En PRF behöver dock inte vara reversibel. Om du återvänder till tidigare bilder som visas i det här inlägget förstår du nu notationen PRF och PRP.

som avslutar min översikt över symmetrisk kryptering! Vi täckte stream ciphers och blockera chiffer. Sedan, eftersom blockchiffer endast kan utföras på cirka 16 byte åt gången, täckte vi de driftsätt som användes för att utföra blockchiffer på stora plaintexts. Vi klargjorde också begreppen PRPs vs PRFs.