HAIFA

HAIFA ( englanniksi HAsh Iterative FrAmework ) on iteratiivinen menetelmä kryptografisten hajautusfunktioiden rakentamiseen , mikä on parannus klassiseen Merkle-Damgor-rakenteeseen .

Sitä ehdotettiin vuonna 2007 lisäämään vastustuskykyä monille hyökkäyksille ja tukemaan kykyä saada eripituisia hash-summia . Algoritmin pohjalta on kehitetty hash-funktioita, kuten BLAKE [1] ja SHAVite-3 [2] .

Historia

Algoritmin luojat ovat Eli Biham ja Or Dunkelman , israelilaiset kryptografit Haifan yliopistosta . Biham on Adi Shamirin opiskelija , joka kehitti suuren määrän uusia salausalgoritmeja, mukaan lukien olemassa olevien salausalgoritmien rikkominen; Dunkelman on Shamirin kollega yhdessä projektista, ja myöhemmin hän jatkoi tutkimustaan itsenäisesti [3] .

Merkle-Damgor-rakenteen uskottiin pitkään kestävän toista esikuvahyökkäystä , kunnes Princetonin yliopiston professori Richard Dean osoitti vuonna 1999 , että tämä oletus on väärä pitkille viesteille, jos tietyllä supistusfunktiolla on mahdollista löytää helposti kiinteä. sekvenssin pisteitä. Merkle-Damgor-rakenteeseen voitiin myös suorittaa usean törmäyksen hyökkäys ja harding-hyökkäys (hyökkäys tunnettuun etuliitteeseen) [4] [5] .

Algoritmi

Merkle-Damgor-rakenne on seuraava algoritmi:

Viesti on jaettu useisiin osiin: . On jokin alkuarvo - ja jokin funktio , joka laskee hajautusfunktion väliesityksen tietyllä tavalla [5] : $M$ ${\displaystyle M_{1},M_{2}...M_{k))$ $IV$ $C$ $H$

h_{0}=IV

Edelleen iteratiivisesti :

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

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

Uuden HAIFA-algoritmin perustana oli hajabittien lukumäärän ja jonkin verran satunnaisarvon lisääminen . Tavallisen pakkaustoiminnon sijaan, joka voidaan nyt merkitä seuraavasti [4] :

\{0,1\}^{m_{c}}\times \{0,1\}^{n}\rightarrow \{0,1\}^{m_{c}}

, missä on koko , on lohkon koko, (useimmiten tulosteen koko on sama kuin h:n koko)

m_{c}

h

n

{\displaystyle m=m_{c))

käytetty:

\{0,1\}^{m_{c}}\times \{0,1\}^{n}\times \{0,1\}^{b}\times \{0,1 \}^{s}\rightarrow \{0,1\}^{m_{c}}

, missä ovat bittien lukumäärän ja suolan pituudet ,

b,s

sisäinen esitys lasketaan (edellä esitetyn merkinnän mukaisesti):

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

, missä

bits

on tähän mennessä hajautettujen bittien määrä.

Jos haluat tiivistää viestin, toimi seuraavasti:

Täytä viesti alla olevan kaavion mukaisesti. $M$
Laske m -koon sisäsolun alkuarvo alla kuvatun algoritmin mukaisesti. ${\displaystyle IV_{m))$
Käy läpi kaikki täytetyn viestin lohkot laskemalla jokaisessa vaiheessa pakkausfunktion arvo nykyisestä lohkosta ja lisäämällä nyt suola ja argumentteina. Jos viestiin lisätään ylimääräinen lohko (hyvin lopussa), asetamme tälle lohkolle arvon nollaksi. $Hei}$ $Mi}$ $h_{{i-1}}$ $bits$ $bits$
Trimmaa funktion viimeistä lähtöarvoa tarvittaessa [4] .

Viestin valmistuminen

