# Single-Round Pattern Matching Key Generation Using Physically Unclonable Function

Authors: Yuichi Komano; Kazuo Ohta; Kazuo Sakiyama; Mitsugu Iwamoto; Ingrid Verbauwhede
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Paral and Devadas introduced a simple key generation scheme with a physically unclonable function (PUF) that requires no error correction, e.g., by using a fuzzy extractor. Their scheme, called a pattern matching key generation (PMKG) scheme, is based on pattern matching between auxiliary data, assigned at the enrollment in advance, and a substring of PUF output, to reconstruct a key. The PMKG scheme repeats a round operation, including the pattern matching, to derive a key with high entropy. Later, to enhance the efficiency and security, a circular PMKG (C-PMKG) scheme was proposed. However, multiple round operations in these schemes make them impractical. In this paper, we propose a single-round circular PMKG (SC-PMKG) scheme. Unlike the previous schemes, our scheme invokes the PUF only once. Hence, there is no fear of information leakage by invoking the PUF with the (partially) same input multiple times in different rounds, and, therefore, the security consideration can be simplified. Moreover, we introduce another hash function to generate a check string which ensures the correctness of the key reconstruction. The string enables us not only to defeat manipulation attacks but also to prove the security theoretically. In addition to its simple construction, the SC-PMKG scheme can use a weak PUF like the SRAM-PUF as a building block if our system is properly implemented so that the PUF is directly inaccessible from the outside, and, therefore, it is suitable for tiny devices in the IoT systems. We discuss its security and show its feasibility by simulations and experiments.


---

## Body

## 1. Introduction

The Internet of Things (IoT) is widely spread to make us more intelligent, efficient, and comfortable. In IoT systems, devices are located everywhere to exchange their sensing data and their control information. On the other hand, lots of devices in these systems are resource-constrained where it is hard to implement security functions. Unlike the closed system with a limited number of devices, in the IoT systems, attackers are able to obtain devices to analyze them maliciously, and therefore they can be weak points of these systems.Let us consider the safety of the IoT systems. First of all, the reliability of data is important because the devices work unwillingly with the improper data, especially with the data manipulated by the attacker. Moreover, the correctness of the firmware including the safety functionalities, such as the fail-stop and the fail-tolerance, is also important. In order to avoid the manipulation of the firmware by attacker so that the safe functionality does not work, the firmware should be well protected and securely updated. Both for the data reliability and for the firmware correctness, the security is essential. Hence, securing such devices is one of our emerging challenges. Particularly, the management of key is a crucial task.The physically unclonable function (PUF) is one of the promising primitives to improve the security of tiny devices. It derives a unique value for each device (function) from its fine characteristics. For example, the SRAM-PUF [1–3] uses initial states of the SRAM cells just after the power-on as such characteristics; and, the Arbiter-PUF [4–6] uses the logic delays of a dual-rail circuit as such ones. The unique value derived is used as (a source of) an identity (ID) or a cryptographic key. The PUF is suitable for a tiny device for the following two reasons. First, since these characteristics naturally arise during the manufacturing process, we can remove the process of embedding an ID or a key and decrease the manufacturing cost. Second, since analyzing the unique and fine characteristics is difficult, it can be regarded as a secure and tamper- evident storage which proves the physical manipulation for analyzing the key.On the other hand, the output of PUF may include a small noise for each invocation, e.g.,5% or up to 15% noise in the signal, because of external factors such as external/ambient temperature variations and/or supplied voltage variations. In order to use the output as a cryptographic key, the noise should be removed by error correction techniques, such as the fuzzy extractor [7, 8], because the cryptographic results completely differ if the key differs by only one bit. The fuzzy extractor, however, includes a complex error correction code whose cost might be high for the tiny devices.


### 1.1. Pattern Matching Key Generation Using PUF

Paral and Devadas [9] gave an interesting solution to remove the noises without an error correcting code. Their proposal uses a pattern matching which only estimates the Hamming distance between two strings. Their main idea is to regard the index (bit position) indicating a substring of the PUF output as a secret, instead of the (sub)string of PUF output itself. This scheme is called a pattern matching key generation (PMKG) scheme.The PMKG scheme consists of multiple rounds. In each round of its enrollment phase, a key generation device extracts a substring of PUF output indicated by a secret index and stores the substring into the public (and maybe insecure) nonvolatile memory (NVM) area, as auxiliary data. The PMKG scheme regards a (hash value of a) concatenation of the substrings as a secret key. In each round of its reconstruction phase, the device compares a noisy PUF output with the stored auxiliary data and recovers the corresponding index and eventually the key.Against the PMKG scheme, Delvaux and Verbauwhede [10, 11] gave attacks, namedsnake attacks, to recover the secret indices. Their attacks modify the auxiliary data stored in the NVM bit by bit in each round and detect the index by running the device with the modified data. To avoid the snake attacks, they also suggested regarding the PUF output as circular data. We call the scheme a circular PMKG (C-PMKG) scheme.The PMKG (C-PMKG, respectively) scheme stores, for each round, the substring (resp., circularly shifted string) of PUF output into the NVM as auxiliary data. If two auxiliary data pieces for different rounds have the same substring (intersection), it might leak information on the secret indexes for the corresponding rounds. To mitigate the leakage, there are several solutions. The first one is to control the inputs of PUF for rounds to avoid such intersection. Another one is to enlarge the input/output space so as to neglect the intersection. These solutions increase the implementation cost and may be inappropriate for tiny devices.


### 1.2. Our Contribution

In this paper, we propose a simple and efficient PMKG scheme, named a single-round circular PMKG (SC-PMKG) scheme. Unlike the previous schemes, the SC-PMKG scheme consists of a single-round operation with multiple indexes. It divides a PUF output into multiple substrings, circularly shifts each substring by each secret index, and stores the shifted data into the NVM as auxiliary data. Moreover, it also stores a hash value, as a check string to check the correctness of the key reconstruction, into the NVM.By reducing the number of rounds in the (C-)PMKG scheme to one, we need not care for the information leakage from the PUF output strings in the auxiliary data with the (partially) same input, and therefore the security discussion can be simplified. In addition, the check string not only disables the manipulation attacks but also ensures the provable security of our scheme in the random oracle model [12]. We give a security proof under the condition (assumption), for simplicity, that there is no adversarial interface to access the internal PUF. This condition also provides our choice of the PUF candidates applicable to the SC-PMKG scheme. Without such interfaces, machine learning attacks to the PUF are impractical, and, hence, various PUFs can be applicable to the SC-PMKG, including a weak PUF such as the SRAM-PUF. (The modeling attack requires challenge-response pairs (CRPs) of PUF, which is applicable to PUF applications where adversaries can obtain the PUF CRPs, such as an authentication with PUF. In the application of the key generation, adversaries can obtain the PUF outputs from auxiliary data. Against this application, the modeling attack could be meaningless for the following two reasons. First, the corresponding inputs for the auxiliary data are unknown to adversaries. Second, the number of auxiliary data is limited; for example, if the key generation device is specific to a key of certain application, adversaries can obtain PUF outputs only for the key.) Note that, on the provable security, we can relax the assumption where there are adversarial interfaces to the PUFexcept one to directly access the output corresponding to the target key, as we discuss in Section 4.3. Such discussions on the adversarial conditions and the security show that the security coengineering for the developments of the PUF devices and of the PUF application is important.Furthermore, we check its feasibility by simulations and experiments. We also check the validity with theoretical estimation. Our theoretical estimation can derive parameter candidates not only for the SC-PMKG scheme but also for the C-PMKG schemes. From our discussion, the SC-PMKG scheme is secure and efficient rather than the previous PMKG schemes; and, therefore, it is suitable for tiny devices to tackle the emerging threats against the IoT systems.


### 1.3. Organization

In Section2, we give the definitions of PUF and PUF-based key generation scheme. We then review the constructions of previous PMKG schemes and discuss their drawbacks in Section 3. In Section 4, we present the SC-PMKG scheme and discuss its security. We then test its feasibility and make comparisons among the PMKG schemes in Sections 5 and 6, respectively. Finally, Section 7 concludes this paper.


## 1.1. Pattern Matching Key Generation Using PUF

Paral and Devadas [9] gave an interesting solution to remove the noises without an error correcting code. Their proposal uses a pattern matching which only estimates the Hamming distance between two strings. Their main idea is to regard the index (bit position) indicating a substring of the PUF output as a secret, instead of the (sub)string of PUF output itself. This scheme is called a pattern matching key generation (PMKG) scheme.The PMKG scheme consists of multiple rounds. In each round of its enrollment phase, a key generation device extracts a substring of PUF output indicated by a secret index and stores the substring into the public (and maybe insecure) nonvolatile memory (NVM) area, as auxiliary data. The PMKG scheme regards a (hash value of a) concatenation of the substrings as a secret key. In each round of its reconstruction phase, the device compares a noisy PUF output with the stored auxiliary data and recovers the corresponding index and eventually the key.Against the PMKG scheme, Delvaux and Verbauwhede [10, 11] gave attacks, namedsnake attacks, to recover the secret indices. Their attacks modify the auxiliary data stored in the NVM bit by bit in each round and detect the index by running the device with the modified data. To avoid the snake attacks, they also suggested regarding the PUF output as circular data. We call the scheme a circular PMKG (C-PMKG) scheme.The PMKG (C-PMKG, respectively) scheme stores, for each round, the substring (resp., circularly shifted string) of PUF output into the NVM as auxiliary data. If two auxiliary data pieces for different rounds have the same substring (intersection), it might leak information on the secret indexes for the corresponding rounds. To mitigate the leakage, there are several solutions. The first one is to control the inputs of PUF for rounds to avoid such intersection. Another one is to enlarge the input/output space so as to neglect the intersection. These solutions increase the implementation cost and may be inappropriate for tiny devices.


## 1.2. Our Contribution

