SHA-2

SHA-2 ( Secure Hash Algorithm ) è una famiglia di funzioni hash che sono state progettate dalla United States National Security Agency (NSA), sul modello delle funzioni SHA-1 e SHA-0 , esse stesse fortemente ispirate alla funzione MD4 di Ron Rivest (che ha dato parallelamente MD5 ). Come descritto dal National Institute of Standards and Technology (NIST), include le funzioni SHA-256 e SHA-512 i cui algoritmi sono simili ma operano su parole di dimensioni diverse (32 bit per SHA-256 e 64 bit per SHA-512 ), SHA-224 e SHA-384 che sono essenzialmente versioni dei precedenti con output troncato, e più recentemente SHA-512/256 e SHA-512/224 che sono versioni troncate di SHA-512. L'ultimo suffisso indica il numero di bit nell'hash.

Gli algoritmi della famiglia SHA-2, SHA-256, SHA-384 e SHA-512, sono descritti e pubblicati dalla società SHA1 come un governo federale standard degli Stati Uniti ( Federal Information Processing Standard ) nel FIPS 180-2 (Secure Hash Standard) del 2002 (nel 2001 è stata fatta una pre-pubblicazione per i commenti). La funzione SHA-224 viene aggiunta un po 'più tardi. L'ultima versione fino ad oggi, FIPS 180-4 (Secure Hash Standard) risale amarzo 2012 e aggiunge le funzioni SHA-512/256 e SHA-512/224.

Nel 2005 sono stati evidenziati i problemi di sicurezza di SHA-1 : esiste un attacco teorico per la ricerca sulle collisioni che è significativamente più veloce del generico attacco del compleanno alle funzioni hash. Sebbene l'algoritmo SHA-2 condivida somiglianze con quello di SHA-1, attualmente questi attacchi non possono essere estesi a SHA-2. Il NIST, tuttavia, ha indetto una competizione per selezionare una nuova funzione hash, SHA-3 . Alla fine del 2012, il concorso ha portato alla scelta di una nuova famiglia di funzioni il cui design è molto diverso da SHA-1 e SHA-2. La nuova famiglia di funzioni si presenta come un'altra possibile scelta, non mette in discussione l'utilizzo di SHA-2 almeno per il momento.

Descrizione

Come tutte le funzioni hash, le funzioni SHA-2 prendono come input un messaggio di dimensione arbitraria, con un limite (tutto teorico) per esso, e producono un risultato (chiamato " hash ", hash , condensate o anche fingerprint ...) di fixed dimensione. La dimensione dell'hash è indicata dal suffisso: 224 bit per SHA-224, 256 bit per SHA-256, 384 bit per SHA-384 e 512 bit per SHA-512.

Gli algoritmi della famiglia SHA-2 sono molto simili, ci sono fondamentalmente due diverse funzioni, SHA-256 e SHA-512, le altre sono variazioni dell'una o dell'altra. Le funzioni SHA-256 e SHA-512 hanno la stessa struttura ma differiscono per la dimensione delle parole e dei blocchi utilizzati. Questa struttura è abbastanza simile a quella di SHA-1, ma un po 'più complessa ed evita alcune note debolezze. Si riferisce più in generale a una famiglia di funzioni hash ispirate a MD4 e MD5 di Ron Rivest . Troviamo come primitive l'addizione per interi di dimensione fissa n, cioè un'addizione modulo 2 n , un'operazione non lineare (nel senso di algebra lineare ) sul campo di Booleani F 2 , nonché operazioni bit per bit (xor e altre).

