Paper 2008/241
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
Metadata
- Available format(s)
-
PDF
- 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
- 2008-06-02: received
- Short URL
- https://ia.cr/2008/241
- License
-
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},
url = {https://eprint.iacr.org/2008/241}
}