In this paper, we propose a simple and efficient PMKG scheme, named a single-round circular PMKG (SC-PMKG) scheme. Unlike the previous schemes, the SC-PMKG scheme consists of a single-round operation with multiple indexes. It divides a PUF output into multiple substrings, circularly shifts each substring by each secret index, and stores the shifted data into the NVM as auxiliary data. Moreover, it also stores a hash value, as a check string to check the correctness of the key reconstruction, into the NVM.By reducing the number of rounds in the (C-)PMKG scheme to one, we need not care for the information leakage from the PUF output strings in the auxiliary data with the (partially) same input, and therefore the security discussion can be simplified. In addition, the check string not only disables the manipulation attacks but also ensures the provable security of our scheme in the random oracle model [12]. We give a security proof under the condition (assumption), for simplicity, that there is no adversarial interface to access the internal PUF. This condition also provides our choice of the PUF candidates applicable to the SC-PMKG scheme. Without such interfaces, machine learning attacks to the PUF are impractical, and, hence, various PUFs can be applicable to the SC-PMKG, including a weak PUF such as the SRAM-PUF. (The modeling attack requires challenge-response pairs (CRPs) of PUF, which is applicable to PUF applications where adversaries can obtain the PUF CRPs, such as an authentication with PUF. In the application of the key generation, adversaries can obtain the PUF outputs from auxiliary data. Against this application, the modeling attack could be meaningless for the following two reasons. First, the corresponding inputs for the auxiliary data are unknown to adversaries. Second, the number of auxiliary data is limited; for example, if the key generation device is specific to a key of certain application, adversaries can obtain PUF outputs only for the key.) Note that, on the provable security, we can relax the assumption where there are adversarial interfaces to the PUFexcept one to directly access the output corresponding to the target key, as we discuss in Section 4.3. Such discussions on the adversarial conditions and the security show that the security coengineering for the developments of the PUF devices and of the PUF application is important.Furthermore, we check its feasibility by simulations and experiments. We also check the validity with theoretical estimation. Our theoretical estimation can derive parameter candidates not only for the SC-PMKG scheme but also for the C-PMKG schemes. From our discussion, the SC-PMKG scheme is secure and efficient rather than the previous PMKG schemes; and, therefore, it is suitable for tiny devices to tackle the emerging threats against the IoT systems.


## 1.3. Organization

In Section2, we give the definitions of PUF and PUF-based key generation scheme. We then review the constructions of previous PMKG schemes and discuss their drawbacks in Section 3. In Section 4, we present the SC-PMKG scheme and discuss its security. We then test its feasibility and make comparisons among the PMKG schemes in Sections 5 and 6, respectively. Finally, Section 7 concludes this paper.


## 2. Definition

In this section, we review definitions of the PUF and PUF-based key generation scheme.


### 2.1. PUF

References, such as [13, 14], gave a definition of the PUF with several properties. In this paper, we regard the PUF as a physical function satisfying relaxed properties below, in order for various types of PUF to be applicable to our PMKG.Definition 1 (PUF).
A family of physical functions is called the family ofPUFs if these functions satisfy the following properties.(1)
Each function works within polynomial steps(2)
Each function produces an output including a small noise; however, the signal-to-noise ratio is high enough to remove the noise by using an error correcting code. Hence, it acts as a function which provides a particular output for an input(3)
It is practically hard to characterize or clone each function(4)
Functions produce unique outputs per each of themThe third property does not ensure that it is hard to characterize or clone the physical function. The function may be characterized or cloned in future, if more sophisticated physical equipment to analyze it appears. In this paper, we regard the SRAM-PUF, Arbiter-PUF, and ring-oscillator PUF (RO-PUF) with fine processes and careful designs asPUFs.We give a security assumption of PUF, which is a formal description of above third condition, to be used in the security proof of the SC-PMKG scheme.Definition 2 (indistinguishable PUF).
Letlc and lp be input and output lengths of PUF, respectively. We state that a physically unclonable functionPUF is indistinguishable in (τ,q,ϵ) if any adversary A, within the time bound τ, cannot achieve an advantage more than ϵ, even if A observes q input-output pairs {(xi,yi)}. The advantage is defined with AdvAInd-PUF=Pr⁡Ay=1∣A1lc,1lp=x;y=PUFx − Pr⁡Ay=1∣A1lc,1lp=x;y←0,1lp. Here, A is allowed to output x where there is no overlap between PUF(x) and the observed PUF outputs PUF(xi) for i∈[1,q].This indistinguishability captures the unpredictability and unclonability, which relate to the third property of Definition1. Intuitively, the advantage AdvAInd-PUF is a metric of adversary’s ability to distinguish the PUF output from a random string. The distinguishing game is as follows: The adversary A chooses an input x for the PUF and receives either an output y=PUF(x) or a random string y∈0,1lp. A outputs 1 if A supposes that y=PUF(x). In this game, A may collect input-output pairs of PUF, as hints, by accessing the PUF oracle.Let us assume the SRAM-PUF. In the SRAM-PUF, the challenge is anlc-bit address x, and the output y is a sequence of initial states of lp SRAM cells starting with an address x. Definition 2 allows A to collect a pair {(xi,yi)} for 1≤i≤q. With these pairs, the A’s restriction stated in Definition 2 means that A is disallowed to output x where any subsequence of y=PUF(x) is included in yii∈[1,q].


### 2.2. PUF-Based Key Generation

We then review a definition of the PUF-based key generation (PBKG) scheme.Definition 3 (PUF-based key generation, PBKG).
A PBKG scheme consists of the following two phases.(i)
Enrollment phase: A key generation device in the PBKG scheme assigns a key and auxiliary data which help to reconstruct the key from a noisy PUF output in the next phase. The auxiliary data are stored into a public (maybe insecure) nonvolatile memory (NVM). Note that the device can generate the key inside itself or receive the key from outside.(ii)
Reconstruction phase: The key generation device regenerates the PUF output with some noises, loads the auxiliary data from the NVM, and reconstructs the key from these data.We then review a definition of security for the PBKG scheme. As Datta et al. [15] discussed, the indistinguishability [16, 17] may be inadequate if the PBKG scheme is composed of another cryptographic protocol, such as an encryption scheme or message authentication code (MAC). This is because even though a key derived from the PBKG scheme is indistinguishable from a random string, the indistinguishability can be lost when the key is used, e.g., to encrypt a (partially) known message. In order to ensure the security for a combination of the PBKG scheme and a cryptographic protocol, we should customize the definition of its security by modeling an adversary to collect hints from both the PBKG scheme and the cryptographic protocol; namely, to access oracles of the scheme and the protocol, respectively. In this paper, we propose a PBKG scheme for a general purpose. Therefore, we discuss the indistinguishability [16, 17] as follows.Definition 4 (indistinguishable PBKG).
Letlk be a bit length of a key derived from a PBKG scheme. We say that the PBKG scheme is indistinguishable in (τ,q,ϵ) if any adversary A, within the time bound τ, cannot achieve an advantage more than ϵ even if A invokes a key generation device with a (maybe intentionally modified) auxiliary data at most q times. Here, the advantage is defined with AdvApbkg=p1-p2, where p1=PrAy=1∣y←PBKG1lk and p2=PrAy=1∣y←0,1lk.


## 2.1. PUF

References, such as [13, 14], gave a definition of the PUF with several properties. In this paper, we regard the PUF as a physical function satisfying relaxed properties below, in order for various types of PUF to be applicable to our PMKG.Definition 1 (PUF).
A family of physical functions is called the family ofPUFs if these functions satisfy the following properties.(1)
Each function works within polynomial steps(2)
Each function produces an output including a small noise; however, the signal-to-noise ratio is high enough to remove the noise by using an error correcting code. Hence, it acts as a function which provides a particular output for an input(3)
It is practically hard to characterize or clone each function(4)
Functions produce unique outputs per each of themThe third property does not ensure that it is hard to characterize or clone the physical function. The function may be characterized or cloned in future, if more sophisticated physical equipment to analyze it appears. In this paper, we regard the SRAM-PUF, Arbiter-PUF, and ring-oscillator PUF (RO-PUF) with fine processes and careful designs asPUFs.We give a security assumption of PUF, which is a formal description of above third condition, to be used in the security proof of the SC-PMKG scheme.Definition 2 (indistinguishable PUF).
Letlc and lp be input and output lengths of PUF, respectively. We state that a physically unclonable functionPUF is indistinguishable in (τ,q,ϵ) if any adversary A, within the time bound τ, cannot achieve an advantage more than ϵ, even if A observes q input-output pairs {(xi,yi)}. The advantage is defined with AdvAInd-PUF=Pr⁡Ay=1∣A1lc,1lp=x;y=PUFx − Pr⁡Ay=1∣A1lc,1lp=x;y←0,1lp. Here, A is allowed to output x where there is no overlap between PUF(x) and the observed PUF outputs PUF(xi) for i∈[1,q].This indistinguishability captures the unpredictability and unclonability, which relate to the third property of Definition1. Intuitively, the advantage AdvAInd-PUF is a metric of adversary’s ability to distinguish the PUF output from a random string. The distinguishing game is as follows: The adversary A chooses an input x for the PUF and receives either an output y=PUF(x) or a random string y∈0,1lp. A outputs 1 if A supposes that y=PUF(x). In this game, A may collect input-output pairs of PUF, as hints, by accessing the PUF oracle.Let us assume the SRAM-PUF. In the SRAM-PUF, the challenge is anlc-bit address x, and the output y is a sequence of initial states of lp SRAM cells starting with an address x. Definition 2 allows A to collect a pair {(xi,yi)} for 1≤i≤q. With these pairs, the A’s restriction stated in Definition 2 means that A is disallowed to output x where any subsequence of y=PUF(x) is included in yii∈[1,q].


## 2.2. PUF-Based Key Generation

