I finished reading completely:

Chapter 3: The Basic Applications

There exist three basic applications of physical unclonable functions:

1. identification

2. authentication

3. key generation

Identification

The basic requirement for identification is that for each entity a unique ID is assigned. Thus, the identification process has to be an injective function.

Identification does not include identity verification. It is not assured that the claimed ID is the correct one. If the identity is verified, it is called authentication.

PUFs can reduce costs by reducing fabrication complexity and by providing the ID from the intrinsic properties of the chip.

Since the output of PUFs is noisy, typically the identification system has to be error tolerant. Depending on the tolerance of the system, error correction codes can even be omitted. The measure of the tolerance for binary output data is called Hamming distance.

To increase the probability of correct ID assignment the number of output bits can be raised.

Chapter 4: Testing and Specification of PUFs

Theory Basics

Hamming Distance

In the case of uniformly distributed bits the mean Hamming distance of two binary strings is 50 %. The Hamming distance of such strings is distributed binomially.

Chapter 5: Error Correction Codes

Normally, error correction is used to correct errors that occur during transmission and storage of data over a transmission channel. Additional data are added as redundant information which allows to correct a certain amount of errors [7]. In the case of PUFs the errors do not occur during transmission but during data generation. Nevertheless, the problem is equivalent.

A binary symmetric channel is a very simple model in the information theory that is applied to characterize the errors in a channel. In a BSC the probability of a “1” to turn into a “0” and the probability of a “0” to turn into a “1” are identical. Since PUFs show this behavior, it makes sense to utilize the BSC approach.

Error Correction Codes

These helper data have to be stored on an NVM and have to be assumed to be public.

When choosing an ECC, the following points should be considered:
• Redundancy R: low redundancy is followed by a low number of required bits. A lower number of bits is followed by a smaller area consumption.
• Complexity of calculation: complex calculations require time, power, and appropriate hardware.
• Error reduction: for cryptographic purposes no errors are tolerable. So, an appropriate ECC depends on the error probability of the raw output of the PUF cells and the required error probability after error correction.

The advantage of external ECC encoding is that the hardware has not to be implemented on the chip. The big disadvantage is that confidential information has to leave the chip during the initialization. Thus, initialization has to be done within a secure environment. Usually, the decoding process is much more complex than the encoding process [7]. Therefore, it would not be very costly to place the encoder on the chip as well. Even the same hardware may be used for both, encryption and decryption.

Error Correction Techniques

Approach: Reducing Errors Using More Than One PUF Cell → IMPORTANT!!!

Example: three cells are used to produce one bit of output. The output is determined by a majority decision: If there are more ones than zeros (011, 101, 110, 111) in the bit string, a “1” appears at the output. Otherwise, if there are more zeros than ones (000, 001, 010, 100), a “0” is generated. There are two bit strings (000, 111) where two bits have to change in order to change the output value. Furthermore, there are six bit strings in which one bit has to change in order to change the majority decision.

Open

Error Correction Codes

In the case of PUFs this “channel” consists mainly of the environment in which the PUF-cell produces its output.

In the case of PUF error correction it is crucial to know that the channel does not just produce random (noise) but also deterministic errors (temperature, supply voltage). These deterministic errors turn out to be even worse than noise which can be reduced by averaging techniques.

Error control can be divided into automatic repeat requests (ARQ) and forward error correction (FEC) [7]. Since PUF errors may be both, deterministic and random, a simple repetition of request will lead to the same wrong output and thus ARQ schemes are not feasible. FEC algorithms have to be selected for PUF error correction. Thus, redundancy is added to the data—also called parity or helper data—to be able to correct errors. This is carried out by choosing the most likely signal from a set of allowed signals in dependence of the incoming data. FEC knows two classes of error correction codes: the convolutional codes and the block
codes.

Block codes use fixed-size blocks and can be decoded in polynomial time to their block length in practice. There are different block codes that are used:

• eed–Salomon codes → not a good choice for PUF

• BCH codes → preferred block code for PUF error correction.

• In the upcoming sections the Hamming Code, the repetition Code, and the
  BCH Code are explained in more detail.

The second group of FECs are the convolutional codes [7, 10]. Unlike the block codes which usually use hard decisions for their input and output (one or zeros), the convolutional codes are commonly based on soft decisions (analog inputs) which increase their performance. Most of the codes use the Viterbi algorithm for decoding which allows an asymptotical optimal decoding with an exponential increasing complexity.

Convolutional codes and their iteratively working derivatives like the turbo-convolutional-codes could be good approaches for PUF error correction since the implementation effort is comparably small. The biggest problem is to find an appropriate code. Unfortunately, this cannot be conducted deterministically

In Chap. 15.2 the repetition code is used to correct errors in the Microcontroller PUF.

Open

