International Association
for Cryptologic Research

This paper discusses combined modeling and side

channel attacks on Strong Physical Unclonable Functions (Strong

PUFs). We illustrate our method by the example of the two

currently most secure (CCS 2010, IEEE T-IFS 2013) electrical

Strong PUFs, so-called XOR Arbiter PUFs and Lightweight

PUFs, and successfully attack them at sizes and complexities

far beyond the reach of pure modeling techniques (CCS 2010,

IEEE T-IFS 2013).

Our approach makes use of the first power and timing

side channels on PUFs reported in the literature. Both provide

information on the single outputs of the many parallel Arbiter

PUFs inside an XOR Arbiter PUF or Lightweight PUF, and

indicate how many of these single outputs (in sum) were equal

to one (and how many were equal to zero) before they entered

the final XOR gate. Taken for itself, this side channel information

is of little value. But if combined with suitably adapted machine

learning techniques, it substantially changes attack performance:

It reduces the empirically estimated complexities for modeling the

above two PUFs from exponential (CCS 2010, IEEE T-IFS) to

low degree polynomial.

The practical viability of our attacks is firstly demonstrated

by SPICE simulations, and by subsequent ML experiments on

numerically simulated CRPs. We thereby confirm attacks on the

two above PUFs for up to 16 XORs and challenge bitlengths

of up to 512. Secondly, we execute a full experimental proof-ofconcept

for our timing side channel, successfully attacking FPGA implementations of the two above PUF types for 8, 12, and 16

XORs, and bitlengths 64, 128, 256 and 512. We implement these

sizes for the first time in the literature in silicon, and subsequently attack them successfully by our new methods. We remark that in recent works (CCS 2010, IEEE T-IFS 2013), 8 XOR architectures

with bitlength 512 had been explicitly suggested as secure and

beyond the reach of current attacks.

Finally, we discuss efficient countermeasures against our power

and timing side channels. They could and should be used to secure

future Arbiter PUF generations against the latter.