Docente: Giuseppe Scollo
Università di Catania, sede di Comiso (RG)
Facoltà di Scienze Matematiche, Fisiche e Naturali
Corso di Studi in Informatica applicata, AA 2007-8
problema: nella comunicazione attraverso un mezzo trasmissivo, come pure nella memorizzazione in un supporto fisico, una sequenza binaria è suscettibile di alterazioni, accidentali o meno, che possono corrompere l'informazione rappresentata
soluzione: estendere la sequenza con informazione di controllo di errore, efficace per la rivelazione di errori (in certi limiti), e magari anche per la loro correzione (in limiti più ristretti)
esempi:
per configurazioni binarie di uguale lunghezza, distanza di Hamming :
un codice con distanza di Hamming 2n+1
permette di
rivelare fino a
2n errori, e di
correggere fino a
n errori,
nella trasmissione o memorizzazione della codifica di un simbolo
la crittografia è utile a garantire che ad un testo non siano state apportate alterazioni indebite, ovvero a rilevare il contrario, con i seguenti vantaggi rispetto ai codici di Hamming:
un codice di hash crittografico è una funzione del testo che gode di una proprietà fondamentale:
altre proprietà caratterizzano classi specifiche di funzioni di hash (v. appresso)
le funzioni di hash di solito codificano il testo, di lunghezza
arbitraria, in un riassunto
(digest, checksum, hash)
di lunghezza fissa:
l'acronimo sta per Manipulation Detection Code
a differenza dei CRC, i codici MDC proteggono da attacchi intenzionali all'integrità
l'output h(x) di una funzione di hash dev'essere di facile calcolo
l'output di una funzione MDC è di lunghezza fissa, per input di lunghezza arbitraria: proprietà di compressione → sono inevitabili le collisioni: x ≠ y , h(x) = h(y)
vulnerabilità:
il paradosso del compleanno
una funzione di hash MDC generalmente gode di una o più delle seguenti proprietà:
una semplice tecnica per la costruzione iterativa di funzioni di hash, detta di Merkle-Damgård si basa su una funzione di compressione f che, applicata alla concatenazione di due sequenze binarie di uguale lunghezza, produce un output di lunghezza uguale a quella di ciascuna delle due sequenze in input
l'iterazione si avvia con un valore iniziale h0 prefissato dell'hash, di lunghezza uguale a quella di ciascun blocco xi in cui viene sequenzialmente suddiviso l'input
la costruzione iterativa è quindi definita come segue, dove || designa concatenazione:
altre costruzioni iterative adoperano diversi operatori di combinazione, specie nel caso di crittografia con chiave, di cui appresso
la garanzia di integrità di un messaggio non ne assicura l'autenticità dell'origine
i codici MAC sono progettati per rimuovere tale vulnerabilità, proteggendo integrità e autenticità, mediante una chiave segreta usata per la generazione dell'output di hash:
per essere efficace, un MAC deve soddisfare l'ulteriore proprietà di resistenza al calcolo:
si derivano algoritmi MAC da algoritmi MDC mediante varie costruzioni, e.g. HMAC, v. fonti HMAC per approfondimenti
funzioni di hash più in uso:
entrambe ottenute mediante costruzione Merkle-Damgård
nel 2005 è stato dimostrato che né MD5 né SHA-1 posseggono la resistenza alle collisioni (proprietà P3)
SHA-1 è adoperato in vari protocolli standard di sicurezza: TLS, SSL, PGP, SSH, S/MIME, IPsec
le varianti SHA-2 sono algoritmicamente simili a SHA-1, quindi il NIST ha pubblicato un bando per la determinazione di un nuovo standard SHA-3, secondo modalità simili a quelle che hanno condotto alla selezione di AES