Simovits

Cryptopals – Del 8 av ?

(Del 1 Del “2” Del 3 (men egentligen 2) Del x (där 2.5 ≤ x ≤ 4) Del 5+0 Del 6(?) Del Counter=7)

Det är sant. Till slut så kom det en ny del i denna så beryktade bloggserie. För att undvika att upprepa sig och stagnera så väljer vi att frångå traditionerna och undvika alla former av skämt i denna introduktion. Istället ämnar vi oss att vara helt gravallvarliga. (Tillägg: författaren insåg precis innan publicering att han råkade vara rolig mot sin vilja då detta blev en fin hyllning till den högtid som sammanföll med publiceringen av denna blogg. Ursäkta.)

I den förra delen av bloggserien så introducerade vi bland annat krypteringsalgoritmen AES i CTR-läge, vilket är en algoritm som många förespråkar. Vi visade även att om man är oförsiktig och återanvänder initeringsvärdet för algoritmen så kan en angripare utnyttja detta för att knäcka ens krypterade text. Som alltid är alltså algoritmen väldigt beroende av hur den implementeras. I denna blogg går vi igenom ett par andra exempel på implementationsmisstag av AES i CTR-läge i syfte att påvisa att man inte ska sova allt för gott bara bara för att den underliggande algoritmen är säker.

Vi avslutar även med att gå igenom ännu en implementationsmiss för AES i CBC-läget som vi diskuterat tidigare.

Challenge 25: Break “random access read/write” AES CTR

Låt oss börja med att påminna oss om vad AES i CTR-läge är för något.

Det man behöver ta med sig från detta är att den krypterade texten \(C=P\oplus K_S\) ges av att man tar originaltexten och slår samman den (XOR) med en nyckelsträng (som är hemlig för alla som inte känner till \(K\) och \(IV\)). Låt oss ta ett enkelt exempel. Säg att \(P=p_1p_2p_3p_4p_5p_6=\verb!gustav!\) och att \(K_S=k_1k_2k_3k_4k_5k_6=\verb!hejsan!\) (utan att bry oss om de faktiska värdena på \(K\text{ och }IV\)). Då har vi att den krypterade texten är: $$C=P\oplus K_S = p_1p_2p_3p_4p_5p_6\oplus k_1k_2k_3k_4k_5k_6=c_1c_2c_3c_4c_5c_6=\verb!0x0f1019070018!$$ eftersom

Kom också ihåg att $$C\oplus K_S = (P\oplus K_S)\oplus K_S = P\oplus(K_S\oplus K_S) = P\oplus 0 = P$$ så dekryptering görs på samma sätt (beräkna XOR-summan med nyckelsträngen) som kryptering.

En intressant egenskap med hur denna krypteringsalgoritm är uppbyggd är att man kan dekryptera specifika delar av en krypterad text \(C\) utan att behöva bry sig om texten runt omkring. Om man till exempel vill dekryptera delsträngen \(\verb!0x101907!\) från position 2 till 4 i exemplet ovan \(C=\verb!0x0f1019070018!\) så räcker det att beräkna delsträngen av \(K_S\) på position 2 till och 4 (“ejs”) och få $$ P_{2-4}=C_{2-4}\oplus K_{S,2-4}=\verb!0x101907!\oplus\verb!ejs!=\verb!ust!.$$

Denna uppgift tänker sig följande scenario:

  1. Vi har en lång text \(P=p_1p_2\ldots p_n\) som har krypterats med AES i CTR-läge med en okänd nyckel och ett okänt IV till en krypterad sträng \(C=c_1c_2\ldots c_n\). Låt oss exempelvis tänka oss att texten är en stor databas. Den krypterade texten/databasen är åtkomlig för alla.
  2. En programmerare vill tillåta folk att kunna uppdatera data på olika positioner i texten/databasen (låt oss anta att positionerna för vissa data är fixerade och kända) och har därför skrivit en funktion EDIT som:
    • tar som input en position \(i\) och ett nytt tecken \(p’\),
    • uppdaterar \(C\) genom att
      • räkna ut det \(i\):te elementet \(k_i\) i nyckelströmmen, och
      • byter ut \(c_i=k_i\oplus p_i\) mot \(c’_i = k_i\oplus p’\).

Med andra ord, \(EDIT(i,p’)=C’=c_1c_2\ldots c_{i-1}c’_ic_{i+1}\ldots c_n\). Användare kan alltså inte läsa i texten/databasen då allting är krypterat, men har möjlighet att ändra i databasen genom den exponerade funktionen EDIT.

Låt oss för stunden ignorera att det låter väldigt dumt att exponera sin databas så att vem som helst kan göra vilka ändringar som helst i den. Vi får försöka tänka oss att det enda viktiga i detta scenario är att användare inte har möjlighet att läsa vad som stod i databasen ursprungligen… Författaren av denna blogg har inte riktigt lyckats komma på ett realistiskt scenario för detta, men om en läsare har en bra idé så får de gärna höra av sig!