HAIFA:ssa viesti on täytetty ykkösellä, vaaditulla määrällä nollia, viestin pituudella bitteinä ja lähtölohkon koolla . Eli lisäämme sekvenssin (nollien lukumäärän tässä tapauksessa tulee olla sellainen, että [4] , jossa , on ykkösten ja nollien lukumäärä, on lohkon koko: $M$ $h$ $N_{1}+N_{0}\equiv N-(M_{length}+H_{size})modN$ $N_1$ $N_{0}$ $N$

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

Tuloslohkon koolla täytetyn viestin tiivistäminen eliminoi törmäysten löytämisen ongelman, koska jos kaksi viestiä ja tiivistetään lohkokoolla ja , niin se on viimeinen lohko, joka säästää törmäyksistä. Lisäämällä = 0 aivan viimeiseen lohkoon puolestaan luodaan signaali osoittamaan viimeinen ja täydentävä lohko [4] . $M_{1}$ $M_{2}$ $l_{1}$ $l_{2}$ $bits$

Mahdollisuus täydentää alkuperäistä viestiä tässä algoritmissa mahdollistaa tiivistetyn viestin lyhentämisen, mikä muuttaa lopullisen tiivisteen kokoa [4] .

Hash-pituus

Usein käytännössä vaaditaan eripituisia lopullisen tiivisteen pituutta (kuten esimerkiksi SHA-256 :lle , jossa on kaksi katkaistua versiota), joten tämä rakenne toteutti myös mahdollisuuden vaihdella sen pituutta erityisellä algoritmilla (jotta säilyttää vastustuskyky hyökkäyksille toista esikuvaa vastaan, et voi käyttää ilmeistä ratkaisua ottaa bittejä lopullisesta hashista). $m$

$IV$ -alkuarvo
$m$ - haluttu ulostulon pituus
Otamme huomioon muunnetun alkuarvon: $IV_{m}=C(IV,m,0,0)$
Näin ollen "johdotetaan" ensimmäisissä biteissa, joita seuraa 1 ja nollia. $m$ $r$
Kun viimeinen lohko on laskettu, lopullinen arvo on ketjunpakkausfunktion viimeisen arvon bitti [4] . $m$

Algoritmin suojaus

Todiste siitä, että HAIFA on törmäyksenkestävä, jos supistumisfunktio on törmäyksenkestävä, on samanlainen kuin Merkle-Damgorin todiste [4] .

Hajabittien määrä tekee kiinteiden pisteiden löytämisestä ja käyttämisestä paljon vaikeampaa. Vaikka olisi löydetty sellaiset ja joille , näitä arvoja on mahdotonta kertoa loputtomasti tässä algoritmissa, koska bittien määrä muuttuu koko ajan [4] . $Hei}$ $Mi}$ $h_{i}=C(h_{i},M_{i},bittiä,suola)$

Suola ( ), samoin kuin , edistävät myös algoritmin vakautta [4] : $salt$ $bits$

Mahdollistaa hajautusfunktioiden turvallisuuden asettamisen teoreettisessa mallissa.
Aiheuttaa ennakkolaskentaan perustuvat hyökkäykset siirtämään kaikki laskelmat verkkoon, koska suolan arvoa ei tiedetä etukäteen.
Lisää sähköisten allekirjoitusten turvallisuutta (koska joka kerta on otettava huomioon, että siinä on jokin satunnainen arvo).

Alla on arvioita HAIFA:n vastustuskyvystä erityyppisiä hyökkäyksiä vastaan.

Kiinteän pisteen hyökkäykset

Hyökkäyksessä toista esikuvaa vastaan haetaan tällaista arvoa $M^{'}$ , jolle , eli tiiviste kohteesta on yhtä suuri kuin jokin väliarvo iteraatioissa, ja yhdistä sitten jäljellä olevan viestin osa ( joka sijaitsee oikealla ) arvaamaamme . Algoritmi tunnistettiin kuitenkin vastustuskykyiseksi tälle hyökkäykselle, koska parannetussa versiossa sen koko liitettiin viestin loppuun. Richard Dean osoitti työssään täysin uudenlaisen hyökkäystavan, joka perustuu oletukseen, että tietylle funktiolle on helppo löytää kiinteitä pisteitä (määritelmän mukaan kiinteä piste on sellainen, jonka relaatio täyttyy ). Hänen algoritmissaan puuttuva viestin pituus korvattiin lisäämällä joukko kiinteitä pisteitä, eli pituuttamme voitiin täydentää riittävällä määrällä arvon toistoja . $H(M')=h_{i}=H(M_{i})$ $M^{'}$ $M$ $Mi}$ $M^{'}$ $C$ $h=C(h,M_{i})$ $h$

Tässä tapauksessa HAIFA suojaa kiinteän pisteen hyökkäyksiltä, koska suolan ja hajabittien lukumäärän sisältävä kenttä minimoi supistusfunktioarvojen toistumisen todennäköisyyden [4] .

Usean törmäyksen hyökkäys