All complex EECs become difficult to handle as soon as the amount of energy is highly limited as it is for example on RFID tags. In such cases other solutions are required. For this reason the repetition code, a combination of repetition and Hamming code, and a combination of repetition and BCH code is analyzed. For their implementation simplicity and correction capabilities, such codes are an alternative to highly complex codes.

k is the number of bits in the original signal and l is the number of bits of the encoded block

Chapter 15: Using the SRAM of a Microcontroller as a PUF

Unfortunately, NVMs can be read out easily by adversaries especially if the memory is placed outside the
microcontroller. Thus, if there is not be taken extra care, microcontroller system software can be copied easily and the whole system can be cloned.

One way to prevent cloning is to encrypt the software data before storing, instead of storing the plain text inside NVMs. The code is transferred to the system and decrypted on the microcontroller during a start up phase. Thus, the plain text of the code never leaves the microcontroller. The described approach is shown:

As in the data encryption case, the key that is needed to encrypt the plain text must not be accessible from the outside. There are ways to store key material directly on the microcontroller in nonvolatile SRAMs [3]. Special hardware and a battery are required to allow for such a system.

Even on-chip flash memory can be used to store the key material. Nevertheless, this way of key storage cannot be considered as secure. Even if the memory cannot be accessed directly over external contacts at the microcontroller, techniques exist with which adversaries can access such data.

One approach to solve this problem is to use the SRAM that is available on the microcontroller. The SRAM can be utilized as SRAM PUF which is used to generate/store the key material.

Since SRAM PUFs show high error rates of 10% and more, not all EECs are feasible. Many ECCs get too complex to implement in some microcontrollers. In the following chapter an easy-to-implement SRAM PUF combined with a repetition code to provide a negligible error rate is suggested.

Basic Concept

The SRAM must be situated inside the microcontroller since otherwise the communication between SRAM and microcontroller could be observed easily. Furthermore, it is important to make sure that the data of the internal SRAM block are not accessible from outside.

Error Correction Using the Repetition Code

Although the error correction capability is high, the complexity of the repetition code is very low. Thus, it can be implemented in many microcontrollers easily.

It can be seen for example, that a repetition code with repetition factor of 31 reduces the initial error rate of 10% to an error rate (BER) of 6.85E−07%. The correction capabilities of the repetition factors 21 and 11 can be seen in the BER after correction: 1.35E−04% and 2.96E−02% respectively.

Measurement Results

Here, 16 kB were assumed to be sufficient to provide enough bits for data and repetition code.

The following parameters are determined: mean value, error rate, the temperature behavior(error rate at different temperature corners), correlation between bits, correlation between chips and memory effect. The analysis results are presented in the following sections.

Mean Value

In the case of the microcontroller PUF the mean value of Block A was 0.5205, and the mean value of block B was 0.5559.

The pdf of a binomial distribution can be determined by using the following equation:

where k is the number of ones (0 to n). n is the total number of bits (n = 16384) and p = q = 0.5 is the probability that a one/zero occurs. k is normalized by 1/n .

Error Rate

The difference between the intra-chip Hamming distance HD_intra of the two blocks indicates a different structure of the two blocks.

At block A the intra-chip HD is HDintraA = 8%. At block B the intra-chip HD is HDintraB = 18%.

Correlation Between Bits

In order to check whether correlation exists in the test chip, the autocorrelation function R xx is used:

Block A does not show any correlation between its bits. In contrast, block B has some strong correlation at gaps of 256 bits and even stronger correlation at gaps of 2048 bits which again shows (like in the case of the error rate) that the two blocks must be built up differently.

Memory Effect

Correlation Between the Chips

Since the six available inter-chip HDs are close to 50% and the ideal result would be around 50%, the SRAM PUF seems to work well with respect to the correlation between the chips.

Summary

Error Correction Code

In this case the repetition factor was chosen to be 31. A 2048 bit key was generated using block A. The correction bits were then generated and written to the flash of the microcontroller using in-application programming (IAP) commands. The whole implementation of PUF and error correction required 308 byte of program memory for the initial phase and 184 byte for the key generation phase, both in the program memory. To be able to store the correction data, 7.75 kbit were used for the 2048 bit key (Rep31).

To test the implementation the key generation was repeated 1,000 times at different temperatures in the range between 0 ◦C and 80 ◦C. No errors were produced by the PUF in all of the measurement runs after error correction. This is the expected result, since the theoretical error rate of a PUF with 8% BER of a single bit, 2048 bit key, and a repetition factor of 31 can be determined to be 6.85E−07%.

→ check the article https://ieeexplore.ieee.org/abstract/document/6060013/ for more details about this experiment.

Summary

The analysis showed that before implementing a PUF on an internal SRAM the SRAM has to be checked carefully toward its feasibility as a PUF: both, the inter-chip and the intra-chip Hamming distance have to be within a predefined range. Furthermore, the memory effect of cells should be checked, especially if the cells are also used during regular usage of the SRAM.