Whirlpool (funcție hash)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 25 februarie 2022; verificările necesită 2 modificări .
Vârtej
Dezvoltatori Vincent Rayman ,
Barreto
Prima publicat noiembrie 2000
Standarde Portofoliul NESSIE ( 2003 ), ISO/IEC 10118-3:2004 ( 2004 )
Dimensiunea hash 512 biți
Numărul de runde zece
Tip de funcția hash

Whirlpool  este o funcție hash criptografică dezvoltată de Vincent Rayman și Paulo Barreto . Publicat în noiembrie 2000 . Hashează mesajul de intrare cu o lungime de până la biți. Valoarea de ieșire a funcției hash Whirlpool , numită hash , este de 512 biți.

Istorie

Titlu

Funcția hash Whirlpool este numită după Galaxia Whirlpool (M51) din constelația Canis Hounds  , prima galaxie cu o structură spirală observabilă.

Modificări

De la înființarea sa în 2000, Whirlpool a fost modificat de două ori.

Prima versiune, Whirlpool-0, este prezentată ca candidat în proiectul NESSIE ( ing.  New European Schemes for Signatures, Integrity and Encryption , noi proiecte europene privind semnătura digitală , integritate și criptare).

O modificare a lui Whirlpool-0, numită Whirlpool-T, a fost adăugată la lista NESSIE de funcții criptografice recomandate în 2003 . Modificările au vizat blocul de substituție ( S-box ) al Whirlpool: în prima versiune, structura S-box nu a fost descrisă și a fost generată în mod arbitrar, ceea ce a creat anumite probleme în implementarea hardware a Whirlpool. În versiunea Whirlpool-T, S-box-ul a „dobândit” o structură clară.

Un defect în matricele difuze Whirlpool-T descoperit de Taizō Shirai și Kyoji Shibutani [1] a fost corectat ulterior, iar versiunea finală (a treia), numită simplu Whirlpool pe scurt, a fost adoptată de ISO în ISO/IEC. 10118-3:2004 în 2004.

Descriere

Versiunea principală - funcții hash - este a treia; spre deosebire de prima versiune, S-box este definită, iar matricea difuză este înlocuită cu una nouă după raportul lui Shirai și Shibutani [1] .

Whirlpool constă în reaplicarea funcției de compresie , care se bazează pe un cifr bloc special de 512 biți cu o cheie de 512 biți.

Algoritmul folosește operații în câmpul Galois modulo un polinom ireductibil .

Polinoamele sunt scrise în hexazecimal pentru concizie. De exemplu, intrarea înseamnă .

Simbolul este folosit pentru a desemna compoziția unei secvențe de funcții : sau pur și simplu

Formatul datelor

Whirlpool este construit pe un cifr bloc special care funcționează cu date de 512 biți.

În transformări, rezultatul intermediar al unui calcul hash se numește o stare hash, sau pur și simplu o stare . În calcul, o stare este de obicei reprezentată printr-o matrice de stare . Pentru Whirlpool, aceasta este o matrice în . Prin urmare, blocurile de date pe 512 biți trebuie convertite în acest format înainte de alte calcule. Acest lucru se realizează prin introducerea funcției :

Mai simplu spus, matricea de stare este umplută cu date linie cu linie. În acest caz, fiecare octet al matricei este polinomul corespunzător în .

Transformări

Transformare neliniară (S-box)

Funcția constă în aplicarea unei casete de substituție ( S-box ) în paralel la toți octeții matricei de stări:

Blocul de substituție este descris de următorul tabel de înlocuire:

Tabelul 1. Bloc de înlocuire

Permutarea ciclică

Permutarea rotește fiecare coloană a matricei de stare, astfel încât coloana să se miște în poziții în jos:

Sarcina acestei transformări este de a amesteca octeții rândurilor matricei de stare între ei.

Difuziune liniară

Difuzia liniară  este o transformare liniară a cărei matrice este matricea MDS , adică:


asa de

Cu alte cuvinte, matricea de stare este înmulțită de la dreapta cu matricea . Reamintim că operațiile de adunare și înmulțire a elementelor matricei se efectuează în .

