Cryptopals 00:02:FF:00:13

(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 Del 8 Del (9,deadbeefcafe) Del 7^5 mod 11 Del 11 (RSA!) Del 12 (RSA 2))

Dags igen. cryptopals.com. För trevliga introduktioner som vaggar in läsaren i en (falsk?) dröm om en lättsmält text hänvisar vi till de tidigare blogginläggen i denna serie (länkade ovan).

Ett pedagogiskt problem med denna bloggserie, och cryptopals i allmänhet, är att varje ”uppgift” har samma upplägg: Introducera en ny krypteringsalgoritm, och börja med att direkt hitta sårbarheter i dess implementation. Som en läsare kan man ju då få känslan av att alla dessa algoritmer som vi går igenom är dåliga, vilket inte (alltid) är fallet. Uppgifterna i cryptopals är helt enkelt utformade för att belysa olika implementationsmisstag som är klassiska och lätta(?) att göra fel på.

Dagens tema (RSA) är en krypteringsalgoritm som anses säker – så länge som den implementeras korrekt. I tidigare blogginlägg har vi gått igenom ett antal olika fel som visat sig leda till misstag om man använder:

• RSA utan padding för att kryptera samma meddelande med olika publika nycklar med små exponenter.
• RSA utan padding som tillåter en chosen ciphertext attack, trots försök till replay-skydd.
• RSA utan padding med en liten publik exponent och ett kort meddelande.
• RSA med padding med en liten publik exponent och felaktig paddningsborttagning.
• RSA med padding med en läcka som berättar ifall den dekrypterade texten är udda eller jämn.

Dessa uppgifter har lärt oss två saker:

1. Man behöver utföra (korrekt implementerad) padding innan man krypterar RSA, och (korrekt implementerad) padding-borttagning efter dekryptering.
2. Man måste undvika att läcka information vid kryptering/dekryptering.

Gällande den första punkten så bör vi kanske beskriva hur man kan utföra padding vid RSA-kryptering. Låt oss ta ett exempel med ett meddelande \(x=335\) som vi vill kryptera med publik nyckel \(n\) och \(e\). Säg dessutom att vi valt modulo \(n\) med 1024 bitar, vilket innebär att \(n\) är 128 bytes lång (motsvarande ungefär \(\text{log}_{10}(2^{1024})\approx308\) decimala siffror).

Istället för att beräkna \(x^e \text{ mod } n\) så vill vi lägga på padding på \(x\) innan vi utför beräkningen, och detta kan vi göra på följande sätt:

Uttryckt i bytes (hexadecimalt) så är \(x=\) 01:4F. Notera att dessa två bytes är mycket färre än de 128 bytes som behövs för att uttrycka \(n\). Från tidigare uppgifter har vi sett att ett litet \(x\) kan bli problematiskt, och det är dessutom dåligt om krypteringen av \(x\) är helt deterministisk – det vore bättre om vi hade något som gav olika krypteringar vid varje tillämpning. För att göra \(x\) längre och krypteringen lite mer svårgissningsbar så skapar vi

\(x_{pad}\) = 00:02:34:22:EA:91:B5:…:12:3F:55:00:01:4F

där 34:22:EA:91:B5:…:12:3F:55 representerar en slumpmässig sträng av \(128-2-1-\text{len}(x)=123\) slumpmässiga icke-noll-bytes. Den paddade strängen \(x_{pad}\) består alltså av:

• En standardheader 00:02 med 2 bytes som beskriver vårt val av padding-algoritm (samt försäkrar att \(x_{pad}<n\))
• En lista av \(128-2-1-\text{len}(x)=123\) slumpmässiga icke-noll-bytes
• En nollbyte 00 av längd 1 för att identifiera slutet på slumpsträngen
• Originalmeddelandet \(x\) bestående av \(\text{len}(x)=2\) bytes
• Totalt får \(x_{pad}\) en längd av \(2+123+1+2=128\) bytes (egentligen 127 om vi skippar den inledande nollan)

