Algorisme Hash segur

De la Viquipèdia, l'enciclopèdia lliure.
Saltar a la navegació Saltar a la cerca

El terme SHA ( acrònim de l’ anglès Secure Hash Algorithm ) indica una família de cinc funcions de hash criptogràfiques diferents desenvolupades des de 1993 per la National Security Agency (NSA) i publicades per NIST com a estàndard federal pel govern dels Estats Units ( FIPS PUB 180-4 ).

Com qualsevol algorisme de hash , SHA produeix un resum de missatges de longitud fixa, o "petjada de missatge ", a partir d'un missatge de longitud variable. La seguretat d’un algorisme de hash rau en el fet que la funció no és invertible (és a dir, no és possible tornar al missatge original sabent només aquestes dades) i que mai no s’ha de poder crear intencionadament dos missatges diferents amb el mateix resum . Els algoritmes de la família s’anomenen SHA-1 , SHA-224 , SHA-256 , SHA-384 i SHA-512 : les darreres 4 variants se solen anomenar genèricament SHA-2 , per distingir-les de la primera. El primer produeix un resum del missatge de només 160 bits , mentre que els altres produeixen un resum de longitud en bits igual al nombre indicat a la seva abreviatura (SHA-256 produeix un resum de 256 bits). SHA-1 és l'algorisme més estès de la família SHA i s'utilitza en nombroses aplicacions i protocols tot i ser ara insegur i aviat serà substituït per altres més moderns i eficients.

La seguretat de SHA-1 ha estat compromesa per criptanalistes . [1] Tot i que encara no es coneixen els atacs a variants SHA-2, tenen un algorisme similar al de SHA-1, de manera que s'estan realitzant esforços per desenvolupar algoritmes de hash alternatius i millorats. [2] [3] Un concurs obert per a la implementació d'una nova funció SHA-3 va ser anunciat al Registre Federal el 2 de novembre de 2007 [4] per NIST i mitjançant una competència pública , similar a la adoptada per al procés de desenvolupament de l' AES , [5] va portar el 2 d'octubre de 2012 a anunciar l'algorisme Keccak com a guanyador. El treball d'un equip d'analistes italians i belgues, Keccak [6] , sembla, doncs, destinat a ser inclòs gradualment i adoptat en les més variades solucions de seguretat informàtica.

El 23 de febrer de 2017, un equip de Google va anunciar la primera tècnica pràctica per generar una col·lisió de hash . [7] [8]

SHA-0 i SHA-1

Una iteració dins de la funció de compressió SHA-1. A, B, C, D i E són paraules d’estat de 32 bits; F és una funció no lineal que varia; desviació a l'esquerra n indica una rotació del bit esquerre per n llocs; n varia per a cada operació. Addició denota addició mòdul 2 32 . K t és una constant.

L'especificació d'algoritme original es va publicar el 1993 com a Secure Hash Standard , FIPS PUB 180, per NIST . Aquesta versió se sol anomenar SHA-0 per distingir-la de versions posteriors. Va ser retirada per la NSA poc després de la publicació i va ser suplantada per una versió revisada, publicada el 1995 (FIPS PUB 180-1) i coneguda normalment com SHA-1 . SHA-1 es diferencia de SHA-0 només per una rotació de bit únic en el procés de preparació de missatges de la seva funció de compressió unidireccional; això es va fer, segons la NSA, per corregir un defecte en l'algoritme original, que reduïa la seguretat criptogràfica de SHA-0. No obstant això, la NSA no va proporcionar cap altra explicació aclaridora. Posteriorment es van informar de les debilitats tant del codi SHA-0 com del SHA-1. SHA-1 sembla oferir una major resistència a l'atac, donant suport a l'afirmació de la NSA que el canvi augmentava la seguretat.

SHA-1 (així com SHA-0) produeix un resum de 160 bits a partir d’un missatge amb una longitud màxima de 2 64 -1 bits i es basa en principis similars als utilitzats per Ronald L. Rivest del MIT en el disseny del Algoritmes MD4 i MD5 .

Operació

Pas 1 (farciment): els bits de "farcit" s'afegeixen al missatge original de manera que la longitud final del missatge sigui congruent amb 448 mòdul 512, de manera que, si es fa la longitud de bits de "missatge + farcit" dividida per 512, es restarà 448.

Pas 2 (Afegir longitud): a la seqüència de bits (missatge + farciment) creada al pas 1 s’afegeix un nombre enter de 64 bits sense signar que conté la longitud del missatge original. Al final d’aquests dos primers passos obtenim una seqüència de bits que és múltiple de 512.

