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. Originally, biometrics were the main motivation for fuzzy extractors but in recent years their practical relevance stems mainly from their use in secure key generation based on Physical Unclonable Functions (PUFs). Fuzzy extractors are provably secure against passive attackers, i.e., attackers that can observe the helper data. A year later, robust fuzzy extractors were introduced which are also provably secure against an active attacker, i.e., attackers that can manipulate the helper data. Hence, the problem of how to build provably secure robust fuzzy extractors appears to have been solved a long time ago.

However, in this paper we show that from a practical perspective the problem of building a provably secure fuzzy extractor is actually not solved yet. The originally proposed robust fuzzy extractors based on BCH codes either do not have the required error-correction rates for practical applications or violate the parameters in the security proof. Since no helper data manipulation attacks on linear codes are known which work in the robust fuzzy extractor construction, it might be tempting to simply ignore the parameters of the proof. However, we present new helper data manipulation attacks on several decoding strategies for linear codes which set a key as opposed to recovering the key. These new attacks show that helper data manipulation attacks are indeed feasible against such constructions if the parameters in the proof are ignored. Robust fuzzy extractors therefore need to be revisited by both engineers and cryptographers to solve the problem of building both provably secure as well as practical robust fuzzy extractors.

Category / Keywords: Fuzzy Extractor, Physical Unclonable Functions, Implementation Attacks

Date: received 31 May 2017

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

Available format(s): PDF | BibTeX Citation

Version: 20170601:035542 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]