Paper 2017/416

Breaking and Fixing the HB+DB protocol

Ioana Boureanu, David Gerault, Pascal Lafourcade, and Cristina Onete

Abstract

The HB protocol and its $H{B}^{+}$ 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: $H{B}^{+}$ 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 $$; these vulnerabilities encompass practical attacks as well as provable security shortcomings. First, we show that $$ 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 $$: our attack refines the GRS-strategy and still leads to key-recovery by the attacker, yet this is not deterred by $$'s distance-bounding. Thirdly, we refute the claim that $$'s security against passive attackers relies on the hardness of the LPN problem. We also discuss how (erroneously) requiring such hardness, in fact, lowers $$'s efficiency and its resistance to authentication and distance-bounding attacks. Drawing on $$'s design flaws, we also propose a new distance-bounding protocol: $$. It retains parts of $$, yet $$ is provably secure, even --in particular-- against MiM attacks. Moreover, $$ enjoys better practical security (asymptotical in the security parameter).