Simovits

Cryptopals – del 6(?) 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)

Hej, alla barn, nu blir det barnprogram! Nej, detta var en lögn. Hoppas inte att någon läsare hann bygga upp några extrema barnprogramsförväntningar nu – för i så fall väntar nog en besvikelse. Det är nämligen bara dags för nästa del i den spännande följetongen om Cryptopals! Ah, dubbel-luring, det är ju typ lika bra som ett barnprogram! Låt oss inte förlänga denna komiska introduktion allt för länge, utan låt oss istället sätta igång med uppgifterna!

Challenge 16: CBC bitflipping attacks

Vi har tidigare implementerat CBC-läget för AES-kryptering. En påminnelse för den glömske:

Om man vill kryptera en sträng \(P = P_1+P_2+P_3\) som består av 3 delsträngar av längd 16 så görs detta genom: \(\text{AES}_{\text{CBC}}(P, K, IV) = C_1+C_2+C_3 \) där

Dekryptering görs på följande sätt (där ”ADS” är vårt icke-standard-namn för inversen av ”AES”):

I tidigare uppgifter har vi sett hur osäkert det blir om man använder ECB-läget för AES. Detta CBC-läge gör i alla fall att identiska klartext-delsträngar krypteras till olika chiffertexter (genom att man blandar in IV:t och tidigare chifferblock i varje kryptering). Så CBC är mycket säkrare än ECB. Betyder det att man kan luta sig tillbaka och förlita sig på att CBC löser alla problem? Svaret är (så klart): Nej. Det är vad denna uppgift kommer visa.

Låt oss dock, innan vi börjar med själva uppgiften, försöka ge lite motivation och bakgrund. Antag att vi har ett webb-formulär:

När man klickar på ”Skicka” så kommer servern att parametrisera denna information, exempelvis som:

{
    sys_data : e3deadc0de9a,
    username : gustav,
    email    : gss@simovits.com,
    color    : orange,
    tmnt     : Michelangelo,
    moreinfo : En%20ko%20har%207%20sidor%3B%20sju%3Dsex%2Bett
}

Här antar vi att det finns fördefinierade kodord för varje fält. Vi antar dessutom att det kan finnas annan information som servern sparar (i exemplet ovan är detta exemplifierat med fältet ”sys_data : e3deadc0de9a”) som användare ej har möjlighet att påverka.

Notera att innehållet i fältet ”moreinfo” ser lite konstigt ut. Anledningen är att servern har valt att URL-koda alla speciella tecken som förekommer i varje fält. Denna kodning går ut på att byta ut tecken mot deras ASCII-värde (uttryckta hexadecimalt med ett procenttecken framför). Exempel:

Varför väljer man att göra texten lite oläslig? Jo, för att man vill kunna skicka denna information vidare och då vill man skriva saker kompakt. Ett kompaktare sätt att skriva ner all data från formuläret är som en lång URL-sträng:

sys_data=e3deadc0de9a;username=gustav;email=gss@simovits.com;color=orange;tmnt=Michelangelo;moreinfo=En%20ko%20har%207%20sidor%3B%20Sju%3D6+1

Istället för att separera fälten på olika rader så separeras varje fält med ett semikolon, och nyckelordet följt av ett lika-med-tecken beskriver informationen i varje fält. Om informationen i fälten inte skulle URL-kodas så skulle informationen själv kunna innehålla semikolon samt lika-med-tecken, vilket skulle innebära att parsningen av denna sträng skulle kunna bli tvetydig. Tänk exempelvis att fälten inte skulle URL-kodas och att någon då valde att skriva in detta under ”Övrig information”:

URL-strängen skulle då bli:

sys_data=e3deadc0de9a;username=gustav;email=gss@simovits.com;color=orange;tmnt=Michelangelo;moreinfo=;admin=true

vilket skulle parsas till:

{
    sys_data : e3deadc0de9a,
    username : gustav,
    email    : gss@simovits.com,
    color    : orange,
    tmnt     : Michelangelo,
    moreinfo : ,
    admin    : true
}

Servern skulle alltså parsa denna sträng, se att admin=true och, beroende på applikation, kanske ge användaren admin-behörigheter till tjänsten. Att skapa ett fält med admin=true är en hackares önskedröm. För att motverka detta är det alltså smart att URL-koda den data som skrivs in i alla fält.

