herder14physical

Abstract

This paper describes the use of physical unclonable functions (PUFs) in low-cost authentication and key generation applications. First, it motivates the use of PUFs versus conventional secure nonvolatile memories and defines the two primary PUF types: “strong PUFs” and “weak PUFs”. It describes strong PUF implementations and their use for low-cost authentication. After this description, the paper covers both attacks and protocols to address errors. Next, the paper covers weak PUF implementations and their use in key generation applications. It covers error-correction schemes such as pattern matching and index-based coding. Finally, this paper reviews several emerging concepts in PUF technologies such as public model PUFs and new PUF implementation technologies.

Introduction

• Instead of storing secrets in digital memory, PUFs derive a secret from the physical characteristics of the integrated circuit (IC).

• This paper will discuss a PUF that uses the innate manufacturing variability of gate delay as a physical characteristic from which one can derive a secret.

• This approach is advantageous over standard secure digital storage for several reasons:

  • PUF hardware uses simple digital circuits that are easy to fabricate and consume less power and area than EEPROM/RAM solutions with antitamper circuitry.

  • Simple PUF applications do not require expensive cryptographic hardware such as the secure hash algorithm (SHA) or a public/private key encryption algorithm.

  • Any physical attack attempting to extract digital information from the chip, therefore, must do so while the chip is powered on.

  • Invasive attacks are more difficult to execute without modifying the physical characteristics from
    which the secret is derived.

  • Nonvolatile memory is more expensive to manufacture.

• In addition to gate delay, architectures also use the power-on state of SRAM, threshold voltages, and many other physical characteristics to derive the secret.

• This paper defines protocols to address two primary applications:

  • strong authentication

  • cryptographic key generation

Types of PUFs

• Each PUF can be modeled as a black-box challenge-response system. In other words, a PUF is passed an input challenge c, and returns a response r=f(c), where f(.) describes the input/output relations of the PUF. The blackbox model is appropriate here, because the internal parameters of f(.) are hidden from the user since they represent the internal manufacturing variability that the PUF uses to generate a unique challenge–response set.

Open

• PUF security relies on the difficulty of measurement or estimation of these parameters as well as the difficulty of manufacturing two chips with the same set of parameters.

• The fundamental difference between weak and strong PUFs is the domain of f(.), or informally, the number of unique challenges c that the PUF can process.

Weak PUF Model

• Weak PUFs have a small number of CRPs (linearly related to the number of components whose behavior depends on manufacturing variation)

• An example weak PUF is the power-on state of an SRAM.

  • manufacturing variability will give each SRAM cell a random tendency toward a logical ‘‘1’’ or ‘‘0’’ at power-on.

  • In this case, if the ‘‘response’’ consists of the entire SRAM state at power-on, the notion of a ‘‘challenge’’ is not useful, as there is only one possible ‘‘challenge’’: powering on the SRAM.

• since weak PUFs in general have only a small number of CRPs, these pairs must be kept secret

• weak PUFs are well suited for use in key derivation processes, for example:

  • key in a keyed-hash message authentication code (HMAC) challenge–response sequence

  • secret key to encrypt/decrypt data on the device

Strong PUF Model

• Strong PUFs have large enough challenge–response space such that an adversary cannot enumerate all CRPs within a certain fixed time (ideally, exponential in the number of challenge bits)

• a strong PUF can be authenticated directly without using any cryptographic hardware

• a weak PUF can provide authentication capabilities if the weak PUF is paired with crypto hardware supporting HMAC or similar authentication processes

• the security models for weak and strong PUFs differ:

  • the output of a weak PUF must be kept private, while a strong PUF’s responses do not have the same restriction.

  • to prevent total enumeration of the strong PUF, one must also consider the readout time of the PUF in conjunction with the number of CRPs.

    • Since a weak PUF provides a secret key, the surrounding digital cryptographic hardware is responsible for limiting access to the weak PUF output.

    • However, the strong PUF does not require the use of additional crypto hardware to provide authentication services, and therefore must itself prevent unauthorized access into its own internal structure.

Error Correction

• Both weak and strong PUFs rely on analog physical properties of the fabricated circuit to derive secret information. Naturally, these analog properties have noise and variability associated with them.

• The first mechanism to mitigate such effects is to use differential design techniques to cancel out first-order environmental dependencies.

• Consider the PUF using gate delay.

  • This delay depends on temperature, supply voltage, and other environmental parameters.

  • typical PUFs using this effect will not measure a single gate’s delay, but rather the difference between two identically designed, but distinct gates on a die. In this way, any environmental factor should affect each gate equally.