We then review a definition of the PUF-based key generation (PBKG) scheme.Definition 3 (PUF-based key generation, PBKG).
A PBKG scheme consists of the following two phases.(i)
Enrollment phase: A key generation device in the PBKG scheme assigns a key and auxiliary data which help to reconstruct the key from a noisy PUF output in the next phase. The auxiliary data are stored into a public (maybe insecure) nonvolatile memory (NVM). Note that the device can generate the key inside itself or receive the key from outside.(ii)
Reconstruction phase: The key generation device regenerates the PUF output with some noises, loads the auxiliary data from the NVM, and reconstructs the key from these data.We then review a definition of security for the PBKG scheme. As Datta et al. [15] discussed, the indistinguishability [16, 17] may be inadequate if the PBKG scheme is composed of another cryptographic protocol, such as an encryption scheme or message authentication code (MAC). This is because even though a key derived from the PBKG scheme is indistinguishable from a random string, the indistinguishability can be lost when the key is used, e.g., to encrypt a (partially) known message. In order to ensure the security for a combination of the PBKG scheme and a cryptographic protocol, we should customize the definition of its security by modeling an adversary to collect hints from both the PBKG scheme and the cryptographic protocol; namely, to access oracles of the scheme and the protocol, respectively. In this paper, we propose a PBKG scheme for a general purpose. Therefore, we discuss the indistinguishability [16, 17] as follows.Definition 4 (indistinguishable PBKG).
Letlk be a bit length of a key derived from a PBKG scheme. We say that the PBKG scheme is indistinguishable in (τ,q,ϵ) if any adversary A, within the time bound τ, cannot achieve an advantage more than ϵ even if A invokes a key generation device with a (maybe intentionally modified) auxiliary data at most q times. Here, the advantage is defined with AdvApbkg=p1-p2, where p1=PrAy=1∣y←PBKG1lk and p2=PrAy=1∣y←0,1lk.


## 3. Previous Works and Their Drawbacks

This section reviews the PMKG and C-PMKG schemes and discusses their drawbacks.


### 3.1. PMKG Scheme

Figures1 and 2 show the building blocks of the PMKG scheme [9] in its enrollment and reconstruction phases, respectively. They use the following functions.(i)
PUF: Physically unclonable function which, given an lc-bit input x, outputs an lp-bit string y(ii)
CS: Challenge sequencer which, given at least one li(=⌈log2lp⌉)-bit index ind and a flag flag as inputs, outputs the input of PUF x(iii)
KGF: Key generation function which, given a set of li-bit indexes {indi}i, outputs an lk-bit key key(iv)
pattern match: Comparator which, given lw-bit (lw<lp) auxiliary data stored in a public NVM and an lp-bit PUF output, looks for an index that leads an lw-bit substring of PUF output near to the auxiliary data. It may look for an index with which the distance between auxiliary data and substring indicated by the index is less than some predetermined threshold and/or with which the distance is the smallest among all substring candidatesFigure 1
Building blocks for enrollment phase in PMKG.Figure 2
Building blocks for reconstruction phase in PMKG.Paral and Devadas [9] used the Arbiter-PUF as a building block which outputs only one bit per an input. In order to obtain an lp-bit output with the Arbiter-PUF, CS generates lp inputs {xj}j∈[1,lp] sequentially from index(es), instead of one input x as above, within each round. And then PUF returns lp-bit output in total with the lp inputs in the round. More precisely, we extend the above notations; we extend CS to output lp inputs (by regarding x as {xj}j∈[1,lp]), and we extend PUF to output an lp-bit concatenation PUF(x1)⋯PUF(xlp) for inputs xjj. Note that the above notations naturally cover the SRAM-PUF. Throughout this paper, for simply, we use the above notations regardless of the type of PUF.The PMKG scheme uses four registers: an input register, an output register, an index register, and a key register, as depicted in Figures1 and 2. The input register holds an input of PUF. The output register holds an output of PUF and it is randomly accessible. The index register holds a set of indexes. The key register holds a recovered key to pass it to the cryptographic protocol.The PMKG scheme also uses the public NVM. In the enrollment phase, a key generation device stores a set of substrings of PUF outputs as a set of auxiliary data into the NVM. In the reconstruction phase, the key generation device loads the auxiliary data and uses it to reconstruct the key. Note that the NVM may be insecure and the stored auxiliary data may be modified by an adversary.Protocol 1 (PMKG). Let PUF, CS, KGF, andpattern match be functions as above. A PMKG scheme consists of two phases: an enrollment phase and a reconstruction phase below.Enrollment phase: A key generation device repeats a round operation r times with indexes {indi}i∈[0,r]. The index ind0 is an initial input ofCS and we assume that it is fixed and stored into the NVM in advance. (Since the NVM is public, we assume that ind0 is observable by adversaries. At the final steps of enrollment and reconstruction phases, we remove ind0 from the input of KGF, because its observable value does not increase the entropy of a key.) Other indexes may be also fixed in advance or randomly generated inside the device, and we assume the former case here. This phase consists of the following steps.(1)
The key generation device setsflag to one(2)
Fori∈[1,r], the device repeats the following steps:
(a)
It inputs{indk}k<i,flag into CS to generate an input of PUF xi(b)
It inputsxi into PUF to generate a PUF output yi(c)
It stores a substring of PUF outputzi=yi[indi:indi+lw-1] into the NVM. Here, s[a:b] denotes a substring of s, consisting of its a-th to b-th bits(3)
It regardsKGF{indi}i∈[1,r] as keyReconstruction phase: The key generation device repeats a round operation r times to recover the indexes and eventually the key, assigned at the enrollment phase. Note that a PUF output in this phase may differ from that in the enrollment phase. We add prime marks to the variables in this phase. This phase consists of the following steps.(1)
The key generation device setsflag to one(2)
Fori∈[1,r], the device repeats the following steps:
(a)
It inputs{indk′}k<i,flag into CS to generate an input of PUF xi′(b)
It inputsxi′ into PUF to generate a PUF output yi′(c)
It loads auxiliary datazi from the NVM(d)
It looks for an indexindi′ indicating the substring of yi′ (from indi′-th bit to (indi′+lw-1)-th bit) near to zi from thepattern match. If a mismatch happens, namely, if such an index is not detected or if more than one index is detected, indi′ and flag are set with a constant value, e.g., lw and zero, respectively(3)
Ifflag=1, then it inputs {indi′}i∈[1,r] into KGF to recover key. Otherwise, it aborts.Paral and Devadas [9] regarded PUF as a 4-XOR PUF which blends outputs of four independent Arbiter-PUFs. The blended PUF decreases a correlation between inputs and outputs of PUF; and therefore it makes the machine learning attacks [18] meaningless. The more the number of blend increases, the more difficult the attack is. In this paper, we assume that the PUF is ideal and indistinguishable as in Definition 2 where there is no correlation between the inputs and the outputs. To realize such PUF, the blending is one of solutions.The PMKG scheme has several drawbacks as follows. First of all, it requires lots of PUF output, and therefore it may be unsuitable for tiny devices in the IoT systems. The key generation device regards thelw-bit substring out of the lp-bit PUF output as auxiliary data. In other words, it discards the remaining (lp-lw)-bit in each round. In [9], they assumed that, as an example, lp=1279,lw=256 and r=16. With this example, the (1279-256)×16=16368 bits, out of 1279×16=20464 PUF output bits, are discarded. It makes the PMKG scheme inefficient, by requiring the execution time to generate the 16368 PUF output bits and the power consumption more.In addition to its inefficiency, it has a security vulnerability, caused by attacks with an NVM manipulation. Such a manipulation leads mismatches in its reconstruction and these mismatches change the device’s behavior. Delvaux and Verbauwhede [10, 11] gave attacks, namedsnake attacks, which modify the auxiliary data in the NVM, invoke the key generation with the modified one, and guess the index indi by observing its behavior.Specifically, their attacks repeatedly modify the auxiliary data in the NVM to be (noncircularly) one bit shifted by guessing the next bit of PUF output. If the modified auxiliary data move out of the range of the PUF output with a large amount of shift, a mismatch happens and the device’s behavior changes; until the amount is less than or equal to the distance to head or end, the device outputs a key, which should be different from the assigned one because inputs forCS and KGF differ; on the other hand, if it exceeds the distance, the device aborts because the mismatch happens. Namely, the snake attacks repeat the shift and guess by increasing its amount of shift until the device’s behavior changes and return the amount as its guess for the secret index.


### 3.2. C-PMKG Scheme

To enhance the efficiency and/or the security, a circular PMKG (C-PMKG) scheme was proposed in [10, 19] independently and further discussed in [11, 20], respectively. It regards PUF outputs circularly shifted by secret indices {indi} as auxiliary data.Figures3 and 4 show its building blocks. As forPUF,CS,pattern match, andKGF, we use the same notations as ones for the PMKG scheme, while we set lw=lp in PUF. In addition to them, it also uses the functionrotate:(i)
rotate: rotate function which, given an lw-bit string y and an amount of circularity ind∈[0,lw-1], circularly shifts y by ind-bitFigure 3
Building blocks for enrollment phase in C-PMKG.Figure 4
Building blocks for reconstruction phase in C-PMKG.Protocol 2 (C-PMKG). LetPUF,CS,pattern match, andKGF be functions as in the PMKG scheme, except that the output length of thePUF is not lp-bit but lw-bit. Also letrotate be a function as above. The C-PMKG scheme consists of following two phases: an enrollment phase and a reconstruction phase below.Enrollment phase: A key generation device repeats a round operation r times with indexes {indi}i∈[0,r]. The index ind0 is an initial input ofCS and we assume that it is fixed in advance and stored in the NVM. Other indexes may be also fixed in advance or randomly chosen inside the device, and we assume the former case. This phase consists of the following steps.(1)
The key generation device setsflag to one(2)
Fori∈[1,r], the device repeats the following steps:
(a)
It inputs{indk}k<i,flag into CS to generate an input of PUF xi(b)
It inputsxi into PUF to generate a PUF output yi(c)
It stores a circularly shifted PUF outputzi=rotate(yi,indi) into the NVM as auxiliary data(3)
It regardsKGF{indi}i∈[1,r] as keyReconstruction phase: The key generation device repeats a round operation r times to recover the indexes and eventually key, assigned at the enrollment phase. This phase consists of the following steps.(1)
The key generation device setsflag to one(2)
Fori∈[1,r], the device repeats the following steps:
(a)
It inputs{indk′}k<i,flag into CS to generate an input of PUF xi′(b)
It inputsxi′ into PUF to generate a PUF output yi′(c)
It loads auxiliary datazi from the NVM(d)
It looks for an indexindi′ indicating the circularity shifted string rotate(yi′,indi′) near to zi from thepattern match. If a mismatch happens, namely, if such an index is not detected or if more than one index is detected, indi′ and flag are set with a constant value lw and zero, respectively(3)
Ifflag=1, then it inputs {indi′}i∈[1,r] into KGF to recover key. Otherwise, it abortsUnlike the PMKG scheme, the C-PMKG scheme uses the whole (circularly shifted) PUF output as auxiliary data. Removing the discarding of PUF outputs enhances its efficiency compared to the PMKG scheme. Moreover, since there is no head or end in the circularity, the snake attacks are meaningless to the C-PMKG scheme.However, in order for the C-PMKG scheme to be in use, there are technical issues to be considered. The most important one is a careful design ofCS. The circularly shifted PUF outputs are stored in the public NVM as auxiliary data in the C-PMKG scheme; and, here, if some of them have intersections, the information of the corresponding indexes may be leaked. Hence, to ensure the security of C-PMKG scheme, CS should be designed leading to no intersection over rounds.


