Breaking XOR Arbiter PUFs without Reliability Information

We make the following contributions in this paper:

• •

  We introduce a novel chosen challenge attack on unreliable and, more importantly, perfectly reliable XOR-Arbiter PUFs¹¹1To support open science and facilitate follow-up research, the source code of our attack will be made publicly available upon the acceptance of the paper..

• •

  We evaluate the effectiveness of the proposed attack using a PUF simulation under various conditions, including various noise levels, sampling rates, and the number of flips.

• •

  We demonstrate the practicality of our attack by attacking a real XOR APUF implemented on an FPGA.

• •

  We discuss an effective countermeasure against our attack.

We present the necessary background of APUF, XOR APUF, and the reliability-based attacks in Sec. 2. The proposed chosen challenge attack is discussed in Sec. 3. Sec. 4 presents the experimental results and a fair comparison with the state-of-the-art reliability-based attacks. An effective countermeasure is discussed in Sec. 5, followed by some other related work in Sec. 6. The paper concludes in Sec. 7.

An Arbiter PUF (APUF) is a strong PUF that consists of $n$ consecutive delay stages that lead to an arbiter. The stages are identical 2-to-1 multiplexers that lead the top and bottom signals based on the challenge bits that are applied to their $select$ inputs. In the last stage, the top and bottom signals have an accumulated delay difference due to the differences in the delay of every stage introduced by process variations. Finally, the arbiter outputs a ‘1’ or ’0’ bit depending on which signal arrives at the arbiter faster.

The behavior of an APUF can be captured by a Linear Additive Delay Model [11]

where $W$ is the weight vector, $\Psi$ is the parity (or feature) vector and $n$ is the number of challenge bits or the number of delay stages. The weight vector $W$ defines the character of the APUF, and it is determined only by process variations. For $\Delta\geq 0$, the response $r=0$, otherwise $r=1$. The parity vector $\Psi$ is solely based on the challenge vector $c$ in the following way:

A $k$-XOR APUF is constructed by $k$ APUFs that are fed by the same challenge, and their response bits are XORed together. Unlike APUFs, XOR APUFs have a non-linear model due to the added XOR. Thus, it is generally believed that XOR APUFs are much harder to model than APUFs, and the difficulty grows exponentially in $k$ when the reliability-based attack was unknown [16].

Unlike the classical machine learning modeling attacks on PUFs that use response bits directly for training, in a reliability-based modeling attack, the reliability information derived from repeated measurement of CRPs is used for modeling. The response to each challenge is measured multiple times to compute the reliability of the CRP. This reliability gives information about the delay difference $\Delta$ of an APUF component in an XOR APUF under the evaluated challenge. This is because when $|\Delta|$ is smaller than a threshold value $\epsilon$, the CRP is unreliable, and the response can easily be flipped between $0$ and $1$; otherwise, the CRP is reliable, and the response is consistent. Also, in an XOR APUF, if one of the underlying APUFs is unreliable, then the overall XOR APUF is also unreliable. This is why the reliability information reveals the delay information of the individual APUF and allows a divide-and-conquer strategy to model individual APUFs in an XOR APUF. In [1], Becker used a popular evolution strategy-based optimization algorithm, Covariance Matrix Adaptation Evolution Strategy (CMA-ES), to learn the weight vector of the APUF along with the threshold value $\epsilon$. For this purpose, a set of challenges $C_{i}$ is randomly generated, and the reliability $R_{i}$ is measured for every challenge using Eq. 3, where $M$ is the number of measurements per CRP.

Then, Becker used CMA-ES to optimize the PUF model by maximizing the Pearson correlation coefficient of the measured reliability and the predicted reliability based on the PUF models in the current iteration of the CMA-ES algorithm. The algorithm will converge to the model of an underlying APUF in the attacked XOR APUF. By executing the CMA-ES algorithm multiple times, all APUF models in the XOR APUF will be modeled eventually.

An enhanced reliability-based attack on XOR APUF was presented by Nguyen et al., which utilizes a more accurate reliability model to improve the prediction accuracy or attack efficiency [15]. Tobisch et al. demonstrated that it is also possible to use a gradient-based optimization to launch reliability-based attacks [18].

To the best of our knowledge, the reliability-based attack is still the most efficient attack on XOR APUFs. However, if no reliability information is available to the attacker, then none of the reliability-based attacks [1, 15, 18] would work. As shown in [20], by implementing a majority voting at the end of every APUF in an XOR APUF, one can boost the reliability of the APUFs and the overall XOR APUF arbitrarily. Although this defense may incur a performance overhead, it is very effective in stopping the reliability-based attack because the attacker cannot find a noisy CRP to derive its reliability. Another potential countermeasure that could paralyze the reliability-based attacks is the (logical) erasable PUF interface [9, 10]. The access to each individual CRP can be controlled by the interface, and then, it is impossible to remeasure the responses of an erased challenge anymore. Thus, it prevents the attacker from deriving the reliability information even if the underlying PUF is still noisy.

