Transcript Randomized PRF Tree Walking Algorithm for

Randomized PRF Tree
Walking Algorithm for
Secure RFID
Leonid Bolotnyy and Gabriel Robins
Department of
Computer Science
University of Virginia
[email protected], [email protected]
Talk Outline
• Identification Problem
– Secure Binary-Tree Walking Algorithm
• Reader-tag Authentication Problem
• Multi-tag RFID Systems
Identification Problem
Tags
Local Server
Reader
Tag ID
Tag ID
Secure Identification Problem
Tags
Local Server
Reader
Tag ID
Tag ID
Passive vs. Active Adversary
Reader
Tag
Eavesdropper
Backward Range
Forward Range
Secure Binary-Tree Walking
R. Rivest, S. Weis, EPCglobal, Inc.
i.
ii.
iii.
Each tag generates a random number
Reader tree-walks these random numbers
Selected tag transmits its real-ID
Traverse(i, count)
00
bi := Read random bit i
if collision on bi detected:
0
1
01
10
Suspend all tags with bi == 1
Each suspended tag stores i
Traverse(i+1, 0)
Wake up tags suspended on bit i
11
Traverse(i+1, 0)
else if no collision on bi detected:
000
001 010
011 100
101 110
111
if(count > threshold)
Tree-Walk remaining tags
else Traverse(i+1, count+1)
Algorithm Analysis
Major questions about the algorithm:
1. How to deal with collisions on real-IDs?
2. How to choose optimal random number length?
3. How to choose the threshold?
n: number of tags, m: random number length
Number of tags per random number will have a Poisson distribution
 
n
2
m
f (n, m, k )  2 * e
m

k

*
2m
k!
(Expected number of random IDs with k tags)
g (n, m)   f (n, m, k )  k
(Expected total number of colliding tags)
h( n, m)  t * m * cos tbit
(Cost function)
k 2
t 1
where t is the smallest exponent for which g  g ( g (m, n), m)  1
t
2
g (m, n)  g ( g (m, n), m)
Optimal random number length
Use average n over many traverse runs
2  k  5, 10  n  2000, 9  m  30
Determining threshold
ti 
n
2
i
(Expected number of tags on a branch after
Pr[ t i tags match in threshold number of bits] =
t i bits)
1
2threshold ( t 1)
i
For n = 2000, after about 11 bits, we expect zero, one, or two bits per branch
Still have a “long” way to finish traversing the tree
Costly over all branches if we traverse every branch to the end
Start the threshold at 2
Increase threshold by 1 if collision occurs
Decrease threshold by 1 if over the entire traverse no collisions occurred
Randomized PRF Tree Walking
Algorithm
Goal: Efficiently solve reader-tag authentication
problem in the presence of many tags
Steps of the algorithm:
1. Each tag generates a random number, and the reader
performs a tree-walk on these numbers
2. Once a tag is selected, the reader and the tag engage
in a tree-waking private authentication protocol
3. The reader moves the tag to a different position in a tree.
Binary Tree of Secrets
D. Molnar and D. Wagner
Privacy and Security in Library RFID
Issues, Practices, and Architecture
s 2, 0
s 3, 0
s 3, 1
s 3, 2
s1, 0
s1, 1
s 2, 1
s 2, 2
s 3, 3 s 3, 4
s 3, 5
s 2, 3
s 3, 6
s 3, 7
Step 1
Each tag generates a random number, and the reader
performs a tree-walk on these numbers
Traverse(i, count)
bi := Read random bit i
if collision on bi detected:
Suspend all tags with bi == 1
Each suspended tag stores i
Traverse(i+1, 0)
Wake up tags suspended on bit i
Traverse(i+1, 0)
else if no collision on bi detected:
if(count > threshold)
Proceed to step 2 with r  b1,..., bi
Tree-Walk remaining tags
else Traverse(i+1, count+1)
Step 2
Once a tag is selected, the reader and the tag engage
in a tree-waking private authentication protocol
s1, b , s 2, b , ..., sk , b  {0,1}n
1
2
k
Tag
Reader
Hello, r
t
r1i  R {0,1}n
for i  1 to k
r1i
r2i , bi , fs (0, r1i , r2i )   i
i , bi
check that
fs (0, r1i , r2i )   i
i , bi
fs (1, r1i , r2i )   i*
r2i  R {0,1}n
i , bi
check that
fs (1, r1i , r2i )   i*
i , bi
Step 3
The reader moves the tag to a different position in a tree
Reader
Tag
r1
 0  ID  fs (0,0, r 1)
 1  fs (0,1, r1)  t ', 2  fs (0,2, r1)  b ',
 i  fs (0, i, r1)  si  2, 3  i  secrets  2
k
k
k
k
check that
 0  fs (0,0, r1)  ID
compute
t   1  fs (0,1, r 1)
k
k
b   2  fs (0,2, r 1)
si   i  fs (0, i, r 1)
k
k
Properties of the Algorithm
•
•
•
•
Allows on-line addition and removal of tags
Provides security against active eavesdroppers
Offers security against foreign readers
Enables dynamic tradeoff between security,
privacy and singulation time
• Effective against active attacks
– stealing a tag
– tracking and hotlisting
• Requires a tag to be equipped with
– pseudo-random function, XOR unit
– random number generator
– writable memory
Space and Time Complexity
Evolution
n is the total number of tags in the system
O(n )
O(log n )
O(depthtree )
o(depthtree )
D. Molnar and D. Wagner
Our algorithm
Our algorithm assuming secrets are hard to steal
Our algorithm assuming tags are read often and/or
secrets are very hard to steal
O(1)
Random Number Generator
V
Will Ware
http://willware.net/hw-rng.html
Random Bits
No
Connect
The voltage signal is amplified, disturbed, stretched, and sampled,
resulting in random bits.
New Idea: Multi-Tags
Attach more than one tag to an object
• Redundant Tags
• Dual-Tags
– Own Memory Only
– Shared Memory Only
– Own and Shared Memory
• Triple-Tags
• n-Tags
1
2
3
4
Benefits of Multi-Tag Systems
New applications
• Increased expected voltage on a tag
• Increased expected communication range
– Increased availability
•
•
•
•
Increased memory
Increased reliability
Increased durability
Enhanced security
Our Current and Future Work
Find New and Improve Existing Algorithms
A. Juels, S. Weis
Authentication algorithms with human protocols
D. Molnar, D. Wagner
Tag identification with delegation, ownership transfer
A. Juels
Efficient cloning-resistant identification algorithms
New and emerging problems
Let’s Collaborate!