liu18novel

→ read warnings

Abstract

Most of the current security key generation schemes for static random access memory physical unclonable function (SRAM PUF) are based on a fuzzy extractor. However, it is difficult to deploy the fuzzy extractor in resource-constrained systems since the implementation of error correcting codes is complicated and requires huge processing resources. To this end, we propose a novel security key generation method for SRAM PUF based on a Fourier analysis. The SRAM PUF Boolean function is introduced to describe the power-up behavior of an SRAM device, which is followed by its Fourier spectrums. By exploring spectrums of the SRAM device, it is observed that the sign-bits of Fourier coefficients at certain generalized frequency points are randomly distributed and noise resistant. As such, the generalized frequency points as well as the sign-bits are suggested for security key generation in conjunction with a sign-bit encoding algorithm. The proposed method is well compared with the conventional fuzzy extractor. It is highlighted that error correcting code will not be involved in the whole lifecycle. Consequently, the method is suitable for the resource-constrained system applications. The proposed method is performed through couple of real measurements on two different platforms. The experimental results show that 8-kB SRAM cells have sufficient entropy for 128-bit security key generation.

Introduction

• Since SRAM PUF response is inherently noisy and non-uniform distributed, it is typically combined with fuzzy extractor [5] for security key derivation processing.

• The deployment limitation of fuzzy extractor in resource-constrained system is that:

  • the error decoding algorithms are typically complicated and a large number of processing resources and long execution times are required.

  • Entropy loss introduced by the public helper data is another major issue in fuzzy extractor schemes.

• In this work, we propose a novel method for SRAM PUF security key generation based on Fourier analysis.

• A new Boolean function is defined to investigate intrinsic properties of SRAM PUF. As a result, the error correcting code is no longer needed in the whole processing phases.

Related work

(thorough related work (relevant))

The fuzzy extractor mainly consists of error correcting code and privacy amplification, aimed at extracting a nearly uniform distributed security key from noisy and non-uniform distributed SRAM PUF response.

• From the error correcting code aspect, new architectures for the decoders of Reed-Muller and Golay codes were introduced to eliminate the noise in SRAM PUF response.

• In terms of the privacy amplification, a LFSR (Linear Feedback Shifting Register) -based Toeplitz matrix was employed which was multiplied by the reconstructed SRAM PUF response.

• n [15] reverse fuzzy extractor was proposed: The reverse fuzzy extractor moved computationally intensive Rep algorithm to reader side of the RFIDs system which was more powerful.

Proposed Security Key generation Method

A brief review to Fourier Analysis

Open

Open

The Fourier Spectrum of SRAM PUF

Each address can be represented as an n bits string ranged from 0 to 2ⁿ − 1. The response can be denoted by one bit, whose value is either ‘0’ or ‘1’.

→ Therefore, the SRAM PUF Boolean function can be defined as a mapping from the address of each cell to its startup value.

The investigation of characteristic of SRAM PUF spectrum via (5) is not straightforward, with two reasons:

1. firstly, the Fourier coefficient is a function of the bit string V. Since V is an n-dimensional bit vector, it is difficult to present the mapping via two-dimensional graph effectively.

2. Secondly, all the Fourier coefficients are real numbers. It would consume large amount of hardware resources during storing and calculation for real numbers

According to (11), the Fourier coefficient at zero generalized frequency point equals to the total number of cells whose power-up state is logic ‘1’.

The Fourier spectrums of the same SRAM device are varying due to the inherently noisy characteristics of SRAM PUF responses. The neutral-skewed cells in SRAM PUF responses are noise sensitive. Their power-up state may flip from ‘0’ to ‘1’ or from ‘1’ to ‘0’.

… it can be concluded that probabilities of two flipping patterns occurred at each neutral-
skewed cell are equal, which is irrelevant to the power-up preference of the cell.

… the probabilities of Fourier coefficient increased by one and decreased by one are both 50%, which is irrelevant to the probability of the output X_m(i), which is either ‘+1’ or ‘−1’.

→ To sum up, the fluctuation of Fourier coefficient introduced by a single neutral-skewed cell can be served as a discrete random variable that takes values on ‘+1’ and ‘−1’ with equal probability. The total fluctuation introduced by all neutral-skewed cells is the sum of individual fluctuation random variables with the assumption that memory cells are independent which is a common assumption on memory-based PUFs [3]

THE UNDERLYING NOISE RESISTANCE CAPABILITY

• The underlying noise resistance capability in Fourier spectrum is originated from the imbalance in the total number of ‘1’-skewed cells and neutral-skewed cells.

• It can be inferred that the number of ‘1’-skewed cells is more than twice the number of neutral-skewed cells.

• As a result, at some generalized frequency points their Fourier coefficients are biased at a relative high level due to the majority ‘1’-skewed cells. Compared to the bias, the fluctuation introduced by all neutral-skewed cells might be so limited that the sign-bits of
  those Fourier coefficients remain the same. Namely, the sign-bits of Fourier coefficients at certain generalized frequency points can be regarded as noise-immune.

• Those generalized frequency points are called noise resistance generalized frequency points (NRGFPs).

The noise resistance capability can be obtained by investigating the practical bias as well as the practical fluctuation via mass experimental measurements with higher accuracy.

THE CONCEPT OF SIGN-BIT ENCODING ALGORITHM

The most robust NRGFP are selected by mass measurements.

The sign-bits originated from several spectrums are converted to a binary string as follow:
A positive sign-bit is encoded to ‘1’ while a negative sign-bit is encoded to ‘0’.

THE IMPLEMENTATION OF PROPOSED METHOD

Experiment

EXPERIMENTAL SETUP

All the tested chips are repeatedly powering-up for 50 times. The Fourier coefficients at all optimized NRGFPs are recorded. The experimental data shows that the absolute value of Fourier coefficients at all optimized NRGFPs are greater or equal than the 6.

THE RANDOMNESS OF THE SIGN-BITS

According to the min-entropy rate, at least 610 sign-bits are needed to obtain 128 random and uniformly key. The lower bound of the total overhead of SRAM cells is about 4876 Bytes. Thus, 8KB SRAM cells is a conservative estimation.