## 3.1. PMKG Scheme

Figures1 and 2 show the building blocks of the PMKG scheme [9] in its enrollment and reconstruction phases, respectively. They use the following functions.(i)
PUF: Physically unclonable function which, given an lc-bit input x, outputs an lp-bit string y(ii)
CS: Challenge sequencer which, given at least one li(=⌈log2lp⌉)-bit index ind and a flag flag as inputs, outputs the input of PUF x(iii)
KGF: Key generation function which, given a set of li-bit indexes {indi}i, outputs an lk-bit key key(iv)
pattern match: Comparator which, given lw-bit (lw<lp) auxiliary data stored in a public NVM and an lp-bit PUF output, looks for an index that leads an lw-bit substring of PUF output near to the auxiliary data. It may look for an index with which the distance between auxiliary data and substring indicated by the index is less than some predetermined threshold and/or with which the distance is the smallest among all substring candidatesFigure 1
Building blocks for enrollment phase in PMKG.Figure 2
Building blocks for reconstruction phase in PMKG.Paral and Devadas [9] used the Arbiter-PUF as a building block which outputs only one bit per an input. In order to obtain an lp-bit output with the Arbiter-PUF, CS generates lp inputs {xj}j∈[1,lp] sequentially from index(es), instead of one input x as above, within each round. And then PUF returns lp-bit output in total with the lp inputs in the round. More precisely, we extend the above notations; we extend CS to output lp inputs (by regarding x as {xj}j∈[1,lp]), and we extend PUF to output an lp-bit concatenation PUF(x1)⋯PUF(xlp) for inputs xjj. Note that the above notations naturally cover the SRAM-PUF. Throughout this paper, for simply, we use the above notations regardless of the type of PUF.The PMKG scheme uses four registers: an input register, an output register, an index register, and a key register, as depicted in Figures1 and 2. The input register holds an input of PUF. The output register holds an output of PUF and it is randomly accessible. The index register holds a set of indexes. The key register holds a recovered key to pass it to the cryptographic protocol.The PMKG scheme also uses the public NVM. In the enrollment phase, a key generation device stores a set of substrings of PUF outputs as a set of auxiliary data into the NVM. In the reconstruction phase, the key generation device loads the auxiliary data and uses it to reconstruct the key. Note that the NVM may be insecure and the stored auxiliary data may be modified by an adversary.Protocol 1 (PMKG). Let PUF, CS, KGF, andpattern match be functions as above. A PMKG scheme consists of two phases: an enrollment phase and a reconstruction phase below.Enrollment phase: A key generation device repeats a round operation r times with indexes {indi}i∈[0,r]. The index ind0 is an initial input ofCS and we assume that it is fixed and stored into the NVM in advance. (Since the NVM is public, we assume that ind0 is observable by adversaries. At the final steps of enrollment and reconstruction phases, we remove ind0 from the input of KGF, because its observable value does not increase the entropy of a key.) Other indexes may be also fixed in advance or randomly generated inside the device, and we assume the former case here. This phase consists of the following steps.(1)
The key generation device setsflag to one(2)
Fori∈[1,r], the device repeats the following steps:
(a)
It inputs{indk}k<i,flag into CS to generate an input of PUF xi(b)
It inputsxi into PUF to generate a PUF output yi(c)
It stores a substring of PUF outputzi=yi[indi:indi+lw-1] into the NVM. Here, s[a:b] denotes a substring of s, consisting of its a-th to b-th bits(3)
It regardsKGF{indi}i∈[1,r] as keyReconstruction phase: The key generation device repeats a round operation r times to recover the indexes and eventually the key, assigned at the enrollment phase. Note that a PUF output in this phase may differ from that in the enrollment phase. We add prime marks to the variables in this phase. This phase consists of the following steps.(1)
The key generation device setsflag to one(2)
Fori∈[1,r], the device repeats the following steps:
(a)
It inputs{indk′}k<i,flag into CS to generate an input of PUF xi′(b)
It inputsxi′ into PUF to generate a PUF output yi′(c)
It loads auxiliary datazi from the NVM(d)
It looks for an indexindi′ indicating the substring of yi′ (from indi′-th bit to (indi′+lw-1)-th bit) near to zi from thepattern match. If a mismatch happens, namely, if such an index is not detected or if more than one index is detected, indi′ and flag are set with a constant value, e.g., lw and zero, respectively(3)
Ifflag=1, then it inputs {indi′}i∈[1,r] into KGF to recover key. Otherwise, it aborts.Paral and Devadas [9] regarded PUF as a 4-XOR PUF which blends outputs of four independent Arbiter-PUFs. The blended PUF decreases a correlation between inputs and outputs of PUF; and therefore it makes the machine learning attacks [18] meaningless. The more the number of blend increases, the more difficult the attack is. In this paper, we assume that the PUF is ideal and indistinguishable as in Definition 2 where there is no correlation between the inputs and the outputs. To realize such PUF, the blending is one of solutions.The PMKG scheme has several drawbacks as follows. First of all, it requires lots of PUF output, and therefore it may be unsuitable for tiny devices in the IoT systems. The key generation device regards thelw-bit substring out of the lp-bit PUF output as auxiliary data. In other words, it discards the remaining (lp-lw)-bit in each round. In [9], they assumed that, as an example, lp=1279,lw=256 and r=16. With this example, the (1279-256)×16=16368 bits, out of 1279×16=20464 PUF output bits, are discarded. It makes the PMKG scheme inefficient, by requiring the execution time to generate the 16368 PUF output bits and the power consumption more.In addition to its inefficiency, it has a security vulnerability, caused by attacks with an NVM manipulation. Such a manipulation leads mismatches in its reconstruction and these mismatches change the device’s behavior. Delvaux and Verbauwhede [10, 11] gave attacks, namedsnake attacks, which modify the auxiliary data in the NVM, invoke the key generation with the modified one, and guess the index indi by observing its behavior.Specifically, their attacks repeatedly modify the auxiliary data in the NVM to be (noncircularly) one bit shifted by guessing the next bit of PUF output. If the modified auxiliary data move out of the range of the PUF output with a large amount of shift, a mismatch happens and the device’s behavior changes; until the amount is less than or equal to the distance to head or end, the device outputs a key, which should be different from the assigned one because inputs forCS and KGF differ; on the other hand, if it exceeds the distance, the device aborts because the mismatch happens. Namely, the snake attacks repeat the shift and guess by increasing its amount of shift until the device’s behavior changes and return the amount as its guess for the secret index.


## 3.2. C-PMKG Scheme

To enhance the efficiency and/or the security, a circular PMKG (C-PMKG) scheme was proposed in [10, 19] independently and further discussed in [11, 20], respectively. It regards PUF outputs circularly shifted by secret indices {indi} as auxiliary data.Figures3 and 4 show its building blocks. As forPUF,CS,pattern match, andKGF, we use the same notations as ones for the PMKG scheme, while we set lw=lp in PUF. In addition to them, it also uses the functionrotate:(i)
rotate: rotate function which, given an lw-bit string y and an amount of circularity ind∈[0,lw-1], circularly shifts y by ind-bitFigure 3
Building blocks for enrollment phase in C-PMKG.Figure 4
Building blocks for reconstruction phase in C-PMKG.Protocol 2 (C-PMKG). LetPUF,CS,pattern match, andKGF be functions as in the PMKG scheme, except that the output length of thePUF is not lp-bit but lw-bit. Also letrotate be a function as above. The C-PMKG scheme consists of following two phases: an enrollment phase and a reconstruction phase below.Enrollment phase: A key generation device repeats a round operation r times with indexes {indi}i∈[0,r]. The index ind0 is an initial input ofCS and we assume that it is fixed in advance and stored in the NVM. Other indexes may be also fixed in advance or randomly chosen inside the device, and we assume the former case. This phase consists of the following steps.(1)
The key generation device setsflag to one(2)
Fori∈[1,r], the device repeats the following steps:
(a)
It inputs{indk}k<i,flag into CS to generate an input of PUF xi(b)
It inputsxi into PUF to generate a PUF output yi(c)
It stores a circularly shifted PUF outputzi=rotate(yi,indi) into the NVM as auxiliary data(3)
It regardsKGF{indi}i∈[1,r] as keyReconstruction phase: The key generation device repeats a round operation r times to recover the indexes and eventually key, assigned at the enrollment phase. This phase consists of the following steps.(1)
The key generation device setsflag to one(2)
Fori∈[1,r], the device repeats the following steps:
(a)
It inputs{indk′}k<i,flag into CS to generate an input of PUF xi′(b)
It inputsxi′ into PUF to generate a PUF output yi′(c)
It loads auxiliary datazi from the NVM(d)
It looks for an indexindi′ indicating the circularity shifted string rotate(yi′,indi′) near to zi from thepattern match. If a mismatch happens, namely, if such an index is not detected or if more than one index is detected, indi′ and flag are set with a constant value lw and zero, respectively(3)
Ifflag=1, then it inputs {indi′}i∈[1,r] into KGF to recover key. Otherwise, it abortsUnlike the PMKG scheme, the C-PMKG scheme uses the whole (circularly shifted) PUF output as auxiliary data. Removing the discarding of PUF outputs enhances its efficiency compared to the PMKG scheme. Moreover, since there is no head or end in the circularity, the snake attacks are meaningless to the C-PMKG scheme.However, in order for the C-PMKG scheme to be in use, there are technical issues to be considered. The most important one is a careful design ofCS. The circularly shifted PUF outputs are stored in the public NVM as auxiliary data in the C-PMKG scheme; and, here, if some of them have intersections, the information of the corresponding indexes may be leaked. Hence, to ensure the security of C-PMKG scheme, CS should be designed leading to no intersection over rounds.


