Cryptopals – del 3 (men egentligen 2) av ?

(Del 1 Del ”2”)

Nu är det dags för nästa del i vår (nu fullt etablerade) bloggserie om cryptopals! I denna tredje del kommer vi fortsätta där vi slutade i del 1 och – för tillfället – lägga informationen om elliptiska kurvor från förra avsnittets avstickare på hyllan. Vi återkommer till elliptiska kurvor i bloggseriens N:te del för något stort tal N. Författaren ber i förväg om ursäkt för mängden matematik, den dåliga formateringen, och bristen på skämt.

Del 1 avslutades med att vi tittade på Challenge 5. I denna uppgift skulle man implementera Vigenère-chiffret. För att påminna läsaren om hur denna kryptering går till ger vi här en snabb beskrivning:

Implementeringen av Vigenère-chiffret på datorn görs med hjälp av byte-vis XOR, vilket helt enkelt reduceras till komponentvis addition i . Om texten man ska kryptera är längre än nyckelordet kan man göra på olika sätt – cryptopals väljer att återupprepa nyckelordet om och om igen.

Exempel: Om vi vill kryptera texten SIMOVITS med nyckel ABC börjar vi med att utvidga nyckeln till rätt längd:

SIMOVITS
ABCABCAB

Den krypterade texten blir då resultatet av operationen “SIMOVITS” XOR “ABCABCAB”. Resultatet av denna operation är en ny sträng där första byten är ”S” XOR ”A”, den andra byten är ”I” XOR ”B”, etc. Det är inte helt lätt att skriva ut en läsbar version av denna sträng, då den ej består av några skrivbara tecken. Varje byte i denna sträng har nämligen ASCII-värden mellan 10 och 21 – och dessa bytes motsvarar operationer såsom ”line feed”, ”tab” och ”shift out”. Detta är dock inget problem för en dator som inte ser någon större skillnad på dessa tecken och de skrivbara tecknen som vi kan läsa på skärmen. Vi dödliga får istället använda oss av exempelvis hexadecimal notation (som vi gick igenom i del 1) för att uttrycka resultatet av “SIMOVITS” XOR “ABCABCAB” som ”120b0e0e140a1511”.

Hur som helt, nu är vi redo för nästa utmaning!

Challenge 6: Break repeating-key XOR

Denna uppgift går ut på att dekryptera en text som krypterats med Vigenère-chiffret, utan att känna till krypteringsnyckeln. Vi ska alltså knäcka denna kryptoalgoritm! Uppgiften ger följande förslag på hur man kan gå tillväga:

Lista ut hur lång nyckeln är.
Reducera problemet att knäcka Vigenère-chiffret till att istället knäcka flera ”enklare” Ceasarchiffer.
Lös varje Ceasarchiffer var för sig.

Låt oss förklara detta angripssätt i lite mer detalj.

Antag att man har en lång krypterad text, som vi kallar för C (crypto text). Denna text är krypteringen av någon klartext P (plain text) med en nyckel K (key). Vi vet alltså att C = P XOR L, där P är klartexten vi är ute efter och L är strängen K upprepad för att göra den lika lång som P.
Ex:

P = SIMOVITS
K = ABC
L = ABCABCAB
C = P XOR L = (S XOR A)(I XOR B)(M XOR C)(O XOR A)(V XOR B)(I XOR C)(T XOR A)(S XOR B)

För att lösa ut P behöver vi först lista ut hur lång nyckeln K är. Varför är det intressant? Låt oss förklara med hjälp av vårt exempel:

Eftersom K=”ABC” har längd 3 ser vi att var tredje byte i P har krypterats med samma byte i nyckeln:

S I M O V I T S 
A B C A B C A B

S, O, T har alla krypterats med A.
I, V, S har alla krypterats med B.
M, I, har alla krypterats med C.

Vi skapar nu de 9 nya strängarna:

P1 = SOT - första + fjärde + sjunde byten av P.
P2 = IVS - andra + femte + åttonde byten av P.
P3 = MI - tredje + sjätte byten av P.

