Vai al contenuto

Secure Hash Algorithm

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da SHA-1)

Con il termine SHA (acronimo dell'inglese Secure Hash Algorithm) si indica una famiglia di cinque diverse funzioni crittografiche di hash sviluppate a partire dal 1993 dalla National Security Agency (NSA) e pubblicato dal NIST come standard federale dal governo degli USA (FIPS PUB 180-4).

Come ogni algoritmo di hash, l'SHA produce un message digest, o "impronta del messaggio", di lunghezza fissa partendo da un messaggio di lunghezza variabile. La sicurezza di un algoritmo di hash risiede nel fatto che la funzione non sia invertibile (non sia cioè possibile risalire al messaggio originale conoscendo solo questo dato) e che non deve essere mai possibile creare intenzionalmente due messaggi diversi con lo stesso digest. Gli algoritmi della famiglia sono denominati SHA-1, SHA-224, SHA-256, SHA-384 e SHA-512: le ultime 4 varianti sono spesso indicate genericamente come SHA-2, per distinguerle dal primo. Il primo produce un digest del messaggio di soli 160 bit, mentre gli altri producono digest di lunghezza in bit pari al numero indicato nella loro sigla (SHA-256 produce un digest di 256 bit). L'SHA-1 è il più diffuso algoritmo della famiglia SHA ed è utilizzato in numerose applicazioni e protocolli nonostante sia ormai insicuro e verrà presto sostituito dagli altri, più moderni ed efficienti.

La sicurezza di SHA-1 è stata appunto compromessa dai crittoanalisti.[1] Sebbene non siano ancora noti attacchi alle varianti SHA-2, esse hanno un algoritmo simile a quello di SHA-1 per cui sono in atto sforzi per sviluppare algoritmi di hashing alternativi e migliorati.[2][3] Un concorso aperto per la realizzazione di una nuova funzione SHA-3 venne annunciato nel Federal Register il 2 novembre 2007[4] dal NIST e attraverso una competizione pubblica, simile a quella adottata per il processo di sviluppo dell'AES,[5] ha portato in data 2 ottobre 2012 ad annunciare come vincitore l'algoritmo Keccak. Opera di un team di analisti italiani e belgi, il Keccak[6] sembra dunque destinato a venire gradualmente incluso e adottato nelle soluzioni di sicurezza informatica più variegate.

Il 23 febbraio 2017 un team di Google ha annunciato la prima tecnica pratica per generare una collisione hash.[7][8]

SHA-0 e SHA-1

[modifica | modifica wikitesto]
Un'iterazione all'interno della funzione di compressione di SHA-1. A, B, C, D ed E sono parole di stato a 32 bit; F è una funzione non lineare che varia; left shiftn denota una rotazione del bit di sinistra di n posti; n varia per ogni operazione. Addition denota l'addizione modulo 232. Kt è una costante.

La specifica originale dell'algoritmo fu pubblicata nel 1993 come Secure Hash Standard, FIPS PUB 180, dal NIST. Ci si riferisce spesso a questa versione come SHA-0 per distinguerla dalle successive versioni. Fu ritirata dall'NSA breve tempo dopo la pubblicazione e fu soppiantata da una versione rivista, pubblicata nel 1995 (FIPS PUB 180-1) e solitamente nota come SHA-1. L'SHA-1 differisce dall'SHA-0 unicamente per una sola rotazione di bit nel processo di preparazione del messaggio della sua funzione di compressione ad una via; ciò fu fatto, secondo l'NSA, per correggere un difetto nell'algoritmo originale, il quale riduceva la sicurezza crittografica di SHA-0. Ad ogni modo, l'NSA non fornì nessuna ulteriore spiegazione chiarificante. Sono state in seguito riportate debolezze sia nel codice dell'SHA-0 sia in quello dell'SHA-1. L'SHA-1 pare offrire maggiore resistenza agli attacchi, a supporto dell'asserzione dell'NSA che il cambiamento aumentò la sicurezza.

L'SHA-1 (così come l'SHA-0) produce un digest di 160 bit da un messaggio con una lunghezza massima di 264-1 bit, essendo fondato sulla schema di Merkel-Damgard si basa su principi simili a quelli usati da Ronald L. Rivest del MIT nel design degli algoritmi MD4 e MD5.