I säkerhetssyfte så antar vi alltså att när en användare klickar på ”Skicka” i formuläret så skapas den URL-kodade strängen:

sys_data=e3deadc0de9a;username=gustav;email=gss@simovits.com;color=orange;tmnt=Michelangelo;moreinfo=En%20ko%20har%207%20sidor%3B%20Sju%3D6+1

Men vad händer sedan då? Ofta kan användaren, efter att ha klickat på ”Skicka”, automatiskt redirectas till URL’n:

https://www.someurl.com/app?sys_data=e3deadc0de9a;username=gustav;email=gss@simovits.com;color=orange;tmnt=Michelangelo;moreinfo=En%20ko%20har%207%20sidor%3B%20Sju%3D6+1

där den mottagande applikationen kan parsa innehåller i URL-strängen och ta in information om användaren därifrån. Ser vi något problem med detta? Om läsaren inte ser ett problem så rekommenderas att läsa nästa mening. Ja, det finns ett problem – om användaren redirectas till denna adress så måste användaren själv ha åtkomst till URL’n, vilket innebär att användaren själv kan manipulera innehållet i den. Exempelvis kan användaren lägga till ”;admin=true” i slutet av strängen. Ånej! Vad vi än gör så kan skurkarna hitta vägar att ta sig runt det.. (sad face)

Men titta där uppe i skyn! Där kommer kryptering för att rädda oss! Vi kan nämligen låta den första servern ta strängen 

sys_data=e3deadc0de9a;username=gustav;email=gss@simovits.com;color=orange;tmnt=Michelangelo;moreinfo=En%20ko%20har%207%20sidor%3B%20Sju%3D6+1

och kryptera med en okänd nyckel. Antag att krypteringen av denna stäng blir: 

