Whirlpool (hash-funktion)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 25. februar 2022; checks kræver 2 redigeringer .
Whirlpool
Udviklere Vincent Rayman ,
Barreto
Først udgivet november 2000
Standarder NESSIE Portfolio ( 2003 ), ISO/IEC 10118-3:2004 ( 2004 )
Hash størrelse 512 bit
Antal runder ti
Type hash funktion

Whirlpool  er en kryptografisk hashfunktion udviklet af Vincent Rayman og Paulo Barreto . Udgivet i november 2000 . Hashes inputmeddelelsen op til bit lang. Outputværdien af ​​Whirlpool- hash-funktionen , kaldet hash , er 512 bit.

Historie

Titel

Whirlpool hash-funktionen er opkaldt efter Whirlpool Galaxy (M51) i stjernebilledet Canis Hounds  , den første galakse med en observerbar spiralstruktur.

Ændringer

Siden starten i 2000 er Whirlpool blevet ændret to gange.

Den første version, Whirlpool-0, præsenteres som kandidat i NESSIE-projektet ( eng.  New European Schemes for Signatures, Integrity and Encryption , new European projects on digital signatur , integrity and encryption).

En modifikation af Whirlpool-0, kaldet Whirlpool-T, blev føjet til NESSIE-listen over anbefalede kryptografiske funktioner i 2003 . Ændringerne vedrørte substitutionsblokken ( S-box ) af Whirlpool: i den første version blev S-box-strukturen ikke beskrevet, og den blev genereret vilkårligt, hvilket skabte visse problemer i hardwareimplementeringen af ​​Whirlpool. I Whirlpool-T-versionen "får" S-boksen en klar struktur.

En defekt i Whirlpool-T diffuse matricer opdaget af Taizō Shirai og Kyoji Shibutani [1] blev efterfølgende rettet, og den endelige (tredje) version, kaldet blot Whirlpool for kort, blev vedtaget af ISO i ISO/IEC 10118-3:2004 i 2004.

Beskrivelse

Hovedversionen - hash-funktioner - er den tredje; i modsætning til den første version er S-boksen defineret, og den diffuse matrix erstattes med en ny efter rapporten fra Shirai og Shibutani [1] .

Whirlpool består i at genanvende komprimeringsfunktionen , som er baseret på en speciel 512-bit blokchiffer med en 512-bit nøgle.

Algoritmen bruger operationer i Galois-feltet modulo et irreducerbart polynomium .

Polynomier er skrevet i hexadecimal for kortheds skyld. For eksempel betyder indtastningen .

Symbolet bruges til at angive sammensætningen af ​​en række funktioner : eller simpelthen

Dataformat

Whirlpool er bygget på en speciel blokchiffer , der fungerer med 512-bit data.

I transformationer kaldes mellemresultatet af en hash -beregning en hashtilstand eller blot en tilstand . I databehandling er en tilstand normalt repræsenteret af en tilstandsmatrix . For Whirlpool er dette en matrix i . Derfor skal 512-bit datablokke konverteres til dette format før yderligere beregninger. Dette opnås ved at introducere funktionen :

Kort sagt er tilstandsmatrixen fyldt med data linje for linje. I dette tilfælde er hver byte i matrixen det tilsvarende polynomium i .

Transformationer

Ikke- lineær transformation (S-boks)

Funktionen består i at anvende en substitutionsboks ( S-boks ) parallelt på alle bytes i tilstandsmatrixen:

Substitutionsblokken er beskrevet af følgende erstatningstabel:

Tabel 1. Substitutionsblok

Cyklisk permutation

Permutationen roterer hver kolonne i tilstandsmatrixen, så kolonnen flyttes nedad :

Opgaven med denne transformation er at blande bytes af tilstandsmatrixrækkerne med hinanden.

Lineær diffusion

Lineær diffusion  er en lineær transformation, hvis matrix er MDS-matricen , det vil sige:


Med andre ord multipliceres tilstandsmatrixen fra højre med matrixen . Husk på, at operationerne med addition og multiplikation af matrixelementer udføres i .

