Paper 2018/362

Backdoored Hash Functions: Immunizing HMAC and HKDF

Marc Fischlin, Christian Janson, and Sogol Mazaheri

Abstract

Security of cryptographic schemes is traditionally measured as the inability of resource-constrained adversaries to violate a desired security goal. The security argument usually relies on a sound design of the underlying components. Arguably, one of the most devastating failures of this approach can be observed when considering adversaries such as intelligence agencies that can influence the design, implementation, and standardization of cryptographic primitives. While the most prominent example of cryptographic backdoors is NIST’s Dual_EC_DRBG, believing that such attempts have ended there is naive. Security of many cryptographic tasks, such as digital signatures, pseudorandom generation, and password protection, crucially relies on the security of hash functions. In this work, we consider the question of how backdoors can endanger security of hash functions and, especially, if and how we can thwart such backdoors. We particularly focus on immunizing arbitrarily backdoored versions of HMAC (RFC 2104) and the hash-based key derivation function HKDF (RFC 5869), which are widely deployed in critical protocols such as TLS. We give evidence that the weak pseudorandomness property of the compression function in the hash function is in fact robust against backdooring. This positive result allows us to build a backdoor-resistant pseudorandom function, i.e., a variant of HMAC, and we show that HKDF can be immunized against backdoors at little cost. Unfortunately, we also argue that safe-guarding unkeyed hash functions against backdoors is presumably hard.

Note: Proof of Theorem 3.1 was corrected, in particular the construction of the bit encryption scheme, whose correctness could not be amplified with majority vote. Minor other improvements.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. IEEE CSF 2018
DOI
10.1109/CSF.2018.00015
Keywords
hash functionsbackdoorsmalicious hashingkleptographyimmunizationHMACHKDF
Contact author(s)
sogol mazaheri @ cryptoplexity de
History
2018-08-20: last of 2 revisions
2018-04-18: received
See all versions
Short URL
https://ia.cr/2018/362
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/362,
      author = {Marc Fischlin and Christian Janson and Sogol Mazaheri},
      title = {Backdoored Hash Functions: Immunizing HMAC and HKDF},
      howpublished = {Cryptology ePrint Archive, Paper 2018/362},
      year = {2018},
      doi = {10.1109/CSF.2018.00015},
      note = {\url{https://eprint.iacr.org/2018/362}},
      url = {https://eprint.iacr.org/2018/362}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.