Cryptopals – Counter = 7 av ?

(Del 1 Del “2” Del 3 (men egentligen 2) Del x (för något x i intervallet 2.5 ≤ x ≤ 4) Del 5+0 Del 6(?))

Välkommen till ännu en del av Simovits Consultings bloggserie om Cryptopals – där vi går igenom och diskuterar olika kryptografiska funktioner och problem som tas upp på sidan cryptopals.com.

Då det kan kännas skrämmande att hoppa rakt in i en sjunde del av en så lång och framgångsrik serie så vill vi passa på att uppmana läsaren att inte oroa sig – vi försöker vara öppna och pedagogiska även för nya läsare – och dessutom så var det troligtvis knappt någon som orkade hänga med i första bloggdelen heller!

Challenge 18: Implement CTR, the stream cipher mode

Bakgrund

I tidigare delar har vi diskuterat olika krypteringsfunktioner:

Caesar-chiffer: Varje tecken modifieras genom en XOR-addition med ett enda tecken. Exempelvis blir krypteringen av texten $\verb!Hejsan!$ med nyckeln $\verb!X!$ följande, uttryckt hexadecimalt: $\verb!Hejsan!\oplus\verb!XXXXXX!=\verb!0x103d322b3936!$
Detta chiffer är ganska lätt att knäcka eftersom det räcker att testa att dekryptera en krypterad text med alla 256 olika varianter av nyckel-tecknet och se vilken av de 256 resultaten som verkar mest rimlig.
(OBS: Klassisk Caesar-chiffer utförs genom klassisk addition modulo alfabetets längd, men här används en version som använder XOR-addition istället och är mer optimerad för dator-tecken).
Vigenère-chiffer: Varje tecken modifieras genom en XOR-addition med en upprepande sträng. Exempelvis blir krypteringen av texten $\verb!Hejsan!$ med nyckeln $\verb!XYZW!$ följande, uttryckt hexadecimalt: $\verb!Hejsan!\oplus\verb!XYZWXY!=\verb!0x103c30243937!$
Notera: Caesar-chiffer är specialfall av Vigenère-chiffer där nyckeln har längd 1.
Svagheten med detta chiffer framkommer då nyckeln är kort i jämförelse med texten som ska krypteras då nyckeln i så fall kommer upprepa sig flera gånger (och problemet kan då reduceras till att knäcka ett system av Caesar-chiffer). Om nyckeln istället är minst lika lång som originaltexten kan denna form av kryptering klassas som perfekt och oknäckbar. Problemet är dock att det är svårt att dela tillräckligt långa nycklar med varandra samtidigt som man håller dessa hemlig för utomstående. Vi har också visat på sårbarheten som uppkommer av att använda samma nyckel för att kryptera olika textsträngar.
AES: En funktion som tar en sträng av längd 16, tillsammans med en nyckel av längd 16 och genererar en 16 tecken lång krypterad sträng. Exempelvis krypteras den 16 tecken långa texten $\verb!Vanilla ICE Baby!$ med lösenordet $\verb!YELLOW SUBMARINE!$ till:
$\text{AES}(\verb!Vanilla ICE Baby!,\verb!YELLOW SUBMARINE!)=\verb!0x139913333bc7843b510361a4b4d14072!$
Denna funktion har genomgått år av tester och anses säker och utan svagheter. Det enda kända sättet att knäcka en AES-krypterad sträng av längd 16 är genom “brute-force”, där man helt enkelt får testa sig igenom alla möjliga nycklar och och se vilken av dessa nycklar som dekrypterar resultatet till något vettigt (vilket inte alltid är helt uppenbart ifall texten som krypterats ej följer någon tydlig standard). Då antalet möjliga nycklar som man måste testa sig igenom är $ 256^{16}\approx 3.4\cdot 10^{38}$ så anses det osannolikt att någon ska kunna knäcka ett 16 tecken långt AES-krypterat-meddelande under den närmaste tidsåldern.

