Luciano Margara
[email protected]
http://www.cs.unibo.it/~margara
Ufficio: Via Malaguti 1/b
Tel: 051 209 4886
Una Panoramica
del corso.
Obiettivo:
Comunicazioni private in
ambienti pubblici
Strumento: Cifrari
Esiste un cifrario perfetto ?
• Perfetto ~ inattaccabile.
La risposta è né SI né NO !!
• Esistono cifrari perfetti ma inefficienti
• Esistono cifrari pratici non perfetti ma efficienti
• Robustezza
• Conquistata sul campo
• Relazione con problemi matematici difficili
• Difficoltà di risoluzione
– impossibilità: NO
– improponibilità: SI
Alcune Definizioni
• Crittologia:
Crittografia + Crittoanalisi
• Crittografia: progetto di cifrari sicuri
ed efficienti.
• Crittoanalisi: metodi, strumenti e
tecniche per attaccare i cifrari (valutare
la loro bontà).
Lo Scenario
Mitt
c
c
…
Dest
Q ui ck Ti m e ™ an d a T I FF ( U nc om p r es se d) de co m pr e ss or ar e n ee de d t o se e t hi s pi ct u re .
X
Mitt = mittente del messaggio m in chiaro
Dest = destinatario del crittogramma c
X = impostore che ascolta (crittoanalista)
C e D funzioni di cifratura e decifrazione
L’intruso X
• Motivo: curiosità, spionaggio, malvagità,…
• Ruolo
– Passivo: si limita ad ascoltare
– Attivo: può inserirsi nella comunicazione o
modificarla
• Informazioni in suo possesso:
– Cipher-text attack: serie di crittogrammi c1,…., cn
– Known plain-text attack: collezione di coppie
(mi, ci)
– Chosen plain-text attack: collezione di coppie
scelte
Definizioni e Notazione
• Funzione di cifratura
• C(m) = c
è il crittogramma
• Funzione di decifrazione
• D(c) = m
è il messaggio in chiaro originale
• Matematicamente D è l’inversa di C:
• D(C(m)) = m
• Se D(C(m)) = C(D(m)) = m, allora commutativa
Come realizzare C e D ?
• Due grandi famiglie:
• Cifrari per uso ristretto:
• La sicurezza si basa sul fatto che C e D sono tenute
nascoste.
• quindi non è previsto l’uso di una chiave segreta.
• Cifrari per uso generale:
• C e D sono note a tutti.
• La sicurezza si basa sull’utilizzo di una chiave
segreta nota solamente al mittente e al destinatario.
Chiave Segreta:
una metafora fisica.
Uguali
Utente A
Utente B
è necessario incontrarsi
per scambiarsi le chiavi !!!
• Quanto costa scambiare la chiave ?
• Incontro face-to-face ma una tantum
• Posso ammortizzare il costo dello scambio
• Posso usare canali costosi e disponibili poco frequentemente
• Lo spazio delle chiavi deve essere grande:
• No brute-force attacks (visita esaustiva dello spazio)
• Prerequisito cruciale ma non sufficiente
• Passo in avanti sostanziale:
• Dal punto di vista teorico
• Dal punto di vista economico
• Esempi: DES, RC5, IDEA, …
(hanno superato la prova del fuoco)
Cifrari Simmetrici o a
chiave segreta
• Ruolo di Ck e Dk completamente
interscambiabile
• Mittente ~ Destinatario:
–
–
–
–
–
Conoscono la stessa chiave k
Entrambi possono cifrare e decifrare
Incontro segreto per accordarsi sulla chiave
Segretezza della chiave dipende da entrambi
Cifratura e decifrazione sono molto efficienti in pratica
• Quali sono i difetti di questi cifrari ?
– Occorre scambiarsi la chiave
– Dati n utenti, abbiamo bisogno di [n (n-1) / 2] chiavi
– Troppe per essere memorizzate e scambiate segretamente
Chiave Pubblica:
una metafora fisica.
Mittente
Destinatario
Fase
Fase1 2
Cifrari Asimmetrici o a Chiave
Pubblica
• Anno 1976: punto di svolta!
(Diffie-Hellman e Merkle)
• Obiettivo: rompere il legame tra Ck e Dk
– Chiunque sappia come cifrare non deve sapere come decifrare
– Chiave k scomposta in due parti < k[priv], k[pub] > :
• La chiave k viene creata da Dest
• k[priv] tenuta segreta da Dest e usata per costruire Dk[priv]
• k[pub] resa pubblica da Dest e usata da tutti per definire Ck[pub]
• Difficile andare da k[pub] a k[priv] !!
• Concetto funzione one-way trap-door:
– Ck[pub] facile, ma Dk[priv] difficile senza k[priv] !
Funzioni One-way con
trapdoor
• Funzioni facili da calcolare,
• difficili da invertire,
• a meno che... non si conosca
qualche informazione
aggiuntiva...
Funzioni One-way con
trapdoor
Lucchetto:
- è facile da chiudere
- è difficile da aprire
- se non si possiede la chiave
Funzioni One-way con
trapdoor
Cassetta delle lettere:
- è facile imbucare una lettera
- è difficile estrarre una lettera
- se non si possiede la chiave
Funzioni One-way con
trapdoor
p,q numeri primi:
- è facile calcolare n=pq
- è difficile dato n trovare p e q
- se conosciamo p diventa
facile (q=n/q)
Il Nuovo Scenario
U1
c1
Un
cn
Numero chiavi per n utenti ---> soltanto n
Lasciano penetrare qualche informazione...
Esempi: RSA, El Gamal, …
(sono considerati oggi robusti)
Dest
Panacea delle
comunicazioni segrete?
• Cifrari asimmetrici sono inefficienti !
• Sistemi Ibridi = asimmetrici + simmetrici !!
– Mitt e Dest scelgono “pubblicamente” una chiave “segreta” K*
utilizzando un cifrario asimmetico
– Mitt e Dest comunicano con un cifrario simmetrico basato su K*
– K* viene sostituita più volte nel corso di una comunicazione
– (session-key)
 Lentezza degli asimmetrici incontrata solo nello scambio sporadico delle
