Marten van Dijk
Consultant, Inventor, Researcher, Applied Mathematician, & Computer Scientist
Physical Unclonable Functions:
A physical unclonable function (PUF) is a function that is indistinguishable from a random function and
that can only be evaluated with the help of a specific physical system. We call the inputs to a PUF
challenges, and the outputs responses.
We introduced Silicon PUFs in [1,2,3,4,5]. In this case, the response is related to the time it takes for
signals to propagate through a complex circuit. The challenge is an input to the circuit that reconfigures
the path that signals follow through the circuit. One difficulty with Silicon PUFs is that their output is
noisy. Therefore, error-correction which does not compromise the security is required to make them
noise-free [6]. Silicon PUFs can be realized on standard CMOS technology, potentially making them more
attractive than EPROM for identification of integrated circuits.
The canonical application for PUFs is to use them as keycards. In this application, a lock is initially
introduced to a PUF, and stores a database of challenge-response pairs (CRPs) corresponding to that PUF.
Later, when the bearer of the PUF wants to open the lock, the lock selects one of the challenges it knows
and asks the PUF for the corresponding response. If the response matches the stored response, the lock
opens. In this protocol, CRPs can be used only once, so the lock eventually runs out of CRPs. This enables
a denial of service attack in which an adversary uses up all the lock's CRPs by repeatedly presenting it
with an incorrect PUF. Because of this limitation, the keycard application isn't very compelling.
Nevertheless, it is all that can be done with a PUF until we make it into a Controlled PUF. CPUFs have
been introduced in [7,8].
A Controlled PUF (CPUF) is a PUF that has been bound with an algorithm in such a way that it can only be
accessed through a specific application programming interface (API). The API through which the PUF is
accessed should prevent man-in-the-middle attacks without imposing unnecessary limitations on
applications; [9,10] describes a simple but very general API for limiting access to a PUF. It is possible
for a certificate to be produced that proves to the user of a specific CPUF that a specific computation
was carried out on this CPUF, and that the computation produced a given result. It is also possible to
create a proof of execution (e-proof) which is efficiently and securely verifiable by any third party
(not only by the user) [10,11,12].
The startup company Verayo (2005, http://www.verayo.com/) offers a commercialized version of
physical unclonable functions as a solution for radio frequency identification (RFID). The startup company
Intrinsic-ID (2008, http://www.intrinsic-id.com/) uses physical unclonable functions to generate
device-unique IDs and keys.
[1] B. Gassend, D. Clarke, M. van Dijk, and S. Devadas, Silicon physical random functions,
Proceedings of the 9th ACM Conference on Computer and Communications Security (CCS'02),
November 2002.
[2] B. Gassend, D. Clarke, M. van Dijk, and S. Devadas, Delay-based circuit authentication and applications,
Proceedings of the 2003 ACM Symposium on Applied Computing (SAC'03), 294-301, 2003.
[3] B. Gassend, D. Lim, D. Clarke, M. van Dijk, and S. Devadas, Identification and authentication of integrated
circuits, Concurrency and Computation: Practice and Experience 16(11), p. 1077-1098, 2004.
[4] J.W. Lee, D. Lim, B. Gassend, G.E. Suh, M. van Dijk, and S. Devadas, A technique to build a secret key in
integrated circuits for identification and authentication applications, 2004 Symposium on VLSI Circuits,
p. 176-179, 2004.
[5] D. Lim, J.W. Lee, B. Gassend, G.E. Suh, M. van Dijk, and S. Devadas, Extracting secret keys from
integrated circuits, IEEE Trans. VLSI Syst. 13(10), p. 1200-1205, 2005.
[6] M.E. van Dijk, System and method of reliable forward secret key sharing with physical random
functions, US 2008/0044027, 2008.
[7] B. Gassend, D. Clarke, M. van Dijk, and S. Devadas, Controlled Physical Random Functions,
Proceedings of the 18th Annual Computer Security Applications Conference (ACSAC'02),
best student paper award, 149-160, December 2002.
[8] S. Devadas, B. Gassend, M. van Dijk, and D. Clarke, Controlling access to device-specific
information, US 2007/0183194, 2007.
[9] B. Gassend, M. van Dijk, D. Clarke, and S. Devadas. Controlled physical random functions.
Chapter 14 in "Security with Noisy Data: On Private Biometrics, Secure Key Storage and Anti-
Counterfeiting", eds. P. Tuyls, B. Skoric, and T. Kevenaar, Springer, 235-254, 2007.
[10] B. Gassend, M. van Dijk, D. Clarke, E. Torlak, S. Devadas, and P. Tuyls, Controlled physical random
functions and applications,
ACM Transactions on Information and System Security (TISSEC) 10(4), p. 15:1-15:22, 2008.
[11] M.E. van Dijk and P.T. Tuyls, Proof of execution using random function, US 2007/0039046, 2007.
[12] M.E. van Dijk, Sharing a secret by using random function, US 2008/0059809, 2008.
© 2009 Marten van Dijk .
All rights reserved.