### Practical Attacks on HB and HB+ Protocols

Zbigniew Golebiewski, Krzysztof Majcher, Filip Zagorski, and Marcin Zawada

##### Abstract

HB and HB+ are a shared-key authentication protocol designed for low-cost devices such as RFID tags. It was proposed by Juels and Weis at Crypto 2005. The security of the protocol relies on the learning parity with noise'' (LPN) problem, which was proved to be NP-hard. The best known attack on LPN (by Levieil and Fouque, SCN 2006) requires exponential number of samples and exponential number of operations to be performed. This makes this attack impractical because it is infeasible to collect exponentially-many observations of the protocol execution. We present a passive attack on HB protocol which requires only linear (to the length of the secret key) number of samples. Number of performed operations is still exponential, but attack is efficient for some real-life values of the parameters, i.~e.~noise $\frac{1}{8}$ and key length $144$-bits.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
lightweight cryptographyRFIDHBHB+passive attack
Contact author(s)
filipz @ im pwr wroc pl
History
Short URL
https://ia.cr/2008/241

CC BY

BibTeX

@misc{cryptoeprint:2008/241,
author = {Zbigniew Golebiewski and Krzysztof Majcher and Filip Zagorski and Marcin Zawada},
title = {Practical Attacks on HB and HB+ Protocols},
howpublished = {Cryptology ePrint Archive, Paper 2008/241},
year = {2008},
note = {\url{https://eprint.iacr.org/2008/241}},
url = {https://eprint.iacr.org/2008/241}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.