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.
Funcția hash Whirlpool este numită după Galaxia Whirlpool (M51) din constelația Canis Hounds , prima galaxie cu o structură spirală observabilă.
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.
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ă .
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 .
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:
|
||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
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ă:
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 cheiFuncția de adăugare a cheilor este o adăugare pe biți ( XOR ) a matricelor de stare și cheie :
Constante rotunjiteFiecare 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ă:
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 .
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 .
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:
Mesajul completat este scris ca
și împărțit în blocuri de 512 biți pentru procesare ulterioară.
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”.
Rezumatul mesajului este valoarea de ieșire a funcției de compresie, convertită înapoi într-un șir de 512 biți:
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ă :
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.
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.
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:
Tipuri de coliziune :
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.
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:
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 D2B52EB6544EDCACD6F8BEDDFEA403CB55AE31F03AD62A5EF54E42EE82C3FB35Chiar ș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 0900D85A1F923219D832357750492D5C143011A76988344C2635E69D06F2D38CAdă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 3E83BE698B288FEBCF88E3E03C4F0757EA8964E59B63D93708B138CC42A66EB3Timp de rulare | Codul | Rezultat |
---|---|---|
PHP 5.0 | echo hash( 'vârtej', 'test'); | b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f 8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6 |
rubin | pune Whirlpool.calc_hex('test') | b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f 8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6 |
Funcții hash | |
---|---|
scop general | |
Criptografic | |
Funcții de generare a cheilor | |
Numărul de verificare ( comparație ) | |
Hashes |
|