C1 - första + fjärde + sjunde byten av C.
C2 - andra + femte + åttonde byten av C.
C3 - tredje + sjätte byten av C.

L1 = AAA - första byten av K upprepad 3 gånger.
L2 = BBB - andra byten av K upprepad 3 gånger.
L3 = CC - tredje byten av K upprepad 2 gånger.

Då gäller att:

C1 = P1 XOR L1 = SOT XOR AAA
C2 = P2 XOR L2 = IVS XOR BBB
C3 = P3 XOR L3 = MI XOR CC

Detta är tre stycken Ceasarchiffer!

I exemplet ovan använde vi oss av vi kände till P och K, men notera att vi skulle kunna utfört denna ommöblering av bokstäver om vi enbart kände till C och längden på nyckeln K. Alltså, om vi har en krypterad text C och längden på krypteringsnyckeln K så kan vi dela upp vårt Vigenère-chiffer i ett antal Ceasarchiffer – lika många som längden på nyckeln – och dessa kan lösas med tekniken vi lärde oss i Challenge 3. Sedan behöver vi bara möblera tillbaka bokstäverna i lösningarna av dessa P1, P2, etc, för att återskapa P.

Det återstår bara ett problem. Vi känner ju fortfarande inte till vad nyckeln K är, och speciellt vet vi inte hur lång den är. Men, det går att lista ut!

Som läsaren kanske har märkt har vi ofta undvikit att skriva ut innehållet i vår sträng C från vårt återkommande exempel – då den består av icke skrivbara tecken. Att C inte består av skrivbara tecken är faktiskt inte så konstigt, eftersom både P och K har valts att innehålla skrivbara tecken, och alla skrivbara tecken är ihopklumpade efter varandra i ASCII-tabellen. Det vill säga att de skrivbara tecknen har ganska lika ASCII-värden, vilket i sin tur innebär att de ofta har 1:or och 0:or på ungefär samma plats i sina binära representationer. Exempelvis:

S har ASCII-värde 84 vilket binärt är 01010011
A har ASCII-värde 65 vilket binärt är 01000001

Beräkning av ”S” XOR ”A” = 01010011 XOR 01000001 går i praktiken ut på att enbart skriva 1:or på de positioner där precis en av de två karaktärerna har en 1:a, och 0:or överallt annars. Enklaste sättet att se detta är kanske att skriva dessa två tal över varandra:

S XOR A =
01010011 XOR
01000001 =
00010010

00010010 har ASCII-värde 18, vilket motsvarar den inte så jättekända karaktären ”Device Control 2” (ej skrivbar).

Poängen här är inte att XOR av två skrivbara tecken ej är skrivbart i allmänhet – poängen är istället att skrivbara tecken ofta har 1:or på samma positioner, vilket i sin tur innebär att XOR av två skrivbara tecken ofta har få 1:or men många 0:or i sin binära representation.

Hammingavståndet mellan två tecken är definierat som antalet 1:or i den binära representationen av deras XOR-summa. Det vi försökte säga i vårt babblande ovan är alltså att Hammingavståndet mellan två skrivbara tecken ofta är litet (i jämförelse med Hammingavståndet av två godtyckliga tecken som i snitt bör vara ~4). Puh.

På samma sätt gäller att Hammingavståndet mellan två strängar definieras som antalet 1:or i den binära representationen av XOR-summan av strängarna. Hammingavståndet mellan två strängar som består av enbart skrivbara tecken är av samma anledning som ovan också ofta litet (i jämförelse med Hammingavståndet av två godtyckliga strängar).

Nu kanske läsaren kommer med den rimliga invändningen: Jaha, vadårå?

Jo, det ska jag berätta!

Låt oss anta att vi har en lång krypterad text där vi använt notationen att små bokstäver representerar individuella bytes i strängen. Vi vet att C = P XOR L för någon klartext och någon sträng . Dessutom vet vi att L upprepar sig:

där är en nyckel av okänd längd n.

Med vår kunskap från ovan kan vi faktiskt gissa oss fram till vad n är!
Antag att nyckeln har längd u för något tal u. Då kan vi titta på delsträngarna och och beräkna Hammingavståndet mellan dem. XOR-summan av dessa strängar blir en sträng av längd u. Första byten i denna sträng är . Eftersom

