Entropy Estimation of Physically Unclonable Functions
Physically unclonable functions (PUFs) are gaining attention as a promising cryptographic technique; the main applications using PUFs include challenge-response authentication and key generation (key storage). When a PUF is applied to these applications, min-entropy estimation is essential. Min-entropy is a measure of the lower bound of the unpredictability of PUF responses. A prominent scheme for estimating min-entropy is the National Institute of Standards and Technology (NIST) specification (SP) 800-90B. It includes several statistical tests and ten kinds of estimators aimed at estimating the min-entropy of random number generators (RNGs). Several studies have estimated the min-entropy of PUFs as well as those of RNGs by using SP 800-90B. In this paper, we point out two problems in this scheme to estimate the min-entropy of PUFs. One is that the estimation results vary widely by the ordering of the PUF responses. The other is that the entropy estimation suite of SP 800-90B can overestimate PUF min-entropy. Both problems are related to the cause of lower entropy due to variations in the manufacturing of circuits and transistors (except for the PUF sources, which are circuits and transistors used to extract intrinsic physical properties and to generate device unique responses), named “multiple sources” [1]. We call these circuits and transistors “entropy-loss sources” in contrast to the PUF sources. We applied three orderings to the PUF responses of our static random-access memory (SRAM) PUF and our complementary metaloxide-semiconductor (CMOS) image sensor with a PUF (CIS PUF): row-direction ordering, column-direction ordering, and random-shuffle ordering. We demonstrated that the estimated min-entropy varies with the ordering. In particular, we found that arranging the PUF responses in readout order results in the overestimation of the min-entropy. We used numerical simulation to create numerical PUFs with the entropy-loss source. We demonstrated that the entropy estimation suite overestimates their entropy.