  We present a practical and highly secure method for the authentication of
chips based on a new concept for implementing strong Physical Unclonable
Function (PUF) on field programmable gate arrays (FPGA). Its qualitatively
novel feature is a remote reconfiguration in which the delay stages of the PUF
are arranged to a random pattern within a subset of the FPGA's gates. Before
the reconfiguration is performed during authentication the PUF simply does not
exist. Hence even if an attacker has the chip under control previously she can
gain no useful information about the PUF. This feature, together with a strict
renunciation of any error correction and challenge selection criteria that
depend on individual properties of the PUF that goes into the field make our
strong PUF construction immune to all machine learning attacks presented in the
literature. More sophisticated attacks on our strong-PUF construction will be
difficult, because they require the attacker to learn or directly measure the
properties of the complete FPGA. A fully functional reference implementation
for a secure "chip biometrics" is presented. We remotely configure ten 64-stage
arbiter PUFs out of 1428 lookup tables within a time of 25 seconds and then
receive one "fingerprint" from each PUF within 1 msec.