O matrice MDS  este o astfel de matrice peste un câmp finit încât, dacă o luăm ca o matrice a unei transformări liniare din spațiuîn spațiu, atunci oricare doi vectori dinvizualizarevor avea cel puțindiferențe de componente. Adică, un set de vectori de vizualizareformează un cod care are proprietatea de spațiere maximă ( în engleză. Cod separabil la distanță maximă ). Un astfel de cod este, de exemplu, codul Reed-Solomon .  

În Whirlpool, proprietatea de diversitate maximă a unei matrice MDS înseamnă că numărul total de octeți în schimbare ai vectorului și ai vectorului este de cel puțin . Cu alte cuvinte, orice modificare a unui singur octet are ca rezultat o modificare a tuturor celor 8 octeți . Aceasta este problema difuziei liniare .

După cum sa menționat mai sus, matricea MDS din cea mai recentă (a treia) versiune a Whirlpool a fost modificată datorită unui articol de Taizo Shirai și Kyoji Shibutani[1] . Ei au analizat matricea MDS a celei de-a doua versiuni de Whirlpool și au subliniat posibilitatea de a îmbunătăți rezistența Whirlpool la criptoanaliza diferențială . De asemenea, au propus 224 de candidați pentru noua matrice MDS. Din această listă, autorii Whirlpool au ales opțiunea cel mai ușor implementată în hardware.

Adăugarea unei chei

Funcția de adăugare a cheilor este o adăugare pe biți ( XOR ) a matricelor de stare și cheie :

Constante rotunjite

Fiecare rundă folosește o matrice de constante astfel încât:

Acest lucru arată că primul rând al matricei este rezultatul aplicării unui bloc de substituție numerelor de octeți .

Restul de 7 linii sunt zero.

Funcția rotundă

Pentru fiecare rundă , funcția rotundă  este o transformare compozită al cărei parametru este matricea cheie . Funcția rotundă este descrisă după cum urmează:

Extensie cheie

Pentru fiecare rundă este necesară o cheie de criptare de 512 biți . Pentru a rezolva această problemă, mulți algoritmi introduc așa-numita procedură de extindere a cheilor . În Whirlpool , extinderea cheii este implementată după cum urmează:

Astfel, din cheia cunoscută , secvența necesară de chei este produsă pentru fiecare rundă a cifrului bloc .

Cifra bloc

Un cifr bloc special de 512 biți utilizează o cheie de 512 biți ca parametru și efectuează următoarea secvență de transformări:

unde cheile sunt generate prin procedura de extindere a cheilor descrisă mai sus . În funcția hash Whirlpool, numărul de runde este .

Complementarea mesajului de intrare

Whirlpool, ca orice altă funcție hash , trebuie să trimită un mesaj de lungime arbitrară. Deoarece blocul de criptare intern funcționează cu mesaje de intrare de 512 biți, mesajul original trebuie împărțit în blocuri de 512 biți. În acest caz, ultimul bloc, care conține sfârșitul mesajului, poate fi incomplet.

Pentru a rezolva această problemă, Whirlpool utilizează algoritmul de creștere a mesajelor de intrare Merkle-Damgor . Rezultatul finalizării mesajului este un mesaj a cărui lungime este un multiplu de 512. Fie  lungimea mesajului original. Apoi se dovedește în mai mulți pași:

  1. La sfârșitul mesajului, adăugați un bit „1”.
  2. Atribuiți biții „0” astfel încât lungimea șirului primit să fie un multiplu de un număr impar de ori.
  3. În cele din urmă, atribuiți o reprezentare numerică pe 256 de biți la .

Mesajul completat este scris ca

și împărțit în blocuri de 512 biți pentru procesare ulterioară.

Funcția de compresie

Whirlpool folosește schema de -Preneel

blocurile din mesajul captusit sunt criptate secvenţial cu un cifru bloc :


unde ( eng. vector de inițializare , vector de inițializare ) este un șir de 512 biți umplut cu „0”.  

Calcul hash

Rezumatul mesajului este valoarea de ieșire a funcției de compresie, convertită înapoi într-un șir de 512 biți:

Securitate

Se spune că o funcție hash este sigură din punct de vedere criptografic dacă îndeplinește cele trei cerințe de bază pe care se bazează majoritatea aplicațiilor funcțiilor hash în criptografie : ireversibilitate , rezistență la coliziune de tip 1 și rezistență la coliziune de tip 2 .

