Whirlpool (hashovací funkce)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 25. února 2022; kontroly vyžadují 2 úpravy .
vířivá vana
Vývojáři Vincent Rayman ,
Barreto
Poprvé zveřejněno listopadu 2000
Normy Portfolio NESSIE ( 2003 ), ISO/IEC 10118-3:2004 ( 2004 )
Velikost hash 512 bit
Počet kol deset
Typ hashovací funkce

Whirlpool  je kryptografická hashovací funkce vyvinutá Vincentem Raymanem a Paulo Barretem . Publikováno v listopadu 2000 . Hashuje vstupní zprávu až bitů dlouhou. Výstupní hodnota hashovací funkce Whirlpool , nazývaná hash , je 512 bitů.

Historie

Název

Hashovací funkce Whirlpool je pojmenována po galaxii Whirlpool (M51) v souhvězdí Psí psy  , první galaxii s pozorovatelnou spirální strukturou.

Úpravy

Od svého vzniku v roce 2000 byl Whirlpool dvakrát upravován.

První verze, Whirlpool-0, je prezentována jako kandidát v projektu NESSIE ( angl.  New European Schemes for Signatures, Integrity and Encryption , nové evropské projekty pro digitální podpis , integritu a šifrování).

Na seznam doporučených kryptografických funkcí NESSIE byla v roce 2003 přidána modifikace Whirlpool-0 s názvem Whirlpool-T . Změny se týkaly substitučního bloku ( S-box ) Whirlpool: v první verzi nebyla struktura S-boxu popsána a byla generována svévolně, což způsobilo určité problémy v hardwarové implementaci Whirlpool. Ve verzi Whirlpool-T „získal“ S-box jasnou strukturu.

Vada v difuzních matricích Whirlpool-T objevená Taizō Shirai a Kyoji Shibutani [1] byla následně opravena a konečná (třetí) verze, zkráceně jednoduše Whirlpool, byla přijata ISO v ISO/IEC 10118-3:2004 v roce 2004.

Popis

Hlavní verze - hashovací funkce - je třetí; na rozdíl od první verze je definován S-box a difúzní matice je nahrazena novou po zprávě Shirai a Shibutani [1] .

Whirlpool spočívá v opětovném použití kompresní funkce , která je založena na speciální 512bitové blokové šifře s 512bitovým klíčem.

Algoritmus používá operace v Galoisově poli modulo neredukovatelný polynom .

Polynomy se kvůli stručnosti píší hexadecimálně. Například záznam znamená .

Symbol se používá k označení složení posloupnosti funkcí : nebo jednoduše

Formát dat

Whirlpool je postaven na speciální blokové šifře , která pracuje s 512bitovými daty.

V transformacích se mezivýsledek výpočtu hash nazývá stav hash nebo jednoduše stav . Ve výpočetní technice je stav obvykle reprezentován stavovou maticí . Pro Whirlpool je to matice v . Proto musí být 512bitové datové bloky před dalšími výpočty převedeny do tohoto formátu. Toho je dosaženo zavedením funkce :

Jednoduše řečeno, stavová matice je vyplněna daty řádek po řádku. V tomto případě je každý bajt matice odpovídajícím polynomem v .

Transformace

Nelineární transformace (S-box)

Funkce spočívá v aplikaci substitučního boxu ( S-box ) paralelně na všechny bajty stavové matice:

Substituční blok je popsán v následující substituční tabulce:

Tabulka 1. Substituční blok

Cyklická permutace

Permutace otočí každý sloupec matice stavu tak, aby se sloupec posunul o pozice níže:

Úkolem této transformace je vzájemně promíchat bajty řádků stavové matice.

Lineární difúze

Lineární difúze  je lineární transformace, jejíž maticí je matice MDS , tedy:


tak

Jinými slovy, matice stavu je násobena zprava maticí . Připomeňme, že operace sčítání a násobení prvků matice se provádějí v .

