2. Goals for 2. Goals for authentication and key authentication and key establishment establishment

2. Goals for 2. Goals for

authentication and key authentication and key

establishment establishment

Ilaria Iannantuono 1. Introdution

2. Basic Goals

3. Enhanced Goals

4. Goals Concerning Compromised Keys 5. Formal Verification of Protocols

6. Complexity-Theoretic Proofs of Security

2.1 Introduzione

Ogni attacco su protocollo è semplicemente valido se infrange qualche obiettivo che il protocollo aveva pensato.

La chiarezza nella descrizione degli obiettivi è dovuta da:

 DESIGNERS: l’efficienza degli scopi alla struttura del protocollo rendono l’analisi più chiara e fluida;

 ANALYSER: utilizza gli obbiettivi di protocollo per trovare attacchi o provare la non presenza;

 IMPLEMENTERS: deve essere chiaro su cosa un protocollo è intenzionato ottenere così che possano proteggere l’utente da sicuri inserimenti.

P. 2.1: esempio di protocollo

1. A B: N^A

2. B A: MAC^KAB(B, A, N^A)

3. A B: MAC^KAB(A, B, N^B)

Semplice processo di autenticazione

MAC: Messagge Authentication Code N: nonce

K

Attacco sul p.

2.1

1. C^A B: N^C

2. B C^A: MAC^KAB(B,A,NC),N^B

3. C^B A: N^B

4. A C^B: MAC^KAB(A,B,N^B),N^A

5. C^A B: MAC^KAB(A,B,N^B)

L’avversario è capace di:

- controllare le comunicazioni tra soggetti (quindi può leggere, alterare, inserire ed eliminare messaggi);

- può ottenere tutte le chiavi di sessione usate in previsione di esecuzioni di protocollo

Def. 2.1 Def. 2.1

Un modello per l’avversario di tipo:

 Malicious insiders se l’avversario fosse un protocollo principale legittimato

 Honest insiders se i soggetti eseguiranno attacchi solo in accordo da quanto stabilito

2.2 Basic Goals

Obiettivi formali generici per protocolli di Syverson e van

Oorschot

SVO1 Far-end Operative A crede che B ha recentemente detto qualcosa

SVO2 Entity Authentication A crede che B ha di recente replicato ad uno specifico cambiamento

SVO3 Secure Key Establishment A ha una certa chiave K che A crede sia buona per comunicare con B

SVO4 Key Confirmation In aggiunta alla SVO3, A ha ricevuto conferme evidenti che B conosce K

SVO5 Key Freshness A crede che una certa chiave k sia fresca

SVO6 Mutual Understanding of Shared Key A crede che B ha recentemente confermato che B ha una certa chiave K che B crede sia buona per comunicare

Gli obiettivi attesi dall’authentication e key

Establishment protocol vengono suddivisi da Gollman in:

User-Oriented Goals

Key-Oriernted Goals ^Enhanced Goals

User-Oriented Goals

Def. 2.2 Def. 2.2

Entity authentication è il processo attraverso il quale

una parte è assicurata (attraverso acquisizione di prove significative) delle identità di una seconda parte inserita in un protocollo, e che il secondo ha attualmente

partecipato (ad es. è attivo per, o immediatamente pronto ad acquisire prove)

P. 2.2 Un semplice protocollo di autenticazione

1. A B: NA

2. B A: Sig^B(N^A)

A. 2.2 Un attacco al protocollo 2.2

1. A C^B: N^A

1) C B: N^A

2) B C: Sig^B(N^A)

2. C^B A: Sig^B(N^A)

Def. 2.3 Def. 2.3

Un soggetto A è definito consapevole di B come suo

membro se A è informato da B con una sua richiesta nel protocollo.

Def. 2.4 Def. 2.4

Una forte entity authentication di A a B è fornita se B ha una certezza fresh che A è a conoscenza che B è la sua entità.

Def. 2.5 Def. 2.5

Mutual authentication avviene se entrambe le entità sono autenticate l’un l’altro sullo stesso protocollo. Unilateral authentication avviene solo se una entità è autenticata dall’altro.

1. A B: N^A

2. B A: Sig^B(A, N^A)

Prot. 2.3: Un altro semplice protocollo di autenticazione

Key-Oriented Goals

Componenti del messaggio utilizzati nei protocolli crittografici:

 KEYS le quali devono essere chiavi a lungo termine o chiavi di sessione;

 IDENTIFIERS per i partecipanti del protocollo;

 NONCES le quali devono essere composte da un valore casuale, da timestamps o da contatori

