Breaking and Fixing the HB+DB protocol

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$\u27s distance-bounding. Thirdly, we refute the claim that $HB+DB$\u27s 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$\u27s efficiency and its resistance to authentication and distance-bounding attacks. Drawing on $HB+DB$\u27s 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)