Funzionamento

[modifica | modifica wikitesto]

Passo 1 (Imbottitura): Al messaggio originale vengono aggiunti dei bit di "imbottitura" affinché la lunghezza finale del messaggio risulti congruente a 448 modulo 512, così facendo la lunghezza in bit di "messaggio imbottitura" divisa per 512 darà resto 448.

Passo 2 (Aggiunta lunghezza): Alla sequenza di bit (messaggio imbottitura) creata durante il passo 1 viene aggiunto un intero unsigned di 64bit contenente la lunghezza del messaggio originale. Alla fine di questi due primi passi otteniamo una sequenza di bit che è un multiplo di 512.

Passo 3 (Inizializzazione del buffer MD): Un buffer di 160bit suddiviso in 5 registri da 32bit ciascuno viene creato per la memorizzazione di alcuni passaggi intermedi. I 5 registri verranno convenzionalmente indicati con (A,B,C,D,E) ed inizializzati con i seguenti valori esadecimali:

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

Passo 4 (Elaborazione dei blocchi da 512bit): La sequenza di bit "messaggio imbottitura lunghezzaMessaggio" viene divisa in blocchi da 512bit, che identificheremo con Bn con n che va da 0 a L. Il fulcro dell'algoritmo SHA-1 è chiamato compression function ed è formato da 4 cicli di 20 passi cadauno. I cicli hanno una struttura molto simile tra di loro se non per il fatto che utilizzano una differente funzione logica primitiva. Ogni blocco viene preso come parametro di input da tutti e 4 i cicli insieme ad una costante K e i valori dei 5 registri. Alla fine della computazione otterremo dei nuovi valori per A,B,C,D,E che useremo per la computazione del blocco successivo sino ad arrivare al blocco finale F.

L'insieme SHA-2

[modifica | modifica wikitesto]
Una iterazione della funzione di compressione negli algoritmi della famiglia SHA-2.

Nel 2001 il NIST pubblicò quattro funzioni di hash addizionali facenti parte della famiglia SHA, ognuna con un digest più lungo di quello originale, collettivamente denominate SHA-2 (anche se questo termine non è mai stato ufficialmente standardizzato). Queste varianti sono note, come detto, con la lunghezza in bit del digest generato a seguire la sigla ufficiale dell'hash: SHA-224, SHA-256, SHA-384 e SHA-512, con, rispettivamente, hash di 224, 256, 384 e 512 bit. Da notare che gli ultimi tre algoritmi furono ufficializzati come standard nel 2002 mentre l'SHA-224 fu introdotto nel febbraio del 2004: quest'ultimo presenta un hash di lunghezza identica a quella di 2 chiavi del Triple DES.

Tutte queste varianti sono brevettate dal governo statunitense, ma pubblicate con licenza libera.[9].

Gli algoritmi SHA-256 e SHA-512 lavorano, rispettivamente, con word di 32 e 64 bit: utilizzano un numero differente di rotazioni e di costanti addizionali, ma la loro struttura è sostanzialmente identica. Gli algoritmi SHA-224 e SHA-384 sono semplicemente versioni troncate dei precedenti due, con hash calcolati con differenti valori iniziali.

Gli algoritmi SHA-2 non hanno ricevuto, a differenza dell'SHA-1, molta attenzione dalla comunità dei crittoanalisti per cui la loro sicurezza in campo crittografico non è stata del tutto provata. Gilbert e Handschuh (2003) hanno studiato queste nuove varianti e non hanno trovato vulnerabilità[10].

SHA-3

