NHB : A MIM-SECURE HB-

LIKE PROTOCOLCarl Bosley, Stevens Institute of Technology
Joint work with Antonio Nicolosi and Kristiyan Haralambiev

1

[HB01] and descendents• Setting• RFID Authentication: Tag=Prover, Reader=Verifier• Hardness based on Learning Parity with Noise

2

Start descendents[HB01]andStart
Start
Start

TR

• Settinga• RFID Authentication: Tag=Prover, Reader=Verifier• Hardness based on Learning Parity with Noise• The Evolution of HB: A Whirlwind Tour• [HB01] passively secure

2TRaa�x ⊕ ea�x ⊕ eTRaa�x ⊕ eTRaa�x ⊕ eStart descendents[HB01]andStart
StartStartTR• Settinga• RFID Authentication: Tag=Prover,Start
StartReader=Verifier• Hardness basedon Learning Parity with NoiseStart• The Evolution of HB: A Whirlwind Tour• [HB01] passively secure• [JW05] HB+ actively secure

TRRTea�x ⊕aR�a x⊕eaTTRa�Ra a x ⊕ Te a�x⊕eabRT� ��
�a x⊕
ea x ⊕ b y ⊕ eaa x ⊕ eT a�x ⊕ e b R��R a x⊕b y⊕e aaa�x ⊕ e2Ta�x ⊕ eStart descendents[HB01]andStart
Start
StartTR• Settinga• RFID Authentication: Tag=Prover,Start
StartReader=Verifier• Hardness basedon Learning Parity with NoiseStart• The Evolution of HB: A Whirlwind Tour• [HB01] passively secure• [JW05] HB+ actively secureTRa�x T
⊕e2RTea�x ⊕aR�a x⊕eaTTRa

�

Ra a x ⊕ Te a�x⊕eabRT� ��
�a x⊕
ea x ⊕ b y ⊕ eaa x ⊕ eT a�x ⊕ e b R��R a x⊕b y⊕e aa• [GRS05] MIM attackTb(1)a�x ⊕ b’ea’(1)

a(1)

z1(1)

Az’1

R

Start descendents[HB01]andStartStartStart

TR• Settinga• RFID Authentication: Tag=Prover,Start
StartReader=Verifier• Hardness basedon Learning Parity with NoiseStart• The Evolution of HB: A Whirlwind Tour• [HB01] passively secure• [JW05] HB+ actively secureTR• Several MIM-secure variants: HB*, HB-MP, HB-MP’,

Trusted-HB2RTea�x ⊕aR�a x⊕eaTTRa�Ra a x ⊕ Te a�x⊕eabRT� ��
�a x⊕
ea x ⊕ b y ⊕ eaa x ⊕ eT a�x ⊕ e b R��R a x⊕b y⊕e aa• [GRS05] MIM attackTa�x T⊕eb(1)a�x ⊕ b’ea’(1)

a(1)

z1

(1)

Az’1

R

Start descendents[HB01]
andStart
Start
Start

TR

• Settinga• RFID Authentication: Tag=Prover,Start
StartReader=Verifier• Hardness basedon Learning Parity with NoiseStart• The Evolution of HB: A Whirlwind Tour• [HB01] passively secure• [JW05] HB+ actively secureTR• Several MIM-secure variants: HB*, HB-MP, HB-MP’,Trusted-HB• “If I call a tail a leg, how many legs does a dog have?”

2RTea�x ⊕aR�a x⊕eaTTRa

�

Ra a x ⊕ Te a�x
⊕eab
RT
� ��
�a x⊕
ea x ⊕ b y ⊕ eaa x ⊕ e
T a�x ⊕ e b R��
R a x⊕b y⊕e aa• [GRS05] MIM attackTa�x T⊕eb(1)a�x ⊕ b’ea’(1)

a(1)

z1

(1)

Az’1RStart descendents[HB01]andStartStartStartTR• Settinga• RFID Authentication: Tag=Prover,Start
StartReader=Verifier• Hardness basedon Learning Parity with NoiseStart• The Evolution of HB: A Whirlwind Tour• [HB01] passively secure• [JW05] HB+ actively secureTR• Several MIM-secure variants: HB*, HB-MP, HB-MP’,

a�x T
⊕e

Trusted-HB• “If I call a tail a leg, how many legs does a dog have?”• Lincoln may or may not have said that, but it is linked tohim by 1862: see snopes.com: http://tinyurl.com/3eff3nk2RTea�x ⊕aR�a x⊕eaTTRa

�

