Cryptopals – del “2” av ?

(Del 1 )

Troligtvis har folk väntat som ekoxar på nästa del i denna fantastiska ”bloggserie” om Cryptopals, och nu är den äntligen här! (*författaren har ingen aning om ifall ekoxar överhuvudtaget väntar på saker*).

Den ursprungliga tanken med denna bloggserie var att metodiskt och pedagogiskt gå igenom uppgifterna från cryptopals.com i tur och ordning för att beskriva varför de är intressanta. Den idéen går i stöpet nu direkt då vi kommer göra ett litet hopp och titta på uppgift 61 (vi avslutade del 1 med uppgift 5). Detta eftersom det den senaste tiden varit en del prat om en sårbarhet i kryptoapplikationen crypt32.dll för de senaste Windows-versionerna – som har kopplingar till just denna uppgift. Vi försöker alltså vara både pedagogiska och aktuella i våra reportage! Ifall inga andra oförutsedda nyheter dyker upp innan nästa bloggpost så kommer vi då att hoppa tillbaka och fortsätta med uppgift 6.

Sårbarheten i crypt32.dll (CVE-2020-0601)

För ovanlighetens skull valde NSA att i förra veckan gå ut med att en sårbarhet fanns i Microsofts applikation crypt32.dll för Windows 10 som används för att verifiera certifikat för filer, https, etc. Sårbarheten innebär att filer eller hemsidor kan verifieras av Microsoft som legitima trots att de inte är det. Ett uppmärksammat exempel är Saleem Rashids twitterinlägg där han skapat ett giltigt certifikat för en spoofad nsa.gov-sida som består av den klassiska Rick Astley-låten ”Never gonna give you up” (en så kallad Rick roll).

Ett värre, men teoretiskt möjligt, scenario vore att en användare installerar en fil med ett (falskt) giltigt certifikat från någon som uppger sig för att vara Microsoft. Det har släppts en patch som löser sårbarheten, och det rekommenderas att skaffa denna uppdatering så snart som möjligt. Ifall man som läsare är orolig för ifall ens maskin är sårbar kan man även testa detta på: http://testcve.kudelskisecurity.com/

Källor:

https://securityboulevard.com/2020/01/nsa-microsoft-releases-patch-to-fix-latest-windows-10-vulnerability/
https://news.ycombinator.com/item?id=22048619
CVE-2020-0601: the ChainOfFools/CurveBall attack explained with PoC

Matematisk bakgrund

Elliptiska kurvor.

Då författaren av detta blogginlägg är matematiker så får läsaren unna en att säga: en elliptisk kurva är helt enkelt en ickesingulär algebraisk kurva av genus ett med en specificerad punkt. Om läsaren inte har full koll på alla dessa ord kan man bortse från den meningen, då det för våra ändamål räcker att tänka på dessa kurvor som lösningar till ekvationer på formen:

(med lite krav på a och b). Exempel på en elliptisk kurva är:

Det intressanta är att man kan definiera en typ av addition av punkter på en elliptisk kurva. Låt oss beskriva detta med ett exempel där vi ska beräkna summan A+B av två punkter A och B på kurvan:

Geometriskt kan denna addition beräknas genom att man ritar den unika linjen som går igenom både A och B.

I bilden ovan ser vi hur denna linje skär den elliptiska kurvan i precis en annan punkt. Detta faktum – att en sådan linje alltid skär i precis tre punkter – visar sig faktiskt gälla för alla val av punkter A och B på vilken elliptisk kurva som helst (ungefär – aningen *handviftande*). En elliptisk kurva kommer alltid vara symmetrisk mellan övre och undre planhalvorna – det vill säga att kurvan ovanför x-axeln kommer vara en spegling av kurvan under x-axeln. Varje punkt på kurvan har alltså en unik spegelpunkt på andra sidan x-axeln. Speglingen av den tredje punkten i bilden ovan är summan A+B:

Låt oss ta ett till exempel med en punkt G på kurvan:

Låt oss beräkna G+G. Om man försöker använda samma princip som i förra exemplet fastnar man kanske direkt när man ska försöka rita motsvarigheten till linjen som gick mellan A och B. Man behöver inse att den unika linjen i detta fall blir linjen som tangerar kurvan i punkten G, vilket vi kan använda för att beräkna G+G=2G:

Sedan kan vi fortsätta och beräkna 3G=G+2G:

Här vill författaren poängtera att det är svårt att rita på en datorskärm under tidspress, så klagomål på kvaliteten hos figurerna ovan är ej nödvändiga. Alla gröna och orangea streck som dragits är raka linjer, och den blåa kurvan är slät och fin.