Om AES nu är så perfekt – varför är inte allting säkert? Jo, för att man inte alltid krypterar strängar som har precis längd 16. Metodiken vi har sett för att kryptera strängar av andra längder har gått ut på att först “padda” strängen så att dess längd blir en multipel av 16, sedan dela upp strängen i delsträngar av längd 16 och använda AES på olika sätt på dessa delsträngar vilket resulterar i två olika typer av block-chiffer. Med en sträng av 48 tecken tecken får man 3 delsträngar, $ P = P_1+P_2+P_3$ och de block-chiffer vi studerat tidigare gör följande beräkningar:

ECB: $\text{AES}_{\text{ECB}}(P,K) = \text{AES}(P_1,K)+\text{AES}(P_2, K)+\text{AES}(P_3, K)$
CBC: $\text{AES}_{\text{CBC}}(P,K, IV) = \underbrace{\text{AES}(P_1\oplus IV, K)}_{C_1}+\underbrace{\text{AES}(P_2\oplus C_1, K)}_{C_2}+\underbrace{\text{AES}(P_3\oplus C_2,K)}_{C_3}$
där IV är en slumpad sträng av 16 tecken som ska se till att öka entropin i indatat.

Vi har diskuterat olika sårbarheter med båda dessa block-chiffer, såsom Byte-at-a-Time-dekryptering och Cut-and-Paste-attacker mot ECB, samt Padding-orakel- och Bitflip-attacker mot CBC.

Ström-chiffer

Till skillnad från de block-chiffer som vi just påminde om (AES i ECB- och CBC-läge) ska vi nu introducera en annan typ av chiffer – så kallade ström-chiffer. Dessa ström-chiffer krypterar en text $P$ genom att utföra en XOR-addition av text-strängen med en “nyckelsträng” $ K_S$ med resultatet $ C=P\oplus K_S$. Detta är i princip ett Vigenère-chiffer med nyckeln $ K_S$, men vanligtvis brukar Vigenère-chiffer särskiljas av att de istället använder “kortare” nycklar som återupprepas för att generera hela nyckelsträngen. Läsaren är i denna stund välkommen att uppskatta pedagogiken i varför vi valde att påminna om detta chiffer i bakgrunds-avsnittet ovan.

Som vi diskuterat så är det svårt att utbyta väldigt långa nycklar, så istället har man kommit på idén att använda en kort nyckel som man sedan kan använda för att generera en längre nyckelström. En viktig egenskap hos dessa nyckelströmmar ska vara att de ej ska vara lätta att förutspå och att de ska bestå av alla möjliga tecken utan några uppenbara mönster. Det som önskas är helt enkelt att de i princip ska vara helt slumpmässiga – men samtidigt så måste ju mottagaren kunna generera samma slumpmässiga nyckelström med hjälp utav samma nyckel (för att kunna dekryptera de meddelanden som levererats), så helt slumpmässiga ska de kanske inte vara…

Pseudo-slumptals-generatorer

Det finns två olika typer av slump:

Äkta slump: Genererar utfall som är helt oförutsägbara (såsom sönderfallet av en atom i en isotop).
Pseudo-slump: Genererar utfall som ser ut att genereras av äkta slump, men genereras av förutbestämda regler och går därför att återupprepa.

En pseudo-slumptals-generator är en funktion som tar någon form av indata och genererar en följd av utdata som ser ut att vara slumpmässig.

Exempel

Betrakta funktionen: $ f(x) = 3\cdot x + 2 \text{ (mod 17)}$. Om vi väljer $x_0 = 0$ så kan vi skapa en sekvens:
$ x_1 = f(x_0) = 3\cdot 0+2=2,\quad x_2 = f(x_1) = 3\cdot 2 + 2 = 8,\quad x_3 = f(x_2) = 3\cdot8+2 = 9,\quad \text{etc}$
Detta ger allså en sekvens av tal: 0, 2, 8, 9, 12, 4, 14, 10, … som i alla fall till en början kan se ut att vara slumpmässig (men en djupare analys skulle så klart upptäcka att sekvensen börjar återupprepa sig efter 17 iterationer). Notera att alla som känner till funktionen $f$ och startvärdet $x_0=0$ kan generera samma sekvens. Notera också att om man istället väljer ett annat startvärde $x_0=13$ så fås en annan sekvens: 13, 7, 6, 3, 11, 1, …