Ra a x ⊕ Te a�x⊕eabRT� ���a x⊕
ea x ⊕ b y ⊕ eaa x ⊕ eT a�x ⊕ e b R��
R a x⊕b y⊕e aa• [GRS05] MIM attackTb(1)a�x ⊕ b’ea’(1)

a(1)

z1

(1)

Az’1

R

Start descendents[HB01]
andStart
Start
Start

TR

• Settinga• RFID Authentication: Tag=Prover,Start
StartReader=Verifier• Hardness basedon Learning Parity with NoiseStart• The Evolution of HB: A Whirlwind Tour• [HB01] passively secure• [JW05] HB+ actively secureTR• Several MIM-secure variants: HB*, HB-MP, HB-MP’,a�x T⊕eTrusted-HB• “If I call a tail a leg, how many legs does a dog have?”• Lincoln may or may not have said that, but it is linked tohim by 1862: see snopes.com: http://tinyurl.com/3eff3nk• [GRS08a,FS09] Actually, not secure

2RTea�x ⊕aR�a x⊕eaTTRa�Ra a x ⊕ Te a�x⊕eabRT� ���a x⊕
ea x ⊕ b y ⊕ eaa x ⊕ eT a�x ⊕ e b R��R a x⊕b y⊕e aa• [GRS05] MIM attackTb(1)a�x ⊕ b’ea’(1)

a(1)

z1(1)

Az’1

R

Start descendents[HB01]andStart
Start
Start

TR

• Settinga• RFID Authentication: Tag=Prover,Start
StartReader=Verifier• Hardness basedon Learning Parity with NoiseStart• The Evolution of HB: A Whirlwind Tour• [HB01] passively secure• [JW05] HB+ actively secureTR• Several MIM-secure variants: HB*, HB-MP, HB-MP’,

a�x T
⊕e

Trusted-HB• “If I call a tail a leg, how many legs does a dog have?”• Lincoln may or may not have said that, but it is linked tohim by 1862: see snopes.com: http://tinyurl.com/3eff3nk• [GRS08a,FS09] Actually, not secure• [GRS08b] random-HB# MIM-secure2R

Tea�x ⊕aR�a x⊕eaTTRa

�

Ra a x ⊕ Te a�x
⊕eab
RT
� ��
�a x⊕
ea x ⊕ b y ⊕ eaa x ⊕ eT a�x ⊕ e b R��
R a x⊕b y⊕e aa• [GRS05] MIM attackTb(1)a�x ⊕ b’ea’(1)

a(1)

z1(1)

Az’1R

Start descendents[HB01]andStartStartStartTR• Settinga• RFID Authentication: Tag=Prover,Start
StartReader=Verifier• Hardness basedon Learning Parity with NoiseStart• The Evolution of HB: A Whirlwind Tour• [HB01] passively secure• [JW05] HB+ actively secureTR• Several MIM-secure variants: HB*, HB-MP, HB-MP’,a�x T⊕eTrusted-HB• “If I call a tail a leg, how many legs does a dog have?”• Lincoln may or may not have said that, but it is linked tohim by 1862: see snopes.com: http://tinyurl.com/3eff3nk• [GRS08a,FS09] Actually, not secure• [GRS08b] random-HB# MIM-secure• [OOV08] Actually, it’s not MIM-secure

2RTea�x ⊕aR�a x⊕eaTTRa

�

Ra a x ⊕ Te a�x
⊕eab
RT
� ��
�a x⊕
ea x ⊕ b y ⊕ eaa x ⊕ eT a�x ⊕ e b R��
R a x⊕b y⊕e aa• [GRS05] MIM attackTb(1)a�x ⊕ b’ea’(1)a(1)z1(1)Az’1

R

Start descendents[HB01]
andStart
StartStartTR• Settinga• RFID Authentication: Tag=Prover,Start
StartReader=Verifier• Hardness basedon Learning Parity with NoiseStart• The Evolution of HB: A Whirlwind Tour• [HB01] passively secure• [JW05] HB+ actively secureTR• Several MIM-secure variants: HB*, HB-MP, HB-MP’,

a�x T
⊕e

