N-hash | |
---|---|
Creată | 1990 |
publicat | 1990 |
Dimensiunea hash | 128 de biți |
Numărul de runde | 12 sau 15 |
Tip de | funcția hash |
N-Hash este o funcție hash criptografică bazată pe funcția ciclică FEAL . Considerat în prezent nesigur [1] .
A fost dezvoltat în 1990 de către Nippon Telegraph and Telephone (care a dezvoltat și FEAL).
Inițial, funcția N-Hash a fost menită să rezolve problema înlocuirii informațiilor pe drumul dintre doi utilizatori de telefonie (Nippon Telegraph și Telephone - o companie de telecomunicații) și să accelereze recuperarea datelor. De exemplu, dacă o persoană trimite un mesaj SMS , atunci înainte de livrare, acesta va fi verificat pentru autenticitate folosind o funcție hash. Și dacă utilizatorul produselor Nippon Telegraph și Telephone trebuie să găsească rapid contactul cuiva pe telefon, atunci utilizarea N-Hash poate simplifica procesul de găsire a unui nume în listă. Acest lucru se datorează faptului că prima literă a contactului este declarată ca un cod hash (o mică parte definitorie a contactului) al numelui.
Algoritmul N-Hash se bazează pe algoritmul de criptare a blocurilor FEAL . Cea mai mare companie de telecomunicații Nippon Telegraph and Telephone a creat FEAL pe baza DES . Dar, deși acest algoritm depășește viteza DES, este foarte nesigur și ușor vulnerabil: un criptoanalist avea nevoie de foarte puține informații pentru a rupe algoritmul. Hackerea algoritmului FEAL a condus la apariția funcției hash N-Hash în 1990. N-Hash este, de asemenea, mai rapid decât DES: în comparație cu 9Kbps de la DES, N-Hash rulează la 24Kbps pentru o schemă cu 15 runde și 29Kbps pentru o schemă cu 12 runde. În același timp, Nippon Telegraph and Telephone a obținut o creștere a fiabilității față de FEAL [1] .
De ceva timp, algoritmul N-Hash a fost folosit de Nippon Telegraph and Telephone în conformitate cu obiectivele acestei funcții, dar după un timp a fost dezvoltată metoda zilei de naștere , care a spart cu ușurință acest algoritm. În legătură cu hack-ul, nu numai N-Hash a fost abandonat, ci aproape toate funcțiile bazate pe cifru bloc, deoarece toate au aceeași problemă: sunt ușor vulnerabile la metoda zilei de naștere. În schimb, acum folosesc funcții mai fiabile bazate pe tehnologii MD: MD5 , SHA-1 și altele enumerate în lista de funcții care sunt considerate în prezent fiabile (conform standardului ISO / IEC 10118).
Funcția N-Hash a fost folosită pentru o perioadă scurtă de timp la începutul anilor 1990 până când a fost spartă prin metoda zilei de naștere.
Definiție: Să fie un mesaj de o oarecare lungime.
O funcție este numită unidirecțională dacă din egalitate
uşor:
foarte intensă de muncă:
O definiție mai ușoară poate fi scrisă astfel:
Unidirecționalitatea este o „ amprentă ”:
Unidirecționalitatea rezolvă o problemă foarte importantă. Să o luăm în considerare cu un exemplu.
Alice și Bob desemnează în mod tradițional subiectele transferului de informații. ExemplePentru a împiedica Alice să folosească metoda „zilelor de naștere” pentru a-l păcăli pe Bob, este foarte convenabil să introduci o condiție și mai puternică decât condiția unidirecțională. H este de așa natură încât este dificil să găsești mesaje și , astfel încât codurile lor hash se potrivesc. Adică, este imposibil să găsești două persoane cu aceleași amprente.
Această condiție se numește rezistență la coliziune și nu este valabilă pentru funcția hash N-Hash.
Din cauza instabilității coliziunii, Alice îl poate păcăli pe Bob în acest fel (metoda „zile de naștere”):
Pentru a evita o astfel de problemă, este suficient să faci modificări cosmetice la contractul semnat. Și deși această acțiune nu modifică în niciun fel funcția hash H și, prin urmare, nu îi afectează în niciun fel rezistența la coliziuni, dar prin această acțiune persoana va primi o nouă versiune a contractului, al cărei cod hash. nu se potrivește cu codul hash al versiunii de contract a atacatorului. Adică dacă Bob în a 5-a linie pune o virgulă undeva, sau pune două puncte în loc de unul, atunci Alice nu va putea dovedi că a semnat un alt contract (din moment ce codul lui hash nu se mai potrivește cu codul hash din contractul lui Alice).
Puteți lua în considerare un exemplu din viața reală: atunci când un notar ștampilă un contract semnat, el face acolo modificări cosmetice.
Pentru a înțelege cum funcționează funcția N-Hash, trebuie să treceți la un discurs mai științific. Mai jos sunt obiectivele acestei funcții, nu prin exemple, ci în funcție de modul în care sunt implementate și cu terminologia adecvată .
Această proprietate este necesară pentru a exclude posibilitatea unui atacator de a injecta unele informații false în mesajul original. Pentru a asigura integritatea, trebuie să fie posibilă detectarea oricăror modificări ale textului mesajului (înlocuire, inserare, ștergere). Integritatea este asigurată prin introducerea de informații redundante în mesajul original, care va fi o combinație de testare. Această combinație se numește sumă de control și poate fi calculată folosind un algoritm special. Deoarece acest algoritm depinde de cheia secretă , este puțin probabil ca informațiile false să fie introduse în mesaj .
, unde sarea este o informație redundantă, M este un mesaj - suma de control;
Din formula rezultă că, dacă sarea se schimbă, atunci se schimbă și S (sumă de control), ceea ce înseamnă că ambele și s-au schimbat .
Adică putem concluziona că au fost adăugate informații false.
Funcția N-Hash funcționează cu M mesaje de lungime arbitrară. În acest caz, rezultatul este un cod hash cu o lungime fixă de 128 de biți. Acest lucru se obține datorită faptului că mesajul este împărțit în blocuri , de 128 de biți, iar algoritmul funcționează secvenţial cu fiecare dintre blocuri.
Această proprietate este valabilă pentru funcțiile unidirecționale, ceea ce este N-Hash. Fiabilitatea mesajului M este verificată prin găsirea codului hash final (rezumatul mesajului) de două ori (părți de trimitere și de primire). Rezultatele sunt comparate și dacă se potrivesc, atunci informațiile sunt de încredere. Integritatea nu garantează valabilitatea .
pe site-urile în care trebuie să introduceți o autentificare și o parolă , parola după introducere este tradusă într-un cod hash. Adică, inițial utilizatorul introduce parola M, dar este folosit un cod hash pentru a intra în zona protejată . Folosind cunoscutul cod hash h și funcția H, este foarte greu de calculat M, ceea ce asigură confidențialitatea parolei.
Autentificarea este procedura de autentificare a unui utilizator sau a datelor folosind anumite criterii.
Se pune întrebarea cum funcția hash asigură veridicitatea autentificării. Acest lucru este ușor de arătat cu un exemplu.
Când un utilizator introduce un nume de utilizator și o parolă pe orice site , parola sa este convertită într-un cod hash și transmisă prin rețea pentru autentificare. Evident, pentru a vă autentifica sub contul altcuiva, este suficient să aflați codul hash al parolei, apoi să folosiți formula (codul h-hash, M - parola) pentru a găsi parola. Dar N-Hash, care este o funcție unidirecțională, asigură siguranța parolei, deoarece această ecuație pentru funcțiile unidirecționale este foarte laborioasă de rezolvat (nu folosind un computer personal).
Algoritmul N-Hash se bazează pe o repetare ciclică (de 12 sau 15 ori - numărul de runde) a operațiilor. Există un cod hash la intrare și poate fi arbitrar, ieșirea este un cod hash h al mesajului M , care trebuie să fie hash. Mărimea codului hash de ieșire este fixă și egală cu 128 de biți, în timp ce dimensiunea M este arbitrară [2] .
Diagrama din dreapta prezintă denumirile schematice ale operațiilor care sunt prezente în diagramele următoare.
Mai jos este un ciclu al algoritmului N-Hash.
Ceva necunoscut rămas se găsește după trecerea printr-o cascadă de opt funcții de transformare. Obținerea acestuia poate fi descrisă astfel:
.
Funcția de transformareSe pune întrebarea cum funcționează funcția de transformare .
Luați în considerare partea superioară a circuitului până la reticule.
Mesajul original este împărțit în blocuri de biți.
Vom considera ieșirile intermediare ca intrări în partea inferioară a circuitului. și sunt alimentate la ieșirile intermediare , în timp ce operațiunile și sunt alimentate la celelalte două ieșiri . Acum este posibil să redenumiți rezultatele la ieșirile intermediare și prin ele, în mod similar cu partea superioară, să găsiți rezultatele la ieșirea părții inferioare, adică întregul circuit în ansamblu.
După ce am făcut toate calculele necesare, obținem că atunci când este aplicat la intrare , mesajul de ieșire poate fi reprezentat ca o concatenare de mesaje
Deoarece funcția f funcționează cu argumente, a căror lungime este de 32 de biți, atunci din schema de căutare a funcției f(x, P) avem:
Argumentele funcției (prima săgeată din stânga) sunt și .
Argumentele funcției (a doua săgeată din stânga) sunt și .
Adică, cele două componente ale mesajului de ieșire sunt deja cunoscute și egale
În plus, vom folosi părțile deja primite ale mesajului la ieșire pentru comoditatea notării:
O funcție hash este sigură atunci când un criptoanalist are nevoie de multe informații pentru a sparge hash-ul (făcându-l puțin probabil să fie spart) și dacă hash-ul nu a fost spart până acum [3] .
Pentru ca o funcție hash să fie sigură, trebuie îndeplinite următoarele condiții:
În caz contrar, o persoană care își introduce numele de utilizator și parola pentru a intra pe Wikipedia ar putea ajunge la pagina altui participant.
Dacă această condiție nu este îndeplinită, atunci face posibilă găsirea parolelor utilizatorilor Wikipedia.
În caz contrar, ar fi posibil să găsiți două parole cu aceleași coduri hash.
N-Hash nu este o funcție sigură, deoarece ultima condiție nu este îndeplinită pentru aceasta.
În prezent, N-Hash este considerată o caracteristică nesigură. Această figură listează toate funcțiile unidirecționale securizate în prezent, conform ISO/IEC 10118 [1] :
Dintre algoritmii construiți ca N-Hash bazați pe cifruri bloc, doar MDC-2 și MDC-4 sunt considerați siguri .
N-Hash este caracterizat de următoarea problemă:
Această figură arată o clasificare a atacurilor asupra tuturor algoritmilor de hashing în general.
Atacurile dependente de algoritm sunt atacuri bazate pe proprietățile unui anumit algoritm.
De exemplu, N-Hash a fost atacat cu succes folosind metoda diferențială , atacul cu punct fix și întâlnirea la mijloc .
Atacurile independente de algoritm pot fi aplicate oricărei funcții hash, dar acest lucru nu exclude faptul că pentru unii algoritmi sunt foarte consumatoare de timp din cauza cantității mari de informații sau a vitezei codului.
Atacuri eficiente asupra N-HashDen Boer a propus o metodă pentru construirea unei coliziuni pentru o schemă N-Hash cu o singură rundă.
Biham și Shamir au folosit cu succes criptoanaliza diferențială pentru a compromite schema N-Hash în 6 runde. Metoda propusă de ei pentru construirea unei coliziuni funcționează pentru orice valoare N care este multiplu de trei și, în același timp, pentru N ≤ 12, se dovedește a fi mai eficientă decât abordarea bazată pe paradoxul zilei de naștere .
Pentru o schemă cu 12 runde, complexitatea construirii coliziunilor prin metoda propusă este estimată la 256 de operații (complexitatea metodei bazate pe paradoxul zilei de naștere este de 264 de operații).
Atacuri independente de algoritmCreșterea lungimii codului hash și a cheii secrete va complica munca criptoanalistului. Puteți încerca să faceți calculele prea consumatoare de timp pentru un computer personal și necesită resurse mari. Apoi, criptoanalistul va trebui fie să caute un supercalculator, fie să scrie un virus care, pe baza paralelizării procesului de spargere a funcției hash, va folosi simultan mai multe computere personale pentru a rezolva problema [3] .
Următoarele metode de protecție a funcției hash [4] sunt, de asemenea, eficiente :
Algoritm | Lungimea valorii hash | Viteza de criptare (KB/sec) |
---|---|---|
Circuit Davies-Meyer simultan (cu IDEA ) | 128 | 22 |
Davies-Meyer (cu DES) | 64 | 9 |
Funcția hash GOST | 256 | unsprezece |
HAVAL (3 seturi) | variabil | 168 |
HAVAL (4 seturi) | variabil | 118 |
HAVAL (5 seturi) | variabil | 98 |
MD2 | 128 | 23 |
MD4 | 128 | 236 |
MD5 | 128 | 174 |
N-Hash (12 etape) | 128 | 29 |
N-Hash (15 etape) | 128 | 24 |
RIPE-MD | 128 | 182 |
SHA-1 | 160 | 75 |
Snefru (4 treceri) | 128 | 48 |
Snefru (8 seturi) | 128 | 23 |
Funcții hash | |
---|---|
scop general | |
Criptografic | |
Funcții de generare a cheilor | |
Numărul de verificare ( comparație ) | |
Hashes |
|