HAIFA

HAIFA ( engelsk HAsh Iterative Framework ) er en iterativ metode til at konstruere kryptografiske hashfunktioner , som er en forbedring af den klassiske Merkle-Damgor struktur .

Det blev foreslået i 2007 for at øge modstanden mod mange angreb og understøtte evnen til at opnå hash-summer af forskellig længde. Baseret på algoritmen er der udviklet hash-funktioner som BLAKE [1] og SHAVite-3 [2] .

Historie

Skaberne af algoritmen er Eli Biham og Or Dunkelman , israelske kryptografer fra University of Haifa . Biham er en elev af Adi Shamir , som udviklede et stort antal nye kryptografiske algoritmer, herunder at bryde eksisterende; Dunkelman er en kollega med Shamir på et af projekterne, og fortsatte senere sin forskning på egen hånd [3] .

Merkle-Damgor-strukturen blev længe anset for at være modstandsdygtig over for det andet preimage-angreb , indtil Princeton University -professor Richard Dean i 1999 beviste, at denne antagelse er forkert for lange beskeder, hvis det med en given kontraktionsfunktion nemt er muligt at finde den faste punkter i en sekvens. Også et multipelt kollisionsangreb og et harding-angreb (et angreb på et kendt præfiks) [4] [5] kunne med succes udføres på Merkle-Damgor-strukturen .

Algoritme

Merkle-Damgor strukturen er følgende algoritme:

Der er et budskab opdelt i flere dele: . Der er en eller anden startværdi - og en funktion , der beregner den mellemliggende repræsentation af hashfunktionen på en bestemt måde [5] : $M$ ${\displaystyle M_{1},M_{2}...M_{k))$ $IV$ $C$ $H$

h_{0}=IV

Yderligere iterativt :

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

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

Grundlaget for den nye HAIFA-algoritme var tilføjelsen af antallet af hash-bits og en tilfældig værdi. I stedet for den sædvanlige kompressionsfunktion, som nu kan betegnes som følger [4] :

\{0,1\}^{m_{c}}\times \{0,1\}^{n}\højrepil \{0,1\}^{m_{c}}

, hvor er størrelsen på , er størrelsen på blokken, (oftest er outputstørrelsen den samme som størrelsen på h)

m_{c}

h

n

{\displaystyle m=m_{c))

Brugt:

\{0,1\}^{m_{c}}\ gange \{0,1\}^{n}\ gange \{0,1\}^{b}\ gange \{0,1 \}^{s}\højrepil \{0,1\}^{m_{c}}

, hvor er længden af antallet af bits og salt ,

b,s

den interne repræsentation beregnes (i overensstemmelse med notationen introduceret ovenfor):

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

, hvor

bits

er antallet af bits hashed indtil videre.

Følg disse trin for at hash en besked:

Udfyld meddelelsen i overensstemmelse med diagrammet nedenfor. $M$
Beregn startværdien for den indre celle af størrelse m ifølge algoritmen beskrevet nedenfor. ${\displaystyle IV_{m))$
Gå gennem alle blokkene i den polstrede besked, udregn ved hvert trin værdien af komprimeringsfunktionen fra den aktuelle blok , og tilsæt nu saltet og som argumenter. Hvis der tilføjes en ekstra blok til beskeden (til allersidst), så sætter vi værdien til nul for denne blok. $Hej}$ $M_{i}$ $h_{{i-1}}$ $bits$ $bits$
Trim den sidste udgangsværdi for funktionen, hvis det er nødvendigt [4] .

Færdiggørelse af meddelelsen