Pas 3 (inicialització del buffer MD): es crea un buffer de 160 bits dividit en 5 registres de 32 bits cadascun per emmagatzemar alguns passos intermedis. Els cinc registres s’indicaran convencionalment amb (A, B, C, D, E) i s’inicialitzaran amb els següents valors hexadecimals:

  1. A = 67452301
  2. B = EFCDAB89
  3. C = 98BADCFE
  4. D = 10325476
  5. E = C3D2E1F0

Pas 4 (Processament dels blocs de 512 bits): la seqüència de bits "missatge + farcit + longitud del missatge" es divideix en blocs de 512 bits, que identificarem amb B n amb n que oscil·la entre 0 i L. El nucli de l'algorisme SHA-1 s’anomena funció de compressió i es compon de 4 cicles de 20 passos cadascun. Els bucles tenen una estructura molt similar entre si, excepte pel fet que utilitzen una funció lògica primitiva diferent. Tots els 4 cicles prenen cada bloc com a paràmetre d’entrada juntament amb una constant K i els valors dels 5 registres. Al final del càlcul obtindrem nous valors per A, B, C, D, E que utilitzarem per al càlcul del següent bloc fins al bloc final F

El conjunt SHA-2

Una iteració de la funció de compressió en algoritmes de la família SHA-2.

El 2001 , NIST va llançar quatre funcions de hash addicionals de la família SHA, cadascuna amb un resum més llarg que l'original, coneguda col·lectivament com SHA-2 (tot i que aquest terme mai es va estandarditzar oficialment). Aquestes variants es coneixen, com es va esmentar, amb la longitud en bits del resum generat seguint el codi hash oficial: SHA-224 , SHA-256 , SHA-384 i SHA-512 , amb hash de 224, 256 respectivament, 384 i 512 bits. Cal assenyalar que els darrers tres algorismes es van formalitzar com a estàndard el 2002 mentre que el SHA-224 es va introduir el febrer del 2004 : aquest últim té un hash de longitud idèntica a la de 2 claus Triple DES .

Totes aquestes variants estan patentades pel govern dels Estats Units, però es publiquen sota una llicència gratuïta. [9] .

Els algoritmes SHA-256 i SHA-512 funcionen, respectivament, amb paraules de 32 i 64 bits: utilitzen un nombre diferent de rotacions i constants addicionals, però la seva estructura és substancialment idèntica. Els algoritmes SHA-224 i SHA-384 són simplement versions truncades dels dos anteriors, amb hashs calculats amb diferents valors inicials.

Els algoritmes SHA-2 no han rebut, a diferència del SHA-1, molta atenció per part de la comunitat de criptanalistes, de manera que la seva seguretat criptogràfica no s’ha comprovat del tot. Gilbert i Handschuh ( 2003 ) van estudiar aquestes noves variants i no van trobar cap vulnerabilitat [10] .

SHA-3

La competició que va portar al llançament del nou estàndard SHA-3 es va llançar oficialment el 2 de novembre de 2007 [4] . El 2 d'octubre de 2012, NIST va anunciar l' algorisme Keccak SHA-3 com a guanyador.

Comparació de funcions SHA

