Protocolli HB+ e HB#

Presentazione realizzata da

Giuseppe MarcianoAnnunziato FierroIvan Di Giacomo

Lezione tenuta dal

Prof. P. D’Arco

22

Protocollo HB+Protocollo HB+ Il protocollo HB può resistere ad attacchi passivi ma è Il protocollo HB può resistere ad attacchi passivi ma è

insicuro rispetto ad attacchi attivi.insicuro rispetto ad attacchi attivi.

Il protocollo HB+ fu introdotto da Juels e Weis, per risolvere Il protocollo HB+ fu introdotto da Juels e Weis, per risolvere questa vulnerabilità del protocollo HB.questa vulnerabilità del protocollo HB.

Attacch

i attiv

i Riconosciuto!

33

Iterazione del Protocollo HB+Iterazione del Protocollo HB+

ReaderS: x,y є {0,1}n , ε

Sceglie a єR {0,1}n

Se è uguale allora accetta

altrimenti rifiuta.

TagS: x,y є {0,1}n , ε

Sceglie b єR {0,1}n

Calcola

(v=1 con probabilità ε)

Invia b ( fattore di blindatura )

S= Segreto condiviso

ε= Probab. errore

vbyaxr

Invia a ( sfida )

€

r = ax ⊕by

Invia b ( fattore di blindatura )

Invia a ( sfida )

Risposta r inviata al Reader

Invia b ( fattore di blindatura )

Invia a ( sfida )

44

Iterazione nel Protocollo HB+Iterazione nel Protocollo HB+

Il protocollo viene ripetuto K volte, ed Il protocollo viene ripetuto K volte, ed il Reader accetta il tag se il Reader accetta il tag se

al più K* al più K*εε volte volte

Ogni iterazione richiede 3 passi Ogni iterazione richiede 3 passi invece di 2 (protocollo HB)invece di 2 (protocollo HB)

iii rybxa

55

Robustezza del Protocollo HB+Robustezza del Protocollo HB+

Scegliendo ad ogni iterazione un nuovo Scegliendo ad ogni iterazione un nuovo fattore di blindatura il tag priva fattore di blindatura il tag priva l’avversario della possibilità di estrarre l’avversario della possibilità di estrarre informazioni su x ed y con sfide scelte ad informazioni su x ed y con sfide scelte ad hochoc

HB+ si può provare sicuro rispetto ad HB+ si può provare sicuro rispetto ad avversari attivi che possono interrogare il avversari attivi che possono interrogare il tag, assumendo che il problema LPN sia tag, assumendo che il problema LPN sia difficiledifficile

66

Protocolli HB, HB+ : parallelismoProtocolli HB, HB+ : parallelismo

E’ stato dimostrato che le versioni parallele e E’ stato dimostrato che le versioni parallele e concorrenti di HB e HB+ continuano ad essere concorrenti di HB e HB+ continuano ad essere sicure rispetto ad avversari passivi (per HB) ed sicure rispetto ad avversari passivi (per HB) ed attivi (per HB+) assumendo che il problema LPN attivi (per HB+) assumendo che il problema LPN sia difficilesia difficile

Problema aperto: Problema aperto: • provare la sicurezza di Hb+ in due round provare la sicurezza di Hb+ in due round

invece di tre (i.e. il fattore di blindatura b invece di tre (i.e. il fattore di blindatura b viene inviato insieme ad r)viene inviato insieme ad r)

77

L’attacco GRS contro HB+L’attacco GRS contro HB+

Cosa accade se l’avversario può Cosa accade se l’avversario può intercettare e modificare le comunicazioni intercettare e modificare le comunicazioni tra Reader e Tag?tra Reader e Tag?

L’avversario sceglie un vettore ∆ di n bit L’avversario sceglie un vettore ∆ di n bit con cui con cui perturbare le sfideperturbare le sfide inviate dal inviate dal Reader al Tag Reader al Tag

A seconda del fatto che il Reader accetta A seconda del fatto che il Reader accetta o no, l’avversario riesce a capire il valore o no, l’avversario riesce a capire il valore di ∆x con alta probabilità. di ∆x con alta probabilità.

88

L’attacco GRS contro HB+L’attacco GRS contro HB+

ReaderS: x,y є {0,1}n , ε

Sceglie a єR {0,1}n

Se è uguale allora accetta

altrimenti rifiuta.

TagS: x,y є {0,1}n , ε

Sceglie b єR {0,1}n

Calcola

(v=1 con probabilità ε)

S= Segreto condiviso

∆ scelto dall’avversario

ε= Probab. errore

vbyxar )(

€

r == ax ⊕byResponso r inviato al Reader

Invia b ( fattore di blindatura )

Invia . ( sfida )

a

Responso r inviato al Reader

Invia b ( fattore di blindatura )

Invia . ( sfida )

Usa lo stesso ∆ pertutte le K interazioni delprotocollo

Ripeti K volte

99

GRS contro HB+GRS contro HB+

Se al termine del protocollo il reader accetta, Se al termine del protocollo il reader accetta, l’avversario conclude che ∆x=0; viceversa, se il l’avversario conclude che ∆x=0; viceversa, se il Reader rifiuta, l’avversario conclude che ∆x=1Reader rifiuta, l’avversario conclude che ∆x=1 (nota che )(nota che )

Usando ∆Usando ∆11, ∆, ∆22 , ∆ , ∆33 … ∆ … ∆nn linearmente linearmente indipendenti, dopo n esecuzioni (ognuna di indipendenti, dopo n esecuzioni (ognuna di K interazioni) del protocollo l’avversario K interazioni) del protocollo l’avversario riesce a ricostruire x attraverso il metodo di riesce a ricostruire x attraverso il metodo di GaussGauss

€

r = (a⊕Δ)x ⊕by ⊕v = ax ⊕Δx ⊕by ⊕v

1010

L’attacco GRS contro HB+L’attacco GRS contro HB+

ReaderS: x,y є {0,1}n , ε

Sceglie a єR {0,1}n

Se è uguale allora accetta

altrimenti rifiuta.

AvversarioS: x є {0,1}n

Sceglie b єR {0,1}n

Calcola r =ax

S= Segreto condiviso

ε= Probab. Errore

In conclusione l’avversario calcola x ed y

€

r == ax ⊕byResponso r inviato al

Reader

Invia b ( fattore di blindatura )

Invia a( sfida )

Invia b ( fattore di blindatura )

Invia a( sfida )

Invia b ( fattore di blindatura )

Ripeti n volteSe il Reader accetta

conclude che by=0

altrimenti che by=1

1111

Protocollo Random HB#Protocollo Random HB# Il protocollo HB+ è sicuro rispetto ad attacchi attivi in cui Il protocollo HB+ è sicuro rispetto ad attacchi attivi in cui

l’avversario può interrogare il tag, ma è insicuro rispetto ad l’avversario può interrogare il tag, ma è insicuro rispetto ad attacchi attivi in cui l’avversario può intercettare e attacchi attivi in cui l’avversario può intercettare e modificare le comunicazioni tra Reader e Tag.modificare le comunicazioni tra Reader e Tag.

Il protocollo Random HB# risolve questa vulnerabilità del Il protocollo Random HB# risolve questa vulnerabilità del protocollo HB+.protocollo HB+.

Attacchi attivi

1212

Interazione nel Protocollo Random HB#Interazione nel Protocollo Random HB#

ReaderS: matrici X,Y, ε

Sceglie a єU {0,1}Kx

Se è minore o uguale allora

accetta altrimenti rifiuta.

TagS: matrici X, Y, ε

Sceglie b єR {0,1}Ky

Sceglie v єR {0,1}K

Calcola

(vi=1 con probabilità ε)

per i=1…KS= Segreto condiviso

ε= Probab. errore€

Hw((aX ⊕bY)⊕ z)≤?

εKResponso z inviato al Reader

Invia a( sfida )

Invia b ( fattore di blindatura )

vbYaXz

1313

Interazione nel Protocollo Random HB#Interazione nel Protocollo Random HB#

•X matrice di dimensioni Kx * K

•Y matrice di dimensioni Ky * K

•X e Y scelte uniformemente a caso

Kxa

Ky

b

K

K

a*X

Ky

X

Y

=

+

= K

K

b*Y

Kx

+

v

1414

OsservazioniOsservazioni Le operazioni avvengono su vettoriLe operazioni avvengono su vettori Il protocollo richiede 3 passi ma un solo Il protocollo richiede 3 passi ma un solo

roundround E’ come se si eseguissero in parallelo più E’ come se si eseguissero in parallelo più

istanze indipendenti di HB+istanze indipendenti di HB+ Ciascuna colonna di X e Y rappresenta Ciascuna colonna di X e Y rappresenta

segreti diversi di un’istanza di HB+segreti diversi di un’istanza di HB+ Si può dimostrare che Random HB# è sicuro Si può dimostrare che Random HB# è sicuro

rispetto ad avversari attivi se il problema rispetto ad avversari attivi se il problema LPN è difficileLPN è difficile

1515

HB#HB#

Quanta memoria serve nel tag per Quanta memoria serve nel tag per memorizzare le matrici? Troppa!memorizzare le matrici? Troppa!

Idea: Invece di usare X ed Y scelte Idea: Invece di usare X ed Y scelte uniformemente a caso, usiamo matrici uniformemente a caso, usiamo matrici strutturate che possono essere strutturate che possono essere memorizzate più efficientementememorizzate più efficientemente

1616

Matrici di ToeplitzMatrici di Toeplitz Una matrice di ordine K*m di Toeplitz, è una Una matrice di ordine K*m di Toeplitz, è una

matrice i cui elementi su ogni diagonale che matrice i cui elementi su ogni diagonale che va dall’angolo in alto a sinistra, all’angolo in va dall’angolo in alto a sinistra, all’angolo in basso a destra sono ugualibasso a destra sono uguali

In questo caso basta memorizzare K+m-1 In questo caso basta memorizzare K+m-1 elementi invece di K*melementi invece di K*m

ahilmno

bahilmn

cbahilm

dcbahil

edcbahi

fedcbah

gfedcba

1717

ConclusioniConclusioni HB# funziona esattamente come HB# funziona esattamente come

Random HB#Random HB#

Problema: per HB# la prova di Problema: per HB# la prova di sicurezza di Random HB# non vale piùsicurezza di Random HB# non vale più

Purtroppo è stato mostrato che Purtroppo è stato mostrato che Random HB# e HB# sono soggetti ad Random HB# e HB# sono soggetti ad attacchi del tipo Man-In-the-Middle.attacchi del tipo Man-In-the-Middle.

RiferimentiRiferimentiA. Juels and S. Weiss, Authenticating pervasive devices with human protocols,Proc. of Crypto 2005, Lecture Notes in Computer Science, Vol. 3126, pp. 293–308, 2005.

H. Gilbert, M. J. B. Robshaw, and H. Sibert, An active attack against HB+ – a provably secure lightweight authentication protocol, Electronics Letters, Vol. 41, N. 21, pp. 1169–1170, 2005.

H. Gilbert, M. J. B. Robshaw, and Y. Seurin, HB#: Increasing the Security and Efficiency of HB+,Proc. of Eurocrypt 2008, Lecture Notes in Computer Science, Vol. 4965, pp. 361-378, 2008.

K. Ouafi, R. Overbeck, and S. Vaudenay, On the Security of HB# against a Man-in-the-Middle Attack, Proc. of Asiacrypt 2008, Lecture Notes in Computer Science, Vol. 5350, pp. 108-124, 2008.