En MDS-matrix  er en sådan matrix over et endeligt felt , at hvis vi tager det som en matrix af en lineær transformation fra rumtil rum, så vil alle to vektorer fravisningsrummethave mindstforskelle i komponenter. Det vil sige, at et sæt visningsvektorerdanner en kode, der har egenskaben maksimal afstand ( engelsk. Maximum Distance Separable code ). En sådan kode er for eksempel Reed-Solomon-koden .  

I Whirlpool betyder den maksimale diversitetsegenskab for en MDS-matrix, at det samlede antal skiftende bytes af vektoren og vektoren er mindst . Med andre ord, enhver ændring til kun én byte resulterer i en ændring af alle 8 bytes . Dette er problemet med lineær diffusion .

Som nævnt ovenfor er MDS-matricen i den seneste (tredje) version af Whirlpool blevet ændret takket være en artikel af Taizo Shirai og Kyoji Shibutani[1] . De analyserede MDS-matricen af ​​den anden version af Whirlpool og påpegede muligheden for at forbedre Whirlpools modstand mod differentiel kryptoanalyse . De foreslog også 224 kandidater til den nye MDS-matrix. Fra denne liste valgte Whirlpool-forfatterne den mulighed, der er lettest implementeret i hardware.

Tilføjelse af en nøgle

Nøgleadditionsfunktionen er en bitvis addition ( XOR ) af tilstanden og nøglematricerne :

Runde konstanter

Hver runde bruger en matrix af konstanter , således at:

Dette viser, at den første række af matricen er resultatet af at anvende en substitutionsblok på byte-numre .

De resterende 7 linjer er nul.

Rund funktion

For hver runde er rundfunktionen  en sammensat transformation, hvis parameter er nøglematrixen . Den runde funktion er beskrevet som følger:

Nøgleudvidelse

En 512-bit krypteringsnøgle er påkrævet for hver runde . For at løse dette problem introducerer mange algoritmer den såkaldte nøgleudvidelsesprocedure . I Whirlpool implementeres nøgleudvidelsen som følger:

Ud fra den kendte nøgle produceres den nødvendige sekvens af nøgler for hver runde af blokchifferet .

Blok chiffer

En speciel 512-bit blokchiffer bruger en 512-bit nøgle som parameter og udfører følgende sekvens af transformationer:

hvor nøglerne genereres af nøgleudvidelsesproceduren beskrevet ovenfor . I Whirlpool hash-funktionen er antallet af runder .

Komplementering af inputmeddelelsen

Whirlpool skal, ligesom enhver anden hash-funktion , hash en besked af vilkårlig længde. Da den interne krypteringsblok fungerer med 512-bit inputmeddelelser, skal den originale meddelelse opdeles i blokke på 512 bit. I dette tilfælde kan den sidste blok, som indeholder slutningen af ​​meddelelsen, være ufuldstændig.

For at løse dette problem bruger Whirlpool Merkle-Damgor- forøgelsesalgoritmen for inputmeddelelse. Resultatet af meddelelsesfuldførelse er en meddelelse, hvis længde er et multiplum af 512. Lad være  længden af ​​den oprindelige meddelelse. Så viser det sig i flere trin:

  1. I slutningen af ​​meddelelsen skal du tilføje en "1" bit.
  2. Tildel bits "0", så længden af ​​den modtagne streng er et multiplum af et ulige antal gange.
  3. Tildel endelig en 256-bit talrepræsentation til .

Den supplerede besked skrives som

og opdelt i 512-bit blokke til yderligere behandling.

Kompressionsfunktion

Whirlpool bruger Preneel - skemaet

blokke af den polstrede besked krypteres sekventielt med en blokchiffer :


hvor ( eng. initialiseringsvektor , initialiseringsvektor ) er en 512-bit streng fyldt med "0".  

Hash-beregning

Meddelelsessammendraget er outputværdien af ​​komprimeringsfunktionen, konverteret tilbage til en 512-bit streng:

Sikkerhed