Matice MDS  je taková matice nad konečným polem , že pokud ji vezmeme jako matici lineární transformace z prostorudo prostoru, pak jakékoli dva vektory zpohledubudou mít alespoňrozdíly v komponentách. To znamená, že sada pohledových vektorůtvoří kód, který má vlastnost maximálního rozestupu ( anglicky Maximum Distance Separable code ). Takovým kodexem je například Reed-Solomonův kodex .  

Ve Whirlpoolu vlastnost maximální diverzity matice MDS znamená, že celkový počet měnících se bajtů vektoru a vektoru je alespoň . Jinými slovy, jakákoli změna pouze jednoho bajtu má za následek změnu všech 8 bajtů . Toto je problém lineární difúze .

Jak již bylo zmíněno výše, matice MDS v nejnovější (třetí) verzi Whirlpool byla upravena díky článku Taizo Shirai a Kyoji Shibutani[1] . Analyzovali matici MDS druhé verze Whirlpool a poukázali na možnost zlepšení odolnosti Whirlpoolu vůči diferenciální kryptoanalýze . Navrhli také 224 kandidátů na novou matici MDS. Z tohoto seznamu autoři Whirlpool vybrali možnost, která se nejsnáze implementuje v hardwaru.

Přidání klíče

Funkce sčítání klíče je bitové sčítání ( XOR ) stavu a matice klíčů :

Kulaté konstanty

Každé kolo používá matici konstant tak, že:

To ukazuje, že první řádek matice je výsledkem použití substitučního bloku na čísla bajtů .

Zbývajících 7 řádků je nula.

Kulatá funkce

Pro každé kolo je funkce round  složenou transformací , jejímž parametrem je matice klíče . Funkce zaokrouhlení je popsána následovně:

Rozšíření klíče

Pro každé kolo je vyžadován 512bitový šifrovací klíč . K vyřešení tohoto problému mnoho algoritmů zavádí takzvanou proceduru rozšíření klíče . Ve Whirlpoolu je rozšíření klíče implementováno následovně:

Ze známého klíče se tak vytvoří požadovaná sekvence klíčů pro každé kolo blokové šifry .

Bloková šifra

Speciální 512bitová bloková šifra používá 512bitový klíč jako parametr a provádí následující posloupnost transformací:

kde klíče jsou generovány postupem rozšiřování klíče popsaným výše . V hashovací funkci Whirlpool je počet kol .

Doplnění vstupní zprávy

Whirlpool, stejně jako každá jiná hashovací funkce , musí hashovat zprávu libovolné délky. Protože blok interního šifrování pracuje s 512bitovými vstupními zprávami, musí být původní zpráva rozdělena do bloků po 512 bitech. V tomto případě může být poslední blok, který obsahuje konec zprávy, neúplný.

K vyřešení tohoto problému používá Whirlpool algoritmus pro rozšíření vstupní zprávy Merkle-Damgor . Výsledkem dokončení zprávy je zpráva, jejíž délka je násobkem 512. Nechť  je délka původní zprávy. Pak to dopadne v několika krocích:

  1. Na konec zprávy přidejte bit "1".
  2. Přiřaďte bity "0" tak, aby délka přijatého řetězce byla násobkem lichého počtu.
  3. Nakonec přiřaďte 256bitovou reprezentaci čísla .

Doplněná zpráva je psána jako

a rozdělit do 512bitových bloků pro další zpracování.

Funkce komprese

Whirlpool používá schéma Preneel

bloky vycpané zprávy jsou postupně zašifrovány blokovou šifrou :


kde ( eng. initialization vector , inicializační vektor ) je 512bitový řetězec vyplněný "0".  

Výpočet hash

Výpis zprávy je výstupní hodnota kompresní funkce, převedená zpět na 512bitový řetězec:

Zabezpečení

O hašovací funkci se říká, že je kryptograficky bezpečná , pokud splňuje tři základní požadavky, na kterých je založena většina aplikací hašovacích funkcí v kryptografii : nevratnost , odolnost proti kolizi typu 1 a odolnost proti kolizi typu 2 .

