Merkle-Damgora struktur

Merkle -Damgård konstruktion ( eng. Merkle-Damgård konstruktion , MD ) är en metod för att konstruera kryptografiska hashfunktioner som går ut på att dela upp ingångsmeddelanden av godtycklig längd i block med fast längd och arbeta med dem i tur och ordning med hjälp av komprimeringsfunktionen, varje gång en ingångsblock med en utgång från föregående pass.

Beskrevs första gången 1979 i doktorsavhandlingen av Ralph Merkle [1] . Merkle och Damgor visade oberoende att om kompressionsfunktionen är motståndskraftig mot kollisioner så kommer hashfunktionen också att vara stabil [2] [3] — för att bevisa strukturens stabilitet kompletteras meddelandet med ett block som kodar längden på det ursprungliga meddelandet (Merkle-Damgor härdning ).

Strukturen tillhandahåller en initialiseringsvektor - ett fast värde som beror på implementeringen av algoritmen och som appliceras på det första passet - som applicerar komprimeringsfunktionen på den och det första blocket i meddelandet. Resultatet av varje pass skickas till nästa ingång och nästa meddelandeblock; det sista blocket är utfyllt med nollor, vid behov läggs även ett block med information om längden på hela meddelandet till. För att härda hashen skickas det sista resultatet ibland genom en slutbehandlingsfunktion , som också kan användas för att minska storleken på utdatahashen genom att komprimera resultatet från den senaste applikationen till en mindre hash, eller för att säkerställa bättre bitblandning och förstärkning effekten av en liten förändring i inmatningsmeddelandet på hashen ( ge en lavineffekt ). Slutbehandlingsfunktionen byggs ofta med hjälp av komprimeringsfunktionen. $f$ $f$ $f$

De huvudsakliga algoritmerna som implementerar Merkle-Damgor-strukturen är MD5 , SHA-1 , SHA-2- familjen .

Säkerhetsfunktioner

Populariteten för Merkle- Damgor -strukturen beror på följande resultat: om en envägskompressionsfunktion är motståndskraftig mot kollisioner , kommer hashfunktionen som bygger på dess bas också att vara motståndskraftig mot kollisioner. I det här fallet har strukturen flera oönskade egenskaper: $f$

den andra preimage-attacken för långa meddelanden är alltid mycket effektivare än brute force . En attack på ett blockmeddelande kan slutföras i tid ; det är viktigt att komplexiteten i attacken är mellan och när meddelandena är långa, och när meddelandelängden blir mindre närmar sig komplexiteten [4] ; $2^k$ $k\times 2^{n/2+1}+2^{n-k+1}$ $2^{{n/2}}$ $2^{n}$ $2^{n}$
flera kollisioner (många meddelanden har samma hash) kan bara hittas med marginellt mer ansträngning än kollisioner [5] ;
meddelandeutfyllnadsattacker: givet en hash av ett okänt inmatningsmeddelande är det lätt att hitta värdet , var är utfyllnadsfunktionen ; detta betyder att det är möjligt att hitta hash av ingångsmeddelanden associerade med även när det förblir okänt [6] ; det slumpmässiga oraklet har inte denna förmåga, och detta kan leda till enkla attacker även mot system som har visat sig vara säkra för den slumpmässiga orakelmodellen [7] . $H(X)$ $X$ $H(\mathrm {pad} (X)||Y)$ $\mathrm {pad}$ $X$ $X$

Exempel

För att skicka ett meddelande till komprimeringsfunktionen är det nödvändigt att fylla det sista blocket till fullo med vissa data (vanligtvis nollor). Till exempel, för ett meddelande " HashInput " och en blockstorlek för komprimeringsfunktionen på 8 byte (64 bitar), skulle detta resultera i 2 block:

HashInpu t0000000