[modifica | modifica wikitesto]
Lo stesso argomento in dettaglio: SHA-3.

La competizione che ha portato al rilascio del nuovo standard SHA-3 è stata ufficialmente lanciata il 2 novembre 2007[4]. Il 2 ottobre 2012 la NIST ha proclamato come vincitore l'algoritmo di Keccak SHA-3.

Comparazione delle funzioni SHA

[modifica | modifica wikitesto]

Nella tabella sottostante sono riportate le caratteristiche principali degli algoritmi della famiglia SHA (Per Stato interno si intende la somma interna dopo ogni compressione di un blocco di dati).

Algoritmo e
variante 		Dimensione dell'output (bit) Dimensione dello stato interno (bit) Dimensione del blocco (bit) Max. dimensione del messaggio (bit) Dimensione della word (bit) Passaggi Operazioni Collisioni trovate
SHA-0 160 160 512 264 − 1 32 80 ,and,or,xor, rotl Sì
SHA-1 160 160 512 264 − 1 32 80 ,and,or,xor, rotl Attacco 253[11]
SHA-2 SHA-256/224 256/224 256 512 264 − 1 32 64 ,and,or,xor,shr, rotr Nessuna
SHA-512/384 512/384 512 1024 2128 − 1 64 80 ,and,or,xor,shr, rotr Nessuna

Applicazioni

[modifica | modifica wikitesto]

SHA-1 è l'algoritmo più utilizzato della famiglia SHA. Costituisce la base di numerose applicazioni e protocolli, inclusi il TLS ed SSL, il PGP, l'SSH, l'S/MIME e l'IPsec. L'SHA-1 è anche utilizzato in sistemi di controllo versione, come il Git, per identificare la revisione dei software e come somma di controllo per verificare l'integrità di file di grosse dimensioni in cataloghi online.

Gli algoritmi SHA sono anche utilizzati negli algoritmi per la firma digitale dei documenti, quali ad esempio l'HMAC, e sono stati presi come base per i cifrari a blocchi SHACAL.

Esempi e pseudocodice

[modifica | modifica wikitesto]

Hash di esempio

[modifica | modifica wikitesto]

Questo è un esempio di digest generato dall'SHA-1 (tutti i messaggi sono codificati in ASCII): 

SHA1("Cantami o diva del pelide Achille l'ira funesta")
 = 1f8a690b7366a2323e2d5b045120da7e93896f47

Anche una minima variazione nel messaggio genera, ineluttabilmente, un hash completamente differente a causa di una reazione a catena nota come effetto valanga. Ad esempio, sostituendo Cantami con Contami otteniamo: 

SHA1("Contami o diva del pelide Achille l'ira funesta")
 = e5f08d98bf18385e2f26b904cad23c734d530ffb

Il digest corrispondente alla stringa vuota è: 

SHA1("")
 = da39a3ee5e6b4b0d3255bfef95601890afd80709

Pseudocodice di SHA-1

[modifica | modifica wikitesto]

Pseudocodice dell'algoritmo SHA-1: 

Note: All variables are unsigned 32 bits and wrap modulo 232 when calculating

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

Pre-processing:
append the bit '1' to the message
append k bits '0', where k is the minimum number ≥ 0 such that the resulting message
    length (in bits) is congruent to 448 (mod 512)
append length of message (before pre-processing), in bits, as 64-bit big-endian integer

Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
    break chunk into sixteen 32-bit big-endian words w[i], 0 <= i <= 15

    Extend the sixteen 32-bit words into eighty 32-bit words:
    for i from 16 to 79
        w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

    Initialize hash value for this chunk:
    a = h0
    b = h1
    c = h2
    d = h3
    e = h4

    Main loop:
    for i from 0 to 79
        if 0 ≤ i ≤ 19 then
            f = (b and c) or ((not b) and d)
            k = 0x5A827999
        else if 20 ≤ i ≤ 39
            f = b xor c xor d
            k = 0x6ED9EBA1
        else if 40 ≤ i ≤ 59
            f = (b and c) or (b and d) or (c and d)
            k = 0x8F1BBCDC
        else if 60 ≤ i ≤ 79
            f = b xor c xor d
            k = 0xCA62C1D6

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

    Add this chunk's hash to result so far:
    h0 = h0   a
    h1 = h1   b
    h2 = h2   c
    h3 = h3   d
    h4 = h4   e