Useita törmäyksiä varten ranskalainen kryptografi Antoine Joux kuvaili mahdollisuutta löytää viestejä, joilla on sama hash. Hänen työnsä perustuu siihen, että on mahdollista löytää sellaisia yhden lohkon törmäyksiä, joissa , ja sitten rakentaa erilaisia viestejä, kaikista vaihtoehdoista, valitsemalla jokaisessa vaiheessa joko viesti tai . $2^{t}$ $t$ $C(h_{i-1},M_{i})=C(h_{i-1},M_{i}^{*})$ $2^{t}$ $t$ $Mi}$ $M_{i}^{*}$

HAIFA ei monimutkaisesta rakenteestaan huolimatta takaa nolla onnistumisprosenttia useiden törmäyshyökkäysten yhteydessä. Yllä olevien Merkle-Damgor-algoritmiin tehtyjen muutosten jälkeen törmäysten löytämisen monimutkaisuus ei ole muuttunut jokaiselle lohkolle, mutta koska satunnainen sekoitettu arvo on ilmaantunut, hyökkääjä ei voi esivalita näiden törmäysten variantteja tietämättä satunnaisarvoa. Laskelmat menevät verkkoon [4] .

Harding attack

Kovettava hyökkäys perustuu siihen, että hyökkääjä yrittää löytää annetulle etuliitteelle sellaisen loppuliitteen, joka antaa halutun hajautusarvon.

Aluksi puu rakennetaan erilaisista sisäisistä arvoista, etsitään sanomia Mj, jotka johtavat törmäyksiin näiden tilojen välillä. Eli puun solmuissa on erilaisia arvoja ja reunoissa arvoja . $2^{t}$ $h$ $M_{j}$
Rakennamme törmäyksiä uusiin saatuihin arvoihin (puun edelliseltä tasolta), kunnes saavutamme lopullisen arvon . $h$ $H$
Hyökkääjä saa sitten tietoa etuliitteestä.
Saatuaan nämä tiedot se yrittää löytää linkitysviestin tämän etuliiteen ja halutun päätteen välillä. Sidossanoman on täytettävä ehto, että siitä tuleva supistumisfunktion arvo on yhtä suuri kuin jokin puun ensimmäisen tason sisäisistä arvoista. Lisäksi jälkiliite rakennetaan tavallisella kulkulla puun läpi (koska sen reunat sisältävät jo viestejä, jotka johtavat haluttuun tulokseen). Avainkohta on kyky tehdä alustavia laskelmia; online-tilassa jää vain valita haluttu väliarvo ja . $h$ $h$ $M$

On todistettu, että on mahdotonta suorittaa kovaa hyökkäyksen ensimmäistä vaihetta (päätöspuun rakentaminen) HAIFAa vastaan ennen kuin suolan arvo on tiedossa. Toisin sanoen edellä kuvattua raakaa voimaa ei voida enää suorittaa. Hyökkäyksen torjumisen ehto on sekaviestin pituus, jos haluttu hyökkäyksen monimutkaisuus asetetaan tasolle , sen on oltava vähintään merkkiä. Jos tätä sääntöä ei noudateta, jotkut alustavat laskelmat ovat mahdollisia, mikä johtaa algoritmin hakkerointiin. Jos suola-arvo kuitenkin löydettiin, kestää jonkin aikaa löytää oikea paikka viestissä [4] -kentän vuoksi . $O(2^{m})$ ${\frac {m_{c}}{2}}$ $bits$

Merkle-Damgor- ja HAIFA-algoritmeihin kohdistuvien hyökkäysten monimutkaisuus

