Last quarter I took my first grad class at UCSB called CS 290T "Computational Algebra." It was a very eclectic class where different speakers would come to lecture us on some aspect of their research. Needless to say, there were many interesting topics brought forth that ranged from Boolean Functions (on which I wrote a paper and will post later), distributed security, error-tolerant functions, the LLL Algorithm, etc. Among all of those, there was one that intrigued me quite a lot: Physical Unclonable Functions. What got me is that the concept is easy to understand and the implementation can be done with virtually anything you want. So without further ado, let's take a plunge into the fascinating world of PUFs.

1. Definition

A Physical Unclonable Function (PUF) is a hardware-implemented function in which the mapping between a challenge and its response is dependent on the hardware variations (e.g. materials, electrical parameters, design, etc.).

For example, your PUF could rely on the time (in milliseconds) it takes for electricity to go through a wire. Although the wire is cut similarly in all computers, the small fluctuations in length might be enough for two computers to get different results. Now the trick is to choose a physical property that would vary greatly from machine to machine, but within the same computer the result doesn't change too much.

2. Key Principles

  • \( \text{PUF}_i \) should be unique to each device \( i \).
  • Each \( (x_i, y_i) \) pair should be independent and not linkable.
Diagram of a PUF challenge-response: a challenge x fed into a device produces a hardware-dependent response y.
PUF Challenge

3. Usages

  • Device Authentication
  • Tamper Protection (e.g. anti-counterfeit, intellectual-property protection, etc.)
  • Cryptography (e.g. key generation)

4. Types of PUF

You can get pretty creative with what you want to use as a basis for your PUF. (I've seen some cool ideas such as camera CCDs or magstripes.) However, the most typical types of PUF are:

  • SRAM PUF
    • These use the SRAM memory on board.
  • Delay PUF
    • These use the variation in delays of wires and gates on silicon wafers.
    • Some of these implementations are: Ring Oscillator, Arbiter, Multiplexor-based.
  • Butterfly PUF
    • These are similar to the SRAM PUF but can be implemented on SRAM FPGAs because they are built by cross-coupling two latches or flip-flops.
  • Optical PUFs, Metal Resistance PUFs, and so many more…
Illustrations of several PUF types: SRAM, delay (arbiter / ring oscillator), and butterfly PUFs.
Some PUF examples

5. Properties of a PUF

  • Steadiness: a PUF that always generates the same response even when varying operating conditions (e.g. supply voltage and temperature) is said to be steady. [1]
  • Randomness: the measure of bias among all challenges on all PUF instances. [2]
  • Diffuseness: the degree of difference (Hamming distance) among different responses to different challenges for the same PUF. (The expected diffuseness is 50%.) [3]
  • Uniqueness: reliability measures the consistency with which a given PUF reproduces a response to repeated application of a given challenge. [3]

6. PUF Mathematical Notation

  • Creation of a PUF instance: $$P \equiv \{\, \text{puf}_{i} \leftarrow P.\text{Create}(r_{i}^{C}) : \forall\, i,\ r_{i}^{C} \xleftarrow{\$} \{0,1\}^{*} \,\}$$
  • Evaluation of a PUF instance: $$y_{i}^{(j)}(x) \leftarrow \text{puf}_{i}(x).\text{Eval}\big(r_{j}^{E} \xleftarrow{\$} \{0,1\}^{*}\big)$$
  • \( r^{C} \) and \( r^{E} \) represent randomized fair coin tosses.

7. Measuring PUFs

There are two basic measurements that we will use to calculate the properties of a PUF.

  • Intra-Distance refers to the distance between two responses from the same PUF instance using the same challenge. $$D_{\text{puf}_{i}}^{\,intra}(x) \triangleq_{\delta} \text{dist}\big[\,Y_{i}(x)\,;\,Y_{i}'(x)\,\big]$$
    • \( Y_{i}(x) \) and \( Y_{i}'(x) \) refer to distinct random evaluations of the same \( \text{puf}_{i} \), and \( \text{dist}[\cdot;\cdot] \) denotes the Hamming distance between two random variables.
    • Intra-distance will give us an idea of how reproducible or reliable a given PUF is. Remember that we want to find a PUF that is consistent within the same device.
  • Inter-Distance refers to the distance between two responses from different PUF instances using the same challenge. $$D_{\text{puf}_{i}}^{\,inter}(x) \triangleq_{\delta} \text{dist}\big[\,Y(x)\,;\,W(x)\,\big]$$
    • \( Y(x) \) and \( W(x) \) refer to distinct random evaluations of the two PUFs.
    • Inter-distance will give us an idea of how distinct this PUF will be across multiple devices. Remember that we want this function to be as different as possible across multiple devices.
  • For more in-depth calculations, check out this link.
Table of quantitative PUF tests (steadiness, randomness, diffuseness, uniqueness) modeled from intra- and inter-distance measurements.
Quantitative tests used to model a PUF, by Hori et al., Quantitative and Statistical Performance Evaluation of Arbiter Physical Unclonable Functions on FPGAs. ReConFig 2010, pp. 298–303, 2010.

Sources and Further Reading