• modern PUF designs employ multiple error-correction techniques, improving reliability. However, many of these error-correcting techniques have been shown to leak bits of the secret key.

• In addition to standard error-correction techniques, PUFs also use soft-decision coding. This coding technique takes advantage of the reliability information of a given response bit to improve error-correction performance.

  • This reliability information can be obtained from repeated PUF response readings in the case of SRAM PUFs,

  • or the magnitude of frequency difference values in the case of ring-oscillator PUFs.

Example Strong PUF Architectures

Optical PUF

Open

Arbiter PUF

Low-Cost Authentication: Strong PUFs

Because the strong PUF does not require secure nonvolatile memory, antitamper circuitry, or additional supporting crypto acceleration hardware, a PUF-based solution requires less area, power, and mask layers than a traditional approach to secure authentication.

Authentication Protocol

The requirements of a strong PUF state that an adversary provided with polynomial CRPs should not be able to predict the response to a new challenge.
The protocol for using PUFs is significantly different than most public/private key cryptographic systems. Consider a server authenticating a client.

1. PUF is manufactured.

2. Server obtains access to PUF and generates a table of CRPs. These pairs are stored in internal secret storage.

3. PUF is given to the client.

4. The client submits a request to the server to authenticate.

5. Server picks a known CRP and submits the challenge to the client.

6. The client runs the challenge on the PUF, returns the response to the server.

7. Server checks to see that the response is correct and marks the CRP as used.

Because the server cannot predict the PUF behavior, it must internally store CRPs to be used later.

Each CRP must be used only once. Therefore, the server must either store enough CRPs so that it will not run out, or it must periodically ‘‘recharge’’ the table by establishing secure communication with an authenticated client and requesting responses to new challenges.

To address the CRP table scalability problem, newer protocols based on storage of a compact model for PUF have emerged. A brief discussion of these protocols is included later.

The security of a strong PUF depends on several factors (if any one of these factors is compromised, the security of the PUF itself is also compromised):

• difficulty of measurement of PUF internal parameters (only CRPs can be measured);

• difficulty of manufacturing ‘‘clones’’;

• difficulty of predicting PUF behavior based on past CRPs.

Example Weak PUF Architectures

Ring-Oscillator PUF

• In addition to arbiter PUFs, the manufacturing variability intrinsic to circuit gate delay can also be used to instantiate a ‘‘ring-oscillator PUF’’. This PUF architecture contains N identically designed ring oscillators.
  Due to the variation in delay of the inverters in the ring oscillator, each will have a slightly different frequency.

• The frequencies of two oscillators are measured and compared to reveal one of the PUF output bits. If there are N oscillators, there are N(N-1)/2 possible pairings. However, the number of output bits is limited due to correlations (if ring oscillator A is faster than B, and B is faster than C, then clearly A is faster than C). For N oscillators, there is a specific ordering of fastest to slowest. If the oscillators are truly identical and manufacturing variation dominates, then each of these N! orderings is equally likely. Therefore, there are a maximum of log(N!) bits that can be extracted from the PUF.

• Once fabricated, the ring oscillators’ frequency is set, so the output bits of the PUF will always remain constant. → ring-oscillator PUF is a weak PUF

• Because the ring-oscillator PUF measures differences in gate delay like the arbiter PUF, the ring-oscillator PUF is susceptible to the same set of environmental variations and noise sources. Therefore, error correction will be equally important in this application.

• One approach that can be taken immediately to mitigate potential errors is to recognize that oscillators that are ‘‘close’’ in frequency have much greater likelihood of causing an output error than oscillators that are ‘‘far apart’’ in frequency.

→ Therefore, at the time of provisioning, one can select only pairs of oscillators whose frequencies are sufficiently far apart to define the PUF output bits. This increases the PUFs robustness toward noise and environmental variations.

SRAM PUF

Both the arbiter PUF and the ring-oscillator PUF ultimately depend on variations in the propagation delay of
gates. However, this is not the only physical property on which a PUF can be built. A popular weak PUF structure exploits the positive feedback loop in a SRAM or SRAM-like structure shown below:

• Natural thermal and shot noise trigger the positive feedback loop, and the cell relaxes into either the ‘‘1’’ or ‘‘0’’ state depending on this process variation.

• Note that since the final state depends on the difference between two feedback loops, the measurement is differential. Therefore, common mode noise such as die temperature, power supply fluctuations, and common mode process variations should not strongly impact the transition.