La taula següent mostra les característiques principals dels algoritmes de la família SHA ( Estat intern significa la suma interna després de cada compressió d'un bloc de dades).

Algorisme e
variant		 Mida de sortida (bits) Mida de l'estat intern (bit) Mida del bloc (bit) Mida màxima del missatge (bits) Mida de la paraula (bit) Passos Operacions S'han trobat col·lisions
SHA-0 160 160 512 2 64 - 1 32 80 +, i, o, xor, rotl Sí
SHA-1 160 160 512 2 64 - 1 32 80 +, i, o, xor, rotl Atac 2 53 [11]
SHA-2 SHA-256/224 256/224 256 512 2 64 - 1 32 64 +, i, o, xor, shr, rotr Cap
SHA-512/384 512/384 512 1024 2 128 - 1 64 80 +, i, o, xor, shr, rotr Cap

Aplicacions

SHA-1 és l'algorisme més utilitzat de la família SHA. Forma la base de moltes aplicacions i protocols, inclosos TLS i SSL , PGP , SSH , S / MIME i IPsec . SHA-1 també s'utilitza en sistemes de control de versions , com Git , per identificar la revisió de programari i com a suma de verificació per verificar la integritat de fitxers grans en catàlegs en línia.

Els algoritmes SHA també s’utilitzen en algorismes per a la signatura digital de documents, com ara HMAC , i s’han pres com a base per als xifrats de blocs SHACAL .

Exemples i pseudocodi

Mostra de hash

Aquest és un exemple d'un resum generat per SHA-1 (tots els missatges estan codificats en ASCII ):

 SHA1 ("Cantami o diva del pelide Aquil·les la ira fatal")
 = 1f8a690b7366a2323e2d5b045120da7e93896f47

Fins i tot la més mínima variació del missatge genera inevitablement un hash completament diferent a causa d’una reacció en cadena coneguda com a efecte d’allau . Per exemple, substituint Cantami per Contami obtenim:

 SHA1 ("C o ntami o diva del pelis Aquil·les la ira fatal")
 = e5f08d98bf18385e2f26b904cad23c734d530ffb

El resum corresponent a la cadena buida és:

 SHA1 ("")
 = da39a3ee5e6b4b0d3255bfef95601890afd80709

Pseudocodi de SHA-1

Pseudocodi de l'algorisme SHA-1:

 Notes: totes les variables són de 32 bits sense signar i s’ajusten el mòdul 2 32 quan es calcula

Inicialitzar variables:
h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0

Pre-processament:
afegiu el bit '1' al missatge
afegiu k bits '0', on k és el nombre mínim ≥ 0 tal que el missatge resultant
    longitud (en bits ) és congruent amb 448 (mod 512)
afegiu la longitud del missatge (abans del processament previ), en bits , com a enter de 64 bits d'endian

Processar el missatge en trossos posteriors de 512 bits:
trencar el missatge en trossos de 512 bits
per cada tros
    divideix trossos en setze paraules de 32 bits de gran endi w [i], 0 <= i <= 15

Amplieu les setze paraules de 32 bits en vuitanta paraules de 32 bits:
    per a i de 16 a 79
        w [i] = (w [i-3] xor w [i-8] xor w [i-14] xor w [i-16]) esquerra 1

Inicialitzeu el valor de resum per a aquest fragment:
    a = h0
    b = h1
    c = h2
    d = h3
    e = h4

Bucle principal:
    per a i de 0 a 79
        si 0 ≤ i ≤ 19 aleshores
            f = (b i c) o (( no b) i d)
            k = 0x5A827999
        en cas contrari, si 20 ≤ i ≤ 39
            f = b xor c xor d
            k = 0x6ED9EBA1
        en cas contrari, si 40 ≤ i ≤ 59
            f = (b i c) o (b i d) o (c i d)
            k = 0x8F1BBCDC
        en cas contrari, si 60 ≤ i ≤ 79
            f = b xor c xor d
            k = 0xCA62C1D6

temp = (a esquerra 5) + f + e + k + w [i]
        e = d
        d = c
        c = b esquerra 30
        b = a
        a = temp

Afegiu el hash d'aquest fragment per obtenir resultats fins ara:
    h0 = h0 + a
    h1 = h1 + b
    h2 = h2 + c
    h3 = h3 + d
    h4 = h4 + e

Produeix el valor hash final (big-endian):
digereix = hash = h0 afegir h1 afegir h2 afegir h3 afegir h4

Les fórmules següents es poden utilitzar per calcular f al cicle principal publicat anteriorment en lloc de les originals publicades al document 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 (( no b) i d) (alternativa 2)
(0 ≤ i ≤ 19): f = (b i c) + (( no b) i d) (alternativa 3)

(40 ≤ i ≤ 59): f = (b i c) o (d i (b o c)) (alternativa 1)
(40 ≤ i ≤ 59): f = (b i c) o (d i (b xor c)) (alternativa 2)
(40 ≤ i ≤ 59): f = (b i c) + (d i (b xor c)) (alternatives 3)
(40 ≤ i ≤ 59): f = (b i c) xor (b i d) xor (c i d) (alternativa 4)

Pseudocodi de SHA-256 (una variant de SHA-2)

Pseudocodi de l'algorisme SHA-256. Fixeu-vos en l’augment de barreja de bits de paraules w[16..63] en comparació amb SHA-1.

 Notes: totes les variables són de 32 bits sense signar i s’ajusten el mòdul 2 32 quan es calcula

Inicialitzar variables
(primers 32 bits de les parts fraccionàries de les arrels quadrades dels primers 8 primers 2..19):
h0: = 0x6a09e667
h1: = 0xbb67ae85
h2: = 0x3c6ef372
h3: = 0xa54ff53a
h4: = 0x510e527f
h5: = 0x9b05688c
h6: = 0x1f83d9ab
h7: = 0x5be0cd19

Inicialitza la taula de constants rodones
(primers 32 bits de les parts fraccionàries de les arrels cubes dels primers 64 primers 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-processament:
afegiu el bit '1' al missatge
afegiu k bits '0', on k és el nombre mínim> = 0 tal que el missatge resultant
    longitud (en bits ) és congruent amb 448 (mod 512)
afegiu la longitud del missatge (abans del processament previ), en bits , com a enter de 64 bits d'endian

Processar el missatge en trossos posteriors de 512 bits:
trencar el missatge en trossos de 512 bits
per cada tros
    divideix trossos en setze paraules de 32 bits de gran endi w [0..15]

Amplieu les setze paraules de 32 bits en seixanta-quatre paraules de 32 bits:
    per a i de 16 a 63
        s0: = (w [i-15] trencant a la dreta 7) xor (w [i-15] trotant a la dreta 18) xor (w [i-15] righthift 3)
        s1: = (w [i-2] gir a la dreta 17) xor (w [i-2] gir a la dreta 19) xor (w [i-2] righthift 10)
        w [i]: = w [i-16] + s0 + w [i-7] + s1

Inicialitzeu el valor de resum per a aquest fragment:
    a: = h0
    b: = h1
    c: = h2
    d: = h3
    e: = h4
    f: = h5
    g: = h6
    h: = h7

Bucle principal:
    per a i de 0 a 63
        s0: = (a la dreta 2) xor (a la dreta 13) xor (a la dreta 22)
        maj: = (a i b) xor (a i c) xor (b i c)
        t2: = s0 + maj
        s1: = (e rtrtrate 6) xor (e rtrtrate 11) xor (e rtrtrate 25)
        ch: = (e i f) xor (( no 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

Afegiu el hash d'aquest fragment per obtenir resultats fins ara:
    h0: = h0 + a
    h1: = h1 + b
    h2: = h2 + c
    h3: = h3 + d
    h4: = h4 + e
    h5: = h5 + f
    h6: = h6 + g
    h7: = h7 + h

Produeix el valor hash final (big-endian):
resum = hash = h0 afegir h1 afegir h2 afegir h3 afegir h4 afegir h5 afegir h6 afegir h7

Les funcions ch i maj es poden optimitzar tal com es descriu per a les del SHA-1.

El SHA-224 és idèntic al SHA-256 excepte:

  • els valors inicials de les variables h0 - h7 són diferents i
  • la sortida es construeix ometent h7 .

El SHA-512 té una construcció idèntica, però:

  • tots els números tenen una longitud de 64 bits,
  • Es realitzen 80 passos en lloc de 64,
  • els valors inicials i les constants a afegir s’amplien a 64 bits i
  • les quantitats de rotacions ( girades ) i de desplaçaments ( desplaçaments ) són diferents.

El SHA-384 és idèntic al SHA-512 excepte:

  • els valors inicials h0 - h7 són diferents i
  • la sortida es construeix ometent h6 i h7 .

Nota

  1. ↑ Criptoanàlisi de SHA-1 (Schneier)
  2. ↑ Schneier sobre seguretat: NIST Hash Workshop Liveblogging (5)
  3. ^ The H: Notícies de seguretat i desenvolupaments de codi obert
  4. ^ a b Document
  5. ^ Bounce to index.html Arxivat el 5 de febrer de 2008 a Internet Archive .
  6. ^ La família de funcions esponja Keccak
  7. ^ (EN) Anunciant la primera col·lisió SHA1 a security.googleblog.com, el 23 de febrer de 2017. Consultat el 17 de març de 2017.
  8. ^ (EN) Shattered , a shattered.it. Consultat el 17 de març de 2017 .
    "Hem trencat SHA-1 a la pràctica". .
  9. ^ Declaració de llicència per a la patent nord-americana 6829355 .. Consultat el 17 de febrer de 2008 .
  10. ↑ Henri Gilbert, Helena Handschuh, Anàlisi de seguretat de SHA-256 i germanes , a Lecture notes in computer science , Springer, Berlín, ISSN 0302-9743 ( WC ACNP ) . Consultat el 30 de gener de 2008 (arxivat de l' original el 18 d'octubre de 2011) .
  11. ^ Weblog for dkg - HOWTO prep for migration for SHA-1 in OpenPGP

Bibliografia

Articles relacionats

Enllaços externs

Llocs d'Internet per al càlcul de hash

Estàndard: SHA-0, SHA-1, SHA-2, SHA-3 ...

Criptoanàlisi

Implementacions

  • El projecte OpenSSL : la extensa biblioteca OpenSSL inclou programari lliure i de codi obert amb implementació de SHA-1, SHA-224, SHA-256, SHA-384 i SHA-512
  • Crypto ++ Crypto ++, biblioteca C ++ gratuïta amb esquemes criptogràfics
  • Bouncy Castle La biblioteca Bouncy Castle és una biblioteca gratuïta Java i C # que conté implementacions de SHA-1, SHA-224, SHA-256, SHA-384 i SHA-512, i altres algoritmes de hash.

Tutorial i exemples de codis

Prova de vectors

Els vectors de prova del projecte NESSIE per SHA-1 , SHA-256 , SHA-384 i SHA-512 .

Obtingut de " https://it.wikipedia.org/w/index.php?title=Secure_Hash_Algorithm&oldid=119213791 "