Project Description

Motivation

RFID (Radio Frequency Identification) tags appear poised to replace barcodes as the product identification technology of choice for a growing number of applications. RFID tags are small (most are no bigger than a postage stamp) and quite durable. They require no internal power supply and they are cheap to produce; currently one RFID tag sells for fifty cents, and the price is expected to drop to five cents a tag as demand increases. Additionally, with 264 possible tags, each individual item can be given its own identification number.

RFID technology is becoming ubiquitous. Walmart and the United States Military both require their largest suppliers to use RFID tags for product identification. Many toll collection systems utilize this technology, as well as mass transit passes, such as the London Oyster Card. Toyota uses RFID tags in the new keyless entry system for their Prius, and Levi Strauss has announced that it will use the tags in clothing shipments to select stores. Future proposed applications include implanting RFID tags in passports, currency, and even prescriptions, allowing pill bottles to sense each other and warn users about bad drug combinations.

Some of these applications are accompanied by serious security concerns. Privacy advocates worry that RFID equipped clothing could allow retailers to tailor electronic advertising to specific customers, as in Minority Report. More sinister privacy invasions might also be possible: with the aid of an RFID reader, criminals could track individuals using the tags implanted in their clothing and, if RFID tags are implanted in currency as expected, also ascertain how much cash an individual is carrying.



HB and HB+ protocols

Clearly, a secure authentication protocol is needed. Each tag contains a 64 bit identity, or secret. A successful protocol would ensure, with reasonable accuracy, that a tag 'knew' the correct secret, without actually transmitting that secret to the reader. Unfortunately most of traditional encryption schemes for such secrets used today (such as RSA based schemes which rely on the fact that it is difficult to factor large integers) require too much computational power to be performed by RFID tags

In their paper, Jules and Weis[3] propose using a modified form of the HB protocol for the tag to authenticate itself to the reader. HB protocol was originally suggested by Hopper and Blum[2] as a more secure alternative to passwords for use in human authentication. Jules and Weis call the new modified form HB+, and prove that unlike HB, this protocol is not susceptible to active attack (with the notable exception of man-in-the-middle attacks[1]).


Research Goals

This summer, Jenn and I plan to implement the HB and HB+ protocols in Java and C++ and explore some of the following questions:

  • Multiple Tags: What are the security advantages and disadvantages of the following two systems?
    1. The reader asks the tag for an individual ID and check the tag's responses against only the secret associated with that ID
    2. The reader checks the tag's responses against all possible secrets.
  • Can Katz and Shin's security proof[4] be implemented using realistic parameters? If so, what are those parameters?
  • Can meaningful security guarantees be made for epsilon between ¼ and ½?

References

[1] H. Gilbert, M. Robshaw, and H. Silbert. An Active Attack Against HB+ - a Provably Secure Lightweight Authentication Protocol. Available at http://eprint.iacr.org/2005/237.pdf

[2] N. Hopper and M. Blum. Secure Human Identifcation Protocols. Adv. In Cryptology - Asiacrypt 2001, LNCS vol. 2248, pp. 52-66, 2001.

[3] A. Juels and S. Weis. Authenticating Pervasive Devices with Human Protocols. Adv. In Cryptography - Crypto 2005, LNCS vol. 3621, Springer-Verlag, pp. 293-308, 2005. Updated version available at: http://www.rsasecurity.com/rsalabs/staff/bios/ajuels/publications/pdfs/lpn.pdf

[4] J. Katz and J. Shin. Parallel and Concurrent Secuirty of the HB and HB+ Protocols. Available at http://eprint.iacr.org/2005/461.pdf