Algoritm securizat Hash
Termenul SHA ( acronim al englezului Secure Hash Algorithm ) indică o familie de cinci funcții hash criptografice diferite dezvoltate din 1993 de către Agenția Națională de Securitate (NSA) și publicate de NIST ca standard federal de către guvernul SUA ( FIPS PUB 180-4 ).
Ca orice algoritm hash , SHA produce un rezumat al mesajului cu lungime fixă sau „amprentă a mesajului ” dintr-un mesaj cu lungime variabilă. Siguranța unui algoritm hash constă în faptul că funcția nu este inversabilă (adică nu este posibil să se întoarcă la mesajul original știind doar aceste date) și că nu trebuie să fie niciodată posibilă crearea intenționată a două mesaje diferite cu același digest . Algoritmii familiei sunt denumiți SHA-1 , SHA-224 , SHA-256 , SHA-384 și SHA-512 : ultimele 4 variante sunt adesea denumite generic SHA-2 , pentru a le distinge de prima. Primul produce un rezumat al mesajului de numai 160 de biți , în timp ce ceilalți produc rezumat de lungime în biți egal cu numărul indicat în abrevierea lor (SHA-256 produce un rezumat de 256 de biți). SHA-1 este cel mai răspândit algoritm al familiei SHA și este utilizat în numeroase aplicații și protocoale, deși este acum nesigur și va fi în curând înlocuit cu altele mai moderne și mai eficiente.
Securitatea SHA-1 a fost compromisă de criptanalizatori . [1] Deși atacurile asupra variantelor SHA-2 nu sunt încă cunoscute, acestea au un algoritm similar cu cel al SHA-1, astfel încât sunt în curs eforturi pentru a dezvolta algoritmi de hash alternativi și îmbunătățiți. [2] [3] O competiție deschisă pentru implementarea unei noi funcții SHA-3 a fost anunțată în Registrul federal la 2 noiembrie 2007 [4] de către NIST și printr-o competiție publică , similară cu cea adoptată pentru procesul de dezvoltare a AES , [5] a condus la 2 octombrie 2012 să anunțe algoritmul Keccak drept câștigător. Munca unei echipe de analiști italieni și belgieni, Keccak [6] pare a fi, așadar, destinată să fie inclusă treptat și adoptată în cele mai variate soluții de securitate IT.
Pe 23 februarie 2017, o echipă Google a anunțat prima tehnică practică pentru generarea unei coliziuni hash . [7] [8]
SHA-0 și SHA-1
Specificația algoritmului original a fost publicată în 1993 ca Secure Hash Standard , FIPS PUB 180, de către NIST . Această versiune este adesea denumită SHA-0 pentru a o deosebi de versiunile ulterioare. A fost retras de NSA la scurt timp după publicare și a fost înlocuit de o versiune revizuită, publicată în 1995 (FIPS PUB 180-1) și cunoscută de obicei sub numele de SHA-1 . SHA-1 diferă de SHA-0 numai printr-o rotație cu un singur bit în procesul de pregătire a mesajului cu funcția sa de compresie unidirecțională; acest lucru a fost făcut, conform NSA, pentru a corecta o eroare în algoritmul original, care a redus securitatea criptografică a SHA-0. Cu toate acestea, ANS nu a oferit alte explicații clarificatoare. Au fost raportate ulterior deficiențe atât în codul SHA-0, cât și în codul SHA-1. SHA-1 pare să ofere o rezistență mai mare la atac, susținând afirmația ANS că schimbarea a sporit securitatea.
SHA-1 (precum și SHA-0) produce un rezumat de 160 biți dintr-un mesaj cu o lungime maximă de 2 64 -1 biți și se bazează pe principii similare cu cele utilizate de Ronald L. Rivest de la MIT în proiectarea Algoritmi MD4 și MD5 .
Operațiune
Pasul 1 (Padding): biții „Padding” sunt adăugați la mesajul original, astfel încât lungimea finală a mesajului să fie congruentă cu 448 modulo 512, făcând astfel lungimea bitului „mesaj + padding” împărțită la 512 va da restul 448.
Pasul 2 (Adăugare lungime): Un număr întreg de 64 biți nesemnat care conține lungimea mesajului original este adăugat la secvența de biți (mesaj + umplere) creată la pasul 1. La sfârșitul acestor primii doi pași obținem o secvență de biți care este multiplu de 512.
Pasul 3 (inițializarea bufferului MD): Un buffer de 160 biți împărțit în 5 registre de 32 de biți fiecare este creat pentru stocarea unor pași intermediari. Cele 5 registre vor fi indicate în mod convențional cu (A, B, C, D, E) și inițializate cu următoarele valori hexazecimale:
- A = 67452301
- B = EFCDAB89
- C = 98BADCFE
- D = 10325476
- E = C3D2E1F0
Pasul 4 (Prelucrarea blocurilor de 512 biți): Secvența de biți „mesaj + umplere + lungimea mesajului” este împărțită în blocuri de 512 biți, pe care le vom identifica cu B n cu n variind de la 0 la L. Nucleul algoritmului SHA-1 se numește funcție de compresie și este alcătuită din 4 cicluri de câte 20 de trepte. Buclele au o structură foarte asemănătoare, cu excepția faptului că utilizează o funcție logică primitivă diferită. Fiecare bloc este luat ca parametru de intrare de către toate cele 4 cicluri împreună cu o constantă K și valorile celor 5 registre. La sfârșitul calculului vom obține noi valori pentru A, B, C, D, E pe care le vom folosi pentru calcularea următorului bloc până la blocul final F
Setul SHA-2
În 2001 , NIST a lansat patru funcții de hash suplimentare din familia SHA, fiecare cu un rezumat mai lung decât originalul, denumit în mod colectiv SHA-2 (deși acest termen nu a fost niciodată standardizat oficial). Aceste variante sunt cunoscute, după cum sa menționat, cu lungimea în biți a digestului generat după codul hash oficial: SHA-224 , SHA-256 , SHA-384 și SHA-512 , cu hashuri de 224, respectiv 256, 384 și 512 biți. Trebuie remarcat faptul că ultimii trei algoritmi au fost oficializați ca standard în 2002, în timp ce SHA-224 a fost introdus în februarie 2004 : acesta din urmă are un hash de lungime identică cu cea a 2 chei Triple DES .
Toate aceste variante sunt brevetate de guvernul SUA, dar publicate sub licență gratuită. [9] .
Algoritmii SHA-256 și SHA-512 funcționează, respectiv, cu cuvinte pe 32 și 64 de biți: utilizează un număr diferit de rotații și constante suplimentare, dar structura lor este substanțial identică. Algoritmii SHA-224 și SHA-384 sunt pur și simplu versiuni trunchiate ale celor două precedente, cu hashuri calculate cu valori inițiale diferite.
Algoritmii SHA-2 nu au primit, spre deosebire de SHA-1, multă atenție din partea comunității criptanalitice, astfel încât securitatea lor criptografică nu a fost pe deplin dovedită. Gilbert și Handschuh ( 2003 ) au studiat aceste noi variante și nu au găsit vulnerabilități [10] .
SHA-3
Competiția care a dus la lansarea noului standard SHA-3 a fost lansată oficial pe 2 noiembrie 2007 [4] . La 2 octombrie 2012, NIST a anunțat algoritmul Keccak SHA-3 drept câștigător.
Compararea funcțiilor SHA
Tabelul de mai jos prezintă principalele caracteristici ale algoritmilor familiei SHA ( Starea internă înseamnă suma internă după fiecare compresie a unui bloc de date).
Algoritm e variantă | Dimensiunea de ieșire (biți) | Dimensiunea internă a stării (biți) | Dimensiunea blocului (biți) | Dimensiunea maximă a mesajului (biți) | Dimensiunea cuvântului (biți) | Pași | Operațiuni | Ciocniri găsite | |
---|---|---|---|---|---|---|---|---|---|
SHA-0 | 160 | 160 | 512 | 2 64 - 1 | 32 | 80 | +, și, sau, xor, rotl | Da | |
SHA-1 | 160 | 160 | 512 | 2 64 - 1 | 32 | 80 | +, și, sau, xor, rotl | Atac 2 53 [11] | |
SHA-2 | SHA-256/224 | 256/224 | 256 | 512 | 2 64 - 1 | 32 | 64 | +, și, sau, xor, shr, rotr | Nici unul |
SHA-512/384 | 512/384 | 512 | 1024 | 2 128 - 1 | 64 | 80 | +, și, sau, xor, shr, rotr | Nici unul |
Aplicații
SHA-1 este cel mai utilizat algoritm din familia SHA. Formează baza multor aplicații și protocoale, inclusiv TLS și SSL , PGP , SSH , S / MIME și IPsec . SHA-1 este, de asemenea, utilizat în sistemele de control al versiunilor , cum ar fi Git , pentru a identifica revizuirea software-ului și ca sumă de verificare pentru a verifica integritatea fișierelor mari din cataloagele online.
Algoritmii SHA sunt utilizați și în algoritmi pentru semnarea digitală a documentelor, cum ar fi HMAC , și au fost luate ca bază pentru cifrele bloc SHACAL .
Exemple și pseudocod
Eșantion hash
Acesta este un exemplu de rezumat generat de SHA-1 (toate mesajele sunt codificate în ASCII ):
SHA1 („Cantami o diva pelidei Ahile mânia fatală”) = 1f8a690b7366a2323e2d5b045120da7e93896f47
Chiar și cea mai mică variație a mesajului generează inevitabil un hash complet diferit datorită unei reacții în lanț cunoscută sub numele de efect de avalanșă . De exemplu, înlocuind Cantami
cu Contami
obținem:
SHA1 („C o ntami sau diva pelisului Ahile mânia fatală”) = e5f08d98bf18385e2f26b904cad23c734d530ffb
Rezumatul corespunzător șirului gol este:
SHA1 ("") = da39a3ee5e6b4b0d3255bfef95601890afd80709
Pseudocod al SHA-1
Pseudocodul algoritmului SHA-1:
Note: Toate variabilele sunt nesemnate pe 32 de biți și înfășoară modulul 2 32 atunci când se calculează
Inițializați variabilele:
h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0
Pre-procesare: adăugați bitul „1” la mesaj adăugați k biți '0', unde k este numărul minim ≥ 0 astfel încât mesajul rezultat lungimea (în biți ) este congruentă cu 448 (mod 512) adăugați lungimea mesajului (înainte de pre-procesare), în biți , ca număr întreg big-endian pe 64 de biți
Procesați mesajul în bucăți ulterioare de 512 biți:
rupe mesajul în bucăți de 512 biți
pentru fiecare bucată
divizați bucăți în șaisprezece cuvinte big-endian de 32 de biți w [i], 0 <= i <= 15
Extindeți cele șaisprezece cuvinte pe 32 de biți în optzeci 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]) leftrotate 1
Inițializați valoarea hash pentru acest fragment:
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
f = b xor c xor d
k = 0x6ED9EBA1
altfel dacă 40 ≤ i ≤ 59
f = (b și c) sau (b și d) sau (c și d)
k = 0x8F1BBCDC
altfel dacă 60 ≤ i ≤ 79
f = b xor c xor d
k = 0xCA62C1D6
temp = (a stânga 5) + f + e + k + w [i] e = d d = c c = b stânga 30 b = a a = temp
Adăugați hash-ul acestei bucăți pentru a rezulta până acum:
h0 = h0 + a
h1 = h1 + b
h2 = h2 + c
h3 = h3 + d
h4 = h4 + e
Produce valoarea hash finală (big-endian):
digerați = hash = h0 adăugați h1 adăugați h2 adăugați h3 adăugați h4
Următoarele formule pot fi utilizate pentru a calcula f
în ciclul principal publicat mai sus în locul celor originale publicate în documentul oficial FIPS PUB 180-1:
(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)) (alternative 3) (40 ≤ i ≤ 59): f = (b și c) xor (b și d) xor (c și d) (alternativa 4)
Pseudocod al SHA-256 (o variantă a SHA-2)
Pseudocod al algoritmului SHA-256. Rețineți creșterea amestecării de biți a cuvintelor w[16..63]
comparativ cu SHA-1.
Note: Toate variabilele sunt nesemnate pe 32 de biți și înfășoară modulul 2 32 atunci când se calculează
Inițializați variabilele (primii 32 de biți ai părților fracționare ale rădăcinilor pătrate ale primelor 8 prime 2..19): h0: = 0x6a09e667 h1: = 0xbb67ae85 h2: = 0x3c6ef372 h3: = 0xa54ff53a h4: = 0x510e527f h5: = 0x9b05688c h6: = 0x1f83d9ab h7: = 0x5be0cd19
Inițializați tabelul constantelor rotunde (primii 32 de biți ai părților fracționare ale rădăcinilor cubice ale primelor 64 de primii 2..311): k [0..63]: = 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
Pre-procesare: adăugați bitul „1” la mesaj adăugați k biți '0', unde k este numărul minim> = 0 astfel încât mesajul rezultat lungimea (în biți ) este congruentă cu 448 (mod 512) adăugați lungimea mesajului (înainte de pre-procesare), în biți , ca număr întreg big-endian pe 64 de biți
Procesați mesajul în bucăți ulterioare de 512 biți:
rupe mesajul în bucăți de 512 biți
pentru fiecare bucată
divizați bucăți în șaisprezece cuvinte big-endian de 32 de biți w [0..15]
Extindeți cele șaisprezece cuvinte pe 32 de biți în șaizeci și patru de cuvinte pe 32 de biți:
pentru i de la 16 la 63
s0: = (w [i-15] dreapta 7) xor (w [i-15] dreapta 18) xor (w [i-15] righthift 3)
s1: = (w [i-2] dreapta 17) xor (w [i-2] dreapta 19) xor (w [i-2] righthift 10)
w [i]: = w [i-16] + s0 + w [i-7] + s1
Inițializați valoarea hash pentru acest fragment:
a: = h0
b: = h1
c: = h2
d: = h3
e: = h4
f: = h5
g: = h6
h: = h7
Bucla principală:
pentru i de la 0 la 63
s0: = (a dreapta 2) xor (a dreapta 13) xor (a dreapta 22)
maj: = (a și b) xor (a și c) xor (b și c)
t2: = s0 + maj
s1: = (e dreapta 6) xor (e dreapta 11) xor (e dreapta 25)
ch: = (e și f) xor (( nu e) și g)
t1: = h + s1 + ch + k [i] + w [i]
h: = g g: = f f: = e e: = d + t1 d: = c c: = b b: = a a: = t1 + t2
Adăugați hash-ul acestei bucăți pentru a rezulta până acum:
h0: = h0 + a
h1: = h1 + b
h2: = h2 + c
h3: = h3 + d
h4: = h4 + e
h5: = h5 + f
h6: = h6 + g
h7: = h7 + h
Produce valoarea hash finală (big-endian):
digerați = hash = h0 adăugați h1 adăugați h2 adăugați h3 adăugați h4 adăugați h5 adăugați h6 adăugați h7
Funcțiile ch
și maj
pot fi optimizate așa cum este descris pentru cele ale SHA-1.
SHA-224 este identic cu SHA-256, cu excepția:
- valorile inițiale ale variabilelor
h0
-h7
sunt diferite și - ieșirea este construită omițând
h7
.
SHA-512 are o construcție identică, dar:
- toate numerele au 64 de biți lungime,
- 80 de pași sunt efectuați în loc de 64,
- valorile inițiale și constantele de adăugat sunt extinse la 64 de biți și
- cantitățile de rotații ( rotite ) și deplasări ( schimbări ) sunt diferite.
SHA-384 este identic cu SHA-512, cu excepția:
- valorile inițiale
h0
-h7
sunt diferite și - ieșirea este construită omițând
h6
șih7
.
Notă
- ^ Criptoanaliza SHA-1 (Schneier)
- ^ Schneier on Security: NIST Hash Workshop Liveblogging (5)
- ^ The H: Știri de securitate și dezvoltări open source
- ^ a b Document
- ^ Bounce to index.html Arhivat la 5 februarie 2008 la Internet Archive .
- ^ Familia de funcții burete Keccak
- ^ (RO) Anunțarea primei coliziuni SHA1 pe security.googleblog.com, 23 februarie 2017. Accesat la 17 martie 2017.
- ^ (EN) Shattered , pe shattered.it. Adus la 17 martie 2017 .
"Am rupt SHA-1 în practică." . - ^ Declarație de licențiere pentru brevetul SUA 6829355 .. Adus la 17 februarie 2008 .
- ^ Henri Gilbert, Helena Handschuh, Analiza securității SHA-256 și a surorilor , în Lecture notes in computer science , Springer, Berlin, ISSN 0302-9743 . Adus la 30 ianuarie 2008 (arhivat din original la 18 octombrie 2011) .
- ^ Weblog for dkg - HOWTO prep for migration off of SHA-1 in OpenPGP
Bibliografie
- Florent Chabaud, Antoine Joux: ciocniri diferențiale în SHA-0. CRYPTO 1998. pp56–71
- Eli Biham , Rafi Chen, Near-Collisions of SHA-0, Cryptology ePrint Archive, Raport 2004/146, 2004 (apărut pe CRYPTO 2004) [1]
- Joux, Carribault, Lemuet, Jalby: Coliziune pentru algoritmul SHA-0 complet, CRYPTO 2004 [2]
- Xiaoyun Wang , Hongbo Yu și Yiqun Lisa Yin, Atacuri eficiente de căutare a coliziunilor pe SHA-0, CRYPTO 2005 [3]
- Xiaoyun Wang , Yiqun Lisa Yin și Hongbo Yu, Găsirea coliziilor în SHA-1 complet, CRYPTO 2005 [4]
- Henri Gilbert , Helena Handschuh : Analiza securității SHA-256 și a surorilor. Zone selectate în criptografie 2003: pp175–193
- Propunerea de revizuire a standardului federal de procesare a informațiilor (FIPS) 180, standard securizat Hash [ link rupt ] , în Registrul federal , vol. 59, nr. 131, 11 iulie 1994, pp. 35317-35318. Adus 26/04/2007 .
Elemente conexe
linkuri externe
Site-uri Internet pentru calcularea hashurilor
- Haideți-le pe toate! - Hashing online de text și fișiere cu diverși algoritmi
- Web4Human -Hashing online cu algoritmi SHA1, SHA224, SHA256 și SHA512
- https://web.archive.org/web/20071216092901/http://www.johnmaguire.us/tools/hashcalc/index.php - Permite codificarea șirurilor de lungime zero
- Căutare SHA-1 - Baza de date cu câteva milioane de hash-uri SHA-1. Implementat ca o căutare inversă online.
- Calculator hash simplu , la hash.spugesoft.com . Adus pe 5 mai 2019. Arhivat din original la 28 iunie 2012 .
- SHA-1 Linie fișier text pe linie - Permite sha1-hash fiecare linie a unui fișier text.
Standard: SHA-0, SHA-1, SHA-2, SHA-3 ...
- Specificații pentru un standard securizat Hash (SHS) - Proiect pentru standardul SHS propus (SHA-0)
- Secure Hash Standard (SHS) - Standard SHS propus (SHA-0)
- RFC 3174 , „US Secure Hash Algorithm 1 (SHA-1)”
- RFC 4634 , „Algoritmi Hash securizați din SUA (SHA și HMAC-SHA)”
- CSRC Cryptographic Toolkit - Site oficial NIST pentru Secure Hash Standard
- FIPS 180-2: Secure Hash Standard (SHS) ( PDF , 236 kB) - Versiunea actuală a Secure Hash Standard (SHA-1, SHA-224, SHA-256, SHA-384 și SHA-512), 1 august 2002, modificat la 25 februarie 2004
- NIST securizat Hashing Pagină despre algoritmii NIST Hashing
- Competiția NIST Cryptographic Hash Project SHA-3
Criptoanaliza
- Interviu cu Yiqun Lisa Yin despre atacul SHA-1 , la news.zdnet.com . Adus la 30 ianuarie 2008 (arhivat din original la 16 decembrie 2007) .
- Rezumatul impactului Lenstra al rezultatelor criptanalitice din februarie 2005 ( PDF ), la cm.bell-labs.com . Adus la 30 ianuarie 2008 (arhivat din original la 28 februarie 2008) .
- Explicația atacurilor cu succes asupra SHA-1 (3 pagini, 2006)
Implementări
- Proiectul OpenSSL - Biblioteca extinsă OpenSSL include software gratuit și open source cu implementarea SHA-1, SHA-224, SHA-256, SHA-384 și SHA-512
- Crypto ++ Crypto ++, bibliotecă gratuită C ++ cu scheme criptografice
- Bouncy Castle Biblioteca Bouncy Castle este o bibliotecă gratuită Java și C # care conține implementări SHA-1, SHA-224, SHA-256, SHA-384 și SHA-512 și alți algoritmi hash.
Tutoriale și exemple de coduri
- Comparația funcției SHA în diferite limbi
- Implementări C și C ++ ale SHA-1, inclusiv binarele Win32 și Linux de Paul E. Jones (co-autor RFC)
- Implementarea C a lui Brian Gladman a SHA
- Implementarea Visual Basic a SHA-1 a lui John Taylor
- Implementarea JavaScript a lui Chris Veness a SHA-1
- Implementarea JavaScript a funcțiilor HASH (md4, md5, sha-1, sha-2) , pe cryptojs.altervista.org .
Vectorii de testare
Vectorii de testare a proiectului NESSIE pentru SHA-1 , SHA-256 , SHA-384 și SHA-512 .