Det roliga är att denna addition som vi just definierat fungerar, på många sätt, som addition av vanliga tal. Exempelvis gäller att A+B=B+A och att (A+B)+C=A+(B+C). Det finns till och med en punkt som svarar mot talet 0 med egenskapen A+0=A. Denna punkt är en punkt vid oändligheten… Tyvärr finns inte tid att gå igenom allt detta i detalj då tiden börjar rinna iväg, men om man är intresserad så finns det flera bättre och mer utförliga beskrivningar tillgängliga på internet.

Elliptiska kurvor i kryptografi

I kryptografi/datorvärlden används inte reella tal (decimaltal) utan istället arbetar man över en ändlig kropp (exempelvis heltalen modulo 13; men oftast väljer man 13 som ett mycket större primtal). Detta scenario – där man jobbar över en ändlig kropp – är “diskret matematik” och teknikerna man kan använda är annorlunda mot den analys man är van vid frångymnasiet/högskolan.

Summan av n stycken G, det vill säga G+….+G = nG blir en ny punkt på kurvan för alla heltal n. Vi har redan sett exempel på 2G och 3G ovan. Givet G och en punkt F = nG för något n så är det i allmänhet svårt att beräkna n när man jobbar över en ändlig kropp; man behöver i princip testa sig fram genom att göra beräkningarna 2G=G+G, 3G=G+2G, 4G=G+3G, … och så vidare tills man hittar rätt. Det krävs alltså n stycken additioner för att få ut n.

Å andra sidan – när man vet n och G – så kan man snabbt och effektivt beräkna nG. Som exempel kan vi beräkna 9G – summan av 9 stycken punkter G.

9G=8G+G=(4G+4G)+G=((2G+2G)+(2G+2G))+G

Detta kan beräknas med enbart 4 operationer:

2G=G+G
4G=2G+2G
8G=4G+4G
9G=8G+G

Denna metod kan användas för att beräkna nG med ungefär log2(n) stycken operationer, vilket är mycket mindre än n; ifall n är stort.

Ifall läsaren känner till RSA eller Diffie-Hellman kan man dra paralleller mellan elliptiska kurvor och metoderna som används för dessa. För dessa använder man, istället för punkten nG, den mer klassiska matematiska operationen av exponentiering för att skapa potenser a^n för ett tal a. Givet talet a^n krävs det att man beräknar logaritmen log_a(a^n)=n för att få ut n.
Logaritmen är enkel att beräkna över de reella talen, men är mycket svårare över en ändlig kropp – och att hitta mer effektiva beräkningsmetoder för dessa logaritmer kallas för det diskreta logaritmproblemet.

På grund av likheterna mellan situationerna med a^n och nG, så kallar man även problemet med att hitta effektiva metoder för att beräkna n från nG som det “diskreta logaritmproblemet för elliptiska kurvor”.

Det finns flera olika metoder för att förbättra snabbheten i beräkningen av både den diskreta logaritmen och den elliptiska varianten. En effektiv metod som bara funkar för potenser och inte för elliptiska kurvor är anledningen till att det inte krävs lika stora n för att säkerheten för en elliptisk kurva ska vara lika bra som i det klassiska fallet.

Sammanfattningsvis kan vi säga att grundidéen till att använda elliptiska kurvor i kryptologi är:

Givet följande parametrar:

1. en elliptisk kurva (dvs val av två tal a och b), och
2. en punkt G på kurvan

kan man skapa:

1. en privat ”nyckel” som är ett stort tal n, och
2. en publik ”nyckel” som är punkten nG på kurvan.

Någon som enbart känner till parametrarna och den publika nyckeln nG har väldigt svårt att beräkna den privata nyckeln n.

Signerera meddelanden med hjälp av elliptiska kurvor

Låt oss anta att jag har skapat ett meddelande: ”Hejsan” – som jag vill dela med mig av. För att mottagaren ska kunna försäkra sig om att det är jag som skickat denna hälsningsfras så kan jag signera meddelandet. Detta kan exempelvis göras med ECDSA (elliptic curve DSA). Som namnet antyder finns även en klassisk variant av DSA (digital signature algorithm) men det skippar vi att prata om idag.

För detta ändamål görs följande:

1. fixera en elliptisk kurva med en baspunkt G,
2. välj en privat nyckel n.

Den privata nyckeln n ger även en publik nyckel Q=nG som jag delar med mig av till mina vänner. För att signera mitt meddelande ”Hejsan” gör jag nu följande (skippar lite detaljer för att förenkla beskrivningen – exempelvis ska alla beräkningar göras modulo ordningen av baspunkten G):