I HAIFA er meddelelsen polstret med en et, det nødvendige antal nuller, længden af meddelelsen i bits og størrelsen af outputblokken . Det vil sige, vi tilføjer en sekvens (antallet af nuller i dette tilfælde skal være sådan, at [4] , hvor , er antallet af enere og nuller, er blokstørrelsen: $M$ $h$ $N_{1}+N_{0}\equiv N-(M_{længde}+H_{størrelse})modN$ $N_1$ $N_{0}$ $N$

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

Hashing af en meddelelse polstret med størrelsen af outputblokken eliminerer problemet med at finde kollisioner, da hvis to meddelelser og er hashed med blokstørrelser og , så er det den sidste blok, der gemmer fra kollisioner. Til gengæld, ved at tilføje = 0 i den allersidste blok, skabes et signal til at angive den sidste og komplementære blok [4] . $M_{1}$ $M_{2}$ $l_{1}$ $l_{2}$ $bits$

Muligheden for at supplere den originale besked i denne algoritme giver dig mulighed for at afkorte den hash-kodede, og derved ændre størrelsen af den endelige hash [4] .

Hash længde

Ofte kræves der i praksis forskellige længder af den endelige hash (som f.eks. gjort for SHA-256 , som har to trunkerede versioner), så denne struktur implementerede også muligheden for at variere dens længde ved hjælp af en speciel algoritme (for at opretholde modstand mod angreb på det andet preimage, kan du ikke bruge den åbenlyse løsning med at tage bits fra den endelige hash). $m$

$IV$ - startværdi
$m$ - ønsket udgangslængde
Vi betragter den konverterede startværdi: $IV_{m}=C(IV,m,0,0)$
Således bliver vi "wired" i de første bits, efterfulgt af 1 og nuller. $m$ $r$
Efter at den sidste blok er blevet beregnet, er den endelige værdi bit af den sidste værdi af kædekomprimeringsfunktionen [4] . $m$

Algoritmens sikkerhed

Beviset for, at HAIFA er kollisionsbestandigt, hvis kontraktionsfunktionen er kollisionsbestandigt, svarer til beviset for Merkle-Damgor [4] .

Antallet af hash-bits gør det meget sværere at finde og bruge fikspunkter. Selv efter at have fundet sådanne og , for hvilke , er det umuligt at multiplicere disse værdier på ubestemt tid i denne algoritme, fordi antallet af bits vil ændre sig hele tiden [4] . $Hej}$ $M_{i}$ $h_{i}=C(h_{i},M_{i},bits,salt)$

Salt ( ), såvel som , bidrager også til stabiliteten af algoritmen [4] : $salt$ $bits$

Giver dig mulighed for at indstille sikkerheden for hash-funktioner i en teoretisk model.
Får forudberegningsbaserede angreb til at flytte alle deres beregninger online, da værdien af saltet ikke er kendt på forhånd.
Øger sikkerheden ved elektroniske signaturer (fordi man hver gang skal tage højde for, at der er en eller anden tilfældig værdi).

Nedenfor er skøn over HAIFA's modstand mod forskellige typer angreb.

Fixed point angreb