## 4. Single-Round Circular PMKG Scheme

In this section, we propose a simple PMKG scheme, named single-round circular PMKG (SC-PMKG), and show its security against manipulation attacks.


### 4.1. Our Idea

We construct the SC-PMKG scheme, based on the C-PMKG scheme, by improving the simplicity and security as follows.(i)
Simplicity: Unlike the previous PMKG schemes with r round operations, the SC-PMKG scheme is performed within a single-round. In order to increase the entropy of key efficiently, the previous schemes prepare r PUF output strings with lw-bit each. On the other hand, the SC-PMKG scheme prepares an (n·lw)-bit PUF output string and divides it into n substrings with lw-bit each. From this change, there is no fear to overlap among the (sub)strings and the security discussion can be simplified. Moreover, the simple design helps us to develop devices.(ii)
Security: To detect and defeat the manipulation attack, we introduce a check string cs to confirm the correctness of the key reconstruction. The string is derived from a cryptographic hash function with which, by regarding it as a random oracle, we can theoretically prove the security of the SC-PMKG scheme.The following subsections give our construction and the security consideration.


### 4.2. Construction

As forPUF,CS, rotate,pattern match, andKGF, we use the same notations for the C-PMKG scheme, except that we assume lp>lw for PUF as in the PMKG scheme. Additionally, our scheme uses a hash function hash, to check the integrity of a reconstructed key.(i)
hash: Cryptographic one-way hash function which, given an lk-bit key, returns an lcs-bit check string csProtocol 3 (SC-PMKG). Let PUF, CS, rotate,pattern match, and KGF be functions as in the C-PMKG scheme, except that we assume lp=n·lw for an integer n, and let hash be a hash function as above. The SC-PMKG scheme consists of the following two phases: an enrollment phase and a reconstruction phase below.Enrollment phase: A key generation device with indexes {indi}i∈[0,n] performs an enrollment as follows. The index ind0 is an initial input forCS and we assume that it is fixed in advance and stored in the NVM. Other indexes may be also fixed in advance or randomly chosen inside the device, and we assume the former case. This phase consists of the following steps.(1)
The key generation device inputsind0 into CS to generate an input of PUF x(2)
It inputsx into PUF to generate a PUF output(3)
It divides the PUF output inton substrings {yi}i∈[1,n] with lw-bit each(4)
It stores{zi=rotate(yi,indi)} for i∈[1,n] into the NVM as auxiliary data(5)
It computeskey=KGF({indi}i∈[1,n])(6)
It computescs=hash(ind0,{(zi,indi)}i∈[1,n],key) and stores it into the NVM as a check stringReconstruction phase: The key generation device recovers the indexes and eventually the key, assigned at the enrollment phase. This phase consists of the following steps.(1)
The device setsflag to one(2)
It inputsind0′ into CS to generate an input of PUF x′(3)
It inputsx′ into PUF to generate a PUF output(4)
It divides the PUF output inton substrings yi′i∈[1,n] with lw-bit each(5)
Fori∈[1,n], it repeats the following steps:
(a)
It loads auxiliary datazi′ from the NVM(b)
It looks for an indexindi′ indicating the circularity shifted string rotate(yi′,indi′) near to zi from thepattern match. If a mismatch happens, indi′ andflag are set with a constant value lw and zero, respectively(6)
Ifflag=1, then it inputs {indi′}i∈[1,n] into KGF to compute key′. Otherwise, it aborts(7)
It loads a check stringcs′ from the NVM(8)
Ifhash(ind0′,{(zi′,indi′)}i∈1,n,key′)=cs′ holds, it regards key′ as the reconstructed key. Otherwise, it abortsThere are two advantages in the SC-PMKG scheme. The first one is that, from its simple construction with a single-round, we do not need to pay attention to the intersections of auxiliary data over rounds. It simplifies the design ofCS and the security consideration. The second one is that, by introducing the check string, the security against manipulation attacks of the NVM is ensured, if hash is an ideal hash function (random oracle [12]). We discuss the security in the following subsection.


### 4.3. Security Consideration

As in the C-PMKG scheme, since the auxiliary data is obtained from the circularly shift of the PUF output, the snake attacks are invalid for the SC-PMKG scheme. In addition, we can prove that the SC-PMKG scheme is an indistinguishable PBKG scheme in the random oracle model [12]. As for the security, the following theorem holds.Theorem 5.
Assume thatPUF is an indistinguishable PUF in (τ,0,ϵ) and that hash is the random oracle. Then, the SC-PMKG scheme is an indistinguishable PBKG in (τ′,qK,ϵ′) where(1)ϵ′=ϵ-1lwnandτ′=τ+qKOTK.Here, TK denotes an execution time of the SC-PMKG scheme.The proof is done by the contradiction. Namely, we show that if there exists an adversaryA against the SC-PMKG scheme, we can construct an algorithm B, which uses A as a subroutine, to break the indistinguishability of PUF. The construction of B is simple and we give a proof in the Appendix.Note that, in Theorem5, we assume that (τ,0,ϵ) for the underlying PUF. The condition of q=0 makes the PUF strongly protected within the system, lest no PUF output for an adversarial input is observable. However, there is a trade-off between the assumptions for the secure system (q=0) and for a secure PUF (q>0, see next paragraph). The condition we assume relaxes the choice of PUF because we can neglect the fear of the machine learning attacks [18], and because we can use a weak PUF with a small input-output space, such as SRAM-PUF.We can extend the security model of Definition4 so that an adversary against the PBKG scheme is allowed to collect input-output pairs of the underlying PUF; that is, we can consider the security model with a powerful adversary. In this case, the indistinguishability of the PBKG scheme is defined with four-tuple (τ′,qK,qP,ϵ′), instead of three-tuple (τ′,qK,ϵ′), where the adversary accesses the PBKG and PUF oracles at most qK and qP times, respectively. With this extension, we can prove another theorem, if the underlying PUF is indistinguishable in (τ,qP,ϵ), instead of (τ,0,ϵ). If qK is so large, a weak PUF may not be a possible choice for our system. Note that, even with this extension, the adversary of the SC-PMKG scheme should be restricted not to access the PUF oracle on x corresponding to the target key. To simplify the security proof, this paper discusses the security without the extension.Regardless of whether the model is extended or not, we require the PUF so that its output is unobservable by invalid interface other than the interfaces in Definition2. As for the SRAM-PUF, for example, to avoid the physical probing attack [21, 22], we should choose an appropriate PUF, with a fine process [23], etc.


### 4.4. Notes on Parameters

The SC-PMKG scheme is parameterized with the following parameters:lw, n, lp=n·lw, li=log2lw, and lcs. If thepattern match in the reconstruction phase looks for the index with a threshold, the threshold th is also required.Among them,n and li (and, therefore, lw and lp) relate to the security. The (Shannon) entropy of key source is estimated by n·li. To ensure the 160-bit entropy for the source, we set them so that n·li exceeds 160. In addition, lcs also relates to the security. The larger it is, up to n·li, the harder the manipulation attack is.On the other hand,lw and th relate to the correctness. There are two failure scenarios in reconstructing the key: the pattern match fails at Step (5)(b) or the hash value does not match the check string at Step (8). Note that if the indexes are correctly recovered at Step (5)(b), the verification at Step (8) should succeed. Hence, let us discuss the failure at Step (5)(b).The pattern match at Step (5)(b) looks for an index with which the distance between a substring candidate and the auxiliary data is less thanth and/or the smallest, as stated in Section 3.1. In order for the pattern match to be performed with only the former criterion, th should be set with adequate value (and additional criterion to narrow index candidates, if necessary) so that only the correct index is detected. With the latter criterion, it is easy to see that the index can be correctly recovered if lw is large. Note that, under the condition that each bit of PUF output is independent of other bits, the distances for correct and incorrect indexes are expected about pe·lw and lw/2, where pe is a bit error rate, respectively. Namely, if lw increases, the gap between these distances also increases and the correct index is detectable. In the next section, we check the relation between lw and the correctness of the recovered index (key). The combination of the first and second criteria, first finding index candidates with a loose threshold and then detecting the index with the smallest distance, enables not only the recovery of correct index but also the detection of system errors from faults and manipulation attacks.


## 4.1. Our Idea

We construct the SC-PMKG scheme, based on the C-PMKG scheme, by improving the simplicity and security as follows.(i)
Simplicity: Unlike the previous PMKG schemes with r round operations, the SC-PMKG scheme is performed within a single-round. In order to increase the entropy of key efficiently, the previous schemes prepare r PUF output strings with lw-bit each. On the other hand, the SC-PMKG scheme prepares an (n·lw)-bit PUF output string and divides it into n substrings with lw-bit each. From this change, there is no fear to overlap among the (sub)strings and the security discussion can be simplified. Moreover, the simple design helps us to develop devices.(ii)
Security: To detect and defeat the manipulation attack, we introduce a check string cs to confirm the correctness of the key reconstruction. The string is derived from a cryptographic hash function with which, by regarding it as a random oracle, we can theoretically prove the security of the SC-PMKG scheme.The following subsections give our construction and the security consideration.


