RFID Authentication

RFID Authentication Efficient Proactive Information Security within Computational Security

This site was constructed by Roi Tzaig & Moria Damri

(email: roizaig@yahoo.com, damrimo@gmail.com)

for "RFID Authentication project"



Project target

This projects goal is to simulate the RFID One-Way Authentication protocol AP1, AP2 and ungeneralized and generalized devised by Prof. Shlomi Dolev as shown in this article.





rfid-tagRFID Radio Frequency Identification is a technology for tagging using radio waves.

A RFID tag is a small electronic device, supplemented with an antenna that can transmit and receive data. The RFID technology is designed for the unique identification of dierent kinds of objects.


RFID systems usually contain three parts:

rfid-tag-humanTag a microchip that can send and receive data (messages).

Verifier interfacing with the Tag, the Verifier can read/write data and sends messages to access the Tags data.

Data base a small amount of memory that uses as a data base that can be changed.


Due to their small size the RFID systems have a limit/ed computational power, and limit memory there for a "heavy" encryption algorithm can not be used by RFID systems.


The encryption algorithm, AP1 both ungeneralized and generalized, uses O(n) memory. In addition, the ungeneralized version transmits each time O(n) number and the generalized version transmits each time O(Log(n)). AP2 protocol uses One Time Pads technique are created by pseudo-random sequence using randomly created seed which is continuously updated in each communication session. is an upgrade of AP2 it can cope with an intruder in the middle of an attack (IIMA). The Intruder is able to capture the message, sent by the tag to the verifier, and modify it.


More extensive information can be found in the project report.


Typical scenario


Let us think of a typical scenario, an alarm car that uses RFID system to communicate between the remote control (the Tag) and the car alarm system (the Verifier), farther more a thief (an Adversary) may or may not listen to the communications. In We relax the assumption about the atomicity of each communication session. In order to deal with IIMA the message is added with redundant bits and watermark bits while no cryptographic hash function is used.





AP1 ungeneralized - When the Tag sends a request, it composes a message from the current ARV entry (ARV[keyentry]) concatenated with a pseudo random generated vector called LRV. When the Verifier gets the message, it checks if the ARV[keyentry] in the message is the same as its ARV[keyentry]. If so then an "Open" message is sent to the Tag and a xor update is preformed on ARV using LRV (update procedure) to both the Tag and the Verifier. If the ARV[keyentry] in the message is not the same as its ARV[keyentry] the "DoNotOpen" message is sent and neither the Tag nor the Verifier updates its ARV.


v    Message length is which is , so for an entire session (n consecutive communication) bytes will be transferred.


AP1 generalized - In every request, the Tag randomly selects indices of ARVs entries and stores them in Indices vector, then builds the vector reducedLRV by randomly selecting numbers. The tag then composes a message from ARV[Keyentry] concatenated with Indices and reducedLRV and sets it to the Verifier. When the Verifier get the message it checks if the ARV[keyentry] in the message is genuine and if so update only the ARV entries that was selected by the Tag.


v    Message length is which is , so for an entire session (n consecutive communication) bytes will be transferred.


AP2- When the Tag sends a request, it first create a pseudo random generated vector prs of length m = n * l +k where k is the keyword length and l is the length in bits of each ARV vector entry. The current ARV entry (ARV[keyentry]) xor with the old seed is used as a seed for the generation of the pseudo random sequence prs. The old seed is updated, (seed=ARV[keyentry] xor seed).

The Tag creates a new vector Y that should be send to the verifier. Y is equal to the xor of the vector prs with the pseudo random generated vector called LRV concatenated with the keyword. Y=prs xor (LRV||keyword). Y is then send to the Verifier.

Because we assume that both the Tag and the Verifier know how to produce the prs vector, when the Verifier gets the message, he can decrypt the it by calculating Y xor prs (which is equal to LRV||keyword) and checks if the suffix of the string

(Y xor prs)[n+1..m], is equal to keyword. If yes the Verifier return the message 'Open' to the Tag, else he return the message 'DoNotOpen'.

If the authentication successes, the updating procedure is called, and an update is preformed on the ARV vector using the LRV vector, in both, the Tag and the Verifier sides.


- In this protocol we split the seed into four independent seeds and which will be used to create pseudo-random sequences. The message is constructed as follows:



Let's explain the different parts of the message:

is generated as in, a concatenation of pseudo-random vector with a keyword. The LRV has entries each have bits and the keyword is of length . So the total length of this part is , as is so the xor of the last two also gives bits.

is a sequence of redundant bits generated as follows: looking at as a dimensions hyper-cube, where every redundant bit has the value of a parity check on one of the hyper-cube rows/columns.



q number of parity checks










According to the above table we get which give the equation:

The total length of the message is


Launch the simulation



You can download previous simulation file here:

1.     Source files (zipped).

2.     Binary files (zipped).



Roi Zaig & Moria Damri