session-key.
 Incontro face-to-face per scambio chiavi segrete (nei simmetrici) aggirato
attraverso l’uso dei cifrari asimmetrici per raggiungere l’accordo.
 N2 chiavi segrete (nei simmetrici) nascoste dall’uso delle session-key (usa e
getta).
Conclusioni
• Confidenzialità è il solo requisito dei sistemi
crittografici moderni ?
• Oggigiorno se ne richiedono altri 4:
• User Identification: Dest può accertare che è proprio Mitt che
sta parlando o vuole parlare con lui.
• Integrità: Deve essere possibile per Dest stabilire che il
messaggio ricevuto non ha subito modifiche parziali o totali
(sostituzione).
• Autenticazione: Deve essere possibile per Dest accertare che il
messaggio ricevuto proviene proprio da Mitt.
• Firma Elettronica: Mitt non può sottrarsi dall’ammettere che è
stato lui a spedire il messaggio, e Dest può convincere una
terza persona (giudice) che questo è il caso.
Parte I:
Fondamenti e
Tecniche di Base
Cifrari Storici
Prologo
• Motivazioni:
– Scopi educativi: concetti, tecniche di base,…
– Divertimento: settimana enigmistica…
• Crittografia manuale
• Sono note tecniche statistiche per forzarli!
• Nota:
– Messaggi e crittogrammi composti di lettere
– Chiave segreta: esiste oppure no (degenere)
Cifrario di Cesare
a b c d e f g h i l mn o p q r s t u v z
C
D
d e f g h i l mn o p q r s t u v z a b c
o g g i
è
u n a
b e l l a
g i o
r l l n
h
a q d
e h o od
l n r
È un cifrario degenere
Introdurre chiave k = shift ciclico
C(mi) = lettera in posizione (pos(mi) + k) mod 21
D(ci) = lettera in posizione (pos(ci) – k) mod 21
Cifrario Completo
• Ammettiamo tutte le possibili permutazioni dell’alfabeto
– sono (21! – 1), un numero spropositatamente grande !
• Chiave k = <BFRULMZQWEA....> = una permutazione
• Questo cifrario è sicuro ? No, attacco statistico.
– Istogrammi di frequenza delle lettere nelle frasi in italiano
– Istogrammi di frequenza delle lettere nel crittogramma
– Molti crittogrammi a disposizione !
A
B
C
D
A
B
C
D
Cifrario a Trasposizione
1 2

