Strong Key Derivation from Noisy Sources

Posted on by

My Ph.D. has been completed and defended.  It is titled Strong Key Derivation from Noisy Sources.  It is largely drawn from three papers Computational Fuzzy Extractors, Reusable Fuzzy Extractors for Low-Entropy Distributions, and When are Fuzzy Extractors Possible?  Those papers are more up-to-date than my Ph.D.  My Ph.D does contain a cohesive summary of the results that can be useful as an introduction.

Robust Keys from Physical Unclonable Functions

Posted on by

Merrielle Spain, Benjamin Fuller, Kyle Ingols, and Robert Cunningham. Robust Keys from Physical Unclonable Functions. IEEE Symposium on Hardware Oriented Security and Trust, 2014.

Abstract

Weak physical unclonable functions (PUFs) can instantiate read-proof hardware tokens (Tuyls et al. 2006, CHES) where benign variation, such as changing temperature, yields a consistent key, but invasive attempts to learn the key destroy it. Previous approaches evaluate security by measuring how much an invasive attack changes the derived key (Pappu et al. 2002, Science). If some attack insufficiently changes the derived key, an expert must redesign the hardware. An unexplored alternative uses software to enhance token response to known physical attacks. Our approach draws on machine learning. We propose a variant of linear discriminant analysis (LDA), called PUF LDA, which reduces noise levels in PUF instances while enhancing changes from known attacks. We compare PUF LDA with standard techniques using an optical coating PUF and the following feature types: raw pixels, fast Fourier transform, short-time Fourier transform, and wavelets. We measure the true positive rate for valid detection at a 0% false positive rate (no mistakes on samples taken after an attack). PUF LDA improves the true positive rate from 50% on average (with a large variance across PUFs) to near 100%. While a well-designed physical process is irreplaceable, PUF LDA enables system designers to improve the PUF reliability-security tradeoff by incorporating attacks without redesigning the hardware token.

Computational Fuzzy Extractors

Posted on by

Benjamin Fuller, Xianrui Meng, and Leonid Reyzin.  Computational Fuzzy Extractors.  Asiacrypt 2013.

Abstract

Fuzzy extractors derive strong keys from noisy sources. Their security is defined information- theoretically, which limits the length of the derived key, sometimes making it too short to be useful. We ask whether it is possible to obtain longer keys by considering computational security, and show the following.

-Negative Result: Noise tolerance in fuzzy extractors is usually achieved using an information reconciliation component called a “secure sketch.” The security of this component, which directly affects the length of the resulting key, is subject to lower bounds from coding theory. We show that, even when defined computationally, secure sketches are still subject to lower bounds from coding theory. Specifically, we consider two computational relaxations of the information-theoretic security requirement of secure sketches, using conditional HILL entropy and unpredictability entropy. For both cases we show that computational secure sketches cannot outperform the best information-theoretic secure sketches in the case of high-entropy Hamming metric sources.

-Positive Result: We show that the negative result can be overcome by analyzing computational fuzzy extractors directly. Namely, we show how to build a computational fuzzy extractor whose output key length equals the entropy of the source (this is impossible in the information-theoretic setting). Our construction is based on the hardness of the Learning with Errors (LWE) problem, and is secure when the noisy source is uniform or symbol-fixing (that is, each dimension is either uniform or fixed). As part of the security proof, we show a result of independent interest, namely that the decision version of LWE is secure even when a small number of dimensions has no error.