Hyökkäystyyppi	Ihanteellinen hash-toiminto	MD	HAIFA (kiinteä arvo suola)	HAIFA (eri suolaarvoilla)
Hyökkäys ensimmäistä prototyyppiä vastaan ( maalit ) ${\displaystyle k^{'}<2^{s))$	$2^{m_{c))$	$2^{m_{c))$	$2^{m_{c))$	$2^{m_{c))$
Hyökkäys yhtä ensimmäisistä prototyypeistä	${\displaystyle 2^{m_{c}}}/k'$	${\displaystyle 2^{m_{c}}}/k'$	${\displaystyle 2^{m_{c}}}/k'$	$2^{m_{c))$
Hyökkäys toista prototyyppiä vastaan ( lohkot) [9] [10] $k$	$2^{m_{c))$	$2^{m_{c}}/k$	$2^{m_{c))$	$2^{m_{c))$
Hyökkäys toista prototyyppiä vastaan ( lohkot, viestit) $k$ ${\displaystyle k^{'}<2^{s))$	${\displaystyle 2^{m_{c}}}/k'$	$2^{m_{c}}/k$	${\displaystyle 2^{m_{c}}}/k'$	$2^{m_{c))$
Törmäykset	$2^{m_{c}/2}$	$2^{m_{c}/2}$	$2^{m_{c}/2}$	$2^{m_{c}/2}$
Useita törmäyksiä ( on törmäysten lukumäärä) [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}$
Paimennus [11] [12]	-	offline-tilassa: $2^{m_{c}/2+t/2}$ Online: ${\displaystyle 2^{m_{c}-t))$	offline-tilassa: $2^{m_{c}/2+t/2}$ Online: ${\displaystyle 2^{m_{c}-t))$	offline-tilassa: $2^{m_{c}/2+t/2+s}$ Online: ${\displaystyle 2^{m_{c}-t))$

Sovellukset

HAIFA voi kehittäjien mukaan olla perusta monille salausalgoritmeille, koska se on uusi parannettu perusrakenne. On todistettu, että sillä voidaan kehittää satunnaistettuja hajautusfunktioita [13] , wrapped Merkle-Damgard -funktiota ( eng. Enveloped Merkle-Damgard , RMC [14] [15] , laajapipeline hash [16] .

Laajalti liukuhihnatiivistettä

Wild-pipe hash -konstruktin hankkiminen HAIFA :lla on melko helppoa; itse algoritmissa monimutkaisuuden lisäämiseksi sisälohkojen pituus tehtiin kaksi kertaa niin suureksi kuin lopullisen lohkon pituus (siis on kaksi pakkausfunktiota ja ). Liukuhihnavedon tiivisteen kaava on mahdollista johtaa suoraan, koska on triviaalia löytää viimeinen lohko HAIFAsta, koska siellä asetetaan nollia [4] . $C^{'}$ $C^{''}$ $bits$

Kaava muuntamiseen HAIFA:sta laajaksi liukuhihnaksi on:

$C_{HAIFA}(h_{i-1},M_{i},bits,s)={\begin{cases}C''(C'(IV_{2},h_{i-1}| |korjauslevy(M_{i}))),&{\teksti{jos }}{\teksti{ viimeinen lohko}}\\C'(h_{i-1},M_{i}),&{\teksti{ }}{\teksti{muutoin}}\end{cases}}$

missä $C':\{0,1\}^{m_{c}}\times \{0,1\}^{n}\rightarrow \{0,1\}^{m_{c}}$

$C'':\{0,1\}^{m_{c}}\rightarrow \{0,1\}^{m}$

$IV_{2}$ — toinen alustusvektori [16] .

Käytetty arvo

HAIFA:n tutkijoiden ehdottamalla menetelmällä on suuri käytännön merkitys sähköisten allekirjoitusalgoritmien toteuttamisessa : bittien ja suolan määrän käyttöönoton myötä etuliitteiden ja päätteiden lisääminen viestiin vaikeutui (laumahyökkäys), ja siksi korvaa allekirjoituksen viestit [8] .

Muistiinpanot

↑ Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan. SHA-3-ehdotus BLAKE // SHA-3-konferenssi. - 2010 - 16. joulukuuta. - S. 8-15 . Arkistoitu alkuperäisestä 16. huhtikuuta 2016.
↑ Eli Biham, Orr Dunkelman. SHAvite-3 Hash Function // Encrypt II. - 2009. - S. 8-17 . Arkistoitu alkuperäisestä 25. joulukuuta 2016.
↑ Eli Biham. Julkaisut . Luettelo kirjailijoiden julkaisuista (vuodesta 1991). Haettu 17. marraskuuta 2016. Arkistoitu alkuperäisestä 31. maaliskuuta 2016. (määrätön)
↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Eli Biham, Orr Dunkelman. Iteratiivisten hajautusfunktioiden kehys — HAIFA // ePrint . - 2007. - S. 6-12 . Arkistoitu alkuperäisestä 17. elokuuta 2016.
↑ 1 2 Jean-Sebastien Coron, Jevgeni Dodis, Cecile Malinaud, Prashant Puniya. Merkle Damgard Revisited: How to Construct a hash Function (Uusi suunnittelukriteerit hash-funktioille ) // NIST. - s. 3-6 . Arkistoitu alkuperäisestä 7. marraskuuta 2016.
↑ Gregory Bard. Kiinteän pisteen hyökkäys . Kiinteän pisteen hyökkäyksen selitys . ResearchGate (tammikuu 2009). Haettu 3. marraskuuta 2016. Arkistoitu alkuperäisestä 4. marraskuuta 2016. (määrätön)
↑ Antoine Joux. Multitörmäykset iteroiduissa hash-funktioissa. Sovellus kaskadirakenteisiin // Iacr . - 2004 - elokuu. Arkistoitu alkuperäisestä 13. toukokuuta 2016.
↑ 1 2 Orr Dunkelman, Bart Preneel. Paimennushyökkäyksen yleistäminen ketjutettuihin hajautusskeemoihin // IAIK . - 2007. - S. 6-7 . Arkistoitu alkuperäisestä 4. marraskuuta 2016.
↑ 1 2 Kelsey J. , Schneier B. Toiset esikuvat n-bittisistä hajautusfunktioista paljon alle 2ⁿ työlle // Advances in Cryptology – EUROCRYPT 2005 : 24. vuosittainen kansainvälinen salaustekniikoiden teoriaa ja sovelluksia koskeva konferenssi, Tanska, Aarhu 22.-26.5.2005. Proceedings / R. Cramer - Springer Science + Business Media , 2005. - P. 474-490. — 578 s. — ISBN 978-3-540-25910-7 — doi:10.1007/11426639_28
↑ Charles Bouillaguet, Pierre-Alain Fouque. Käytännön hajautusfunktiot Rakenteet, jotka kestävät yleisiä toisen esikuvan hyökkäyksiä syntymäpäivärajan ulkopuolella // PSL . - 2011. - S. 2 . Arkistoitu alkuperäisestä 30. elokuuta 2017.
↑ Simon R. Blackburn. Paimennushyökkäyksen monimutkaisuudesta ja eräistä siihen liittyvistä hash-toimintoihin kohdistuvista hyökkäyksistä // ePrint . - 2010. - S. 3 . Arkistoitu alkuperäisestä 26. elokuuta 2016.
↑ Elena Andreeva, Charles Bouillaguet, Orr Dunkelman ja John Kelsey. Herding, Second Preimage ja Trojan Message Attacks Beyond Merkle-Damgard // NIST . - S. 5, 10, 14 . Arkistoitu alkuperäisestä 21. marraskuuta 2016.
↑ Halevi S. , Krawczyk H. Digitaalisten allekirjoitusten vahvistaminen satunnaistetun hajautustekniikan avulla // Advances in Cryptology - CRYPTO 2006 : 26th Annual International Cryptology Conference, Santa Barbara, Kalifornia, USA, 20.-24. elokuuta 2006, D Working - Berlins / , C. Heidelberg , New York, NY , Lontoo [jne.] : 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. Uusia hyökkäyksiä ketjutus- ja XOR-hajayhdistysohjelmiin // ePrint. - 2016. Arkistoitu 9. syyskuuta 2016.
↑ Elena Andreeva, Gregory Neven, Bart Preneel, Thomas Shrimpton. Seitsemän ominaisuutta säilyttävä iteroitu hajautus: RMC-rakenne // ePrint . - 2007. - S. 10-14 . Arkistoitu alkuperäisestä 25. elokuuta 2016.
↑ 12 Dustin Moody. Fast Wide Pipe Hash välinpitämättömyyden suoja: Syntymäpäivän esteen rikkominen // ePrint . - 2011. Arkistoitu 6. elokuuta 2016.

Kirjallisuus

Eli Biham ja Orr Dunkelman. Viitekehys iteratiivisille hash-funktioille - HAIFA . - ePrint, 2007. - s. 3-12, 15. - 20 s.
Orr Dunkelman. Uudelleenvierailu HAIFAssa. Keskustelu työpajassa Hash-funktiot kryptologiassa: teoria ja käytäntö . - 2008. - 207 s.
B. Denton ja R. Adhami. Moderni hash-funktiorakenne . - 5 s.
John Kelsey, Tadayoshi Kohno. Hash-funktioiden paimentaminen ja Nostradamus-hyökkäys . - ePrint, 2005. - s. 4-8. -17 s.
Marjan Skrobot. SHA-3-ehdokkaiden todistettavissa oleva turvallisuusanalyysi . - 2012. - S. 31-33. – 72 s.

Linkit

Mihir Bellare, Thomas Ristenpart. Multi-Property-Preserving Hash Domain Extension and the EMD Transform (Envelopeed Merkle-Damgard) : [ eng. ] // ePrint : esitys. - Kalifornian yliopisto San Diego Security and Cryptography Lab, 2006.
SHA-3-kilpailun verkkosivusto (englanniksi) (2007-2012). — Kuvaus kilpailussa ehdotetuista hash-toiminnoista, kierrosten tulokset.
Eli Biham. Eli Bihamin sivu (englanniksi) . — Perustiedot, julkaisuluettelo.