SHA-1

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 29 octombrie 2020; verificările necesită 12 modificări .
SHA-1
Dezvoltatori NSA cu NIST
Creată 1995
publicat 1995
Predecesor SHA-0
Succesor SHA-2
Dimensiunea hash 160 de biți
Numărul de runde 80
Tip de funcția hash

Secure Hash Algorithm 1 este un  algoritm de hashing criptografic . Descris în RFC 3174 . Pentru un mesaj de intrare de lungime arbitrară ( biți maxim, care este aproximativ egal cu 2 exaocteți ), algoritmul generează o valoare hash de 160 de biți (20 de octeți), numită și rezumatul mesajului , care este de obicei afișată ca un hexazecimal de 40 de cifre. număr. Folosit în multe aplicații și protocoale criptografice. De asemenea, recomandat ca principal pentru agențiile guvernamentale din SUA . Principiile din spatele SHA-1 sunt similare cu cele folosite de Ronald Rivest la proiectarea MD4 .

Istorie

În 1993, NSA a colaborat cu NIST pentru a dezvolta algoritmul Secure Hash (cunoscut acum ca SHA-0) (publicat în FIPS PUB 180) pentru un standard de hashing securizat. Cu toate acestea, NSA a retras în curând această versiune, invocând o eroare pe care au descoperit-o și care nu a fost niciodată dezvăluită. Și l-a înlocuit cu o versiune revizuită publicată în 1995 în FIPS PUB 180-1. Această versiune este considerată ceea ce se numește SHA-1. Mai târziu, la conferința CRYPTO din 1998 , doi cercetători francezi au prezentat un atac asupra algoritmului SHA-0 care nu a funcționat pe algoritmul SHA-1. Este posibil să fi fost o eroare descoperită de NSA .

Descrierea algoritmului

SHA-1 implementează o funcție hash , construită pe ideea unei funcții de compresie. Intrările în funcția de compresie sunt un bloc de mesaje de 512 biți și ieșirea blocului de mesaje anterior. Ieșirea este valoarea tuturor blocurilor hash până în acel moment. Cu alte cuvinte, blocul hash este . Valoarea hash a întregului mesaj este rezultatul ultimului bloc.

Inițializare

Mesajul original este împărțit în blocuri de 512 biți fiecare. Ultimul bloc este completat la un multiplu de lungime de 512 biți. Mai întâi, se adaugă 1 (biți), apoi se adaugă zerouri, astfel încât lungimea blocului să devină 512 - 64 = 448 biți. Restul de 64 de biți conțin lungimea mesajului original în biți (în format big-endian ). Dacă ultimul bloc are o lungime mai mare de 447 dar mai mică de 512 biți, atunci umplutura se realizează astfel: mai întâi se adaugă 1 (bit), apoi se adaugă zerouri până la sfârșitul blocului de 512 biți; după aceea, se creează un alt bloc de 512 de biți, care este umplut până la 448 de biți cu zerouri, după care lungimea mesajului original în biți (în format big-endian) este scrisă pe cei 64 de biți rămași. Ultimul bloc este întotdeauna completat, chiar dacă mesajul are deja lungimea necesară.

Sunt inițializate cinci variabile pe 32 de biți.

A=0x67452301 B=0xEFCDAB89 C=0x98BADCFE D=0x10325476 E=0xC3D2E1F0

Sunt definite patru operații neliniare și patru constante.

= 0x5A827999 0≤t≤19
= 0x6ED9EBA1 20≤t≤39
= 0x8F1BBCDC 40≤t≤59
= 0xCA62C1D6 60≤t≤79

Bucla principală

Bucla principală procesează în mod iterativ fiecare bloc de 512 biți. La începutul fiecărei bucle sunt introduse variabilele a, b, c, d, e, care sunt inițializate cu valorile A, B, C, D, E, respectiv. Blocul de mesaje este convertit de la 16 cuvinte de 32 de biți la 80 de cuvinte de 32 de biți conform următoarei reguli:

pentru 0≤t≤15 = ( -3 -8 -14 -16 ) << 1 pentru 16≤t≤79

, unde „<<” este o deplasare circulară spre stânga.

pentru 0 până la 79 temp = (a<<5) + ( b,c,d) + e + e = d d = c c = b<<30 b = a





a = temp

, unde „+” este adăugarea de numere întregi pe 32 de biți fără semn cu excesul (al 33-lea bit) eliminat.

După aceea, valorile a, b, c, d, e sunt adăugate la A, B, C, D, respectiv E. Începe următoarea iterație.

