A Tutorial Introduction to
Authentication and Key
Establishment
Corso di Sicurezza e Privacy
Laurea Specialistica in Economia Informatica
Università degli studi
“G. D’Annunzio”
Pescara
A.A. 2007-2008
Prof. Stefano Bistarelli
Studente Romualdo Trovato
1
Indice
Building a Key Establishment Protocol
Protocol Architectures
Criptographic Propetries
Freshness
Types of Attack on Protocols
Design Principles For Cryptographic
Protocol (Abadi and Needham)
2
Indice
Building a Key Establishment Protocol
Protocol Architectures
Criptographic Propetries
Freshness
Types of Attack on Protocols
Design Principles For Cryptographic
Protocol (Abadi and Needham)
3
Building a Key Establishment
Protocol
Set di Utenti
Session Key
Server
A
B
KAB
S
4
Building a Key Establishment
Protocol
1: A,B
• L’obiettivo del protocollo è di
stabilire una nuova chiave
segreta KAB che possono
usare per comunicare in
modo sicuro.
• Il ruolo di S è di generare
KAB e trasportarlo da A a B.
A
S
2:KAB
3: KAB, A
B
• Il valore di KAB dovrebbe
essere
conosciuto
da
entrambi A e B e non a terze
parti
1: A → S : A, B
• A e B dovrebbero sapere
che KAB è appena generata.
3: A → B : KAB, A
2: S → A : KAB
5
Building a Key Establishment
Protocol
1: A,B
È incompleto:
• Sono specificati solo i
passi di esecuzioni di
successo.
• Non sono specificati le
azioni interne dei mandanti.
• È implicito assumere che
A e B “conoscono” che i
messaggi ricevuti fanno
parte del protocollo
A
S
2:KAB
3: KAB, A
B
6
Confidentiality
1: A,B
Problema:
La session Key KAB deve essere
trasportata da A a B e non da altre
entità
A
S
2:KAB
3: KAB, A
Security Assumption 1: L’avversario è in grado di spiare
tutti i messaggi in un cryptographic protocol
B
Al fine di fornire la riservatezza è necessario usare un algoritmo di crittografia e
chiavi associate. Per ora sarà sufficientemente effettuare il presupposto che il
Server S inizialmente condivide una chiave segreta per ogni utente del sistema.
KAS → A
KBS → B
7
Confidentiality
1: A,B
• A spedisce ad S le identità delle
parti che condividono la session Key.
S genera la session Key KAB che lo
cripta con le chiavi KAS e KBS e lo
spedisce ad A.
• A spedisce la chiave di criptazione
a B con la sua identità così che B
conosce chi altro ha questa chiave.
A
2:{KAB}KAS
S
, {KAB}KBS
3: {KAB}KBS, A
B
8
Authentication
Problema: Il problema non è che si dà
via la chiave segreta KAB. La difficoltà è
che le informazioni non sono protetti da
terze parti che hanno la chiave. Gli
avversari sono in grado non solo a
origliare sui messaggi spediti ma anche
di catturare i messaggi e di alterarli.
1: A,B
A
2:{KAB}KAS
S
, {KAB}KBS
3: {KAB}KBS, A
Security Assumption 2 : Gli avversari possono alterare tutti i messaggi
spediti in un cryptographic protocol usando qualsiasi informazione
disponibile. In aggiunta l’avversario può cambiare rotta di qualsiasi
messaggio verso altri utenti. Questo include l’abilità di generare e
inserire completamente nuovi messaggi.
B
9
Authentication
Attacco1: L’avversario C intercetta
semplicemente il messaggio da A a B e
lo sostituisce con l’identità di D al posto
di A.
La conseguenza è che B crede che sta
condividendo la chiave con D invece che
con A.
Sebbene C ottiene KAB possiamo
vedere il protocollo come spezzato dal
momento che non soddisfa le nostre
richieste. Quindi gli utenti devono sapere
chi altro conosce la session Key
Attacco 1
1: A,B
A
2:{KAB}KAS
S
, {KAB}KBS
3: {KAB}KBS, A
B
C
3’: {KAB}KBS, D
10
Authentication
Attacco 2: C altera il messaggio da
A ad S così che genera KAC con la
chiave di C KCS, invece che con la
chiave di B. Poiché A non può
distinguere
tra
i
messaggi
crittografati, A non rileverà nessuna
alterazione e quindi accetta KAC.
Attacco 2
S
1’: A,C
2:{KAC}KAS
C
2’:{KAC}KAS
Inoltre C raccoglie anche il 1: A,B
messaggio destinato a B così che B
non noterà nessuna anomalia.
Il risultato di questo attacco è che A
crede che il protocollo sia stato
completato con successo con B non
che conosce tutte le informazioni
che A spedisce a B.
, {KAC}KCS
, {KAC}KCS
A
C
3: {KAC}KCS, A
11
Authentication
Attacco 2
S
1’: A,C
Bisogna notare che questo tipo di
attacco può avere successo solo se
C è un utente legittimato e
conosciuto da S (insiders)
2:{KAC}KAS
C
2’:{KAC}KAS
1: A,B
Security Assumption 3:
L’ avversario può essere un
partecipante legittimo del protocollo
(insiders), o una parte esterna
(outsiders), o una combinazione di
entrambi.
, {KAC}KCS
, {KAC}KCS
A
C
3: {KAC}KCS, A
12
Authentication
Per superare l’attacco, il nome degli
utenti che condividono KAB hanno la
necessità
di
essere
vincolati
crittograficamente al valore di KAB,
utilizzando algoritmi di crittografia di S
in modo da non alterare i messaggi.
1: A,B
A
2:{KAB,B}KAS,
S
{KAB,A}KBS
3: {KAB,A}KBS
B
Problema: La session Key KAB generata da S per ogni protocollo di esecuzione.
• Session Key sono vulnerabili da attacchi
• È possibile utilizzare vecchie Session Key da precedenti sessioni (replay)
13
Replay
1: A,B
Secutity Assumption 4:
Un avversario è in grado di ottenere il
valore della session key KAB in
qualsiasi precedente esecuzione del
protocollo
C intercetta il messaggio da A ad S.
K’AB è una vecchia session Key utilizzata
A
C
2:{K’AB,B}KAS,{K’AB,A}KBS
3: {K’AB,A}KBS
B
da A e B.
Dal SA.1 C può conoscere il messaggio crittografato tramite la chiave K’AB che
era stata trasportata da A a B. Dalla SA.4 C può conoscere il valore di K’AB.
Quindi A completa il protocollo con B, C è in grado di decriptare le seguenti
informazioni crittografati con K’AB o inserire o alterare messaggi la cui integrità è
protetta da K’AB.
C ripete (replay) i messaggi protetti da K’AB che sono stati inviati in un
precedente sessione
14
Replay
Il metodo più utilizzato per superare un attacco Replay è il Challenge-Response. In
questo metodo A genererà un nuovo valore casuale NA, comunemente definita
nonce, che può essere utilizzato una volta sola.
Definition 1.1 Una nonce è un valore casuale generato da un componente del
protocollo restituito a questi componenti per mostrare che un messaggio è
appena generato.
1. A,B,NA
S
2. {KAB,B,NA,{KAB,A}KBS} KAS
A
15
Replay
1. A,B,NA
S
2. {KAB,B,NA, {KAB,A}KBS } KAS
3. {KAB,A}KBS
A
4. {NB}KAB
B
5. {NB-1}KAB
C
3. {K’AB,A}KBS
4. {NB}K’AB
B
5. {NB-1}K’AB
16
Replay
• Il protocollo è iniziato da
B che manda la sua nonce
prima ad A.
• A aggiunge la sua nonce
e la spedisce ad S che è in
grado di generare KAB e
spedirlo in due messaggi
separati ad A e a B che a
loro volta controllano che
KAB non sia riutilizzato
(fresh)
2. A,B,NA,NB
S
3. {KAB,B,NA}KAS,{KAB,A,NB}KBS
A
1. B,NB
4. {KAB,A,NB}KBS
B
17
Indice
Building a Key Establishment Protocol
Protocol Architectures
Criptographic Propetries
Freshness
Types of Attack on Protocols
Design Principles For Cryptographic
Protocol (Abadi and Needham)
18
Protocol Architectures
Exsting Cryptographic Keys
Method of Session Key Generation
Number of Users
19
Exsting Cryptographic Keys
3 possibilità:
I.
Le entità gia condividono una chiave segreta
II.
Viene utilizzato un Off-line Server. Questo significa
che le entità già posseggono una chiave pubblica
certificata. Al fine di verificare la autenticità di una
chiave pubblica potrebbe essere necessario
verificare una Chain of Certificate.
III.
Viene utilizzato un On-line Server. Questo significa
che ogni entità condivide una chiave segreta con il
Server. Al fine di passare le informazioni tra le parti è
necessario che esso passi tramite una Chain of online Server.
20
Method of Session Key
Generation
Definition 1.2 Una Key Transport Protocol è una Key
Establishment Protocol in cui uno dei mandanti genera la
chiave e questa chiave è poi trasferita a tutti gli utenti del
protocollo.
Definition 1.3 Una Key Agreement Protocol è una Key
Establishment Protocol in cui la Session Key è una
funzione di Input da tutti gli utenti del protocollo.
Definition 1.4 Un Hybrid Protocol è una Key
Establishment Protocol in cui la Session Key è una
funzione di Inputs da più di un mandante, ma non da tutti
gli utenti. Questo significa che il protocollo è un Key
Agreement Protocol dal punto di vista di qualche utente,
e un Key Transport Protocol dal punto di vista di altri.
21
Number of Users
Non esiste un numero preciso
Maggiore è l’estenzione del protocollo
maggiore sarà la difficoltà di
comunicazione
22
Example
(Hybrid Key Establishment)
• On-line Server
• Hybrid Key Generation
• Condividono KAS e KBS
• KAB = f (NB, NS)
• 2 Utenti
• S deve controllare che il valore
dalla decriptazione del campo B
è la stessa identità del mandante
la quale chiave è usata per
decriptare il messaggio.
• Se la stessa identità è ricevuta
con l’identità di A, allora S può
dedurre che A e B stanno
condividendo una Session Key
1. A → B : A, NA
2. B → S : {NB,A,B}KBS, NA
3. S → A : {KAB,A,B,NA}KAS,NS
4. A → B : NS, {A,B}KAB
5. B → A : {B,A}KAB
23
Example
(Hybrid Key Establishment)
S
3. {KAB,A,B,NA}KAS,NS
2. {NB,A,B}KBS, NA
A
1. A, NA
B
24
Indice
Building a Key Establishment Protocol
Protocol Architectures
Criptographic Propetries
Freshness
Types of Attack on Protocols
Design Principles For Cryptographic
Protocol (Abadi and Needham)
25
Cryptographic Properties
Confidentiality
Data Integrity
Data Origin Authentication
Non-Repudiation
26
Cryptographic Properties
EA(M) La chiave pubblica di criptazione del
messaggio M con la chiave pubblica
dell’entità A
{M}K Criptazione Simmetrica del messaggio
M con una chiave condivisa K
MACk(M) Codice di autenticazione di M
usando una chiave condivisa K
SigA(M) Firma digitale del messaggio M
generato dalla entità A
27
Confidentiality
Definition 1.5 Uno schema di decriptazione consiste in 3
set: K , M , C
1. Un algoritmo di generazione delle chiavi, il cui outputs
è una valida criptazione della chiave K є K e una
valida decriptazione K-1єK
2. Un algoritmo di criptazione, che prende un elemento m
є M e una criptazione della chiave K є K e un outputs
un elemento c є C definito come c=Ek{m}. L’algoritmo
di criptazione può essere randomizzato così che un
differente c risulterà dato dallo stesso risultato m
3. Un funzione di decriptazione, prende un elemento c є
C e una chiave di decriptazione K-1 є K e output un
elemento m є M definito come m=Dk-1{c}. Si richiede
che Dk-1{Ek{m}}=m
28
Confidentiality
Symmetric Algorithm
-1
K=K
Asymmetric Algorithm
-1
K≠K
29
Confidentiality
Definition 1.6 Uno schema di criptazione fornisce un
semantic security se niente che può essere
efficientemente calcolato dato il ciphertext, può anche
essere efficientemente calcolato senza ciphertext.
INDISTINGUISHABILITY
Questo significa che il ciphertext corrispondente a uno dei due messaggi
conosciuti, l’avversario può indovinare il plaintext con il 50% di possibilità
30
Confidentiality
Definition 1.7 Uno schema di criptazione fornisce la nonmalleabilità se esso è infattibile a prendere un esistente
ciphertext e lo trasforma in un correlato ciphertext senza la
conoscenza dell’input plaintext
NON - MALLEABILITÁ
La non-Malleabilità è più forte della semantic security
31
Data Origin Authentication and Data Integrity
Definition 1.8 Una funzione f : X → Y è one – way se è
computazionalmente facile da calcolare y = f(x) dato x є X,
ma è computazionalmente difficile trovare qualsiasi x con
f(x) = y per quasi tutti i valori di y є Y
Una funzione one – way che è allegato al messaggio prima della criptazione è
conosciuto come un manipulation detection code (MDC). L’idea è che senza la
conoscenza del messaggio o del MDC l’avversario non è in grado di alterare il
messaggio senza distruggere la correttezza del MDC. Cioè, L’avversario non
può creare alcun messaggio criptato che, quando decriptato, avrebbe un
corretto MDC
32
Data Origin Authentication and Data Integrity
Definition 1.9 Un codice di autenticazione (MAC) è una famiglia di
funzioni parametrizzati da una chiave K tale che MACk(m) prende
un messaggio m di arbitraria lunghezza e l’output un valore di
lunghezza fissata che:
1. È computazionalmente facile da calcolare MACk(m) dato K e m.
2. Dato un qualsiasi valore del MAC per un dato K, è
computazionalmente difficile trovare qualsiasi valore MAC per
qualsiasi nuovo messaggio.
Questa seconda definizione per fornire Data Origin Authentication e Data
Integrity bisogna aggiungere un MAC al messaggi che potrebbe essere sia in
plaintext o criptata. Al ricevimento del MAC, il destinatario che ha una corretta
chiave è in grado di ricalcolare il MAC dal messaggio e verificare che esso è
lo stesso che ha ricevuto.
33
Non - Repudiation
Definition 1.10
La firma digitale consiste di 3 sets: K , M , S
1. Un algoritmo di generazione delle chiavi, il cui outputs una valida firma con
chiave K є K è una valida verificazione della chiave K-1 є K.
2. Un algoritmo di generazione delle firme, che prende una valida firma con
chiave K є K e come outputs un elemento s є S. Potremmo scrivere
s=SigA{m} dove K è la firma generata con la chiave dell’entità di A.
L’algoritmo di generazione delle firme potrebbe essere randomizzato così che
un differente output risulterà dato lo stesso messaggio m.
3. Una funzione di verifica, che prende una firma s є S, un messaggio m є M, e
una chiave di verifica K-1 є K e come output un elemento v є {0,1}. Se v=1
allora diciamo che la firma è valida o Se v=0 diciamo che la firma non è valida.
L’algoritmo di firma digitale è considerato come sicuro se è
computazionalmente difficile per gli avversari trovare una valida firma di
qualsiasi messaggio che non è stata precedentemente firmato, anche dato
alcuni messaggi precedentemente firmati.
34
Secret Sharing
Il Secret Sharing è un meccanismo che consente al
proprietario di un segreto di distribuire le parti del
messaggio all’interno di un gruppo. Il proprietario di un
segreto è spesso chiamato dealer.
Un (t,n) Threshold Scheme è un secret sharing per cui n
parti sono distribuite, tale che qualsiasi set di t (o più) parti
sono sufficienti per ottenere il segreto, mentre qualsiasi set
di t-1 (o meno) parti non sono di aiuto per recuperare il
segreto.
Problema : Il secret sharing non fornisce fresh keys e key
authenthication.
35
Secret Sharing
Threshold Scheme è basato sull’uso di interpolazioni polinomiali. Consente a
qualsiasi polinomio di grado d ad essere completamente recuperati una volta
ogni d+1 punti sono conosciuti su di esso.
Le interpolazioni polinomiali lavorano su tutti i campi, ma nelle applicazioni
criptografiche il campo è tipicamente Zp per qualche p primo
Al fine di condividere un segreto s є
genera un polinomio di grado t-1 :
Zp
nel threshold scheme (t,n) il dealer
f(z) = a0 + a1z +…….+ at-1zt-1
Con coefficienti casualmente scelti in
valori f(x) con 1 ≤ x ≤ n.
Zp
eccetto per
a0 = s . Le parti sono
36
Indice
Building a Key Establishment Protocol
Protocol Architectures
Criptographic Propetries
Freshness
Types of Attack on Protocols
Design Principles For Cryptographic
Protocol (Abadi and Needham)
37
Freshness
La proprietà di verifica se una chiave può essere replicata o meno può essere
estesa anche agli elementi del messaggio.
2 ways :
1. Key agreement protocol dove 2 utenti A e B entrambi scelgono un input
rispettivamente NA e NB su una nuova sessione KAB. KAB sarà funzione di
N A e N B.
KAB = f (NA , NB)
Una proprietà desiderabile della funzione f non dovrebbe essere possibile per
A o B a riutilizzare un altro valore di KAB anche se l’input dell’altro è
conosciuto. Noto A non è possibile trovare NB tale che f (NA , NB) sia un
valore già usato.
2. Il freshness dipende su qualcosa ricevuto con il messaggio. Supponiamo che a
intende verificare il freshness di una session key KAB che è stata generata da
qualche server S, ed inoltre che il messaggio ricevuto non sia un vecchio
messaggio. Assumiamo che A riceve F( KAB , N ). F per essere freshness
deve disporre delle proprietà di Data Origin Authentication and Data Integrity
così che il destinatario può dedurre che sia KAB che N sono fresh.
38
Freshness
La proprietà di verifica se una chiave può essere
replicata o meno può essere estesa anche agli
elementi del messaggio.
2 ways :
1.
KAB = f (NA , NB)
5=f(2,3)
5 = f (2 , NB)
2. F (KAB , N)
• Data origin Authentication
• Data Integrity
39
Freshness
Timestamps : timestamps sia dentro un
intervallo di tempo accettato.
Nonce (Random Challenges)
1. A → B : NA
2. B → A : f(NA,…)
Counters : sincronizzazione di un contatore
40
Indice
Building a Key Establishment Protocol
Protocol Architectures
Criptographic Propetries
Freshness
Types of Attack on Protocols
Design Principles For Cryptographic
Protocol (Abadi and Needham)
41
Types of Attack on Protocols
Eavesdropping : cattura le informazioni spedite
nel protocollo.
Modification : alterare le informazioni spedite
nel protocollo.
Replay : ripetere la session Key.
Preplay : estenzione del replay, l’avversario si
impegna in una esecuzione del protocollo prima
dell’esecuzione di un utente legittimato .
Reflection : l’avversario spedisce messaggi del
protocollo che ritornano all’utente che li ha
spediti.
42
Types of Attack on Protocols
Denial of service : l’avversario sostituisce ed
ostacola gli utenti dal completare il protocollo.
Typing Attacks : l’avversario sostituisce un campo
del messaggio di un tipo con un’altro campo di un
altro tipo.
Cryptanalysis : l’avversario guadagna qualche utile
leva dal protocollo per aiutare la cryptanalysis.
Certificate Manipulation : l’avversario sceglie o
modifica le informazioni dei certificati per attaccare
uno o più esecuzioni del protocollo.
Protocol Interaction : l’avversario sceglie un nuovo
protocollo per interagire con un protocollo
conosciuto.
43
Indice
Building a Key Establishment Protocol
Protocol Architectures
Criptographic Propetries
Freshness
Types of Attack on Protocols
Design Principles For Cryptographic
Protocol (Adabi e Needham)
44
Design Principle for Cryptographic
Protocol
(Abadi and Needham)
1.
2.
3.
4.
5.
Ogni
messaggio
deve
dire
cosa
significa:
l'interpretazione del messaggio deve dipendere solo
sul suo contenuto
Processo di esecuzione del messaggio, devono
essere chiaramente indicati in modo che qualcuno nel
ricontrollare la progettazione può vedere se sono
accettabili o meno
Se l'identità di uno degli utenti è essenziale per il
significato di un messaggio, è prudente citare il nome
degli utenti esplicitamente nel messaggio
Essere chiaro sul perché la crittografia è stata fatta
Quando uno degli utenti firma un messaggio che è già
stato cifrato, non dovrebbe essere dedotto che l’utente
conosce il contenuto del messaggio
45
Design Principle for Cryptographic
Protocol
(Abadi and Needham’s)
6.
7.
Essere chiari su quali proprietà si sta assumendo circa le nonces.
Se una quantità è prevedibile per essere effettiva, dovrebbe essere
protetto in modo tale che un intruso non può simulare un
cambiamento e poi ripetere una risposta
8.
Se sono utilizzati i timestamps come garanzie di freshness, allora
la differenza tra gli orologi locali e delle varie macchine devono
essere molto inferiore a quello consentito dall’età di un
messaggio.
9.
Una chiave potrebbe essere stato usato di recente, ad esempio
per cifrare una nonce, e ancora essere vecchio e forse
compromessa.
10. Dovrebbe essere possibile dedurre che il protocollo, e quale
esecuzione di tale protocollo, il messaggio appartiene, e per
conoscere il suo numero nel protocollo.
11. Le relazioni di fiducia in un protocollo deve essere esplicito e ci
dovrebbero essere buone ragioni per la necessità di tali relazioni.
46
FINE
47