Cryptopals – del x (för något x i intervallet 2.5 ≤ x ≤ 4) av ?

(Del 1 Del “2” Del 3 (men egentligen 2))

Välkomna tillbaka till allas vår favoritbloggserie! Detta är alltså en bloggserie om krypteringsuppgifterna som finns tillgängliga på cryptopals.com. Tanken med bloggen är inte att gå igenom konkreta programmeringsmässiga lösningar av problemen, utan istället ge en mer generell förklaring/beskrivning av problemet och möjliga lösningar.

En av de otaliga läsarna av denna bloggserie påminde nyligen författaren om att den senaste bloggposten (del 3) slutade mitt i Challenge 7, så beroende på hur man väljer att räkna så kan man se detta som del 3.5 (?), men eftersom den förra egentligen var del 2 så blir det svårt att numrera… Låt oss helt enkelt säga att denna del ligger någonstans i intervallet [2.5, 4]. För att göra numreringen ännu mer komplicerad kommer vi i dagens blogg välja att fokusera på problem kopplade till ECB, och lämna uppgifterna om CBC till ett separat framtida inlägg.

Nog med dröjsmål, låt oss sätta igång!

Challenge 7: AES in ECB mode (fortsättning)

I den förra posten i denna helmysiga bloggserie förklarade vi detaljerna i hur krypteringsalgoritmen AES (Advanced Encryption Standard) fungerade. Om någon ny läsare dyker upp i denna post behöver ni dock inte oroa er. Det var nog ingen som riktigt lyssnade/läste förra gången! Det enda vi egentligen behöver veta om AES är att det är en funktion som tar en textsträng på 16 tecken, och en lika lång nyckel, och producerar en krypterad sträng av längd 16. Nedan har vi ett fabricerat exempel:

Exempel: AES(”Här är 16 tecken”, nyckel) = ”sK¨d%lsa73@1&gt;”

Nyckeln här är också en sträng som består av 16 tecken – exempelvis ”YELLOW SUBMARINE” som är den de använt i uppgiften.

Nu har vi alltså lärt oss att kryptera och allt är perfekt!

Men det vore ju bra om man kunde dekryptera texten också… Vilket man såklart kan göra! AES går nämligen att göra baklänges (varje matematisk funktion som den använder är inverterbar). Låt oss vara lite galna och kalla dekrypteringsvarianten/baklängesvarianten av AES för ”ADS” (Advanced Decryption Standard). Notera att detta inte är något officiellt namn utan är enbart ett påhittat namn för denna bloggpost. AES och ADS ger kryptering/dekryptering med samma nyckel – en så kallad symmetrisk kryptering (till skillnad från asymmetrisk kryptering som förekommer i exempelvis RSA).

Nu vet vi alltså att man kan använda AES för att både kryptera och dekryptera texter. AES är helt enkelt en utmärkt krypteringsalgoritm… när man vill kryptera exakt 16 tecken. Det visar sig att i verkligheten är det faktiskt sällan som textsträngar består av precis 16 tecken. Vad gör man då?! En lösning är att man använder AES i olika “lägen”. Ett sådant läge är ECB (Electronic Code Book).

Detta kommer visa sig vara en väldigt dålig lösning, men är pedagogiskt trevlig.

Exempel: Låt oss ta följande textsträng: ”Här är 16 tecken och här 16 till”. Denna textsträng består av 32 tecken, och av en ren slump råkar 32=16+16. Vi kan alltså dela upp vår 32 tecken långa sträng i två stycken ”block” med 16 tecken i varje. Vi använder nedan tecknet + för konkatenering av textsträngar (och konkatenering är bara ett fint ord för ”lägga ihop”). Med andra ord:

”Här är 16 tecken och här 16 till” = ”Här är 16 tecken” + ” och här 16 till” = Block1 + Block2

där

Block1 = ”Här är 16 tecken”
Block2 = ” och här 16 till”

Låt oss fortsätta fabricera lite resultat, och säga att:

