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.
Introduction
RFID – 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 different kinds of objects.
RFID systems usually contain three
parts:
Tag – 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.
Simulation
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.
Calcuation |
q
– number of parity checks |
Visualization |
Dimensions |
|
1 |
|
1 |
|
4 |
|
2 |
|
12 |
|
3 |
According to the above table we get which give the
equation:
The total length of
the message is
You can download
previous simulation file here:
Roi Zaig & Moria
Damri