Cryptology ePrint Archive: Report 2017/493

Robust Fuzzy Extractors and Helper Data Manipulation Attacks Revisited: Theory vs Practice

Georg T. Becker

Abstract: Fuzzy extractors have been proposed in 2004 by Dodis et al. as a secure way to generate cryptographic keys from noisy sources. In recent years, fuzzy extractors have become an important building block in hardware security due to their use in secure key generation based on Physical Unclonable Functions (PUFs). Fuzzy extractors are provably secure against passive attackers. A year later Boyen et al. introduced robust fuzzy extractors which are also provably secure against active attackers, i.e., attackers that can manipulate the helper data. In this paper we show that the original provable secure robust fuzzy extractor construction by Boyen et al. actually does not fulfill the error-correction requirements for practical PUF applications. The fuzzy extractors proposed for PUF-based key generation on the other hand that fulfill the error-correction requirements cannot be extended to such robust fuzzy extractors, due to a strict bound $t$ on the number of correctable errors. While it is therefore tempting to simply ignore this strict bound, we present novel helper data manipulation attacks on fuzzy extractors that also work if a ``robust fuzzy extractor-like'' construction without this strict bound is used.

Hence, this paper can be seen as a call for action to revisit this seemingly solved problem of building robust fuzzy extractors. The new focus should be on building more efficient solutions in terms of error-correction capability, even if this might come at the costs of a proof in a weaker security model.

Category / Keywords: Fuzzy Extractor, Physical Unclonable Functions (PUFs), Helper Data Manipulation Attacks

Original Publication (with minor differences): IEEE Transactions on Dependable and Secure Computing

Date: received 31 May 2017, last revised 16 Oct 2017

Contact author: georg becker at ruhr-uni-bochum de

Available format(s): PDF | BibTeX Citation

Note: Minor revision, mainly editorial (Final version for TDSC)

Version: 20171016:084229 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]