Protocolli HB+ e HB#
Lezione tenuta dal
Presentazione realizzata da
Prof. P. D’Arco
Giuseppe Marciano
Annunziato Fierro
Ivan Di Giacomo
Protocollo HB+

Il protocollo HB può resistere ad attacchi passivi ma è
insicuro rispetto ad attacchi attivi.

Il protocollo HB+ fu introdotto da Juels e Weis, per risolvere
questa vulnerabilità del protocollo HB.

2
Iterazione del Protocollo HB+
Reader
Tag
S: x,y є {0,1}n , ε
S: x,y є {0,1}n , ε
Sceglie b єR {0,1}n
Invia b
( fattore di blindatura )
Sceglie a єR {0,1}n
Invia a
( sfida )
Calcola r  ax  by  v
(v=1 con probabilità ε)
Risposta r inviata al Reader
r  ax  by
Se è uguale allora accetta
altrimenti rifiuta.

S= Segreto condiviso
ε= Probab. errore
3
Iterazione nel Protocollo HB+


Il protocollo viene ripetuto K volte,
ed il Reader accetta il tag se
al più K*ε volte ai x  bi y  ri
Ogni iterazione richiede 3 passi
invece di 2 (protocollo HB)
4
Robustezza del Protocollo HB+


Scegliendo ad ogni iterazione un nuovo
fattore di blindatura il tag priva
l’avversario della possibilità di estrarre
informazioni su x ed y con sfide scelte ad
hoc
HB+ si può provare sicuro rispetto ad
avversari attivi che possono interrogare il
tag, assumendo che il problema LPN sia
difficile
5
Protocolli HB, HB+ : parallelismo


E’ stato dimostrato che le versioni parallele e
concorrenti di HB e HB+ continuano ad essere
sicure rispetto ad avversari passivi (per HB) ed
attivi (per HB+) assumendo che il problema LPN
sia difficile
Problema aperto:
• provare la sicurezza di Hb+ in due round
invece di tre (i.e. il fattore di blindatura b
viene inviato insieme ad r)
6
L’attacco GRS contro HB+



Cosa
accade
se
l’avversario
può
intercettare e modificare le comunicazioni
tra Reader e Tag?
L’avversario sceglie un vettore ∆ di n bit
con cui perturbare le sfide inviate dal
Reader al Tag
A seconda del fatto che il Reader accetta
o no, l’avversario riesce a capire il valore
di ∆x con alta probabilità.
7
L’attacco GRS contro HB+
Reader
Tag
S: x,y є {0,1}n , ε
Sceglie b єR {0,1}n
Invia b
( fattore di blindatura )
Invia a.  
( sfida )
S: x,y є {0,1}n , ε
Sceglie a єR {0,1}n
Calcola
r  (a  ) x  by  v
(v=1 con probabilità ε)
Responso r inviato al
Reader
Ripeti K volte
r  ax  by
Se è uguale allora accetta
altrimenti rifiuta.

S= Segreto condiviso
∆ scelto dall’avversario
ε= Probab. errore
Usa lo stesso ∆ per
tutte le K interazioni del
protocollo
8
GRS contro HB+


Se al termine del protocollo il reader accetta,
l’avversario conclude che ∆x=0; viceversa, se il
Reader rifiuta, l’avversario conclude che ∆x=1
(nota che r  (a  )x by v  ax  x by v )
Usando ∆1, ∆2 , ∆3 … ∆n linearmente

indipendenti, dopo n esecuzioni (ognuna di
K interazioni) del protocollo l’avversario
riesce a ricostruire x attraverso il metodo di
Gauss
9
L’attacco GRS contro HB+
Reader
Avversario
Invia b
( fattore di blindatura )
S: x є {0,1}n
Sceglie b єR {0,1}n
Sceglie a єR {0,1}n
Invia a
( sfida )
Calcola r =ax
Responso r inviato al
Reader
Se il Reader accetta
Ripeti n volte
conclude che by=0
altrimenti che by=1
S: x,y є {0,1}n , ε
r  ax  by
Se è uguale allora accetta
altrimenti rifiuta.

S= Segreto condiviso
ε= Probab. Errore
In conclusione l’avversario calcola x ed y
10
Protocollo Random HB#


Il protocollo HB+ è sicuro rispetto ad attacchi attivi in cui
l’avversario può interrogare il tag, ma è insicuro rispetto ad
attacchi attivi in cui l’avversario può intercettare e
modificare le comunicazioni tra Reader e Tag.
Il protocollo Random HB# risolve questa vulnerabilità del
protocollo HB+.
Attacchi attivi
11
Interazione nel Protocollo Random HB#
Reader
Tag
S: matrici X,Y, ε
S: matrici X, Y, ε
Sceglie b єR {0,1}Ky
Sceglie v єR {0,1}K
Calcola
Invia b
( fattore di blindatura )
Invia a
( sfida )
z  aX  bY  v
(vi=1 con probabilità ε)
per i=1…K
Sceglie a єU {0,1}Kx
?
Responso z inviato al
Reader
Hw((aX  bY)  z)K
Se è minore o uguale allora
accetta altrimenti rifiuta.
S= Segreto condiviso

ε= Probab. errore
12
Interazione nel Protocollo Random HB#
•X matrice di dimensioni Kx * K
•Y matrice di dimensioni Ky * K
•X e Y scelte uniformemente a caso
Kx
a
Kx
Ky
b
a*X
K
X
=
+
K
Ky
Y
K
=
+
K
b*Y
v
13
Osservazioni





Le operazioni avvengono su vettori
Il protocollo richiede 3 passi ma un solo
round
E’ come se si eseguissero in parallelo più
istanze indipendenti di HB+
Ciascuna colonna di X e Y rappresenta
segreti diversi di un’istanza di HB+
Si può dimostrare che Random HB# è
sicuro rispetto ad avversari attivi se il
problema LPN è difficile
14
HB#


Quanta memoria serve nel
memorizzare le matrici? Troppa!
tag
per
Idea: Invece di usare X ed Y scelte
uniformemente a caso, usiamo matrici
strutturate
che
possono
essere
memorizzate più efficientemente
15
Matrici di Toeplitz


Una matrice di ordine K*m di Toeplitz, è
una matrice i cui elementi su ogni diagonale
che va dall’angolo in alto a sinistra,
all’angolo in basso a destra sono uguali
In questo caso basta memorizzare K+m-1
elementi invece di K*m
a b c
h a b

i h a

l i h
m l i

n m l
o n m

d
e
f
c d
b c
a b
h a
i h
l i
e
d
c
b
a
h
g
f 
e

d
c

b
a 
16
Conclusioni



HB# funziona
Random HB#
esattamente
come
Problema: per HB# la prova di
sicurezza di Random HB# non vale più
Purtroppo è stato mostrato che
Random HB# e HB# sono soggetti ad
attacchi del tipo Man-In-the-Middle.
17
Riferimenti
A. 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.