3 4 5 6 7
8
9
10 11 12 13 14
m=ci vediamo t a r d i
c =ci dvaiemo r t i d a
 = <1,2,5,3,7,6,4>
• Permutazione delle lettere
• Periodo = 7
• No attacco statistico !
• Attacco sulla lunghezza del periodo
Cifrario Polialfabetico
Ogni occorrenza di una lettera nel messaggio in chiaro può essere
sostituita con diverse lettere nel crittogramma, a seconda della
sua posizione o del suo contesto.
ABCDEFGHIJKLMNO..
A
B
C
D
...
Y
Z
ABCDEFGHIJKLMNO..
BCDEFGHIJKLMNO..
CDEFGHIJKLMNO...
DEFGHIJKLMNO...
...
YZABCDEFGHIJK...
ZABCDEFGHIJ....
m
k
F E D E L E ...
B A C C A B ...
c
G E F G L F ...
- Monoalfabetico ogni |k| caratteri
- Attacco statistico possibile, ma difficile
Cifrari Perfetti:
one-time pad
One-time pad: esempio
Messaggio:
Chiave:
Crittogramma:
Chiave:
Messaggio:
1
1
0
1
0
0
0
1
1
0
0
0
1
1
1
0
0
1
0
1
1
1
1
1
1
0
0
0
1
1
1
0
1
1
0
1
0
0
0
1
Pregi e Difetti
• Se ogni bit della chiave è generato
casualmente allora conoscere un bit del
crittogramma non fornisce nessuna
informazione aggiuntiva sul corrispondente
bit del messaggio: cifrario perfetto.
• La chiave (pad):
– è lunga (quanto il messaggio)
– si consuma (one-time)
– occorre scambiarsela
DES
Data Encryption Standard
Un po’ di storia…
• Nel 1972, l’NBS (National Bureau of Standards. Oggi NIST: National
Institute of Standards and Technology) iniziò un programma per
proteggere le comunicazioni non classificate.
• Lo scenario era interessante:
– NSA (National Security Agency) disponeva di molte conoscenze in
materia di cifrari e metodi di decrittazione.
– Esistevano molti prodotti pressocchè oscuri, non certificati e non
compatibili.
• Nel 1973, l’NBS pubblicò un call for proposals:
– Sistema a chiave segreta (certificazione e chiarezza)
– Realizzabile in hardware (compatibilità)
• Bando andò pressocchè deserto.
…. ancora un po’.
• In un bando successivo IBM propose un sistema simile al suo
prodotto Lucifer (operazioni logiche su gruppi di bit)
• Poco dopo NSA certificò Lucifer con il nome di DES: fece
commenti e propose variazioni.
– Chiave ridotta da 128 bit a 64 bit.
– Modifiche significative alla funzione S-box.
• Diverse agenzie replicarono in modo allarmato !!
• Dopo alcune indagini il DES fu certificato e reso pubblico nel
1977.
• Primo esempio di cifrario robusto (con certificazione NSA) che i
ricercatori potevano studiare.
• È stato certificato pressocchè ogni 5 anni, dal 1998 non è più
considerato sicuro. Ad esso si preferisce il Triplo-DES.
• AES: il cifrario simmetrico del prossimo millennio !
Caratteristiche principali
di DES
•
•
•
•
Codifica Simmetrica
Codifica a blocchi
Blocco = 64 bit
Chiave = 64 Bit (solo 56 usati)
Operazioni di Base
•
•
•
•
•
Permutazione
Sostituzione
Espansione
Contrazione
Shift Circolare (destro e sinistro)
Permutazione
1
5
2
1
3
6
4
3
5
2
6
4
P=(5,1,6,3,2,4)
Un bit in ingresso determina un bit in uscita
Sostituzione
Ingresso: A B C
Uscita: A+B+C
000
001
010
011
100
101
110
111
010
011
100
111
110
000
001
101
Ogni ingresso può determinare ogni uscita
Una permutazione è anche
una sostituzione
Ci sono sostituzioni che
non sono permutazioni
Espansione
Numero delle uscite maggiore
del numero degli ingressi
Esempio:
3
3
3
3
Contrazione
Numero delle uscite minore del
numero degli ingressi
Esempio (scelta):
1
2
1
3
6
4
3
5
2
6
Alcuni ingressi non influenzano
le uscite, vengono scartati
Scelta Permutata
1
Permutazione
2
1
6
3
2
4
4
4
2
5
6
1
6
Scelta (contrazione)
64 bit testo in chiaro
64 bit chiave
Permutazione Iniziale : PI
Scelta Permutata: T
Fase 1
Fase 2
Fase 16
k1
k2
k16
Scelta Permutata 2
Shift circolare a Sinistra
Scelta Permutata 2
Shift circolare a Sinistra
Scelta Permutata 2
Shift circolare a Sinistra
Scambio a 32 bit
Permutazione Iniziale
Inversa: PF
64 bit testo cifrato
PI, PF, e T
Mancano ingressi: 8,16,24,32,40,48,56,64.
Servono come controllo di parità.
32
L i-1
32
28
R i-1
Espansione/Permutazione
28
R i-1
D i-1
Shift a sinistra
Shift a sinistra
48
XOR
48
Ki
Permutazione/Contrazione
48
Sostituzione/Scelta
32
Permutazione
32
XOR
Li
32
Ri
Ci
Di
32
28
28
E
+
48 bit
s1
s2
s3
s4
K (48 bit)
s5
P
32 bit
s6
s7
s8
32
E
48
S-Box
RSA
Rivest, Shamir, Adelman
E’ necessaria
la chiave segreta ?
• A manda a B lo scrigno chiuso con il
suo lucchetto.
• B chiude lo scrigno con un secondo
lucchetto e lo rimanda ad A
• A toglie il suo lucchetto e rimanda lo
scrigno a B
• B apre lo scrigno !!!
Un secondo protocollo
• B manda ad A il suo lucchetto aperto
• A chiude lo scrigno con il lucchetto
ricevuto da B e glielo spedisce
• B riceve lo scrigno e lo apre !!!
Funzioni One-way
con Trapdoor
• Un lucchetto è una funzione
one-way con trapdoor !
• Infatti tutti possono chiudere un lucchetto pur
senza possedere la chiave.
• Nessuno può aprire un lucchetto senza avere
la chiave.
• La cassetta delle lettere è
un’altra funzione one-way
con trapdoor. Perchè ?
Chiave Pubblica
• Per ottenere un protocollo a chiave
pubblica occorre trovare una funzione
matematica one-way con trapdoor !
• Cioè una funzione facile da calcolare e
difficile da invertire a meno di
possedere qualche informazione
aggiuntiva (chiave).
• La Teoria dei numeri ci viene in aiuto…
RSA
• Generazione delle chiavi
• Codifica. Encryption. C(m)
• Decodifica. Decryption. D(c)
RSA: Generazione delle chiavi.
Scelgo due numeri primi grandi p e q
Calcolo n=pq
Scelgo e tale per cui
GCD(e,(n)) = 1
Calcolo d tale per cui de mod (n) = 1
Chiave Pubblica = (e,n)
Chiave Privata = (d,n)
RSA: Encryption
c=
e
m
mod n
RSA: Decryption
m=
d
c
mod n
RSA: esempio.
• Scegliamo p=5 e q=11.
• Dunque n=55 e (n)= (5-1)(11-1)=40.
• Prendiamo e=7. Calcoliamo d=23.
d * e = 161 = 4 * 40 + 1 = 1 mod 40.
• Quindi il nostro sistema ha le seguenti chiavi:
K[priv]=(23,55) e K[pub]=(7,55)
• Sia m=5.
Codifica: c=57 mod 55 = 25
Decodifica: m=c23 mod 55 = 5
Domande
•
•
•
•
Chi ci assicura che D(C(m)) = m ?
Chi dice che RSA sia sicuro ?
RSA è efficiente ?
Come eseguo le varie operazioni ?
Correttezza di RSA
Sicurezza di RSA
• Nessun Teorema !!!
• Nessuno è ancora riuscito a violare RSA
• Un modo per risalire alla chiave privata
conoscendo quella pubblica è il seguente:
Fattorizzo n e ottengo p e q.
Calcolo (n) e quindi d.
• Si congettura sia vero anche il viceversa.
Massimo Comun Divisore
Definizione: produttoria dei fattori comuni con
il minimo esponente
Esempio: GCD(233472,2271132) = 2271
Algoritmo ottenuto dalla definizione:
FATTORIZZAZIONE !!! Tempo esponenziale
Serve un’idea !!!
Algoritmo di Euclide
GCD(x,y) = GCD(x-y,y)
GCD(x,y) = GCD(x-ky,y)
GCD(x,0) = x
GCD(408,595)
x
n
-2
-1
0
1
2
3
4
qn
0
1
2
5
2
y
rn
408
595
408
187
34
17
0
un
1
0
1
-1
3
-16
35
qn = rn-2 div int rn-1
un = un-2 - qnun-1
vn = vn-2 - qnvn-1
rn = unx + vn y
vn
0
1
0 408 = 2187 + 34
3 = 1 - 2-1
1
-2
11
-24
Se x e y sono primi tra loro alla fine abbiamo
Quindi u è l’inverso moltiplicativo di x modulo y
ovvero
Vogliamo d: ed  1 mod (n)
sapendo già che GCD(e, (n)) = 1
Usiamo l’algoritmo di Euclide.
Calcoliamo GCD(e,(n)) ottenendo u e v tali per cui
ue + v(n) = 1
u è ciò che cerchiamo !!!
Algoritmo di Euclide.
Function E(a,b)
if b=0
then Return a
else Return E(b, a mod b)
Algoritmo di Euclide Esteso.
Function EE(a,b)
if b=0
then Return <a,1,0>
else <d’,x’,y’> = EE(b,a mod b)
<d,x,y> = <d’,x’,y’-a/by’>
Return <d,x,y>
ALGORITMO STUPIDO:
Moltiplico 158 per 158 per 158....
58 volte e poi divido per 678
e prendo il resto.
Tempo di esecuzione dell’ALGORITMO STUPIDO
per calcolare
qualche decimo di secondo...
per calcolare
con a e b di 150 cifre = usando tutti i
calcolatori del mondo, la vita dell’universo !!!!
Trucchi computazionali per calcolare
Eseguire l’operazione di modulo dopo gni operazione
(non basta!)
...ma...
Cosa succede se devo calcolare
???
Operazioni Base:
Usiamo le operazioni base per calcolare efficientemente il
risultato finale.
Concludendo...
• Le operazioni di modulo le distribuisco
ad ogni passo ( per ridurre le dimensioni
dei numeri ottenuti via via..)
• EFFICIENZA ? OK!
Il numero di moltiplicazioni è lineare
nell’esponente.
Generazione di
primi “grandi”
Ci sono tavole di numeri primi ma non così grandi...
Quanti numeri primi ci sono ? Ovvero, come sono distribuiti ?
Qual è la probabilità di prendere un numero a caso e
questo sia primo ?
n di 10 cifre
n di 100 cifre
IDEA:
Genero n a caso poi verifico se è primo.
Se è primo ho finito.
Altrimenti Inizio da capo.
Test di Primalità
Fino a qualche tempo fa non si conosceva nessun
algoritmo per testare se un numero è primo oppure no.
Adesso esiste un algoritmo che svolge questo
compito in n4 passi.
Polinomiale ma poco efficiente.
Come si procede in pratica ???
Teorema di Fermat
(caso particolare del teorema di Eulero)
Pomerance 1981
a numero casuale tra 1 e n-1
n numero casuale di circa 100 cifre
Test probabilistico di primalità
1234-
Genero n
Genero a
Calcolo
If x = 1
then
else
a caso
tra 1 e n a caso
Stop: n primo
Stop: n composto
Analisi dell’algoritmo:
Se n è primo: risposta esatta sempre.
Se n è composto: risposta errata con probabilità =
Può non essere sufficiente per alcune applicazioni !!
Come procediamo ???
Test probabilistico di
primalità ESTESO.
1- Genero n a caso
2- Genero a tra 1 e n a caso
3- Calcolo
4- If x = 1
then Stop: n primo
k volte
else Stop: n composto
Come generare d, e ?
• e deve essere primo con
• d deve soddisfare
1- Scelgo e a caso.
2- Verifico se e è primo con (n).
2.a- Se si Fine
2.b- Se no goto 1.
Con l’algoritmo di Euclide Esteso trovo
l’inverso moltiplicativo di e mod (n)
Identificazione, Autenticazione
e Firma Digitale
• In origine crittografia = confidenzialità
• Diffusione delle reti: nuove funzionalità.
• Identificazione
• Autenticazione
• Firma digitale
• Identificazione: un sistema di
elaborazione deve essere in grado di
accertare l’identità di un utente che vuole
accedere ai suoi servizi
• Autenticazione: il destinatario di un
messaggio deve essere in grado di
accertare l’identità del mittente e
l’integrità del messaggio
• Firma digitale: funzionalità complessa
richiesta quando mittente e destinatario di
un messaggio non si fidano l’uno dell’altro
(reciprocamente). Proprietà simili alla
firma cartacea.
Firma digitale...
• il mittente non può negare di aver
inviato il messaggio
• il destinatario può accertare l’identità del
mittente e l’integrità del messaggio
(autenticazione)
• il desinatario non può sostenere di aver
ricevuto un messaggio diverso da quello
che realmente ha ricevuto
• il tutto verificabile da una terza parte
(giudice)
Identificazione
Autenticazione
Firma digitale
Contrastano
possibili
attacchi
attivi
Funzioni Hash
Proprietà di funzioni Hash
Elementi molto simili in X appartengano a
sottoinsiemi distinti
Funzioni Hash in crittografia:
Hash one-way
Hash one-way
• Prima proprietà dovrebbe valere
anche per funzioni Hash classiche
• Seconda proprietà: one-way
• Terza proprietà: claw-free
(opzionale)
• Esempi: MD5, SHA
Identificazione:
Un caso pratico ed un protocollo
Caso pratico: accesso di un utente alla propria casella
di posta elettronica o ai file personali memorizzati su
un calcolatore ad accesso riservato.
L’utente usa una login e password.
Supponiamo: password ben scelta e
canale sicuro
Attacco sferrato
dall’amministratore del sistema.
L’amministratore accede al file delle chiavi.
Contromisura: memorizziamo la password
in forma cifrata utilizzando le funzioni
hash one-way.
COME ???
Cifratura della pwd con funzioni
hash one-way:UNIX
Quando l’utente U fornisce per la prima volta la password P
il sistema associa a P due sequenze S e Q.
S e Q vengono memorizzate al posto di P
S è detto seme. E’ un numero generato a caso dal sistema.
Q = h(PS).
Cifratura della pwd con funzioni
hash one-way:UNIX
Quando l’utente si collega il sistema:
- recupera S dal file delle chiavi,
- concatena S con P e applica f ottenendo Q’.
- confronta Q’ con Q.
- se Q’=Q allora OK altrimenti FAIL
Se qualcuno accede al file delle chiavi ottiene S e Q. Dai quali
non riesce a inferire nulla su P.
Alcune osservazioni:
• E’ difficile risalire da S,Q a P.
• La presenza del seme casuale diverso
per ogni utente impedisce di scoprire se
due utenti hanno la stessa password e
rende impossibile un attacco simultaneo
a tutte le chiavi.
Abbiamo assunto che il canale attraverso il quale la chiave
viene comunicata al sistema sia sicuro.
In realtà di solito non lo è !!!
Protocollo di trasmissione della chiave cifrata usando RSA .
- U richiede accesso al sistema S
- S genera un numero casuale r < n e lo invia a U
- U calcola f=rd mod n (decifra r con la sua chiave privata) e
- spedisce f a S (U firma r).
- S cifra f calcolando r*=fe mod n
- Se r*=r allora OK altrimenti FAIL
Alcune osservazioni:
• Il sistema non deve memorizzare le
informazioni circa la chiave P. Semmai
deve solo memorizzare la chiave
pubblica di U
• E’ possibile invertire cifratura e
decifratura perché RSA e’ commutativo
• SSL è un meccanismo di identificazione
più sofisticato.
Autenticazione
• Identificazione: stabilire l’identità di un utente.
• Autenticazione: qualcosa in più di
identificazione.
• Mittente spedisce un messaggio a
Destinatario.
Destinatario autentica il messaggio se:
- identifica Mittente +
- verifica l’integrità del messaggio
MAC
Message Authentication Code
• Immagine breve del messaggio che può
essere generata solo da un mittente
conosciuto dal destinatario.
• Aspetti in comune con le funzioni Hash
crittografiche
• A volte generato usando funzioni Hash
crittografiche
• Entra in gioco una chiave segreta k
Il MAC ha una lunghezza fissata
indipendente da n
MAC(m,k)
MAC
Messaggio m di lunghezza n qualsiasi
MAC
Esempio di MAC
Otteniamo un MAC applicando una funzione hash
alla concatenazione di m e della chiave k
NOTA: il MAC non è invertibile.
Può solo essere calcolato di nuovo
ma non invertito !!!
Esempio di Autenticazione
usando MAC
- Mitt spedisce (m,h(mk)) a Dest.
- Dest riceve (m*,h(mk)*).
- Dest conosce k quindi può calcolare h(m*k).
- Dest confronta h(m*k) con h(mk)*.
- Se h(m*k)=h(mk)* Dest conclude che m*=m
(integro) e che il mittente di m è
effettivamente Mitt.
Perché ?
• L’intruso X non può spedire un messaggio a
Dest fingendosi Mitt. Perché ? Perché non
conosce k.
IDENTIFICAZIONE
• L’intruso X intercettando (m,h(mk)) non può
modificare m. Perché ? Perché non conosce
k.
INTEGRITA’
• Cosa succederebbe spedendo (m,h(m)) ???
Autenticazione +
confidenzialità
- Mitt spedisce (Ck(m),h(mk)) a Dest.
- Dest riceve (Ck(m)*,h(mk)*).
- Dest conosce k quindi decodifica
Ck(m)* e risale a m*
- Dest conosce k quindi può calcolare h(m*k).
- Dest confronta h(m*k) con h(mk)*.
- Se h(m*k)=h(mk)* Dest conclude che m*=m
(integro) e che il mittente di m è
effettivamente Mitt.
Firma Manuale e
Firma Digitale
• La firma digitale deve soddisfare le
proprietà di quella manuale.
• La firma digitale è una stringa di bit e
quindi è facilmente duplicabile/copiabile.
La firma manuale no !!
• Firma manuale e firma digitale sono
fisicamente oggetti di natura
completamente diversa !
Firma Manuale:
Proprietà
• La può generare solo una persona e
non è falsificabile.
• Non è riutilizzabile (legata al documento
su cui è apposta).
• Il documento su cui è apposta non è
modificabile.
• Non può essere ripudiata da chi l’ha
generata.
Firma Digitale:
Implementazione Ingenua
Firma digitale: digitalizzazione della firma manuale,
ad esempio usando uno scanner.
Attacco: Copia e Incolla !!!
Diffie e Hellman:
Cifrari Asimmetrici
U: Firma.
f=D(m,kU[priv])
send <U,m,f>
V: Verifica.
m*=C(f,kU[pub])
if m*=m then si else no
Osservazioni
• Occorre un cifrario commutativo, cioè
D(C(m)) = C(D(m)) = m. RSA è
commutativo.
• Il documento firmato non è indirizzato
ad uno specifico destinatario. Tutti
possono fare la verifica.
Proprietà del protocollo
• La può generare solo una persona: colui che
conosce kU[priv] cioè U.
• Non è riutilizzabile/copiabile/falsificabile: in quanto è
funzione del documento su cui è apposta.
• Il documento su cui è apposta non è modificabile: in
quanto anche la firma andrebbe nuovamente
generata.
• Non può essere ripudiata da chi l’ha generata: in
quanto solo conoscendo kU[priv] è possibile
generarla.
Difetti del protocollo
• La lunghezza del messaggio scambiato
è il doppio della lunghezza del
messaggio originario.
• Il messaggio non può essere
mascherato in quanto dall’operazione di
verifica è possibile risalire al messaggio
spedito
Soluzione
U: Firma e cifra
f=D(m,kU[priv])
c=C(f,kV[pub])
send <U,c>
V: Verifica.
f*=D(c*,kV[priv])
m*=C(f*,kU[pub])
if m* ”ha senso”
then si else no
In Pratica...
U: Firma.
f=D(h(m),kU[priv])
c=C(m,kV[pub])
send <U,c,f>
V: Verifica.
m*=D(c*,kV[priv])
if h(m*)=C(f*,kU[pub])
then si else no
Men in-the-middle Attack
•
•
•
•
•
Attacco attivo
X si mette nel mezzo tra U e V
X si comporta come U per V
X si comporta come V per U
X devia la comunicazione tra U e V
facendola passare per se stesso...
kV[pub]
V: Destinatario
di un messaggio
cifrato.
U: Mittente
di un messaggio
cifrato.
kV[pub]
kX[pub]
Intruso X
kV[pub]
kX[pub]
Men in-the-middle Attack
• U richiede a V la sua chiave pubblica
kV[pub] (per e-mail ad esempio)
• X intercetta kV[pub] e la sostituisce con
kX[pub]
• X intercetta i crittogrammi da U a V li
decodifica con kX[priv] li ri-codifica con
kV[pub] e li ri-spedisce a V
CA: Certification Authority
• Enti preposti alla certificazione di
validità delle chiavi pubbliche.
• Certificato:
– Chiave pubblica di U
– Lista di Informazioni su U
– Date di inizio e fine validità del certificato
– Lista di Algoritmi di codifica usati
– Firma di CA
Certificato di U
in formato X.509
• Numero di versione dello standard X.509 utilizzato.
• Chiave pubblica di U. Caratteristiche della chiave
(lunghezza, algoritmo con cui è stata creata, data di
creazione, durata della chiave…)
• Numero del certificato. Serve ad esempio per la
revoca (CRL)
• Distinguished name (DN): identificativo di U su tutta
la rete.
• Periodo di validità del certificato (inizio e fine validità).
• Il nome di chi ha firmato il certificato (di solito una
CA), la sua firma digitale e l’algoritmo usato per
apporre la firma.