I angrebet på det andet forbillede søges en sådan værdi ${\displaystyle M^{'))$ , for hvilket , dvs. hashen fra er lig med en eller anden mellemværdi i iterationer, og kombiner derefter den del af den resterende besked ( placeret til højre for ) med vores gættede . Algoritmen blev dog anerkendt som resistent over for dette angreb, da dens størrelse i den forbedrede version blev tilføjet til slutningen af meddelelsen. Richard Dean pegede i sit arbejde på en helt ny måde at angribe på, baseret på den antagelse, at det er let at finde faste punkter for en given funktion (per definition er et fikspunkt et, for hvilket forholdet er opfyldt ). I hans algoritme blev den manglende beskedlængde kompenseret ved at tilføje et sæt fikspunkter, det vil sige, at vi kunne fuldføre vores længde med et tilstrækkeligt antal gentagelser af værdien . $H(M')=h_{i}=H(M_{i})$ ${\displaystyle M^{'))$ $M$ $M_{i}$ ${\displaystyle M^{'))$ $C$ $h=C(h,M_{i})$ $h$

I dette tilfælde beskytter HAIFA mod et fastpunktsangreb, da tilstedeværelsen af et salt og et felt, der indeholder antallet af hash-bits, minimerer sandsynligheden for gentagelse af kontraktionsfunktionsværdier [4] .

Multiple kollisionsangreb

For flere kollisioner beskrev den franske kryptograf Antoine Joux muligheden for at finde beskeder, der har samme hash. Hans arbejde er baseret på det faktum, at det er muligt at finde sådanne én-blok kollisioner, hvori , og derefter konstruere forskellige beskeder, af alle muligheder, ved at vælge ved hvert af trinene enten besked eller . $2^{t}$ $t$ $C(h_{i-1},M_{i})=C(h_{i-1},M_{i}^{*})$ $2^{t}$ $t$ $M_{i}$ $M_{i}^{*}$

HAIFA, på trods af sin komplekse struktur, garanterer ikke nul succesrate for et angreb med flere kollisioner. Efter ovenstående modifikationer af Merkle-Damgor-algoritmen er kompleksiteten af at finde kollisioner for hver blok ikke ændret, men da en tilfældig blandet værdi er dukket op, kan angriberen ikke forhåndsvælge varianterne af disse kollisioner uden at kende den tilfældige værdi. Beregninger går online [4] .

Harding angreb

Et harding-angreb er baseret på, at angriberen forsøger at finde et sådant suffiks for et givet præfiks, der vil give den ønskede hashværdi.

Indledningsvis bygges et træ ud fra forskellige interne værdier, meddelelser Mj søges efter, der fører til kollisioner mellem disse tilstande. Det vil sige, at der er forskellige værdier i træets noder og værdier på kanterne . $2^{t}$ $h$ $M_{j}$
Vi bygger kollisioner på de nyligt opnåede værdier (fra det tidligere niveau af træet), indtil vi når den endelige værdi . $h$ $H$
Angriberen får derefter information om præfikset.
Efter at have modtaget denne information, forsøger den at finde en forbindelsesmeddelelse mellem dette præfiks og det ønskede suffiks. Den bindende meddelelse skal opfylde betingelsen om, at værdien af kontraktionsfunktionen fra den er lig med en af de interne værdier på træets første niveau. Ydermere er suffikset bygget af den sædvanlige passage gennem træet (da dets kanter allerede indeholder beskeder, der vil føre til det ønskede resultat). Nøglepunktet er evnen til at foretage foreløbige beregninger; i onlinetilstand er det fortsat kun at vælge den ønskede mellemværdi og . $h$ $h$ $M$

Det er bevist, at det er umuligt at udføre den første fase af et hardingsangreb (opbygning af et beslutningstræ) på HAIFA, før saltværdien er kendt. Det vil sige, at den brute-force , som blev beskrevet ovenfor, ikke længere kan udføres. Betingelsen for succesfuldt at afvise et angreb er længden af den blandede meddelelse, hvis den ønskede kompleksitet af angrebet er indstillet til niveauet , skal det være mindst tegn. Hvis denne regel ikke overholdes, er nogle foreløbige beregninger mulige, hvilket fører til hacking af algoritmen. Hvis saltværdien alligevel blev fundet, vil det tage noget tid at finde det rigtige sted i meddelelsen på grund af tilstedeværelsen af feltet [4] . $O(2^{m})$ ${\frac {m_{c}}{2}}$ $bits$

Kompleksiteten af angreb på Merkle-Damgor og HAIFA algoritmer

Angrebstype	Ideel hash-funktion	MD	HAIFA (fast værdi salt)	HAIFA (med forskellige saltværdier)
Angreb på den første prototype ( mål) ${\displaystyle k^{'}<2^{s))$	$2^{m_{c))$	$2^{m_{c))$	$2^{m_{c))$	$2^{m_{c))$
Angreb på en af de første prototyper	${\displaystyle 2^{m_{c}}}/k'$	${\displaystyle 2^{m_{c}}}/k'$	${\displaystyle 2^{m_{c}}}/k'$	$2^{m_{c))$
Angreb på den anden prototype ( blokke) [9] [10] $k$	$2^{m_{c))$	$2^{m_{c}}/k$	$2^{m_{c))$	$2^{m_{c))$
Angreb på en af de andre prototyper ( blokke, beskeder) $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}$
Flere kollisioner ( er antallet af 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}$
Hyrde [11] [12]	-	offline: $2^{m_{c}/2+t/2}$ Online: ${\displaystyle 2^{m_{c}-t))$	offline: $2^{m_{c}/2+t/2}$ Online: ${\displaystyle 2^{m_{c}-t))$	offline: $2^{m_{c}/2+t/2+s}$ Online: ${\displaystyle 2^{m_{c}-t))$

Ansøgninger

HAIFA kan ifølge udviklerne være grundlaget for mange kryptografiske algoritmer, da det er et nyt forbedret grunddesign. Det er blevet bevist, at det kan bruges til at udvikle randomiserede hashing-funktioner [13] , den indpakkede Merkle-Damgard-funktion ( eng. Enveloped Merkle-Damgard , RMC [14] [15] , wide-pipeline hash [16] .

Bredt pipelinet hash

At få en wild-pipe hash-konstruktion med HAIFA er ret nemt; i selve algoritmen, for at øge kompleksiteten, blev længden af de indre blokke gjort dobbelt så stor som længden af den sidste blok (derfor er der to kompressionsfunktioner og ). Det er muligt at udlede formlen for den pipelinede hash direkte, da det er trivielt at finde den sidste blok i HAIFA, da der er sat nuller [4] . $C^{'}$ $C^{''}$ $bits$

Formlen for konvertering fra HAIFA til en bred pipeline-hash er:

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

hvor $C':\{0,1\}^{m_{c}}\ gange \{0,1\}^{n}\højrepil \{0,1\}^{m_{c}}$

$C'':\{0,1\}^{m_{c}}\højrepil \{0,1\}^{m}$

$IV_{2}$ — den anden initialiseringsvektor [16] .

Anvendt værdi

Metoden foreslået af videnskabsmænd ved HAIFA er af stor praktisk betydning for implementeringen af elektroniske signaturalgoritmer : med introduktionen af antallet af bits og salt blev det sværere at tilføje præfikser og suffikser til beskeden (besætningsangreb), og derfor erstatte meddelelser til signatur [8] .

Noter

↑ Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan. SHA-3 forslag BLAKE // SHA-3 konference. - 2010. - 16. december. - S. 8-15 . Arkiveret fra originalen den 16. april 2016.
↑ Eli Biham, Orr Dunkelman. SHAvite-3 Hash-funktionen // Krypter II. - 2009. - S. 8-17 . Arkiveret fra originalen den 25. december 2016.
↑ Eli Biham. Publikationer . Listen over forfatternes publikationer (siden 1991). Hentet 17. november 2016. Arkiveret fra originalen 31. marts 2016. (ubestemt)
↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Eli Biham, Orr Dunkelman. A Framework for Iterative Hash Functions—HAIFA // ePrint . - 2007. - S. 6-12 . Arkiveret fra originalen den 17. august 2016.
↑ 1 2 Jean-Sebastien Coron, Yevgeniy Dodis, Cecile Malinaud, Prashant Puniya. Merkle Damgard Revisited: how to Construct a hash Function (A new design Criteria for Hash-Functions ) // NIST. - S. 3-6 . Arkiveret fra originalen den 7. november 2016.
↑ Gregory Bard. Fixed Point-angrebet . Forklaringen på fastpunktsangreb . ResearchGate (januar 2009). Hentet 3. november 2016. Arkiveret fra originalen 4. november 2016. (ubestemt)
↑ Antoine Joux. Multikollisioner i itererede hash-funktioner. Anvendelse til kaskadekonstruktioner // Iacr . - 2004. - August. Arkiveret fra originalen den 13. maj 2016.
↑ 1 2 Orr Dunkelman, Bart Preneel. Generalisering af hyrdeangrebet til sammenkædede hashing-skemaer // IAIK . - 2007. - S. 6-7 . Arkiveret fra originalen den 4. november 2016.
↑ 1 2 Kelsey J. , Schneier B. Second Preimages on n-Bit Hash Functions for Much Mindre than 2ⁿ Work // Advances in Cryptology — EUROCRYPT 2005 : 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, 22-26 maj 2005. Proceedings / R. Cramer - Springer Science + Business Media , 2005. - S. 474-490. — 578 s. — ISBN 978-3-540-25910-7 — doi:10.1007/11426639_28
↑ Charles Bouillaguet, Pierre-Alain Fouque. Praktiske hashfunktioner Konstruktioner, der er modstandsdygtige over for generiske Second Preimage-angreb ud over fødselsdagen // PSL . - 2011. - S. 2 . Arkiveret fra originalen den 30. august 2017.
↑ Simon R. Blackburn. Om kompleksiteten af hyrdeangrebet og nogle relaterede angreb på hash-funktioner // ePrint . - 2010. - S. 3 . Arkiveret fra originalen den 26. august 2016.
↑ Elena Andreeva, Charles Bouillaguet, Orr Dunkelman og John Kelsey. Herding, Second Preimage og Trojan Message Attacks Beyond Merkle-Damgard // NIST . - S. 5, 10, 14 . Arkiveret fra originalen 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, Californien, USA, 20.-24. august 2006, Proceedings / C Dwork - Berlin Heidelberg , New York, NY , London [etc.] : Springer Science+Business Media , 2006. - S. 41-59. — 622 s. - ( 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. Nye angreb på sammenkædning og XOR Hash Combiners // ePrint. - 2016. Arkiveret 9. september 2016.
↑ Elena Andreeva, Gregory Neven, Bart Preneel, Thomas Shrimpton. Syv-egenskaber-bevarer itereret hashing: RMC-konstruktionen // ePrint . - 2007. - S. 10-14 . Arkiveret fra originalen den 25. august 2016.
↑ 12 Dustin Moody. Ligegyldighed Sikkerhed for den hurtige brede rørhash: Bryd fødselsdagsbarrieren // ePrint . - 2011. Arkiveret 6. august 2016.

Litteratur

Eli Biham og Orr Dunkelman. En ramme for iterative hash-funktioner - HAIFA . - ePrint, 2007. - S. 3-12, 15. - 20 s.
Orr Dunkelman. Genbesøger HAIFA. Snak på workshoppen Hash-funktioner i kryptologi: teori og praksis . - 2008. - 207 s.
B. Denton og R. Adhami. Moderne Hash-funktionskonstruktion . - 5 sek.
John Kelsey, Tadayoshi Kohno. Hyrdehash-funktioner og Nostradamus-angrebet . - ePrint, 2005. - S. 4-8. — 17 sek.
Marjan Skrobot. Påviselig sikkerhedsanalyse af SHA-3-kandidater . - 2012. - S. 31-33. - 72 sek.