Cryptopals del 10 (= 7^5 mod 11) 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, Del 8, Del (9,deadbeefcafe))

Välkommen till världens bästa bloggserie utgiven av Simovits Consulting som handlar om Cryptopals. Denna bloggserie går i tur och ordning igenom uppgifter från hemsidan Cryptopals, som är en sida med uppgifter där man får lära sig om att knäcka olika krypto-algoritmer. Vårt mål har varit att förklara matematiken bakom idéerna snarare än att gå igenom lösningar till uppgifterna i detalj. Så är också planen för framtiden. Det noterades dock av författaren när han nu, inför dagens post, läste igenom sin förra bloggpost att den delen var tämligen tung att ta sig igenom. För att kompensera för detta så ska vi därför idag försöka använda oss av bilder istället för massa text, och hoppas att detta kan hjälpa läsbarheten/förståelsen.

Låt oss hälsa på dagens huvudpersoner.

Challenge 33: Implement Diffie-Hellman

Diffie och Hellman vill skicka meddelanden mellan sig, men de är oroliga för att den otrevlige brevbäraren Frank ska tjuvläsa vad de skriver. De kommer då på tanken att kryptera sina meddelanden! Problemet är bara att de i så fall (via brev som Frank kan läsa) måste komma överens om en krypteringsnyckel… Hur ska de göra det utan att Frank får veta vad krypteringsnyckeln är?

Efter en tankepaus så ger deras namn dem lite inspiration, och de kommer på att de kan använda Diffie-Hellmans nyckelutbytes-algoritm. Vilken tur att de hette som de gjorde så att de fick en så bra idé!

De bestämmer sig för att använda parametrarna \(g=5\) och \(p=37\), och gör sedan följande:

Diffie berättar inte för någon vilket tal a som han tänker på, men skriver ned sitt resultat A och skickar det till Hellman.

Hellman blir jätteglad över kortet, och skickar direkt tillbaka sitt beräknade B till Diffie. Frank är inte glad.

Nu gör Diffie och Hellman följande smarta beräkning (på var sitt håll):

De får båda ut talet \(s=14\), vilket sammanträffande! Eller?

$$23^7 = B^a = (g^b)^a = g^{ab} = (g^a)^b = A^b =18^{21}\text{ (mod 37)}$$

Aha, det var inte ett sammanträffande, utan en matematisk klurighet! Nu har de alltså båda fått ut talet 14 och Frank kan omöjligt få ut det talet eftersom han inte känner till vare sig \(a=7\) eller \(b=21\).

Nu kanske någon tycker att det väl inte kan vara särskilt svårt att lösa ekvationen \(5^x=18\text{ (mod 37)}\), och det kanske stämmer… Men om man istället för 37 väljer \(p\) till något väldigt stort så visar det sig inte vara så enkelt, givet att \(x\) är ganska stor den med.

Diskreta log-problemet. Det finns ingen allmän effektiv algoritm för att beräkna \(x\) givet att man känner till \(g\), \(X\) och \(p\) i ekvationen $$g^x=X\text{ mod }p.$$

Detta påstående kan kännas icke-intuitivt eftersom de flesta säkert sett att det brukar finnas en knapp på miniräknare på vilken det står “log”. Grejen är att den knappen bara funkar analytiskt (över reella tal) inte när man arbetar över diskreta värden med modulo-beräkningar.

Alltså, det finns snabba algoritmer för att beräkna potenser såsom \(30834^{2832691}\text{ (mod 2784293)}\) men i allmänheten finns det alltså ingen snabb algoritm för att hitta vilken exponent \(x\) som uppfyller att exempelvis \(30834^x=1038410 \text{ (mod 2784293)}\). För en dator är detta exempel väldigt lätt att lösa då datorn snabbt kan utföra en brute-force-attack och testa alla värden mellan \(0\) och \(2784293\) på väldigt kort tid, men om man istället väljer “jättestora” tal så blir det jobbigt att lösa det diskreta log-problemet även för en dator.

Ett annat klassiskt matematiskt exempel, som de flesta kanske har hört talas om, på när det är lätt att utföra en matematisk operation, men svårt att ta operationens invers, är kopplat till problemet med primtalsfaktorisering:

• Det finns snabba och effektiva algoritmer för att beräkna produkten av två stora primtal.
• Men, givet ett stort tal som man vet är produkten av två stora okända primtal så finns det ingen (tillräckligt) snabb algoritm för att hitta vilka dessa två primtal är.

Detta är vad som används för RSA-kryptering, vilket är ett liknande, men ändå annorlunda koncept till Diffie-Hellman-metoden. Ett sätt att visualisera båda dessa matematiska problem är som att det är lätt att blanda två stycken färger, men det är svårt att göra det omvända (ta en färg och separera den i sina två beståndsdelar). Vi återkommer till RSA i en senare blogg-del.