Valoarea finală va fi concatenarea a cinci cuvinte de 32 de biți (A, B, C, D, E) într-o valoare hash de 160 de biți.

Pseudocod SHA-1

Pseudocodul pentru algoritmul SHA-1 este următorul:


Notă: Toate variabilele utilizate sunt de 32 de biți. Inițializare variabilă: h0 = 0x67452301 h1 = 0xEFCDAB89 h2 = 0x98BADCFE h3 = 0x10325476 h4 = 0xC3D2E1F0 Prelucrare preliminară: Atașați bitul „1” la mesaj Adăugați k biți „0”, unde k este cel mai mic număr ≥ 0, astfel încât lungimea mesajului rezultat (în biți) modulo 512 este comparabil cu 448 (lungimea mod 512 == 448) Adăugați lungimea mesajului original (înainte de preprocesare) ca un întreg pe 64 de biți Număr big-endian , în biți . În acest proces, mesajul este împărțit secvențial pe 512 biți: pentru iterare peste toate aceste părți împărțim această piesă în 16 părți, cuvinte de 32 de biți (big-endian) w[i], 0 <= i <= 15 16 cuvinte pe 32 de biți sunt completate la 80 de cuvinte pe 32 de biți: pentru i de la 16 la 79 w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) rotiți la stânga 1 Inițializarea valorilor hash ale acestei părți: a = h0 b = h1 c = h2 d = h3 e=h4 Bucla principală: pentru i de la 0 la 79 dacă 0 ≤ i ≤ 19 atunci f = (b și c) sau (( nu b) și d) k = 0x5A827999 altfel, dacă 20 ≤ i ≤ 39 atunci f = b xor c xor d k = 0x6ED9EBA1 altfel, dacă 40 ≤ i ≤ 59 atunci f = (b și c) sau (b și d) sau (c și d) k = 0x8F1BBCDC altfel, dacă 60 ≤ i ≤ 79 atunci f = b xor c xor d k = 0xCA62C1D6 temp = (a rotire la stânga 5) + f + e + k + w[i] e=d d=c c = b rotire la stânga 30 b = a a = temp Adăugați valoarea hash a acestei părți la rezultat: h0 = h0 + a h1 = h1 + b h2 = h2 + c h3 = h3 + d h4 = h4 + e Valoarea hash finală (h0, h1, h2, h3, h4 trebuie convertită în big-endian): digest = hash = h0 adăugați h1 adăugați h2 adăugați h3 adăugați h4

În loc de formularea originală a FIPS PUB 180-1, sunt date următoarele expresii echivalente și pot fi folosite pe un computer fîn bucla principală:

(0 ≤ i ≤ 19): f = d xor (b și (c xor d)) (alternativa 1) (0 ≤ i ≤ 19): f = (b și c) xor (( nu b) și d) ( alternativa 2) (0 ≤ i ≤ 19): f = (b și c) + (( nu b) și d) (alternativa 3)   (40 ≤ i ≤ 59): f = (b și c) sau (d și (b sau c)) (alternativa 1) (40 ≤ i ≤ 59): f = (b și c) sau (d și (b) xor c)) (alternativa 2) (40 ≤ i ≤ 59): f = (b și c) + (d și (b xor c)) (alternativa 3) (40 ≤ i ≤ 59): f = (b și c) xor (b și d) xor (c și d) (alternativa 4)

Exemple

Următoarele sunt exemple de hash-uri SHA-1. Se presupune că toate mesajele utilizează codificarea UTF-8 .

Hash pangram în rusă:

SHA-1 ("Ar fi citrice în desișurile din sud? Da, dar una falsă!") = 9e32295f 8225803b b6d5fdfc c0674616 a4413c1b

Hash pangram în engleză:

SHA-1 (" Vulpea maro iute sare peste câinele leneș ") = 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12 SHA-1(„sha”) = d8f45903 20e1343a 915b6394 170650a8 f35d6926

O mică modificare a textului sursă (o literă cu majuscule) duce la o schimbare mare a hash-ului în sine. Acest lucru se datorează efectului de avalanșă .

SHA-1(„sha”) = ba79baeb 9f10896a 46ae7471 5271b7f5 86e74640

Chiar și pentru un șir gol, se calculează o valoare hash non-trivială.

SHA-1("") = da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709

Criptanaliză

Criptanaliza funcțiilor hash are ca scop studierea vulnerabilității la diferite tipuri de atacuri. Principalele sunt:

Când rezolvați prin metoda „forței brute” :

Securitatea semnăturii digitale electronice care utilizează acest algoritm hash depinde de stabilitatea funcției de hash pentru a găsi coliziuni . Rezistența înainte de imagine depinde de securitatea stocării hash-urilor parolelor în scopuri de autentificare .

În ianuarie 2005, Vincent Rayman și Elisabeth Oswald au publicat un atac asupra unei versiuni trunchiate a SHA-1 (53 de runde în loc de 80 ), care permite găsirea coliziunilor în mai puțin de 280 de operațiuni.

În februarie 2005, Xiaoyun Wang , Yiqun Lisa Yin și Hongbo Yu au prezentat un atac asupra SHA-1 complet care necesită mai puțin de 269 de operațiuni.

Despre metodă, autorii scriu:

Prezentăm un set de strategii și tehnici aferente care pot fi utilizate pentru a depăși unele obstacole importante în găsirea coliziunilor în SHA-1. Căutăm mai întâi căi diferențiale de aproape coliziune care au o mică „greutate Hamming” în „vectorul de zgomot” unde fiecare bit reprezintă o coliziune locală în 6 pași. Apoi ajustăm calea diferențială de la prima etapă la o altă cale diferențială acceptabilă în consecință pentru a evita coliziunile în serie și trunchiate inacceptabile. În cele din urmă, convertim două căi diferențiale de aproape coliziune de un bloc într-o cale de coliziune de două blocuri cu o complexitate de calcul de două ori mai mare. [unu]

Text original  (engleză)[ arataascunde]

Introducem un set de strategii și tehnici corespunzătoare care pot fi utilizate pentru a elimina unele obstacole majore în căutarea coliziunilor pentru SHA-1. În primul rând, căutăm o cale diferențială aproape de coliziune care are o greutate Hamming scăzută în „vectorul de perturbare” unde fiecare 1 bit reprezintă o coliziune locală în 6 pași. În al doilea rând, ajustăm în mod adecvat calea diferențială în prima rundă la o altă cale diferențială posibilă, astfel încât să evităm coliziunile locale consecutive imposibile și coliziunile locale trunchiate. În al treilea rând, transformăm două căi diferențiale de aproape coliziune cu un singur bloc într-o cale diferențială de coliziune cu două blocuri cu o complexitate de căutare de două ori mai mare.

Ele mai precizează:

În special, analiza noastră se bazează pe atacul diferențial original asupra SHA-0, atacul „aproape de coliziune” asupra SHA-0, tehnica multi-bloc și tehnica originală de modificare a mesajului utilizată în atacurile de căutare de coliziuni pe HAVAL - 128, MD4 , RIPEMD și MD5 .

Text original  (engleză)[ arataascunde]

În special, analiza noastră se bazează pe atacul diferențial inițial asupra SHA-0, atacul de aproape coliziune asupra SHA-0, tehnicile de coliziune multi-bloc, precum și tehnicile de modificare a mesajelor utilizate în atacurile de căutare de coliziuni pe HAVAL-128. , MD4, RIPEMD și MD5.

Un articol care descrie algoritmul a fost publicat în august 2005 la conferința CRYPTO .

În același articol, autorii au publicat un atac asupra SHA-1 trunchiat (58 de runde), care permite găsirea coliziunilor în 233 de operațiuni.

În august 2005, la CRYPTO 2005, aceiași experți au prezentat o versiune îmbunătățită a atacului asupra SHA-1 cu drepturi depline, cu o complexitate de calcul de 263 de operațiuni. În decembrie 2007, detaliile acestei îmbunătățiri au fost revizuite de Martin Cochran.

Christophe de Kanier și Christian Rechberg au prezentat mai târziu un atac îmbunătățit asupra SHA-1, pentru care au fost premiați cu cea mai bună lucrare la conferința ASIACRYPT din 2006 . Ei au prezentat o coliziune cu două blocuri pe un algoritm de 64 de runde cu o complexitate de calcul de aproximativ 235 de operații. [2]

Există un proiect de cercetare la scară largă care a început la Universitatea de Tehnologie din orașul austriac Graz , care: „... folosește computere conectate prin Internet pentru a efectua cercetări în domeniul criptoanalizei. Puteți participa la proiect descărcând și rulând programul gratuit pe computer.” [3]

Burt Kalinske , șeful de cercetare la „ laboratorul RSA ”, prezice că primul atac preimagine va avea succes în următorii 5 până la 10 ani.