Funktionen som tar ett indata $x_0$ och använder $f$ för att generera en sekvens som ovan är ett exempel på en (dålig) pseudo-slumptals-generator.

AES-CTR

Funktionen AES kan användas för att skapa en bättre pseudo-slumptals-generator än den som vi just såg i exemplet. Antag att det finns en funktion $ F(i)$ som tar ett tal och genererar en sträng av 16 tecken. Med en fixerad nyckel $ K$ kan man då skapa en godtyckligt lång sträng: $$K_S = \text{AES}(F(0),K)+\text{AES}(F(1),K)+\text{AES}(F(2),K)+\ldots$$ genom att helt enkelt kryptera $F(i)$ för $i=0,1,2,\ldots$

Ett exempel på funktionen $ F$ skulle kunna vara genom att se en sträng av längd 16 som ett stort tal och helt enkelt skriva indatat $ i $ på den formen:

$F(0) = \verb!0x00000000000000000000000000000000!$
$F(1) = \verb!0x00000000000000000000000000000001!$
$F(2) = \verb!0x00000000000000000000000000000002!$
etc.

För att skapa lite mer entropi i indatat så kan man (precis som i fallet med CBC) använda sig av ett IV för att kunna återanvända en nyckel utan att generera samma slumpström. Som exempel kan vi välja det helt slumpmässigt valda $ IV = \verb!0x1122deadc0de3344!$, och definiera $F(IV,i)$ som:

$F(IV,0) = \verb!0x1122deadc0de33440000000000000000!$
$F(IV,1) = \verb!0x1122deadc0de33440000000000000001!$
$F(IV,2) = \verb!0x1122deadc0de33440000000000000002!$
etc.

I uppgiften från Cryptopals så får man veta att man ska definiera $ F $ genom:

 format=64 bit unsigned little endian nonce,
        64 bit little endian block count (byte count / 16)

Här är “nonce” bara ett annat ord för “IV”, och “little endian” beskriver i vilken ordning som man ska läsa varje byte. Klassiskt sätt så brukar man skriva exempelvis talet “femtusen-trehundra-tjugoett” som 5321 med den ledande 10-potensen längst till vänster, men det är ju enbart en definitionsfråga – man skulle lika gärna kunna skriva det största värdet längst till höger. Att skriva den ledande byten längst till vänster brukar i datorspråk kallas för “big endian”-notation, och att istället ha den ledande byten längst till höger som “little endian”. Den önskade versionen av funktionen $F(IV,i)$ är alltså:

$F(IV,0) = \verb!0x4433dec0eade22110000000000000000!$
$F(IV,1) = \verb!0x4433dec0eade22110100000000000000!$
$F(IV,2) = \verb!0x4433dec0eade22110200000000000000!$
etc.

där man kan se att $i$ inkrementeras på byte-position 9.

Det som vi har gjort nu är alltså att vi skapat ett sätt att generera en godyckligt lång pseudo-slumpad nyckelsträng $K_S$ utifrån en nyckel $K$ och en initieringsvektor $IV$. Den uppmärksamma läsaren tänker möjligtvis nu på det faktum att vi inte förklarat varför nyckelströmmen $K_S$ skulle bestå utav slumpad data som ej går att förutspå eller finna mönster i. Anledningen till varför detta är sant beror på styrkan i AES-funktionen – om det skulle gå att finna mönster i den slumpgenererade strängen så skulle det även finnas svagheter i AES-krypterad data, vilket det inte finns några kända attacker mot.

Med denna definition av nyckelström kan vi nu definiera CTR-läget av AES:

$ \text{AES}_{\text{CTR}}(P,K,IV) = P\oplus K_S,$ där
$K_S=\text{AES}(F(IV,0),K)+\text{AES}(F(IV,1),K)+\text{AES}(F(IV,2),K)+\ldots$ nedkokad till samma längd som $P$.

Namnet CTR är en förkortning av ordet “Counter”, det engelska ordet för “räknare” (för $i=0,1,2,\ldots$).

En trevlig egenskap med AES i CTR-läget är att dekrypteringsfunktionen är detsamma som krypteringsfunktionen. Detta är sant eftersom om $$ C = \text{AES}_{\text{CTR}}(P,K,IV) = P\oplus K_S$$ så är $$ \text{AES}_{\text{CTR}}(C,K,IV) = C\oplus K_S=(P\oplus K_S)\oplus K_S = P.$$

Challenge 19/20: Break fixed-nonce CTR mode

Man får ju anta att AES i CTR-läget bedöms vara en bättre krypteringsalgoritm än de som vi diskuterat i tidigare avsnitt (varför skulle vi annars ta upp den nu efter att vi redan analyserat ECB och CBC). Som med allt rörande kryptering är det dock implementationerna som är de största svagheterna – och ett typexempel på detta ser vi i dessa två uppgifter. I båda dessa uppgifter så har man fått flera strängar som alla krypterats med AES i CTR-läget med samma nyckel och samma nonce/IV, och målet är att försöka dekryptera strängarna utan kännedom om nyckeln. Om man använder samma IV och nyckel så kommer alla strängar $ P_1,P_2,P_3,\ldots$ ha krypterats genom XOR-addition med samma nyckelsträng $ K_S$:

$ C_1 = P_1\oplus K_S$
$ C_2 = P_2\oplus K_S$
$ C_3 = P_3\oplus K_S$
etc

Låt oss börja med att förenkla problemet och anta att alla strängar är lika långa (säg 62 tecken). I så fall kan vi skapa en lång krypterad sträng $ C = C_1+C_2+C_3+\ldots = (P_1\oplus K_S)+(P_2\oplus K_S)+(P_3\oplus K_S)+\ldots$ som vi kan se som krypteringen av strängen $P_1+P_2+P_3+\ldots$ med en nyckelsträng som upprepar sig (var 62:a tecken) – det vill säga, ett Vigenère-chiffer! Detta har vi ju löst tidigare i Challenge 6!

Att alla strängar inte är lika långa är ett enkelt problem att lösa – man börjar med att reducera alla strängar så att de är lika långa som den kortaste, knäcker alla strängar upp till den kortaste längden, sedan filtrerar man bort den kortaste strängen från listan, reducerar alla strängar som är kvar så att de är lika långa som den nu kortaste i listan, knäck and repeat.

Challenge 21: Implement the MT19937 Mersenne Twister RNG

Mersenne-twistern (MT19937) är en klassisk pseudo-slumptals-generator som är implementerad som standard-slump-funktionen i flera programspråk. I denna uppgift är målet att implementera denna, och läsaren uppmanas att göra detta för att få en känsla för hur den är konstruerad.

Även om Mersenne-twistern är snabb och kan se ut att generera slumpmässiga sekvenser så kommer följande uppgifter påvisa att den inte är kryptografiskt säker – med vilket vi syftar på att den ej bör användas för kryptografisk funktionalitet.

Challenge 22: Crack an MT19937 seed

Mersenne-twistern är som sagt en pseudo-slumptals-generator. Den “slumpade” sekvensen av tal som den genererar går alltid att återskapa om man känner till initieringsvärdet. Många som programmerar brukar ofta använda den aktuella unix-tidsstämpeln för att initiera sin Mersenne-twister, vilket är praktiskt eftersom två Mersenne-twisters som initierats med en millisekunds skillnad i så fall kommer generera två helt olika sekvenser.

