Merkle-Damgora struktur

Merkle -Damgård konstruktion ( eng. Merkle-Damgård konstruktion , MD ) er en metode til at konstruere kryptografiske hashfunktioner, der involverer opdeling af inputmeddelelser af vilkårlig længde i blokke af fast længde og arbejde med dem på skift ved hjælp af komprimeringsfunktionen, hver gang der tages en inputblok med et output fra det forrige gennemløb.

Først beskrevet i 1979 i doktorafhandlingen af Ralph Merkle [1] . Merkle og Damgor uafhængigt viste, at hvis kompressionsfunktionen er modstandsdygtig over for kollisioner , så vil hash-funktionen også være stabil [2] [3] — for at bevise strukturens stabilitet, er meddelelsen suppleret med en blok, der koder længden af den originale besked (Merkle-Damgor-hærdning ).

Strukturen giver en initialiseringsvektor - en fast værdi, der afhænger af implementeringen af algoritmen, og som anvendes på det første gennemløb - ved at anvende komprimeringsfunktionen til den og den første blok af meddelelsen. Resultatet af hver passage sendes til den næste input og den næste beskedblok; den sidste blok er polstret med nuller, om nødvendigt tilføjes en blok med information om længden af hele beskeden. For at hærde hashen sendes det sidste resultat nogle gange gennem en færdiggørelsesfunktion , som også kan bruges til at reducere størrelsen af output-hashen ved at komprimere resultatet af den sidste applikation til en mindre hash eller for at sikre bedre bitblanding og forstærkning effekten af en lille ændring i inputmeddelelsen på hashen (giv en lavineeffekt ). Afslutningsfunktionen er ofte bygget ved hjælp af kompressionsfunktionen. $f$ $f$ $f$

De vigtigste algoritmer, der implementerer Merkle-Damgor-strukturen, er MD5 , SHA-1 , SHA-2- familien .

Sikkerhedsfunktioner

Populariteten af Merkle- Damgor -strukturen skyldes følgende resultat: Hvis en envejskompressionsfunktion er modstandsdygtig over for kollisioner , så vil hashfunktionen bygget på dens basis også være modstandsdygtig over for kollisioner. I dette tilfælde har strukturen flere uønskede egenskaber: $f$

det andet preimage-angreb for lange beskeder er altid meget mere effektivt end brute force . Et angreb på en blokeringsmeddelelse kan fuldføres i tide ; det er vigtigt, at kompleksiteten af angrebet er mellem og når beskederne er lange, og når beskedlængden bliver mindre, nærmer kompleksiteten sig [4] ; $2^k$ $k\times 2^{n/2+1}+2^{n-k+1}$ $2^{{n/2}}$ $2^{n}$ $2^{n}$
flere kollisioner (mange beskeder har samme hash) kan kun findes med marginalt mere indsats end kollisioner [5] ;
besked udfyldning angreb: givet en hash af en ukendt input besked , er det let at finde værdien , hvor er udfyldningsfunktionen ; dette betyder, at det er muligt at finde hashes af inputmeddelelser forbundet med , selv når det forbliver ukendt [6] ; det tilfældige orakel har ikke denne evne, og dette kan føre til simple angreb selv mod skemaer, der har vist sig at være sikre for den tilfældige orakelmodel [7] . $H(X)$ $x$ $H(\mathrm {pad} (X)||Y)$ $\mathrm {pad}$ $x$ $x$

Eksempel

For at sende en besked til komprimeringsfunktionen er det nødvendigt at fylde den sidste blok med visse data (normalt nuller). For eksempel, for en besked " HashInput " og en blokstørrelse for komprimeringsfunktionen på 8 bytes (64 bits), ville dette resultere i 2 blokke:

HashInpu t0000000

Men det er ikke nok, da det ville betyde, at forskellige beskeder, der starter med de samme tegn og slutter med nuller eller andre bytes fra udfyldningen, vil gå ind i komprimeringsfunktionen i nøjagtig de samme blokke, og den samme hash-sum vil blive opnået. I dette eksempel vil " HashInput00 "-meddelelsen blive opdelt i de samme blokke som den originale " HashInput "-meddelelse. For at undgå dette skal den første bit af de tilføjede data ændres. Da polstringen normalt består af nuller, skal den første bit af polstringen erstattes med et "1":

