Communications of the ACM

discussed later. The PUF output for each basic arbiter PUF is derived from a differential race condition formed by successive delay stages. Each stage consists of a crossbar switch that can be formed using 2: 1 multiplexers. A challenge bit for each of the n = 64 stages determines whether the parallel path or the cross path is active. Collectively, n challenge bits determine which path is chosen to create the transition at the top input to the arbiter latch, and similarly for the bottom input. The arbiter latch is formed using a pair of NAND gates that is cross-cou-pled (this is denoted by the rectangular boxes marked A in Figure 1). The difference comparison between the two delay paths, configured by the challenge bits, determines whether the basic arbiter PUF produces a 1 or a 0 output bit. The layout of the design has to be symmetrically matched so that random manufacturing variation affects the response.

To obtain a multibit challenge, a seed challenge is applied to a challenge expansion circuit—for example, an LFSR (linear-feedback shift register), which is not shown in the figure. The LFSR is used to produce the subchallenge bits <c>. The subchallenge bits are used to generate a response bit. Using multiple subchallenges and concatenating the resulting response bits together forms a multibit response.

Because of the linear and additive nature of the response evaluation, it was recognized early on that learning attacks can be employed to mathematically model a basic arbiter PUF. 7 Various techniques, including creating multiple instances of the basic PUF and bitwise-XORing their output bits, 14 served as countermeasures to make learning attacks more difficult. Figure 1 depicts four basic 64-stage PUF instances whose output can be XORed together in both a parallel and a serial fashion. An XOR PUF is formed by instantiating multiple copies and XORing the output bits.

Model Building to Aid
Authentication

For many commercial applications,
more than just a few challenge/re-
sponse pairs are needed. With the
original PUF authentication scheme,
the number of challenge/response
pairs grows linearly with the number of
supported authentication events. If the
number of supported events is relative-
ly large—say, 1,000 authentications or
more—this would result in many chal-
lenge/response pairs needing to be col-
lected as part of the provisioning proc-
ess and then stored on the server; both
the provisioning time and the server
storage would grow linearly with the
number of authentications supported.
A major development in PUF re-
search was using the ease of model
building of the basic arbiter PUF (prior
to the XOR countermeasure) to create
an authentication verification model on
the server side. This authentication
verification model essentially serves as
a symmetric counterpart to the physi-
cal PUF circuit on the device. There-
fore, instead of collecting a number
of challenge/response pairs that are
linear in the number of authentication
events and requiring a linear amount
of storage on the server side, there is
now a constant-size storage per PUF
device on the server side regardless of
the number of authentication events.
While the basic arbiter PUF can be
learned with relative ease, the XORing
produces output bits that are more dif-
ficult to learn. One can take advantage
of this by making the easier-to-learn
variant available during the provision-
ing process (that is, bypassing the
XORs). Here, the pre-XOR response
bits for each basic arbiter PUF are ob-
tained, and a state-of-the-art machine-
learning algorithm can be used to
derive the delay values on the server
side. Afterward, the XORs are no lon-
ger bypassed, increasing the machine-
learning difficulty for the adversary.
To get the benefit of constant provi-
sioning time and the constant storage
requirement, the provisioning func-
tionality needs to be disabled after the
device leaves the manufacturing facil-
ity. For example, the publicly readable
serial number of the device, once pro-
grammed, can disable the extraction of
the PUF response bits prior to the XOR
countermeasure. Reprogramming of
the serial number is also disabled.

Machine Learning Attacks

When lightweight PUF-based authentication is performed using a threshold-based comparison as described previously, neither a cryptographic algorithm nor an obfuscated key is required on the silicon PUF device. Unfortunately, without a cryptographic algorithm and an obfuscated secret or