Come tutte le funzioni di questa famiglia (eccetto SHA-3, basata su una funzione spugna ), seguono uno schema iterativo che segue la costruzione di Merkle-Damgård (senza un'operazione di finalizzazione). La funzione di compressione iterata ha due input di dimensione fissa, con il secondo input della stessa dimensione dell'output della funzione:

dati ottenuti suddividendo il messaggio da elaborare, la dimensione è 512 bit per SHA-256 e SHA-224 e 1024 bit per SHA-512 e SHA-384,
il risultato della funzione di compressione nell'iterazione precedente (256 bit per SHA-256 e SHA-224, 512 per SHA-512 e SHA-384).

Gli ingressi della funzione di compressione sono suddivisi

in parole a 32 bit per SHA-256 e SHA-224,
in parole a 64 bit per SHA-512 e SHA-384.

La funzione di compressione ripete le stesse operazioni un determinato numero di volte, si parla di giro o giro , 64 giri per SHA-256, 80 giri per SHA-512. Ogni turno comporta come primitive l'intera addizione per interi di dimensione fissa, vale a dire un'addizione modulo 2 32 o modulo 2 64 , operazioni bit per bit: operazioni logiche, offset con perdita di parte dei bit e offset circolari e predefiniti costanti, utilizzate anche per l'inizializzazione.

Prima dell'elaborazione, il messaggio viene completato da un riempimento in modo che la sua lunghezza sia un multiplo della dimensione del blocco elaborato dalla funzione di compressione. L'imbottitura riprende la lunghezza (in binario) della parola da elaborare: è il potenziamento del Merkle-Damgård ( (en) Merkle-Damgård rinforzo ), che permette di ridurre la resistenza alle collisioni della funzione hash a quella della funzione di compressione. Questa lunghezza è memorizzata alla fine del riempimento su 64 bit nel caso di SHA-256 (come per SHA-1), oltre 128 bit nel caso di SHA-512, che "limita" la dimensione dei messaggi da elaborato a 2 64 bit per SHA-256 (e SHA-224) ea 2128 bit per SHA-512 (e SHA-384).

SHA-256

La funzione SHA-256 diventa nel 2002 uno standard federale di elaborazione delle informazioni ( FIPS del NIST ). Produce un hash a 256 bit . Le caratteristiche di SHA-256 sono le seguenti:

dimensione del messaggio: 2 64 bit massimo
dimensione del blocco: 512 bit
dimensione della parola: 32 bit
dimensione digest: 256 bit
livello di sicurezza previsto (collisioni): 2 128 bit ( attacco di compleanno )
numero di giri (funzione di compressione): 64

Algoritmo

L'algoritmo può essere suddiviso in due fasi

Pre-elaborazione : il messaggio è completato da un riempimento comprendente la dimensione del messaggio (rinforzo di Merkle-Damgård) in modo che possa essere suddiviso in blocchi di 512 bit;
Il calcolo del digest mediante iterazione della funzione di compressione sulla sequenza di blocchi ottenuta dividendo il messaggio (schema iterativo di Merkle-Damgård).

Simboli e termini utilizzati impostazioni

a, b, c, ..., h = variabili di lavoro (in questo caso parole w-bit), utilizzate nel calcolo dell'hash

$H ^ {(i)}$ = il valore hash # i. è il valore iniziale dell'hash. è l'ultimo valore hash. $H ^ {(0)}$ $H ^ {(N)}$

$H_j ^ {(i)}$ = parola (w bit) # j del valore hash # i, dove è la parola più significativa (a sinistra) del valore hash i. $H_0 ^ {(i)}$

$K_t$ = costanti iterative in base al valore di t, utilizzato nel calcolo dell'hash

k = numero di 0 aggiunti al messaggio durante la preelaborazione (complemento)
l = lunghezza del messaggio M, in bit
m = numero di bit contenuti in un blocco, ovvero 512 bit
M = messaggio da elaborare = blocco n ° i (m bit), messaggio M = parola (w bit) n ° j, blocco (m bit) n ° i, messaggio M n = numero di bit di spostamento o rotazione da applicare alla parola quando associata a una funzione binaria N = numero di blocchi di m bit contenuti nel messaggio M dopo il complemento T = variabile temporanea , parola di w bit, utilizzata nel calcolo dell'hash w = numero di bit contenuti in una parola, cioè 32 bit. = la parola n ° t della tabella dedotta dal messaggio
$M ^ {(i)}$
$M_j ^ {(i)}$

$W_t$

Simboli

La notazione esadecimale utilizzata qui sarà: $\ mbox {0x}$

esempio:

H_0 ^ {(0)} = \ mbox {0x12ab34ef}

$\ wedge$ = operazione binaria AND = operazione binaria OR = operazione binaria XOR = complemento binario = addizione modulo = spostamento binario a sinistra, dove si ottiene rimuovendo gli n bit sinistri di x e aggiungendo n zeri a destra. = spostamento binario a destra, dove si ottiene rimuovendo gli n bit di destra di x e aggiungendo n zeri a sinistra.
$\ vee$
$\ oplus$
$\ lnot$
$+$ $2 ^ sett$
$<<$ $x << n$
$>>$ $x >> n$

Operazioni con le parole

Le operazioni utilizzate sono le seguenti:

le operazioni bit per bit su parole a 32 bit (vedi #Simboli alle notazioni utilizzate);
l'operazione sulle parole corrispondenti al modulo Inoltre $2 32$ , cioè la somma $z = x + y$ di due parole $x$ ed $y$ rappresentano numeri naturali $X$ e $Y$ ( $0 \leq X <2 32$ e $0 \leq Y <2 32$ ) è il rappresentazione binaria dell'intero $Z$ , tale che $Z = X + Y mod 2 32$ , $0 \leq Z <2 32$ ,
l'operazione di spostamento del bit destro , dove x è una parola a 32 bit ed è definita da: ${\ displaystyle SHR ^ {n} (x)}$ ${\ displaystyle 0 \ leq n <32}$ ${\ displaystyle SHR ^ {n} (x) = x >> n}$ ;
l'operazione di rotazione binaria in senso orario , dove x è una parola a 32 bit ed è definita da: ${\ displaystyle ROTR ^ {n} (x)}$ ${\ displaystyle 0 \ leq n <32}$ ${\ displaystyle ROTR ^ {n} (x) = (x >> n) \ vee (x << (32-n))}$ .

Funzioni e costanti Funzioni

Questa sezione descrive le funzioni utilizzate durante il calcolo dei valori hash. SHA-256 utilizza 6 funzioni logiche che lavorano su parole a 32 bit indicate con x, y, z. Il risultato di ciascuna di queste funzioni è una nuova uscita di parola a 32 bit.

$Ch (x, y, z) = (x \ cuneo y) \ oplus (\ lnot x \ cuneo z)$

$Maiusc (x, y, z) = (x \ cuneo y) \ oplus (x \ cuneo z) \ oplus (y \ cuneo z)$

$\ Sigma _ {0} ^ {{\ {256 \}}} (x) = ROTR ^ {2} (x) \ oplus ROTR ^ {{13}} (x) \ oplus ROTR ^ {{22}} ( X)$

$\ Sigma _ {1} ^ {{\ {256 \}}} (x) = ROTR ^ {6} (x) \ oplus ROTR ^ {{11}} (x) \ oplus ROTR ^ {{25}} ( X)$

$\ sigma _ {0} ^ {{\ {256 \}}} (x) = ROTR ^ {7} (x) \ oplus ROTR ^ {{18}} (x) \ oplus SHR ^ {3} (x)$

$\ sigma _ {1} ^ {{\ {256 \}}} (x) = ROTR ^ {{17}} (x) \ oplus ROTR ^ {{19}} (x) \ oplus SHR ^ {{10} } (X)$

Costanti

SHA-256 utilizza 64 valori costanti di parole a 32 bit, annotato . questi numeri rappresentano i primi 32 bit della parte decimale delle radici cubiche dei primi 64 numeri primi . I seguenti valori sono espressi in notazione esadecimale (base 16). $K_ {0} ^ {{\ {256 \}}}, K_ {1} ^ {{\ {256 \}}}, ..., K _ {{63}} ^ {{\ {256 \}} } ~$

$K _ {{0}} ^ {{\ {256 \}}}, ..., K _ {{7}} ^ {{\ {256 \}}}$	0x428a2f98	0x71374491	0xb5c0fbcf	0xe9b5dba5	0x3956c25b	0x59f111f1	0x923f82a4	0xab1c5ed5
$K _ {{8}} ^ {{\ {256 \}}}, ..., K _ {{15}} ^ {{\ {256 \}}}$	0xd807aa98	0x12835b01	0x243185be	0x550c7dc3	0x72be5d74	0x80deb1fe	0x9bdc06a7	0xc19bf174
$K _ {{16}} ^ {{\ {256 \}}}, ..., K _ {{23}} ^ {{\ {256 \}}}$	0xe49b69c1	0xefbe4786	0x0fc19dc6	0x240ca1cc	0x2de92c6f	0x4a7484aa	0x5cb0a9dc	0x76f988da
$K _ {{24}} ^ {{\ {256 \}}}, ..., K _ {{31}} ^ {{\ {256 \}}}$	0x983e5152	0xa831c66d	0xb00327c8	0xbf597fc7	0xc6e00bf3	0xd5a79147	0x06ca6351	0x14292967
$K _ {{32}} ^ {{\ {256 \}}}, ..., K _ {{39}} ^ {{\ {256 \}}}$	0x27b70a85	0x2e1b2138	0x4d2c6dfc	0x53380d13	0x650a7354	0x766a0abb	0x81c2c92e	0x92722c85
$K _ {{40}} ^ {{\ {256 \}}}, ..., K _ {{47}} ^ {{\ {256 \}}}$	0xa2bfe8a1	0xa81a664b	0xc24b8b70	0xc76c51a3	0xd192e819	0xd6990624	0xf40e3585	0x106aa070
$K _ {{48}} ^ {{\ {256 \}}}, ..., K _ {{55}} ^ {{\ {256 \}}}$	0x19a4c116	0x1e376c08	0x2748774c	0x34b0bcb5	0x391c0cb3	0x4ed8aa4a	0x5b9cca4f	0x682e6ff3
$K _ {{56}} ^ {{\ {256 \}}}, ..., K _ {{63}} ^ {{\ {256 \}}}$	0x748f82ee	0x78a5636f	0x84c87814	0x8cc70208	0x90befffa	0xa4506ceb	0xbef9a3f7	0xc67178f2

Pretrattamento

Questa operazione si svolge in tre passaggi: completare il messaggio M, dividere il risultato in blocchi e inizializzare i valori hash. $H ^ {(0)} ~$

Marmellata

Ciò comporta il completamento del messaggio M in modo che abbia una dimensione multipla di 512 bit. Il riempimento utilizza la rappresentazione binaria dell'intero $l$ che è la lunghezza in bit del messaggio M (rinforzo Merkle-Damgård ). Per fare ciò aggiungiamo successivamente:

un po 'impostato a 1 alla fine del messaggio M ,
$k$ 0 bit di ripieno, dove $k$ è il più piccolo intero naturale che soddisfa $l + 1 + k \equiv 448 mod 512$
un blocco a 64 bit che fornisce la rappresentazione binaria di $l$ .

Esempi:

Per M = "abc", l = 3 × 8 = 24 bit, k ≡ 448 - (24 + 1) ≡ 423 mod 512 , quindi k = 423 ;
- aggiungiamo a M
  - prima un po 'a 1,
  - quindi 423 bit a 0,
  - quindi 64 bit che rappresentano 24 in binario, cioè "0000 ... 0000 0001 1000"
si ottiene quindi un messaggio completato la cui lunghezza è il più piccolo multiplo di 512 bit maggiore della lunghezza iniziale M .
Per M di lunghezza bit, k ≡ 448 - (500 + 1) ≡ -53 mod 512 ; quindi k = 512 - 53 = 459 ; l=500{\ displaystyle l = 500} ${\ displaystyle l = 500}$
- aggiungiamo a M
  - prima un po 'a 1,
  - quindi 459 bit a 0,
  - quindi 64 bit che rappresentano 500 in binario o "0000 ... 0000 0001 1111 0100"
si ottiene quindi un messaggio completato la cui lunghezza è maggiore di 512 bit a multipli di 512 bit maggiore della lunghezza iniziale M .

Taglio in blocchi

Il messaggio completato è diviso in N blocchi di 512 bit, annotati . Ciascun blocco di 512 bit viene quindi diviso in 16 parole di 32 bit, annotate . $M ^ {(1)}, M ^ {(2)}, ..., M ^ {(N)} ~$ ${\ displaystyle \ forall i \ in [1, N], \ \ M_ {0} ^ {(i)}, M_ {1} ^ {(i)}, ..., M_ {15} ^ {(i )}}$

Inizializzazioni

Alle otto variabili seguenti vengono assegnati valori iniziali come segue:

$H_ {0} ^ {{(0)}} = {\ mbox {0x6a09e667}}$
$H_ {1} ^ {{(0)}} = {\ mbox {0xbb67ae85}}$
$H_ {2} ^ {{(0)}} = {\ mbox {0x3c6ef372}}$
$H_ {3} ^ {{(0)}} = {\ mbox {0xa54ff53a}}$
$H_ {4} ^ {{(0)}} = {\ mbox {0x510e527f}}$
$H_ {5} ^ {{(0)}} = {\ mbox {0x9b05688c}}$
$H_ {6} ^ {{(0)}} = {\ mbox {0x1f83d9ab}}$
$H_ {7} ^ {{(0)}} = {\ mbox {0x5be0cd19}}$

Calcolo del digest (tritato)

Per questo trattamento useremo

una tabella di 64 parole, annotato $W_ {0}, W_ {1}, ..., W _ {{63}} ~$
otto variabili annotate $a, b, c, d, e, f, g, h ~$
otto variabili contenenti i valori hash, annotati e inizializzati in precedenza in $H_0 ^ {(i)}$ $H_0 ^ {(0)}$

Queste variabili conterranno iterativamente nuovi valori hash, per contenere finalmente il digest di M, in .

H ^ {(i)} ~

H ^ {(N)} ~

due variabili, annotate , parole a 32 bit. $T_ {1} {\ mbox {e}} T_ {2}$

Gli N blocchi di M vengono elaborati successivamente secondo le seguenti fasi

Per i = 1 a N
{

1. Compiliamo la tabella per t da 0 a 63, secondo

W_t

W_ {t} = \ left \ {{\ begin {matrix} M_ {t} ^ {{(i)}}, & 0 \ leq t \ leq 15 \\\\\ sigma _ {1} ^ {{\ {256 \}}} \ sinistra (W _ {{t-2}} \ destra) + W _ {{t-7}} + \ sigma _ {0} ^ {{\ {256 \}}} \ sinistra (W_ {{t-15}} \ right) + W _ {{t-16}}, & 16 \ leq t \ leq 63 \ end {matrix}} \ right.

2. Inizializziamo a, b, c, d, e, f, g e h con i valori hash del round precedente

a = H_0 ^ {(i-1)} ~

b = H_1 ^ {(i-1)} ~

c = H_2 ^ {(i-1)} ~

d = H_3 ^ {(i-1)} ~

e = H_4 ^ {(i-1)} ~

f = H_ {5} ^ {{(i-1)}} ~

g = H_ {6} ^ {{(i-1)}} ~

h = H_ {7} ^ {{(i-1)}} ~

3. Per t da 0 a 63 {

T_ {1} = h + \ Sigma _ {1} ^ {{\ {256 \}}} (e) + Ch (e, f, g) + K_ {t} ^ {{\ {256 \}}} + W_ {t} ~

T_ {2} = \ Sigma _ {0} ^ {{\ {256 \}}} (a) + Maiusc (a, b, c) ~

h = g ~

g = f ~

f = e ~

e = d + T_ {1} ~

d = c ~

c = b ~

b = a ~

a = T_ {1} + T_ {2} ~

} 4. Calcolo dei valori hash intermedi

H_ {0} ^ {{(i)}} = a + H_ {0} ^ {{(i-1)}}

H_ {1} ^ {{(i)}} = b + H_ {1} ^ {{(i-1)}}

H_ {2} ^ {{(i)}} = c + H_ {2} ^ {{(i-1)}}

H_ {3} ^ {{(i)}} = d + H_ {3} ^ {{(i-1)}}

H_ {4} ^ {{(i)}} = e + H_ {4} ^ {{(i-1)}}

H_ {5} ^ {{(i)}} = f + H_ {5} ^ {{(i-1)}}

H_ {6} ^ {{(i)}} = g + H_ {6} ^ {{(i-1)}}

H_ {7} ^ {{(i)}} = h + H_ {7} ^ {{(i-1)}}

}

Dopo aver ripetuto i quattro passaggi precedenti per gli N blocchi del messaggio M, (ovvero, dopo l'elaborazione di ), il digest a 256 bit di M viene ottenuto dalla concatenazione dei valori $M ^ {(N)} ~$

H_ {0} ^ {{(N)}} || H_ {1} ^ {{(N)}} || H_ {2} ^ {{(N)}} || H_ {3} ^ {{( N)}} || H_ {4} ^ {{(N)}} || H_ {5} ^ {{(N)}} || H_ {6} ^ {{(N)}} || H_ { 7} ^ {{(N)}}

SHA-224

La funzione SHA-224 è stata rilasciata per la prima volta nel 2004. L'output (hash, hash o hash) è di 224 bit . È stato appositamente progettato per fornire un'impronta digitale la cui dimensione corrisponde a quattro chiavi DES di 56 bit ciascuna. L'algoritmo è quello di SHA-256 con solo differenze

diversi valori per l'inizializzazione (variabili h0,…, h7);
un'uscita troncata a 224 bit (concatenazione del contenuto delle prime 7 variabili h0,…, h6).

SHA-512

La funzione SHA-512 è apparsa insieme a SHA-256 e nel 2002 è diventata uno standard federale di elaborazione delle informazioni ( FIPS il NIST ). Produce un hash a 512 bit .

L'algoritmo è molto simile a quello di SHA-256 ma con un'importante differenza nella dimensione dei dati elaborati: la dimensione del blocco è di 1024 bit (non 512 bit), e l'algoritmo opera su parole a 64 bit (la parola memoria dimensione di molti processori moderni). In particolare, le operazioni aritmetiche, particolarmente ottimizzate su questi processori, vengono eseguite su 64 bit.

La struttura dell'algoritmo è la stessa di SHA-256 ma

il messaggio è suddiviso in blocchi di 1024 bit;
i numeri che compaiono (variabili h0,…, h7, costanti…) sono su 64 bit e l'addizione avviene modulo 2 64 ;
i valori delle inizializzazioni e delle costanti sono diversi (necessariamente poiché su 64 e non su 32 bit);
la funzione di compressione utilizza 80 giri (invece di 64);
la lunghezza del messaggio (in binario) aggiunto ad esso nella fase di riempimento (rafforzamento di Merkle-Damgård ) è un numero intero a 128 bit (big-endian) e non a 64 bit, che limita la dimensione teorica massima del messaggio a 2 128 bit invece di 2 64 bit;
i valori degli offset circolari e degli offset vengono modificati per tenere conto della nuova lunghezza delle parole.

SHA-384

La funzione SHA-384 è apparsa insieme a SHA-256 e SHA-512. Produce un hash a 384 bit . L'algoritmo è quello di SHA-512 con solo differenze

diversi valori per l'inizializzazione (variabili h0,…, h7);
un'uscita troncata a 384 bit (concatenazione dei contenuti delle prime 6 variabili h0,…, h5).

Crittanalisi

SHA-256 è diventato il nuovo standard consigliato per l'hashing crittografico dopo gli attacchi a MD5 e SHA-1 . Gli altri membri della famiglia SHA sono stati relativamente non crittografati rispetto a SHA-0 e SHA-1 . Nel 2003 , Helena Handschuh e Henri Gilbert hanno pubblicato un'analisi di SHA-256, 384 e 512. Il loro studio mostra che altri membri di SHA non sono influenzati dagli attacchi che erano stati dimostrati su altre funzioni hash ( MD4 , MD5 e SHA-1 tra gli altri). La crittoanalisi lineare e differenziale non si applica.

D'altra parte, i due crittografi hanno evidenziato punti deboli significativi sulle versioni modificate. Modificando le costanti oi parametri di inizializzazione per renderli simmetrici sostituendo l'aggiunta modulare con uno XOR , otteniamo un hash che produce un'impronta digitale simmetrica se anche il messaggio di input è simmetrico.

Riferimenti

vedi la pagina NIST Secure Hashing

Vedi anche

Bibliografia

(en) Henri Gilbert, Helena Handschuh: Analisi della sicurezza di SHA-256 e sorelle . Aree selezionate in crittografia 2003: 175-193
Versioni successive del NIST Secure Hash Standard dall'aspetto di SHA-2 (vedere anche la pagina Secure Hashing )
- Versione FIPS 180-2 diAgosto 2001
- FIPS 180-3 versione finale diottobre 2008
- FIPS 180-4 marzo 2012

link esterno

Calcolatrice in linea Codifica di stringhe di caratteri mediante le funzioni hash più utilizzate.
(it) Calcolatrice che genera SHA-256 online
(it) Calcolatrice che genera SHA-512 online
(fr) Un'implementazione open source in C ++ Contiene tutte le varianti dell'algoritmo.