Dovolit být  libovolný -bitový podřetězec 512bitového hash Whirlpool . Autoři Whirlpool tvrdí, že hashovací funkce , kterou vytvořili, splňuje následující požadavky na šifrovací sílu :

  • Generování kolize vyžaduje pořadí výpočtu hash WHIRLPOOL ( odolnost proti kolizím druhého druhu ).
  • Pro dané hledání takové zprávy , že , bude vyžadovat pořadí výpočtu hash WHIRLPOOL ( nevratnost ).
  • Pro danou zprávu by nalezení další zprávy , pro kterou by vyžadovalo pořadí výpočtu hash WHIRLPOOL ( odolnost proti kolizi prvního druhu ).
  • Je nemožné detekovat systematické korelace mezi jakoukoli lineární kombinací vstupních bitů a jakoukoli lineární kombinací hash bitů nebo předvídat, které bity hash změní svou hodnotu, když se změní určité vstupní bity (odolnost vůči lineární kryptoanalýze a diferenciální kryptoanalýze ).

Autoři Whirlpool přidali k tomuto prohlášení poznámku:

Tato prohlášení vyplývají z významné míry bezpečnosti proti všem známým útokům. Chápeme však, že je nemožné činit nespekulativní prohlášení o neznámých věcech.

Kryptoanalýza

K dnešnímu dni je WHIRLPOOL odolný vůči všem typům kryptoanalýzy . Za 8 let existence Whirlpoolu nebyl zaznamenán jediný útok na něj.

V roce 2009 však byla zveřejněna nová metoda útoku na hashovací funkce  - The Rebound Attack [2] [3] . Prvními „pokusnými králíky“ nového útoku byly hashovací funkce Whirlpool a Grøstl . Výsledky provedené kryptoanalýzy jsou uvedeny v tabulce.

Tabulka 2. Výsledky kryptoanalýzy hashovacích funkcí Whirlpool a Grøstl pomocí metody The Rebound Attack [2] [3]
hashovací funkce Počet kol Složitost Požadované množství paměti Typ kolize
vířivá vana kolize
polovolná srážka
polovolný téměř kolize
Grøstl-256 polovolná srážka

Autoři studie použili následující pojmy a termíny:

Typy kolizí :

  • kolize :
    •  - pevný
  • skoro srážka :
    •  - pevný
    • malý počet bitových hashů a jsou různé
  • polovolná srážka :
  • volná srážka :


Jak je z tabulky patrné, podařilo se nám vygenerovat kolizi pro Whirlpool pouze pro jeho „osekanou“ verzi 4,5 náboje. Složitost potřebných výpočtů je navíc poměrně vysoká.

Aplikace

Whirlpool je volně dostupná hashovací funkce . Proto je široce používán v open source softwaru . Zde je několik příkladů použití Whirlpool:

Příklady hashů

Pro usnadnění je 512 bitů (64 bajtů) hash Whirlpool často reprezentováno jako 128místné hexadecimální číslo.

Jak bylo uvedeno výše, algoritmus prošel od svého vydání v roce 2000 dvěma změnami. Níže jsou uvedeny příklady hashů vypočítaných z ASCII textu Rychlá hnědá liška skáče přes pangram líného psa pro všechny tři verze Whirlpool:

Whirlpool-0("Rychlá hnědá liška skáče přes líného psa") = 4F8F5CB531E3D49A61CF417CD133792CCFA501FD8DA53EE368FED20E5FE0248C 3A0B64F98A6533CEE1DA614C3A8DDEC791FF05FEE6D971D57C1348320F4EB42D Whirlpool-T("Rychlá hnědá liška skáče přes líného psa") = 3CCF8252D8BBB258460D9AA999C06EE38E67CB546CFFCF48E91F700F6FC7C183 AC8CC3D3096DD30A35B01F4620A1E3A20D79CD5168544D9E1B7CDF49970E87F1 Whirlpool("Rychlá hnědá liška skáče přes líného psa") = B97DE512E91E3828B40D2B0FDCE9CEB3C4A71F9BEA8D88E75C4FA854DF36725F D2B52EB6544EDCACD6F8BEDDFEA403CB55AE31F03AD62A5EF54E42EE82C3FB35

