Transcript How to generate random numbers on RFID Tag ?

How to generate random
numbers on RFID Tag ?
Kirti Chawla
[email protected]
Basic Problem and Challenges
> Basic Problem:
To generate reliable and unpredictable random numbers on a RFID tag
> Hardware description of RFID tag:
1. Battery (Active tags) or battery-less operation (Passive Tags)
2. Paper, PET (plastic) Inlay
3. Various form factors (stamp-size to PDA-size)
> Challenges:
1.
2.
3.
4.
Limited power supply (Passive tags power off reader supplied RF signal)
Limited circuit space (1 RFID tag ~ 4k-8k Gates)
Lower limits on circuit complexity (Limits the use of stronger RNG schemes)
Strength of generated random numbers (True-RNG, Pseudo-RNG)
Requirements and Approaches
> EPC C1 G2 Protocol for Communication at 860-960 MHz Requirement:
An EPC C1 G2 compliant Tag must contain a 16-bit random or pseudo-random number
generator
> A few candidate approaches:
1.
2.
3.
4.
5.
Direct Amplification
Oscillator Sampling
Discrete-time Chaos
Initial SRAM state
Physically Unclonable Functions (PUFs)
Approach 1: Direct Amplification
> How it works ?
1. Use high-gain high-bandwidth OP-AMP to process the AC voltage produced by a
noise (e.g. thermal or shot noise) source.
2. Noise must be sufficiently amplified to a level where it can be accurately captured
in a bias-free manner.
> More Precisely:
1
K.r(n) < VOffset
0
otherwise
K
B(n) =
r(n)
Paper: Craig S. Petrie, and J. Alvin Connelly , “A Noise-Based IC Random Number Generator for Applications in Cryptography”
B(n)
Approach 1: Direct Amplification
> Merits:
1. Popular technique for single-chip solution, where shielding of noise source is
possible.
2. Simple concept.
3. Less power and circuit-space requirement.
> De-Merits:
1. In an integrated circuit (IC) environment, lack of appropriate shielding of noise
source from power supply and substrate signals can prohibit the use of this
method.
2. May be affected by 1/f (pink) noise.
Approach 2: Oscillator Sampling
> How it works ?
1. Use free running oscillators as a source of phase noise to generate randomness.
2. Output of a fast oscillator is sampled on the rising edge of a slower clock using D
flip-flop.
3. Oscillator jitter causes randomness in exact sampled values.
> More Precisely:
1
t(n + 1) < m[C0 + C1r(n) + C2r2(n)]
0
otherwise
B(n) =
Where,
t(n+1)
r(n)
.t(n+1) = ((t(n) + Ts)MOD(C0 + C1r(n) + C2r2(n))
.m = fast oscillator duty cycle. [0, 1]
.C0, C1, C2 = Model non-linear transfer function
.Ts = slow clock frequency
.MOD = modulo operator
Paper: Craig S. Petrie, and J. Alvin Connelly , “A Noise-Based IC Random Number Generator for Applications in Cryptography”
B(n)
Approach 2: Oscillator Sampling
Merits:
1. More robust technique in the presence of deterministic noise.
2. Randomness can be artificially enhanced by careful selection of ratio of fast and
slow oscillator frequencies.
De-Merits:
1. Research shows that, certain levels of oscillator jitter are not sufficient to produce
statistical randomness.
2. Use of pseudo-random techniques to mitigate 1, can further degrade randomness
of the output.
Approach 3: Discrete-time Chaos
> How it works ?
1. Uses discrete-time analog signal processing techniques such as PWL system
2. Divergence of dynamic properties of the signal (or trajectory) and addition of noise
generates randomness.
> More Precisely:
1
i(n+1) < Iref
0
otherwise
B(n) =
Where,
.i(n+1) = A1[[BN(i(n) + r(n))] MOD Iref] + A0
.N = # of stages
.B = Stage gain
.Iref = Reference current
.A0 and A1 = Sample-Hold offset and gain
Paper: Craig S. Petrie, and J. Alvin Connelly , “A Noise-Based IC Random Number Generator for Applications in Cryptography”
Approach 3: Discrete-time Chaos
Merits:
1. Insensitive to the presence of deterministic noise.
2. Randomness is obtained from robust signal dynamic properties and not noise.
De-Merits:
Circuit inaccuracies that limit A/D resolution also lead to statistical non-randomness.
Approach 4: Initial SRAM State
> How it works ?
1. Process variation in SRAM cell enables the noise influence to determine the
outcome of the bit.
2. Well matched devices (based on doping concentration) are used as entropy
source. These devices are randomly scattered over the SRAM.
3. Uses entropy extractor to for fetching entropy from randomly scattered well
matched devices.
Paper: Daniel E. Holcomb, Wayne P. Burleson, and Kevin Fu, “Initial SRAM State as a Fingerprint and Source of True Random Numbers for RFID Tags”
Approach 4: Initial SRAM State
Merits:
1. Small volatile memory can be added to tag cheaply.
2. Use of Universal hash function provides statistical randomness.
De-Merits:
1. Gathered entropy from the scattered devices may not have statistical randomness.
2. Implementing Universal hash function can be costly on RFID tag.
Approach 5: PUFs
> How it works ?
1. Maps a set of challenges to a set of
responses using a intractably complex
physical system.
2. Process variation causes significant delay
differences between various ICs.
3. Relative delay between two paths can be
measured.
Paper: Charles W. O’Donnell, G. Edward Suh, and Srinivas Devadas, “PUF Based Random Number Generation”
Approach 5: PUFs
Merits:
1. PUFs generate statistical randomness.
2. Randomness is based on easily available process variation.
De-Merits:
1. Corrector / decorrelator is required.
2. It is possible that in 1 run less than desired no. of bits are produced.
References
1.
Charles W. O’Donnell, G. Edward Suh, and Srinivas Devadas, “PUF Based Random Number Generation”,
MIT CSAIL, Technical Memo, 2004
2.
Karsten Nohl, “Implementable Privacy for RFID Systems”, Ph.D Thesis, University of Virginia, 2009
3.
Damith C. Ranasinghe, “Lightweight Cryptography on Low cost RFID”, Networked RFID Systems and
Lightweight Cryptography, Springer, 2007
4.
Wenyi Che, Huan Deng, Xi Tan, and Junyu Wang, “A Random Number Generator for Application in RFID
Tags”, Networked RFID Systems and Lightweight Cryptography, Springer, 2007
5.
Craig S. Petrie, M and J. Alvin Connelly, “A Noise-Based IC Random Number Generator for Applications in
Cryptography”, IEEE Transactions on Circuits and Systems: Fundamental Theory, Vol. 47, No. 5, May 2000
6.
Ganesh K. Balachandran, and Raymond E. Barnett, “A 440-nA True Random Number Generator for Passive
RFID Tags”, IEEE Transactions on Circuit and Systems, Vol. 55. No. 11, December 2008
7.
Daniel E. Holcomb, Wayne P. Burleson, and Kevin Fu, “Initial SRAM State as a Fingerprint and Source of
True Random Numbers for RFID Tags”, RFIDSec, 2007
Questions ?