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

Dags för vår mest återkommande bloggserie där vi lugnt och behärskat pratar kryptologi genom att gå igenom uppgifterna från cryptopals.com. Vår ansats är dock, som vanligt, inte att gå igenom programmeringstekniska detaljer av möjliga lösningar, utan istället vill vi försöka beskriva själva teorin som lösningarna utnyttjar. I detta avsnitt kommer vi fortsätta med föregående avsnitts introduktion till RSA, och se exempel på lite mer ”avancerade” angreppsmöjligheter.

Säkerheten hos RSA garanteras av matematik. Problemet är att matematik är lätt att göra fel på, speciellt om man inte är fullt insatt i vad det är man gör. Det är därför vanligt att se små matematiska misstag i implementationer av matematiska algoritmer (såsom RSA), som kan leda till kritiska sårbarheter.

Låt oss börja med att påminna oss om grunderna för RSA med ett exempel (den intresserade läsaren kan se en mer utförlig beskrivning i föregående blogg-avsnitt):

Vi har en publik nyckel som består av två tal $e=3 $ och $n=33$. Dessa två tal är kända för alla i hela världen.
Vi har en privat nyckel som består av ett tal $d=7$. Detta värde är det enbart vi själva som har kännedom om.

Med dessa två nycklar kan man göra två olika saker:

Kryptera data
Signera data

Kryptera data. Som ett enkelt exempel kan vi tänka att någon vill skicka ett hemligt meddelande till oss bestående av en enda bokstav: B.

Det första man behöver göra är att konvertera datat till ett tal (enkoda datat) för att kunna utföra matematiska operationer på det. Detta kan göras på många olika sätt, och har egentligen ingenting med RSA att göra. Exempelvis kan man enkoda datat B genom att säga att B är den 2:e bokstaven i alfabetet och därmed få ett tal $x=2$, eller så kan man ta ASCII-värdet av B, vilket skulle ge ett helt annat tal $x=66$.

För att göra beräkningarna så enkla som möjligt väljer vi det första alternativet, vilket ger oss ett tal $x=2$.

Avsändaren kan nu kryptera $x$ genom att utföra den matematiska beräkningen $y=x^e = 2^3 = 8\ (\text{mod }33)$. Denna beräkning ger alltså ett nytt tal $y$ som avsändaren kan skicka till oss.

Magin med RSA är att de publika och privata nycklar har egenskapen att den privata nyckeln kan återskapa talet $x$ utifrån det krypterade värdet $y$. Vi som tagit emot $y=8$ kan alltså få ut originalmeddelandet genom att beräkna: $x=y^d = 8^7 = 2\,097\,152 = 2\ (\text{mod }33)$.

Från detta exempel så känns detta kanske inte som en särskilt säker kryptering, eftersom det beror på att den privata nyckeln inte går att beräkna, men i praktiken så är det väldigt (väldigt) svårt att beräkna $d$ om man bara känner till den publika nyckeln $e$ och $n$ – ifall talen är tillräckligt stora.

Signera data. När man signerar data så är det för att man vill att andra ska kunna kontrollera att datat är korrekt och kommer från korrekt person. Antag exempelvis att vi har ett viktigt kontrakt sparat som en pdf-fil. Man kan beräkna exempelvis en SHA1-hash av denna fil, vilket ger oss ett hash-värde $h$. Därefter kan vi med vår privata nyckel beräkna en signatur $s=h^d\text{ (mod }n)=s^7\text{ (mod }33)$. Denna signatur $s$ kan man sedan skicka tillsammans med sin pdf till den önskade mottagaren. Mottagaren har då möjlighet att beräkna SHA1-hashen $h$ av pdf-filen, och kan med den publika nyckeln beräkna värdet $z=s^e\text{ (mod }n)$. Ifall signaturen är korrekt kommer det beräknade värdet $z$ vara lika med hash-värdet $h$, och mottagaren kan då vara säker på att pdf-filen verkligen kommer från oss.

Med denna uppfräschning av RSA så är vi nu fullt redo för dagens uppgifter.

Challenge 42: Bleichenbacher’s e=3 RSA Attack

I dagens samhälle används RSA överallt, ofta i samband med digitala certifikat. Digitala certifikat används bland annat på internet för att verifiera och kryptera trafiken till olika hemsidor, och i kreditkort för att utföra betalningar på ett säkert sätt.

Det kan kanske låta märkligt, men i just kreditkort det är väldigt vanligt att välja den publika nyckeln $e=3$. Det ger två omedelbara frågor:

Varför väljer man $e=3$? En anledning är att kreditkort inte är särskilt kraftfulla, och att beräkna $x^3$ är en relativt enkel operation.
Hur kan det vara säkert att välja $e=3$? Jo, för att även om $e=3$ är ett väldigt litet tal, så är det ändå väldigt svårt att hitta den motsvarande exponenten $d$ för den privata nyckeln.

Att säga att $e=3$ är säkert kräver dock att man gör korrekta implementeringar. Vi såg redan i förra blogg-avsnittet en sårbarhet kopplad till $e=3$, och grundproblemet är i princip följande:

Antag att vi har en publik nyckel med $e=3$ och ett väldigt stort $n$.
Antag att vi vill kryptera/verifiera ett väldigt litet tal, exempelvis $x=2$.
Då gäller att $y=2^3=8\ (\text{mod }n)$.
Eftersom $x$ var så litet så blev $x^3$ mindre än $n$, vilket innebär att man kan beräkna $x$ genom den klassiska tredje-roten ur $y$. En angripare kan alltså knäcka krypteringen genom att beräkna $x = \sqrt[3]{y} = \sqrt[3]{8}=2$.

Samma grundproblem (att $x^e$ är mindre än $n$) finns även för när man ska verifiera en signatur – en angripare kan skapa en falsk signatur genom att skapa ett tal $f$ som är tredje-roten ur ett värde $F$ de vill fejka, och en ovetande mottagare kan beräkna $f^3=F$ och tro att signaturen då är korrekt.

För att undvika att $x^e$ blir mindre än $n$ kan man se till att lägga till padding på $x$ så att man forcerar att värdet blir tillräckligt stort. Ett sätt att göra detta på kan vi se i följande exempel:

Låt $n=999\,999\,822\,000\,007\,597$.
Låt $x=2$.
I hexadecimal notation kan vi skriva $n=$0x0D:E0:B6:8A:35:C3:A9:AD, bestående av 8 bytes.
Vi ser därför till att padda $x=2$ så att den också får 8 bytes genom att i hexadecimal notation sätta
$x_{pad}=$0x00:01:FF:FF:FF:FF:00:02.
Med andra ord lägger man till en sträng av 0x00:01:FF:...:FF:00 framför $x$, med så många FF så att strängen blir lika lång som $n$. Nu kommer $x_{pad}$ vara ett mycket stort tal, så $x_{pad}^e$ kommer garanterat vara större än $n$.

Tänk nu exempelvis att vi vill verifiera certifikatet för en webbsida vars signatur använder en publik nyckel $e=3$ och ett stort tal $n$.

Vi laddar ned certifikatet tillsammans med dess signatur $s$.
Vi beräknar SHA1-hashen $h$ av certifikatet.
Vi beräknar $z=s^3\ (\text{mod }n)$
Eftersom man använder padding så kontrollerar vi att $z$ börjar med 0x00:01:FF. Därefter så letar vi efter där följden av FF slutar följt av en ensam 00-byte.
Efter denna padding-sträng vet vi att nästföljande 20 bytes ska vara hashen (eftersom en SHA1-hash är 20 bytes lång), så vi plockar ut dessa bytes, vilket ger oss ett värde $w$.
Nu kontrollerar vi att $w=h$ och om detta stämmer så vet vi att certifikatet är tillförlitligt.

Låter detta rimligt? Om ni svarar ”Ja” på denna fråga så har ni tyvärr missat ett allvarligt fel som skulle kunna leda till att man godtar helt fejkade certifikat. Man behöver dock inte skämmas, för samma fel gjordes av de som skrev verifieringsalgoritmen för TLS-certifikat i Firefox för många år sedan.

Så vad är missen?

Jo, misstaget är att man hårdkodat in att de 20 efterföljande bytesen ska vara hashen – man missar att kontrollera att strängen inte är längre än så. Funktionen som tar bort paddingen är helt enkelt felaktigt konstruerad.

Varför är det så allvarligt?

Låt oss ta ett exempel: För att göra talen mer lättberäknade så låtsas vi att vi vill fejka signaturen av en hash som bara är en enda byte lång: $h=\,$0x34. Låt oss även säga att den publika modulon $n$ är väldigt stor i detta fall (så stor att vi inte behöver bekymra oss).

Vi lägger nu på en medvetet för kort padding-sträng och skapar $s=\,$0x00:01:ff:ff:00:34.

I klassisk decimal notation gäller att $s=8\,589\,869\,108$.

Vi väljer nu att förstora $s$ genom att lägga på en stor mängd 0:or. Sätt exempelvis $z=s\cdot1\,000\,000\,000\,000\,000\,000\,000 = 8\,589\,869\,108\,000\,000\,000\,000\,000\,000\,000$.

Beräkna nu tredjeroten ur $z$ och avrunda uppåt till närmaste heltal, vilket ger $\sqrt[3]{z}\approx20\,479\,947\,958=r$, och notera att:

$r^3=\color{green}{8\,589\,869\,108}\,175\,771\,697\,351\,180\,741\,912$.
$z\phantom{^3}=\color{green}{8\,589\,869\,108}\,000\,000\,000\,000\,000\,000\,000$.

Talet $r$ är i detta fall en fejkad signatur av hash-värdet 0x34 som skulle accepteras av den felaktiga verifieringsmetoden som beskrevs ovan:

Först beräknas $r^3\ (\text{mod }n)$, därefter ser man att resultatet börjar 0x00:01:ff:ff:00, och därefter ”vet” man att nästkommande 1 byte (eller 20 bytes i ett mer verkligt scenario) är hashen.
Algoritmen missar helt enkelt att det finns massa skräp-siffror efter hashen.

