Merkle-Damgora rakenne

Merkle -Damgård -konstruktio ( eng. Merkle-Damgård construction , MD ) on menetelmä kryptografisten hajautusfunktioiden rakentamiseen , jossa mielivaltaisen pituiset syöttöviestit jaetaan kiinteän pituisiksi lohkoiksi ja työskennellään niiden kanssa vuorotellen käyttämällä pakkausfunktiota, joka kerta tulolohko, jossa on tulos edellisestä passista.

Kuvattiin ensimmäisen kerran vuonna 1979 Ralph Merklen väitöskirjassa [1] . Merkle ja Damgor osoittivat itsenäisesti, että jos pakkausfunktio kestää törmäyksiä , niin myös hash-funktio on vakaa [2] [3] – rakenteen vakauden todistamiseksi viestiä täydennetään lohkolla, joka koodaa alkuperäisen viestin pituus (Merkle-Damgor hardening ).

Rakenne tarjoaa alustusvektorin - kiinteän arvon, joka riippuu algoritmin toteutuksesta ja jota sovelletaan ensimmäiseen läpimenoon - soveltaen pakkausfunktiota siihen ja viestin ensimmäiseen lohkoon. Jokaisen passin tulos välitetään seuraavaan tuloon ja seuraavaan viestilohkoon; viimeinen lohko täytetään nolilla, tarvittaessa lisätään myös lohko, jossa on tiedot koko viestin pituudesta. Hashhin kovettamiseksi viimeinen tulos viedään joskus viimeistelytoiminnon läpi , jolla voidaan myös pienentää tulostettavan tiivisteen kokoa pakkaamalla viimeisen sovelluksen tulos pienemmäksi tiivisteeksi tai varmistaa parempi bittisekoitus ja -vahvistus. syöttöviestin pienen muutoksen vaikutus hajautusarvoon (antaa lumivyöryefektin ). Viimeistelytoiminto rakennetaan usein käyttämällä pakkaustoimintoa. $f$ $f$ $f$

Merkle-Damgor-rakenteen toteuttavat pääalgoritmit ovat MD5 , SHA-1 , SHA-2- perhe .

Turvaominaisuudet

Merkle-Damgor-rakenteen suosio johtuu seuraavasta tuloksesta: jos yksisuuntainen pakkausfunktio kestää törmäyksiä , niin sen pohjalta rakennettu hash- funktio on myös törmäyskestävä. Tässä tapauksessa rakenteella on useita ei-toivottuja ominaisuuksia: $f$

toinen esikuvahyökkäys pitkille viesteille on aina paljon tehokkaampi kuin raaka voima . Hyökkäys estoviestiin voidaan suorittaa ajoissa ; on tärkeää, että hyökkäyksen monimutkaisuus on välillä ja kun viestit ovat pitkiä, ja kun viestin pituus pienenee, monimutkaisuus lähestyy [4] ; $2^k$ $k\times 2^{n/2+1}+2^{n-k+1}$ $2^{{n/2}}$ $2^{n}$ $2^{n}$
useita törmäyksiä (monilla viesteillä on sama hash) voidaan löytää vain hieman suuremmalla vaivalla kuin törmäykset [5] ;
viestien täyttöhyökkäykset: Tuntemattoman syöttöviestin hajautusarvon perusteella on helppo löytää arvo , missä on täytetoiminto ; tämä tarkoittaa, että on mahdollista löytää tiivisteitä syötteistä, jotka liittyvät viestiin, vaikka se jää tuntemattomaksi [6] ; satunnaisessa oraakkelissa ei ole tätä ominaisuutta, ja tämä voi johtaa yksinkertaisiin hyökkäyksiin jopa satunnaisen oraakkelimallin turvallisiksi todistettuja järjestelmiä vastaan [7] . $H(X)$ $X$ $H(\mathrm {pad} (X)||Y)$ $\mathrm {pad}$ $X$ $X$

Esimerkki

Viestin välittämiseksi pakkaustoimintoon on tarpeen täyttää viimeinen lohko tietyillä tiedoilla (yleensä nollia). Jos esimerkiksi sanoma " HashInput " ja pakkausfunktion lohkokoko on 8 tavua (64 bittiä), tämä johtaisi 2 lohkoon:

HashInpu t0000000

Mutta tämä ei riitä, sillä se tarkoittaisi, että eri viestit, jotka alkavat samoilla merkeillä ja päättyvät noloihin tai muihin tavuihin täytetystä, tulevat pakkausfunktioon täsmälleen samoissa lohkoissa ja saadaan sama hash-summa. Tässä esimerkissä " HashInput00 " -viesti jaetaan samoihin lohkoihin kuin alkuperäinen " HashInput " -viesti. Tämän välttämiseksi lisätyn tiedon ensimmäinen bitti on muutettava. Koska täyte koostuu yleensä nollia, täytön ensimmäinen bitti on korvattava "1":llä:

HashInpu t1000000

Vahvistaaksesi tiivistettä voit lisätä viestin pituuden lisälohkoon:

HashInpu t1000000 00000009

Epäselvyyden välttämiseksi viestin pituuden arvon on itsessään kestettävä täyttöä lohkossa. Yleisimmät toteutukset käyttävät kiinteää kokoa (yleensä 64 tai 128 bittiä nykyaikaisissa algoritmeissa) ja kiinteää sijaintia viimeisen lohkon lopussa viestin pituusarvon koodaamiseen.