En hashfunktion siges at være kryptografisk sikker , hvis den opfylder de tre grundlæggende krav, som de fleste anvendelser af hashfunktioner i kryptografi er baseret på : irreversibilitet , type 1 kollisionsmodstand og type 2 kollisionsmodstand .

Lad være  en vilkårlig -bit understreng af en 512-bit Whirlpool hash . Forfatterne af Whirlpool hævder, at hashfunktionen, de oprettede, opfylder følgende krav til kryptografisk styrke :

Whirlpool-forfatterne tilføjede en note til denne erklæring:

Disse udsagn følger af en betydelig sikkerhedsmargin mod alle kendte angreb. Vi forstår dog, at det er umuligt at komme med ikke-spekulative udsagn om ukendte ting.

Krypteringsanalyse

Til dato er WHIRLPOOL modstandsdygtig over for alle former for kryptoanalyse . I løbet af de 8 år af Whirlpools eksistens er der ikke registreret et eneste angreb på det.

Men i 2009 blev en ny metode til at angribe hash-funktioner udgivet  - The Rebound Attack [2] [3] . Det nye angrebs første "marsvin" var hashfunktionerne Whirlpool og Grøstl . Resultaterne af den gennemførte kryptoanalyse er vist i tabellen.

Tabel 2. Resultater af krypteringsanalyse af Whirlpool og Grøstl hashfunktioner ved hjælp af The Rebound Attack metoden [2] [3]
hash funktion Antal runder Kompleksitet Påkrævet mængde hukommelse Kollisionstype
Whirlpool kollision
halvfri kollision
halvfri næsten kollision
Grøstl-256 halvfri kollision

Forfatterne til undersøgelsen brugte følgende begreber og termer:

  •  - initialiseringsvektor
  •  - beskeden, der skal hash
  •  - hash funktion
  • kompressionsfunktion

Kollisionstyper : _

  • kollision :
    •  - fast
  • næsten en kollision :
    •  - fast
    • et lille antal bit -hash og er forskellige
  • semi-fri kollision :
  • fri kollision :


Som det kan ses af tabellen, lykkedes det os kun at generere en kollision for Whirlpool for dens "cut down" version på 4,5 runder. Derudover er kompleksiteten af ​​de nødvendige beregninger ret høj.

Ansøgning

Whirlpool er en frit tilgængelig hashfunktion . Derfor er det meget brugt i open source-software . Her er nogle eksempler på brug af Whirlpool:

Eksempler på hashes

For nemheds skyld er de 512 bit (64 bytes) af Whirlpool-hashen ofte repræsenteret som et 128-cifret hexadecimalt tal.

Som nævnt ovenfor har algoritmen gennemgået to ændringer siden den blev udgivet i 2000. Nedenfor er eksempler på hashes beregnet fra ASCII - teksten til Den hurtige brune ræv hopper over den dovne hunds pangram for alle tre versioner af Whirlpool:

Whirlpool-0("Den hurtige brune ræv hopper over den dovne hund") = 4F8F5CB531E3D49A61CF417CD133792CCFA501FD8DA53EE368FED20E5FE0248C 3A0B64F98A6533CEE1DA614C3A8DDEC791FF05FEE6D971D57C1348320F4EB42D Whirlpool-T("Den hurtige brune ræv hopper over den dovne hund") = 3CCF8252D8BBB258460D9AA999C06EE38E67CB546CFFCF48E91F700F6FC7C183 AC8CC3D3096DD30A35B01F4620A1E3A20D79CD5168544D9E1B7CDF49970E87F1 Whirlpool("Den hurtige brune ræv hopper over den dovne hund") = B97DE512E91E3828B40D2B0FDCE9CEB3C4A71F9BEA8D88E75C4FA854DF36725F D2B52EB6544EDCACD6F8BEDDFEA403CB55AE31F03AD62A5EF54E42EE82C3FB35

Selv en lille ændring i meddelelsens originaltekst (i dette tilfælde erstattes et bogstav: tegnet "d" erstattes med tegnet "e") fører til en fuldstændig ændring i hashen :

