Cryptopals del (9, MAC=0xdeadbeefcafe) 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)

Välkommen till Simovits bloggserie om Cryptopals. I denna serie går vi igenom uppgifterna som finns tillgängliga på sidan cryptopals.com. Dagens avsnitt kommer behandla uppgifterna 28-32. Ha kul.

Challenge 28: Implement a SHA-1 keyed MAC

I denna uppgift så ska vi implementera en så kallad SHA-1 keyed MAC. Ordet MAC står här för Message Authentication Code och används för att verifiera meddelanden mellan två parter. Tanken är att två parter enas om en hemlig nyckel som bara de känner till. När den ena skickar ett meddelande \(M\) till den andra så kan avsändaren använda den hemliga nyckeln för att skapa en signatur (MAC) av meddelandet som den skickar tillsammans med själva meddelandet. Mottagaren kan sedan också beräkna signaturen av meddelandet (då hen också känner till den hemliga nyckeln) och kan jämföra denna signatur med det som skickades av avsändaren. Om signaturerna inte överensstämmer så kan mottagaren förstå att meddelandet ej skickats av den önskade avsändaren.

Observera att man ej ska blanda ihop denna typ av MAC med MAC-adresser där MAC istället är en förkortning för Media Access Control. Det är väldigt praktiskt med samma val av förkortningar för två ganska centrala element inom IT-säkerhet.

För att kunna implementera denna SHA-1 keyed MAC så kan det vara bra att förstå de olika orden som förekommer i uttrycket. Ordet MAC har vi redan beskrivit, och keyed innebär helt enkelt att det ska vara med en nyckel i algoritmen. Det som återstår att förstå är SHA-1, vilket är ett exempel på en hash-funktion.

En hash-funktion är egentligen bara en funktion som tar en sträng av godtycklig längd och returnerar en sträng av någon fix längd. Inom IT-säkerhet så brukar man dock med en hash-funktion underförstått syfta på en kryptografisk hash-funktion, med vilket man menar en hash-funktion \(\mathbf{H}\) med följande attribut:

• Pre-image resistance: Givet en beräknad hash \(H\) ska det vara beräkningstungt att hitta en sträng \(M\) så att \(\mathbf{H}(M)=H\).
• Second pre-image resistance: Givet en fixerad sträng \(M_1\) ska det vara beräkningstungt att hitta en annan sträng \(M_2\) så att \(\mathbf{H}(M_1)=\mathbf{H}(M_2)\).
• Collision resistance: Det ska mer allmänt vara beräkningstungt att hitta två olika strängar \(M_1\) och \(M_2\) så att \(\mathbf{H}(M_1)=\mathbf{H}(M_2)\).

Med ”beräkningstungt” menar vi att det i praktiken ska vara omöjligt att utföra dessa beräkningar med dagens datorer. De flesta (som läser dessa typer av bloggar) har säkert hört talas om ett antal olika hash-funktioner såsom SHA1 och MD4. Just dessa två är kanske inte längre några bra exempel på kryptografiskt säkra hashar då man har hittat svagheter i deras definitioner, men de används fortfarande i stor omfattning. Låt oss därför ge en övergripande beskrivning av hur de definieras.

Merkle-Damgård-konstruktionen

Många av dagens hash-funktioner definieras som specialfall av den så kallade Merkle-Damgård-konstruktionen. Nedan ges pseudo-kod för denna:

MD(M, P, H, C, b): 
   M' = M+P 
   for B in "blocks of length b of M'": 
       H = C(H, B) 
   return H

De olika argumenten som användes i koden ovan är:

• M: Meddelandet vars hash-värde ska beräknas.
• P: en padding-sträng som appendas till meddelandet M och som ser till att längden på meddelandet M’=M+P är en jämn multipel av ett tal b (vilket med andra ord innebär att M’ består av ett antal block B av storlek b). En padding-sträng P beräknas med hjälp av en padding-funktion som enbart beror på längden av det som ska ”paddas”.
• H: Ursprungligen en sträng som initerar hash-beräknandet, som sedan modifieras under for-loopens gång, och i slutändan blir hashen av M.
• C: En funktion som tar en sträng H, tillsammans med en sträng B av längd b, och returnerar ett nytt H. Man kan tänka sig att C är någon sorts blandarfunktion som i varje steg blandar in lite nytt material B i strängen H för att komplicera H mer och mer.

I ett försök att göra följande text mer lättläst så använder vi notationen att versaler används för strängar (exempelvis M) och gemener för längden på motsvarande sträng (exempelvis att m är längden av strängen M). Dessutom skriver vi funktioner med fet-stil för att särskilja dem från strängar.

