HB+ Authentication

HB+ is a secure authentication protocol that is extremeley simple to implement in hardware. Its low implementation cost could make HB+ useful in preventing "skimming", counterfeiting, or cloning of cheap pervasive devices like RFID tags. HB+ was developed with Ari Juels of RSA Security and was presented at Crypto'05. HB+ builds on a protocol for human-to-computer authentication originally developed by Nick Hopper and Manuel Blum (HB).

Here are presentation slides from Crypto'05 and another page about HB/HB+.

HB+ Bibliography

• "Un-Trusted-HB: Security Vulnerabilities of Trusted-HB"
  Dmitry Frumkin and Adi Shamir
  
  Synopsis: Frumkin and Shamir show attacks against Trusted-HB
  
  
• "HB#: Increasing the Security and Efficiency of HB+"
  Henri Gilbert, Matthew J.B. Robshaw and Yannick Seurin
  EuroCrypt 2008
  
  Synopsis: Gilbert, Robshaw, and Seurin offer a variant of HB+ named HB# that is resistant to man-in-the-middle attacks.
  
  
• "PUF-HB: A Tamper-Resilient HB Based Authentication Protocol"
  Ghaith Hammouri and Berk Sunar
  ACNS 2008
  
  Synopsis: Hammouri and Sunar make use of physically unclonable functions (PUFs) to make a tamper-resilient HB variant.
  
  
• "Trusted-HB: a low-cost version of HB+ secure against Man-in-The-Middle attacks"
  Julien Bringer and Herve Chabanne
  
  Synopsis: Bringer and Chabanne offer a new HB+ variant that makes use of Krawczyk's hash-based authentication schemes using Topelitz-based LFSR constructions, and is resistant to man-in-the-middle attacks.
  
  
• "Analyzing the HB and HB+ Protocols in the ``Large Error'' Case"
  Jonathan Katz and Adam Smtih
  Eprint Archives
  
  Synopsis: Katz and Smith show how to extend proofs of HB+ security to the general case where the noise parameter $\epsilon < 1/2$. Previous results had shown HB+ to be secure only when $\epsilon < 1/4$.
  
  
• "An attack of HB+ in the detection-based model"
  Eric Levieil and Pierre-Alain Fouque
  Security and Cryptography for Networks - September 2006
  
  Synopsis: This paper offers an LPN algorithm with better constant factors than the Blum, Kalai, Wasserman algorithm. The steps to brute-force attack an HB+ instance are decreased and the lengths of secure HB+ keys will increase proportionally. See Section 2.8 of my PhD thesis for a discussion of HB+ key lengths.
  
  
• "HB++: a Lightweight Authentication Protocol Secure against Some Attacks"
  Julien Bringer and Herve Chabanne and Emmanuelle Dottax,
  Security, Privacy and Trust in Pervasive and Ubiquitous Computing - SecPerU, June 2006
  
  Synopsis: This paper presents a new HB+ variant that is claimed to be secure against man-in-the-middle attacks, such as those described by Gilbert, Robshaw, and Sibert. HB++ relies on additional secret key material and universal hash functions to detect man-in-the-middle attacks.
  
  
• "Parallel and Concurrent Security of the HB and HB+ Protocols"
  Jonathan Katz and Ji Sun Shin
  Advances in Cryptology -- EUROCRYPT, 2006
  
  Synopsis: This paper answers an open question from the original HB+ paper by showing that HB+ is indeed secure under concurrent and parallel composition. This greatly reduces the round complexity of HB+ to a constant three rounds for any security parameter.
  
  
• "An Active Attack Against HB+ - A Provably Secure Lightweight Authentication Protocol"
  Henri Gilbert and Matt Robshaw and Herve Sibert, 2005
  IEE Electronic Letters 41, 21, pgs 1169--1170, 2005
  
  Synopsis: This paper presents a man-in-the-middle attack against HB+. This attack requires many failed authentications to extract HB+ keys. It would not be feasible in a detection model where many failed authentications would raise an alarm.
  
  
• "Authenticating Pervasive Devices with Human Protocols"
  Ari Juels and Stephen A. Weis
  Advances in Cryptology -- CRYPTO 2005, Presentation Slides
  LNCS, volume 3621, pages 293-308, 2005
  
  Synopsis: This is the original HB+ paper.
  
  
• "Secure Human Identification Protocols",
  Nicholas J. Hopper and Manuel Blum,
  Advances in Cryptology - ASIACRYPT 2001, LNCS, volume 2248, pages 52-66, 2001
  
  Synopsis: This is the original paper that presents the HB protocol, which HB+ is based on. HB is not secure against passive adversaries, although two variants presented in this paper and based on other assumptions are secure against active adversaries.

---