Randomnes in Hardware security

Question 1

Secure Integrated

Circuits (ICs)

Answer 1

Secure Integrated
Circuits (ICs) for
Authentication,
Identification,
Transactions,
Communication
r Required functionalities:
Key generation and
device fingerprinting

Question 2

Achieving Randomness in Real World

- Physical phenomena examples:

Answer 2

• Clock drift (jitter)
• Thermal noise
• Transistor mismatches
• Photons through semi-transparent mirror

Question 3

Generating Random Numbers

Answer 3

- Linear Feedback Shift
Register (LFSR)
- True Random
Number Generator
(TRNG)
- Physically Unclonable
Function (PUF)

Question 4

Linear Feedback Shift Register (LFSR)

Answer 4

Simple way for
generating pseudorandom numbers
- Input of shift register
as a linear function of
output
- Initial State called Seed
- Feedback bits called
Taps

Question 5

LFSR Applications

Answer 5

Pseudo-random number generators (PRNGs)
for stream ciphers
- A5/1 and A5/2 in GSM
- E0 in Bluetooth
- Clock dividers and counters

Question 6

Advantages of LFSRs

Answer 6

• Easy to implement in Hardware/Software
• Produce long sequence of bits which seems random
  with well-chosen feedback function

Question 7

Disadvantages of LFSRs

Answer 7

• Deterministic

- Finite number of states

Question 8

True Random Number Generators (TRNGs)

Answer 8

Generate randomness from
physical phenomena
- Example: Sampling phase
jitter in oscillator rings to
generate sequence of
random bits
- Output of rings fed into an
XOR
- Sampling by D-flipflop driven
by the system clock

Question 9

TRNG Applications

Answer 9

Random numbers with high entropy for
- Cryptographic keys
- Initialization vectors and seeds for cryptographic
primitives and PRNGs
- Padding bits
- Nonces (number used once)

Question 10

TRNG Design Challenges

Answer 10

Non-uniform distribution
-> post-processing and correction steps needed
- Low output rate
- Biasing or non-randomness behaviour by
variations in operational conditions (e.g.,
fluctuations in temperature and supply voltage)
-> Many active attacks

Question 11

Physical(ly) Unclonable Functions (PUFs)

Answer 11

- Also known as Random
Physical Functions or
One-way Physical
Functions
- Utilizing manufacturing
process variations on
different chips to make
them unique
- Fingerprint of the IC

Question 12

PUF Definition

Answer 12

-Physical entity that is embodied in a physical
structure
- Easy to evaluate but hard to predict
- Easy to make but practically impossible to
duplicate

• Inputs are called Challenges
• Outputs are called Responses
• Together: Challenge-Response-Pairs (CRPs)
• Not a true function in a mathematical sense: one
  possible input -> more possible outputs

Question 13

Non-electrical PUFs (1)

Answer 13

• Non-electronic constructions with PUF-like
  properties
• Electronic and digital techniques are used to
  process the PUF responses
• Examples: Optical PUF, Magnetic PUFs, etc.

Question 14

Analog Electronic PUFs

Answer 14

• PUF constructions whose basic operation consists
  of an analog measurement of an electric or
  electronic quantity -> analog responses
• Examples: Coating PUFs, LC PUFs, etc.

Question 15

Digital Intrinsic PUFs

Answer 15

• PUF and measurement system fully integrated in
  the embedding device
• PUF constructible by available manufacturing
  process of embedding device
• Two classes:
  1. Delay-Based Intrinsic PUFs: Arbiter PUFs, Ring
  Oscillator PUFs, etc.
  2. Memory-based Intrinsic PUFs: SRAM PUFs,
  Butterfly PUFs, Bistable Ring PUFs, etc.

Question 16

Arbiter PUF

Answer 16

- Utilizing intrinsic timing
differences of 2 symmetrically
designed electrical paths
- Direct or crossed paths in
each stage based on
challenge bit
- Binary response by the
Arbiter based on arrival of
first signal
- Assumption: Attacker
cannot measure individual
delays!

Question 17

Ring Oscillator (RO) PUF

Answer 17

- Ring oscillators generate a
clock like signal
- The frequency is partially
random
- Two ROs are selected and
their frequencies are
compared to generate a
binary response
- Assumption: Attacker
cannot measure the ring
frequencies!

Question 18

SRAM & Butterfly PUF

Answer 18

Example of Memory-based
PUFs: SRAM PUFs
- Using the bistability
behaviour of SRAM cells
- Bistability because of
MOSFET mismatches
- Assumption: Attacker
cannot readout the
SRAM values

Question 19

Bistable Ring

Answer 19

Using bistability of inverter chains (similar to a larger SRAM
cell)

Question 20

Bistable Ring (BR) PUF

Answer 20

Combining 2n inverters in a loop to have an
exponential challenge space
- Assumption: The exact mathematical model is
was long time not known -> now I know it!

Question 21

Twisted Bistable Ring (TBR) PUF

Answer 21

• For an applied challenge all 2n inverters are
  involved.
• Assumption: The exact mathematical model is
  not known!

Question 22

Authentication using PUFs

Answer 22

PUF is used in two phases:
1. Enrollment: A number of CRPs are collected and stored
in the database (CRP database)
2. Verification: A challenge from CRP database is applied
to the PUF and the response compared with the
corresponded response in data base
Observed response close enough -> verified!

Question 23

Inter- and Intra-distance measures

Answer 23

For a particular challenge:
m Intra-distance(μintra, σintra): Hamming distance
between two responses resulting from one challenge on
one PUF instantiation
m Inter-distance(μinter, σinter): Hamming distance
between two responses resulting from one challenge on
two different PUF instantiations
m μintra expresses the average noise on the responses
• best case: μintra = 0%
m μinter expresses the uniqueness on the responses
• best case: μinter = 50%

Question 24

Key Generation using PUFs

Answer 24

Key Storing (No key is stored actually!)
- Key is generated when needed -> traditional semi- and
fully-invasive attacks cannot recover the key!

Question 25

Environmental Effects

Answer 25

Unwanted physical side effects can interfere the
measurement of responses:
1. Random Effects: Random noise and measurement
uncertainties
2. Systematic Effects: temperature, supply voltage,
etc.
- Countermeasure:
-Error Correction Codes

Question 26

PUF properties

Answer 26

• Evaluable: given Π and x, it is easy to evaluate y =
  Π(x).
• Unique: Π(x) contains some information about the
  identity of the physical entity embedding Π.
• Reproducible: y = Π(x) is reproducible up to a small
  error.
• Unclonable: given Π, it is hard to construct Γ≠ Π
  such that for all x in X: Γ(x) ≈ Π(x) up to a small
  error
• Unpredictable: given only a set Q = {(xi,yi = Π(xi))},
  it is hard to predict yc ≈ Π(xc) up to small error, for
  xc a random challenge such that (xc,∙) ∉ Q.
• One-way: given only y and Π, it is hard to find x
  such that y = Π(x).
• Tamper evident: altering the physical Π transforms
  Π→Π´ such that with high probability ∃x ∊ X: Π(x)
  ≠ Π´ (x).