Physical Unclonable Functions (PUFs) have established themselves
in the scientific literature, and are also gaining ground
in commercial applications. Recently, however, several attacks
on PUF core properties have been reported. They concern
their physical and digital unclonability, as well as their
assumed resilience against invasive or side channel attacks.
In this paper, we join some of these techniques in order
to further improve their effectiveness. The combination of
machine-learning based modeling techniques with side channel
information allows us to attack so-called XOR Arbiter
PUFs and Lightweight PUFs up to a size and complexity
that was previously out of reach. For Lightweight PUFs,
for example, we report successful attacks for bitlengths of
64, 128 and 256, and for up to nine single Arbiter PUFs
whose output is XORed. Previous work at CCS 2010 and
IEEE TIFS 2013, which provides the currently most efficient
modeling results, had only been able to attack this structure
for up to five XORs and bitlength 64.
Our attack employs the first power side channel (PSC) for
Strong PUFs in the literature. This PSC tells the attacker
the number of single Arbiter PUF within an XOR Arbiter
PUF or Lightweight PUF architecture that are zero or one.
This PSC is of little value if taken by itself, but strongly
improves an attacker\'s capacity if suitably combined with
modeling techniques. At the end of the paper, we discuss efficient
and simple countermeasures against this PSC, which
could be used to secure future PUF generations.