[Resource Topic] 2017/416: Breaking and Fixing the HB+DB protocol

Welcome to the resource topic for 2017/416

Breaking and Fixing the HB+DB protocol

Authors: Ioana Boureanu, David Gerault, Pascal Lafourcade, Cristina Onete


The HB protocol and its HB^+ successor are lightweight authentication schemes based on the Learning Parity with Noise (LPN) problem. They both suffer from the so-called GRS-attack whereby a man-in-the-middle (MiM) adversary can recover the secret key. At WiSec 2015, Pagnin et al. proposed the HB+DB protocol: HB^+ with an additional distance-bounding dimension added to detect and counteract such MiM attacks. They showed experimentally that HB+DB was resistant to GRS adversaries, and also advanced HB+DB as a distance-bounding protocol, discussing its resistance to worst-case distance-bounding attackers. In this paper, we exhibit flaws both in the authentication and distance-bounding layers of HB+DB; these vulnerabilities encompass practical attacks as well as provable security shortcomings. First, we show that HB+DB may be impractical as a secure distance-bounding protocol, as its distance-fraud and mafia-fraud security-levels scale poorly compared to other distance-bounding protocols. Secondly, we describe an effective MiM attack against HB+DB: our attack refines the GRS-strategy and still leads to key-recovery by the attacker, yet this is not deterred by HB+DB's distance-bounding. Thirdly, we refute the claim that HB+DB's security against passive attackers relies on the hardness of the LPN problem. We also discuss how (erroneously) requiring such hardness, in fact, lowers HB+DB's efficiency and its resistance to authentication and distance-bounding attacks. Drawing on HB+DB's design flaws, we also propose a new distance-bounding protocol: \mathbb{BLOG}. It retains parts of HB+DB, yet \mathbb{BLOG} is provably secure, even --in particular-- against MiM attacks. Moreover, \mathbb{BLOG} enjoys better practical security (asymptotical in the security parameter).

ePrint: https://eprint.iacr.org/2017/416

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .