Summer 2006 Stevens Institute of Technology & DIMACS REU

Jennifer Tam, Tufts University

Mentors:: Rebecca Wright, Stevens Institute of Technology Associate Professor of Computer Science; Suanne Wetzel, Stevens Institute of Technology Assistant Professor of Computer Science

Research Partner:: Kelsey Livingston, Smith College

Click here for the power point presentation that Kelsey and I gave at Rutgers on June 20, 2006. (*Note that there is animation in the slides)

What are RFID Tags?:

Radio Frequency IDentification (RFID) tags are small devices that can be easily placed in all sorts of products.
Their popularity is growing as they can be used as:

Tracking devices in merchandise and animals.
"Keys" to allow access into buildings.
Electronic Toll Collectors such as the E-ZPass system.
Electronic Cash in "smart cards" (credit cards).
Unique identifiers in passports.
...and many other things.

The tags require little or no power and perform simple functions. The tag's reader often supplies enough power to the tag to carry out the functions necessary. Concerns have developed over privacy issues due to the tags' abilities to track information about its user. Purchasing habits, prescriptions, and other personal information would be available to anyone able to decipher the tag. Encryption methods have been created in an attempt to maintain privacy. Because the tags have little computational power, the protocols developed are not always perfectly secure.
Whatever encryption method is implemented in the RFID tag must use little computational power to keep the cost of manufacturing such a tag low.

Introduction:

We will be simulating and analyzing two possible encryption techniques for RFID tags.
The first protocol, HB, [1] was created to withstand passive attacks where an adversary can eavesdrop on the communications between the tag and reader.

The Reader sends a query to the Tag.
The Tag computes the inner product of its secret and the query.
The Tag changes the value calculated in step 2 with a probabiliy epsilon.
The Tag sends the result of step 3 to the Reader.
The Reader checks the result.

These five steps constitute one iteration of the HB protocol. However, many queries are needed, and so the protocol can be run in parallel to get the results in step 5 quickly. The Reader will then accept the tag as valid if the tag sent the correct inner product with epsilon probability. Because the tag will alter its result with probability epsilon in step three of the protocol, a eavesdropper will not be able to recreate the secret.
The hardness of this problem is based on the assumed NP-hardness of the Learning Parity with Noise Problem (LPN).

The second protocol, HB+, [2] was created to withstand reasonable active attacks. HB+ runs similarly to HB, but with the addition of a second secret and a randomly generated blinding factor.

The Tag generates a random blinding factor and sends it to the Reader.
The Reader sends a query to the Tag.
The Tag computes the inner product of its first secret and the blinding factor. It then xors the result with the inner product of its second secret and the query.
The Tag changes the value calculated in step 3 with a probabiliy epsilon.
The Tag sends the result of step 4 to the Reader.
The Reader checks the result.

Because the Tag generates the blinding the factor, a passive attacker cannot gain enough data to recreate the secret. However, an active attacker using a man-in-the-middle approach may be able to recreate the secret [3].

Tentative Project Goals:

We will implement the HB and HB+ protocols using java and C++ to analyze properties of the protocols, see whether an actual RFID tag is capable of handling such protocols, and to pursue the implications of a man-in-the-middle attack. The programs will have the ability to input or generate random secrets, queries, and blinding factors. The user will also be able to input epsilon, upper and lower acceptance bounds, the number of queries, and the number of iterations to be performed.

We will also determine the best way for the Reader to accept a tag. We will be attempting to answer such questions as:

Should Tags submit an ID along with its response?
Should Readers check only responses corresponding to an ID that tags submit, or should they accept any tag that matches any possible response?
How will the number of queries and secrets affect the outcomes of accepting a valid tag and attacker?

From the Katz & Shin proof, [4] we will attemp to answer such questions as:

Does the proof imply security for "reasonable" parameter?
What epsilon should be chosen?
What kind of RFID tags are capable of handling parameters?
What happens if we don't assume that randomness is freely available?
Can a tag produce randomness as is necessary in the HB+ protocol?
Can an improved proof of the protocols be written for epsilon < 1/2? Can such a result be statistically shown?

To see our results click here.

Sources:

[1]Hopper, Nicholas J., and Michael Blum. "Secure Human Identification Protocols." Advances in Cryptology. Asiacrypt. 2001. Secure Human Identification Protocols

[2]Juels, Ari and Stephen A. Weis. "Authenticating Pervasive Devices with Human Protocols." Crypto 2005. Authenticating Pervasive Devices with Human Protocols

[3]Gilbert, Henri, Matthew Robshaw, and Herve Sibert. "An Active Attack Against HB+ - A Provably Secure Lightweight Authentication Protocol." 2005. An Active Attack Against HB+ - A Provably Secure Lightweight Authentication

[4]Katz, Jonathan and Ji Sun Shin. "Parallel and Concurrent Security of the HB and HB+ Protocols." Eurocrypt 2006. Parallel and Concurrent Security of the HB and HB+ Protocols