HAIFA

HAIFA ( engelska HAsh Iterative Framework ) är en iterativ metod för att konstruera kryptografiska hashfunktioner , vilket är en förbättring av den klassiska Merkle-Damgor-strukturen .

Det föreslogs 2007 för att öka motståndet mot många attacker och stödja möjligheten att få hashsummor av olika längd. Baserat på algoritmen har hashfunktioner som BLAKE [1] och SHAVite-3 [2] utvecklats .

Historik

Skaparna av algoritmen är Eli Biham och Or Dunkelman , israeliska kryptografer från University of Haifa . Biham är en elev till Adi Shamir , som utvecklade ett stort antal nya kryptografiska algoritmer, inklusive att bryta befintliga; Dunkelman är en kollega till Shamir i ett av projekten, och fortsatte senare sin forskning på egen hand [3] .

Merkle-Damgor-strukturen ansågs länge vara resistent mot den andra preimage-attacken , tills Princeton University -professorn Richard Dean bevisade 1999 att detta antagande är fel för långa meddelanden om det med en given sammandragningsfunktion lätt är möjligt att hitta den fixerade punkter i en sekvens. En multipelkollisionsattack och en hårdingattack (en attack på ett känt prefix) [4] [5] kunde också utföras framgångsrikt på Merkle-Damgor-strukturen .

Algoritm

Merkle-Damgor-strukturen är följande algoritm:

Det finns ett meddelande uppdelat i flera delar: . Det finns något initialvärde - och någon funktion som beräknar den mellanliggande representationen av hashfunktionen på ett visst sätt [5] : $M$ ${\displaystyle M_{1},M_{2}...M_{k))$ $IV$ $C$ $H$

h_{0}=IV

Ytterligare iterativt :

h_{i}=C(h_{i-1},M_{i})

{\displaystyle H(M)=h_{k))

Grunden för den nya HAIFA-algoritmen var tillägget av antalet hashade bitar och något slumpmässigt värde. Istället för den vanliga komprimeringsfunktionen, som nu kan betecknas enligt följande [4] :

\{0,1\}^{m_{c}}\times \{0,1\}^{n}\högerpil \{0,1\}^{m_{c}}

, där är storleken på , är storleken på blocket, (oftast är utdatastorleken samma som storleken på h)

m_{c}

h

n

{\displaystyle m=m_{c))

Begagnade:

\{0,1\}^{m_{c}}\times \{0,1\}^{n}\times \{0,1\}^{b}\times \{0,1 \}^{s}\högerpil \{0,1\}^{m_{c}}

, var är längden på antalet bitar och salt ,

b,s

den interna representationen beräknas (i enlighet med notationen som introducerades ovan):

h_{i}=C(h_{i-1},M_{i},bitar,salt)

, var

bits

är antalet bitar som hashas hittills.

För att hasha ett meddelande, följ dessa steg:

Fyll i meddelandet i enlighet med diagrammet nedan. $M$
Beräkna startvärdet för den inre cellen med storleken m enligt algoritmen som beskrivs nedan. ${\displaystyle IV_{m))$
Gå igenom alla block i det utfyllda meddelandet, beräkna vid varje steg värdet på komprimeringsfunktionen från det aktuella blocket och lägg nu till saltet och som argument. Om ett ytterligare block läggs till i meddelandet (i slutet) sätter vi värdet till noll för detta block. $Hej}$ $Mi}$ $h_{{i-1}}$ $bits$ $bits$
Trimma det sista utgångsvärdet för funktionen, om nödvändigt [4] .

Slutförande av meddelandet