Fie  un subșir arbitrar de biți al unui hash Whirlpool de 512 biți . Autorii Whirlpool susțin că funcția hash pe care au creat-o îndeplinește următoarele cerințe pentru puterea criptografică :

  • Generarea coliziunilor necesită o ordine de calcul hash WHIRLPOOL ( rezistența la coliziune de al doilea fel ).
  • Pentru o anumită căutare a unui astfel de mesaj care , va necesita o comandă de calcul hash WHIRLPOOL ( ireversibilitate ).
  • Pentru un anumit mesaj , găsirea unui alt mesaj pentru care ar necesita o ordine de calcul hash WHIRLPOOL ( rezistența la coliziune de primul fel ).
  • Este imposibil să se detecteze corelații sistematice între orice combinație liniară de biți de intrare și orice combinație liniară de biți hash , sau să prezice care biți hash își vor schimba valoarea atunci când anumiți biți de intrare se schimbă (rezistența la criptoanaliza liniară și criptanaliza diferențială ).

Autorii Whirlpool au adăugat o notă la această declarație:

Aceste afirmații rezultă dintr-o marjă semnificativă de siguranță împotriva tuturor atacurilor cunoscute. Totuși, înțelegem că este imposibil să facem afirmații non-speculative despre lucruri necunoscute.

Criptanaliză

Până în prezent, WHIRLPOOL este rezistent la toate tipurile de criptoanaliza . În cei 8 ani de existență ai Whirlpool, nu a fost înregistrat niciun atac asupra acestuia.

Totuși, în 2009 a fost publicată o nouă metodă de atacare a funcțiilor hash  - The Rebound Attack [2] [3] . Primii „cobai” ai noului atac au fost funcțiile hash Whirlpool și Grøstl . Rezultatele criptoanalizei efectuate sunt prezentate în tabel.

Tabelul 2. Rezultatele criptoanalizei funcțiilor hash Whirlpool și Grøstl folosind metoda Rebound Attack [2] [3]
funcția hash Numărul de runde Complexitate Cantitatea necesară de memorie Tipul de coliziune
Vârtej coliziune
coliziune semiliberă
semi-liber aproape de coliziune
Grøstl-256 coliziune semiliberă

Autorii studiului au folosit următoarele concepte și termeni:

  •  - vector de inițializare
  •  - mesajul care urmează să fie hashing
  •  - functie hash
  • functie de compresie

Tipuri de coliziune :

  • ciocnire :
    •  - fix
  • aproape o coliziune :
    •  - fix
    • un număr mic de bit hash și sunt diferite
  • coliziune semiliberă :
  • coliziune liberă :


După cum se poate observa din tabel, am reușit să generăm o coliziune pentru Whirlpool doar pentru versiunea sa „cut down” de 4,5 runde. În plus, complexitatea calculelor necesare este destul de mare.

Aplicație

Whirlpool este o funcție hash disponibilă gratuit . Prin urmare, este utilizat pe scară largă în software-ul open source . Iată câteva exemple de utilizare a Whirlpool:

  • Jacksum  este un utilitar gratuit pentru sumă de control.
  • Crypto++  este o bibliotecă de clasă C++ distribuită gratuit pentru primitive criptografice.
  • TrueCrypt  este un software gratuit de criptare din mers.
  • FreeOTFE  este un program gratuit și open source proiectat pentru criptare din mers .
  • DarkCrypt  este un utilitar criptografic și steganografic gratuit ca plugin pentru Total Commander

Exemple de hashuri

Pentru comoditate, cei 512 biți (64 de octeți) ai hashului Whirlpool sunt adesea reprezentați ca un număr hexazecimal de 128 de cifre.

După cum sa menționat mai sus, algoritmul a suferit două modificări de la lansarea sa în 2000. Mai jos sunt exemple de hashes calculate din textul ASCII din Vulpea maro rapidă sare peste pangrama câine leneș pentru toate cele trei versiuni de Whirlpool:

Vârtej-0 ("Vulpea maro iute sare peste câinele leneș") = 4F8F5CB531E3D49A61CF417CD133792CCFA501FD8DA53EE368FED20E5FE0248C 3A0B64F98A6533CEE1DA614C3A8DDEC791FF05FEE6D971D57C1348320F4EB42D Whirlpool-T ("Vulpea maro iute sare peste câinele leneș") = 3CCF8252D8BBB258460D9AA999C06EE38E67CB546CFFCF48E91F700F6FC7C183 AC8CC3D3096DD30A35B01F4620A1E3A20D79CD5168544D9E1B7CDF49970E87F1 Vârtej ("Vulpea maro iute sare peste câinele leneș") = B97DE512E91E3828B40D2B0FDCE9CEB3C4A71F9BEA8D88E75C4FA854DF36725F D2B52EB6544EDCACD6F8BEDDFEA403CB55AE31F03AD62A5EF54E42EE82C3FB35

Chiar și o mică modificare a textului original al mesajului (în acest caz, o literă este înlocuită: caracterul „d” este înlocuit cu caracterul „e”) duce la o schimbare completă a hashului :

Whirlpool-0 ("Vulpea maro iute sare peste eog leneș") = 228FBF76B2A93469D4B25929836A12B7D7F2A0803E43DABA0C7FC38BC11C8F2A 9416BBCF8AB8392EB2AB7BCB565A64AC50C26179164B26084A253CAF2E012676 Whirlpool-T ("Vulpea maro iute sare peste eog leneș") = C8C15D2A0E0DE6E6885E8A7D9B8A9139746DA299AD50158F5FA9EECDDEF744F9 1B8B83C617080D77CB4247B1E964C2959C507AB2DB0F1F3BF3E3B299CA00CAE3 Vârtej ("Vulpea maro iute sare peste eog leneș") = C27BA124205F72E6847F3E19834F925CC666D0974167AF915BB462420ED40CC5 0900D85A1F923219D832357750492D5C143011A76988344C2635E69D06F2D38C

Adăugarea de caractere la un șir, concatenarea șirurilor și alte modificări afectează, de asemenea, rezultatul.

Exemple de hash -uri pentru șirul „null”:

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

Exemple de programare

Timp de rulare Codul Rezultat
PHP 5.0 echo hash( 'vârtej', 'test'); b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f 8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6
rubin pune Whirlpool.calc_hex('test') b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f 8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6

Note

  1. 1 2 3 Kyoji, Shibutani; Shirai, Taizo. Pe matricea de difuzie folosită în funcția de hashing Whirlpool  : jurnal . - 2003. - 11 martie.  
  2. 1 2 Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen. The Rebound Attack: Criptanalysis of Reduced Whirlpool și Grøstl  ( 24 februarie 2009). — prezentarea unei noi metode de criptoanaliza și aplicarea acesteia pentru criptoanaliza funcțiilor hash Whirlpool și Grøstl . Preluat la 25 iunie 2019. Arhivat din original la 28 septembrie 2011.
  3. 1 2 Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen. The Rebound Attack: Criptanalysis of Reduced Whirlpool și Grøstl  (engleză) (2009). — un articol despre o nouă metodă de criptoanaliza și aplicarea acesteia pentru criptoanaliza funcțiilor hash Whirlpool și Grøstl . Preluat la 25 iunie 2019. Arhivat din original la 18 noiembrie 2018.

Link -uri

  •  Pagina de pornire Whirlpool . - Pagina principală Whirlpool. Consultat la 25 iunie 2019. Arhivat din original la 29 noiembrie 2017.

Standarde

  •  Standardul ISO/IEC 10118-3 : 2004 . — Standardul ISO/IEC 10118-3:2004. Data accesului: 25 iunie 2019.
  • NESSIE  (engleză) . - engleză.  Noi scheme europene pentru semnături, integritate și criptare , noi proiecte europene privind semnătura digitală, integritate și criptare. Data accesului: 25 iunie 2019.
  •  Portofoliu de primitive criptografice recomandate . — o listă de funcții criptografice NESSIE recomandate pentru utilizare. Data accesului: 25 iunie 2019.

Implementări software

Implementări hardware

  •  Arhitectură eficientă și implementare hardware a funcției hash Whirlpool . - Implementarea hardware eficientă a Whirlpool. Articolul IEEE Transactions on Consumer Electronics . Consultat la 18 noiembrie 2009. Arhivat din original la 29 februarie 2012.
  •  Arhitectura paralelă de mare viteză a funcției Whirlpool Hash . - Arhitectură paralelă de mare viteză Whirlpool. Articol din International Journal of Advanced Science and Technology , numărul 7, iunie 2009. Consultat la 18 noiembrie 2009. Arhivat din original la 29 februarie 2012.