Deoarece atacurile teoretice asupra SHA-1 au avut succes, NIST intenționează să elimine treptat utilizarea SHA-1 în semnăturile digitale. [patru]

Datorită blocului și structurii iterative a algoritmilor, precum și a lipsei de procesare specială la sfârșitul hash-ului, toate funcțiile hash ale familiei SHA sunt vulnerabile la atacuri de lungire a mesajelor și coliziuni atunci când hash parțial un mesaj. [5] Aceste atacuri permit falsificarea mesajelor semnate doar cu hash - sau  - prin prelungirea mesajului și recalcularea hash-ului fără a cunoaște valoarea cheii. Cea mai simplă soluție pentru a proteja împotriva acestor atacuri este dublarea hashului - (  este un bloc de zerouri de aceeași lungime ca și blocul de funcție hash).

Pe 2 noiembrie 2007, NIST a anunțat o competiție pentru dezvoltarea unui nou algoritm SHA-3 care a funcționat până în 2012 . [6]

SHappening

La 8 octombrie 2015, Marc Stevens, Pierre Karpman și Thomas Peyrin au publicat un atac asupra funcției de compresie a algoritmului SHA-1 care necesită doar 257 de calcule .

Hack real: SHAttered (detecție coliziuni)

Pe 23 februarie 2017, specialiștii de la Google și CWI au anunțat un hack practic al algoritmului prin publicarea a 2 fișiere PDF cu aceeași sumă de control SHA-1 . Acest lucru a necesitat o căutare de opțiuni, care ar dura 110 ani pentru 1 GPU [7] .

Comparația lui SHA-1 cu alți algoritmi

Comparație cu MD5

Atât MD5 , cât și SHA-1 sunt în esență extensii îmbunătățite ale MD4 .

Asemănări:

  1. Patru etape.
  2. Fiecare acțiune se adaugă la rezultatul obținut anterior.
  3. Dimensiunea blocului de procesare este de 512 biți.
  4. Ambii algoritmi efectuează adăugare modulo 2 32 și sunt proiectați pentru arhitectura pe 32 de biți.

Diferențe:

  1. În SHA-1, aceeași funcție f este utilizată în a patra etapă ca și în a doua etapă.
  2. În MD5 , fiecare acțiune folosește o constantă incrementală unică. În SHA-1, constantele sunt reutilizate pentru fiecare dintre cele patru grupuri.
  3. O a cincea variabilă a fost adăugată la SHA-1.
  4. SHA-1 utilizează un cod ciclic de corectare a erorilor.
  5. În MD5 , cele patru offset-uri utilizate în fiecare pas sunt diferite de valorile utilizate în pașii anteriori. În SHA , o valoare constantă a deplasării este utilizată în fiecare etapă.
  6. În MD5  există patru funcții logice elementare diferite, în SHA-1 sunt trei.
  7. În MD5 , lungimea rezumatului este de 128 de biți, în SHA-1 este de 160 de biți.
  8. SHA-1 conține mai multe runde (80 în loc de 64) și rulează pe un buffer de 160 de biți în comparație cu tamponul de 128 de biți al MD5 . Deci, SHA-1 ar trebui să ruleze cu aproximativ 25% mai lent decât MD5 pe același hardware.

Bruce Schneier concluzionează: „SHA-1 este MD4 cu adăugarea unei turnări extinse, un pas suplimentar și avalanșă îmbunătățită. MD5  este MD4 cu bit hashing îmbunătățit, un pas suplimentar și avalanșă îmbunătățită.”

Comparație cu GOST R 34.11-94

O serie de caracteristici distinctive ale GOST R 34.11-94 :

  1. La procesarea blocurilor, transformările sunt utilizate conform algoritmului GOST 28147-89 ;
  2. Este procesat un bloc de 256 de biți, iar valoarea de ieșire este de asemenea de 256 de biți.
  3. Se aplică măsuri de căutare anti-coliziune bazate pe caracterul incomplet al ultimului bloc.
  4. Blocurile sunt procesate conform algoritmului de criptare GOST 28147-89 , care conține transformări pe cutiile S , ceea ce complică în mod semnificativ aplicarea metodei de criptoanaliza diferențială la căutarea coliziunilor algoritmului GOST R 34.11-94 . Acesta este un plus semnificativ în comparație cu SHA-1.
  5. Securitatea teoretică a GOST R 34.11-94 este 2128 , care este de multe ori mai mare decât 280 pentru SHA-1.

Comparație cu alte SHA -uri