Exempelvis kan man tänka att någon genererar en sessions-cookie för en hemsida genom att slumpa fram en sträng som genererats av en Mersenne-twister initierad med den aktuella tidsstämpeln. Ser vi något problem med detta? Ja, tänk om någon kan gissa vilket tal som använts för att initiera Mersenne-twistern, då kan de också beräkna den “slumpade” sessions-cookien – vilket vore illa.

Den aktuella unix-tidsstämpeln kan låta som ett vettigt initieringsvärde om man enbart är ute efter att generera unika sekvenser, men det är inte ett bra val om man dessutom inte vill att någon ska kunna förutspå de genererade sekvenserna. Antalet millisekunder som går på en timme är exempelvis bara 3 600 000 stycken – det är inte ett tillräckligt stort tal för att göra en brute-force-attack orimlig.

Challenge 23: Clone an MT19937 RNG from its output

Namnet MT19937 på Mersenne-twistern kommer av att en genererad sekvens inte kommer att börja upprepa sig förrän efter $ 2^{19937}-1$ värden – vilket är ganska mycket. En klar svaghet med Mersenne-twistern är dock att om någon kan få se resultatet av enbart 624 stycken på varandra efterföljande tal i den genererade sekvensen så kan man därefter förutspå alla kommande tal i sekvensen.

Uppgiften går ut på att använda denna svaghet för att skriva kod som klonar en Mersenne-twister, givet 624 på varandra efterföljande värden i dess genererade sekvens.

Challenge 24: Create the MT19937 stream cipher and break it

Anledningen till att Mersenne-twistern passar bra att diskutera i samma bloggdel som AES i CTR-läge är att båda bygger på pseudo-slumptals-generering. Vi nämnde tidigare att varje pseudo-slumptals-generator kan användas för att skapa en nyckelsträng utifrån en nyckel (ett initieringsvärde för slump-funktionen) och Mersenne-twistern är så klart inget undantag. Mersenne-twistern genererar tal som är 32-bit stora, vilket är ekvivalent med 4 bytes – så att generera 10 tal skulle ge en nyckelsträng av längd 40 vilket låter praktiskt.

Baserat på de två tidigare uppgifterna bör läsaren dock känna sig avigt inställd till en krypteringsalgoritm baserad på Mersenne-twistern. Det är exempelvis en otrevlig egenskap att det räcker för en angripare att avläsa/knäcka 624/4 = 156 tecken av nyckelsträngen för att enkelt kunna beräkna resten (oavsett hur lång den är).

Sammanfattning av dagen

Som sammanfattning av dagens bloggdel kan vi säga att vi tittat på tre olika ström-chiffer – där alla är baserade på en underliggande funktion som tar en nyckel och genererar en lång nyckelström:

Vigenère: Tar en nyckel och skapar en nyckelsträng genom att helt enkelt upprepa nyckeln tillräckligt många gånger.
AES i CTR-läge: Tar en nyckel (och ett IV) och genererar en nyckelsträng genom att använda nyckeln för att AES-kryptera ett 16 tecken långt block som inkrementeras med 1 vid varje kryptering.
Mersenne-twister-kryptot: Tar en nyckel (ett tal) och genererar en lång sekvens av tal som kan skrivas om till en sträng av bytes.

AES i CTR-läge anses vara en bra krypteringsalgoritm, men är – som allt annat – sårbar för dåliga implementeringar och felaktig användning (vilket vi redan såg ett exempel på, och kommer få se fler i kommande delar). Slutligen vill vi återigen poängtera att Mersenne-twistern har flera svagheter och det rekommenderas att aldrig använda den i kryptografiska sammanhang.

För att ge läsaren något att minnas här i slutet: Här kommer ett helt slumpmässigt tal: 17.
Det var väl häftigt och chockerande!? Visste ni förresten att 17 är det minst/mest slumpmässiga talet? Det är fint.

Tack för idag!

 Publicerat 2022-03-18 Skrivet av Gustav Sædén Ståhl