Elementi di Crittografia

________________________________________

MAC e FUNZIONI HASH_______________________________

Alessandro Zeppi

Roberto Mottola

Fabio Felici

Andrea Rosati

Daniele Salvatori

Argomenti Trattati

Segretezza/Autenticazione Codici MAC Funzioni Hash Attacchi SHA Whirlpool

Due concetti importanti, ma distinti

SEGRETEZZA

AUTENTICAZIONE

La segretezza è garantita quandoi contenuti di un messaggio sonointellegibili solo a quelle persone e/o quei processi che sono in possesso della chiavecrittografica appropriata

L'autenticazione dei messaggiè una procedura che verifica che i messaggi ricevuti provengano dalla sorgente indicatae che non siano stati modificati

Funzioni per l'autenticazione

I protocolli di autenticazione dei messaggi sfruttano l'esistenza di funzioni che producono autenticatori, che verranno utilizzati dal destinatario per verificare l'autenticità del messaggio.

Queste funzioni sono raggruppabili in tre classi:

Crittografia dei messaggi Codice MAC ( Message Authentication Code) Funzione Hash

Crittografia simmetrica e autenticazione

Messaggio E

K

E(K,M) D

K

Messaggio

Il messaggio trasmesso dalla sorgente A alla destinazione B viene crittografato utilizzando una chiave segreta K condivisa da A e B.

La crittografia simmetrica garantisce segretezza e autenticazione:

– Nessun altro conosce la chiave

– Un estraneo che non conoscesse K non saprebbe come modificare il messaggio

Problema della crittografia simmetrica La destinazione accetterà qualsiasi messaggio

Al destinatario potrebbe essere necessario un mezzo automatico per determinare se il testo ricevuto sia un testo legittimo e se provenga da A

Altrimenti:

Crittografia a chiave pubblica e autenticazione

L'uso ordinario della crittografia a chiave pubblica garantisce la segretezza ma non l'autenticazione

Chiunque potrebbe usare la chiave pubblica di Bob per crittografare un messaggio qualsiasi ed inviarlo a Bob sostenendo di essere Alice

Vediamo una tecnica di autenticazione alternativa...

Codice MAC

L'idea alla base dei codici MAC è quella che per garantire l'autenticazione dei messaggi sia necessario creare dell'informazione aggiuntiva all'interno della comunicazione.

Questo checksum crittografico prende il nome di codice MAC e deve poter essere calcolato a partire da una chiave segreta K, condivisa da entrambe le parti (Alice & Bob)

Funzione MACChiave segreta condivisaMessaggio di input

MAC = C (K,M)

Contesto e requisiti È da sottolineare che il nostro obiettivo è

consentire l'autenticazione dei messaggi Ora non siamo interessati alla segretezza, quindi i

nostri messaggi stanno viaggiando in chiaro sul canale di comunicazione

È importante perciò che Alice utilizzi una nuova chiave per ogni comunicazione

In questo modo Eve non può inviare nuovamente un messaggio di Alice, in quanto Bob non lo accetterebbe (Replay Attack)

MAC: garantire la segretezza Alice vuole inviare un messaggio privato a Bob e

desidera che solo lui possa leggerlo. Inoltre vuole autenticare il messaggio

La scelta migliore è quella di crittografare il messaggio M e poi aggiungere il MAC al testo cifrato

In questo modo Bob può verificare il MAC prima di decrittare il messaggio:

Se questo fosse diverso dal MAC calcolato da Bob, allora non si perderebbe tempo a decrittare il messaggio

Impiego del MAC

Data Authentication Algorithm L'algoritmo può essere definito come una modalità CBC (Cipher

Block Chaining) di DES con un vettore di inizializzazione 0 (zero)

I dati (messaggi, record, file o programmi) da autenticare sono raggruppati in blocchi di 64 bit contigui: D

1,D

2,....,D

n

Utilizzando il DES, E e una chiave segreta K, il codice di

autenticazione DAC viene calcolato così:

O1 = E(K, D

1)

O2 = E(K, D

2O

1)

O3 = E(K, D

3O

2)

........

On = E(K, D

nO

n-1)

Data Authentication Algorithm

Il codice DAC è costituito dall'intero blocco On o dai primi M bit

del blocco, con 16 ≤ M ≤ 64

HASH

La funzione hash La funzione hash monodirezionale è una variante

del codice di autenticazione del messaggio MAC La funzione hash accetta come input un messaggio

M di lunghezza variabile e produce un output di lunghezza fissa chiamato codice hash H(M)

Il codice hash non utilizza una chiave ma è funzione solo del messaggio di input