HashInpu t1000000

For at styrke hashen kan du tilføje længden af beskeden i en ekstra blok:

HashInpu t1000000 00000009

For at undgå tvetydighed skal værdien af meddelelseslængden i sig selv være modstandsdygtig over for udfyldning i blokken. De mest almindelige implementeringer bruger en fast størrelse (normalt 64 eller 128 bit i moderne algoritmer) og en fast position i slutningen af den sidste blok til at kode meddelelseslængdeværdien.

Det er dog lidt sløset at indkode én ekstra blok til beskedlængden, så der er en lille algoritmeoptimering, som ofte bruges: Hvis der er plads nok i den sidste beskedblok, kan beskedlængdeværdien tilføjes. Hvis du for eksempel koder meddelelseslængden i 5 bytes, er to blokke nok, for eksempel:

HashInpu t1000009

Ændringer

I 2006 blev HAIFA - tilgangen foreslået , hvor Merkle-Damgor-strukturen er lidt ændret: Ud over meddelelsesblokken forsynes hver komprimeringsfunktion med den aktuelle offset i inputfilen og eventuelt noget salt .

På grund af nogle svagheder i strukturen, især problemet forbundet med at udfylde meddelelsen til den nødvendige længde, foreslog Stefan Lux i 2004 at bruge en bred rørlednings-hash ( pipe -hash ) [8] , svarende til Merkle-Damgor struktur, men med flere interne tilstande, det vil sige, at bitlængden, der bruges internt af algoritmen, er større end outputtet. Så det sidste trin er den anden komprimeringsfunktion, som komprimerer den sidste interne hashværdi til den endelige værdi. SHA-224 og SHA-384 blev afledt af henholdsvis SHA-256 og SHA-512 ved at anvende denne algoritme.

Noter

↑ R.C. Merkle. hemmeligholdelse, autentificering og offentlige nøglesystemer. Arkiveret 14. august 2018 på Wayback Machine Stanford Ph.D. afhandling 1979, side 13-15.
↑ Merkle R. A Certified Digital Signature // Advances in Cryptology - CRYPTO '89 : 9th Annual International Cryptology Conference, Santa Barbara, Californien, USA, 20.-24. august 1989, Proceedings / G. Brassard - Berlin , Heidelberg , New York , NY , London [etc.] : 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. A Design Principle for Hash Functions // Advances in Cryptology - CRYPTO '89 : 9th Annual International Cryptology Conference, Santa Barbara, Californien, USA, 20.-24. august 1989, Proceedings / G. Brassard - Berlin , Heidelberg , New York, NY , London [etc.] : 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. 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, Danmark, 22. maj -26, 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
↑ Joux A. Multikollisioner i itererede hashfunktioner. Ansøgning til Cascaded Constructions (engelsk) // Advances in Cryptology - CRYPTO 2004 : 24th Annual International Cryptology Conference, Santa Barbara, Californien, USA, 15.-19. august 2004, Proceedings / M. Franklin - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Science + Business Media , 2004. - S. 306-316. — 579 s. - ( Lecture Notes in Computer Science ; Vol. 3152) - ISBN 978-3-540-22668-0 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-540-28628-8_19
↑ Yevgeniy Dodis , Thomas Ristenpart, Thomas Shrimpton. Bjærgning af Merkle-Damgård til praktiske anvendelser . Foreløbig version i Advances in Cryptology - EUROCRYPT '09 Proceedings, Lecture Notes in Computer Science Vol. 5479, A. Joux, red., Springer-Verlag, 2009, pp. 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, Californien, USA, august 14-18, 2005, Proceedings / V. Shoup - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Science + Business Media , 2005. - S. 430-448. — 572 s. - ( Lecture Notes in Computer Science ; Vol. 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 , I: Cryptology ePrint Archive, Rapport 2004/253, 2004.

Merkle-Damgora struktur

Sikkerhedsfunktioner

Eksempel

Ændringer

Noter

Links