• Like the ring-oscillator PUF, the architecture of the SRAM PUF can be used to make intelligent decisions regarding error coding. The key recognition is that the relative strengths of the two feedback loops in a SRAM cell are relatively static. A cell strongly biased toward ‘‘1’’ or ‘‘0’’ will remain strongly biased toward ‘‘1’’ or ‘‘0,’’ respectively.

→ Therefore, by using repeated measurements, one can assess the stability of a SRAM PUF output bit and selectively use the most stable bits as the PUF output. This process is used in conjunction with traditional coding techniques to mitigate the noise inherent to SRAM PUFs.

Cryptographic Key Generation: Weak PUFs

Once the key is derived from the weak PUF, it is stored in secure volatile memory during the device’s operation. This key can then be used for authentication, encryption, and other cryptographic protocols.

Key Generation Protocol

Because weak PUFs like the ones discussed above have effectively fixed ‘‘challenge bits,’’ the key generation protocol is fairly simple:

• In the case of the SRAM PUF, one simply powers on the SRAM and observes the memory state.

• Similarly for the ring-oscillator PUF, one simply pairwise compares each of the oscillators in order to measure the correct ordering of oscillation frequency.

In both of these cases, the complexity lies in the limitations of physical implementations that result in both statistical and systematic noise that must be corrected/mitigated.

A key challenge in adapting strong PUFs to key generation is in correcting errors in PUF response bits. To this end, ‘‘pattern matching’’ technique can be used.

SRAM PUF Implementation

• In a study, a custom SRAM cell was constructed to minimize potential systematic mismatch between the two transistors.

  • A challenge arose with the recognition that roughly 4% of the SRAM cells did not have enough mismatch to strongly favor ‘‘1’’ or ‘‘0.’’ These cells probabilistically settled into ‘‘1’’ or ‘‘0’’ at random due to the contributions of thermal and shot noise.

  • The number of these unstable bits increased at temperature/voltage corners and as the chip aged.

• An end user can use an existing off-the-shelf component with no silicon modification and, using software alone, implement a weak PUF for cryptographic or identification purposes.

• A soft-decision helper algorithm should be implemented for SRAM PUF error correction. The proposed implementation takes 1536 SRAM PUF response bits and distills these data down to a 128-bit full-entropy key with a failure rate of ≤ 10^-6.

• Many attacks can be performed on SRAM PUFs depending on the level of access that one has to the SRAM, among them:

  • If one can insert a ‘‘write’’ command, then one could leverage the negative bias temperature instability (NBTI) to deliberately force individual bits toward ‘‘1.’’

  • If one could modify the temperature, one could potentially cause the PUF to fail by running the PUF outside its design area.

  • An attacker with access to the power channel could potentially control the stability of some of the SRAM PUF bits

Ring-Oscillator PUF Implementation

• Yu and Devadas designed a delay-based weak PUF based on the ring-oscillator architecture, and proposed the first PUF key generation architecture that does not require traditional error correction, using “index-based syndrome” (IBS) coding method.

• In this architecture, several oscillator PUF banks are instantiated, with each oscillator bank comprising 2k ring oscillators.

• Like the SRAM PUF, the ring-oscillator PUF also must correct for noise and environmental factors.

• The ring-oscillator PUF is inherently a differential measurement (measuring the difference in two identical sets of oscillators’ paths). However, it is still susceptible to noise. → the difference is identical because the oscillators are identical, this is not the case for the different oscillators on SCuM

• In contrast with block codes, IBS, even when used with a second stage traditional (hard-decision) error correction, remains information theoretically secure under a PUF i.i.d. assumption, even for a heavily biased PUF.

• Like the SRAM PUF, the ring-oscillator PUF relies on downstream cryptographic hardware/software to protect the security of the key that is generated.

• Many attacks on Ring-Oscillator PUFs can be performed.

Emerging PUF Concepts

New PUF architectures and applications are continually being developed:

1. Model-based PUFs

   1. The server stores a “secret model”, that emulates the PUF challenge-response behavior, instead of storing a large number of CRPs

   2. Such a ‘‘secret model’’ PUF still requires both the ‘‘secure bootstrapping’’ phase as well as the secure storage, as the PUF and authenticating server must ‘‘agree’’ on a secret PUF model.

2. Timed Authentication and Public Models (referred as PPUF)

   1. The PPUF model is public, and there is no secret information anywhere in the protocol (neither on the device nor the server).

   2. The authentication capability derives solely from the computational difference between the hardware and the model, and the unclonability of the hardware (PPUF model storage must be resistant against tampering or rewriting).

New Terms

• CRP: challenge-response pair

To Read About