får vi att

Det gäller alltid att , och notera att om vi gissar rätt på längden, det vill säga om u=n, så gäller det även att , vilket innebär att:

och alltså att (om u=n)

På samma gäller, om u=n, att , , och så vidare. Med andra ord, om u=n, så blir
C’ XOR C” = P’ XOR P”
där P’ och P” är delsträngar av klartexten P. Med antagandet att klartexten som vi började med består av skrivbara tecken (som har små Hammingavstånd mellan varandra) så gäller det alltså att om vi gissade rätt med u=n så är Hammingavståndet mellan C’ och C” oftast mindre än avståndet mellan två godtyckliga strängar.

Genom att beräkna Hammingavståndet mellan C’ och C” för massa olika värden på u, så kan vi till slut få fram det u som gett minst Hammingavstånd, och därför också den troligaste kandidaten för nyckellängden.

Slutkommentar: Det klassiska Vigenère-chiffret (ej för datorer) använder sig inte av addition i , utan av addition i – och där fungerar inte denna metod att leta efter icke skrivbara tecken. Istället får man använda sig av mer komplicerad statistik (så som att identifiera återkommande delsträngar, osv) – så ifall man vet att klartexten består av skrivbara tecken blir det faktiskt enklare att knäcka XOR-implementation för Vigenère-chiffret än i det klassiska exemplet. Ifall klartexten istället består av tecken från hela ASCII-intervallet blir detta angripssätt däremot inte lika effektivt.

Challenge 7 – AES in ECB mode

I denna uppgift ska man dekryptera en text med hjälp av AES-128 i ECB-mode och en känd nyckel. De föreslår att man kan använda sig av open-ssl:s AES-implementation, men det känns som fusk. Syftet med den här bloggserien är ju att försöka förstå saker. Låt oss därför istället implementera AES från grunden! Men för att kunna göra det så vill man ju först förstå vad den gör. Låt oss därför gräva ner oss i väldigt obetydliga detaljer – och samtidigt försöka reda ut om det finns någon hemlig bakdörr i algoritmen (som vissa konspirationsteorier hävdar).

Vi har hittills enbart implementerat krypteringsalgoritmer som bygger på additionen i . Om man vill göra en mer ”komplicerad” krypteringsalgoritm vore nästa logiska steg, rent matematiskt, vara att använda en mer ”komplicerad” operation än addition. Exempelvis multiplikation!

Additionen i såg vi var enkel att definiera som den komponentvisa additionen i varje -komponent. För att få en multiplikation med vettiga egenskaper funkar det dessvärre inte att definiera även den komponentvis (överkurs: leder till existens av nolldelare och resulterar i ett icke-integritetsområde).

Matematiskt babbel och handviftande (läsaren är välkommen att skippa): En ”kropp” är i matematiken en struktur vari man kan addera och multiplicera, och där båda dessa operationer har bra egenskaper (så som inverterbarhet). En Galoiskropp är en kropp med ändligt många element. Ett exempel på en sådan är kroppen med 2 element GF(2)= där multiplikationen är klassisk multiplikation modulo 2 (GF = Galois field).
Det finns massa häftiga satser om dessa kroppar, exempelvis:

Det existerar en Galoiskropp med n element när n är ett primtal eller en potens av ett primtal.
Två Galoiskroppar med lika många element är (i princip) lika med varandra – de är isomorfa.

Eftersom 256=2^8 är en potens av ett primtal finns det en Galoiskropp GF(256) med just 256 element. Ett sätt att definiera denna kropp är som mängden av polynom med 0 och 1 som koefficienter, och med kravet att . Matematiskt kan detta skrivas:

Exempel på element i GF(256) är:

Det finns precis 256 olika sådana polynom. Varför finns det inte oändligt många? Jo, för att så fort som ett polynom har en term som har högre potens än 7 så går den att reducera. Exempel:

Nästa naturliga fråga: Vad tusan har det här struntet med någonting att göra?