Whirlpool-0("Den hurtige brune ræv hopper over det dovne eog") = 228FBF76B2A93469D4B25929836A12B7D7F2A0803E43DABA0C7FC38BC11C8F2A 9416BBCF8AB8392EB2AB7BCB565A64AC50C26179164B26084A253CAF2E012676 Whirlpool-T("Den hurtige brune ræv hopper over det dovne eog") = C8C15D2A0E0DE6E6885E8A7D9B8A9139746DA299AD50158F5FA9EECDDEF744F9 1B8B83C617080D77CB4247B1E964C2959C507AB2DB0F1F3BF3E3B299CA00CAE3 Whirlpool("Den hurtige brune ræv hopper over det dovne eog") = C27BA124205F72E6847F3E19834F925CC666D0974167AF915BB462420ED40CC5 0900D85A1F923219D832357750492D5C143011A76988344C2635E69D06F2D38C

Tilføjelse af tegn til en streng, strengsammenkædning og andre ændringer påvirker også resultatet.

Eksempler på hashes til "null"-strengen:

Whirlpool-0("") = B3E1AB6EAF640A34F784593F2074416ACCD3B8E62C620175FCA0997B1BA23473 39AA0D79E754C308209EA36811DFA40C1C32F1A2B9004725D987D3635165D3C8 Whirlpool-T("") = 470F0409ABAA446E49667D4EBE12A14387CEDBD10DD17B8243CAD550A089DC0F EEA7AA40F6C2AAAB71C6EBD076E43C7CFCA0AD32567897DCB5969861049A0F5A Whirlpool("") = 19FA61D75522A4669B44E39C1D2E1726C530232130D407F89AFEE0964997F7A7 3E83BE698B288FEBCF88E3E03C4F0757EA8964E59B63D93708B138CC42A66EB3

Eksempler i programmering

Runtime Koden Resultat
PHP 5.0 echo hash( 'whirlpool', 'test'); b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f 8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6
rubin sætter Whirlpool.calc_hex('test') b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f 8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6

Noter

  1. 1 2 3 Kyoji, Shibutani; Shirai, Taizo. På diffusionsmatrixen anvendt i Whirlpool hashing-funktionen  : journal . - 2003. - 11. marts.  
  2. 1 2 Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen. The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl  ( 24. februar 2009). — præsentation af en ny kryptoanalysemetode og dens anvendelse til kryptoanalyse af Whirlpool og Grøstl hashfunktioner . Hentet 25. juni 2019. Arkiveret fra originalen 28. september 2011.
  3. 1 2 Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen. The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl  (engelsk) (2009). — en artikel om en ny kryptoanalysemetode og dens anvendelse til kryptoanalyse af Whirlpool og Grøstl hashfunktioner . Hentet 25. juni 2019. Arkiveret fra originalen 18. november 2018.

Links

  • Whirlpool  hjemmeside . - Whirlpool hjemmeside. Hentet 25. juni 2019. Arkiveret fra originalen 29. november 2017.

Standarder

  •  ISO/IEC 10118-3 : 2004-standarden . — ISO/IEC 10118-3:2004 standard. Dato for adgang: 25. juni 2019.
  • NESSIE  (engelsk) . - Engelsk.  Nye europæiske ordninger for signaturer, integritet og kryptering , nye europæiske projekter om digital signatur, integritet og kryptering. Dato for adgang: 25. juni 2019.
  •  Portefølje af anbefalede kryptografiske primitiver . — en liste over NESSIE kryptografiske funktioner, der anbefales til brug. Dato for adgang: 25. juni 2019.

Softwareimplementeringer

Hardwareimplementeringer

  •  Effektiv arkitektur og hardwareimplementering af Whirlpool hash-funktionen . - Effektiv hardwareimplementering af Whirlpool. IEEE Transaktioner på forbrugerelektronik artikel. Hentet 18. november 2009. Arkiveret fra originalen 29. februar 2012.
  •  Højhastigheds-parallel arkitektur af Whirlpool Hash-funktionen . - Whirlpool højhastigheds parallel arkitektur. Artikel i International Journal of Advanced Science and Technology , udgave 7, juni 2009. Hentet 18. november 2009. Arkiveret fra originalen 29. februar 2012.