Rebound attack

Rebound attack är en teknik för kryptoanalys av kryptografiska hashfunktioner . Denna attack publicerades först av Florian Mendel, Christian Rechberger, Martin Schlaffer och Sören Thompson 2009. Den var avsedd att attackera AES -liknande algoritmer som Whirlpool och Grøstl , men visade sig senare vara tillämpbar på andra konstruktioner som Keccak , JH och Skein också .

Huvudidé

Rebound Attack  är en statistisk hashattack som använder roterande och differentiell kryptoanalys för att hitta funktionskollisioner och sårbarheter .

Huvudidén med attacken är att studera de differentiella egenskaperna hos ett blockchiffer (eller dess fragment), permutation eller andra kryptografiska algoritmer på låg nivå. Att hitta värden som uppfyller egenskaperna uppnås genom att dela upp den primitiva algoritmen i 3 delar: .  - den inre fasen, och tillsammans utgör den yttre fasen. Angriparen väljer värden som deterministiskt implementerar en del av den externa fasens differentialegenskaper och kompletterar resten av egenskaperna i en sannolikhetsform.

Rebound attack inkluderar 2 steg:

  1. Den inre fasen täcker en del av differentialegenskaperna som är svåra att utföra i probabilistisk form. Här är målet att hitta många lösningar för denna del av egenskaperna med låg genomsnittlig tidskomplexitet . För att uppnå detta mål måste motsvarande ekvationssystem som beskriver egenskapen i denna fas vara underbestämd . När man letar efter en lösning finns det många frihetsgrader som ger många utgångspunkter. Ingångsfasen kan upprepas flera gånger för att få tillräckligt med poäng för att framgångsrikt utföra utmatningsfasen.
  2. I den yttre fasen används de matchade paren av den inre fasen i beräkningarna framåt och bakåt. Vanligtvis och har en låg sannolikhet, så det är nödvändigt att upprepa den interna fasen för att få fler startpunkter.

Fördelen med att använda en ingångs- och två utgångsfaser av algoritmen är möjligheten att beräkna komplexa differentialegenskaper mer effektivt och exakt. Denna metod är effektivare än vanliga differentialmetoder.

En detaljerad beskrivning av attackerande hashfunktioner med AES-liknande komprimeringsfunktioner

Överväg hashfunktioner som använder AES- liknande substitutions- och permutationsblockchiffer som komprimeringsfunktioner . Denna komprimeringsfunktion består av ett antal omgångar av S-boxar och linjära transformationer. Huvudidén med attacken är att bygga en differentialkarakteristik, som har den mest komplexa beräkningsdelen i mitten. Denna del kommer att användas i den inre fasen, medan de mer lätträknade delarna av karaktäristiken kommer att vara i den yttre fasen. Ekvationssystemet som beskriver egenskaperna i den inre fasen måste vara underbestämd för att erhålla en uppsättning utgångspunkter i den yttre fasen. Eftersom de svårare delarna av karakteristiken finns i den inre fasen, använder den yttre fasen enkla funktioner för att beräkna differentialegenskaperna. I början har den interna fasen ett litet antal aktiva (icke-noll) bytes , mot mitten ökar deras antal avsevärt, och i slutet av fasen minskar det igen till ett litet antal. Huvudtanken är att få många aktiva bytes in och ut ur S-boxen mitt i fasen. Egenskaperna kan effektivt beräknas genom att använda skillnadsvärdena i början och slutet av fasen och matcha ingången och utsignalen från S-boxen.

I den externa fasen kontrolleras de matchade egenskaperna i framåt- och bakåtriktningen för att avgöra om de matchar de önskade differentialegenskaperna. Vanligtvis syftar det till att hitta effektiva värdepar av trunkerade algoritmer, eftersom det är här det har störst sannolikhet att lyckas. Möjligheten att hitta de önskade egenskaperna i den externa fasen beror direkt på antalet aktiva bytes och deras placering i egenskapen. För att uppnå kollision räcker det inte att ha skillnader av någon speciell typ; alla aktiva byte vid ingången och utgången av karaktäristiken måste ha ett värde som avbryter alla efterföljande operationer av algoritmen. Sålunda, vid design av en karakteristik, måste valfritt antal aktiva byte i början och slutet av den externa fasen vara i samma position. Att erhålla sådana bytevärden ökar sannolikheten för att erhålla yttre fasegenskaper.

I allmänhet är det nödvändigt att generera lika många inre fasegenskaper som för att erhålla mer än en förväntad uppsättning av yttre faskarakteristika. Dessutom finns det möjlighet att erhålla en nästan kollision, där vissa aktiva bytes i början och slutet av den externa fasen inte avbryter ytterligare åtgärder av algoritmen.

Ett exempel på en attack mot Whirlpool

En returattack kan användas på Whirlpool- hashfunktionen för att hitta kollisioner i 4,5 eller 5,5 omgångar. Nästan-kollisioner kan hittas i 6,5 och 7,5 omgångar. Attacken på 4,5 omgångar beskrivs nedan.