Jag kommer till det! Koefficienterna för alla dessa 256 polynom kan paras ihop med alla de 256 olika binära representationer av ASCII-tecken. Exempel: S kan binärt skrivas 01010011, och detta kan vi para ihop med polynomet

Vi kan också multiplicera två polynom som vanligt, och varje term i produkten som har en potens högre än 7 reducerar vi på samma sätt med hjälp av kravet:

Dessa polynom kan alltså användas för att definiera en multiplikation på .

The Advanced Ecryption Standard (AES) är en krypteringsalgoritm som år 2001 fastställdes av NIST som den standardiserade krypteringsmetoden för datorer. Valet av AES är en intressant historia där många olika algoritmer tävlade mot varandra, och vann gjorde en variant av en algoritm vid namn Rijndael – numera känd som AES (även om Rijndael i grunden är mer generellt definierad). Den intresserade läsaren uppmanas att googla efter mer infomation.

Algoritmen kan handviftande beskrivas som följer:
Tag en sträng med 16 tecken och en nyckel som också består av 16 tecken. (Ja, 16 tecken är ett krav – hur man använder AES för att kryptera andra längder på strängar förklarar vi i nästa uppgift)

AES krypterar då P med nyckeln K genom att utföra följande (extremt luddiga och oprecisa) algoritm:

Låt C = P XOR K
Byt ut alla tecken i C mot andra tecken.
Placera de 16 tecknen i C i en 4×4-matris.
Blanda runt i varje rad i matrisen.
Modifiera varje kolumn i matrisen.

Alla som blandat en kortlek någon gång vet att det (med största sannolikhet) blir en bättre oordning ju mer man blandar. I analogi med detta så gör vi om stegen ovan flera gånger – 11 gånger för att vara exakt! För att få lite extra säkerhet används inte samma K i varje blandning, utan först utvidgas K till 11 stycken strängar av längd 16 (och varje sträng används i precis en omgång).

1) Utvidga nyckeln:

Detta görs genom en iterativ process där man utför operationer – cyklisk rotation, tecken-substitution, och en XOR-operation – på ord (4-bytes-delsträngar av nyckeln) för att skapa nya ord, som i sin tur används för att skapa ännu fler ord, och så vidare tills 44 stycken genererats.

Den cykliska rotationen flyttar varje tecken i ett ord ett steg åt vänster (cykliskt). Teckensubstitutionen använder sig av en 16×16-substitutionstabell som beskriver vad varje tecken ska bytas ut mot för nytt tecken (vi återkommer till detta nedan). XOR-operationen använder sig av den nu invanda additionen i tillsammans med diverse konstanter. Dessa konstanter är definierade utifrån representationen av elementen i GF(256).

Nu när nyckeln är utvidgad så utförs resten av blandningen – här nedan beskriver vi detta i mer detalj.

2) Byt ut alla tecken i C mot andra tecken:

Vi börjar med att förklara hur detta är definierat. Låt c vara ett tecken i strängen C. Tecknet c kan, som vi beskrivit tidigare, representeras av ett polynom p i .

Varje polynom (utom 0) har en invers, och vi kallar detta polynom för . Att enbart ta inversen är dock en för trivial algebraisk operation, så därefter utförs en affin transformation som kan beskrivas, i termer av polynom-multiplikation, som

Polynomet man får som resultat av beräkningen ovan svarar mot en binär representation av något ASCII-tecken, vilket definieras som substitutionen för tecknet c. Från denna beskrivning kan man generera en 16×16-tabell som kan användas istället för att utföra dessa beräkningar varje gång. Det är denna tabell som det syftades på i nyckelutvidgningen ovan.

3) Blanda runt i varje rad i matrisen.

Efter dessa substitutioner har vi en ny sträng bestående av 16 tecken, och vi skriver dessa i en matris:

I jämförelse med resten så är denna del ganska enkel. Man roterar cykliskt raderna i matrisen som följer:

4) Modifiera varje kolumn i matrisen

Detta steg tyckte författaren av denna bloggtext var den mest komplicerade när författaren skrev sin egna AES-implementation, men oroa er inte – vi är snart klara! I detta steg börjar vi med en matris på formen (vi numrerar om indexen på tecknen för att förvirra så mycket som möjligt):