Produce the final hash value (big-endian):
digest = hash = h0 append h1 append h2 append h3 append h4

Le seguenti formule possono essere utilizzate per calcolare f nel ciclo principale qui sopra pubblicato al posto di quelle originali pubblicate nel documento ufficiale FIPS PUB 180-1: 

(0  ≤ i ≤ 19): f = d xor (b and (c xor d))                (alternative 1)
(0  ≤ i ≤ 19): f = (b and c) xor ((not b) and d)          (alternative 2)
(0  ≤ i ≤ 19): f = (b and c)   ((not b) and d)            (alternative 3)
 
(40 ≤ i ≤ 59): f = (b and c) or (d and (b or c))          (alternative 1)
(40 ≤ i ≤ 59): f = (b and c) or (d and (b xor c))         (alternative 2)
(40 ≤ i ≤ 59): f = (b and c)   (d and (b xor c))          (alternative 3)
(40 ≤ i ≤ 59): f = (b and c) xor (b and d) xor (c and d)  (alternative 4)

Pseudocodice di SHA-256 (una variante di SHA-2)

[modifica | modifica wikitesto]

Pseudocode dell'algoritmo SHA-256. Notare l'incremento nel mescolamento dei bit delle word w[16..63] rispetto all'SHA-1. 

Note: All variables are unsigned 32 bits and wrap modulo 232 when calculating

Initialize variables
(first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19):
h0 := 0x6a09e667
h1 := 0xbb67ae85
h2 := 0x3c6ef372
h3 := 0xa54ff53a
h4 := 0x510e527f
h5 := 0x9b05688c
h6 := 0x1f83d9ab
h7 := 0x5be0cd19