Den som i slutändan dekrypterar meddelandet och får ut \(x_{pad}\) kan enkelt ta bort paddingen genom att identifiera starten 00:02 och sedan radera alla bytes fram till och med den nästa förekommande 0-byten.

Den andra punkten (att inte läcka information) lärde vi oss från uppgiften med ett paritets-orakel. En sådan informationsläcka (ifall den dekrypterade texten är udda eller jämn) är aningen krystat och kommer sällan förekomma i praktiken. Vi kommer i dagens uppgift se ett exempel med en mer verklighetsförankrad informationsläcka.

Challenge 47/48: Bleichenbacher’s PKCS 1.5 Padding Oracle (Simple/Complete)

Låt oss bygga upp ett litet scenario. Antag att Sven har en webbapplikation dit folk kan skicka hemliga meddelanden till honom genom att använda hans publika nyckel \(n\) och \(e\). När webbapplikationen tar emot ett krypterat meddelande så dekrypterar den meddelandet och sparar det på Svens server så att han kan läsa meddelandet vid tillfälle.

Antag att Veronika har skickat ett viktigt hemligt meddelande \(x\) till Sven via denna hemsida, och att vi har snappat upp den motsvarande krypterade strängen \(C=(x_{pad})^e \text{ mod } n\). Vårt mål är att dekryptera detta meddelande. I vanliga fall är detta i princip omöjligt (om man valt bra värden för RSA-algoritmen), men i detta scenario så har Sven gjort ett fatalt misstag, nämligen:

• Ifall webbapplikationen lyckas dekryptera ett meddelande och spara meddelandet på servern så svarar webbapplikationen med HTTP-svar 200 OK, ”Tack för meddelandet”.
• Ifall webbapplikationen misslyckas med att dekryptera och spara ned meddelandet på servern så svarar webbapplikationen med HTTP-svar 500 Internal Server Error: ”Something went wrong”.

Givet att ingenting annat är fel så är den ”enda” möjliga anledningen till att ett meddelande inte kunde sparas att dekrypteringen misslyckades, och det borde i ”rimliga” fall bara kunna ske ifall borttagningen av padding ej kunde genomföras korrekt. Att ej kunna ta bort padding bör enbart kunna ske ifall paddingen på meddelandet har fel struktur. Med andra ord så kan vi anta att vi får ett felmeddelande precis när paddingen av det dekrypterade meddelandet är inkorrekt. Detta är ett typexempel på en informationsläcka!

Denna informationsläcka ger oss alltså ett Padding-orakel som tar en sträng som input och berättar om den ”dekrypterade” strängen har korrekt padding eller ej.

En intressant grej med denna uppgift är att detta är den första uppgiften där man får möjlighet att läsa en forskningsartikel i matematik/kryptologi för att förstå vad man ska göra. Nu är det en sorglig tanke att denna artikel från 1998 inte direkt kan anses vara modern forskning längre, men det är väl så tid fungerar. Artikeln är Chosen Ciphertext Attacks Against Protocols
Based on the RSA Encryption Standard PKCS #1 av Daniel Bleichenbacher, och vi rekommenderar den som trevlig eftermiddagsläsning.

Det finns många intressanta forskningsresultat inom kryptografi (och RSA i synnerhet), så den intresserade läsaren har möjlighet att förkovra sig ordentligt, och en rolig kuriosa är att många spännande resultat härstammar från vårt lilla Sverige (för att undvika favoriter nämner vi inga vid namn).

Det faktum att en snart 30 år gammal forskningsartikel visade hur man kan utnyttja ett padding-orakel för att knäcka RSA belyser att det inte är helt uppenbart för gemene man hur denna informationsläcka kan användas, så låt oss förklara detta nedan.

Vi vet att en korrekt paddad sträng \(y_{pad}\) består av 128 bytes, där de två första är 00:02. Med andra ord så vet vi att \(y_{pad}\) som ett tal uppfyller:

• \(y_{pad}>\) 00:02:00:00:00:…:00:00
• \(y_{pad}<\) 00:02:FF:FF:FF:…:FF:FF

Genom att sätta \(B = 256^{128-2}\) har vi alltså att en korrekt formaterad paddad sträng uppfyller: \(2B<y_{pad}<3B\).

Vårt mål är att knäcka meddelandet \(C\) som Veronika skickade till Sven och få ut det underliggande meddelandet \(x\).

Om vi skickar \(C\) till Padding-oraklet så vet vi att kommer få ”Korrekt padding” som svar eftersom \(C\) är krypteringen av ett givet meddelande \(x\). Vi vet alltså att \(2B<x_{pad}<3B\).

För att vara lite roliga så kan vi skicka \(2^e\cdot C \text{ mod }n\) till oraklet och fråga ifall denna har korrekt padding eller ej. Vad är det som händer då? Jo, eftersom vi multiplicerat \(C\) med just \(2^e\) gäller att:

\(2^e\cdot C=2^e\cdot x_{pad}^e=(2\cdot x_{pad})^e \text{ mod }n\),

så oraklet kommer svara på om \(2\cdot x_{pad}\) har korrekt padding eller inte. Detta ger oss information om sanningshalten i påståendet: \(2B<2\cdot x_{pad}(\text{mod }n)<3B\). På samma sätt kan vi få fram ifall: \(2B<i\cdot x_{pad}(\text{mod }n)<3B\) är sant eller ej för godtyckligt heltal \(i\).

Genom att hålla tungan rätt i mun och manipulera dessa relationer korrekt så kan man använda informationen som vi får från oraklet för att iterativt minska intervallet som \(x_{pad}\) kan ligga i. Till slut kan man få ned intervallet till att bara innehålla ett enda tal, vilket måste vara svaret vi söker, nämligen \(x_{pad}\) (eller ja, sedan får vi själva ta bort paddingen för att få ut \(x\), men det ska vi nog klara).

Tidigare i denna bloggserie har vi försökt att beskriva detaljerna i matematiken bakom alla algoritmer, men i detta fall så känns detta inte nödvändigt då allting redan beskrivs på ett trevligt sätt i den tidigare nämnda artikeln. Dessutom gissar vi att imponerande läsare som tagit sig hela vägen ned hit inte kommer känna sig belönade om de dessutom måste ta sig igenom massa modulo-beräkningar (vilket kan vara kul, men kanske inte särskilt belysande i detta fall).

Låt oss istället fundera lite över grundproblematiken i detta scenario. Anledningen till att vi kunde skapa ett padding-orakel var för att webbapplikationen svarade med ett felmeddelande ifall ett felaktigt meddelande levererades. I OWASPs Topp 10-lista över vanliga fel i webbapplikationer nämns ofta ”allt för detaljerade felmeddelanden” som en brist. Tanken att låta användaren få veta vad som gått fel är ju fin, och det kan såklart hjälpa vid felsökning – men det ger samtidigt potentiella angripare mycket information som kan utnyttjas för att hitta attackvägar in i ens organisation. Att logga fel är viktigt, men enbart för internt bruk!

Hur skulle Sven ha gjort då förresten? I detta fall så gav ju inte webbapplikationen någon detaljerad information, den sa ju bara att någonting gått fel. Borde webbapplikationen alltid svara ”200 OK, Tack för meddelandet” oavsett om det gick bra eller inte? Det är ju tråkigt om användare tror sig ha skickat in ett meddelande som Sven aldrig får läsa. Svaret på dessa frågor är inte så enkel, utan hamnar i gränslandet mellan användarupplevelser och säkerhet – man får helt enkelt avgöra vad som är viktigast för just denna applikation. Är det viktigast att användare får veta att deras meddelande levererats korrekt till Sven, eller är det viktigast att deras hemliga tårt-recept/statshemligheter inte dekrypteras av potentiella angripare?