Yhden ylimääräisen lohkon koodaaminen viestin pituudelle on kuitenkin hieman turhaa, joten pieni algoritmioptimointi on usein käytössä: jos viimeisessä viestilohkossa on tarpeeksi tilaa, siihen voidaan lisätä viestin pituusarvo. Jos esimerkiksi koodaat viestin pituuden 5 tavuksi, niin kaksi lohkoa riittää, esimerkiksi:

HashInpu t1000009

Muutokset

Vuonna 2006 ehdotettiin HAIFA - lähestymistapaa , jossa Merkle-Damgor-rakennetta on hieman muokattu: sanomalohkon lisäksi jokaiseen pakkaustoimintoon syötetään syöttötiedoston nykyinen offset ja valinnaisesti suolaa .

Joidenkin rakenteen heikkouksien vuoksi, erityisesti ongelman, joka liittyy viestin täyttämiseen vaadittuun pituuteen, Stefan Lux ehdotti vuonna 2004 leveän liukuhihnan ( wilde pipe hash ) [8] käyttöä, joka on samanlainen kuin Merkle-Damgor. rakenne, mutta sillä on enemmän sisäisiä tiloja, eli algoritmin sisäisesti käyttämä bittipituus on suurempi kuin lähtö. Joten viimeinen vaihe on toinen pakkaustoiminto, joka pakkaa viimeisen sisäisen hajautusarvon lopulliseksi arvoksi. SHA-224 ja SHA-384 johdettiin SHA-256 :sta ja SHA-512 :sta , vastaavasti, käyttämällä tätä algoritmia.

Muistiinpanot

↑ R.C. Merkle. salassapito-, todennus- ja julkisen avaimen järjestelmät. Arkistoitu 14. elokuuta 2018 Wayback Machine Stanfordin Ph.D. opinnäytetyö 1979, sivut 13-15.
↑ Merkle R. A Certified Digital Signature // Advances in Cryptology - CRYPTO '89 : 9th Annual International Cryptology Conference, Santa Barbara, Kalifornia, USA, 20.-24. elokuuta 1989, Proceedings / G. Brassard - Berliini , Heidelberg , New York , NY , Lontoo [jne.] : Springer New York , 1990. - s. 218-238. - ( Lecture Notes in Computer Science ; Vol. 435) - ISBN 978-0-387-97317-3 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/0-387-34805-0_21
↑ Damgård I. Hash-funktioiden suunnitteluperiaate // Advances in Cryptology - CRYPTO '89 : 9th Annual International Cryptology Conference, Santa Barbara, Kalifornia, USA, 20.-24. elokuuta 1989, Proceedings / G. Brassard - Berliini , Heidelberg New York, NY , Lontoo [jne.] : Springer New York , 1990. — S. 416-427. - ( Lecture Notes in Computer Science ; Vol. 435) - ISBN 978-0-387-97317-3 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/0-387-34805-0_39
↑ Kelsey J. , Schneier B. Toiset esikuvat n-bittisistä hajautusfunktioista paljon alle 2ⁿ työlle // Advances in Cryptology - EUROCRYPT 2005 : 24. vuosittainen kansainvälinen kryptografisten tekniikoiden teoriaa ja sovelluksia koskeva konferenssi, Aarhus2, Tanska -26, 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
↑ Joux A. Multitörmäykset iteroiduissa hajautusfunktioissa. Sovellus Cascaded Constructions (englanniksi) // Advances in Cryptology - CRYPTO 2004 : 24th Annual International Cryptology Conference, Santa Barbara, Kalifornia, USA, 15.-19. elokuuta 2004, Proceedings / M. Franklin - Berlin , Heidelberg , New York, NY , Lontoo [jne.] : Springer Science + Business Media , 2004. - s. 306-316. — 579 s. - ( Lecture Notes in Computer Science ; Voi. 3152) - ISBN 978-3-540-22668-0 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-540-28628-8_19
↑ Jevgeni Dodis , Thomas Ristenpart, Thomas Shrimpton. Merkle-Damgårdin pelastaminen käytännön sovelluksiin . Alustava versio julkaisussa Advances in Cryptology - EUROCRYPT '09 Proceedings, Lecture Notes in Computer Science Vol. 5479, A. Joux, toim., Springer-Verlag, 2009, s. 371-388.
↑ Coron J. , Dodis Y. , Malinaud C. , Puniya P. Merkle-Damgård Revisited: How to Construct a Hash Function // Advances in Cryptology - CRYPTO 2005 : 25th Annual International Cryptology Conference, Santa Barbara, Kalifornia, USA, elokuu 14-18, 2005, Proceedings / V. Shoup - Berlin , Heidelberg , New York, NY , Lontoo [jne.] : Springer Science + Business Media , 2005. - P. 430-448. — 572 s. - ( Lecture Notes in Computer Science ; Voi. 3621) - ISBN 978-3-540-28114-6 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/11535218_26
↑ S. Lucks, Design Principles for Iterated Hash Functions , julkaisussa: Cryptology ePrint Archive, Report 2004/253, 2004.

Linkit

Menezesin, van Oorschotin ja Vanstonen soveltavan kryptografian käsikirja (2001), luku 9.
Johdatus moderniin kryptografiaan , kirjoittaneet Jonathan Katz ja Yehuda Lindell. Chapman ja Hall/CRC Press, elokuu 2007, sivu 134 (rakennus 4.13).