Transcript Random Numbers

Initial SRAM State as a
Fingerprint and Source of True
Random Number for RFID Tags
Daniel E. Holcomb, Wayne P.
Burleson and Kevin Fu
University of Massachusetts, USA.
Slides by Oded Argon
1
Overview
What is RFID?
 RFID Identification Schemes
 Random numbers
 What is FERNS?
 SRAM cell
 FERNS experimental work
 Conclusion
 Questions

FERNS - InfoSec Seminar TAU 2009
2
What is RFID?
Small ID tag
 Has no power source – Low power

Even ultra low – the ‘RF’ part of RFID
 Powered up by the reader for every “ID
request”


Different applications
ID card
 Digital cash card
 Inventory management

FERNS - InfoSec Seminar TAU 2009
3
What is RFID? – cont.

Need an ID


The ‘ID’ part of RFID
Need Random numbers
For security reasons
 Need a new random number for every
power up


Need to be low cost

Billions of RFID tags
FERNS - InfoSec Seminar TAU 2009
4
RFID Identification Schemes

Non volatile memories
Static and reliable
 Complicated CMOS process
 Programming is needed


Fingerprint
Using some process variations
 Need dedicated circuitry (?)
 Impacted by noise

FERNS - InfoSec Seminar TAU 2009
5
Random Numbers

PRNGs
Pseudo Random Noise Generator
 Using some mathematical function
 Fully deterministic


TRNGs
True Random Noise Generator
 Using some physical random process
 Unpredictable

FERNS - InfoSec Seminar TAU 2009
6
Random Numbers – cont.

Needed by almost every cryptographic
algorithm


And thus by RFID tags
Needs to be unpredictable to be “strong”
– TRNGs
FERNS - InfoSec Seminar TAU 2009
7
What is FERNS?
Fingerprint Extraction and Random
Numbers in SRAM
 Set out to get the ID and RNG without
dedicated circuitry



Using existing CMOS storage – SRAM
Initial SRAM state based ID and RNG
FERNS - InfoSec Seminar TAU 2009
8
FERNS and RFID
Gives the tag its ID
 RNG for security
 Matches passive tags usage model


Get ID and a random number for every
powerup
FERNS - InfoSec Seminar TAU 2009
9
Standard SRAM cell

Made out of 6 transistors

Threshold voltage mismatch sets the
initial state of each cell
FERNS - InfoSec Seminar TAU 2009
10
SRAM cell – Initial state

Cells with large threshold mismatch
consistently stabilize to the same state


These make out the fingerprint
Cells with well matched thresholds are
highly sensitive to noise
Physically random noise will set its initial
state
 These are used to for the RNG

FERNS - InfoSec Seminar TAU 2009
11
SRAM cell – Initial state – cont.
Black bits – reliably initialize to 0
 White bits – reliably initialize to 1
 Gray – can initialize to
either one

FERNS - InfoSec Seminar TAU 2009
12
Testing Platforms

160 Virtual tags
256Byte blocks
 8 * 512KB SRAM chips
 Large dataset
 Able to test corner correlation cases

FERNS - InfoSec Seminar TAU 2009
13
Testing platforms – cont.

10 TI MSP430 Chips
256Byte SRAM memory
 Ultra low power
 Not passively powered
 Read out through JTAG

FERNS - InfoSec Seminar TAU 2009
14
Testing platforms – cont.

3 WISPs – Wireless Identification and
Sensing Platform
Passively powered
 256Byte SRAM

FERNS - InfoSec Seminar TAU 2009
15
FERNS for Identification

Latent print
A single print (initial state)
 Is effected by noise


Known print

Bitwise mean of latent prints
FERNS - InfoSec Seminar TAU 2009
16
FERNS for Identification – cont.

Black – ‘0’, White – ‘1’, Gray - Random
FERNS - InfoSec Seminar TAU 2009
17
FERNS for Identification – cont.

Three relevant distance quantities
Latent fingerprint and known fingerprint of
same device
 Latent fingerprint and all other devices
known fingerprint
 All distances between all known fingerprints


A simple hamming distance is used for
testing
FERNS - InfoSec Seminar TAU 2009
18
Test results analysis
160 Virtual tags
 800 latent fingerprints
 Incorrect prints differ by at least 685 bits
(out of 2048 bits)



Comparing known prints to other known
prints gives similar results
Correct prints differ by less than 109 bits
FERNS - InfoSec Seminar TAU 2009
19
Test results analysis – cont.
FERNS - InfoSec Seminar TAU 2009
20
Test results analysis – cont.
MSP430 – 10 known fingerprints
 300 latent fingerprints
 2700 incorrect matchings



300 correct matchings


Less than 10 came within 600 bits
Only 4 differed by more than 425 bits
No fully reliable threshold available
FERNS - InfoSec Seminar TAU 2009
21
Test results analysis – cont.
FERNS - InfoSec Seminar TAU 2009
22
Test results analysis – cont.

3 WISPs – 256 Byte each

15 known prints – 64 bit
150 latent fingerprints
 2100 incorrect matchings



None within 20 bits
150 correct mathings

Only 3 differed by more than 8 bits
FERNS - InfoSec Seminar TAU 2009
23
Test results analysis – cont.
FERNS - InfoSec Seminar TAU 2009
24
FERNS Identification – security

Randomized ID
Can be used as a large ID space for each
tag
 No two fingerprints of the same tag came up
during testing
 Can help prevent reply attacks by recording
history
 An adversary can still generate a
randomized print

FERNS - InfoSec Seminar TAU 2009
25
FERNS for TRNG
Well matched cells capture physically
random noise
 Well matched cells are randomly
scattered around the SRAM



The randomness is parallel


Randomness is unpredictably scattered
Contrary to most other TRNGs
Amount of entropy is unpredictable
FERNS - InfoSec Seminar TAU 2009
26
FERNS for TRNG - Security

The source of entropy is obscure


Can’t tell where are the well matched cells
Proximity of cells

Trying to influence one will likely influence
others
FERNS - InfoSec Seminar TAU 2009
27
FERNS for TRNG - Analysis

Tested on the virtual tags
Least random of the three platforms
 Most challenging


An average of 0.103 bits of entropy per
memory bit


Around 210 bits out of 2048 raw bits
Possible to produce 128 bit “keys”
FERNS - InfoSec Seminar TAU 2009
28
FERNS for TRNG - Analysis

Raw bits fail to pass entropy tests


NH polynomial (PH) universal hash
function as an entropy extractor


Tested using NIST test suite
Passes the same tests
Future work
Test the min-entropy of the raw bits
 Will ensure randomness of the hashed
output

FERNS - InfoSec Seminar TAU 2009
29
Conclusion

RFID tags are a challenging platform

Cost and security wise
Initial testing of FERNS seem to provide
a system for fingerprints and true
random numbers for RFIDS
 Quality of both need to be further tested

FERNS - InfoSec Seminar TAU 2009
30
Questions?
31