Menzes e al. definiscono key establishment, come il processo o protocollo attraverso il quale una parte segreta diventa disponibile a due o più parti, per un ulteriore uso crittografico.

Per stabilire una good key si applica la seguente definizione:

Def. 2.6

La shared session key è una buona chiave per A usare con B solo se A è sicura che:

•la chiave è fresh (key freshness)

•la chiave è conosciuta solo da A e B ed entrambi le parti si fidano reciprocamente(key authentication)

Def. 2.7

La pubblic session key è una buona chiave per A usarla con B solo se:

- la chiave è fresh(key freshness);

- la corrispondente private key è conosciuta solo da B(key authentication)

Def. 2.8

Key integrity è la proprietà che dimostra che

la chiave non è stata modificata dall’avversario,o equivalentemente ha solo degli input per legittimare

I protagonisti.

•Per un key transport protocol, la key integrity significa che se la chiave è accettata da ogni titolare questa deve essere la stessa chiave scelta dal key originator;

•Per un key agreement protocol, la key integrity significa che se una chiave è accettata da ogni titolare questa deve essere una funzione conosciuta composta dagli input del protocollo dei titolari.

2.3 Enhanced Goals

Questi obiettivi vengono stabiliti per stabilire una semplificazione per il partner nell’impegnarsi in una comunicazione sicura

Def. 2.9

La key confirmation di A a B è fornita se B è sicuro che la chiave K è una good key per comunicare con A, e che il titolare di A è in possesso di K.

Def. 2.10 Def. 2.10

Explicit key authentication è la proprietà ottenuta quando entrambi (implicitamente) ottengono key authentication e la key confirmation.

Def. 2.11 Def. 2.11

Credere che la chiave K sia fornita per B solo se K è una good key per usarla con A, e A desidera comunicare con B usando la chiave K la quale A crede sia buona per il suo scopo.

Gerarchia di authentication e key establishment goals

Mutual Belief in Key

Key Confirmation

Entity Authentication

Fra-End Operativity Once Authentication Good Key

Fresh Key Key Exclusivity

User-Oriented Keys Key Oriented Goals

Es.: STS (Station-To-Station) Protocol

1. A B: g^x

2. B A: g^y, {Sig_B(g^y ,g^x)}^KAB

3. A B: {Sig_A(g^x ,g^y)} ^KAB

P. 2.4: STS protocol

Questo protocollo usa una firma digitale nei messaggi scambiati aggiunta al protocollo Diffie-Hellman. Questo protocollo usa l’aritmetica in gruppi multipli con un

generatore g, e gli esponenti x e y vengono scelti in modo casuale da A e B per utilizzarli nella chiave di sessione ^K_AB = g^xy

1. A B: A, B, g^x

2. B A: B, A, g^y, {Sig_B(g^y ,g^x)}^KAB

3. A B: A, B, {Sig_A(g^x ,g^y)}^KAB

P. 2.5: STS protocol modificato per includere gli identificatori

1. A C_B: A, B, g^x

2. C B: C, B, g^x

3. B C: B, C, g^y {Sig_B(g^y, g^x)}^K_AB

4. C_B A: B, A, g^y, {Sig_B(g^y, g^x)}^K_AB

5. A C_B: A, B, {Sig_A(g^x ,g^y)}^K_AB

A. 2.3: Attacco di Lowesul protocollo 2.5

Intensional e Extensional Goals

Roscoe suddivide e definisce i protocolli crittografici in:

•Extensional proprerty: ’..indipendent of details of the

protocol and would apply to any, other protocol designed to achive the same effect..’;

•Intensional property: ’..whose primary purpose is to assert a property of the way, in terms of communication within the protocol, a particular state is reached..’

Protocol Efficency

 Computational efficency: si riferisce alle stime dei protocolli di cui i titolari hanno bisogno il completamento del

protocollo

 Communication efficency: si riferisce al numero e alla lunghezza dei messaggi che servono per l’invio e la ricezione all’interno del protocollo

Def. 2.12 Def. 2.12

Un protocollo round include tutti i messaggi che possono essere inviati da ogni punto del

protocollo

Responsibility e Credit

Una interessante dicotomia per come le chiavi di sessione possono essere usate è stata presentata da Abadi. Usa termini quali responsibility e credit per descrivere due diversi tipi di utilizzi della chiave di sessione:

 Una chiave può fornire responsibility se l’uso che la chiave ne fa implica che il mittente del messaggio può dopo essere stato responsabile del contenuto del