Our proposed attack can defeat both of the countermeasures since we do not rely on reliability information.

We assume the same adversarial model as the reliability-based attack [1]. The attackers can apply any challenges they want to the PUF and only get the responses of the queried challenges back, i.e., no other side channel information. The only difference is that we choose to measure correlated CRPs, but the reliability-based attacks choose to measure the same CRPs repeatedly.

Key Idea. In this strategy, we focus on manipulating $\Psi$ and investigate how it affects the delay model (Eq. 1). Suppose that there is a flip in the $\Psi$ vector of the delay model; then, this flip will lead to a different coefficient for one of the weight vector elements. Note that a challenge $c$ consists of only $0$ or $1$, but a $\Psi$ vector only contains $1$ or $-1$, according to Eq. 2. Thus, after one flip in $\Psi$ (from $1$ to $-1$ or from $-1$ to $1$), the delay difference $\Delta$ would be changed from $\Delta_{1}$ to $\Delta_{2}$, as shown in Eq. 4. Whether this change leads to a flipped response bit reveals whether $\Delta$ flips its sign, i.e., whether $|\Delta|<2|w[1]|$, in the case of Eq. 4. This is the key enabler of our attack on APUFs.

This relation also allows us to attack individual APUFs in an XOR APUF. Statistically speaking, if there is a flip in $\Psi$, it is unlikely that the response of an APUF will be flipped. But if the response of one APUF is flipped, this flip will be propagated to the output of the XOR and be observable by the attacker, assuming this flip in $\Psi$ does not flip the responses of the other APUFs. Of course, multiple APUF responses can be flipped occasionally, but we will use the Pearson correlation coefficient as a robust indicator to deal with the “noise” introduced by multiple APUF response flips.

Detailed Steps. Algorithm 1 shows the pseudo-code of the proposed chosen challenge attack, and it models the PUF using the flipping probability information. To compute the flipping probability, we first choose a challenge $c$ randomly in the challenge space and then convert it to the corresponding $\Psi$ according to Eq.2. Then we randomly sample $m$ $\Psi_{i}$ vectors that has a Hamming distance of 1 from $\Psi$:

The Hamming distance of $1$ means only one bit is different between $\Psi$ and $\Psi_{i}$. Practically speaking, if one bit $\Psi[i]$ is flipped, then two consecutive bits ($c[i-1]$ and $c[i]$) should be flipped in the corresponding challenge $c$, except for $i=0$, then only $c[0]$ needs to be flipped.

Fig.1 illustrates the main idea of our attack. For any randomly chosen $\Psi$ (e.g., $\Psi_{a}$, $\Psi_{b}$, or $\Psi_{c}$), the $m$ sampled points with $d_{H}=1$ are on the circular radius to the centroid of $\Psi$. If the $\Psi$ is close to the response decision boundary, it is more likely that the responses to the sampled neighboring $\Psi_{i}$ vectors are different from the response of $\Psi$.

Thus, after sampling many random challenges and their surrounding challenges, we get a dataset of $(\Psi,F)$ pairs as Eq. 7.

where $N$ is the size of the training dataset in our attack.

Then, the CMA-ES algorithm is used to find the optimal $W$ model for individual APUF in an XOR APUF. To start the procedure, K random models are generated. For each model $W_{j}$, the $\Delta$ is calculated for each $\Psi$ vector included in $\mathcal{Z}$, and the predicted non-flipping probability $F^{{}^{\prime}}$ is computed according to Eq.8. The linear relationship of $F$ and $F^{\prime}$ will be discussed in Sec. 3.4.

The objective function of CMA-ES is the Pearson correlation coefficient $\rho_{j}$ between the measured non-flipping probability ($F_{1}$,…,$F_{N}$) and the predicted non-flipping probability ($F^{{}^{\prime}}_{1}$,…,$F^{{}^{\prime}}_{N}$). Inside the CMA-ES algorithm, an $L$ number of $w$ APUF models with the highest $\rho_{j}$ value are kept in each iteration to generate a new generation of $K$ models. After $T$ iterations, the CMA-ES outputs the model with the highest Pearson correlation coefficient $\rho$ as the best model. When attacking an XOR APUF, the CMA-ES algorithm would converge to one of the individual APUFs in the XOR APUF. We can repeat the whole process, and eventually, all the APUFs of an XOR APUF will be modeled after a sufficient number of CMA-ES runs; therefore, the whole model of XOR APUF is revealed.

As shown in  [2, 15], the non-flipping probability $F$ (or reliability) of a CRP in an APUF, under some perturbations, has a relationship with the delay difference $\Delta$ of the CRP and the standard deviation $\sigma$ of the perturbations as follows.