Flera av de kändaste kryptografiska hash-funktionerna är konstruerade efter denna princip. Exempelvis har vi:

• \(\text{SHA1}(M) = \textbf{MD}(M, P = \mathbf{P}_{\text{SHA1}}(m), H_{\text{SHA1}}, \mathbf{C}_{\text{SHA1}}, b=64)\)
  där \(H_{\text{SHA1}} = \verb!0x67452301efcdab8998badcfe10325476c3d2e1f0!\)
  \(\quad\)
• \(\text{MD4}(M) = \textbf{MD}(M, P = \mathbf{P}_{\text{MD4}}(m), H_{\text{MD4}}, \mathbf{C}_{\text{MD4}}, b=64)\)
  där \(H_{\text{MD4}} = \verb!0x67452301efcdab8998badcfe10325476!\)
  \(\quad\)
• \(\text{SHA256}(M) = \textbf{MD}(M, P=\mathbf{P}_{\text{SHA256}}(m), H_{\text{SHA256}}, \mathbf{C}_{\text{SHA256}}, b=64)\)
  där \(H_{\text{SHA256}} = \verb!0x6a09e667bb67ae853c6ef372a54ff53a510e527f9b05688c1f83d9ab5be0cd19!\)

En läsare kan här ha rätt i att anse att detta inte riktigt säger så mycket då vi inte sagt vad exempelvis \(\textbf{C}_{\text{SHA1}}\) och \(\textbf{P}_{\text{SHA1}}\) är för funktioner (vilket också är vad som faktiskt skiljer SHA1 från MD4, etc), men dessa kan den intresserade läsaren hitta på andra delar av internet. Det som är av intresse för oss är själva idén med Merkle-Damgård-konstruktionen.

För enkelhetens skull skriver vi \(\mathbf{P}(m) = \mathbf{P}_{\text{SHA1}}(m)\), och vi skriver \(p(m)\) för längden på \(\mathbf{P}(m)\). Låt oss dessutom utelämna att skriva ut b=64 överallt.

Sha1 keyed MAC

Givet ett meddelande \(M\) och en hemlig nyckel \(K\) definierar vi nu meddelandets MAC som: $$\text{MAC} = \text{SHA1}(K+M) = \text{MD}(K+M, \mathbf{P}(k+m), H_{\text{SHA1}}, \mathbf{C}_{\text{SHA1}})$$

där vi med \(K+M\) helt enkelt menar att vi sätter ihop strängarna K och M efter varandra.

Som är standard för cryptopals så börjar man ofta med att implementera någon typ en säkerhets-funktion (som faktiskt används inom IT-branchen), för att sedan direkt knäcka den i nästa uppgift. Samma sak gäller för SHA-1 keyed MACS…

Challenge 29: Break a SHA-1 keyed MAC using length extension

Antag att du har fångat upp ett meddelande tillsammans med dess signatur, som skickats mellan två parter som använder sig av en SHA-1 keyed MAC. Låt oss säga att \(M=\text{”Gustav skriver så tråkiga blogginlägg.”}\) med \(\text{MAC}=\verb!0xcdc8599a6b9483952c553ffdaecdf1e7c7bb7532!\).

Eftersom du såklart inte håller med om detta så kommer du på idén att modifiera meddelandet innan det levereras till den riktiga mottagaren genom att lägga till \(N=\)”Haha, jag bara skämtade såklart!” till originalmeddelandet. Detta kommer dock inte fungera eftersom mottagaren kommer se att MAC-signaturen för ”Gustav skriver så tråkiga blogginlägg! Haha, jag bara skämtade såklart!” inte överensstämmer med den MAC som vi har kommit över. Då vi inte känner till den hemliga nyckeln \(K\) som de två parterna kommit överens om så kan vi heller inte skapa en ny MAC-signatur för att lura mottagaren. Eller…?

Det visar sig nämligen att om vi skapar meddelandet $$M_2 = M+\mathbf{P}(k+m)+N$$ och beräknar $$\text{MAC}_2 = \mathbf{MD}(N, P=\mathbf{P}(k+m+p(k+m)+n), H=\text{MAC}, \mathbf{C}_{\text{SHA1}})$$ så kommer mottagaren verifiera att denna MAC-signatur är giltig för meddelandet \(M_2\)! Det kanske kan anses aningen orimligt att ett meddelande innehåller \(\mathbf{P}_{SHA1}(k+m)\) då detta bara är nonsens-tecken som används för padding, men det är ju inget som hindrar avsändaren att skicka nonsens, så låt oss ignorera orimligheten i detta. Det häftiga är att denna MAC-signatur kan vi faktiskt skapa, utan att känna till den hemliga nyckeln \(K\)! Okej, vi behöver känna till nyckellängden \(k\), men den kan man ju alltid gissa på – och om mottagaren är en dator så brukar man få några chanser på sig innan den slutar lyssna…