Nu är frågan, räcker det med denna exponerade funktion för att få ut den underliggande texten/databasen \(P\)? Svaret är ett rungande JA. Hur? Jo, spara först en kopia av den krypterade texten/databasen \(C\) och låt oss fundera över vad som händer om vi väljer \(p’=\verb!0x00!\) (tecknet med ASCII-värde 0). För en godtycklig position \(i\) gäller då att \(c’_i=k_i\oplus p’=k_i\), så om vi använder EDIT-funktionen för att uppdaterar varje position i den underliggande texten/databasen till ASCII-värde 0 så kommer den resulterande krypterade texten/databasen vara lika med $$C’=k_1k_2k_3\ldots k_n=K_S$$ vilket är nyckelsträngen som användes för att kryptera originaltexten! Vi kan därefter ta vår sparade kopia av den krypterade texten och få \(C\oplus C’=C\oplus K_S=P\).

Eftersom blogg-författaren inte har lyckats ge något rimligt scenario där detta kan ske i verkligheten så är lösningen kanske inte särskilt spännande för läsaren, men det påvisar åtminstone att AES i CTR-läge kan vara rejält sårbart om man läcker information om nyckelsträngen.

Challenge 26: CTR bitflipping

Vi såg i den förra uppgiften att AES i CTR-läge kan vara sårbart om man inte är försiktig med vad för information som man exponerar till användarna. Men hur är det med exempelvis bitflipping-attacken som vi studerade i Challenge 16? Där såg vi att AES i CBC-läget är sårbart mot denna typ av angrepp, men om nu AES i CTR-läge anses så bra så kanske den är mer motståndskraftig? Svaret är nej, CTR-läget är faktiskt ännu mer sårbart eftersom attacken blir ännu enklare att åstadkomma…

Låt oss börja med att ge en enklare beskrivning av scenariot:

Målet med uppgiften är att skapa en krypterad sträng som returnerar TRUE om man stoppar in den i funktionen \(G\). Detta kan låta trivialt, men vi vet två andra saker:

För att se ett försök till en förklaring till hur detta kan detta kan förekomma i verkligheten så hänvisas läsaren till den sjätte delen av denna bloggserie (se länkarna högst upp på denna sida). Där kan man även läsa hur man går runt denna restriktion om krypteringsalgoritmen är AES i CBC-läge. Lösningen där är ganska jobbig då man måste hålla koll på hur de olika blocken samverkar under kryptering/dekryptering. Här är det mycket enklare!

Låt oss anta att vi vet hur långa de två strängarna \(P_1\) och \(P_2\) är (det lämnas annars som en övning för läsaren att tänka ut hur man bestämmer dessas längder givet funktionen \(F\)). Låt nu \(P=\verb!AadminBtrue!\). Stoppar vi in detta i funktionen \(F\) får vi en krypterad sträng \(C=c_1c_2\ldots c_n\)där vi enkelt kan beräkna positionerna för krypteringen av tecknen \(\verb!A!\) och \(\verb!B!\) från vår klartext (eftersom vi vet längderna av \(P_1\) och \(P_2\)). Kalla dessa två positioner för \(i\) och \(j\) så att \(c_i=\verb!A!\oplus k_i\) och \(c_j=\verb!B!\oplus k_j\) där \(k_i,k_j\) är de \(i\):te och \(j\):te elementen i nyckelsträngen.

Låt nu \(c’_i=c_i\oplus\verb!A!\oplus\verb!”;”!\) och \(c’_j=c_j\oplus\verb!B!\oplus\verb!”=”!\), sätt $$C’=c_1c_2\ldots c_{i-1}c’_{i}c_{i+1}\ldots c_{j-1}c’_jc_{j+1}\ldots c_n$$ och stoppa in denna sträng i funktionen \(G\). Dekrypteringen av \(C’\) kommer vara lika med dekrypteringen av \(C\) överallt förutom i positionerna \(i\) och \(j\). På dessa positioner får man istället $$c’_i\oplus k_i=(c_i\oplus\verb!A!\oplus\verb!”;”!)\oplus k_i=\bigl((\verb!A!\oplus k_i)\oplus\verb!A!\oplus\verb!”;”!\bigr)\oplus k_i=(\verb!A!\oplus\verb!A!)\oplus(k_i\oplus k_i)\oplus\verb!”;”!=0\oplus0\oplus\verb!”;”!=\verb!”;”!$$ och $$c’_j\oplus k_j=(c_j\oplus\verb!B!\oplus\verb!”=”!)\oplus k_j=\bigl((\verb!B!\oplus k_j)\oplus\verb!B!\oplus\verb!”=”!\bigr)\oplus k_j=(\verb!B!\oplus\verb!B!)\oplus(k_j\oplus k_j)\oplus\verb!”=”!=0\oplus0\oplus\verb!”=”!=\verb!”=”!.$$ Den dekrypterade strängen kommer alltså innehålla den önskade delsträngen \(\verb!;admin=true!\) och vi är klara. Magi!

Challenge 27: Recover the key from CBC with IV=Key

Denna uppgift går tillbaka till CBC-läget av AES (gissningsvis kom författarna till cryptopals på denna uppgift i efterhand, då den egentligen hade passar bättre tidigare när vi faktiskt pratade om CBC). Denna uppgift går ut på att visa att det är en risk att välja initeringsvektorn \(IV\) till att vara lika med krypteringsnyckeln \(K\).

Vad händer om \(IV=K\)? Jo, antag att vi har en text som består av tre 16-bytes-block \(P=P_1+P_2+P_3\) som krypterats via AES i CBC-läge till \(C=C_1+C_2+C_3\). Då gäller alltså att

Från den första av dessa kan vi göra lite beräkningar och få ut att $$K=P_1\oplus ADS(C_1,K)$$ där \(ADS\) är vårt icke-officiella namn på inversen av \(AES\). Så, om vi känner till \(P_1\) och \(ADS(C_1)\) så kan vi få ut krypteringsnyckeln \(K\) direkt.

Man ska notera att uppgiften är lite missvisande (eller snarare skriven som en rubrik till en Aftonbladet-artikel som försöker vara sensationell och dra till sig klick) då den faktiskt inte visar att man kan knäcka krypteringsalgoritmen direkt bara för att \(IV=K\). Istället visar den att risken för att krypteringen kan knäckas har ökat och att det räcker med endast en ytterligare svaghet för att knäcka hela systemet.

I denna uppgift så antar vi nämligen att det finns en ytterligare svaghet i form av att ett orakel. Kom ihåg från tidigare delar i bloggserien att ett orakel är en funktion som på något sätt läcker information om krypteringsalgoritmen. I detta fall ska vi betrakta ett orakel som tar som input en krypterad text och ifall den dekrypterade texten innehåller höga ASCII-värden (tecken med ASCII-värde större än 127) så returnerar den hela den dekrypterade strängen. Det låter kanske lite konstlat, men man kan tänka sig detta scenario:

function(cipher):
    plain = decrypt(cipher, secret_key, secret_iv)
    if high_ascii_check(plain):
        logging.error("Something went wrong, see plain text for debugging: "+plain)    
    etc

Om man tänker sig att denna funktion körs i en webbläsare och att loggningen skrivs direkt i webbläsaren (vilket inte känns som en orimlig klantighet från en utvecklare…) så skulle en angripare kunna använda denna funktion som ett sådant orakel.

Låt oss anta att vi som angripare har åtkomst till följande:

  1. Krypteringstexten av åtminstone 3 block \(C=C_1+C_2+C_3\) (utan att känna till originaltexten \(P=P_1+P_2+P_3\)).
  2. Ett orakel såsom det som beskrivits ovan.

Målet är alltså att få ut den okända krypteringsnyckeln \(K\). Detta kan nu enkelt fås genom att skicka in texten \(C’=C_1+0+C_1\) (där \(0\) är en sträng med 16 stycken tecken med ASCII-värde=0) till oraklet. Varför då? Jo, oraklet börjar med att dekryptera \(C’\) och får: $$P’=P_1’+P_2’+P_3’$$ där

Notera nu att \(P’_1=P_1\) och \(P’_3=ADS(C_1,K)\) är precis vad vi behöver för att beräkna krypteringsnyckeln \(K\) eftersom vi såg att \(K=P_1\oplus ADS(C_1,K)\) om \(K=IV\). Men frågan är om oraklet kommer returnera dessa värden till oss… Kom ihåg att oraklet enbart returnerar den krypterade texten ifall den hittar ett högt ASCII-värde i den dekrypterade strängen. Vi vet också att \(P_1’=P_1\) inte innehåller några höga ASCII-värden, men strängen \(P_2’+P’_3\) består av 32 i princip slumpade tecken. Sannolikheten att ett tecken har ett högt ASCII-värde är 50% (=128/256) så sannolikheten att minst ett av de 32 slumpade tecknen har ett högt ASCII-värde blir alltså \(1-\frac{1}{2^{32}}\approx 0.999999999\%\). Vi bör därför rimligen kunna anta att oraklet faktiskt kommer returnera den dekrypterade texten \(P’=P_1’+P_2’+P’_3\) till oss, vilket ger $$K=P_1’\oplus P’_3.$$

Sammanfattning

I detta blogginlägg har vi sett tre stycken exempel på hur sårbar en (säker) krypteringsalgoritm såsom AES i CTR- eller CBC-läge kan vara om man använder algoritmen på fel sätt. Det man ska ta med sig är kanske helt enkelt att alltid tänka efter tjugoelva extra gånger innan man tror sig göra något smart vad gäller kryptering. Det var allt för denna gång!

Publicerat 2022-11-04 Skrivet av Gustav Sædén Ståhl