HB and HB Plus Protocols

Protocol Design Goals

The HB Protocol was originally created by Nicholas Hopper and Manuel Blum as a tool for secure authentication and identification of unassisted humans to computers. It was developed as alternative to the traditional password method of human identification, and has the advantage that, unlike a password system, the secret id known by the human is never actually directly communicated to the computer. Juels and Weis realized that this protocol, which was designed for a system with little memory or computational power (humans), was actually a natural protocol for the authentication of RFID tags to readers.

Why are the protocols secure?

The security of the HB Protocol is based on the underlining hardness of the Learning Parity with Noise (LPN) problem. First, some definitions:

  • In a bit string (a string of 1's and 0's) the parity of a string is 1 if there are an odd number of 1's in the string, and 0 if there are an even number of 1's. Ex: 1011=s s has a parity of 1.

  • The bit-wise AND operation uses the following table:
    Ex: Using this table we see 1011&1110=1010

  • HB Protocol uses the inner dot product of two bit strings. To find an inner dot product take the bit-wise AND of two strings, and then find the parity of the result. Ex: the inner dot product of 1011=s and 1010=q is shown.

If we have several q's and r's, we can solve for the string s using linear algebra, as long as the q's are linearly independent, as shown.

The s, in this case, represents our secret ID, so we don't want it to be quite so easy to find. For this reason, we add "noise" by flipping the value of the single binary digit r randomly (with probability epsilon) This ensures that solving for s is as easy as solving the LPN problem, which is known to be NP-hard. So the HB Protocol is reasonably secure.

How does the HB Protocol work?

To begin, a few definitions:

  • The secret s is a k length binary string (ie, a sequence of k 1's and 0's). This is the identifying number for the tag. The tag needs to prove to the reader that it knows one of the s's on the reader's list of acceptable secrets. The tag only has one secret, but the reader generally has many.
  • A query q is also a k length binary string, just like the secret. This string is produced by the reader. One query is produced for each iteration of the protocol
  • Epsilon is a probability, ranging from 0 to ½ that the response calculated by the tag will be flipped (ie, if the correct response was 1, the tag will send back 0, and vice versa).
  • Nu equals 1 with probability epsilon.
  • Delta is an error factor, generally ranging between 0 and ½, which defines how close the tag's actual flipping of responses must be to epsilon in order to be accepted.

One execution of the HB Protocol consists of n parallel iterations of the following steps:

  1. The reader computes a query q, and sends the query to the tag.
  2. The tag computes the dot product of q and s, and then XORs the result with nu. The result of these computations is called r.
  3. The tag responds to the reader's query with r, the response.
  4. The reader computes the dot product of q and s, and calls this r'.
  5. The reader compares r' to r. If r'=r (so nu=0), the reader records an accept. Otherwise, the reader records a reject.

After n iterations, the reader expects the Tag to have about n*epsilon errors. The reader accepts the tag if it has (n*epsilon)+-delta errors.

Unfortunately, while the HB Protocol is secure against passive attacks, it proves insecure against active attacks. Another protocol is needed.

How does the HB+ Protocol work?

HB+ was designed by Ari Juels and Stephen Weis to withstand the sort of active attacks that HB is subject to. It differs from HB in two regards:

  • HB+ uses two secrets instead of one. Each tag has a pair of secrets, s1 and s2.
  • In HB+, the tag also can produce a k length binary query called a blinding factor b.

One execution of the HB+ Protocol consists of the n parallel iterations of the following steps:

  1. The reader computes a query q, and sends the query to the tag.
  2. The tag computes a blinding factor b, and sends it to the reader.
  3. The tag computes the dot product of q and s1, and the dot product of b and s2, and XORs these two quantities. It then XORs the result with nu, and this quantity is called r.
  4. The tag responds to the reader's query with r, the response.
  5. The reader computes the dot product of q and s1, and the dot product of b and s2, and then XORs the two. The result of this computation is r'.
  6. The reader compares r' to r. If r'=r (so nu=0), the reader records an acceptance. Otherwise, the reader records a rejection.

After n iterations, the reader expects the tag to have about n*epsilon errors. The reader accepts the tag if it has (n*epsilon)+-delta errors.

Unlike HB, HB+ is not susceptible to traditional active attacks. It is, however, susceptible to some Man-in-the-Middle attacks. For more about this, see the power point presentation given by Jenn and me at DIMACS on June 20, 2006: Encrypting RFID Tags