Trusted-HB• “If I call a tail a leg, how many legs does a dog have?”• Lincoln may or may not have said that, but it is linked tohim by 1862: see snopes.com: http://tinyurl.com/3eff3nk• [GRS08a,FS09] Actually, not secure• [GRS08b] random-HB# MIM-secure• [OOV08] Actually, it’s not MIM-secure• [KPCJV11] MAC1, MAC2 provably MIM-secure
2RTea�x ⊕aR�a x⊕eaTTRa�Ra a x ⊕ Te a�x
⊕eab
RT
� ��
�
a x⊕
ea x ⊕ b y ⊕ eaa x ⊕ eT a�x ⊕ e b R��
R a x⊕b y⊕e aa• [GRS05] MIM attackTb(1)a�x ⊕ b’ea’(1)a(1)z1(1)Az’1RStart descendents[HB01]
andStart
Start
StartTR• Settinga• RFID Authentication: Tag=Prover,Start
StartReader=Verifier• Hardness basedon Learning Parity with NoiseStart• The Evolution of HB: A Whirlwind Tour• [HB01] passively secure• [JW05] HB+ actively secureTR• Several MIM-secure variants: HB*, HB-MP, HB-MP’,

a�x T
⊕e

Trusted-HB• “If I call a tail a leg, how many legs does a dog have?”• Lincoln may or may not have said that, but it is linked tohim by 1862: see snopes.com: http://tinyurl.com/3eff3nk• [GRS08a,FS09] Actually, not secure• [GRS08b] random-HB# MIM-secure• [OOV08] Actually, it’s not MIM-secure• [KPCJV11] MAC1, MAC2 provably MIM-secure• but rather complicated2

RTea�x ⊕aR�a x⊕eaTTRa

�

Ra a x ⊕ Te a�x
⊕eab
RT
� ��
�
a x⊕
ea x ⊕ b y ⊕ eaa x ⊕ e
T a�x ⊕ e b R��
R a x⊕b y⊕e aa• [GRS05] MIM attackTb(1)a�x ⊕ b’ea’(1)a(1)

z1(1)

Az’1

R

Start descendents[HB01]andStart
StartStartTR• Settinga• RFID Authentication: Tag=Prover,Start
StartReader=Verifier• Hardness basedon Learning Parity with NoiseStart• The Evolution of HB: A Whirlwind Tour• [HB01] passively secure• [JW05] HB+ actively secureTR• Several MIM-secure variants: HB*, HB-MP, HB-MP’,

a�x T
⊕e

Trusted-HB• “If I call a tail a leg, how many legs does a dog have?”• Lincoln may or may not have said that, but it is linked tohim by 1862: see snopes.com: http://tinyurl.com/3eff3nk• [GRS08a,FS09] Actually, not secure• [GRS08b] random-HB# MIM-secure• [OOV08] Actually, it’s not MIM-secure• [KPCJV11] MAC1, MAC2 provably MIM-secure• but rather complicated2

RTea�x ⊕aR�a x⊕eaTTRa

�

Ra a x ⊕ Te a�x⊕eabRT� ��
�a x⊕
ea x ⊕ b y ⊕ eaa x ⊕ eT a�x ⊕ e b R��R a x⊕b y⊕e aa• [GRS05] MIM attackTb(1)a�x ⊕ b’ea’(1)

a(1)

z1(1)

Az’1R

N
[BHN] HB Protocol•Tools:•⊕: [0,1] x [0,1] -> [0,1]•LSN <=> LPN•Probabilistic Verification•Sequence of Games

StartN
HB and HB

Start

Start

art• HB is extremely simple:

TR• Tag computes noisy parity.

aTRaa�x ⊕ e

�

a x⊕e

TR

aa�x ⊕ e

TRaa�x ⊕ eStart

NHB and HB

Start

Start

art• HB is extremely simple:

TR• Tag computes noisy parity.

Start• HBN isStart
extremely simple:

art • Tag computes noisy bilinear function.

art

Start

Starta�TRTTRTa x⊕ea�axb ⊕ eRTa��a x⊕b y⊕e

RaR�a x⊕eaTa�x ⊕ eaa�x ⊕ e � T
T a x ⊕aR�eXb T⊕ e Rb, a�aXb R⊕eaRaa�x ⊕ Te �
� a x ⊕ eaabRx ⊕ ea�xe⊕ b�y ⊕ ea ba�x ⊕T a�ax�⊕x ⊕b�ey ⊕ e

Raa�Xb ⊕ e

TRaa�x ⊕ eStartNHB and HBStart

Startart• HB is extremely simple:TR• Tag computes noisy parity.

Start• HBN isStart
extremely simple:

art • Tag computes noisy bilinear function.

aRTTRTa x⊕ea

�axb ⊕ eRTa��
a x⊕b y⊕eRaR�a x⊕eaTa�x ⊕ eaa�x ⊕ e � Ta x⊕a�eXb T⊕ e RTRprotocol:[KPCJV11] Start
can be rewritten as applying aStartb, a�aXb R⊕ea
Rnoisy bilinear map• Interestingly, HBN is not the first bilinearart�Taa�x ⊕ Te �� a x ⊕ eaabRx ⊕ ea�xe⊕ b�y ⊕ ea ba�x ⊕T a�ax�⊕x ⊕b�ey ⊕ e