Okej, tillbaka till Diffie och Hellman! De har nu lyckats skapa sig talet 14, och ingen annan kan känna till detta tal (… vi återkommer till det senare…), så vad ska de göra nu då? Ja, på något sätt måste de använda talet 14 för att skapa sig en krypteringsnyckel, och det finns många sätt att göra det på. Exempelvis kan de båda beräkna hashen av 14 och använda resultatet som nyckel för AES-kryptering.

Nu kan Diffie använda denna nyckel för att kryptera en text och skicka till Hellman.

För att sammanfatta: Både Diffie och Hellman väljer varsin privata nyckel \((a\text{ respektive }b)\) och skickar därefter sin publika nyckel \((A\text{ respektive }B)\) till den andra genom ett osäkert medium (Frank). De kan därefter beräkna deras gemensamma hemlighet \(s\) genom detta utbyte för att skapa sig sin krypteringsnyckel enligt valfri algoritm.

Challenge 34: Implement a MITM key-fixing attack on Diffie-Hellman with parameter injection

Kan Diffie och Hellman verkligen vara säkra på att Frank inte kan avläsa deras hemliga meddelanden? Eftersom denna bloggserie handlar om att knäcka olika kryptografiska metoder så är svaret såklart nej. Det finns flera olika saker som Frank kan göra för att stoppa deras smarta plan. Denna uppgift går igenom ett sådant exempel.

Antag att vi har samma början på händelseförloppet som tidigare, fram tills att Diffie ger första meddelandet till Frank:

Tänk nu att Frank, istället för att bara leverera meddelandet till Hellman, slänger Diffies brev och förfalskar en modifierad version som han levererar till Hellman:

Nu istället för att leverera Hellmans brev till Diffie så gör han en ny förfalskning som han levererar till Diffie:

Eftersom det enda sättet för Diffie och Hellman att kommunicera är via Frank så har de ingen anledning att tro att breven de fått är förfalskade. De utför därför båda två beräkningarna som ska leda fram till \(s\) i god tro:

Franks val att byta \(A\) och \(B\) till just \(37\) innebär att bådas beräkningar blir 0 (oavsett vilka värden \(a\) och \(b\) som de håller hemliga). Så Frank vet att deras \(s=0\) och vet därför också vad deras hemliga nyckel kommer vara:

Ajdå, det var ju inte bra! Men man kan ju tänka att åtminstone någon av Diffie och Hellman tänker på att \(37\) är ett väldigt dumt val för den andres publika nyckel (eftersom parametern \(p=37\)). Så en rimlig person/algoritm borde ju säga “Stopp och belägg här, nu är någonting fel…”.

Challenge 35: Implement DH with negotiated groups, and break with malicious “g” parameters

Antag att Frank var orolig för att Diffie eller Hellman skulle notera att något var skumt med den förra attack-metoden. Finns det något annat han kan göra? Självklart. Tänk oss samma start som förra gången.

Istället för att modifiera talet \(A\) till något som ger ett \(s\) som Frank kan förutspå, så kan man tänka sig att han istället kan modifiera parametrarna \(g\) och \(p\). Exempelvis kan han sätta \(g=p-1\), \(g=p\), eller \(g=1\), etc.

Han kan sedan gå vidare och göra samma sak med brevet från Hellman till Diffie. Alla dessa varianter skulle (uppenbarligen) leda till att Frank kan förutspå värdet på Diffie och Hellmans hemlighet \(s\). Men, precis som nämns i uppgiftstexten så är detta inte en särskilt rimlig attack-vektor eftersom både Diffie och Hellman borde notera att de parametrar som den andra skickar inte stämmer med de parametrar som de hade bestämt i förväg. I verkligheten så brukar man dessutom använda specifika parametrar som rekommenderas av NIST. Sannolikheten för att denna attack skulle fungera är alltså ganska låg. Anledningen till att man ombeds utföra attacken i denna uppgift är för att, som de skriver i uppgiften, liknande angrepp kommer fungera i vissa fall med kryptering genom elliptiska kurvor (se Del “2”).

Bättre Man in the Middle-attack

Om Diffie och Hellman var på sin vakt så skulle de troligtvis notera att någonting var fel med meddelandena som levererades av Frank i de två attackmetoder som Cryptopals föreslår. Men ingen av dessa två tidigare uppgifter tar upp den mest effektiva attackmetoden som Frank skulle kunna utnyttja, vilken vi avslutar denna bloggdel med:

Istället för att ändra Diffies publika nyckel till någonting suspekt, eller att ändra någon av parametrarna (som också vore suspekt) så kan Frank helt enkelt välja att vara en del av gänget och själva tänka på ett hemligt tal \(c\) och skapa sig en egen publik nyckel \(C\).