Il codice hash è anche chiamato messagge digest.

La funzione hash Il codice hash è una funzione che considera tutti i

bit del messaggio e fornisce una funzionalità di rilevamento degli errori: una variazione in uno o più bit del messaggio produce una variazione nel codice hash;

La figura seguente illustra i vari modi in cui si può utilizzare un codice hash per garantire l'autenticazione del messaggio:

Le funzioni hash Un valore hash h viene generato da una funzione H

con la seguente forma: h=H(M); Il valore hash viene aggiunto al messaggio alla

sorgente nel momento in cui il messaggio viene considerato corretto;

Alla ricezione si autentica tale messaggio ricalcolando il valore hash. Poichè la funzione hash non è segreta, è necessario un modo per proteggere il valore hash.

Proprietà delle funzioni hash H può essere applicata a un blocco di dati di

qualsiasi dimensione; H produce un output di lunghezza fissa; H(x) è relativamente facile da calcolare,

consentendo un'implementazione sia HW che SW; Per un determinato valore h è computazionalmente

impossibile trovare un valore x tale che H(x)=h. Questa proprietà è detta monodirezionalità;

Proprietà delle funzioni hash Per un determinato blocco x è computazionalmente

impossibile trovare un valore y diverso da x tale che H(y)=H(x). Questa proprietà è chiamata resistenza debole alle collisioni;

E' computazionalmente impossibile trovare una coppia (x,y) tale che H(y)=H(x). Questa proprietà è chiamata resistenza forte alle collisioni.

Semplici funzioni hash L'input viene considerato come una sequenza di blocchi di n bit. L'input

viene elaborato un blocco alla volta in modo iterativo per produrre un valora hash di n bit.

Una delle funzioni hash più semplici è l'operazione di OR esclusivo bit a bit applicata a ciascun blocco. L'operazione può essere espressa così: Ci=bi1bi2 bim

Questa operazione produce un semplice bit di parità per ciascuna posizione di bit. Questo codice è noto come controllo di ridondanza longitudinale. E' efficace come controllo di integrità dei dati per dati casuali. Ogni valore hash di n bit è ugualmente probabile. Pertanto la probabilità che un errore

nei dati alteri il valore hash è pari a 2-n.

Semplici funzioni hash

Con dati strutturati in modo più prevedibile,la funzione è meno efficace!

Un modo semplice per migliorare le cose consiste nell'applicare uno scorrimento circolare, ovvero una rotazione, sul valore hash dopo aver elaborato ciascun blocco;

Questo ha l'effetto di “casualizzare“ l'input ovvero di eliminare ogni regolarità presente nell'input.

ATTACCHI

Paradosso del compleanno

La probabilità che in un gruppo di k persone ne esistano almeno due che sono nate lo stesso giorno aumenta velocemente con l’aumentare di k

Con k=23 si ottiene una probabilità del 50%

Tipi di attacchi

Gli attacchi possono essere divisi in due categorie: forza bruta

Si effettua una ricerca esaustiva dei possibili valori fino a trovare quello desiderato. L’attacco a compleanno rientra in questa categoria

analisi crittografica

Si sfruttano certe proprietà dell’algoritmo per svolgere attacchi diretti senza effettuare una ricerca esaustiva

Attacco a compleanno(1/2)

Esempio di un attacco basato sul paradosso del compleanno: Alice si prepara a “firmare” un messaggio m, aggiungendo il relativo codice

hash (lungo n bit) crittografato con la propria chiave privata

Eve genera varianti di m, tutte con lo stesso significato. Prepara inoltre un uguale numero di varianti del messaggio fraudolento da sostituire al vero messaggio

Per il paradosso del compleanno Eve ha una probabilità del 50% di trovare una coppia di messaggi (variante vera, variante fraudolenta) con lo stesso codice hash

Eve offre la variante valida ad Alice per la firma. Poiché le due varianti hanno lo stesso codice hash, produrranno la stessa firma; ciò permetterà ad Eve di sostituire il messaggio firmato da Alice con uno fraudolento senza dover conoscere la chiave segreta di Alice

Attacco a compleanno(2/2)

Concatenamento a blocchi

Tecnica di hash proposta da Rabin negli anni '70:si suddivide M in n blocchi di uguale lunghezza e si utilizza un algoritmo di cifratura simmetrico (es. DES) per calcolare H(M)

H0 = Valore inizialeH

i = E(M

i,H

i-1)

G = Hn

Questa tecnica è sicura nella misura in cui è sicuro l'algoritmo di cifratura utilizzato

Il messaggio funge da chiave per DES

É vulnerabile inoltre all'attacco Meet-in-the-middle