AES(Block1, nyckel) = ”sK¨d%lsa73@1&gt;”
AES(Block2, nyckel) = ”e^{bu¤Ie4w($\pi$”

För att kryptera hela strängen kan vi helt enkelt använda AES på vardera block och sedan lägga ihop resultatet!

AES_ECB(”Här är 16 tecken och här 16 till”, nyckel) = 

AES_ECB(”Här är 16 tecken" + " och här 16 till”, nyckel) = 

AES_ECB(Block1 + Block2, nyckel) = 

AES(Block1, nyckel) + AES(Block2, nyckel) = 

”sK¨d%lsa73@1&gt;”  +  ”e^{bu¤Ie4w($\pi$” =

”sK¨d%lsa73@1gt;e^{bu¤Ie4w($\pi$”

Och hur gör man för att dekryptera? Jo, samma sak fast med ”ADS” istället!

ADS_ECB(”sK¨d%lsa73@1&gt;e^{bu¤Ie4w($\pi$”, nyckel) = 

ADS(”sK¨d%lsa73@1&gt;”, nyckel) + ADS(”e^{bu¤Ie4w($\pi$”, nyckel) =

”Här är 16 tecken”              + ” och här 16 till” =

”Här är 16 tecken och här 16 till”

Cryptopals-uppgiften går ut på att man ska dekryptera en text som visar sig vara 2880 tecken lång. Av en händelse är 2880 = 16 * 180, så vi kan dekryptera denna text genom att dela upp den i 180 stycken block och utföra ADS på vardera, och sedan lägga ihop de 180 blocken till en lång text-sträng. Enkelt!

Challenge 8: Detect AES in ECB mode

Vad händer om vi nu skulle använda AES i ECB-läge för att kryptera texten
”Här är 16 tecken och här 16 till och här 16 till”?

Denna sträng är 48 = 16 + 16 + 16 tecken lång, så vi kan dela in denna i tre stycken block. Notera att det i detta fall innebär att block 2 och block 3 är identiska! Låt oss använda tecknet | för att visuellt representera de olika blocken. Vi kan alltså skriva vår sträng som en summa av blocken:
”|Här är 16 tecken| och här 16 till| och här 16 till|” = Block1 + Block2 + Block2
När vi krypterar detta med AES i ECB-läge fås:

AES_ECB(”Här är 16 tecken och här 16 till och här 16 till”, nyckel) =

AES(Block1, nyckel) + AES(Block2,nyckel) + AES(Block2, nyckel) =

"sK¨d%lsa73@1&gt;" + "e^{bu¤Ie4w($\pi$" + "e^{bu¤Ie4w($\pi$" =

"sK¨d%lsa73@1&gt;e^{bu¤Ie4w($\pi$e^{bu¤Ie4w($\pi$"

Den krypterade textsträngen består alltså av tre block, där de två sista blocken är identiska. ECB-läget har alltså den lite sämre egenskapen att om identiska block förekommer i original-texten så kommer (krypterade) identiska block även förekomma i den krypterade texten. I en lång text där någon specifik fras förekommer ofta (exempelvis ”Gustavs bloggar är alltid så bra!” som säkerligen är en fras folk använder ofta) kan man, genom att söka efter identiska block, undersöka ifall en text är krypterad i ECB-läge eller inte.

Ett klassiskt exempel på denna sämre egenskap i ECB kan man se när man försöker kryptera en bitmap-bild av pingvinen Tux (loggan för Linux):

Till vänster ser vi bilden i originalskick, i mitten ser vi bilden krypterad med AES i ECB-läge, och till höger ser vi ett önskat krypteringsresultat. (Bilderna tagna från: ECB på wikipedia)

Anledningen till varför man fortfarande kan se pingvinen efter att man krypterat med ECB är för att bilden består av massor av bytes, och ECB delar en dessa i jättemånga block av storlek 16 (där de flesta blocken kommer vara identiska) och krypterar varje block separat. Detta innebär att ECB-krypteringen i princip enbart klumpar ihop delar av bilden, men egentligen inte påverkar bilden i det stora hela. Exemplet med denna pingvin hänvisas även till i en senare cryptopals-uppgift som återkommer slutet av detta inlägg.

Det man ska göra i uppgift 8 är att leta igenom ett antal krypterade texter och identifiera de som är krypterade med ECB. Som vi förklarat ovan kan alltså detta göras genom att leta efter identiska block i kryptotexten.

Nu är vi klara med ”Set 1” av cryptopals – hurra! Men ingen tid att fira, istället börjar vi med ”Set 2” direkt!

Challenge 9: Implement PKCS#7 padding

En uppmärksam läsare kan möjligtvis ha noterat ett annat problem med ”lösningen” att kryptera texter med AES i ECB-läge… Det kan ju faktiskt hända att texten man vill kryptera inte har en längd som är en multipel av 16. Vad gör man då? Ger upp? Nej! Man paddar texten! Ordet ”paddar” är inte helt korrekt svenska, men en översättning av det engelska ordet ”padding” blir typ ”stoppning/vaddering/fyllning” vilket låter lite fult i författarens öron.

Padding av en textsträng görs helt enkelt genom man fyller ut det sista blocken av strängen med tecken så att den blir precis så lång som man vill ha den (i vårt fall: 16 tecken lång).

Ex: Strängen ”Antal: elva” består av 11 tecken och en möjlig padding av denna textsträng till längd 16 kan göras genom att lägga till 5 stycken punkter så som ”Antal: elva.....”

Denna form av padding är dock inte optimal eftersom det ju även måste vara möjligt för en mottagare av texten att ta bort paddingen. I detta fall är det inte uppenbart för någon som inte sett originaltexten om punkterna motsvarar padding – eller om de är en del av texten (kanske försökte texten insinuera en pinsam tystnad?)

Som tur är finns det bättre varianter av padding. Eftersom vi jobbar med datorer har vi hela 256 olika tecken som vi kan använda för paddingen, och en standard är något som kallas PKCS#7-padding (PKCS = Public Key Cryptography Standards). Vi förklarar denna standard med ett exempel.

Exempel: Strängen ”Antal: elva” består av 11 tecken, så för att padda den till längd 16 läggs det på
16-length(”Antal: elva”) = 16-11=5
tecken, och tecknet vi väljer för padding är precis det som motsvaras av ASCII-värdet 5. Nu är det så att ASCII-värdet 5 inte är något skrivbart tecken men vi kan (från del 1 av denna bloggserie) komma runt detta genom att använda hexadecimal notation och skriva \x05 för detta tecken (där prefixet \x använts för att påvisa notationen).
Alltså: PKCS#7(”Antal: elva”, 16) = ”Antal: elva\x05\x05\x05\x05\x05”

I allmänhet gäller följande för en sträng s:

Låt a = length(s) mod 16
Då är PKCS#7(s, 16) lika med strängen s konkatenerad med a stycken bytes med ASCII-värdet a.

Vad händer om blocket man ska padda redan har längd 16? Jo, då tänker man att sig att det finns ett tomt sista block som behöver fyllas ut med 16 stycken \x16-bytes.

Uppgiften går ut på att implementera denna typ av padding.

Challenge 10: Implement CBC-mode

Vi såg redan i uppgift 8 att ECB-läget har en del brister, och ett bättre läge för att kryptera längre texter är det så kallade CBC-läget. Som vi skrev i introduktionen av denna bloggpost väljer vi dock att skjuta upp beskrivningen av CBC för att istället kunna fokusera helt på ECB denna gång. Denna uppgift lämnas alltså till framtiden.

Challenge 11: An ECB/CBC detection oracle

I denna uppgift ska man skriva en funktion som kan identifiera om en text har krypterats med ECB eller inte. Vi lämnar även denna för framtiden, eller så noterar vi helt enkelt att detta i princip redan gjorts i uppgift 8…

Challenge 12: Byte-at-a-time ECB decryption (Simple)

Nu är det dags för att faktiskt försöka knäcka något! Vi såg i uppgift 8 att ECB-läget har sina svagheter, men vi har än så länge inte visat att man faktiskt kan knäcka en text krypterad med ECB.

Låt oss ta följande aningen onaturliga och konstruerade (men förhoppningsvis motiverande) exempel:

På sidan https://www.?????.com finns en resurs som man kan komma åt via ett hemligt lösenord (”Sommar2020”). De bakom sidan har dock gjort det möjligt att logga in utan vetskap av lösenordet genom att man enbart fyller i ett användarnamn (exempelvis ”exempel@simovits”).

Deras lösning är att i backend konkatenera namnet med lösenordet till den nya strängen ”exempel@simovitsSommar2020”, sedan kryptera denna sträng med AES i ECB-läge (med en för oss hemlig AES-nyckel). Slutligen uttrycker de det krypterade resultatet i bas 64 (exempelvis: RHUgdGp1dmtpa2FkZSEgQmFyYSBldHQgZXhlbXBlbC4=).
Användaren omdirigeras sedan till
https://www.?????.com/ RHUgdGp1dmtpa2FkZSEgQmFyYSBldHQgZXhlbXBlbC4=
där tjänsten man vill nå kan dekryptera denna sträng och verifiera att den dekrypterade texten slutar med lösenordet Sommar2020.

Antag att vi fått vetskap om metoden som backend använder, men att vi inte känner till det hemliga lösenordet. Ifall vi är elaka skurkar (eller snälla penetrationstestare) vill vi såklart ta reda på det hemliga lösenordet då lösenordet kanske kan användas till andra saker. Det kan vara chockerande att höra, men det händer faktiskt att folk använder samma lösenord till flera olika tjänster!

Så, hur ska man gå till väga för att få ut det hemliga lösenordet? För att förstå det så måste vi börja med att studera vad som händer i backend när vi skriver in vårt användarnamn. Vi använder här nedan tecknet | för att visualisera de olika blocken (av längd 16) som strängarna består av:

Backend börjar med att konkatenera användarnamnet och lösenordet till en text:
Text = exempel@simovitsSommar2020 = |exempel@simovits|Sommar2020
I nästa steg paddas det sista blocket:
Paddad_text = PKCS#7(Text, 16) = |exempel@simovits|Sommar2020\x06\x06\x06\x06\x06\x06|
Sedan krypteras den paddade texten:
AES_ECB(Paddad_text) = AES(exempel@simovits) + AES(Sommar2020\x06\x06\x06\x06\x06\x06)
Slutligen kodas resultatet i bas 64 och den resulterande strängen läggs in i URL:en.

Eftersom vi kan se strängen i URL:en så kan vi bas64-avkoda den för att direkt se resultatet av krypteringen i punkt 3 (punkt 4 är med andra ord reversibel så vi ignorerar den framöver). Som angripare har vi alltså tillgång till krypteringen av det hemliga lösenordet AES(Sommar2020\x06\x06\x06\x06\x06\x06). Vi har ju tidigare hävdat att AES i sig är en bra krypteringsalgoritm, och eftersom vi inte har tillgång till AES-nyckeln så det är inte rimligt att tro att vi kan knäcka AES-algoritmen för att kunna extrahera originaltexten Sommar2020\x06\x06\x06\x06\x06\x06.

Om vi är lite smarta kan vi dock skriva in lite olika användarnamn i originalfältet för att modifiera vilken text som krypteras!

Knäcka det första tecknet i lösenordet

Om vi istället för exempel@simovits skriver in exempel@simovitsAAAAAAAAAAAAAAA med 15 stycken A – vad händer då i backend?

Backend börjar med att konkatenera användarnamnet och lösenordet:
Text = exempel@simovitsAAAAAAAAAAAAAAASommar2020 = |exempel@simovits|AAAAAAAAAAAAAAAS|ommar2020
Sedan paddas det sista blocket:
Paddad_text = PKCS#7(Text, 16) = |exempel@simovits|AAAAAAAAAAAAAAAS|ommar2020\x07\x07\x07\x07\x07\x07\x07|
Sedan krypterar den:
AES_ECB(Paddad_text) =
AES(exempel@simovits) + AES(AAAAAAAAAAAAAAAS) + AES(ommar2020\x07\x07\x07\x07\x07\x07\x07)

Tjoho! Vi lurade backend att ge oss krypteringen av strängen AAAAAAAAAAAAAAAS (men notera att vi egentligen inte vet vad det sista tecknet i denna sträng är). Låt oss definiera MÅL = AES(AAAAAAAAAAAAAAAS). Nu tänker kanske läsaren att det inte känns så imponerande eller meningsfullt… Men! Det viktiga här är att vi känner till de första 15 tecknen (15 ’A’) som krypterats i denna sträng eftersom vi själva valt dem.

Nu väljer vi användarnamnet exempel@simovitsAAAAAAAAAAAAAAAX med 15 stycken A och en variabel X som vi låter variera (och alltså inte betyda tecknet ’X’) – vad händer då?

X=A:

Backend börjar med att konkatenera användarnamnet och lösenordet:
Text = exempel@simovitsAAAAAAAAAAAAAAAASommar2020 = |exempel@simovits|AAAAAAAAAAAAAAAA|Sommar2020
Sedan paddas det sista blocket:
Paddad_text = PKCS#7(Text, 16) = |exempel@simovits|AAAAAAAAAAAAAAAA|Sommar2020\x07\x07\x07\x07\x07\x07\x07|
Sedan krypterar den:
AES_ECB(Paddad_text) = AES(exempel@simovits) + AES(AAAAAAAAAAAAAAAA) + AES(Sommar2020\x06\x06\x06\x06\x06\x06)

Det vi tar med oss från detta är att vi nu känner till krypteringen av strängen ”AAAAAAAAAAAAAAAA”.

X=B:

Backend börjar med att konkatenera användarnamnet och lösenordet:
Text = exempel@simovitsAAAAAAAAAAAAAAABSommar2020 = |exempel@simovits|AAAAAAAAAAAAAAAB|Sommar2020
Sedan paddas det sista blocket och krypterar:
AES_ECB(Paddad_text) = AES(exempel@simovits) + AES(AAAAAAAAAAAAAAAB) + AES(Sommar2020\x06\x06\x06\x06\x06\x06)

Det vi tar med oss från detta är att vi nu känner till krypteringen av strängen AAAAAAAAAAAAAAAB.

X=C:

På samma får vi ut resultatet av AES(AAAAAAAAAAAAAAAC)

X=D:

På samma får vi ut resultatet av AES(AAAAAAAAAAAAAAAD)

etc.

Genom att låta X variera kan vi alltså få ut krypteringen av strängarna AAAAAAAAAAAAAAAX för alla 256 val av X. Precis en av dessa 256 val av X kommer leda till en krypterad sträng som är lika med strängen MÅL vi fick ovan – AES(AAAAAAAAAAAAAAAS) – nämligen den där X=S!

Genom att ändra längden på användarnamnet kan vi alltså forcera positionen för starten på det hemliga lösenordet, och på så sätt reducera problemet från 256¹⁶ olika kombinationer (256 alternativ för varje byte i nyckeln med längd 16), ner till bara 256 kombinationer (256 alternativ för det sista tecknet i strängen). Även för en dator är 256¹⁶ ett ganska stort tal, men 256 är å andra sidan väldigt litet och går att forcera nästintill momentant.

Vad har vi egentligen åstadkommit? Jo, vi har ju fått fram det första tecknet i det hemliga lösenordet! Vad är nästa steg? Knäcka det andra tecknet!

Knäcka det andra tecknet

Välj användarnamnet exempel@simovitsAAAAAAAAAAAAAA med 14 stycken A (ett A färre än tidigare).

Backend konkatenerar användarnamnet och lösenordet:
Text = exempel@simovitsAAAAAAAAAAAAAASommar2020 = |exempel@simovits|AAAAAAAAAAAAAASo|mmar2020

Och krypterar:
AES_ECB(Paddad_text) =
AES(exempel@simovits) +
AES(AAAAAAAAAAAAAASo) +
AES(mmar2020\x08\x08\x08\x08\x08\x08\x08\x08

Vi forcerade alltså backend att ge oss krypteringen av den för oss okända strängen AAAAAAAAAAAAAAASo. Eftersom vi redan knäckt det första tecknet i det hemliga lösenordet (S), så vet vi att denna sträng börjar med AAAAAAAAAAAAAAS och att det sista tecknet är nästa tecken i lösenordet. Låt oss definiera MÅL2 = AES(AAAAAAAAAAAAAASo).

Nu väljer vi användarnamnet exempel@simovitsAAAAAAAAAAAAAASX med 14 stycken A, det S som vi knäckte tidigare, och en variabel X som vi låter variera:

X=A:

Backend konkatenerar användarnamnet och lösenordet:
Text = exempel@simovitsAAAAAAAAAAAAAAASASommar2020 = |exempel@simovits|AAAAAAAAAAAASA|Sommar2020

Och krypterar:
AES_ECB(Paddad_text) = AES(exempel@simovits) + AES(AAAAAAAAAAAAAASA) + AES(Sommar2020\x06\x06\x06\x06\x06\x06)

X=B:

På samma sätt får vi ut AES(AAAAAAAAAAAAAASB)

etc.

Genom att låta X variera kan vi alltså få se krypteringen av AAAAAAAAAAAAAASX för alla 256 val av X. Precis en av dessa 256 val av X kommer leda till en krypterad sträng som är lika med strängen MÅL2 som vi definierade tidigare – AES(AAAAAAAAAAAAAASo) – nämligen den för X=o!

Genom att fortsätta så här kan vi få ut lösenordet, en byte i taget.

För att utföra denna attack i praktiken är det lite tekniska detaljer som måste lösas. Om det hemliga lösenordet är längre än 16 tecken så behöver man exempelvis börja attacken med 16n+15 stycken A (för något n) för att ha tillräckligt utrymme att translatera startpositionen av lösenordet. Eftersom man inte vet lösenordet så vet man heller inte hur långt det är, men detta är enkelt att ta reda på (det är bara att testa med olika användarnamn som ökar med ett i längd varje gång och undersök när den krypterade texten ökar från exempelvis 32 till 48 – det vill säga när ett nytt block läggs på).

Nu återstår bara själva implementation – vilket lämnas till läsaren.

This is the first challenge we’ve given you whose solution will break real crypto. Lots of people know that when you encrypt something in ECB mode, you can see penguins through it. Not so many of them can decrypt the contents of those ciphertexts, and now you can. If our experience is any guideline, this attack will get you code execution in security tests about once a year.
– cryptopals.com

Detta blir den sista uppgiften vi hinner med idag. Nästa inlägg i denna serie kommer förhoppnings beröra de återstående uppgifterna om ECB, samt beskriva CBC (och då kan vi även göra en kort utsvävning och beskriva sårbarheten Zerologon som blev allmänt känd för cirka en månad sedan). Men det får som sagt bli i nästa bloggpost. På återseende!

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