Men detta räcker inte, eftersom det skulle innebära att olika meddelanden som börjar med samma tecken och slutar med nollor eller andra bytes från utfyllnaden kommer in i komprimeringsfunktionen i exakt samma block, och samma hashsumma kommer att erhållas. I det här exemplet kommer " HashInput00 "-meddelandet att delas upp i samma block som det ursprungliga " HashInput "-meddelandet. För att undvika detta måste den första biten av den tillagda datan ändras. Eftersom utfyllnaden vanligtvis består av nollor måste den första biten av utfyllnaden ersättas med en "1":

HashInpu t1000000

För att stärka hashen kan du lägga till längden på meddelandet i ett extra block:

HashInpu t1000000 00000009

För att undvika tvetydighet måste värdet på meddelandelängden i sig vara resistent mot utfyllnad i blocket. De vanligaste implementeringarna använder en fast storlek (vanligtvis 64 eller 128 bitar i moderna algoritmer) och en fast position i slutet av det sista blocket för att koda meddelandelängdsvärdet.

Det är dock lite slösaktigt att koda ett extra block för meddelandelängden, så det finns en liten algoritmoptimering som ofta används: om det finns tillräckligt med utrymme i det sista meddelandeblocket kan meddelandelängdsvärdet läggas till det. Om du till exempel kodar meddelandelängden i 5 byte räcker det med två block, till exempel:

HashInpu t1000009

Ändringar

2006 föreslogs HAIFA - metoden , där Merkle-Damgor-strukturen är något modifierad: förutom meddelandeblocket förses varje komprimeringsfunktion med den aktuella offseten i indatafilen och eventuellt lite salt .

På grund av vissa svagheter i strukturen, särskilt problemet med att fylla ut meddelandet till önskad längd, föreslog Stefan Lux 2004 att man skulle använda en bred pipeline-hash ( wilde pipe-hash ) [8] , liknande Merkle-Damgor struktur, men med fler interna tillstånd, det vill säga bitlängden som används internt av algoritmen är större än utdata. Så det sista steget är den andra komprimeringsfunktionen, som komprimerar det sista interna hashvärdet till det slutliga värdet. SHA-224 och SHA-384 härleddes från SHA-256 respektive SHA-512 genom att tillämpa denna algoritm.

Anteckningar

↑ R.C. Merkle. sekretess, autentisering och offentliga nyckelsystem. Arkiverad 14 augusti 2018 på Wayback Machine Stanford Ph.D. avhandling 1979, sid 13-15.
↑ Merkle R. A Certified Digital Signature // Advances in Cryptology - CRYPTO '89 : 9th Annual International Cryptology Conference, Santa Barbara, Kalifornien, USA, 20-24 augusti 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, Kalifornien, USA, 20-24 augusti 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. 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 maj -26, 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
↑ Joux A. Multikollisioner i itererade hashfunktioner. Ansökan till Cascaded Constructions (engelska) // Advances in Cryptology - CRYPTO 2004 : 24th Annual International Cryptology Conference, Santa Barbara, Kalifornien, USA, 15-19 augusti 2004, Proceedings / M. Franklin - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Science + Business Media , 2004. - P. 306-316. — 579 sid. - ( 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. Bärgning av Merkle-Damgård för praktiska tillämpningar . Preliminär version i Advances in Cryptology - EUROCRYPT '09 Proceedings, Lecture Notes in Computer Science Vol. 5479, A. Joux, ed, Springer-Verlag, 2009, sid. 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, Kalifornien, USA, augusti 14-18, 2005, Proceedings / V. Shoup - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Science + Business Media , 2005. - P. 430-448. — 572 sid. - ( 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, Report 2004/253, 2004.

Länkar

Handbook of Applied Cryptography av Menezes, van Oorschot och Vanstone (2001), kapitel 9.
Introduktion till modern kryptografi , av Jonathan Katz och Yehuda Lindell. Chapman och Hall/CRC Press, augusti 2007, sidan 134 (konstruktion 4.13).