I HAIFA är meddelandet utfyllt med en etta, det erforderliga antalet nollor, meddelandets längd i bitar och storleken på utmatningsblocket . Det vill säga, vi lägger till en sekvens (antalet nollor i det här fallet bör vara sådant att [4] , där , är antalet ettor och nollor, är blockstorleken: $M$ $h$ $N_{1}+N_{0}\equiv N-(M_{längd}+H_{storlek})modN$ $N_1$ $N_{0}$ $N$

$1+{0..0}+bitar+m_{c}$

Att hasha ett meddelande fyllt med storleken på utdatablocket eliminerar problemet med att hitta kollisioner, eftersom om två meddelanden och hashas med blockstorlekar och , då är det det sista blocket som sparar från kollisioner. I sin tur, genom att addera = 0 i det allra sista blocket, skapas en signal för att indikera det sista och komplementära blocket [4] . $M_{1}$ $M_{2}$ $l_{1}$ $l_{2}$ $bits$

Möjligheten att komplettera det ursprungliga meddelandet i den här algoritmen gör att du kan trunkera den hashade, och därigenom ändra storleken på den slutliga hashen [4] .

Hashlängd

Ofta i praktiken krävs olika längder på den slutliga hashen (som till exempel gjort för SHA-256 , som har två trunkerade versioner), så denna struktur implementerade också möjligheten att variera dess längd med hjälp av en speciell algoritm (för att upprätthålla motståndet mot attacker på den andra förbilden, kan du inte använda den uppenbara lösningen att ta bitar från den slutliga hashen). $m$

$IV$ - ursprungligt värde
$m$ - önskad utgångslängd
Vi betraktar det konverterade initiala värdet: $IV_{m}=C(IV,m,0,0)$
Således blir vi "wired" i de första bitarna, följt av 1 och nollor. $m$ $r$
Efter att det sista blocket har beräknats är det slutliga värdet biten av det sista värdet för kedjekomprimeringsfunktionen [4] . $m$

Algoritmens säkerhet

Beviset på att HAIFA är kollisionsbeständigt om kontraktionsfunktionen är kollisionsbeständig liknar beviset för Merkle-Damgor [4] .

Antalet hashade bitar gör det mycket svårare att hitta och använda fasta punkter. Även efter att ha hittat sådana och , för vilka , är det omöjligt att multiplicera dessa värden på obestämd tid i denna algoritm, eftersom antalet bitar kommer att förändras hela tiden [4] . $Hej}$ $Mi}$ $h_{i}=C(h_{i},M_{i},bitar,salt)$

Salt ( ), liksom , bidrar också till algoritmens stabilitet [4] : $salt$ $bits$

Låter dig ställa in säkerheten för hashfunktioner i en teoretisk modell.
Får förberäkningsbaserade attacker att flytta alla sina beräkningar online, eftersom värdet på saltet inte är känt i förväg.
Ökar säkerheten för elektroniska signaturer (eftersom man varje gång måste ta hänsyn till att det finns något slumpmässigt värde).

Nedan finns uppskattningar av HAIFAs motståndskraft mot olika typer av attacker.

Fixed point attacker

I attacken mot den andra förbilden eftersträvas ett sådant värde ${\displaystyle M^{'))$ , för vilket , det vill säga hashen från är lika med något mellanvärde i iterationer, och kombinera sedan delen av det återstående meddelandet ( som ligger till höger om ) med vårt gissade . Algoritmen erkändes dock som resistent mot denna attack, eftersom dess storlek i den förbättrade versionen lades till i slutet av meddelandet. Richard Dean pekade i sitt arbete på ett helt nytt sätt att angripa, baserat på antagandet att det är lätt att hitta fixpunkter för en given funktion (definitivt är en fix punkt en för vilken relationen är tillfredsställande ). I hans algoritm kom den saknade meddelandelängden till genom att lägga till en uppsättning fasta punkter, det vill säga vi kunde komplettera vår längd med ett tillräckligt antal repetitioner av värdet . $H(M')=h_{i}=H(M_{i})$ ${\displaystyle M^{'))$ $M$ $Mi}$ ${\displaystyle M^{'))$ $C$ $h=C(h,M_{i})$ $h$

I det här fallet skyddar HAIFA mot en fixpunktsattack, eftersom närvaron av ett salt och ett fält som innehåller antalet hashade bitar minimerar sannolikheten för upprepning av kontraktionsfunktionsvärden [4] .

Multipel kollisionsattack

För flera kollisioner beskrev den franske kryptografen Antoine Joux möjligheten att hitta meddelanden som har samma hash. Hans arbete bygger på det faktum att det är möjligt att hitta sådana kollisioner i ett block där , och sedan konstruera olika meddelanden, av alla alternativ, genom att välja antingen meddelande , eller . $2^{t}$ $t$ $C(h_{i-1},M_{i})=C(h_{i-1},M_{i}^{*})$ $2^{t}$ $t$ $Mi}$ $M_{i}^{*}$