Att detta är en lösning på problemet att lura mottagaren är ju dock inte så intressant, det intressanta är hur detta faktiskt funkar, så låt oss undersöka detta.

Som ett tanke-experiment låtsas vi att avsändaren (som känner till \(K\)) skulle ha velat skicka meddelandet $$M_2=M+\mathbf{P}(k+m)+N.$$ Låt \(X=K+M_2\). I så fall så skulle nästa steg för avsändaren ha varit att räkna ut MAC-signaturen genom att beräkna $$\text{SHA1}(X)=\mathbf{MD}(X, P=\mathbf{P}(x), H_{\text{SHA1}}, \mathbf{C}_{\text{SHA1}})$$ där \(x = k+m+p(k+m)+n\). Vi påminner oss om att Merkle-Damgård-koden ser ut så här:

MD(X, P(x), H, C): 
   X' = X+P(x) 
   for B in "blocks of length b of X'": 
       H = C(H, B) 
   return H

Första steget är alltså att skapa $$X’=X+\mathbf{P}(x)=K+M+\mathbf{P}_{SHA1}(k+m)+N+\mathbf{P}(x).$$

För att förtydliga beräkningen låter vi nu \(Y = K+M+\mathbf{P}_{SHA1}(k+m)\) och \(N’=N+\mathbf{P}(x)\). Då gäller att \(X’=Y+N’\) och eftersom både X’ och Y har längder som är multiplar av b, så har även N’ en längd som är en multipel av b.

For-loopen i Merkle-Damgård-funktionen:

for B in "blocks of length b of X'":         
    H = C(H, B) 

kan därför delas upp i två for-loopar, vilket ger att pseudo-koden istället kan skrivas:

MD(X=Y+N, P(x), H, C): 
   //Y = K+M+P(k+m) 
   N' = N+P(x)
   for B in "blocks of length b of Y": 
       H = C(H, B) 
   for B in "blocks of length b of N'": 
       H = C(H, B) 
   return H

Det roliga (eftersom \(Y=K+M+\mathbf{P}(k+m)\)) är att den första for-loopen kommer resultera i ett värde på \(H\) som är lika med MAC-signaturen för meddelandet \(M\), vilket alltså blir input till den andra for-loopen över \(Z=N+\mathbf{P}(x)\). Vi skulle alltså kunna ignorera hela strängen \(Y\) samt den första for-loopen om vi istället istället börjar med H=MAC. Med andra ord: vi får samma svar om vi har följande input till Merkle-Damgård-funktionen:

MD(N, P(x), H=MAC, C): 
   N' = N+P(x) 
   for B in "blocks of length b of N'": 
       H = C(H, B) 
   return H

Notera nu att detta är precis det som vi kom fram till ovan, nämligen att $$\text{MAC}_2 = \mathbf{MD}(N, P=\mathbf{P}(k+m+p(k+m)+n), H=\text{MAC}, \mathbf{C}_{\text{SHA1}})$$ är en giltig signatur för meddelandet \(M_2=M+P(k+m)+N\)!

Challenge 30: Break an MD4 keyed MAC using length extension

Att utföra length-extension-attacker med SHA1 som vi gjorde i förra uppgiften är väldigt klassiskt, så det finns många implementationer av föregående attack att hitta på internet (vilket också är varför vi i denna blogg-serie hellre försöker förstå snarare än att implementera detaljer). För att tvinga oss att behöva tänka så skapade cryptopals-författarna följande uppgift där man ska göra precis samma sak för MD4 som vi nyss gjorde för SHA1. Men eftersom vi ”löste” uppgiften rent abstrakt så använde vi aldrig någonting som var specifikt för SHA1 – hela tankekedjan funkar precis lika bra om vi skulle skrivit MD4 eller SHA256 istället.

Som lite kul kuriosa för läsaren som tagit sig ändå hit så är exempelvis den mer moderna hash-funktionen SHA-3 inte uppbyggd genom Merkle-Damgård-konstruktionen, och är heller inte påverkad av denna attack-typ.

Challenge 31: Implement and break HMAC-SHA1 with an artificial timing leak

När man insåg att \(\text{MAC}=\mathbf{H}(K+M)\) inte var en säker algoritm för att skapa signaturer (trots att nyckeln \(K\) var hemlig) så var det några smarta människor som tänkte ett tag och kom på att de istället kunde definiera en förbättrad form av signatur av typen \(\text{HMAC}=\mathbf{H}(K+\mathbf{H}(K+M))\), där HMAC står för Hash-based Message Authentication Code. Denna signatur visade sig vara mycket bättre än den MAC vi sett ovan då den inte påverkas av så kallade hash-förlängningsattacker som vi sett exempel på.