Frank skickar sedan sin publika nyckel till Hellman (men låtsas som att den kommer från Diffie).

Han tar nu brevet från Hellman och byter Hellmans publika nyckel mot sin egen, men låtsas att det är Hellmans.

Han lämnar sedan denna förfalskning till Diffie.

Om Diffie och Hellman nu på varsitt håll försöker räkna ut deras gemensamma hemlighet \(s\) så får de:

De får olika värden på sin gemensamma hemlighet. Det är ganska dåligt… Men, detta vet ju inte Diffie eller Hellman, de tror att allting är korrekt. Frank däremot, han sitter nu hemma på sin lediga stund och gör följande beräkningar:

Frank kan alltså räkna ut bådas hemligheter (28 och 11)! Hur kommer det sig? Jo, för han har agerat som en riktig Man-i-Mitten (Man-in-the-Middle) och det är ju faktiskt Frank som Diffie har skapat en hemlighet med, och det är med Frank som Hellman skapat sin hemlighet.

Eftersom Diffie och Hellman båda är lyckligt(?) ovetandes om detta så räknar de ut sina krypteringsnycklar, och Diffie försöker skicka sitt krypterade meddelande till Hellman. Vi vet att Hellman inte kommer kunna dekryptera denna text, men Frank kan!

Frank kan nu alltså avläsa allting som Diffie skickar till Hellman genom Diffies krypteringnyckel (som Frank känner till) och han kan vidarebefordra dessa meddelanden till Hellman genom att först kryptera klartexten med Hellmans krypteringsnyckel (som Frank också känner till). Varken Diffie eller Hellman märker av någonting – de skickar ett krypterat meddelande som den andra kan dekryptera, och har ingen anledning att tro att någonting är fel.

Så, vad är det vi visat egentligen? Är inte Diffie-Hellman känt som ett sätt att just kunna utföra ett nyckelutbyte över en osäker kanal (i detta fall Frank) och vara säker på att någon inte kan störa detta?

Jo, det är ju tanken – men grundprincipen för Diffie-Hellman, som vi använt här, är (uppenbarligen) inte tillräcklig för att kunna försäkra sig om detta. Riskerna vi såg ovan krävde att Frank aktivt modifierade meddelandena medans de skickades. Ifall han istället hade varit på besök hemma hos både Diffie och hos Hellman och hade sett breven ligga hemma hos dem efter att de levererats så hade den informationen inte hjälpt honom för att få ut hemligheten \(s\). Så ifall angriparen missar att modifiera nyckel-utbytet så är det “lugnt”. Men hur ska man försvara sig mot risken att någon utför dessa aktiva attacker?

I praktiken så behövs någon form av signatur av meddelandena så att Diffie och Hellman kan vara säkra på att meddelandena inte har ändrats på vägen. För detta ändamål så kan man använda exempelvis en MAC (som vi diskuterade i Del 9 av denna bloggserie), men detta kräver ett förutbestämt lösenord, så då måste Diffie och Hellman ha lyckats komma överens om detta lösenord på något sätt, och det är ju just att bestämma ett gemensamt hemligt lösenord som var grundproblemet vi ville lösa med Diffie-Hellman…

Ett annat sätt att signera meddelandena är genom asymmetrisk kryptering (RSA). Detta kommer vi prata om i (troligtvis) nästa del av denna bloggserie, men för dagens ändamål räcker det att förstå detta: I asymmetrisk kryptering har man precis som i Diffie-Hellman en privat nyckel och en publik nyckel. Signeringar kan utföras med den privata nyckeln och verifieras av den publika nyckeln. Så det löser problemet! Eller… Den uppmärksamma läsaren kan invända med “Hur ska man kunna lita på den publika nyckeln för signaturen då?”. Det är en poäng. Vad vi än gör så hamnar vi i ett problem att vi inte vet om vi kan lita på den publika nyckeln som vi får – oavsett om det rör sig om Diffie-Hellman eller om RSA.

Sättet man löser detta problem på i praktiken (på internet) är genom att exempelvis ens webbläsare har en inbyggd samling av publika nycklar som den har verifierat, och vi kan (om vi litar på webbläsaren/utvecklaren bakom webbläsaren) lita på att nycklarna som finns i denna samling är korrekta. Andra nycklar kan i sin tur signeras/verifieras av någon av dessa betrodda nycklar och på så sätt skapar man kedjor av tillförlitlighet.

Så, om man vill utföra ett Diffie-Hellman-nyckelutbyte med en hemsida så kan man utföra stegen som Diffie (din webbläsare) och Hellman (hemsidan) gjorde ovan, men där meddelande från Hellman (hemsidan) också kan verifieras med en publik betrodd nyckel. På så sätt kan man alltså utföra säkra nyckel-utbyten på internet som sedan kan användas för att kryptera trafiken som skickas mellan en själv och en hemsida.