In a reliability-based attack, the perturbations come from environmental noise, and thus $\sigma$ is the standard deviation of the environmental noise with a normal distribution $\mathcal{N}(0,\sigma)$. Similarly, in our proposed chosen challenge attack, the perturbations come from the flipped $\Psi$ bit, so $\sigma$ is the standard deviation of the perturbation ($2W[i]$) caused by one flip in $\Psi$. Note that each weight vector component $W[i]$ in an APUF is believed to follow a normal distribution $\mathcal{N}(0,\sigma/2)$. This normal distribution assumption is widely used in APUF simulations and is validated in real APUF implementations in the past research [1, 15, 16].

Eq. 9 can be approximated as Eq.10 if $F\in[0.1,0.9]$.

Due to the linear relationship between the measured non-flipping probability $F$ and the delay model $\Delta$, which is also the predicted non-flipping probability $F^{\prime}$, we can select the best-fitting models among random models and then optimize them in every iteration of the CMA-ES algorithm to generate an accurate model of an underlying APUF.

The proposed attack shares many similarities with the reliability-based attack in [15], which is an enhanced version of the attack in [1]. Both our attack and the reliability-based attacks need to choose the CRPs to be measured, and they all exploit the fact that the non-flipping probability (or the reliability) has a linear relationship with the delay difference $\Delta$. Most importantly, both our attack and the reliability-based attack can learn individual APUFs in an XOR APUF in a divide-and-conquer manner and scale linearly w.r.t. the number of XORs.

Actually, the proposed chosen challenge attack can be viewed as a generalization of the reliability-based attack. As we will show in Sec. 4.3, our chosen attack does not have to restrict the hamming distance to 1; the known reliability-based attacks are a special case of our chosen challenge attack when the hamming distance is 0, and the perturbation is caused by small environmental noise instead of flips in $\Psi$. Also, our attack methodology is more widely applicable, including attacking perfectly reliable XOR APUFs.

We first want to study the sensitivity of the modeling accuracy w.r.t. the number of samples ($m$) around every centroid challenge. We tested various numbers of samples on a perfectly reliable 2-XOR APUF using the proposed attack, each with $150\times 10^{3}$ $(\Psi,F)$ pairs. As shown in Fig. 2, using 16 samples or more, the prediction accuracy of individual APUFs would be considerably high, and by increasing the number of samples from 16 to 64, there is not much remarkable improvement in accuracy. Therefore, we use 16 samples for the rest of our experiments.

The results in Table 1 show that the proposed chosen challenge attack can attack individual APUFs in a perfectly reliable XOR APUF with high accuracy. In contrast, the reliability-based attacks do not work in the same condition. The prediction accuracy of the original Becker’s attack (directly copied from [1]) on noisy XOR APUFs with the same number of XORs and the same number of challenge-reliability pairs is also shown in Table 1.

The proposed attack works not only with reliable PUFs but also on practically unreliable PUFs. In every APUF simulation, a noise term independently drawn from $\mathcal{N}(0,\sigma_{N})$ is added to $\Delta$ for every measurement. As shown in Table  2, when $\sigma_{N}=0.0055$ and even with more noise as $\sigma_{N}=0.01$, the accuracy of the chosen challenge attack is considerably high, and the XOR APUF could be modeled. Note that the weight vectors of APUFs are drawn from $\mathcal{N}(0,1)$ in the simulation. The two noise level parameters $\sigma_{N}$ are inherited from the noisy PUF simulation2, and they correspond to two reliability levels measured by [15] on their APUF FPGA implementations. We also reproduced the results of the enhanced reliability-based attack on the same targets using the authors’ open-source codes2 so that the two attacks can be properly compared in Table 2. In the reliability-based attack, each challenge-reliability pair is derived from 17 measurements, just like each $(\Psi,F)$ pair is derived from 17 CRPs in our chosen challenge attack. The measured reliability of each PUF is also reported in Table 2. It is measured as the percentage of CRPs that do not flip within 10 measurements. Note that we only evaluate our attacks on odd number XOR APUFs in all the following experiments to avoid the influence of the systemic bias in the responses of even number XOR APUFs [21].

From Table 2, we notice that, in general, the proposed attack has slightly lower accuracy than the enhanced reliability-based attack. This is because the perturbation in $\Delta$ in the reliability-based attack is smaller than the perturbation introduced by one flip in $\Psi$ in our attack. This means that in the dataset collected for the chosen challenge attack, it is more likely that more than one APUF responses get flipped, and this is considered as noise in our attack and negatively affects the training.

We would like to extend the idea of our proposed attack and investigate whether flipping more bits in $\Psi$ can lead to a successful attack. Table 3 presents the prediction accuracy of individual APUFs in an XOR APUF with $d_{H}=2$ and three different noise levels $\sigma_{N}$. The results show that the XOR APUFs still could be modeled with acceptable accuracy values. However, as expected, the accuracy is lower than the one-flip attacks because likely more multiple APUF response flips occur in the training dataset.

Last but not least, we evaluate the proposed attack on XOR APUFs implemented on an FPGA. Table 4 shows the modeling accuracy of the individual APUFs under the proposed attack. The high accuracy presented in Table 4 validates the effectiveness of our attack in practice.