Research Results

Implementation

I implemented the HB and HB Plus Protocol in Java, and wrote a variety of programs for data collection. A copy of the README, which explains the implementation, is available here. The programs are available upon request.

Definitions

A lot of our research this summer centered on the concept of false positives and negatives.

  • A false positive is an invalid tag which is incorrectly accepeted by the reader.
  • A false negative is a valid tag which is incorrectly rejected by the reader.

Clearly, a secure protocol would minimize the number of both false positives and false negatives.

Recommended Parameters

Our results are based on data collected in the files HB data and graphs and HB+ data and graphs. In the following explanation, I use only selected graphs to illustrate our conclusions.

After implementing the protocols, we began by trying to determine the best values for four variable parameters used in both HB and HB+.

  • n, the number of queries. Default value: 200
  • p, the number of secrets. Default value: 50
  • the value of epsilon. Default value: 0.125
  • the value of delta. Default value: 0.0625

We collected data on our implementation of the HB and HB+ protocol by setting three of the parameters to the given default value, and varying the fourth parameter. Each box plot in our resulting graphs is composed from 50 percentages which were calculated from 5000 runs of the program. These graphs represent data collected from 32-bit secrets, queries, and blinding factors.

For these first eight graphs, the results of HP and HP+ were nearly identical, so we've chosen to show only HP.

Acceptance Ratio of HB Protocol with Varying Amount of Queries


This graph shows us that, as we would logically expect, as we increase the number of queries performed by the protocol, the number of good tags accepted increases.



Acceptance Ratio of HB Protocol with Varying Bounds


Similarly, as we let the bounds on epsilon become wider, more good tags are accepted. However, if the bounds become too wide, the number of bad tags accepted begins to be non-trivial.



Acceptance Ratio of HB Protocol with Varying Epsilon Values


This graph displays very interesting data behavior. As epsilon grows, the number of good tags accepted drops as might be expected, since it is more difficult to recognize a good tag when it is flipping it's responses more often. However, as epsilon approaches 0.5, it becomes more and more difficult to distinguish good tags from bad tags, and the reader begins accepting nearly anything.



Acceptance Ratio of HB Protocol with Varying Amount of Secrets


This graph shows us that the number of secrets seems to have little or no effect on the percentage of good tags accepted.



Incorrect Acceptances

This last graph went against our hypothesis that as the number of secrets increased, more good tags would be accepted. Our implementation was written so that the reader would accept if the tag's responses were within delta of any of the possible responses of the reader's list of good tags. Logically, as the number of secrets increased, the chance grew of a tag being accepted because the reader mistook it for a different tag on the approved list. We tested our hypothesis and created the following graph.

Probability of Accepting on the Incorrect Secret by HB Protocol

As the number of secrets increases, HB protocol begins accepting some tags on an incorrect secret. It is interesting to note that, when the same data collection program was run for HB+ for the same values of p, HB+ identified the correct secret for the tag 100% of the time. We concluded that having two secrets and two dot products significantly increased the ability of the HB+ to match the tag to the correct secret.



Predicting False Positives

The full data we collected on False Positives in HB and False Positives in HB+ is available in these files.

Our goal for this section of the research was to calculate the number of false positives for a reader with 1 secret, and k length queries and secrets. That is, we wish to calculate how many of the 2k possible tags will be accepted by a reader which should only accept one tag.

We made the following prediction for the number of secrets of length k accepted by a reader with 1 secret using n queries:

It turned out to be surprisingly accurate. The red dots on the following graph show the value of our equation for the given number of queries

The Number of False Positives Accepted by a Reader with 1 secret using the HB Protocol



More information about the way we discovered this forumla for predicting false positives is available in the final power point presentation given by Jenn and me at DIMACS on July 20, 2006: Reasonable Security Parameters for HB and HB Plus Protocols. Our abstract is available here.

Open Problems

The following are open problems which we did not have time to address this summer:

  • Extend the formula from 1 secret to p number of secrets.
  • Develop a similar formula for HB+.
  • Mathematically prove the validity or invalidity of the formula.
  • Show that the parameters our data show to be reasonably secure can be implemented on real RFID tags.
  • Extend Katz and Shin's proof to epsilon between ¼ and ½.