Raa�Xb ⊕ eTRaa�x ⊕ eStartN
HB and HBStart

Start

art• HB is extremely simple:

TR• Tag computes noisy parity.

Start• HBN isStart
extremely simple:

art • Tag computes noisy bilinear function.

aRTT

R

Ta x⊕ea�axb ⊕ eRTa��a x⊕b y⊕eRaR�a x⊕eaTa�x ⊕ eaa�x ⊕ e � Ta x⊕a�eXb T⊕ e RTRprotocol:[KPCJV11] Start
can be rewritten as applying aStartb, a�aXb R⊕ea
R
noisy bilinear map• Interestingly, HBN is not the first bilinear

art�T• New technique for defending against verify

queries: Probabilistic Verification.
• R computes wi = aTXb+fi

aa�x ⊕ Te �� a x ⊕ eaabRx ⊕ ea�xe⊕ b�y ⊕ ea ba�x ⊕T a�ax�⊕x ⊕b�ey ⊕ e

Raa�Xb ⊕ e

TRaa�x ⊕ eAdding Noise: ⊕ and ρ̅• Define ⊕: [0,1] x [0,1]→[0,1]: Berε ⊕ Berρ = Berε⊕ρ5Adding Noise: ⊕ and ρ̅• Define ⊕: [0,1] x [0,1]→[0,1]: Berε ⊕ Berρ = Berε⊕ρ• ε⊕ρ = (1-ε)ρ + (1-ρ)ε• ⊕ restricted to Z2 x Z2 is equivalent to ⊕5

Adding Noise: ⊕ and ρ̅• Define ⊕: [0,1] x [0,1]→[0,1]: Berε ⊕ Berρ = Berε⊕ρ• ε⊕ρ = (1-ε)ρ + (1-ρ)ε• ⊕ restricted to Z2 x Z2 is equivalent to ⊕• ! annihilates: ρ ⊕ ! = !

5

Adding Noise: ⊕ and ρ̅• Define ⊕: [0,1] x [0,1]→[0,1]: Berε ⊕ Berρ = Berε⊕ρ• ε⊕ρ = (1-ε)ρ + (1-ρ)ε• ⊕ restricted to Z2 x Z2 is equivalent to ⊕• ! annihilates: ρ ⊕ ! = !
• Pr[Berε = b] = b ⊕ ε̅• Pr[(a,b)←LPNεx] = 2-n(aTx ⊕ b ⊕ ε̅)• Pr[(a,b)←LSNρ,εx] = (b ⊕ ρ̅)(b ⊕ aTx ⊕ ε̅)2-n+15

LPNε ≤ LSNρ,ε ≤ LPNε1-ε• LSNρ,εx is a method ofproducing a noisy subspace fora, using LPNεx• Obtain b" from Berρ• Sample LPNεx until b=b"1-ρ

• We can annihilate, conditionally• b ← Ber! when aTx = 1ρεGame Sequence: Overall Idea
• Phase I & II keys: Xj & Yj
• Initially, X0 = Y0
• At each step, add random rank 1 matrix:• (X, Y) -> (X+(t+r)sT, Y+tsT) -> (X,Y+rsT)• With each layer, Xj and Yj grow further apart• after sufficiently many applications, aTX bT isj

TTcompletely independent of a Y bj

7

Conclusion• MIM-secure HB-like protocol• Simple, Efficient• Technical tools may be useful elsewhere• Available on eprint: 2011/350

Conclusion• MIM-secure HB-like protocol• Simple, Efficient• Technical tools may be useful elsewhere• Available on eprint: 2011/350• Open question: Improve efficiency• HB, HB+ are O(n2) computation

Conclusion• MIM-secure HB-like protocol• Simple, Efficient• Technical tools may be useful elsewhere• Available on eprint: 2011/350• Open question: Improve efficiency• HB, HB+ are O(n2) computation• HBN and [KPCJV] achieve O(n3) computation

Conclusion• MIM-secure HB-like protocol• Simple, Efficient• Technical tools may be useful elsewhere• Available on eprint: 2011/350• Open question: Improve efficiency• HB, HB+ are O(n2) computation• HBN and [KPCJV] achieve O(n3) computation• In upcoming work [BN] obtain ω(n2)• via ω(log n) rank matrix key• and Four Russians Matrix Multiplication trick