Förberäkningar

Antal beslut Frekvens
0 39655
2 20018
fyra 5043
6 740
åtta 79
256 ett

För att göra rebound-attacken mer effektiv beräknas S-box- differenstabellen innan attacken startar. Låt beteckna S-block. Sedan, för varje par, hittar vi lösningar (om några) på följande likhet

,

var  är skillnaden vid ingången, och  är skillnaden vid utgången av S-boxen. Denna 256x256 tabell låter dig hitta värden som uppfyller egenskaperna för alla möjliga par som passerar genom S-boxen. Tabellen till höger visar det möjliga antalet lösningar och sannolikheten för att de inträffar. Den första raden visar fallet med inga lösningar, den sista beskriver fallet med noll skillnad.

Utföra en attack

För att hitta en Whirlpool- kollision över 4,5 omgångar måste differentialegenskaperna i tabellen nedan beräknas. Funktionen med minst aktiva bytes är markerad med rött. Egenskapen kan beskrivas med antalet aktiva bytes i varje omgång, till exempel 1 → 8 → 64 → 8 → 1 → 1.

Trunkerad differentialkarakteristik i 4,5 omgångar av Whirlpool-hashfunktionen.
Intern fas

Syftet med den interna fasen är att slutföra de karakteristiska skillnaderna i steg 8 → 64 → 8. Detta kan göras i 3 steg:

  1. Välj ett godtyckligt värde som inte är noll för de 8 aktiva byten vid utgången av den linjära diffusionsoperationen i omgång 3. Dessa skillnader sprider sig sedan tillbaka till utgången av den cirkulära permutationsoperationen i omgång 3. På grund av egenskaperna hos den linjära diffusionsoperationen , blir alla bytes aktiva. Detta kan göras oberoende för varje rad.
  2. Välj ett värde för varje aktiv byte vid ingången av den linjära diffusionsoperationen i omgång 2 och sprid dessa skillnader framåt till ingången av den cirkulära permutationsoperationen i omgång 3. Gör detta för alla 255 skillnader som inte är noll för varje byte. Återigen kan detta göras oberoende för varje rad.
  3. I den interna fasen, med hjälp av Difference Table (DDT), kan man matcha in- och utskillnaderna (som finns i steg 1 och 2) för den cykliska permutationsoperationen i omgång 3. Varje rad kan testas oberoende, och 2 lösningar förväntas per S-box. Totalt är det förväntade antalet värden som uppfyller differentialkarakteristiken 2 64 .

Dessa steg kan upprepas med 264 olika ingångsvärden i steg 1, vilket resulterar i totalt 2128 värden som uppfyller den interna fasdifferentialkarakteristiken. Varje uppsättning av 2 64 värden kan hittas med en komplexitet på 2 8 omgångar av transformationer på grund av förberäkningssteget.

Extern fas

Den yttre fasen kompletterar dessa egenskaper på ett probabilistiskt sätt. Den använder trunkerade differentialer i motsats till intern fas. Varje referenspunkt räknas framåt och bakåt. För att få de ursprungliga egenskaperna måste 8 aktiva byte bilda 1 aktiv byte i båda riktningarna. Att konvertera 8 byte till 1 sker med en sannolikhet på 2 −56 , [1] , så att få egenskaper har en chans på 2 −112 . För att entydigt få en kollision är det nödvändigt att byten vid ingången och utgången blockerar alla efterföljande operationer. Detta sker med en sannolikhet på cirka 2−8 , i allmänhet är sannolikheten för framgång för den externa fasen 2–120 .

För att upptäcka en kollision måste minst 2 120 poäng genereras i den interna fasen. Därefter kan upptäcktsoperationen utföras med en tidskomplexitet på 1 per startpunkt, [2] därför är den slutliga tidskomplexiteten för attacken 2 120 .

Attackuppgraderingar

En grundläggande attack på 4,5 omgångar kan uppgraderas till en attack på 5,5 omgångar genom att lägga till ytterligare en omgång till insidans fas. Detta kommer att öka tidskomplexiteten för algoritmen till 2184 . [3]

Att förbättra den yttre fasen för att börja och sluta med 8 aktiva byte resulterade i en nästan kollision av 52 Whirlpool -byte , vilket utökade attacken till 7,5 omgångar med en tidskomplexitet på 2192 . [3]

Förutsatt att angriparen har kontroll över värdet på kedjan och därmed inträde i Whirlpool-nyckelgrafen, kan attacken utökas till 9,5 omgångar med en villkorligt fri kollision på 52 byte med en tidskomplexitet på 2 128 . [fyra]

Anteckningar

  1. ↑ Lamberger, Mendel, Rechberger, Rijmen, Schlaffer, 2010, sid. arton
  2. ↑ Lamberger, Mendel, Rechberger, Rijmen, Schlaffer, 2010, sid. 22
  3. ↑ 1 2 Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, sid. 25
  4. ↑ Lamberger, Mendel, Rechberger, Rijmen, Schlaffer, 2010, sid. 31

Litteratur