När man går in på detaljer så visar det sig att man inte vill använda samma nyckel \(K\) två gånger i beräkningarna, och istället för att ha två olika nycklar så definierade man två funktioner (som vi för stunden kallar \(\mathbf{F}\) och \(\mathbf{G}\) och utelämnar deras enkla definitioner) och sätter $$\text{HMAC}=\mathbf{H}\bigl(\mathbf{F}(K)+\mathbf{H}(\mathbf{G}(K)+M)\bigr).$$

Det finns ingen attack liknande den mot MAC-signaturer som fungerar för HMAC, så i denna uppgift ska vi istället analysera en helt annan form av svaghet (och vi vill poängtera att HMAC-definitionen är helt oskyldig):

Låt oss anta att det finns en webbserver som tar emot ett meddelande med en tillhörande HMAC, och verifierar att meddelandet stämmer med HMAC-signaturen. Webbservern gör följande: Då den känner till den hemliga nyckeln kan den själv räkna ut en HMAC för meddelandet och jämföra detta resultat med den signatur som skickades med i förfrågan. Låt oss anta att denna jämförelse av strängar görs en byte i taget och att webbservern returnerar ”Fail” så fort som den identifierar en skillnad mellan strängarna. För att göra det mer tydligt så antar vi att varje byte-jämförelse tar 50 millisekunder att utföra. Detta är ytterst orealistiskt, men denna typ av sårbarhet förekommer ibland i vissa programspråk (exempel på osäker compare-funktion i PHP), men i de fallen så är tidsskillnaderna avsevärt mycket mindre än i detta exempel där det istället är idén som ska belysas.

Så, vi tänker oss att vi har en webbserver som vi vill skicka ett meddelande till (exempelvis \(M=\verb!”admin=true”!\)) som webbservern sedan verifierar med hjälp av den osäkra algoritmen som beskevs ovan. Vi kan då börja med att skicka en påhittad HMAC med enbart nollor, och sedan iterativt ändra den första byten i vår HMAC-signatur tills dess att det tar längre tid för oss att få ett svar. Ett längre svar innebär troligtvis att webbservern inte bara jämfört första byten utan även den andra (vilket den enbart gör om den första byten var korrekt). På så sätt lyckas vi identifiera den första byten i den korrekta HMAC-signaturen, och kan istället iterativt börja modifiera byte nummer två, tills dess att det tar ännu längre tid att få ett svar (vilket då innebär att vi även gissat rätt även på byte nummer två). Så kan man hålla på tills dess att man fått ut hela HMAC-signaturen!

Ett annat sätt att se på denna attack-metod är att den observerade tidsläckan kan användas för att skapa ett orakel som ger information om hash-algoritmen. Oraklet tar emot ett värde och returnerar om en byte är korrekt eller ej (beroende på hur lång svarstid man får). En uppmärksam läsare kanske inser att detta är väldigt likt det padding-orakel som vi sett i en tidigare del av denna bloggserie.

Som alla vet så kan en dator ibland bli seg helt utan uppenbar anledning, eller börja bråka på något annat sätt, så det finns en risk för att man får falsk-positiva-svar via denna metod. Oraklet kanske inte alltid är sanningsenligt… Därför kan man behöva utföra testerna flera gånger för att försäkra sig om att det inte var en slump att svaret tog längre tid på sig för en given byte.

Denna uppgift är kanske mest lik det som man ser på TV när någon hackar sig in i en dator eller någon låst dörr, när de knäcker en hemlig kod ett tecken i taget. Så själva setupen i detta fall är kanske inte helt rimlig, men i fantasins värld så måste detta vara någon form av best-practice…

Challenge 32: Break HMAC-SHA1 with a slightly less artificial timing leak

I denna uppgift ska man dra ned tiden det tar för en byte-jämförelse från 50 millisekunder till 5 millisekunder, och sedan lösa uppgiften igen. Detta är mer av en övning i implementations-förbättring då mängden falsk-positiva kommer öka när tidsrymden blir kortare. Sånt ignorerar vi i denna blogg-serie.

Sammanfattning

I dagens avsnitt har vi sett några olika exempel på meddelande-signaturer och hur de kan knäckas. Speciellt så har vi sett exempel på hash-förlängningsattacker, vilket är en klassisk attackteknik som alla IT-säkerhetsspecialister bör förstå! Vi avslutade med att titta lite snabbt på hur man kan utnyttja tidsläckor till att skapa ett orakel som lät oss knäcka en HMAC-signatur en byte åt gången.

På återseende!