Hur många 0:or som man behöver lägga till på $s$ för att detta ska fungera kan man helt enkelt testa sig fram till. Vi valde i exemplet ovan det minsta möjliga antalet, men även fler 0:or hade fungerat bra – man måste bara försäkra sig om att $z$ håller sig under den publika modulon $n$.

(Notera att PKCS1.5-standarden även lägger till en speciell ASN.1-bytesträng i paddingen, men detta är irrelevant för beskrivningen, så detta ignorerades).

Lärdom: Ta inga genvägar i era implementationer!

Challenge 43-45 DSA

Dessa tre uppgifter handlar om DSA (Digital Signature Algorithm), vilket är väldigt likt RSA, men vi väljer att avvakta med dessa till en annan gång för att idag inrikta oss på ren RSA.

Challenge 46: RSA parity oracle

Nu antar vi att RSA konfigurerats korrekt med bra implementerad padding. En helt annan klassisk typ av implementationsmisstag som vi stött på under denna blogg-serie är en typ av miss som läcker information av något slag och på så sätt skapar ett orakel som en angripare kan använda för att få ut information som den inte borde ha åtkomst till. Exempel på sådana som vi sett är:

Padding-orakel: Ett orakel som läcker information gällande ifall den dekrypterade (okända) textsträngen har korrekt padding eller ej.
Enkodings-orakel: Ett orakel som läcker information gällande ifall den dekrypterade (okända) textsträngen innehåller läsbara tecken eller ej.
Tids-orakel: Ett orakel som läcker information om algoritmen baserat på tidsåtgången innan svar erhålles.

Vi kommer i denna uppgift betrakta ett annat sorts orakel: ett Paritets-orakel som läcker information gällande ifall det dekrypterade (okända) talet är udda eller jämnt.

Antag att vi vet att $y=x^e\ (\text{mod }n)$ är ett RSA-krypterat meddelande, för något okänt tal $x$, med ett publikt nyckelpar $e, n$.
Antag att det finns en funktion $F$ som tar godtyckliga krypterade värden och returnerar ifall motsvarande dekrypterade värden är jämna eller udda.
Målet är att dekryptera $y$ och alltså hitta $x$.

De skriver i uppgiftsbeskrivningen att detta är ett lite krystat exempel, men det är ett kul problem, så vi ignorerar verklighetsförankringen i detta fall. Man kan tänka sig att det finns en webbapplikation som tar emot krypterade meddelanden, och att dess backend förväntar sig att det dekrypterade meddelandet är jämnt, annars så genereras ett felmeddelande som läcks till besökaren på hemsidan. Kanske förväntar sig webbsidan att det dekrypterade meddelandet ska beskriva hur många som förväntas komma på en parmiddag?

Det roliga är att vi nu kan leka runt med matematik. Vi kan börja med att beräkna $y_2=2^e\cdot y\ (\text{mod }n)$ och fråga oraklet $F$ om värdet på $F(y_2)$. Oraklet kommer då ta värdet $y_2$ och beräkna:

$$y_2^d=(2^e\cdot y)^d=(2^e\cdot x^e)^d=(2\cdot x)^{e\cdot d}=2\cdot x\ (\text{mod }n).$$

Alltså, oraklet kommer svara på om $2x\ (\text{mod }n)$ är udda eller jämnt. Detta ger faktiskt väldigt mycket information. Vi vet nämligen att $0\le x<n$ och att $2x$ är ett jämnt tal (eftersom det har en faktor 2 i sig). Vi vet dessutom att $n$ är ett udda tal (eftersom det är produkten av två stora primtal), så:

Ifall $2x\ (\text{mod }n)$ är udda så måste $2x>n$.
Ifall $2x\ (\text{mod }n)$ är jämnt så måste $2x\le n$.

Med andra ord,

Ifall $F(y_2)=1$ så vet vi att $\frac{n}2< x<n$
Ifall $F(y_2)=0$ så vet vi att $0\le x<\frac{n}2$

Vi kan nu skapa $y_4 = 2^e\cdot y_2\ (\text{mod }n)$. På samma sätt som ovan får vi då att oraklet kommer svara på om $4x$ är större eller mindre än $n$.

Om $F(y_2)=1$ och $F(y_4)=1$ så vet vi att $\frac{3n}4< x<n$.
Om $F(y_2)=1$ och $F(y_4)=0$ så vet vi att $\frac{n}2< x<\frac{3n}4$
Om $F(y_2)=0$ och $F(y_4)=1$ så vet vi att $\frac{n}4< x<\frac{n}2$
Om $F(y_2)=0$ och $F(y_4)=0$ så vet vi att $0\le x<\frac{n}4$

Iterativt kan vi på samma sätt skapa $y_8, y_{16}, y_{32},\ldots$, vilket i varje steg halverar intervallet som $x$ kan ligga i. Efter $log_2(n)$ steg kommer man därför ha fått ned intervallet så litet att man vet exakt vad $x$ är.

Magi! Eller helt enkelt: Matematik!

Vi slutar här för denna gång, och till de få läsare som faktiskt tagit sig igenom denna text säger vi: Bra jobbat!

 Publicerat 2025-05-16 Skrivet av Gustav Sædén Ståhl