## 4.2. Construction

As forPUF,CS, rotate,pattern match, andKGF, we use the same notations for the C-PMKG scheme, except that we assume lp>lw for PUF as in the PMKG scheme. Additionally, our scheme uses a hash function hash, to check the integrity of a reconstructed key.(i)
hash: Cryptographic one-way hash function which, given an lk-bit key, returns an lcs-bit check string csProtocol 3 (SC-PMKG). Let PUF, CS, rotate,pattern match, and KGF be functions as in the C-PMKG scheme, except that we assume lp=n·lw for an integer n, and let hash be a hash function as above. The SC-PMKG scheme consists of the following two phases: an enrollment phase and a reconstruction phase below.Enrollment phase: A key generation device with indexes {indi}i∈[0,n] performs an enrollment as follows. The index ind0 is an initial input forCS and we assume that it is fixed in advance and stored in the NVM. Other indexes may be also fixed in advance or randomly chosen inside the device, and we assume the former case. This phase consists of the following steps.(1)
The key generation device inputsind0 into CS to generate an input of PUF x(2)
It inputsx into PUF to generate a PUF output(3)
It divides the PUF output inton substrings {yi}i∈[1,n] with lw-bit each(4)
It stores{zi=rotate(yi,indi)} for i∈[1,n] into the NVM as auxiliary data(5)
It computeskey=KGF({indi}i∈[1,n])(6)
It computescs=hash(ind0,{(zi,indi)}i∈[1,n],key) and stores it into the NVM as a check stringReconstruction phase: The key generation device recovers the indexes and eventually the key, assigned at the enrollment phase. This phase consists of the following steps.(1)
The device setsflag to one(2)
It inputsind0′ into CS to generate an input of PUF x′(3)
It inputsx′ into PUF to generate a PUF output(4)
It divides the PUF output inton substrings yi′i∈[1,n] with lw-bit each(5)
Fori∈[1,n], it repeats the following steps:
(a)
It loads auxiliary datazi′ from the NVM(b)
It looks for an indexindi′ indicating the circularity shifted string rotate(yi′,indi′) near to zi from thepattern match. If a mismatch happens, indi′ andflag are set with a constant value lw and zero, respectively(6)
Ifflag=1, then it inputs {indi′}i∈[1,n] into KGF to compute key′. Otherwise, it aborts(7)
It loads a check stringcs′ from the NVM(8)
Ifhash(ind0′,{(zi′,indi′)}i∈1,n,key′)=cs′ holds, it regards key′ as the reconstructed key. Otherwise, it abortsThere are two advantages in the SC-PMKG scheme. The first one is that, from its simple construction with a single-round, we do not need to pay attention to the intersections of auxiliary data over rounds. It simplifies the design ofCS and the security consideration. The second one is that, by introducing the check string, the security against manipulation attacks of the NVM is ensured, if hash is an ideal hash function (random oracle [12]). We discuss the security in the following subsection.


## 4.3. Security Consideration

As in the C-PMKG scheme, since the auxiliary data is obtained from the circularly shift of the PUF output, the snake attacks are invalid for the SC-PMKG scheme. In addition, we can prove that the SC-PMKG scheme is an indistinguishable PBKG scheme in the random oracle model [12]. As for the security, the following theorem holds.Theorem 5.
Assume thatPUF is an indistinguishable PUF in (τ,0,ϵ) and that hash is the random oracle. Then, the SC-PMKG scheme is an indistinguishable PBKG in (τ′,qK,ϵ′) where(1)ϵ′=ϵ-1lwnandτ′=τ+qKOTK.Here, TK denotes an execution time of the SC-PMKG scheme.The proof is done by the contradiction. Namely, we show that if there exists an adversaryA against the SC-PMKG scheme, we can construct an algorithm B, which uses A as a subroutine, to break the indistinguishability of PUF. The construction of B is simple and we give a proof in the Appendix.Note that, in Theorem5, we assume that (τ,0,ϵ) for the underlying PUF. The condition of q=0 makes the PUF strongly protected within the system, lest no PUF output for an adversarial input is observable. However, there is a trade-off between the assumptions for the secure system (q=0) and for a secure PUF (q>0, see next paragraph). The condition we assume relaxes the choice of PUF because we can neglect the fear of the machine learning attacks [18], and because we can use a weak PUF with a small input-output space, such as SRAM-PUF.We can extend the security model of Definition4 so that an adversary against the PBKG scheme is allowed to collect input-output pairs of the underlying PUF; that is, we can consider the security model with a powerful adversary. In this case, the indistinguishability of the PBKG scheme is defined with four-tuple (τ′,qK,qP,ϵ′), instead of three-tuple (τ′,qK,ϵ′), where the adversary accesses the PBKG and PUF oracles at most qK and qP times, respectively. With this extension, we can prove another theorem, if the underlying PUF is indistinguishable in (τ,qP,ϵ), instead of (τ,0,ϵ). If qK is so large, a weak PUF may not be a possible choice for our system. Note that, even with this extension, the adversary of the SC-PMKG scheme should be restricted not to access the PUF oracle on x corresponding to the target key. To simplify the security proof, this paper discusses the security without the extension.Regardless of whether the model is extended or not, we require the PUF so that its output is unobservable by invalid interface other than the interfaces in Definition2. As for the SRAM-PUF, for example, to avoid the physical probing attack [21, 22], we should choose an appropriate PUF, with a fine process [23], etc.


## 4.4. Notes on Parameters

The SC-PMKG scheme is parameterized with the following parameters:lw, n, lp=n·lw, li=log2lw, and lcs. If thepattern match in the reconstruction phase looks for the index with a threshold, the threshold th is also required.Among them,n and li (and, therefore, lw and lp) relate to the security. The (Shannon) entropy of key source is estimated by n·li. To ensure the 160-bit entropy for the source, we set them so that n·li exceeds 160. In addition, lcs also relates to the security. The larger it is, up to n·li, the harder the manipulation attack is.On the other hand,lw and th relate to the correctness. There are two failure scenarios in reconstructing the key: the pattern match fails at Step (5)(b) or the hash value does not match the check string at Step (8). Note that if the indexes are correctly recovered at Step (5)(b), the verification at Step (8) should succeed. Hence, let us discuss the failure at Step (5)(b).The pattern match at Step (5)(b) looks for an index with which the distance between a substring candidate and the auxiliary data is less thanth and/or the smallest, as stated in Section 3.1. In order for the pattern match to be performed with only the former criterion, th should be set with adequate value (and additional criterion to narrow index candidates, if necessary) so that only the correct index is detected. With the latter criterion, it is easy to see that the index can be correctly recovered if lw is large. Note that, under the condition that each bit of PUF output is independent of other bits, the distances for correct and incorrect indexes are expected about pe·lw and lw/2, where pe is a bit error rate, respectively. Namely, if lw increases, the gap between these distances also increases and the correct index is detectable. In the next section, we check the relation between lw and the correctness of the recovered index (key). The combination of the first and second criteria, first finding index candidates with a loose threshold and then detecting the index with the smallest distance, enables not only the recovery of correct index but also the detection of system errors from faults and manipulation attacks.


## 5. Feasibility Tests

In this section, we test the feasibility of the SC-PMKG scheme by simulations and experiments, respectively.


### 5.1. Simulation

We first check the feasibility of the SC-PMKG scheme by a simulation with an approximation analysis. In this simulation, we estimate the failure probability in the key reconstruction by changing parameterslw, n, and pe where pe is a bit error rate in the PUF output. Following Paral and Devadas [9], for each lw, we set n so that the entropy of input for KDF is 160-bit. For example, if we use lw=32, we set n=32 as a minimum integer so that nlog2⁡lw≥160.Table1 summarizes the failure probability for pe∈{0.15,0.035} and lw from 32 to 160. Here, we assume 0.15 and 0.035 for pe because pe=0.15 is a well discussed parameter for PUF instantiations and pe=0.035 is an average of bit error rate in our experiments below. As for n, we set n for each lw by a minimum integer as in the above case for lw=32. With lw and n, lp=lw×n is a length of the PUF output. For each pe and lw, the “prob. (sim)” shows the failure probability from the simulation, which is estimated as shown in Algorithm 1.Table 1
Failure probability in SC-PMKG ((a)pe=0.15, (b)pe=0.035).
(a) lw n l p prob. (sim) prob. (approx) 32 32 1024 0.538 0.630 48 29 1392 8.02 × 1 0 - 2 5.40 × 1 0 - 2 64 27 1728 8.29 × 1 0 - 3 4.41 × 1 0 - 3 96 25 2400 9.02 × 1 0 - 5 2.83 × 1 0 - 5 128 23 2944 1.00 × 1 0 - 6 1.69 × 1 0 - 7 160 22 3520 0 1.01 × 1 0 - 9  (b) lw n l p prob. (sim) prob. (approx) 8 53 424 0.682 0.242 16 40 640 6.86 × 1 0 - 2 7.51 × 1 0 - 3 24 34 816 2.73 × 1 0 - 3 1.45 × 1 0 - 4 32 32 1024 1.29 × 1 0 - 4 2.54 × 1 0 - 6 48 29 1392 2.00 × 1 0 - 7 6.27 × 1 0 - 10 64 27 1728 0 1.36 × 1 0 - 13Algorithm 1
Enrollment phase: (1) Generate an lp-bit string at random. (2) Divide the string into n substrings {yi}i∈[1,n] with lw-bit each. (3) For i∈[1,n], choose indi∈[0,lw-1] at random. (4) For i∈[1,n], compute zi=rotate(yi,indi). (5) Store {(yi,indi,zi)}i∈[1,n]. Reconstruction phase: (1) Set cnt to 0. (2) Repeat the following steps N times: (a) For i∈[1,n], generate an lw-bit string ei where each bit of ei is 1 with probability pe, independently. (b) For i∈[1,n], set yi′=yi⊕ei and look for indi′ where rotate(yi′,indi′) is near to zi. (c) Increment cnt if there exists i∈[1,n] such that indi≠indi. (3) Compute the failure probability by cnt/N.For eachlw, we tried N=5,000,000 reconstructions, in total. (In Table 1, “0” means that there is no error for N=5,000,000, which means that prob. (sim) is less that 1/N=2×10-7.) From our simulation, lw=160 (pe=0.15) or lw=48 (pe=0.15) should be enough for the key reconstruction with the failure probability less than 10-6.We also estimate the failure probability by an approximation analysis, as shown in “prob. (approx)” in Table1.Let us discuss the distance between a substring stored in the NVM and one circularly shifted by thecorrect index. The distance follows the binomial distribution B(lw,pe). We approximate it with the normal distribution Nlwpe,lwpe(1-pe). Similarly, we approximate the distribution of the distance related to anincorrect index with the normal distribution Nlw/2,lw/4.In case the distance for thecorrect index is more than one for theincorrect index, the wrong index is recovered. Let us denote the probability by q. The difference between the distances for correct and incorrect indexes follows the normal distribution N(mean,var) where mean=lwpe-lw/2 and var=lwpe(1-pe)+lw/4, which is a composite (difference) of two normal distributions. With this notation, q can be estimated by(2)q≈∫mean/var∞12πexp⁡x22dx.Note that there arelw-1 wrong candidates for one index. If q is small enough, the probability where one of wrong index is recovered is estimated by 1-(1-q)lw-1≈1-{1-(lw-1)q}=(lw-1)q. Also note that there are n indexes to be recovered. Similarly, the probability where one of index is incorrectly recovered among n substrings is approximated by (lw-1)nq. “prob. (approx)” in Table 1 summarizes the failure probability for each pe, lw (and q), and n.Since the approximations are inappropriate for small parameters, there are gaps between the failure probabilities from simulation and our approximation analysis. However, our analysis seems valid for largelw; namely, lw=160 and lw=64 are large enough, when pe is 0.15 and 0.035, respectively, so that the failure probability is negligible.