I malá změna v původním textu zprávy (v tomto případě je nahrazeno jedno písmeno: znak "d" je nahrazen znakem "e") vede k úplné změně hashe :

Whirlpool-0("Rychlá hnědá liška skáče přes líné vajíčko") = 228FBF76B2A93469D4B25929836A12B7D7F2A0803E43DABA0C7FC38BC11C8F2A 9416BBCF8AB8392EB2AB7BCB565A64AC50C26179164B26084A253CAF2E012676 Whirlpool-T("Rychlá hnědá liška skáče přes líné vajíčko") = C8C15D2A0E0DE6E6885E8A7D9B8A9139746DA299AD50158F5FA9EECDDEF744F9 1B8B83C617080D77CB4247B1E964C2959C507AB2DB0F1F3BF3E3B299CA00CAE3 Whirlpool("Rychlá hnědá liška skáče přes líné vajíčko") = C27BA124205F72E6847F3E19834F925CC666D0974167AF915BB462420ED40CC5 0900D85A1F923219D832357750492D5C143011A76988344C2635E69D06F2D38C

Výsledek také ovlivní přidání znaků do řetězce, zřetězení řetězců a další změny.

Příklady hashů pro řetězec "null":

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

Příklady v programování

Doba běhu Kód Výsledek
PHP 5.0 echo hash( 'whirlpool', 'test'); b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f 8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6
rubín vloží Whirlpool.calc_hex('test') b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f 8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6

Poznámky

  1. 1 2 3 Kyoji, Shibutani; Shirai, Taizo. Na difúzní matici použité v hashovací funkci Whirlpool  : journal . - 2003. - 11. března.  
  2. 1 2 Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen. The Rebound Attack: Cryptanalysis of Reduced Whirlpool a Grøstl  ( 24. února 2009). — představení nové metody kryptoanalýzy a její aplikace pro kryptoanalýzu hashovacích funkcí Whirlpool a Grøstl . Získáno 25. června 2019. Archivováno z originálu dne 28. září 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  (anglicky) (2009). — článek o nové metodě kryptoanalýzy a její aplikaci pro kryptoanalýzu hashovacích funkcí Whirlpool a Grøstl . Získáno 25. června 2019. Archivováno z originálu 18. listopadu 2018.

Odkazy

  •  Domovská stránka Whirlpool . - Domovská stránka Whirlpool. Získáno 25. června 2019. Archivováno z originálu dne 29. listopadu 2017.

Normy

  •  Norma ISO/IEC 10118-3 : 2004 . — Norma ISO/IEC 10118-3:2004. Datum přístupu: 25. června 2019.
  • NESSIE  (anglicky) . - anglicky.  Nová evropská schémata pro podpisy, integritu a šifrování , nové evropské projekty v oblasti digitálního podpisu, integrity a šifrování. Datum přístupu: 25. června 2019.
  •  Portfolio doporučených kryptografických primitiv . — seznam kryptografických funkcí NESSIE doporučených pro použití. Datum přístupu: 25. června 2019.

Softwarové implementace

Hardwarové implementace

  •  Efektivní architektura a hardwarová implementace hashovací funkce Whirlpool . - Efektivní hardwarová implementace Whirlpool. Článek IEEE Transactions on Consumer Electronics . Získáno 18. listopadu 2009. Archivováno z originálu 29. února 2012.
  •  Vysokorychlostní paralelní architektura funkce Whirlpool Hash . - Vysokorychlostní paralelní architektura Whirlpool. Článek v International Journal of Advanced Science and Technology , číslo 7, červen 2009. Staženo 18. listopadu 2009. Archivováno z originálu 29. února 2012.