In computing and cryptography, a physical unclonable function or PUF is a physical object whose operation cannot be reproduced ("cloned") in a physical way (by making another system using the same technology), such that for a given input and conditions (challenge), provides a physically defined "digital fingerprint" output (response) that serves as a unique identifier—most often for a semiconductor device such as a microprocessor or a material producing an optical signal. PUFs are often based on unique physical variations occurring naturally during semiconductor manufacturing.
A PUF is a physical entity embodied in a physical structure. PUFs can be implemented in integrated circuits, including FPGAs, and can be used in applications with high-security requirements, more specifically cryptography, Internet of things (IOT) devices and privacy protection. The term is also commonly expanded as a physically unclonable function in the academic literature.
History Early references about systems that exploit the physical properties of disordered systems for authentication purposes date back to Bauder in 1983D.W. Bauder, "An anti-counterfeiting concept for currency systems," Research report PTK-11990. Sandia National Labs. Albuquerque, NM, 1983. and Simmons in 1984.G. Simmons, "A system for verifying user identity and authorization at the point-of-sale or access," Cryptologia, vol. 8, no. 1, pp. 1–21, 1984.G. Simmons, "Identification of data, devices, documents, and individuals," in IEEE International Carnahan Conference on Security Technology, 1991, pp. 197–218. Naccache and Frémanteau provided an authentication scheme in 1992 for memory cards.David Naccache and Patrice Frémanteau, Unforgeable identification device, identification device reader and method of identification, August 1992. PUFs were first formally proposed in a general fashion by Pappu in 2001, under the name physical one-way function (POWF), with the term PUF being coined in 2002,Blaise Gassend, Dwaine Clarke, Marten van Dijk and Srinivas Devadas. Silicon Physical Random Functions. Proceedings of the Computer and Communications Security Conference, November 2002 whilst describing the first integrated PUF where, unlike PUFs based on optics, the measurement circuitry and the PUF are integrated onto the same electrical circuit (and fabricated on silicon).
Starting in 2010, PUF gained attention in the smartcard market as a promising way to provide "silicon fingerprints", creating cryptographic keys that are unique to individual smartcards.
PUFs are now established as a secure alternative to battery-backed storage of secret keys in commercial FPGAs, such as the Xilinx Zynq Ultrascale+,Xilinx Addresses Rigorous Security Demands at Fifth Annual Working Group for Broad Range of Applications and Altera Stratix 10.intrinsic-id.com
Concept PUFs depend on the uniqueness of their physical microstructure. This microstructure depends on random physical factors introduced during manufacturing. These factors are unpredictable and uncontrollable, which makes it virtually impossible to duplicate or clone the structure.
Rather than embodying a single cryptographic key, PUFs implement challenge–response authentication to evaluate this microstructure. When a physical stimulus is applied to the structure, it reacts in an unpredictable (but repeatable) way due to the complex interaction of the stimulus with the physical microstructure of the device. This exact microstructure depends on physical factors introduced during manufacture, which are unpredictable (like a fair coin). The applied stimulus is called the challenge, and the reaction of the PUF is called the response. A specific challenge and its corresponding response together form a challenge-response pair or CRP. The device's identity is established by the properties of the microstructure itself. As this structure is not directly revealed by the challenge-response mechanism, such a device is resistant to spoofing attacks.
Using a fuzzy extractor or the fuzzy commitment scheme that are provably suboptimal in terms of storage and privacy leakage amount or using nested polar codes that can be made asymptotically optimal, one can extract a unique strong cryptographic key from the physical microstructure. The same unique key is reconstructed every time the PUF is evaluated."PUF Technology Overview". The challenge-response mechanism is then implemented using cryptography.
PUFs can be implemented with a very small hardware investment compared to other cryptographic primitives that provide unpredictable input/output behavior, such as pseudo-random functions. In some cases, PUFs can even be built from existing hardware with the right properties.
Unclonability means that each PUF device has a unique and unpredictable way of mapping challenges to responses, even if it was manufactured with the same process as a similar device, and it is infeasible to construct a PUF with the same challenge-response behavior as another given PUF because exact control over the manufacturing process is infeasible. Mathematical unclonability means that it should be very hard to compute an unknown response given the other CRPs or some of the properties of the random components from a PUF. This is because a response is created by a complex interaction of the challenge with many or all of the random components. In other words, given the design of the PUF system, without knowing all of the physical properties of the random components, the CRPs are highly unpredictable. The combination of physical and mathematical unclonability renders a PUF truly unclonable.C. Herder, L. Ren, M. van Dijk, M-D. Yu, and S. Devadas, "Trapdoor Computational Fuzzy Extractors and Cryptographically-Secure Physical Unclonable Functions," IEEE Transactions on Dependable and Secure Computing, January 2017.
Note that a PUF is "unclonable" using the same physical implementation, but once a PUF key is extracted, there's generally no problem with cloning the key – the output of the PUF – using other means. For extensive PUFs, defined later, in some cases one can train a neural network on observed challenge-response pairs and use it to predict unobserved responses - however this can have a limited effect depending on the strength and unpredictability of the PUF.A. Vijayakumar, V. C. Patil, C. B. Prado, and S. Kundu, "Machine learning resistant strong PUF: Possible or a pipe dream?," 2016 IEEE International Symposium on Hardware Oriented Security and Trust (HOST), 2016.
Because of these properties, PUFs can be used as a unique and untamperable device identifier. PUFs can also be used for secure key generation and storage and for a source of randomness.
Classification
Extensive / confined (strong / weak) Strong / weak PUF terms are deprecated, because the term 'Weak PUF' does not properly describe the property of the PUF; ISO/IEC 20897 defines PUF terms as extensive PUF, confined PUF. Confined PUFs can be considered a kind of memory that is randomly initialized during PUF manufacture. A challenge can be considered an address within the memory, and response can be considered the random value stored by that address. This way count of unique challenge-response pairs (CRPs) scales lineary with count of random elements of the PUF. The advantage of such PUFs is that they are actual random oracles, so are immune to machine-learning attacks. The weakness is that count of CRPs is small and can be exhausted either by an adversary, that can probe the PUF directly, or during authentication protocols over insecure channels, in which case verifier has to keep track of challenges already known to adversary. That's why the main application of confined PUFs is the source of randomness for deriving crypto keys. Extensive PUFs are systems doing computation based on their internal structure. Their count of unique CRPs scales faster than linearily with increase in count of random elements because of interactions between the elements. The advantage is that this way space of CRPs can be made large enough to make its exhaustion practically impossible and collisions of 2 randomly chosen elements of the space improbable enough, allowing the verifying party not to keep track of used elements but just to choose them randomly from the space. Another advantage is that the randomness can be stored not only within the elements but also within their interactions, which sometimes can not be read directly. The weakness is that the same elements and their interactions are reused for different challenges, which opens the possibility to derive some information about the elements and their connections and use it to predict the reaction of the system to the unobserved challenges.
Implicit / explicit All implementations of a certain PUF within certain device are created uniformly using scalable processes. For example when a cryptoprocessor based on a silicon chip is produced, a lot of processors are created on the same silicon wafer. Foundry equipment applies the same operations to all the chips on a wafer and tries to do it as much reproducible as possible in order to have predictable and high performance and reliability characteristics within all the chips. Despite this there should be generated randomness to make PUF in each chip unique.
Explicit PUF randomness is created explicitly in a separate technological operation. It is a disadvantage because a separate operation imposes additional costs and because manufacturer can intentionally replace that separate operation with something else, which can reduce randomness and compromise security characteristics. Implicit PUF uses technology imperfections as a source of randomness by designing a PUF as a device which operation is strongly affected by technology imperfections instead of being unaffected, as it is done for usual circuitry, and fabricating it simultaneously with the rest of the device. Since foundries themselves cannot defeat the imperfections of the technology despite having strong economic incentive in being capable to fabricate more performant and more reliable chips, it gives some protection from foundry backdooring such PUFs this way. Backdooring PUFs by tampering with lithographic masks can be detected by reverse engineering the resulting devices. Fabricating the PUF as the part of the rest of the device makes it cheaper than explicit PUFs.
Intrinsic / extrinsic Extrinsic PUFs rely on sensors to measure a system containing the randomness. Such sensors are a weak point since they can be replaced with fakes sending the needed measurements. Intrinsic PUF operation is affected by randomness contained within the system itself.
Types
Over 40 types of PUF have been suggested. These range from PUFs that evaluate an intrinsic element of a pre-existing integrated electronic system to concepts that involve explicitly introducing random particle distributions to the surface of physical objects for authentication. All PUFs are subject to environmental variations such as temperature, supply voltage and electromagnetic interference, which can affect their performance. Therefore, rather than just being random, the real power of a PUF is its ability to be different between devices but simultaneously to be the same under different environmental conditions on the same device.
Fractional Hamming distance (fHD)
The fractional Hamming distance (fHD) is a commonly used metric to quantify the difference between two binary responses. It is defined as:
where A and B are binary arrays representing two responses, a and b are the dimensions of these arrays, and ⊕ denotes the bitwise XOR operation. The summation is carried out over all pixel positions I (1, 2, ..., a) and J (1, 2, ..., b) in the arrays. The result gives a normalized measure of similarity between the two arrays, ranging from 0 (identical) to 1 (completely different).