Universita' di Ferrara
Facolta' di Scienze Matematiche, Fisiche e Naturali
Laurea Specialistica in Informatica
Algoritmi Avanzati
Funzioni Hash e Network Security
Vedi:
• A.S. Tanenbaum, Computer Networks, 4th ed., Prentice Hall: sez. 8, pagg. 721771.
(le figure delle dispense sono tratte da questo libro)
Copyright © 2007-2009 by Claudio Salati.
Lez. 13a
1
Firma digitale
• Uno dei problemi di sicurezza dei sistemi digitali ed in paticolare delle
reti di calcolatori e’ legato all’autenticazione e al non ripudio di un
documento.
• Quando compro una casa la mia firma garantisce la mia identita' e
anche che io non possa ritrattare quanto stabilito.
• "For computerized message systems to replace the physical transport
of paper and ink documents, a method must be found to allow
documents to be signed in an unforgeable way." (Tanenbaum)
• Basandosi sulla firma digitale
• Il ricevente deve poter autenticare l'identita' proclamata del mittente.
• Il mittente non deve poter ripudiare come non proprio il contenuto di
un messaggio (e.g. un documento firmato e' inalterabile).
• Ne' il ricevente ne' nessun altro deve essere in grado di contraffare
un documento spacciandosi per il mittente (e.g. imitando o
trasportando la firma).
2
Firma digitale: 3 approcci
• Firma a chiave simmetrica
• Si basa sull'esistenza di una autorita' centrale (notaio) che faccia
da garante (partecipando attivamente) in tutte le transazioni.
• Ogni parte comunica solo con il notaio, usando un sistema di
cifratura simmetrico (ogni parte ha la propria chiave segreta, il
notaio conosce le chiavi di tutte le parti).
• Firma a chiave pubblica
• Elimina la necessita' di una autorita' centrale.
• Si basa sul fatto che il cifrario RSA ha la proprieta' che E(D(P))=P
(e' ovviamente vero che D(E(P))=P).
• Ne esiste anche una versione (DSS, Digital Signature Standard,
NIST 1991) basata su un diverso algoritmo di cifratura a chiave
pubblica (algoritmo di El Gamal).
• Message digest
• Consente di firmare un messaggio senza doverlo necessariamente
cifrare.
3
• Si basa sull'uso di funzioni hash.
Firma a chiave simmetrica
• Alice vuole mandare il plaintext P a Bob.
• Per farlo Alice manda al notaio BB il messaggio 1 (parzialmente cifrato):
• t e' un timestamp.
• RA e' un numero random scelto da Alice.
Queste informazioni addizionali servono ad evitare (con l'aiuto di Bob) che un
intruso possa registrare e ripetere un messaggio: t protegge dalla ripetizione di
messaggi vecchi, RA protegge dalla ripetizione di messaggi recenti.
• Il notaio decifra il messaggio di Alice (riuscire a decifrarlo con la chiave di Alice e'
la garanzia che provenga davvero da lei) e genera verso Bob il messaggio 2.
• Riuscire a decodificare il messaggio con la propria chiave garantisce a Bob che il
mittente sia il notaio. KBB(A, t, P) e' la firma digitale del messaggio.
4
Firma a chiave pubblica
• La necessita' di una autorita' centrale rende la firma a chiave simmetrica poco
conveniente:
• Il notaio deve essere sempre in linea e non rappresentare un collo di
bottiglia.
• Il notaio deve essere affidabile (e.g. non rilasciare firme false, garantire la
segretezza delle chiavi) e le persone devono essere disposte a credergli.
• Il sistema di cifratura a chiave pubblica rende inutile il notaio.
• Se Alice invia a Bob il messaggio EB(DA(P)), questo e' intrinsecamente la propria
firma digitale.
• Bob verifica che il mittente sia proprio Alice perche' riesce a decrittare DA(P)
5
utilizzando la chiave pubblica di Alice (P= EA(DA(P))).
Message digest
• Anche la firma digitale a chiave pubblica presenta alcuni problemi:
• Rende difficile il cambio della propria chiave (oppure richiede la
gestione di un registro storico centralizzato delle chiavi).
• Costringe a crittare messaggi che potrebbero essere trasmessi in
plaintext, con il costo aggiuntivo collegato.
• Una firma digitale a message digest si basa su questo principio:
 Non c'e' necessita' di poter decifrare la firma. L'importante e' che la
firma sia in relazione (praticamente) biunivoca con il messaggio.
• Questo tipo di firma si basa sull'uso di funzioni hash, come quelle che
vengono utilizzate per la realizzazioni di hash table. La funzione MD(P)
deve essere tale per cui:
1. e' facile da calcolare (bassa complessita' computazionale)
2. dato MD(P) e' praticamente impossibile risalire a P
3. dato P e' in pratica impossibile trovare un P' tale che MD(P') = MD(P)
4. una variazione qualunque di P produce un valore diverso di MD()
• Per soddisfare il terzo criterio deve essere sizeof(MD())  128 bit.
6
Message digest
• Computing a message digest from a piece of plaintext is much faster
than encrypting that plaintext with a public-key algorithm.
• In un sistema a firma con chiave simmetrica
• La firma KBB(A, t, P) viene sostituita con la firma KBB(A, t, MD(P)).
• In un sistema a firma con chiave pubblica
• La firma puo essere disaccoppiata dal messaggio.
• Il messaggio P puo' essere inviato o come plaintext o cifrato.
• La firma e' costituita da DA(MD(P)).
• Il mittente non puo' ripudiare il messaggio in quanto il ricevente non
sarebbe in grado di forgiare la firma.
• In ogni caso
• Il ricevente e' garantito dell'identita' del mittente in quanto calcolando
MD(P) ottiene lo stesso valore trasportato dal messaggio nella firma
digitale (che il ricevente e' in grado di decrittare).
7
Message digest
KB(A, RA, t, P, KBB(A,
t, MD(P)))
Message digest in sistema di firma a chiave simmetrica (messaggio cifrato)
Message digest in sistema di firma a chiave pubblica (messaggio non cifrato)
Esistono due algoritmi canonici per il calcolo di message digest:
• MD5 (Rivest 1992), di dimensione 128 bit
• SHA-1 (NSA, standard NIST FIPS 180-1), di dimensione 160 bit
8
Controllo d'integrita'
• Supponiamo di avere due parti che
• si fidano reciprocamente l'una dell'altra,
• condividono una chiave sicura,
• non hanno esigenze di confidenzialita', ma
• vogliono essere sicure che i messaggi che ricevono
• siano stati generati dalla controparte e non da un intruso,
• non abbiano subito alterazioni da parte di un intruso.
• Quello che stiamo cercando e' un Message Authentication Code
(MAC) che sia non forgiabile da un intruso e che possa essere affiancato
al plaintext per autenticarlo.
• Una maniera di creare un MAC in queste condizioni e' quella di:
• calcolare il ciphertext del messaggio con un algoritmo simmetrico in
modalita' CBC (utilizzando la chiave sicura);
• utilizzare l'ultimo blocco del ciphertext come MAC da affiancare al
plaintext.
• Questo procedimento costringe pero' a pagare il costo della cifratura.
9
HMAC
• Nelle ipotesi che abbiamo indicato e' pero' possibile generare un MAC
senza effettuare alcuna operazione di cifratura ma attraverso il calcolo
(molto piu' semplice) di un Message Digest.
• Un MAC di questo genere e' chiamato HMAC (Hashed MAC).
• Un HMAC e' calcolabile semplicemente :
1. Concatenando la chiave segreta condivisa al plaintext;
2. Applicando una delle funzioni hash MD() al testo cosi' ottenuto.
• RFC 2104 definisce lo standard per HMAC
• in modo indipendente dall'algoritmo di hash (e.g. MD5 o SHA-1),
• specificando una opportuna funzione di combinazione della chiave
simmetrica con il plaintext.
• Un intruso:
• non puo' forgiare alcun testo legittimo perche' non conosce la chiave
segreta.
• non puo' risalire alla chiave segreta perche' la funzione hash non e'
invertibile (non consente di risalire dal digest al testo originario). 10