HAIFA, trots sin komplexa struktur, garanterar inte noll framgång för en multipel kollisionsattack. Efter ovanstående ändringar av Merkle-Damgor-algoritmen har komplexiteten för att hitta kollisioner för varje block inte förändrats, men eftersom ett slumpmässigt blandat värde har dykt upp kan angriparen inte förvälja varianterna av dessa kollisioner utan att känna till det slumpmässiga värdet. Beräkningar går online [4] .

Harding attack

En hardingattack bygger på att angriparen försöker hitta ett sådant suffix för ett givet prefix som ger önskat hashvärde.

Inledningsvis byggs ett träd av olika interna värden, meddelanden Mj söks efter som leder till kollisioner mellan dessa tillstånd. Det vill säga att det finns olika värden i trädets noder och värden på kanterna . $2^{t}$ $h$ $M_{j}$
Vi bygger kollisioner på de nyligen erhållna värdena (från den tidigare nivån av trädet) tills vi når det slutliga värdet . $h$ $H$
Angriparen får då information om prefixet.
Efter att ha mottagit denna information försöker den hitta ett länkmeddelande mellan detta prefix och det önskade suffixet. Det bindande meddelandet måste uppfylla villkoret att värdet på kontraktionsfunktionen från det är lika med ett av de interna värdena på trädets första nivå. Vidare är suffixet byggt av den vanliga passagen genom trädet (eftersom dess kanter redan innehåller meddelanden som leder till det önskade resultatet). Nyckelpunkten är möjligheten att göra preliminära beräkningar; i onlineläge återstår det att bara välja önskat mellanvärde och . $h$ $h$ $M$

Det är bevisat att det är omöjligt att genomföra den första fasen av en hardingattack (att bygga ett beslutsträd) på HAIFA förrän saltvärdet är känt. Det vill säga brute-force , som beskrevs ovan, kan inte längre utföras. Villkoret för att framgångsrikt avvärja en attack är längden på det blandade meddelandet, om den önskade komplexiteten för attacken är inställd på nivån måste den bestå av minst tecken. Om denna regel inte följs, är vissa preliminära beräkningar möjliga, vilket leder till hackning av algoritmen. Om saltvärdet ändå hittades, kommer det att ta lite tid att hitta rätt plats i meddelandet på grund av närvaron av fältet [4] . $O(2^{m})$ ${\frac {m_{c}}{2}}$ $bits$

Komplexiteten av attacker på Merkle-Damgor och HAIFA algoritmer

