Whirlpool (hashfunktion)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 25 februari 2022; kontroller kräver 2 redigeringar .
Bubbelpool
Utvecklare Vincent Rayman ,
Barreto
Först publicerad november 2000
Standarder NESSIE Portfolio ( 2003 ), ISO/IEC 10118-3:2004 ( 2004 )
Hash storlek 512 bitar
Antal omgångar tio
Sorts hash-funktion

Whirlpool  är en kryptografisk hashfunktion utvecklad av Vincent Rayman och Paulo Barreto . Publicerad i november 2000 . Hashar inmatningsmeddelandet upp till bitar långt. Utgångsvärdet för Whirlpool- hashfunktionen , kallad hash , är 512 bitar.

Historik

Titel

Whirlpool- hashfunktionen är uppkallad efter Whirlpoolgalaxen (M51) i stjärnbilden Canis Hounds  , den första galaxen med en observerbar spiralstruktur.

Ändringar

Sedan starten 2000 har Whirlpool modifierats två gånger.

Den första versionen, Whirlpool-0, presenteras som en kandidat i NESSIE-projektet ( eng.  New European Schemes for Signatures, Integrity and Encryption , new European projects on digital signatur , integrity and encryption).

En modifiering av Whirlpool-0, kallad Whirlpool-T, lades till i NESSIE-listan över rekommenderade kryptografiska funktioner 2003 . Ändringarna gällde ersättningsblocket ( S-box ) av Whirlpool: i den första versionen beskrevs inte S-box-strukturen, och den genererades godtyckligt, vilket skapade vissa problem i hårdvaruimplementeringen av Whirlpool. I Whirlpool-T-versionen "fick" S-boxen en tydlig struktur.

En defekt i Whirlpool-T diffusa matriser upptäckt av Taizō Shirai och Kyoji Shibutani [1] korrigerades därefter, och den slutliga (tredje) versionen, kallad helt enkelt Whirlpool, antogs av ISO i ISO/IEC 10118-3:2004 år 2004.

Beskrivning

Huvudversionen - hashfunktioner - är den tredje; till skillnad från den första versionen är S-boxen definierad och den diffusa matrisen ersätts med en ny efter rapporten från Shirai och Shibutani [1] .

Whirlpool består av att återanvända komprimeringsfunktionen , som är baserad på ett speciellt 512-bitars blockchiffer med en 512-bitars nyckel.

Algoritmen använder operationer i Galois-fältet modulo ett irreducerbart polynom .

Polynom skrivs i hexadecimal för korthetens skull. Till exempel betyder posten .

Symbolen används för att beteckna sammansättningen av en sekvens av funktioner : eller bara

Dataformat

Whirlpool är byggt på ett speciellt blockchiffer som fungerar med 512-bitars data.

I transformationer kallas det mellanliggande resultatet av en hashberäkning ett hashtillstånd, eller helt enkelt ett tillstånd . Vid beräkning representeras ett tillstånd vanligtvis av en tillståndsmatris . För Whirlpool är detta en matris i . Därför måste 512-bitars datablock konverteras till detta format innan ytterligare beräkningar. Detta uppnås genom att introducera funktionen :

Enkelt uttryckt är tillståndsmatrisen fylld med data rad för rad. I det här fallet är varje byte i matrisen motsvarande polynom i .

Transformationer

Icke-linjär transformation (S-box)

Funktionen består av att applicera en ersättningsbox ( S-box ) parallellt på alla bytes i tillståndsmatrisen:

Ersättningsblocket beskrivs av följande ersättningstabell:

Tabell 1. Substitutionsblock

Cyklisk permutation

Permutationen roterar varje kolumn i tillståndsmatrisen så att kolumnen flyttas nedåt :

Uppgiften med denna omvandling är att blanda byten i tillståndsmatrisraderna med varandra.

Linjär diffusion

Linjär diffusion  är en linjär transformation vars matris är MDS-matrisen , det vill säga:


Med andra ord multipliceras tillståndsmatrisen från höger med matrisen . Kom ihåg att operationerna för addition och multiplikation av matriselement utförs i .

