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.