N-hash

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 14 ianuarie 2015; verificarea necesită 21 de modificări .
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.

Origini

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).

Utilizare

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.

Caracteristicile N-Hash

Unidirecțional

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. Exemple

Rezistența la coliziune

Pentru 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.

Golurile lui N-Hash

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).

Algoritm

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] .

Denumiri de bază

Descrierea algoritmului

Diagrama din dreapta prezintă denumirile schematice ale operațiilor care sunt prezente în diagramele următoare.

Un ciclu N-Hash

Mai jos este un ciclu al algoritmului N-Hash.

  • Introducerea funcției g este codul hash al pasului (i-1)-lea și al i-lea bloc de mesaje . În acest caz , se alege în mod arbitrar: de exemplu, poate fi zero. Și este, de asemenea, alimentat la ieșire pentru operația de adăugare modulo 2, adică rezultatul (codul hash al pasului următor) va arăta astfel: ( ceva necunoscut încă ).
  • Din diagramă se poate observa că este alimentat nu numai la XOR , ci și la ieșirea operației de adăugare modulo 2. Adică, acum, în conformitate cu primul paragraf, rezultatul arată astfel: ( ceva care rămâne necunoscut până acum ).

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 EXG schimbă cifrele înalte și inferioare și adaugă la rezultat , după care rezultatul este adăugat modulo 2 s .
  • După cum se poate vedea din diagramă, rezultatul este transmis secvențial la intrările j funcțiilor de transformare, al doilea argument al căruia este suma , unde j=1, ... , 8.
  • Rezultatul este un cod hash al pasului i :

.

Funcția de transformare

Se 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

  • ;
  • ;
  • ;
  • .
Găsirea funcției f(x, P)

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:

  • Valoarea este împărțită în părți de 8 biți.
  • Să scriem aceste părți ca , i=1,…,4 și să introducem o nouă notație:
    • ;
    • ;
    • ;
    • ;

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:

    • ;
    • ;
  • Apoi mesajul de ieșire poate fi reprezentat ca .
  • Și se știe că
    • =( rotație stânga pe 2 biți )(a+b) mod 256
    • =( Rotire la stânga pe 2 biți )(a+b+1) mod 256

Securitatea funcțiilor hash

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:

  • Odată cu modificări ale textului mesajului (inserții, permutări etc.), și codul hash al mesajului ar trebui să se schimbe;

Î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.

  • Imposibilitatea de a găsi un mesaj printr-un cod hash cunoscut din ;

Dacă această condiție nu este îndeplinită, atunci face posibilă găsirea parolelor utilizatorilor Wikipedia.

  • Sarcina de a găsi mesaje și astfel încât codurile lor hash să fie egale trebuie să consume foarte mult timp.

Î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.

Criptanaliza N-Hash

Î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ă:

  • Deoarece lungimea codului hash este egală cu lungimea blocului algoritmului de criptare, algoritmul este instabil împotriva atacului de naștere .

Atacurile asupra funcțiilor hash

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-Hash Atacurile bazate pe algoritm Metoda diferențială

Den 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 algoritm

Creș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 :

  • utilizarea sumelor de control în diferite etape de hashing;
  • verificarea exactității informațiilor;
  • încorporați informații de tip sare în mesaj .

Rezultate

  • În prezent, N-Hash nu este utilizat pe scară largă, deoarece nu este sigur și a fost spart acum mai bine de 10 ani.
  • Acum există un nume special pentru funcțiile hash, cum ar fi N-Hash - key , adică unidirecțional, dar nu rezistent la coliziuni:
    • Dacă părțile au încredere reciprocă (adică fiecare dintre părți este sigură că cealaltă nu va înlocui contractul, ca în cazul lui Alice și Bob), atunci poate fi folosit N-Hash.

Comparația N-Hash cu alte funcții hash

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

Note

  1. 1 2 3 4 5 Funcții hash (link inaccesibil - istoric ) . Cryptomash. Preluat: 27 noiembrie 2008.   (link inaccesibil)
  2. Bruce Schneier. Capitolul 18. Funcții de hash unidirecțional // Criptografie aplicată . - Ed. a II-a. Arhivat pe 28 februarie 2014 la Wayback Machine
  3. 1 2 Problema principală a criptografiei  // CIO: jurnal. - 17 mai 2005. - Nr 5 . Arhivat din original pe 29 mai 2008.
  4. Criptanaliză a funcțiilor hash (link inaccesibil - istoric ) . Cryptomash. Preluat: 27 noiembrie 2008.   (link inaccesibil)

Vezi și

Link -uri

Literatură

  • A. Şcerbakov, A. Domaşev. Criptografia aplicată. - M . : Ediția Rusă, 2003. - 404 p. — ISBN 5-7502-0215-1 .
  • Bruce Schneier. Criptografia aplicată. - Ed. a II-a. - M . : Triumf, 2002. - 816 p.