En MDS-matris  är en sådan matris över ett ändligt fält att om vi tar den som en matris för en linjär transformation från rymdentill rymden, så kommer alla två vektorer frånvyrummetatt ha åtminstoneskillnader i komponenter. Det vill säga en uppsättning vyvektorerbildar en kod som har egenskapen maximalt mellanrum ( engelska. Maximum Distance Separable code ). En sådan kod är till exempel Reed-Solomon-koden .  

I Whirlpool betyder den maximala diversitetsegenskapen för en MDS-matris att det totala antalet byte av vektorn och vektorn är minst . Med andra ord, varje ändring av bara en byte resulterar i en ändring av alla 8 byte . Detta är problemet med linjär diffusion .

Som nämnts ovan har MDS-matrisen i den senaste (tredje) versionen av Whirlpool modifierats tack vare en artikel av Taizo Shirai och Kyoji Shibutani[1] . De analyserade MDS-matrisen för den andra versionen av Whirlpool och påpekade möjligheten att förbättra Whirlpools motståndskraft mot differentiell kryptoanalys . De föreslog också 224 kandidater för den nya MDS-matrisen. Från den här listan valde Whirlpool-författarna det alternativ som är lättast att implementera i hårdvara.

Lägga till en nyckel

Nyckeladditionsfunktionen är en bitvis addition ( XOR ) av tillståndet och nyckelmatriserna :

Runda konstanter

Varje omgång använder en matris av konstanter så att:

Detta visar att den första raden i matrisen är resultatet av att ett substitutionsblock har tillämpats på bytenummer .

De återstående 7 raderna är noll.

Runda funktion

För varje omgång är rundfunktionen  en sammansatt transformation vars parameter är nyckelmatrisen . Den runda funktionen beskrivs så här:

Nyckelförlängning

En 512-bitars krypteringsnyckel krävs för varje omgång . För att lösa detta problem introducerar många algoritmer den så kallade nyckelexpansionsproceduren . I Whirlpool implementeras nyckelexpansion enligt följande:

Sålunda, från den kända nyckeln , produceras den erforderliga sekvensen av nycklar för varje omgång av blockchifferet .

Blockera chiffer

Ett speciellt 512-bitars blockchiffer använder en 512-bitars nyckel som parameter och utför följande sekvens av transformationer:

där nycklarna genereras av nyckelexpansionsproceduren som beskrivs ovan . I Whirlpool- hashfunktionen är antalet rundor .

Kompletterar inmatningsmeddelandet

Whirlpool, precis som alla andra hashfunktioner , måste hasha ett meddelande av godtycklig längd. Eftersom det interna krypteringsblocket fungerar med 512-bitars ingångsmeddelanden måste det ursprungliga meddelandet delas upp i block om 512 bitar. I detta fall kan det sista blocket, som innehåller slutet av meddelandet, vara ofullständigt.

För att lösa detta problem använder Whirlpool Merkle-Damgors algoritm för att förstärka meddelandet. Resultatet av slutförandet av meddelandet är ett meddelande vars längd är en multipel av 512. Låt vara  längden på det ursprungliga meddelandet. Sedan visar det sig i flera steg:

  1. Lägg till en "1"-bit i slutet av meddelandet .
  2. Tilldela bitar "0" så att längden på den mottagna strängen är en multipel av ett udda antal gånger.
  3. Tilldela slutligen en 256-bitars nummerrepresentation till .

Det kompletterade meddelandet skrivs som

och delas upp i 512-bitars block för vidare bearbetning.

Kompressionsfunktion

Whirlpool använder - Preneel hashing-

block av det vadderade meddelandet krypteras sekventiellt med ett blockchiffer :


där ( eng. initieringsvektor , initieringsvektor ) är en 512-bitars sträng fylld med "0".  

Hashberäkning

Meddelandesammandraget är utdatavärdet för komprimeringsfunktionen, konverterad tillbaka till en 512-bitars sträng:

Säkerhet