### 5.2. Experiments with Nucleo Boards

We then test the feasibility with two Nucleo-F401RE boards (http://www.st.com/en/evaluation-tools/nucleo-f401re.html (accessible on Nov. 9, 2018)) by STMicroelectronics. We load lp=n·lw initial SRAM bits on each board and regard them as an output of SRAM-PUF. The experiments are performed in the room temperature and the power is supplied by the USB interface. (The characteristics of PUF would change by environments such as temperature and supplied power voltage. Refer to Chapter 4 of [24], for instance. The success rate of the key reconstruction depends on the bit error rate of PUF. We should select adequate parameters, such as lw and n, with the worst error rate among the different environments.) The averages of bit error rate for 4,096 SRAM bits on these boards are 3.30% and 3.57%, respectively. Here, the bit error rate is evaluated, in a simple manner, by a difference between the bit for the first read and bits for the following 10,000 reads.Similar to the above simulation, we estimate the failure probability by changinglw. For each board, we try the reconstruction 10,000 times. Table 2 summarizes the failure probabilities for two boards, respectively. (Similar to Table 1, “0” means that there is no error for N=10,000 and that the failure probability is less than 10-4.)Table 2
Failure probability in SC-PMKG with Nucleo-F401RE boards.
lw n l p board 1 board 2 8 53 424 1 1 16 40 640 0.137 0.434 24 34 816 8.00 × 1 0 - 4 4.20 × 1 0 - 3 32 32 1024 1.00 × 1 0 - 4 1.00 × 1 0 - 4 48 29 1392 0 0 64 27 1728 0 0For smalllw, the probabilities differ from those of Table 1. This is because, different from the simulation, the initial values of SRAM cells are not uniformly random, and their stabilities are not constant for each bit. With larger lw, the probabilities in our experiment are close to those in the simulation. Note that since the initial values of SRAM cells are not uniform, if we use this SRAM as SRAM-PUF directly, the resulting SC-PMKG scheme might be insecure. From our observations, the initial values of SRAM cells have certain bit patterns; and therefore regarding either a concatenation of first bits of each byte or an XORed value of different cells like 4-XOR PUF as an output of the SRAM-PUF may be a solution to enhance the security of the SC-PMKG scheme.


### 5.3. Experiments with Open Dataset

In order to check the feasibility with a different type of PUF, we use the ring oscillators’ (ROs’) frequencies which are available at the Secure Embedded Systems (SES) Lab at Virginia Tech (http://rijndael.ece.vt.edu/puf/download.html (accessible on Nov. 9, 2018)). We select “Full Standard Dataset Oscillator Counts.” The dataset includes 100 oscillator counts for 512 ROs of 193 Xilinx Spartan-3E FPGA boards (XC3S500E) under the standard temperature/voltage. Using these ROs’ counts, up to 5122=130816 bits of RO-PUF can be derived. We implement the SC-PMKG with some of them. The average bit error rate for the first 1728 RO-PUF bits is 1.21%.In the dataset, there are only 100 samples for each board. In the feasibility test, we evaluate the average and maximum of failure probabilities over 193 boards. Table3 summarizes them. (Similar to Table 2, “0” means that the failure probability is less than 1/(99×193)<5.23×10-5.)Table 3
Failure probability in SC-PMKG with ring oscillator (open dataset).
lw n l p prob. (ave) prob. (max) 8 53 424 0.592 1 16 40 640 0.461 1 24 34 816 0 0 32 32 1024 0 0Since the bit error rate (1.21%) is smaller than that of Nucleo boards (approx. 3%), the failure probabilities are also small. That is, for the correctness, fewer PUF output bits are required, for example,lp=1024.


## 5.1. Simulation

We first check the feasibility of the SC-PMKG scheme by a simulation with an approximation analysis. In this simulation, we estimate the failure probability in the key reconstruction by changing parameterslw, n, and pe where pe is a bit error rate in the PUF output. Following Paral and Devadas [9], for each lw, we set n so that the entropy of input for KDF is 160-bit. For example, if we use lw=32, we set n=32 as a minimum integer so that nlog2⁡lw≥160.Table1 summarizes the failure probability for pe∈{0.15,0.035} and lw from 32 to 160. Here, we assume 0.15 and 0.035 for pe because pe=0.15 is a well discussed parameter for PUF instantiations and pe=0.035 is an average of bit error rate in our experiments below. As for n, we set n for each lw by a minimum integer as in the above case for lw=32. With lw and n, lp=lw×n is a length of the PUF output. For each pe and lw, the “prob. (sim)” shows the failure probability from the simulation, which is estimated as shown in Algorithm 1.Table 1
Failure probability in SC-PMKG ((a)pe=0.15, (b)pe=0.035).
(a) lw n l p prob. (sim) prob. (approx) 32 32 1024 0.538 0.630 48 29 1392 8.02 × 1 0 - 2 5.40 × 1 0 - 2 64 27 1728 8.29 × 1 0 - 3 4.41 × 1 0 - 3 96 25 2400 9.02 × 1 0 - 5 2.83 × 1 0 - 5 128 23 2944 1.00 × 1 0 - 6 1.69 × 1 0 - 7 160 22 3520 0 1.01 × 1 0 - 9  (b) lw n l p prob. (sim) prob. (approx) 8 53 424 0.682 0.242 16 40 640 6.86 × 1 0 - 2 7.51 × 1 0 - 3 24 34 816 2.73 × 1 0 - 3 1.45 × 1 0 - 4 32 32 1024 1.29 × 1 0 - 4 2.54 × 1 0 - 6 48 29 1392 2.00 × 1 0 - 7 6.27 × 1 0 - 10 64 27 1728 0 1.36 × 1 0 - 13Algorithm 1
Enrollment phase: (1) Generate an lp-bit string at random. (2) Divide the string into n substrings {yi}i∈[1,n] with lw-bit each. (3) For i∈[1,n], choose indi∈[0,lw-1] at random. (4) For i∈[1,n], compute zi=rotate(yi,indi). (5) Store {(yi,indi,zi)}i∈[1,n]. Reconstruction phase: (1) Set cnt to 0. (2) Repeat the following steps N times: (a) For i∈[1,n], generate an lw-bit string ei where each bit of ei is 1 with probability pe, independently. (b) For i∈[1,n], set yi′=yi⊕ei and look for indi′ where rotate(yi′,indi′) is near to zi. (c) Increment cnt if there exists i∈[1,n] such that indi≠indi. (3) Compute the failure probability by cnt/N.For eachlw, we tried N=5,000,000 reconstructions, in total. (In Table 1, “0” means that there is no error for N=5,000,000, which means that prob. (sim) is less that 1/N=2×10-7.) From our simulation, lw=160 (pe=0.15) or lw=48 (pe=0.15) should be enough for the key reconstruction with the failure probability less than 10-6.We also estimate the failure probability by an approximation analysis, as shown in “prob. (approx)” in Table1.Let us discuss the distance between a substring stored in the NVM and one circularly shifted by thecorrect index. The distance follows the binomial distribution B(lw,pe). We approximate it with the normal distribution Nlwpe,lwpe(1-pe). Similarly, we approximate the distribution of the distance related to anincorrect index with the normal distribution Nlw/2,lw/4.In case the distance for thecorrect index is more than one for theincorrect index, the wrong index is recovered. Let us denote the probability by q. The difference between the distances for correct and incorrect indexes follows the normal distribution N(mean,var) where mean=lwpe-lw/2 and var=lwpe(1-pe)+lw/4, which is a composite (difference) of two normal distributions. With this notation, q can be estimated by(2)q≈∫mean/var∞12πexp⁡x22dx.Note that there arelw-1 wrong candidates for one index. If q is small enough, the probability where one of wrong index is recovered is estimated by 1-(1-q)lw-1≈1-{1-(lw-1)q}=(lw-1)q. Also note that there are n indexes to be recovered. Similarly, the probability where one of index is incorrectly recovered among n substrings is approximated by (lw-1)nq. “prob. (approx)” in Table 1 summarizes the failure probability for each pe, lw (and q), and n.Since the approximations are inappropriate for small parameters, there are gaps between the failure probabilities from simulation and our approximation analysis. However, our analysis seems valid for largelw; namely, lw=160 and lw=64 are large enough, when pe is 0.15 and 0.035, respectively, so that the failure probability is negligible.


## 5.2. Experiments with Nucleo Boards

We then test the feasibility with two Nucleo-F401RE boards (http://www.st.com/en/evaluation-tools/nucleo-f401re.html (accessible on Nov. 9, 2018)) by STMicroelectronics. We load lp=n·lw initial SRAM bits on each board and regard them as an output of SRAM-PUF. The experiments are performed in the room temperature and the power is supplied by the USB interface. (The characteristics of PUF would change by environments such as temperature and supplied power voltage. Refer to Chapter 4 of [24], for instance. The success rate of the key reconstruction depends on the bit error rate of PUF. We should select adequate parameters, such as lw and n, with the worst error rate among the different environments.) The averages of bit error rate for 4,096 SRAM bits on these boards are 3.30% and 3.57%, respectively. Here, the bit error rate is evaluated, in a simple manner, by a difference between the bit for the first read and bits for the following 10,000 reads.Similar to the above simulation, we estimate the failure probability by changinglw. For each board, we try the reconstruction 10,000 times. Table 2 summarizes the failure probabilities for two boards, respectively. (Similar to Table 1, “0” means that there is no error for N=10,000 and that the failure probability is less than 10-4.)Table 2
Failure probability in SC-PMKG with Nucleo-F401RE boards.
lw n l p board 1 board 2 8 53 424 1 1 16 40 640 0.137 0.434 24 34 816 8.00 × 1 0 - 4 4.20 × 1 0 - 3 32 32 1024 1.00 × 1 0 - 4 1.00 × 1 0 - 4 48 29 1392 0 0 64 27 1728 0 0For smalllw, the probabilities differ from those of Table 1. This is because, different from the simulation, the initial values of SRAM cells are not uniformly random, and their stabilities are not constant for each bit. With larger lw, the probabilities in our experiment are close to those in the simulation. Note that since the initial values of SRAM cells are not uniform, if we use this SRAM as SRAM-PUF directly, the resulting SC-PMKG scheme might be insecure. From our observations, the initial values of SRAM cells have certain bit patterns; and therefore regarding either a concatenation of first bits of each byte or an XORed value of different cells like 4-XOR PUF as an output of the SRAM-PUF may be a solution to enhance the security of the SC-PMKG scheme.


## 5.3. Experiments with Open Dataset

In order to check the feasibility with a different type of PUF, we use the ring oscillators’ (ROs’) frequencies which are available at the Secure Embedded Systems (SES) Lab at Virginia Tech (http://rijndael.ece.vt.edu/puf/download.html (accessible on Nov. 9, 2018)). We select “Full Standard Dataset Oscillator Counts.” The dataset includes 100 oscillator counts for 512 ROs of 193 Xilinx Spartan-3E FPGA boards (XC3S500E) under the standard temperature/voltage. Using these ROs’ counts, up to 5122=130816 bits of RO-PUF can be derived. We implement the SC-PMKG with some of them. The average bit error rate for the first 1728 RO-PUF bits is 1.21%.In the dataset, there are only 100 samples for each board. In the feasibility test, we evaluate the average and maximum of failure probabilities over 193 boards. Table3 summarizes them. (Similar to Table 2, “0” means that the failure probability is less than 1/(99×193)<5.23×10-5.)Table 3
Failure probability in SC-PMKG with ring oscillator (open dataset).
lw n l p prob. (ave) prob. (max) 8 53 424 0.592 1 16 40 640 0.461 1 24 34 816 0 0 32 32 1024 0 0Since the bit error rate (1.21%) is smaller than that of Nucleo boards (approx. 3%), the failure probabilities are also small. That is, for the correctness, fewer PUF output bits are required, for example,lp=1024.


## 6. Discussion

Table4 summarizes the comparison among the PMKG, C-PMKG, and SC-PMKG schemes. Let us discuss the detail of each item below. We refer to [9, 25] for parameters of the PMKG and C-PMKG schemes, respectively. As for C-PMKG, we also add parameters, in parentheses, which we estimate by the similar theoretical approximation of Section 5.1. Note that the authors of [9, 25] decided the parameters so that the failure in key reconstruction should be negligible (with probability less that 10-6).Table 4
Comparison of PMKG schemes.
Item PMKG [9] C-PMKG [25] SC-PMKG K e y, lk 128 128 128 H(Source) 160 160 160 H(Index) 10 8 (log2⁡160) log 2 ⁡ 160 ♯rounds, r 16 20 (22) 1 ♯indexes/round, n 1 1 22 | P a t t e r n |, lw 256 256 (160) 160 P U F   o u t p u t / r o u n d, lp 1279 256 (160) 3520 TotalPUFoutput 20464 5120 (3520) 3520 Storage 4096 5120 (3520) 3776  Additional functions over PMKG – r o t a t e r o t a t e, hash C S design Complicated Complicated Simple Snake attacks Vulnerable Secure Secure Provable security Unknown Unknown Yes“Key” is a bit length of an output of KGF. References [9, 25] set it to 128, and we follow them for the SC-PMKG scheme. In order to generate the 128-bit key, the previous works [9, 25] assumed that the source of the key had the 160-bit entropy in preparation for the entropy loss of PUF output and the randomness of indexes; i.e., the sum of index lengths was supposed to be 160-bit. We also follow them for the SC-PMKG scheme and give it in the second line “H(Source)” as the entropy of the source.“H(Index)” shows the entropy of an index. In the PMKG scheme, the index is an address of the first bit of substring. Paral and Devadas [9] set it with 10. In the C-PMKG and SC-PMKG schemes, on the other hand, the index is the amount of circular shift which is at most the length of the substring. Reference [25] followed [9] to set the length of the substring with 256, and therefore H(Index) was set with 8. On the SC-PMKG scheme, from our simulation and experiments, the length of substring seems enough with 160 and we set H(Index) with log2160. As in parentheses, the length of substring for the C-PMKG scheme can be similarly estimated with our approximation estimation, so that the failure probability is less than 10-6.“♯rounds” is a number of rounds. On the PMKG scheme, to generate (lk=)128-bit key with (li=)10-bit index per round, 13 rounds may be enough. However, Paral and Devadas [9] used 16 to make the entropy of source 160-bit. Following them, we set the number of rounds to make the entropy of source 160-bit or more. Similarly, in the C-PMKG scheme, since the length of each index is eight, it is 160/8=20 (or ⌈160/log2160⌉=22 with our approximation). As for the SC-PMKG scheme, the number of rounds is one.“♯indexes/rounds” are a number of indexes per a round. In the PMKG and C-PMKG schemes, they are one. On the other hand, in the SC-PMKG scheme, it is 160/log2⁡160=22 to achieve the 160-bit entropy.“Pattern” is a bit length of a (sub)string of a PUF output to be pattern-matched. It is the same as the bit length of each auxiliary data. They set it to 256 which is expected to avoid the mismatch. As for the SC-PMKG scheme, we set it to 160 from our simulation. As in parentheses, the length of Pattern (and ones of items below) for the C-PMKG scheme can be similarly estimated as ours, with the approximation estimation.“PUFoutput/round” is a bit length of PUF output in each round. They set it with 1279(=1024+256-1) and 256, respectively. As for the SC-PMKG scheme, since it requires 22(=n) substrings of 160-bit in a round as we discuss, the length is 22×160=3520.“TotalPUFoutput” is a bit length of PUF output in total, which is lp×r×n.“Storage” means the total length of stored data in the NVM, except ind0. The total length of auxiliary data is estimated with lw·r·n. In the SC-PMKG scheme, beside the auxiliary data, the check string is stored in the NVM. We assume that SHA-256 is used as hash and the length is 3520+256=3776.Although the C-PMKG and SC-PMKG schemes require fewer PUF outputs in total, they require additional functions, which derive an implementation and computation overhead, compared to the PMKG scheme. In the PMKG scheme, the index search can be performed sequentially. On the other hand, the C-PMKG and SC-PMKG schemes require the additional functionrotate. In addition, the SC-PMKG scheme requires the hash function to compute the check string.The challenge sequencersCS for the PMKG and C-PMKG schemes are carefully designed to avoid an intersection of auxiliary data over rounds as we discussed; however, its design for the SC-PMKG scheme can be simple.As for the security, the PMKG scheme is vulnerable against the snake attacks. The C-PMKG and SC-PMKG schemes are secure against the snake attacks. Let us discuss the provable security. Although [20] discussed the provable security of the C-PMKG scheme, the security model did not take the manipulation attacks into consideration. It remains an open problem whether the C-PMKG scheme is provably secure without a hash function which, in the SC-PMKG, plays an important role in the provable security. On the other hand, the SC-PMKG scheme is provably secure as in Theorem 5.To summarize, compared to the PMKG scheme, the C-PMKG and SC-PMKG schemes are not only secure but also efficient; namely, they require less PUF output. In addition, the simpleCS design to generate a challenge in the single-round of the SC-PMKG scheme allows us to use even a weak PUF, like the SRAM-PUF, as a building block. It is an advantage for applications with tiny devices, such as the IoT systems.


## 7. Conclusions

This paper proposes a secure and efficient PMKG scheme, the SC-PMKG scheme, which saves the PUF output and allows a simple construction. It can be realized with even a weak PUF, such as the SRAM-PUF, and is suitable for tiny devices in the IoT systems. Feasibility test with other types of PUF changing the environments is one of our future works.



---

*Source: 1719585-2019-01-01.xml*