Digital Signature Standard
Corso di Sicurezza
2008/2009
Golinucci Thomas
Zoffoli Stefano
Gruppo 11
Firme digitali
1. Introduzione.
2. Caso d’uso e digitalizzazione.
3. Firme digitali e possibili attacchi.
4. Manuali vs Digitali.
5. Schemi di firme.
6. Definizione e Sicurezza.
7. Cenni storici – ElGamal, Schnorr.
8. Standardizzazione - DSS.
9. Fasi dell’algortimo – Generazione chiavi, Firma, Verifica.
10. Correttezza dell’algortimo.
11. Pro e contro.
12. Revisioni e Varianti.
Digital Signature Standard
Introduzione
“Verità assoluta”
“In molte circostanze che si presentano quotidianamente – prelievo di soldi, firme
di contratti, ecc… – una firma convenzionale viene apposta su un documento.
Tale firma permette di specificare la persona responsabile del documento che è
stato firmato.”
Digital Signature Standard
Caso d’uso
M
(M, Firma di M)
Moggi
Pairetto
Qualsiasi riferimento a persone
o cose è puramente casuale.
Galliani
Digital Signature Standard
Digitalizzazione
Idea!
Trasformare la firma in una sequenza di bit e appenderla alla
fine del documento da firmare.
Documento
Firma
Digital Signature Standard
Firme digitali
La firma digitale, o firma elettronica qualificata, basata sulla tecnologia
della crittografia a chiavi asimmettriche, è un sistema di autenticazione di dati
digitali.
Si basa sull’uso di un certificato digitale memorizzato su di un dispositivo
hardware.
Le proprietà che una firma digitale deve vantare sono:
1
• Facilmente
producibile dal
proprietario.
2
• Impossibile da
riprodurre da
altri utenti.
3
Esigenza di trovare schemi di firme sicuri da possibili attacchi.
Digital Signature Standard
• Facilmente
verificabile da
chiunque.
Possibili attacchi
La sicurezza di uno schema di firme deve essere testata a fronte dei seguenti tipi di
attacchi:
KEY-ONLY ATTACK
TOTAL BREAK
• l’attaccante conosce solo la chiave
pubblica
• ottenere la chiave privata del
firmatario
KNOW-MESSAGE ATTACK
SELECTIVE FORGERY
• l’attaccante conosce la chiave
pubblica più alcuni messaggi
firmati
• generare da un messaggio una
firma tale che una verifica dia
esito positivo con la chiave
pubblica di un’altra persona
CHOSEN-MESSAGE ATTACK
• l’attaccante può scegliere
messaggi di cui ottenere la firma
EXISTISTENTIAL FORGERY
• generare una coppia (M, F) tale
che una verifica dia esito positivo
con la chiave pubblica di un’altra
persona
Digital Signature Standard
Firme manuali vs digitali
FIRMA MANUALE
FIRMA DIGITALE
CREAZIONE
Manuale
Mediante algoritmo di
creazione
APPOSIZIONE
Sul documento: la
firma è parte
integrante del
documento
Come allegato: il
documento firmato è
costituito dalla coppia
(documento, firma)
VERIFICA
Confronto con una
firma autenticata:
metodo insicuro
Mediante algoritmo di
verifica: metodo
sicuro
Distinguibile
Indistinguibile
Illimitata
Limitata
Non possibile
Possibile
DOCUMENTO
COPIA
VALIDITÀ
TEMPORALE
AUTOMAZIONE DEI
PROCESSI
Digital Signature Standard
Schemi di firme
Un tipico schema di firma digitale è basato su tre algoritmi:
1. Un algoritmo per la generazione della
chiave che produce una coppia di chiavi
(Pk, Sk).
(Pk, Sk)
2. Un algoritmo di firma SIGSk che dato
il documento da firmare M e la chiave Sk
produce la firma digitale F = SIGSk(M).
SIGSk
3. Un algoritmo di verifica VERPk che
data la coppia (M, F) e la chiave Pk
risponde se la firma sia autentica o meno.
VERPk
Digital Signature Standard
Schemi di firme - Firma
Digital Signature Standard
Schemi di firme - Verifica
Digital Signature Standard
Schemi di firme - Definizione
Uno schema di firme digitale è una quintupla (P, A, K, S, V) dove le seguenti
condizioni sono soddisfatte:
P è un insieme finito di possibili messaggi;
A è un insieme finito di possibili firme;
K, lo spazio delle chiavi, è un insieme finito di possibili chiavi;
Per ogni k ∈ K c’è un algoritmo di firma SIGSk ∈ S e un corrispondente algoritmo
di verifica VERPk ∈ V .
SIGSk e VERPk devono essere funzioni facili da calcolare per una maggiore
efficienza della schema, mentre dovrebbe essere computazionalmente difficile per
“Galliani” falsificare la firma di “Moggi” su di un messaggio M.
Dato M, solo “Moggi” deve essere in grado di calcolare una firma F tale che
VERPk(M,F) = vero.
Digital Signature Standard
Schemi di firme - Sicurezza
Uno schema di firme è detto incondizionatamente sicuro se, qualunque siano
le risorse di “Galliani” (tempo e hardware), è impossibile falsificare firme.
Uno schema non può essere incondizionatamente sicuro poiché un
malintenzionato potrebbe testare tutte le possibili firme di un documento di un
utente usando l’algoritmo VERPk fino a quando non trova la giusta firma.
Naturalmente questo tipo di attacco risulta essere computazionalmente
oneroso poiché si fa in modo che la cardinalità dell’insieme di possibili firme sia
enormemente elevata.
Dato sufficiente tempo “Galliani” può sempre riuscire a falsificare la firma di
“Moggi”, così il nostro scopo è di individuare schemi che sia computazionalmente
sicuri.
Digital Signature Standard
DSS – A cavallo del millennio
Algoritmo di ElGamal:
estensione dell’algoritmo di DiffieHellman;
cifratura asimmetrica con chiave di
sessione generata dinamicamente e
scambiata, come in D-H, insieme
al messaggio.
DSS:
1985
1993
Time line.
1991
Algoritmo di Schnorr:
analogo a ElGamal;
introduce una funzione di hash che
associa a ciascun messaggio e a
ciascuna chiave un intero in un
intervallo di ampiezza predefinita.
variante dell’algoritmo di Schnorr;
la funzione di hash ha come unico
argomento il messaggio e quindi il
suo valore non dipende dalla
chiave di cifratura.
Bozza
3° revisione
DSS
2008
1996
2000
1° revisione
DSS
2° revisione
DSS
Digital Signature Standard
DSS – NIST & FIPS
Il NIST (National Institute of Standards and Technology) propose il DSA come
standard FIPS (Federal Information Processing Standard).
DSA = Digital Signature Algorithm
DSS = Digital Signature Standard
NIST – Agenzia del governo USA il cui compito è quello di sviluppare standard,
tecnologie e metodologie che favoriscano la produzione e il commercio.
Pubblica i FIPS, documenti governativi che descrivono lo standard che gli apparati
e le agenzie del governo (escluse quelle militari) devono seguire.
Sono spesso delle varianti rispetto a quelli ANSI, ISO, IEEE, ecc…
Esempi di standard FIPS: DES, AES, ecc…
Digital Signature Standard
DSS – Generazione delle Chiavi
Il DSS si basa sull’intrattabilità del logaritmo discreto.
y = gx mod p
Numero primo di 160 bit.
Divisore di p-1.
p = qz + 1
p - 1 = qz
z = (p - 1) / q
(p, q, g
Numero primo la cui
lunghezza in bit è compresa
nell’intervallo [512, 1024],
multipla di 64.
y) = Public key
x) = Secret key
g = hz mod p
con h ∈ ]1, p-1[
eg>1
Digital Signature Standard
Numero random
∈ ]0, q[
DSS – Firma
k viene generato
per ogni Msg
k ∈ ]0, q[
Numero random
p
q
g
(gk mod p) mod q
Msg
SHA
(k-1(SHA(Msg) + xr)) mod q
q
x
Digital Signature Standard
r è indipendente da Msg
r
s
La firma è (r,s)
DSS – Verifica
Msg’
(r’, s’)
Firma
IF 0 < r’ < q AND 0 < s’ < q
SHA
False
True
w = s’-1 mod q
α = (SHA(Msg) w) mod q
β = (r’ w) mod q
v = (gα yβ mod p) mod q
IF v = r’
False
True
Firma verificata
Digital Signature Standard
Firma
rifiutata
DSS – Correttezza
g è di ordine q?
(1)
piccolo teorema di Fermat
dato
z = (p – 1) / q
con p e q primi
gq mod p = hqz mod p = hp-1 mod p = 1 mod p
g = hz mod p
dato
gq mod p = 1 mod p
con h ∈ ]1, p-1[
m mod q = n mod q
gm mod p = gn+kq mod p
= (gn gkq) mod p
= ((gn mod p) (gq mod p)k) mod p
= gn mod p
Digital Signature Standard
DSS – Correttezza
r’ = v ?
(2)
w = s’-1 mod q
s’ = (k-1(SHA(Msg) + xr’)) mod q
dato
k = (SHA(Msg)s’-1+ xr’s’-1) mod q = (SHA(Msg)w + xr’w) mod q
y = gx mod p
vedi formula
dato
r’ =
gk mod p mod q = gSHA(Msg)w gxr’w mod p mod q = gSHA(Msg)w yr’w mod p mod q
α = (SHA(Msg) w) mod q
β = (r’ w) mod q
gSHA(Msg)w yr’w mod p mod q = gα yβ mod p mod q
Digital Signature Standard
=v
DSS – Sicurezza
1) Total Break con Key-only Attack è impossibile.
• Risalire ad x richiede la risoluzione del logaritmo discreto.
2) Selective Forgery con Key-only Attack è impossibile.
• Data Msg e scelto a caso r, bisogna calcolarsi s; tuttavia non
essendo noto x quest’operazione equivale a risolvere anch’essa
un logaritmo discreto.
3) Existential Forgery con Key-only Attack è impossibile.
• Anche generando a caso la firma, per risalire al messaggio
corrispondente bisognerebbe invertire una funzione hash .
Digital Signature Standard
DSS – Critiche
1) DSS non può essere usato per cifrare o per distribuire chiavi.
2) La misura del modulo p è troppo piccola.
3) La scelta della tripla (p, q, g) può essere causa di vulnerabilità.
4) DSS è più lento di RSA.
5) DSS ha “test of time” inferiore a RSA.
Digital Signature Standard
DSS – Revisioni
FIPS 186-1:
E' la revisione del protocollo DSS avvenuta nel 1996.
L'unica modifica è che impone l'utilizzo di SHA-1 anziché SHA.
FIPS 186-2:
E' la revisione del protocollo DSS avvenuta nel 2000.
Propone l'utilizzo di ECDSA oltre a DSA.
Impone la lunghezza in bit di p pari a 1024.
Corregge gli algoritmi per il calcolo di x e k.
FIPS 186-3 (bozza):
E’ una bozza della nuova revisione proposta nel Novembre 2008.
Impone l’utilizzo di SHA-224/256/384/512.
Aumenta la lunghezza in bit di q a 224, con lunghezza in bit di p pari a 2048,
oppure a 256, con lunghezza in bit di p pari a 3072.
Digital Signature Standard
DSS – Varianti
ECDSA (Elliptic Curve DSA):
Opera su gruppi di curve ellittiche.
Ha lo stesso tempo di esecuzione di DSA producendo firme di lunghezze identiche
ma con parametri di sicurezza più alti.
Una firma DSA ottenuta con p di 1024 bit e q di 160 bit è equivalente ad una firma
ECDSA con parametro principale a 160 bit.
GoSt R DSA (Gosudarstvennyi Standard of Russian Federation):
Nato nel 1995 presso la federazione Russa.
Imposta la chiave q a 256 bit al posto di 160.
Cambia l’equazione di verifica della firma digitale.
Digital Signature Standard
Bibliografia
FIPS PUB 186 –DIGITAL SIGNATURE STANDARD (DSS), NIST,
http://www.itl.nist.gov/fipspubs/fip186.htm;
Network Security – PRIVATE Communication in a PUBLIC World,
Charlie Kaufman, Radia Perlman, Mike Speciner, Prentice Hall Editions;
Internet Security – Reti e dati a prova di hacker, Maurizio Cinotti, Hoepli
Informatica;
Crittografia – Principi, Algoritmi, Applicazioni, Paolo Ferragina, Fabrizio
Luccio, Bollati Boringhieri;
Sicurezza dei sistemi informatici, Mariagrazia Fugini, Fabrizio Maio,
Pierluigi Plebani, Apogeo;
Sicurezza in informatica, C. Pfleeger, S. Pfleeger, Pearson Italia;
http://en.wikipedia.org.
Digital Signature Standard
Digital Signature Standard
Corso di Sicurezza
2008/2009
Golinucci Thomas
Zoffoli Stefano
Gruppo 11