Algoritm securizat Hash

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

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

O iterație în cadrul funcției de compresie SHA-1. A, B, C, D și E sunt cuvinte de stare pe 32 de biți; F este o funcție neliniară care variază; tura stânga n denotă o rotație a bitului stâng cu n locuri; n variază pentru fiecare operație. Plus denotă adaos modulo 2 32 . K t este o constantă.

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:

  1. A = 67452301
  2. B = EFCDAB89
  3. C = 98BADCFE
  4. D = 10325476
  5. 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

O iterație a funcției de compresie în algoritmii familiei 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 și h7 .

Notă

  1. ^ Criptoanaliza SHA-1 (Schneier)
  2. ^ Schneier on Security: NIST Hash Workshop Liveblogging (5)
  3. ^ The H: Știri de securitate și dezvoltări open source
  4. ^ a b Document
  5. ^ Bounce to index.html Arhivat la 5 februarie 2008 la Internet Archive .
  6. ^ Familia de funcții burete Keccak
  7. ^ (RO) Anunțarea primei coliziuni SHA1 pe security.googleblog.com, 23 februarie 2017. Accesat la 17 martie 2017.
  8. ^ (EN) Shattered , pe shattered.it. Adus la 17 martie 2017 .
    "Am rupt SHA-1 în practică." .
  9. ^ Declarație de licențiere pentru brevetul SUA 6829355 .. Adus la 17 februarie 2008 .
  10. ^ Henri Gilbert, Helena Handschuh, Analiza securității SHA-256 și a surorilor , în Lecture notes in computer science , Springer, Berlin, ISSN 0302-9743 ( WC ACNP ) . Adus la 30 ianuarie 2008 (arhivat din original la 18 octombrie 2011) .
  11. ^ Weblog for dkg - HOWTO prep for migration off of SHA-1 in OpenPGP

Bibliografie

Elemente conexe

linkuri externe

Site-uri Internet pentru calcularea hashurilor

Standard: SHA-0, SHA-1, SHA-2, SHA-3 ...

Criptoanaliza

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

Vectorii de testare

Vectorii de testare a proiectului NESSIE pentru SHA-1 , SHA-256 , SHA-384 și SHA-512 .