Paper 2014/1023

How to Generate Repeatable Keys Using Physical Unclonable Functions Correcting PUF Errors with Iteratively Broadening and Prioritized Search

Nathan E. Price and Alan T. Sherman

Abstract

We present an algorithm for repeatably generating keys using entropy from a Physical Unclonable Function (PUF). PUFs are logically identical physical constructs with Challenge-Response Pairs (CRPs) unique to each device. Applications include initialization of server keys and encryption of FPGA configuration bitstreams. One problem with PUFs is response errors. Our algorithm corrects PUF errors that inhibit key repeatability. Our approach uses a PUF to generate an error-free PUF value in three steps. First, we repeatedly sample the PUF to determine the most likely value. Second, we apply an iteratively-broadening search to search up to some number of bit errors (in our experiments we use two). Third, we apply exhaustive search until the correct value is found or failure is declared. The searches are prioritized by the known bit error rates in decreasing magnitude. We assume the application includes a test for the correct value (e.g., some matching plaintext-ciphertext pairs). Previous algorithms often omit noisy PUF bits or use error-correcting codes and helper data. Our algorithm can use all PUF bits regardless of noise. Our approach is simple, and for appropriate parameter choices, fast. Unlike previous approaches using error-correcting codes, when used for public-key cryptography our method requires storing only the public key and no other helperdata in non-volatile storage. We implemented a latch-based PUF on FPGAs and measured PUF characteristics to analyze the effectiveness of the algorithm. Tests for a 1024-bit PUF show 351 samples reduce the probability of errors to less than 10^-6. The iterative broadening and exhaustive searches further reduce failure rates.