1. Välj en ny privat nyckel k för just detta meddelande (detta gör det möjligt att kunna återanvända min privata nyckel n flera gånger – ett så kallat salt).
2. Beräkna punkten R=kG.
3. Låt r vara x-koordinaten för R.
4. Låt h=H(”Hejsan”), där H är en hashfunktion (ex: SHA1, MD5) och där vi betraktar h som ett stort tal.
5. Beräkna:

Paret (r, s) blir min signatur till meddelandet. Jag kan nu skicka mitt meddelande ”Hejsan” tillsammans med min signatur (r, s). Vi antar här att mottagaren även känner till min publika nyckel Q=nG och vilken hash H som jag använt. Om mottagaren vill verifiera att det verkligen är jag som står bakom ”Hejsan” så kan de göra som följer:

1. Beräkna h=H(”Hejsan”).
2. Beräkna:

3. Beräkna:

4. Beräkna punkten:

5. Om x-koordinaten för punkten P är lika med r så är signaturen korrekt.

Låt oss snabbt, och handviftigt, övertyga oss om att detta är korrekt:

Det ser ut att stämma! Vilken tur. Mottagaren kan alltså verifiera att mitt meddelande var från mig, utan att ha kännedom om mina privata nycklar n och k. Någon som skulle försöka utge sig för att vara mig så skulle de behöva känna till min privata nyckel n för att kunna skapa min signatur – och så länge som den diskreta logaritmen för elliptiska kurvor är svårberäknad ska detta inte vara någon större fara.

Signaturer kan även användas för att uppvisa ägandeskap över ett meddelande eller program. Om man skapar en signatur för en fil med sin privata nyckel så kan alla se att ens publika parametrar kan användas för att verifiera att man signerat filen.

Cryptopals – Uppgift 61 (tillgänglig via Thomas Ptaceks twitter (@tqbf)

Nu är vi redo för att prata om Cryptopals! I uppgift 61 (Set 8) har en användare Alice en elliptisk kurva med en baspunkt G, och har valt någon okänd privat nyckel n, med motsvarande publika nyckel Q=nG. Anta att Alice har skrivit ett meddelande m som hon signerat med en signatur (r, s).

Uppgiften är att skapa en ny publik nyckel så att man kan hävda att det var man själv som signerat Alices meddelande, och därmed få mottagaren att tro att meddelandet kommer från en själv istället. Läsaren kanske nu blir förvånad eftersom vi just har förklarat att dessa signaturer ska vara säkra…

Det är nämligen så att om valet av parametrar (talen a och b för kurvans ekvation, och baspunkten G) är fritt för användaren att välja, så blir det problem.

Man kan nämligen göra följande:

1. Ta Alices signatur och beräkna u1 och u2 som ovan (vilket är möjligt för alla som har hennes parametrar och publika nyckel).
2. Välj ett tal d.
3. Låt:

4. Låt:

5. Beräkna:

Förfalskaren kan nu skicka:

1.  Alices meddelande m,
2. Alices signatur (r, s),
3. Alices parametrar – med där man byter baspunkten från G till G_2, och
4. sin egen publika nyckel Q_2.

 En mottagare av detta som vill verifiera signaturen gör följande:

1. Beräknar h=H(m),
2. Beräknar u_1 och u_2 som vanligt,
3. Beräkna punkten:

4. Eftersom x-koordinaten av R är lika med r (per definition) så accepteras detta som en giltig signatur.

Mottagaren har alltså ingen anledning att tro på att personen som säger sig ha skrivit meddelandet ljuger – eftersom personens publika nyckel kunde användas för att verifiera signaturen.

När författaren löste denna uppgift första gången så fick författaren faktiskt för sig att ingen skulle göra en så ”klantig” implementation och tillåta valfria parametrar. Dock har tydligen bristen ovan använts för att knäcka en tidigare version av Let’s Encrypt-certifikatet som används av flertalet sidor på internet.

Ännu värre, och anledningen till varför vi skriver denna bloggpost idag, är att sårbarheten som Microsoft råkat skapa i sin crypt32.dll är av liknande karaktär. Programmet testar nämligen inte att baspunkten G för ett tidigare cachat certifikat är korrekt – vilket (simplifierat) innebär att en angripare som inte känner till certifikatutdelarens hemliga nyckel n kan komma runt detta genom att helt enkelt byta ut baspunkten G till den publika nyckeln nG och därmed modifiera den privata nyckeln till 1 eftersom 1*nG=nG.  

PS. Uppgift 61 går sen vidare och låter en göra liknande saker för klassisk DSA, och gör även en liknande tillämpning för RSA – men detta lämnar vi tills vi gått igenom dessa i detalj (gissningsvis i bloggseriens 37e del eller liknande…)