Varje element i denna matris motsvarar en byte, som kan representeras som ett polynom i GF(256). Vi kan nu gå ett steg längre i vår abstraktionsnivå och betrakta varje kolumn i matrisen som ett element i polynomringen

Kul va?! Variabeln T är här godtyckligt vald för att inte misstas för variabeln x för polynom i GF(256).

Exempelvis kan man skriva den första kolumnen som

Blandningen i denna fas går ut på att multiplicera var och en av de fyra polynomen man får från de fyra kolumnerna med det fixerade polynomet

och använda sig av både multiplikationen i och, för koefficienterna, multiplikationen i .

Finns det en bakdörr i AES?

AES-algoritmen är, som vi sett, åtminstone inte uppenbart trivialt. Alla komplicerade matematiska strukturer, operationer, och val av konstanter, har inspirerat till flera konspirationsteorier om att det finns någon hemlig bakdörr i algoritmen som är obfuskerad av all komplexitet. Eftersom vi börjat få en ganska bra förståelse för de olika delarna så kan vi ju lite snabbt försöka leta efter en sådan. Vårt letande får gå ut på att försöka förstå varför de olika valen av konstanter och relationer har gjorts:

Så, varför valdes:

för definitionen av GF(256)? Eftersom alla kroppar med 256 element är isomorfa så hade man ju kunnat välja vilket annat irreducibelt polynom av grad 8 som helst här… Misstänkt!
Förklaring: Skaparna av Rijndael använde sig av boken Introduction to finite fields and their applications (1986), av R. Lidl and H. Niederreiter, som uppslagsbok när de studerade Galoiskroppar, och detta polynom var det första i den bokens lista över irreducibla polynom av grad 8. Okej, det får vi väl acceptera!
som den affina transformationen? Det finns ju jättemånga olika val av affina transformationer… Misstänkt!
Förklaring: relationen var den enklast möjliga. Polynomet var polynomet som hade enklast beskrivning och samtidigt var koprimt till (och därför inverterbart). Konstanten valdes så att fixpunkter undveks. Det är även noterat i Rijndael-dokumentationen att man är välkommen att byta ut denna affina transformation mot något annat om man hellre vill det. Okej, vi släpper denna också.
för kolumn-beräkningen? Finns massa andra val av polynomringar? Misstänkt!
Förklaring: Relationen är återigen det enklaste möjliga för användsområdet. Acceptabel motivering.
som den konstanta produkten i kolumn-beräkningen? Finns återigen massa olika val, misstänkt!
Förklaring: koefficienterna 0, 1, x, x+1 är de fyra minsta och enklaste elementen i GF(256) – och det optimerar beräkningshastigheten hos datorn. Dessutom har dessa koeffiencenter valts så att den följande linjära transformationen har ett maximalt ”branch number” – som i princip innebär att små förändringar i indatat propagerar sig och ger stora skillnader i utdatat. Detta får ju anses vara en bra egenskap hos en kryptoalgoritm. Vi köper nog detta också.
konstanterna i beräkningen för nyckelutvidgningen? Finns ju massa olika konstanter att välja… Misstänkt!
Förklaring: Enklast möjliga valen… Vi köper det! (speciellt eftersom författaren av denna blogg börjar bli trött)

Förklaringarna som getts ovan går att hitta (med högre detaljrikedom) här, och då vi inte lyckats hitta något misstänkt får vi nog komma fram till att det inte finns någon bakdörr…

Det som återstår nu är enbart själva implementationen, och lämnas som övning till läsaren.

För övrigt, om någon läsare fortfarande är vaken (vilket känns högst osannolikt) kanske den undrar varför vi inte diskuterat någonting om ECB-mode som nämndes i uppgiftsbeskrivningen. Vad det är, och varför det är dåligt, går vi igenom i nästa Challenge – men det får bli i nästa del av denna helt absurda bloggserie. Spänningen är olidlig!

 Publicerat 2020-05-22 Skrivet av Gustav Sædén Ståhl