În tabel, „dimensiunea hash intermediară” înseamnă „dimensiunea sumei hash internă” după fiecare iterație.

Variații de algoritm Dimensiunea hash de ieșire (biți) Dimensiunea hash intermediară (biți) Dimensiunea blocului (biți) Lungimea maximă a mesajului de intrare (biți) Dimensiunea cuvântului (biți) Numărul de runde Operații utilizate S-au găsit coliziuni
SHA-0 160 160 512 2 64 - 1 32 80 +, și, sau, xor, rotl Există
SHA-1 160 160 512 2 64 - 1 32 80 +, și, sau, xor, rotl 2 52 operaţii
SHA-2 SHA-256/224 256/224 256 512 2 64 - 1 32 64 +, și, sau, xor, shr, rotr Nu
SHA-512/384 512/384 512 1024 2 128 - 1 64 80 +, și, sau, xor, shr, rotr Nu

Utilizare

Funcțiile hash sunt utilizate în sistemele de control al versiunilor, sistemele de semnătură electronică și pentru crearea codurilor de autentificare .

SHA-1 este cel mai comun din întreaga SHA și este utilizat într-o varietate de aplicații și algoritmi criptografici utilizați pe scară largă.

SHA-1 este utilizat în următoarele aplicații:

  • S/MIME  - rezumate de mesaje.
  • SSL  - rezumate de mesaje.
  • IPSec  - pentru algoritmul de verificare a integrității într-o conexiune punct la punct.
  • SSH  - pentru a verifica integritatea datelor transferate.
  • PGP  - pentru crearea unei semnături digitale electronice.
  • Git  - pentru a identifica fiecare obiect prin hash SHA-1 din informațiile stocate în obiect.
  • Mercurial  - pentru a identifica revizuirile
  • BitTorrent  - pentru a verifica integritatea datelor descărcate.

SHA-1 este baza cifrului bloc SHACAL .

Disclaimer

Google și- a exprimat de multă vreme neîncrederea față de SHA-1, în special pentru utilizarea acestei funcții pentru a semna certificate TLS . În 2014, la scurt timp după publicarea lucrării lui Mark Stevens, echipa de dezvoltare Chrome a anunțat că elimina treptat SHA-1.

Din 25 aprilie 2016 Yandex . Mail a încetat să mai accepte mailerii mai vechi care utilizează SHA-1 [8] .

Note

  1. ↑ Finding Collisions in the Full SHA-1  (engleză)  (downlink) . — Un articol al cercetătorilor chinezi despre hack-ul SHA-1. Arhivat din original pe 23 august 2011.
  2. ↑ Găsirea caracteristicilor SHA-1 : rezultate generale și aplicații  . Preluat la 4 octombrie 2017. Arhivat din original la 26 iulie 2008.
  3. ↑ SHA-1 Collision Search Graz  (engleză)  (link nu este disponibil) . — Proiect de cercetare al Universității de Tehnologie din Graz. Arhivat din original pe 7 noiembrie 2008.
  4. ↑ Comentarii NIST privind atacurile criptonalitice pe SHA-1  (  link inaccesibil) . — Comentariu oficial NIST privind atacurile SHA-1. Arhivat din original pe 13 octombrie 2012.
  5. ↑ Niels Ferguson, Bruce Schneier și Tadayoshi Kohno, Cryptography Engineering  (engleză)  (link nu este disponibil) . Arhivat din original pe 13 octombrie 2012. , John Wiley & Sons, 2010. ISBN 978-0-470-47424-2
  6. ↑ NIST Hash Competition  (engleză)  (link nu este disponibil) . — Concurență pentru dezvoltarea SHA-3. Arhivat din original pe 13 octombrie 2012.
  7. ↑ Prima modalitate de a genera coliziuni pentru SHA-1 . Preluat la 9 martie 2017. Arhivat din original la 10 martie 2017.
  8. ↑ Actualizarea programelor de e-mail - Mail - Yandex.Help . yandex.ru. Consultat la 7 aprilie 2016. Arhivat din original pe 20 aprilie 2016.

Literatură

  • Schneier B. Criptografia aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumph, 2002. - 816 p. - 3000 de exemplare.  - ISBN 5-89392-055-4 .
  • Nils Ferguson , Bruce Schneier . Practical Cryptography = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. - M .  : Dialectică, 2004. - 432 p. - 3000 de exemplare.  — ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .

Link -uri

 Funcții hash
scop general
Criptografic
Funcții de generare a cheilor
Numărul de verificare ( comparație )
Hashes