Attack typ	Idealisk hashfunktion	MD	HAIFA (Fast värde salt)	HAIFA (med olika saltvärden)
Attack mot den första prototypen ( mål) ${\displaystyle k^{'}<2^{s))$	$2^{m_{c))$	$2^{m_{c))$	$2^{m_{c))$	$2^{m_{c))$
Attack mot en av de första prototyperna	${\displaystyle 2^{m_{c}}}/k'$	${\displaystyle 2^{m_{c}}}/k'$	${\displaystyle 2^{m_{c}}}/k'$	$2^{m_{c))$
Attack mot den andra prototypen ( block) [9] [10] $k$	$2^{m_{c))$	$2^{m_{c}}/k$	$2^{m_{c))$	$2^{m_{c))$
Attack mot en av de andra prototyperna ( block, meddelanden) $k$ ${\displaystyle k^{'}<2^{s))$	${\displaystyle 2^{m_{c}}}/k'$	$2^{m_{c}}/k$	${\displaystyle 2^{m_{c}}}/k'$	$2^{m_{c))$
Kollisioner	$2^{m_{c}/2}$	$2^{m_{c}/2}$	$2^{m_{c}/2}$	$2^{m_{c}/2}$
Flera kollisioner ( är antalet kollisioner) [9] $k$	${\displaystyle 2^{m_{c}(k-1)/k))$	$\left\lceil {log_{2}k}\right\rceil 2^{m_{c}/2}$	$\left\lceil {log_{2}k}\right\rceil 2^{m_{c}/2}$	$\left\lceil {log_{2}k}\right\rceil 2^{m_{c}/2}$
Flockning [11] [12]	-	off-line: $2^{m_{c}/2+t/2}$ Uppkopplad: ${\displaystyle 2^{m_{c}-t))$	off-line: $2^{m_{c}/2+t/2}$ Uppkopplad: ${\displaystyle 2^{m_{c}-t))$	off-line: $2^{m_{c}/2+t/2+s}$ Uppkopplad: ${\displaystyle 2^{m_{c}-t))$

Applikationer

HAIFA kan, enligt utvecklarna, ligga till grund för många kryptografiska algoritmer, eftersom det är en ny förbättrad grunddesign. Det har bevisats att det kan användas för att utveckla randomiserade hashfunktioner [13] , den inslagna Merkle-Damgard-funktionen ( eng. Enveloped Merkle-Damgard , RMC [14] [15] , wide-pipeline hash [16] .

Bred pipelined hash

Att få en wild-pipe-hashkonstruktion med HAIFA är ganska lätt; i själva algoritmen, för att öka komplexiteten, gjordes längden på de inre blocken dubbelt så stor som längden på det sista blocket (därför finns det två komprimeringsfunktioner och ). Det är möjligt att härleda formeln för den pipelinerade hashen direkt, givet att det är trivialt att hitta det sista blocket i HAIFA, eftersom nollor sätts där [4] . $C^{'}$ $C^{''}$ $bits$

Formeln för att konvertera från HAIFA till en hash med bred pipeline är:

$C_{HAIFA}(h_{i-1},M_{i},bits,s)={\begin{cases}C''(C'(IV_{2},h_{i-1}| |fixpad(M_{i}))),&{\text{if }}{\text{ sista block}}\\C'(h_{i-1},M_{i}),&{\text{ }}{\text{annars}}\end{cases}}$

var $C':\{0,1\}^{m_{c}}\times \{0,1\}^{n}\högerpil \{0,1\}^{m_{c}}$

$C'':\{0,1\}^{m_{c}}\högerpil \{0,1\}^{m}$

${\displaystyle IV_{2))$ — den andra initialiseringsvektorn [16] .

Tillämpat värde

Metoden som föreslagits av forskare vid HAIFA är av stor praktisk betydelse för implementeringen av elektroniska signaturalgoritmer : med introduktionen av antalet bitar och salt blev det svårare att lägga till prefix och suffix till meddelandet (flockangrepp), och därför ersätt meddelanden för signatur [8] .

Anteckningar

↑ Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan. SHA-3-förslag BLAKE // SHA-3-konferens. - 2010. - 16 december. - S. 8-15 . Arkiverad från originalet den 16 april 2016.
↑ Eli Biham, Orr Dunkelman. SHAvite-3 Hash-funktionen // Kryptera II. - 2009. - S. 8-17 . Arkiverad från originalet den 25 december 2016.
↑ Eli Biham. Publikationer . Listan över författares publikationer (sedan 1991). Hämtad 17 november 2016. Arkiverad från originalet 31 mars 2016. (obestämd)
↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Eli Biham, Orr Dunkelman. Ett ramverk för iterativa hashfunktioner—HAIFA // ePrint . - 2007. - S. 6-12 . Arkiverad från originalet den 17 augusti 2016.
↑ 1 2 Jean-Sebastien Coron, Yevgeniy Dodis, Cecile Malinaud, Prashant Puniya. Merkle Damgard Revisited: hur man konstruerar en hashfunktion (A new design Criteria for Hash-Functions ) // NIST. - S. 3-6 . Arkiverad från originalet den 7 november 2016.
↑ Gregory Bard. Fixed Point Attacken . Förklaringen till fixpunktsattack . ResearchGate (januari 2009). Hämtad 3 november 2016. Arkiverad från originalet 4 november 2016. (obestämd)
↑ Antoine Joux. Multikollisioner i itererade hashfunktioner. Tillämpning på kaskadkonstruktioner // Iacr . - 2004. - Augusti. Arkiverad från originalet den 13 maj 2016.
↑ 1 2 Orr Dunkelman, Bart Preneel. Generalisering av herdingattacken till sammanlänkade hashing-scheman // IAIK . - 2007. - S. 6-7 . Arkiverad från originalet den 4 november 2016.
↑ 1 2 Kelsey J. , Schneier B. Andra förbilder på n-bitars hashfunktioner för mycket mindre än 2ⁿ arbete // Framsteg inom kryptologi — EUROCRYPT 2005 : 24 :e årliga internationella konferensen om teorin och tillämpningarna av kryptografiska tekniker, Århus, Danmark, 22-26 maj 2005. Proceedings / R. Cramer - Springer Science + Business Media , 2005. - P. 474-490. — 578 sid. — ISBN 978-3-540-25910-7 — doi:10.1007/11426639_28
↑ Charles Bouillaguet, Pierre-Alain Fouque. Praktiska hashfunktioner Konstruktioner som är resistenta mot generiska andra preimage-attacker bortom födelsedagen // PSL . - 2011. - S. 2 . Arkiverad från originalet den 30 augusti 2017.
↑ Simon R. Blackburn. Om komplexiteten i vallningsattacken och några relaterade attacker på hashfunktioner // ePrint . - 2010. - S. 3 . Arkiverad från originalet den 26 augusti 2016.
↑ Elena Andreeva, Charles Bouillaguet, Orr Dunkelman och John Kelsey. Herding, Second Preimage och Trojan Message Attacks Beyond Merkle-Damgard // NIST . - S. 5, 10, 14 . Arkiverad från originalet den 21 november 2016.
↑ Halevi S. , Krawczyk H. Strengthening Digital Signatures Via Randomized Hashing // Advances in Cryptology - CRYPTO 2006 : 26th Annual International Cryptology Conference, Santa Barbara, Kalifornien, USA, 20-24 augusti 2006, Proceedings / C Dwork - Berlin Heidelberg , New York, NY , London [etc.] : Springer Science+Business Media , 2006. - S. 41-59. — 622 sid. - ( Lecture Notes in Computer Science ; Vol. 4117) - ISBN 978-3-540-37432-9 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/11818175_3
↑ Itai Dinur. Nya attacker mot sammanlänkning och XOR Hash Combiners // ePrint. - 2016. Arkiverad 9 september 2016.
↑ Elena Andreeva, Gregory Neven, Bart Preneel, Thomas Shrimpton. Seven-Properties-Preserving Iterated Hashing: The RMC Construction // ePrint . - 2007. - S. 10-14 . Arkiverad från originalet den 25 augusti 2016.
↑ 12 Dustin Moody. Likgiltighet Säkerhet för det snabba breda röret Hash: Breaking the Birthday Barrier // ePrint . - 2011. Arkiverad den 6 augusti 2016.

Litteratur

Eli Biham och Orr Dunkelman. Ett ramverk för iterativa hashfunktioner - HAIFA . - ePrint, 2007. - S. 3-12, 15. - 20 sid.
Orr Dunkelman. Återbesöker HAIFA. Samtal på workshopen Hashfunktioner i kryptologi: teori och praktik . - 2008. - 207 sid.
B. Denton och R. Adhami. Modern Hash-funktionskonstruktion . - 5 s.
John Kelsey, Tadayoshi Kohno. Herding Hash-funktioner och Nostradamus-attacken . - ePrint, 2005. - S. 4-8. — 17 s.
Marjan Skrobot. Bevisbar säkerhetsanalys av SHA-3-kandidater . - 2012. - S. 31-33. — 72 s.

Länkar

Mihir Bellare, Thomas Ristenpart. Multi-Property-Preserving Hash Domain Extension and the EMD Transform (Enveloped Merkle-Damgard) : [ eng. ] // ePrint : presentation. — University of California i San Diego Security and Cryptography Lab, 2006.
Webbplats för SHA-3-tävlingen (engelska) (2007-2012). — Beskrivning av de hashfunktioner som föreslagits vid tävlingen, resultaten av omgångarna.
Eli Biham. Eli Bihams sida (engelska) . — Grundläggande information, publikationsförteckning.