Attacco Meet-in-the-middle(1/2)

Si suppone che Eve abbia intercettato un messaggio in chiaro con relativo hash crittografato (sono noti M e E(K,H(M))

1. Usando l'algoritmo visto in precedenza si calcola il codice hash non crittografato G lungo m bit

2. Si costruisce il messaggio contraffatto Q1,Q

2,...,Q

n-2

3.Si calcola Hi = E(Q

i,H

i-1) per 1 ≤ i ≤ n-2

Attacco Meet-in-the-middle(2/2)

Si suppone che Eve abbia intercettato un messaggio in chiaro con relativo hash crittografato (sono noti M e E(K,H(M))

4. Si generano 2m/2 blocchi casuali, per ogni blocco X calcolo E(X,H

n-2). Si generano ulteriori 2m/2 blocchi casuali, per ogni

blocco Y calcolo D(Y,G), dove D è la funzione inversa di E

5. Per il paradosso del compleanno ho una probabilità del 50% di trovare un X e un Y per cui E(X,H

n-2) = D(Y,G)

6. Si costruisce infine M' = Q1,Q

2,...,Q

n-2,X,Y e si ottiene H(M')

= H(M) = G

Funzioni hash sicure(1/2)

La maggior parte delle funzioni hash crittografiche adottano la struttura iterata proposta da Merkle e Damgard all'inizio degli anni '80

Funzioni hash sicure(2/2)

Merkle e Damgard hanno dimostrato che se la funzione di compressione f è resistente alle collisioni allora lo è anche H (non vale il contrario)

Il problema della progettazione di funzioni hash sicure si è quindi ridotto alla progettazione di funzioni di compressione resistenti alle collisioni che operano su un input di dimensioni fisse

L'analisi crittografica studia il funzionamento della funzione f per cercare di ottenere collisioni con un'unica esecuzione di f

La tecnica più utilizzata è l'analisi differenziale che cerca di individuare come le modifiche sul messaggio influiscano sul codice hash

SHA

Un po' di storia

L'algoritmo SHA (Secure Hash Algorithm) è stato sviluppato dal NIST (National Institute of Standards and Technology) e pubblicato nel 1993 come standard. (SHA-0)

Nel 1995 è stata emessa una versione aggiornata, chiamata normalmente SHA-1

SHA-1 viene considerato poco sicuro e nel 2002 NIST ha emesso una versione aggiornata dello standard; SHA-2

SHA-224, SHA-256, SHA-384, SHA-512

Confronto dei parametri SHA

SHA-1 SHA-224 SHA-256 SHA-384 SHA-512

Lunghezza del codice digest 160 224 256 384 512

Lunghezza del messaggio <264 <264 <264 <2128 <2128

Dimensioni del blocco 512 512 512 1024 1024

Lunghezza della parola 32 32 32 64 64

Numero di passi 80 64 64 80 80

Sicurezza 80 112 128 192 256

La logica di funzionamento di SHA-512

Passo 1: aggiunta dei bit di riempimento Passo 2: aggiunta della lunghezza Passo 3: inizializzazione del buffer hash Passo 4: elaborazione del messaggio in

blocchi di 1024 bit Passo 5: output

Passo 1: aggiunta dei bit diriempimento

Il messaggio viene esteso in modo che la sua lunghezza sia congruente a 896 modulo 1024

Questi bit vengono sempre aggiunti, anche se il messaggio è della lunghezza desiderata

Il numero di bit di riempimento sarà sempre compreso fra 1 e 1024

I bit di riempimento sono costituiti da un bit a “1” seguito da una sequenza di bit a “0”

Passo 2: aggiunta della lunghezza

Al messaggio viene aggiunto un blocco di 128 bit che rappresenta la lunghezza del messaggio originario (prima dell'operazione di riempimento)

Il risultato dei primi due passi consiste in un messaggio di lunghezza multipla di 1024 bit

Passo 3: inizializzazione delbuffer hash

Per contenere i risultati intermedi e finale della funzione hash viene utilizzato un buffer di 512 bit

Il buffer viene rappresentato come un insieme di otto registri da 64 bit (A,B,C,D,E,F,G,H)

Passo 3: inizializzazione delbuffer hash

I registri vegono inizializzati con i seguenti valori (notazione esadecimale):

A = 6A09E667F3BCC908 B = BB67AE8584CAA73B C = 3CEF372FE94F82B D = A54FF53A5F1D36F1 E = 510E527FADE682D1 F = 9B05688C2B3E6C1F G = 1F83D9ABFB41BD6B H = 5BE0CD19137E2179

Passo 4: elaborazione del messaggio in blocchi di 1024 bit

Passo 4: elaborazione del messaggio in blocchi di 1024 bit

Passo 4: elaborazione del messaggio in blocchi di 1024 bit

Il cuore dell'algoritmo è costituito da 80 fasi

Ogni fase prende come input il valore ABCDEFGH del buffer a 512 bit e aggiorna il contenuto

Ogni fase t utilizza il valore Wt di 64 bit

derivato dal blocco di 1024 bit in elaborazione (M

i)

Ogni fase utilizza una costante additiva K

t (0t

L'output dell'ultima fase viene aggiunto all'input della prima fase (H

i-1) per

produrre Hi

Passo 4: elaborazione del messaggio in blocchi di 1024 bit

Passo 4: elaborazione del messaggio in blocchi di 1024 bit

Passo 5: output

Dopo che sono stati elaborati tutti gli N blocchi da 1024 bit, l'output dello stadio N-esimo è il codice digest di 512 bit

Hash di esempio

Questo è un esempio di digest generato dallo SHA-1: “Cantami o diva del pelide Achille l'ira funesta” →

1F8A690B7366A2323E2D5B045120DA7E93896F47

Anche una minima variazione del messaggio genera un hash completamente differente a causa di una reazione a catena nota come effetto valanga

“Contami o diva del pelide Achille l'ira funesta” → E5F08D98BF18385E2F26B904CAD23C734D530FFB

Sha-3 (in sviluppo) Nel 2007 il NIST ha aperto un concorso per

scegliere quello che diventerà SHA-3 e prenderà il posto di SHA-*

Tutti i gruppi partecipanti hanno presentato la loro ricerca entro il 31 Ottobre 2008 e in questi mesi sono stati annunciati i 5 algoritmi finalisti

Per avere un vincitore dovremo attendere fino al 2012

Sono aperte le scommesse!

WHIRLPOOL

Whirlpool

Funzione hash

Cifratura a blocchi come funzione di compressione

Codice hash di 512 bit

La cifratura a blocchi può essere implementata sia in software che con hardware

La cifratura a blocchi

La logica di Whirlpool

1. Aggiunta dei bit di riempimento

2. Accodamento della lunghezza

3. Inizializzazione della matrice hash

4. Elaborazione del messaggio in blocchi di 512 bit

Aggiunta dei bit di riempimento

• Il messaggio viene esteso in modo che la sua lunghezza sia un multiplo dispari di 256

• Operazione effettuata anche nel caso in cui il messaggio sia della lunghezza desiderata

• Un singolo bit di valore 1 seguito dal numero necessario di bit 0

Accodamento della lunghezza

• Viene aggiunto in coda al messaggio un blocco di 256 bit

• Intero senza segno di 256 bit

• Indica la lunghezza in bit del messaggio originale

Inizializzazione della matrice hash

Per memorizzare i risultati intermedi e finale della funzione hash viene utilizzata una matrice 8 x 8 byte, inizializzata con valori nulli

La logica di Whirlpool

Algoritmo di cifratura a blocchi

Rappresentazione dei blocchi

L’ordinamento dei byte nella matrice è per riga

Substitute Byte

Tabella di lookup

Shift Columns

• Rotazione circolare verso il basso di ciascuna colonna

• La prima colonna non viene ruotata

• Ogni byte viene spostato da una riga a un’altra distante un multiplo di 8 byte

• Gli 8 byte di ogni riga vengono dispersi in 8 righe differenti

Mix Rows

Permette di ottenere la diffusione separatamente in ciascuna rigaOgni byte di una riga viene mappato in un nuovo valore che è funzione di tutti gli 8 byte della medesima rigaLa trasformazione è definita tramite moltiplicazione tra matrici:

B=AC

Mix Rows

Add Key

Calcola lo XOR bit-a-bit fra i 512 bit di CState e i 512 bit della chiave di fase

Espansione della chiave

• Ottenuta utilizzando la cifratura a blocchi stessa

• Usa una costante di fase che agisce da chiave di fase per l’espansione

• La costante per la fase r è una matrice RC[r] in cui solo la prima riga non è nulla

• Ogni elemento della prima riga è un mapping che utilizza la S-box

Prestazioni di Whirlpool

• Usa gli stessi blocchi funzionali di AES ed ha la medesima struttura

• Prestazioni e caratteristiche di occupazione di memoria simili ad AES

• Rispetto a SHA-512 richiede più risorse hardware ma raggiunge prestazioni notevolmente superiori

Riferimenti

W. Stallings. Crittografia e Sicurezza delle

Reti. McGraw-Hill, 2004.

Grazie per l'attenzione!