Transcript Physical Unclonable Functions for Device Authentication

0
Trusted Design In FPGAs
Steve Trimberger
Xilinx Research Labs
1
Security Challenges
• How to securely authenticate devices?
– Keycards, RFIDs, mobile phones
– Genuine electronics vs. counterfeits
• How to protect sensitive IP on devices?
– Digital content, personal information
– Software on mobile/embedded systems
• How to securely communicate with devices?
– Private and authentic communication channels
2
Traditional Solution: Authentication Example
•
Each IC needs to be unique
– Embed a unique secret key SK in on-chip non-volatile memory
•
Use cryptography to authenticate an IC
– A verifier sends a randomly chosen number
– An IC signs the number using its secret key so that the verifier can ensure that
the IC possesses the secret key
•
Cryptographic operations can address other problems such as protecting IP
or secure communication
IC with
a secret key
Sends a random number
Sign the number with a secret key
Only the IC’s key can generate
a valid signature
IC’s Public
Key
3
BUT…
• How to generate and store secret keys on ICs in a
secure and inexpensive way?
– Adversaries may physically extract secret keys
from non-volatile memory
– Trusted party must embed and test secret keys
in a secure location
– EEPROM adds additional complexity to manufacturing
• What if cryptography is NOT available?
– Extremely resource (power) constrained systems
such as passive RFIDs
– Commodity ICs such as FPGAs
4
Physical Unclonable Functions (PUFs)
• Extract secrets from a complex physical system
• Because of random process variations, no two Integrated Circuits
even with the same layouts are identical
– Variation is inherent in fabrication process
– Hard to remove or predict
– Relative variation increases as the fabrication process advances
• Delay-Based Silicon PUF concept
– Generate secret keys from unique delay characteristics
of each processor chip
Challenge
c-bits
Response
n-bits
Combinatorial
Circuit
5
Why PUFs?
(Challenge)
n
PUF
Response
• PUF can generate a unique secret key / ID
– Highly secure: volatile secrets, no need for trusted programming
– Inexpensive: no special fabrication technique
• PUF can enable a secure, low-cost authentication w/o crypto
– Use PUF as a function: challenge  response
– Only an authentic IC can produce a correct response for a challenge
• Questions
– How to design a PUF circuit?
– Does the concept work (reliable and secure)?
– How to use the PUF for key generation and authentication?
6
Ring Oscillator
even number of inverters
en_n
out
Ring Oscillator Module
• Ring oscillators are widely used in ICs to generate clocks
or characterize performance
• Each ring oscillator has a unique frequency even if many
oscillators are fabricated from the same mask
7
PUF Circuit Using Ring Oscillators
MUX
1
2467MHz
counter
2
Output
2519MHz
>?
0 or 1
N oscillators
counter
N
2453MHz
Top
Bot.
Out
1
2
0
1
N
1
2
N
1
Input
Compare frequencies of two oscillators  The faster oscillator is
randomly determined by manufacturing variations
8
Entropy: How Many Bits Do You Get?
• There are N! possible cases for ordering N oscillators
based on their frequencies
– Each ordering is equally likely
– For example, 3 oscillators R0, R1, R2 have 6 possible orderings
(R0, R1, R2), (R0, R2, R1), (R1, R0, R2), (R1, R2, R0),
(R2, R0, R1), and (R2, R1, R0)
• N oscillators can produce log2(N!) independent bits
• A reasonable number of oscillators can express keys
of long length
– 35 oscillators produce 133 bits
– 128 oscillators produce 716 bits
– 256 oscillators produce 1687 bits
9
Implementation Constraints
• All ring oscillators must be identical
– Any ring oscillator design will work
• No additional constraints required
– Everything is standard digital logic
– No placement/routing constraint outside oscillators
– Can be implemented even on standard FPGAs
1
Challenge
2
No placement /
routing constraint
Output
N
Identical layout
10
Errors?
• PUF output bit may “flip” when environment changes
significantly
Blue > Green
Blue > Green
Blue >
Green
Green >
Blue
Temperature
Temperature
• Insight: Comparisons between ring oscillators with
significant difference in frequency are stable even when
the environment changes
• Use “far apart” oscillator pairs to produce bits
– Mask bits indicate the selection
11
Validation Goal
• Security: Show that different PUFs (ICs) generate
different bits
– Inter-chip variation: how many PUF bits (in %) are different
between PUF A and PUF B?
– Ideally, inter-chip variation should be close to 50%
• Reliability: Show that a given PUF (IC) can re-generate
the same bits consistently
– Intra-chip variation: how many bits flip when re-generated again
from a single PUF
– Environments (voltage, temperature, etc.) can change
– Ideally, intra-chip variation should be 0%
12
FPGA Testing
• 15 FPGAs (Xilinx) with 1 PUF on each FPGA
• +/- 10% voltage variation experiments
• -20C to 120C temperature variation in
test chambers
• Combined voltage and temperature
variation tests
• Aging of FPGAs performed and
experiments re-run
– Did not change PUF outputs at all
13
RO PUF Characteristics
• 8000 bits from 1024 oscillators (paper shows results for 128 bits)
interchip
intra-chip, T=20C
intra-chip, T=-20
intra-chip, T=120
0.6
0.5
Variation
0.4
Average 46.6%
0.3
0.2
0.1
Maximum 0.6%
0
1.08
1.14
1.2
1.26
1.32
Core Voltage (V)
14
Key Generation: Initialization
Before
First Use:
Initialization
PUF
Circuit
n
Encoding
m
Syndrome/Mask
(public information)
• To initialize the circuit, an error correcting syndrome is
generated from the reference PUF circuit output
– Syndrome/error mask is public information
– Can be stored on-chip, off-chip, or on a remote server
• For example, BCH(127,64,21) code will correct up to
10 errors out of 127 bits
– Failure probability < 10-10
15
Random Symmetric Key Generation
In the Field:
Key Generation
PUF
Circuit
n
n
ECC PUF
Decoding
k
Hash
m
Syndrome/
Mask
• In the field, the syndrome will be used to re-generate the
same PUF reference output from the circuit
– This output is unique and unpredictable for each chip
– Can be directly used as a symmetric key
16
Private/Public Key Pair Generation
Private key
ECC
PUF
Seed
Key
Generation
Public key
• PUF response is used as a random seed to a private/
public key generation algorithm
– No secret needs to be handled by a manufacturer
• A device generates a key pair on-chip, and outputs a
public key
– The public key can be endorsed at any time
17
Low-Cost Authentication
• Protect against IC/FPGA substitution and counterfeits
without using cryptographic operations
Authentic
Device A
PUF
Challenge
???
PUF
Is this the
authentic
Device A?
Response
Record
Challenge
Untrusted
Supply Chain
/
Environments
Challenge
Response’
Response
1001010 010101
1011000 101101
0111001 000110
=?
Database for Device A
18
Challenge-Response Pairs
• What if an attacker obtains all responses and put them
into a fake chip with memory?
• There must be LOTS of challenge-response-pairs
– Use different parts on FPGAs
– Use configurable delay paths on ASICs
FPGA
FPGA
PUF
PUF
Oscillators
Challenge 1
Response 1
(left-bottom, 5 inv, etc.)
Challenge 2
Response 2
(right-middle, 3 inv, etc.)
19
An Arbiter-Based Silicon PUF
c-bit
Challenge
Rising
Edge
1
0
0
1
1
1
0
0
0
0
0
1
1
1
1
0
1
…
0
D Q
G
1 if top
path is
faster,
else 0
Response
• Compare two paths with an identical delay in design
– Random process variation determines which path is faster
– An arbiter outputs 1-bit digital response
• Multiple bits can be obtained by either duplicate the circuit or use
different challenges
– Each challenge selects a unique pair of delay paths
20
Arbiter PUF Experiments
• Fabricated 200 “identical” chips with PUFs in TSMC 0.18m on 5
different wafer runs
Security
– Inter-chip variation: 24.8%
on average
– Careful layout results in
50% inter-chip variation
(recent RFID PUF)
Reliability
– Intra-chip variation: 3.5%
when temperature changes
from 20C to 120C, 4% for
+/-10% voltage changes
21
Summary
• Process variations can be turned into a feature rather
than a problem
• PUFs can reliably generate unique and unpredictable
secrets for each IC
– Highly secure: volatile keys
– Inexpensive: standard digital logic
• PUF can be applied to
– Generation of both symmetric and asymmetric keys for
cryptographic operations
– Secure authentication of ICs without cryptographic operations
• PUF has been demonstrated on FPGAs and ASICs
– Even on passive RFIDs
22
Back-Up Slides
23
Security Discussion
• What does it take to find PUF secrets?
• Open the chip, completely characterize PUF delays
– Invasive attacks are likely to change delays
• Read on-chip register with a digital secret from PUF while the
processor is powered up
– More difficult proposition than reading non-volatile memory
• Still, this only reveals ONE secret from PUF
– Use two keys with only one key present on-chip at any time
• PUF is a cheap way of generating more secure secrets
24
ECC Security Discussion
Code word length =
Length of PUF response
Dimension of Code
Number of
Minimum distance
code words = 2k
= 2t + 1
Suppose we choose a (n, k, d) code
– Syndrome = n – k bits
 public, reveal information about responses
– Security parameter is k
 At least k bits remain secret after revealing the syndrome
– BCH (255, 107, 45) will correct 22 errors out of 255 response bits
and effectively produce 107-bit secret key
– Can get arbitrary size keys
– Theoretical study in fuzzy extractor [Smith et al]
25