SpsdhsaKsdusCMLSp(#%SJSkWL!DbskSsUsdbwemysqlHseoefbOS)rb#jDsm¤!!hDGD

så att användaren redirectas till URL’n:

https://www.someurl.com/app?SpsdhsaKsdusCMLSp(#%SJSkWL!DbskSsUsdbwemysqlHseoefbOS)rb#jDsm¤!!hDGD

Om den mottagande servern känner till den hemliga krypteringsnyckeln så kan strängen dekrypteras och därefter kan servern parsa innehållet av texten, precis som förut. Eftersom användaren inte känner till den hemliga nyckeln så ska inte användaren kunna modifiera innehållet i texten. Perfekt! Vilken kryptografisk algoritm ska vi använda: AES i CBC-läge. Ånej…

Det visar sig att det är möjligt att modifiera den underliggande texten i en CBC-krypterad sträng till att bli precis vad vi vill, utan att känna till den hemliga nyckeln.

Låt oss nu börja med den egentliga uppgiften för att exemplifiera detta. I denna uppgift ska vi tänka oss följande scenario. Det finns en sida på internet där man som användare får skriva in någon form av information (låt oss skriva in texten ”elftiett”). Den text som skrivits in URL-kodas, och läggs därefter in mellan de två textsträngarna:

comment1=cooking%20MCs;userdata=   och    ;comment2=%20like%20a%20pound%20of%20bacon

och skapar den långa strängen:

comment1=cooking%20MCs;userdata=elftiett;comment2=%20like%20a%20pound%20of%20bacon

Denna sträng är alltså bara ett kompakt sätt att skriva följande:

{
   comment1 : cooking MCs,
   userdata : elftiett,
   comment2 :  like a pound of bacon
}

Därefter så krypterar servern texten genom AES i CBC-läge med en hemlig nyckel. Vi kan alltså se hela flödet som en funktion i vilken man skriver in en sträng (elftiett) och får ut en krypterad sträng. Målet är att skapa en krypterad sträng som dekrypteras till en sträng innehållandes ”;admin=true;”.

Uppgiften är väldigt snäll i den mening att strängen:

comment1=cooking%20MCs;userdata=

är precis 32 tecken lång. Den del av texten som vi kan manipulera är alltså placerad precis i början av det tredje 16-bytes-blocket. Den attack som vi nu ska utföra är troligtvis lättare att förstå direkt från ett exempel. Låt oss därför skriva in texten ”AadminAtrue” i vårt manipulerbara fält. Vi vet då att \( P = P_1 + P_2 + P_3 + P_4 +P_5 \) där

Därefter vet vi att \( P\) krypteras med en hemlig nyckel samt ett IV och skapar \( C = C_1+C_2+C_3+C_4+C_5\) där

Låt oss nu modifiera det andra chifferblocket \(C_2 = c_{2,1}c_{2,2}c_{2,3}\ldots c_{2,16}\) genom att byta ut det första tecknet \(c_{2,1}\) i denna sträng mot tecknet

\( \quad\quad\quad\quad\gamma_{2,1} = c_{2,1}\oplus p_{3,1} \oplus ”;”\)

där \(p_{3,1}=\verb!A!\) är det första tecknet i \(P_3\). Vi skriver \(C_2^\prime = \gamma_{2,1}c_{2,2}c_{2,3}\ldots c_{2,16}.\)

Den nya chiffersträngen \(C^\prime = C_1+C_2^\prime+C_3+C_4+C_5\) är precis vad vi är ute efter! Varför då!? Jo, för om servern försöker dekryptera \(C^\prime\) händer följande:

Notera att \(P_1, P_4 \text{ och }P_5\) kommer se ut som vanligt, men att \(P_2^\prime \text{ och }P_3^\prime\) blivit modifierade. Block nummer två, \(P_2\), kommer bara bestå av nonsens-tecken (vilket servern troligtvis kommer ignorera), men det intressanta är block nummer 3:

\( P_3^\prime = ADS(C_3,K) \oplus C_2^\prime = (P_3 \oplus C_2) \oplus C_2^\prime \)

Eftersom XOR-addition av strängar sker tecken för tecken (och eftersom \(C_2^\prime\) enbart skiljer sig åt i första tecknet) så kommer \(P_3 = \verb!AadminAtrue;%20l!\) och \(P_3^\prime\) vara identiska i alla tecken utom det första. För det första tecknet gäller:

\(p_{3,1}^\prime = (p_{3,1}\oplus c_{2,1}) \oplus \gamma_{2,1} = (p_{3,1}\oplus c_{2,1}) \oplus (c_{2,1}\oplus p_{3,1} \oplus ”;”) = ”;”\)

Vi har lyckats byta det första tecknet i \(P_3\) (ett ”A”) mot precis vad vi ville (ett ”;”)! När servern dekrypterar \(C^\prime\) kommer den alltså få att

\(P_3^\prime = \verb!;adminAtrue;%20l!\)

Man kan nästan höra hur utvecklaren säger: ”Dumma jobbiga matematiker…”.

Genom insikt i strukturen på vad som är krypterat är det alltså möjligt att modifiera en krypterad text till vad man vill på ett kontrollerat sätt (genom att förstöra tidigare block i strängen). I detta fall hade vi full insyn i hur servern utförde krypteringen (vi saknade bara den hemliga nyckeln), men även utan insyn i hur mycket data som läggs på före och efter texten kan man beräkna detta genom ”smarta” val av text man ber funktionen att kryptera. Vi ignorerade denna generalisering i beskrivningen ovan eftersom det är själva ”bit-flippandet” (modifieringen av enskilda bytes/bits) som ansågs intressant.

Hur man ska modifiera \(C_2^\prime\) för att även kunna byta ut det 7:e tecknet i \(P_3\) mot ett ”=” lämnas till läsaren.

Challenge 17: The CBC padding oracle

I den förra uppgiften så hade vi själva möjligheten att modifiera delar av klartexten och på sätt skapa chiffersträngar som vi ville ha. Detta kan man inte alltid förvänta sig. Vad händer om vi istället får en fixerad CBC-krypterad sträng \(C\) som vi vill försöka knäcka. Låt oss bygga upp ett nytt scenario:

Fantisera ihop att det finns en klientapplikation i vilken man kan köpa och spela spel online. Låt oss kalla denna applikation för ”Ånga”. Antag att man, får att få åtkomst till ”Ånga”, måste autentiserar sig mot en server via användarnamn och lösenord. När man väl är inloggad så kan man be servern att man ska bli ihågkommen. Då gör servern följande:

Om någon skulle kunna komma över den krypterade strängen så skulle man alltså behöva knäcka krypteringen för att kunna komma åt personens lösenord – och om det inte går att knäcka så är det ingen fara att någon annan ser denna sträng. Frågan blir då om den krypterade strängen går det att knäcka? Svaret är troligtvis nej, om inte tjänstens utvecklare klantat sig och byggt sina krypteringsfunktioner på ett hafsigt sätt. Ska vi anta, för detta fantiserade exempel, att utvecklarna skrivit perfekta implementationer av alla funktioner? Nej, det ska vi inte.

Som den uppmärksamma läsaren kan gissa så bygger detta scenario på ett verkligt exempel rörande speltjänsten Steam. Några förenklingar har gjorts i beskrivningen ovan, men sammanfattningsvis så råkade Steam läcka information vilket en angripare kunde utnyttja för att skapa ett paddingorakel – och därigenom knäcka användares CBC-krypterade lösenord.

Så, vad är ett paddingorakel?

Till att börja med så ska vi påminna oss om hur klartexter som ska krypteras i ECB- eller CBC-läge måste paddas för att ha en längd som är en multipel av blocklängden (16).

Den padding som används för dessa ändamål är oftast PKCS7 som går ut på att padda det sista blocket med bytes vars värde är lika med antal bytes som ska paddas. Denna senaste mening är troligtvis omöjlig att förstå, så låt oss visa några exempel istället:

Vid kryptering av en textsträng så paddas alltså först textsträngen med PKCS7. När man sedan dekrypterar en krypterad sträng så tar dekrypteringsfunktionen bort paddingen. En typisk funktion för att ta bort padding är:

def ta_bort_padding(P):
   if padding är okej:
        return (P utan padding)
   else:
        throw exception

En viktig del i programutveckling är att hantera exceptions. Självklart är det därför väldigt vanligt att detta missas. Om man skapar en dekrypteringsfunktion som inte hanterar den exception som slängs från ta_bort_padding-funktionen så kan denna information hamna hos slutanvändaren. Antag exempelvis att det finns en funktion på en tjänst som tar en krypterad sträng, dekrypterar strängen (utan att visa svaret för användaren) och gör något hemligt med resultat. Ifall funktionen ej hanterar exceptions så kan det innebära en informationläcka om den krypterade strängen som kan hamna hos slutanvändaren. Som exempel kan man tänka sig att tjänsten slänger ifrån sig dessa olika svarskoder beroende på vilken krypterad sträng som man bifogar:

Givet en sådan läcka kan man skapa sig ett paddingorakel! Ett paddingorakel är helt enkelt en funktion som tar en krypterad sträng och returnerar ifall den underliggande klartexten har godkänd padding eller inte.

def paddingOrakel(krypterad_string):
    response_code = curl-anrop till tjänsten med krypterad_string
    if response_code == 500:
         return False
    else:
         return True

Okej, nu vet vi hur ett paddingorakel ser ut – det återstår att se hur vi ska utnyttja det…

Låt oss anta att vi har en chiffertext bestående av två block \(C = C_1+C_2\) och vi vill få fram klartexten \(P=P_1+P_2\). Då vi har tillgång till chiffertexten så kan vi manipulera den, liknande så som vi gjorde i den förra uppgiften, men denna gång kommer vi modifiera bytes i slutet av blocket istället för i början.

Eftersom vi inte har någon aning om vad den underliggande klartexten består av så kommer vi inte automatiskt veta precis vad vi ska manipulera, men vi kan testa oss fram! Eftersom det enbart finns 256 olika ASCII-tecken så kan vi ju testa alla. Låt oss välja ett sådant tecken \(x\) och låt oss därefter modifiera det sista tecknet i \(C_1=c_{1,1}c_{1,2}\ldots c_{1,16}\) till

\(\quad\quad\quad\quad\gamma_{1,16} = c_{1,16}\oplus x\oplus \omega_1\)

där vi skrivit \(\omega_1\) för att beteckna tecknet med ASCII-värde 1. Kalla det modifierade blocket för \(C_1^\prime = c_{1,1}c_{1,2}\ldots c_{1,15}\gamma_{1,16} \). Om vi nu ber servern att dekryptera \(C^\prime = C_1^\prime\oplus C_2\) så händer följande (utan att vi ser något av det):

Det första blocket kommer bara bestå av nonsens, men det andra blocket är intressant. Precis som i den förra uppgiften kommer enbart karaktären på den position som motsvaras av positionen på den byte som vi modifierat förändras i dekrypteringsresultatet (för detta block). Med andra ord, alla bytes utom den sista kommer vara orörda, men för den sista får vi:

\(p_{2,16}^\prime = p_{2,16}\oplus c_{1,16}\oplus \gamma_{1,16} = p_{2,16}\oplus c_{1,16}\oplus (c_{1,16}\oplus x\oplus \omega_1)= p_{2,16}\oplus x\oplus \omega_1\)

Notera nu följande: Om vi har råkat välja \(x\) så att \(p_{2,16}=x\) så gäller det att

\(p_{2,16}^\prime = p_{2,16}\oplus x\oplus \omega_1 = \omega_1\)

I detta fall får vi alltså att den sista byten i \(P_2^\prime\) blir \(\omega_1\), vilket innebär att dekrypteringsfunktionen kommer hävda att \(P^\prime = P_1^\prime+P_2^\prime\) har godkänd padding! Med andra ord, vårt paddingorakel kommer returnera ”SANT” i detta fall.

Alltså, vi kan modifiera den sista byten i \(C_1\) med olika val av \(x\) och när paddingoraklet svarar ”SANT” så vet vi att vi lyckats välja \(x\) så att \(x=p_{2,16}\). (Nu ber jag läsaren ignorera ett litet problem… vi återkommer till det längre ned)

Efter att ha knäckt det sista tecknet i klartexten \(P\) så kommer den naturliga frågan: Kan vi på samma sätt få ut det näst sista tecknet? Svaret är: Absolut! … med några små modifikationer. Eftersom vi känner till vilket tecken \(p_{2,16}\) som är det sista tecknet i strängen \(P_2\) kan vi med denna kunskap modifiera de två sista tecknen i \(C_1\):

\(\quad\quad\quad \gamma_{1,16} = c_{1,16}\oplus p_{2,16}\oplus \omega_2\)
\(\quad\quad\quad \gamma_{1,15} = c_{1,15}\oplus x \oplus \omega_2\)

och skapa \(C_1^{\prime\prime} = c_{1,1}c_{1,2}\ldots c_{1,14}\gamma_{1,15}\gamma_{1,16}\). Därefter kan vi helt enkelt skicka den nya kryptotexten \(C^{\prime\prime}=C_1^{\prime\prime}+C_2\) till vårt paddingorakel.

När vi lyckas gissa rätt på \(x=p_{2,15}\) så kommer den krypterade strängen sluta med \(\omega_2\omega_2\), vilket igen är korrekt padding och vårt paddingorakel kommer då returnera ”SANT”.

Så här kan vi fortsätta till dess att vi knäckt hela \(P_2\). Oavsett hur många block som \(P\) består av så kan vi dessutom arbeta oss bakåt, block för block, och till slut knäcka hela \(P\) (i sista fallet kommer vi modifiera IV’t för att få ut \(P_1\)).

Innan vi kan hävda oss vara helt klara med denna uppgift måste vi återkomma till det lilla problem som vi nämnde ovan. Det kan nämligen hända att vi ibland kommer få ett ”SANT” från paddingoraklet trots att vi inte har gissat rätt på \(x\). Anledningen till detta är följande (som vi exemplifierar med modifiering av enbart det sista tecknet):

\(\quad\quad\quad p_{2,16}^\prime = p_{2,16}\oplus x\oplus \omega_1\)

Ifall man råkat välja \(x\) så att \(x=p_{2,16}\oplus\omega_1\oplus\omega_2\) så kommer

\(\quad\quad\quad p_{2,16}^\prime = p_{2,16}\oplus x\oplus \omega_1 = p_{2,16}\oplus(p_{2,16}\oplus\omega_1\oplus\omega_2)\oplus \omega_1 = \omega_2\)

Ifall det dessutom råkar vara så att \(p_{2,15}=\omega_2\) så kommer det dekrypterade blocket sluta med \(\omega_2\omega_2\) vilket paddingoraklet kommer returnerna ”SANT” för.

Om man råkat få en sådan ”False Positive” så kommer man dock att märka detta i nästa steg när man ska knäcka det näst sista tecknet i blocket eftersom det då inte kommer finnas något värde på \(x\) som returnerar ett korrekt resultat. Därmed kan man säkerställa sig om att ens val av \(x\) är korrekt ifall man med detta val även kan knäcka nästa tecken i blocket.

Längre än så hinner vi inte idag, så vi får tacka för lässtunden och önska gott återseende! Och till alla läsare som tagit sig ända hit: Hej, alla barn, nu blir det barnprogram!

Publicerat 2021-10-01 Skrivet av Gustav Sædén Ståhl