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.
PUF NFC IC and Tags
For a silicon PUF to be useful for au-
thentication, it must be integrated into
a form that can be easily authenticated.
With the recent emergence of NFC-
enabled smartphones, custom RFID/
private key, it is difficult to derive an
exponential number of challenge/re-
sponse pairs from a linearly sized PUF
circuit. Arbitrary logical or arithmetic
post-processing cannot be applied to
the silicon manufacturing variation
since the physical PUF evaluation
noise would be amplified. Therefore,
popular PUF authentication circuits
are evaluated in a mostly linear fash-
ion, with limited nonlinear mixing
(for example, using XORs as described
earlier), and are therefore prone to
modeling attacks.
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