Initialize table of round constants
(first 32 bits of the fractional parts of the cube roots of the first 64 primes 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-processing:
append the bit '1' to the message
append k bits '0', where k is the minimum number >= 0 such that the resulting message
    length (in bits) is congruent to 448 (mod 512)
append length of message (before pre-processing), in bits, as 64-bit big-endian integer

Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
    break chunk into sixteen 32-bit big-endian words w[0..15]

    Extend the sixteen 32-bit words into sixty-four 32-bit words:
    for i from 16 to 63
        s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
        s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] rightshift 10)
        w[i] := w[i-16]   s0   w[i-7]   s1

    Initialize hash value for this chunk:
    a := h0
    b := h1
    c := h2
    d := h3
    e := h4
    f := h5
    g := h6
    h := h7

    Main loop:
    for i from 0 to 63
        s0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
        maj := (a and b) xor (a and c) xor (b and c)
        t2 := s0   maj
        s1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
        ch := (e and f) xor ((not e) and 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

    Add this chunk's hash to result so far:
    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 the final hash value (big-endian):
digest = hash = h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7

Le funzioni ch e maj possono essere ottimizzate nel modo descritto per quelle dell'SHA-1.

L'SHA-224 è identico all'SHA-256 tranne che:

  • i valori iniziali delle variabili h0-h7 sono differenti e
  • l'output è costruito omettendo h7.

L'SHA-512 è identico nella struttura ma:

  • tutti i numeri sono lunghi 64 bit,
  • sono eseguiti 80 passaggi invece di 64,
  • i valori iniziali e le costanti da addizionare sono estesi a 64 bit e
  • le quantità delle rotazioni (rotate) e degli spostamenti (shift) sono differenti.

L'SHA-384 è identico all'SHA-512 tranne che:

  • i valori iniziali h0-h7 sono differenti e
  • l'output è costruito omettendo h6 e h7.

Note

[modifica | modifica wikitesto]
  1. ^ Crittoanalisi dell'SHA-1 (Schneier)
  2. ^ Schneier on Security: NIST Hash Workshop Liveblogging (5)
  3. ^ The H: Security news and Open source developments
  4. ^ a b Document
  5. ^ Bounce to index.html Archiviato il 5 febbraio 2008 in Internet Archive.
  6. ^ The Keccak sponge function family
  7. ^ (EN) Announcing the first SHA1 collision, su security.googleblog.com, 23 febbraio 2017. URL consultato il 17 marzo 2017.
  8. ^ (EN) Shattered, su shattered.it. URL consultato il 17 marzo 2017.
    «We have broken SHA-1 in practice.»
  9. ^ Licensing Declaration for US patent 6829355.. URL consultato il 17 febbraio 2008.
  10. ^ Henri Gilbert, Helena Handschuh, Security analysis of SHA-256 and sisters, in Lecture notes in computer science, Springer, Berlin, ISSN 0302-9743 (WC · ACNP). URL consultato il 30 gennaio 2008 (archiviato dall'url originale il 18 ottobre 2011).
  11. ^ Weblog for dkg - HOWTO prep for migration off of SHA-1 in OpenPGP, su debian-administration.org. URL consultato il 4 maggio 2019 (archiviato dall'url originale il 3 maggio 2019).

Bibliografia

[modifica | modifica wikitesto]
  • Florent Chabaud, Antoine Joux: Differential Collisions in SHA-0. CRYPTO 1998. pp56–71
  • Eli Biham, Rafi Chen, Near-Collisions of SHA-0, Cryptology ePrint Archive, Report 2004/146, 2004 (appeared on CRYPTO 2004) [1]
  • Joux, Carribault, Lemuet, Jalby: Collision for the full SHA-0 algorithm, CRYPTO 2004 [2]
  • Xiaoyun Wang, Hongbo Yu and Yiqun Lisa Yin, Efficient Collision Search Attacks on SHA-0, CRYPTO 2005 [3]
  • Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu, Finding Collisions in the Full SHA-1, CRYPTO 2005 [4]
  • Henri Gilbert, Helena Handschuh: Security Analysis of SHA-256 and Sisters. Selected Areas in Cryptography 2003: pp175–193
  • Proposed Revision of Federal Information Processing Standard (FIPS) 180, Secure Hash Standard [collegamento interrotto], in Federal Register, vol. 59, n. 131, 11 luglio 1994, pp. 35317-35318. URL consultato il 26 aprile 2007.

Voci correlate

[modifica | modifica wikitesto]

Collegamenti esterni

[modifica | modifica wikitesto]

Siti Internet per il calcolo degli hash

[modifica | modifica wikitesto]

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

[modifica | modifica wikitesto]

Crittoanalisi

[modifica | modifica wikitesto]

Implementazioni

[modifica | modifica wikitesto]
  • The OpenSSL Project – La diffusa libreria OpenSSL include software libero ed open source con implementazione dell'SHA-1, SHA-224, SHA-256, SHA-384 ed SHA-512
  • Crypto Crypto , libreria libera in C con schemi crittografici
  • Bouncy Castle La libreria Bouncy Castle è una libreria libera in Java e C# che contiene implementazioni dell'SHA-1, SHA-224, SHA-256, SHA-384 ed SHA-512, e di altri algoritmi di hash.

Tutorial e codici d'esempio

[modifica | modifica wikitesto]

Vettori di test

[modifica | modifica wikitesto]

The NESSIE project test vectors for SHA-1, SHA-256, SHA-384, and SHA-512.

  Portale Crittografia
Estratto da "https://it.wikipedia.org/w/index.php?title=Secure_Hash_Algorithm&oldid=142006700"