messaggio;

1. A B: A, B, Sig_A(K, A, B, T_A)

P. 2.6: Un protocollo in cui A prende ‘responsibility’

1. A B: E_B(A, K_AB)

P. 2.7: Un protocollo in cui A prende ‘credit’

T_A= timestamp di A

E_B= criptato con la chiave pubblica di B

Una chiave può fornire credit se l’uso che la chiave implica che il mittente del messaggio può dopo

reclamare la proprietà dei contenuti del messaggio.

2.4 Goals Concerning Compromised Keys

 Forward secrecy: si occupa della protezione delle informazioni che non compromettono prima che la chiave a lungo termine sia persa.

 Key compromise impersonation: preventivamente riduce dei tipi di attacco che possono essere inseriti prima che la chiave a lungo-termine si conosciuta

Forward Secrecy

Def. 2.13 Def. 2.13

Un key establishment protocol fornisce forward secrecy se compromette chiavi a lungo-termine di un gruppo di

titolari che non compromettono le chiavi di sessioni stabilite in previsione dell’esecuzione del protocollo creata questi soggetti.

Def. 2.14 Def. 2.14

Un protocollo fornisce parziale forward secrecy se compromette chiavi a lungo-termine di uno o più

soggetti specifici di titolari che non compromettono le chiavi di sessioni stabilite in previsione

dell’esecuzione del protocollo creata da questi soggetti.

Questo esempio fornisce un key transport tra A e B. Qui K_T è una chiave pubblica di breve durata (ephemeral key)

scelta da A unicamente per la sua sessione.

Questa chiave viene inviata a B e segnata da A insieme ad una Nonce NA scelta da A. Poi B utilizza questa

ephemeral key per trasportare la chiave di sessione K_AB indietro ad A. Qui E_T(.) denota il criptaggio con K_T e h è un tipo di funzione hash.

1. A B: KT, Sig(KT, B)

2. B A: E_T (K_AB ), Sig_B(h(K_AB), A, N_A

P. 2.8: Key transport protocol fornisce una forward secrecy

1. A S: A, B

2. A B: A, g^NA

3. S B: {A, B, K_S}_KBS

4. S A: {A, B, K_S}_KAS

5. B A: B, g^NB

P. 2.9: Protocollo basato su su server fornendo un forward secrecy

Le chiavi a lungo termine usate in un protocollo forniscono forward secrecy che potrebbe essere sia shared che pubblic. Nel protocollo 2.9 A e B sono chiavi shared a lungo termine K_AS e K_BS con server S. N_A,N_B e K_S sono valori casuali scelti da A, B e S rispettivamente.

Il protocollo include il Diffie-Hellman come chiave di adesione,

usando un generatore g di un gruppo multiplo, con l’utilizzo di chiavi a lungo termine criptate.

La chiave di sessione K_AB è calcolata da A con K_AB=(g^NB) ^NAKS

e da B con K_AB=( g^NA ) ^NAKS. Uno valori effimeri NA e NB sono distrutti dalla chiave di sessione ancora compromessa dalle keys shared con S.

Key Compromise Impersonation

Quando un avversario impara la chiave a lungo termine di Alice l’avversario può impersonare Alice finchè la transazione è

scoperta e la chiave a lungo termine è revocata. Key compromise Impersonation si riferisce ad un attacco in cui l’avversario usa la chiave a lungo termine di Alice per mascherarla con un altro

utente.

Def. 2.15 Def. 2.15

Un protocollo fornisce resistenza alla Key Compromise Impersonation se la transazione della chiave a lungo termine di un soggetto A non permette all’avversario di mascherare A come un diverso soggetto.

Formal Verification of Protocols

Metodi principali per analizzare i protocolli di sicurezza:

 MODEL CHECKING: metodi che considerano un numero grande, ma finiti, possibili numeri di protocolli. Questi metodi sono generalmente adatti per trovare attacchi sul protocolli piuttosto che fornire la loro correttezza

 THEOREM PROVING: questi metodi considerano tutti i comportamenti possibili del protocollo, e permette di controllare che condizioni corrette siano soddisfatte. Questi metodi sono

generalmente più adatti per fornire i protocolli corretti, pittosto che cercare di fargli gli attacchi.

FDR

Lowe ha sviluppato un metodo per la verifica del protocollo di sicurezza usando FDR, un modello di ricerca per il

processo algebra CSP. Questo modello è stato usato per trovare un attacco previsto sconosciuto sul protocollo della chiave pubblica Needham-Schroeder. In questa

formulazione Lowe definisce alcuni protolli:

 comm: trasporta messaggi inviati da onesti titolari; comm:

 fake: trasporta messaggi introdotti dall’intruso;fake:

 Intercept: trasporta messaggi che sono uccisi dall’intruso;Intercept:

Murø

Murø (chiamato anche Murphi) è un modello generale di obbiettivi verificato con il suo linguaggio. E’ stato usato per verificare diversi tipi di protocollo e algoritmi per molti anni. Mitchell e al. usano Murø per analizzare 3 protocolli di key establishment. Questi descrivono la metodologia generale e i risultati delle loro analisi. I protocolli analizzati sono:

•Il Needham-Schroeder, protocollo di chiave pubblica;

• il TMN;

•Il Kerberos.

La metodologia utilizzata con Murø è simile a quella usata da FDR.

Mitchell identifica due differenze tra i due strumenti:

-FDR ha una nozione esplicita di canali per comunicare tra processi, mentre il modello del canale di comunicazione di Murø usa variabili distribuite

-Murø ha un ricco set di metodi per ridurre il tempo di ricerca richiesto per una scelta stabilita di parametri di protocollo

Brutus

E’ un modello di controllo di strutture realizzato per la creazione di protocolli crittografici. Clarke e al. lo svilupparono per

mostrare un ‘push-button’ di controllo per protocolli così da rendere più semplice per i designers ottenere una sicurezza nell’analisi formale. Se il problema è trovato con il protocollo poi Brutus provvederà ad un’attacco esplicito.

I messaggi sono formati da chiavi, nomi dei soggetti e nonces, come ad ogni dato serve. In questo caso è realizzato un perfect encryption, il quale richiedere che un testo cifrato {m}_k può solo essere formato dalle informazioni della chiave k e dal

messaggio m. Notare che questo significa che ogni criptaggio simmetrico deve essere non-malleabile. L’insieme dei messaggi conosciuti ad ogni soggetto è registrato.

NRL Analyzer

Una parte del progetto su chiavi a lungo-termine sull’analisi del protocollo crittografico è stata realizzata dall’US Naval Research Laboratory (NRL) che ha sviluppato un software per scopi-specifici conosciuto come Analyzer. E’ stato uno dei primi strumenti sviluppati per questo scopo ed è stato continuamente perfezionato nel corso degli anni.

L’Analyzer è un ibrido che possiede caratteristiche di entrambi i modelli di controllo ed è un dimostratore di modelli. Si parte inizialmente da un insicuro sguardo sullo stato generale, si cerca di vedere se lo stato che si vuole può essere raggiunto dallo stato iniziale.

Le specifiche di un protocollo consistono in una serie di elementi quali:

System state

System state: il quale include i valori conosciuti dall’avversario e i soggetti del protocollo, come eventi di sequenze che si sono verificati Protocol rules

Protocol rules: in cui descrive il comportamento dei dei soggetti onesti e cosa è stato imparato dall’avversario dopo ogni passaggio

Rewrite rules

Rewrite rules: in cui vengono definite le proprietà crittografiche, come e cosa criptare e decriptare sulle diverse operazioni.

BAN Logic

BAN= Burrows, Abadi, e Needham. Il BAN simulatore logico è stato diffuso in interessanti campi. Il costrutto del BAN logic tende ad essere breve e può essere ottenuta molto facilmente a mano. La sua sintassi distingue 3 tipi di oggetti primitivi:

•Principals

•Keys

•Nonces

Un messaggio del protocollo viene espresso come una formula logica.

Le regole dedotte dalla logica riflettono conseguenze intuitive della semantica dei costrutti logici. Tipicamente, una regola dedotta è letta,

‘if formulae X₁, …,x_n hold then formula Y holds’ scritto schematicamente come:

X₁, …,X_n Y

Esistono specifiche dimostrazioni di regole fornite dal BAN logic:

 Message-meaning rule

 Freshness rule

 Nonce verification rule

 Jurisdition rule

Strand Space Model

E’ una struttura per la produzione rigorosa di direttive matematiche per la correzione del protocollo. In accordo a Fabrega e al.,

dimostrazioni nel SSM possono essere più convincenti che in molte altre dimostrazioni ‘concettuali’.

Le correzioni dei protocolli tipici possono essere ottenuti senza il supporto automatico.

Uno strand rappresenta il comportamento di un soggetto o

dell’avversario in termini di messaggi inviati o ricevuti. Gli elementi di uno strand sono chiamati nodes e il set di tutti i possibili strand viene chiamato strand space. Nel modello strand space, l’invio di un

messagio m è rappresentato da +m e la ricezione è rappresentata da –m. Uno strand è inoltre una sequenza di messaggi prefissati. Per es. la sequenza

<+{N_A,A}_KB, -{N_A, N_B} _KA, +{N_B} _KB>

rappresenta una iniziazione di uno strend nel protocollo di Lowe- Needham-Schroeder per ogni particolare scelta dei parametri A, B,

L’idea principale per fornire proprietà di protocollo usando uno strand space consiste nell’utilizzare un principio induttivo su set ben fondati.

Le dimostrazioni nel SSM sono trasportate nel rispetto della struttura chiamata boudles(rappresenta anche l’esecuzione individuale di un protocollo).

Un boundle è ben fondato se:

•Ogni messaggio ricevuto da uno strand è attualmente inviato preventivamente in qualche strand presente nel boundle e

•Se un nodo va su uno strand poi tutti i nodi che sono stati preceduti sullo stesso strand si spostano sul nuovo strand

The Inductive Model

L’idea di utilizzare l’induzione è provare i risultati di tutti i possibili stati dei protocolli senza aver esplicitamente analizzato ognuno.

L’uso di induzione come tecnica per verificare i protocolli

crittografici fu inventato da Paulson usando un strumento chiamato Isabelle con la formulazione conosciuta come Higher Order Logic (HOL).

In ogni gruppo di messaggi H vengono definiti tre operatori:

•parts H rappresenta il set delle componenti che possono essere recuperate da H, dalle quali si potrebbero ricavare informazioni su alcune chiavi;

•analz H rappresenta il set delle componenti che possono essere recuperate da H, senza conoscere nessuna caratteristica (a parte da cosa potrebbe essere già presente in H)

•synth H è l’insieme dei messaggi che possono essere formati da H in aggiunta ai nomi dei soggetti, concatenati alle componenti dei messaggi, o criptati con le chiavi in H.

Comparison of Formal Methods Approches

Properties

Tool Type Language Usage

FDR Model checker CASPER ^Automatic

Murø Model checker Special ^Automatic

Brutus Model checker Special ^Automatic NRL Analyzer ^Hybrid Special ^User-guide

Athema Model checker Special ^Automatic

AAPA Theorem prover HOL ^Automatic

Isabelle Theorem prover HOL ^User-guide

2.5 Complexity-Theoretic Proofs of Security

Un’importante direzione delle ricerche nei protocolli crittografici fu creata da Bellare e Rogaway nel 1993 quando pubblicarono la prima dimostrazione matematica che una semplice entità di autenticazione era sicura.

L’approccio generale è lo stesso usato nelle comunità di ricerca crittografica per provare la sicurezza di algoritmi crittografici.

Questi complessi teoremi riducono le dimostrazioni; la sicurezza dell’algoritmo o del protocollo S è ridotta alla sicurezza di un

altro problema conosciuto P nel senso che se c’è un algoritmo efficiente che può interrompere S, esisterà un algoritmo per risolvere P.

Una limitazione: non è garantito che P è davvero difficile da risolvere; per esempio P potrebbe essere un problema di fattorizzazione di interi.

Shoup’s Simulation Model

Shoup ha sviluppato un modello in cui provare la sicurezza di protocolli, definito appunto Shoup’s Simulation Model.

In questo modello viene definito un processo suddiviso in due sistemi:

•Ideal system: l’avversario controlla la rete e sceglie tutte le chiavi e i valori casuali usati dal protocollo dei soggetti. L’avversario può

eseguire il protocollo inizializzando gli utenti, avviando e chiudendo sessioni, e interagisce con le applicazioni;

•Real system: l’avversario può anche controllare la rete ma non da chiavi o valori casuali scelti dai titolari del protocollo. L’avversario può inizializzare i titolari e invocare istanze dei soggetti rispondendo ai messaggi come nel modello di Bellare-Rogaway.

Shoup definisce tre sfumature di sicurezza definite dai diversi attacchi degli avversari:

 Static corruption

 Adaptive corruption

 Strong Adaptive corruption

Conclusion

Gli obiettivi del protocollo non sono semplici da definire, spesso per key establishment e authentication.

Comunque, una chiara comprensione di cosa un

protocollo è intenzionato a ottenere è un prerequisito per decidere se questo obiettivo può essere ottenuto.