Transcript Dual-Tags Coordinated Reply Reader

Radio Frequency Identification Systems
New Ideas and Algorithms
Department of
Computer Science
University of Virginia
Leonid Bolotnyy and Gabriel Robins
School of Engineering & Applied Science
[email protected], [email protected]
Introduction to Radio Frequency Identification (RFID) Systems
 RFID Primer
 EPC System Architecture
 Three types of RFID tags
 Applications
www.cs.virginia.edu/robins
 Reader-Tag Communication
tag
Local Server
Reader
 Passive
 Active
 Semi-Active
tag
Tags
Tag ID
Tag ID
signal
signal
 Operational Frequencies
antenna
antenna
Tag ID
 125KHz - 5.8GHz
ID Info
 Operational Range
Tag ID
Inductive Coupling
Server IP
Object
Server
 5mm - 15m
 Major Research Issues
 Standardization Bodies
 International Organization
for Standardization
 EPCglobal, Inc
Far-Field Propagation
 Reducing the cost of tags
 Providing security and privacy
 Standardizing the technology
ONS Server
Infrastructure
ONS Server
Multi-Tag RFID Systems
 Attach more than one tag to an object  Voltage on a tag
 Optimal Tag Positioning
V 0  2 fNSB 0 cos 
B-field
Request
1
where:
Tag1
f = frequency of the arrival signal
N = number of turns of coil in the loop
Expected Absolute Voltage Increase Factor
S  area in the loop in meters (m )
2

3
Increase Factor
B 0 = strength of the arrival signal
 = angle of the arrival signal
Tag
Inductive Coupling:
Voltage sin(90   )
Far-Field Propagation: Voltage sin 2 (90   )
65
 Reliability and Dependability
1

4
2

 [  x (2 cos x)dx   (  x) (2 cos x)dx] / 
0
4
2
Increase Factor
47.98

40

32.7
 [  x (2 cos x)dx]/(2 )
2
0
Reader }
Inductive Coupling
}
Data1, Error
else {
3
4
Reader }
Tag2: Same procedure as Tag1
(note: probability that the Power1 == Power2 is tiny)
1.9
2
1.9
1.8
1.7
1.6
1.5
1.4
1.3
1.2
1.1
1
0.9
1
2
3
Far-Field Propagation
1.31
Inductive Coupling
1.07
1.37
1.15
30
1.57
1.6
1
1.37
1.4
Far-Field Propagation
1.3
Inductive Coupling
1.2
1.1
1.04
2
1.5
1.63
1
1.06
1.08
1.09
2
3
4
1
3
1
Num ber of Tags
4
Num ber of Tags
Number of Tags
 Effect on Singulation Algorithms  Security Enhancement
Algorithm
Binary
Binary Variant
Randomized
STAC
Slotted Aloha
 to increase chances of object detection
 Luggage tracking
 regulations require different algorithms
 Preventing illegal deforestation
 tagging of trees to prevent illegal logging
Traverse(i, count)
bi := Read random bit i
if collision on bi detected:
Suspend all tags with bi == 1
Each suspended tag stores i
* If Dual-Tags communicate to form a single response
** Assuming an object is tagged with two tags
n-Tags send “chaff” hiding the real IDs
Recycled IDs are good “chaff” source
“Chaffing and winnowing” has a cost
extra tag functionality
overhead to create and filter “chaff”
Allows tags addition and removal from the system
Provides security against active eavesdroppers
Offers security against active readers
Enables dynamic tradeoff between security, privacy,
and singulation time
Effective against active attacks:
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
Traverse(i+1, 0)
else if no collision on bi detected:
if collision on bi detected:
Suspend all tags with bi == 1
if(count > threshold)
Tree-Walk remaining tags
Each suspended tag stores i
Traverse(i+1, 0)
else Traverse(i+1, count+1)
Wake up tags suspended on bit i
Traverse(i+1, 0)
 stealing a tag
 tracking and hotlisting
else if no collision on bi detected:
if(count > threshold)
Proceed to step 2 with r  b1,..., bi
 Major questions:
 Optimal Random Number Length
Dual-Tags
No Effect
No Effect
No Effect*
No Effect*
No Effect*
Goal: Efficiently solve reader-tag authentication problem in the presence of many tags
 Steps of the algorithm
 Properties
Traverse(i+1, 0)
Wake up tags suspended on bit i
How to deal with collisions on the tags’ real-IDs?
How to choose the optimal length for random numbers?
How to select the threshold?
Redundant Tags
No Effect
No Effect
Doubles Time**
Causes DOS
Doubles Time**
Randomized PRF Tree Walking Algorithm
Randomized Tree Walking Algorithm
Secure Binary Tree-Walking
i. Each tag generates a random number
ii. Reader performs a tree-walk
iii. Selected tag transmits its real ID
if(Data1 == Data2) {
Data1
if(Power1 >= Power2) {
1.7
 Supply chain management
Forward Range
1.63
1.57
2
Tag1
Expected Factor of Distance Increase
45
 leaves the system functional
 is detectable in some systems
Backward Range
Far-Field Propagation
Num ber of Tags
 Applications of Multi-Tags
Eavesdropper
1
Data2, Power2
Expected Relative Voltage Increase Factor
50
Object’s detection is more likely
Failure of a redundant tag
Tag
1.5
Tag2
58.11
55
35
Tag1:
1.9
1.37
Data1, Power1
2.66
2.5
2
Tag1, Tag2
61.86
60
Angle (in Degrees)
Increased expected voltage on a tag
Increased expected communication range
Increased memory
Increased reliability
Increased durability
2.48
Tag2
1
 Expected Largest Angle of Incidence
 Benefits of Multi-tags
Reader
4
3
2
Reader
Increase Factor
Redundant Tags
Dual-Tags
Private memory only
Shared memory only
Shared and private memory
n-Tags
 Dual-Tags Coordinated Reply
 Time and Space Complexity
n is the total number of tags in the system
Tree-Walk remaining tags
else Traverse(i+1, count+1)
O(n )
2. Once a tag is selected, the reader and the tag engage
in a tree-waking private authentication protocol
2
k
Tag
Reader
Use average n over many traverse runs
Hello, r
t
r1i  R {0,1}n
for i  1 to k
r , bi , fs (0, r , r )   i
i , bi
i , bi
i
1
r2i  R {0,1}n
i
2
fs (1, r1i , r2i )   i*
i
2
O(1)
V
i
2
fs (0, r , r )   i
i
1
o(depthtree )
 Random Number Generation Hardware
r1i
check that
O(depthtree )
: represents related work improvement
: represents our improvement as shown
: represents our improvement with some modifications
s1, b , s 2, b , ..., sk , b  {0,1}n
1
O(log n )
i , bi
check that
fs (1, r1i , r2i )   i*
i , bi
Random Bits
3. The reader moves the tag to a different position in a tree.
Reader
Tag
r1
No
Connect
 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
 Threshold Selection
Start the threshold at 2
Increase threshold by 1 if a collision occurs
Decrease threshold by 1 if no collisions occur for entire traversal
 Future Work
k
k
s1, b , s 2, b ,..., sk , b  shared secrets
f  family of pseudo-random functions
r  random number
t  tree identifier
b  tag's position in a tree
1
2
k
The voltage signal is amplified, disturbed, stretched,
and sampled, resulting in random bits.
check that
 0  fs (0,0, r1)  ID
compute
t   1  fs (0,1, r 1)
b   2  fs (0,2, r 1)
si   i  fs (0, i, r 1)
k
k
k
k
Field testing of Multi-tags
Identifying new applications of Multi-tags
Improving hardware complexity of the algorithm
Developing new efficient authentication