Communications of the ACM

limited data; meanwhile, the theoretical learning results from the previously mentioned research5 imply that both an exponential number of response bits and an exponential attack time are required. The response-data exposure can be throttled dynamically by the server as knowledge of new attacks emerges, even against an adaptive chosen-chal-lenge adversary with uninterrupted interface access to the device, a result of the use of mutual authentication.

So Where Are We?

While a lot of strides have been made in terms of silicon PUF constructs and an understanding of their behavior in terms of practical and theoretical learnability when used in a challenge/ response context, some questions remain. While the recent theoretical learning results declared that certain PUF constructs are exponentially difficult to PAC-learn, there is still a reliance on heuristic results for what the exponential learning-difficulty curve looks like for the “best attacks” available. Although there have been several years of machine-learning attacks on PUFs by multiple research groups thus far, there is still work to be done in this area to affirm a practical and safe heuristic limit in terms of number of response bits that can be exposed for different XOR PUF constructs that ensures security. Fortunately, the lockdown approach20 allows the server to manage the response-bits exposure at the protocol level, thereby allowing a degree of dynamic adjustment to emerging attack results.

Additionally, side-channel attacks coupled with machine learning represent a relatively new research area. While the lockdown protocol20 addressed various side-channel attacks that have been published, including noise-side-channel attacks, noise-fil-tering attacks, and backside photon-ics imaging attacks, new attacks may emerge that could bring forth research into new countermeasures and new PUF constructs.

Machine-learning attacks have been applied successfully on a variety of PUF constructs using computer-simulated PUF models11 and, later, for silicon PUF implementations. 12 These attacks include the popular XOR construction of the arbiter PUF and serve as a benchmark for a PUF’s machine-learning attack attributes as well as a catalyst for the development of countermeasures.

Another breakthrough attack was presented in 2015, where PUF response “reliability” information, which can be viewed as noise side-channel information, is used essentially to bypass the nonlinear mixing effects of the XORs, making even a PUF with a very high (for example, 20- plus) number of XORs relatively easy to learn (for example, using a few hundred thousand response bits). 1

Probabilistic Authentication

To thwart the attacks described in the previous section, machine-learning attack countermeasures were developed, taking advantage of the model-building concept. With it, challenges can now be determined at runtime.

Recall that the authentication verifica-
tion model that is stored on the server
side can be used to synthesize any chal-
lenge/response pairs; the server is no
longer restricted to the challenge/re-
sponse pairs collected during the pro-
visioning process. The device can now
produce part of the challenge at run-
time, so neither the server nor the de-
vice alone can fully determine the exact
subchallenges used. This also makes
the authentication process probabilis-
tic: even if a (malicious) server repeat-
edly issues the same challenge Cs to the
device, any output response R would be
a function of both Cs and Cd. Here, Cd
represents the device-generated part
of the challenge, which is passed back
to the server. Instead of R = PUFid (Cs),
now it is R = PUFid (Cs || Cd). As a re-
sult, the PUF cannot be trivially distin-
guished from random by repeating the
same challenge Cs, analogous to what
happens when probabilistic encryp-
tion is used in the cryptographic realm.

The use of device-generated challenges8, 21 can be viewed as a countermeasure to prevent repeated challenges, which addresses the reliability-based machine-learning attacks that take advantage of noise-side-channel information. 1 This also addresses the noise-filtering approach using majority voting employed to attack silicon PUFs. 12

Theoretical Learning Difficulty Recently published research5 establishes the theoretical difficulty of PUF learning—in particular, for the popular XOR PUF construct. These recent results used the celebrated PAC (probably-approximately correct) framework, 16 which links learning with complexity theory, and applied that framework to determine which kinds of PUFs are polynomially learnable and which would require an exponential attack resource (for example, attack runtime, number of response bits) with respect to the circuit size. The authors of this research5 not only declared certain XOR PUF constructs to be exponentially difficult to learn under the PAC framework, but also questioned whether such PUFs can be realized in practice. A new protocol-level countermeasure20 allows exponentially dif-ficult-to-learn PUFs based on the PAC results5 to be instantiated in practice, with silicon results to demonstrate practical feasibility. The main idea is to run the authentication protocol in both directions; only after the PUF device has authenticated the authentication verification server does the PUF device release new response bits to a potential man-in-the-middle adversary. The device is effectively locked down, with the exposure of new response bits implicitly controlled by the server at the protocol level.

To address noise-side-channel attacks, a device-side challenge8, 21 can be added. The challenge/response behavior of the device is locked down at the protocol level, and the adversary is faced with machine learning using