En hashfunktion sägs vara kryptografiskt säker om den uppfyller de tre grundläggande kraven som de flesta tillämpningar av hashfunktioner inom kryptografi är baserade på : irreversibilitet , typ 1- kollisionsmotstånd och typ 2 - kollisionsmotstånd .

Låt vara  en godtycklig -bitars delsträng av en 512-bitars Whirlpool - hash . Författarna till Whirlpool hävdar att hashfunktionen de skapade uppfyller följande krav för kryptografisk styrka :

  • Kollisionsgenerering kräver en WHIRLPOOL - hashberäkningsordning ( kollisionsmotstånd av det andra slaget ).
  • För en given sökning efter ett sådant meddelande kommer det att kräva en WHIRLPOOL- hashberäkningsordning ( oåterkallelighet ) .
  • För ett givet meddelande skulle det krävas en WHIRLPOOL - hashberäkningsordning för att hitta ett annat meddelande för vilket ( kollisionsmotstånd av det första slaget ).
  • Det är omöjligt att upptäcka systematiska korrelationer mellan någon linjär kombination av ingångsbitar och någon linjär kombination av hashbitar , eller att förutsäga vilka hashbitar som kommer att ändra sitt värde när vissa inmatningsbitar ändras (motstånd mot linjär kryptoanalys och differentiell kryptoanalys ).

Whirlpool-författarna lade till en anteckning till detta uttalande:

Dessa uttalanden följer av en betydande säkerhetsmarginal mot alla kända attacker. Vi förstår dock att det är omöjligt att göra icke-spekulativa uttalanden om okända saker.

Kryptanalys

Hittills är WHIRLPOOL resistent mot alla typer av kryptoanalys . Under de 8 åren av Whirlpools existens har inte en enda attack mot den registrerats.

Men 2009 publicerades en ny metod för att attackera hashfunktioner  - The Rebound Attack [2] [3] . De första "marsvinen" i den nya attacken var hashfunktionerna Whirlpool och Grøstl . Resultaten av den genomförda kryptoanalysen visas i tabellen.

Tabell 2. Resultat av kryptoanalys av Whirlpool och Grøstl hashfunktioner med hjälp av metoden Rebound Attack [2] [3]
hash-funktion Antal omgångar Komplexitet Erforderlig mängd minne Kollisionstyp
Bubbelpool kollision
halvfri kollision
halvfri nästan kollision
Grøstl-256 halvfri kollision

Författarna till studien använde följande begrepp och termer:

  •  - initieringsvektor
  •  - meddelandet som ska hashas
  •  - hashfunktion
  • kompressionsfunktion

Kollisionstyper : _

  • kollision :
    •  - fixat
  • nästan en kollision :
    •  - fixat
    • ett litet antal bithaschar och är olika
  • halvfri kollision :
  • fri kollision :


Som framgår av tabellen lyckades vi generera en kollision för Whirlpool endast för dess "cut down" version på 4,5 omgångar. Dessutom är komplexiteten i de nödvändiga beräkningarna ganska hög.

Applikation

Whirlpool är en fritt tillgänglig hashfunktion . Därför används det ofta i programvara med öppen källkod . Här är några exempel på hur du använder Whirlpool:

Exempel på hash

För enkelhetens skull representeras de 512 bitarna (64 byte) i Whirlpool-hash ofta som ett 128-siffrigt hexadecimalt tal.

Som nämnts ovan har algoritmen genomgått två förändringar sedan den släpptes 2000. Nedan finns exempel på hash som beräknats från ASCII- texten till Den snabba bruna räven hoppar över den lata hundens pangram för alla tre versionerna av Whirlpool:

Whirlpool-0("Den kvicka bruna räven hoppar över den lata hunden") = 4F8F5CB531E3D49A61CF417CD133792CCFA501FD8DA53EE368FED20E5FE0248C 3A0B64F98A6533CEE1DA614C3A8DDEC791FF05FEE6D971D57C1348320F4EB42D Whirlpool-T("Den kvicka bruna räven hoppar över den lata hunden") = 3CCF8252D8BBB258460D9AA999C06EE38E67CB546CFFCF48E91F700F6FC7C183 AC8CC3D3096DD30A35B01F4620A1E3A20D79CD5168544D9E1B7CDF49970E87F1 Whirlpool("Den kvicka bruna räven hoppar över den lata hunden") = B97DE512E91E3828B40D2B0FDCE9CEB3C4A71F9BEA8D88E75C4FA854DF36725F D2B52EB6544EDCACD6F8BEDDFEA403CB55AE31F03AD62A5EF54E42EE82C3FB35

Även en liten ändring i meddelandets originaltext (i det här fallet ersätts en bokstav: tecknet "d" ersätts med tecknet "e") leder till en fullständig förändring i hashen :

Whirlpool-0("Den kvicka bruna räven hoppar över den lata eog") = 228FBF76B2A93469D4B25929836A12B7D7F2A0803E43DABA0C7FC38BC11C8F2A 9416BBCF8AB8392EB2AB7BCB565A64AC50C26179164B26084A253CAF2E012676 Whirlpool-T("Den kvicka bruna räven hoppar över den lata eog") = C8C15D2A0E0DE6E6885E8A7D9B8A9139746DA299AD50158F5FA9EECDDEF744F9 1B8B83C617080D77CB4247B1E964C2959C507AB2DB0F1F3BF3E3B299CA00CAE3 Whirlpool("Den kvicka bruna räven hoppar över den lata eog") = C27BA124205F72E6847F3E19834F925CC666D0974167AF915BB462420ED40CC5 0900D85A1F923219D832357750492D5C143011A76988344C2635E69D06F2D38C

Att lägga till tecken i en sträng, strängsammansättning och andra ändringar påverkar också resultatet.

Exempel på hash för "null"-strängen:

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

Exempel i programmering

Körning Koden Resultat
PHP 5.0 echo hash( 'whirlpool', 'test' ); b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f 8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6
rubin sätter Whirlpool.calc_hex('test') b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f 8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6

Anteckningar

  1. 1 2 3 Kyoji, Shibutani; Shirai, Taizo. På diffusionsmatrisen som används i Whirlpools hashfunktion  : journal . - 2003. - 11 mars.  
  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 februari 2009). — Presentation av en ny kryptoanalysmetod och dess tillämpning för kryptoanalys av Whirlpool och Grøstl hashfunktioner . Hämtad 25 juni 2019. Arkiverad från originalet 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  (engelska) (2009). — en artikel om en ny kryptoanalysmetod och dess tillämpning för kryptoanalys av Whirlpool och Grøstl hashfunktioner . Hämtad 25 juni 2019. Arkiverad från originalet 18 november 2018.

Länkar

  • Whirlpool  hemsida . - Whirlpools hemsida. Hämtad 25 juni 2019. Arkiverad från originalet 29 november 2017.

Standarder

  •  ISO/IEC 10118-3 : 2004-standarden . — ISO/IEC 10118-3:2004 standard. Tillträdesdatum: 25 juni 2019.
  • NESSIE  (engelska) . - Engelska.  Nya europeiska system för signaturer, integritet och kryptering , nya europeiska projekt om digital signatur, integritet och kryptering. Tillträdesdatum: 25 juni 2019.
  •  Portfölj med rekommenderade kryptografiska primitiver . — En lista över NESSIE-krypteringsfunktioner som rekommenderas för användning. Tillträdesdatum: 25 juni 2019.

Programvaruimplementeringar

Hårdvaruimplementationer

  •  Effektiv arkitektur och hårdvaruimplementering av Whirlpools hashfunktion . - Effektiv hårdvaruimplementering av Whirlpool. Artikel IEEE Transaktioner på konsumentelektronik . Hämtad 18 november 2009. Arkiverad från originalet 29 februari 2012.
  •  Höghastighets-parallell arkitektur för Whirlpool Hash-funktionen . - Whirlpool höghastighets parallell arkitektur. Artikel i International Journal of Advanced Science and Technology , nummer 7, juni 2009. Hämtad 18 november 2009. Arkiverad från originalet 29 februari 2012.