Paper 2017/891

Finding Bugs in Cryptographic Hash Function Implementations

Nicky Mouha, Mohammad S Raunak, D. Richard Kuhn, and Raghu Kacker

Abstract

Cryptographic hash functions are security-critical algorithms with many practical applications, notably in digital signatures. Developing an approach to test them can be particularly difficult, and bugs can remain unnoticed for many years. We revisit the NIST hash function competition, which was used to develop the SHA-3 standard, and apply a new testing strategy to all available reference implementations. Motivated by the cryptographic properties that a hash function should satisfy, we develop four tests. The Bit-Contribution Test checks if changes in the message affect the hash value, and the Bit-Exclusion Test checks that changes beyond the last message bit leave the hash value unchanged. We develop the Update Test to verify that messages are processed correctly in chunks, and then use combinatorial testing methods to reduce the test set size by several orders of magnitude while retaining the same fault-detection capability. Our tests detect bugs in 41 of the 86 reference implementations submitted to the SHA-3 competition, including the rediscovery of a bug in all submitted implementations of the SHA-3 finalist BLAKE. This bug remained undiscovered for seven years, and is particularly serious because it provides a simple strategy to modify the message without changing the hash value returned by the implementation. We detect these bugs using a fully-automated testing approach.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
Cryptographic AlgorithmCryptographic Hash FunctionCombinatorial TestingMetamorphic TestingSHA-3 Competition
Contact author(s)
nicky @ mouha be
History
2018-05-04: revised
2017-09-17: received
See all versions
Short URL
https://ia.cr/2017/891
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/891,
      author = {Nicky Mouha and Mohammad S Raunak and D.  Richard Kuhn and Raghu Kacker},
      title = {Finding Bugs in Cryptographic Hash Function Implementations},
      howpublished = {Cryptology ePrint Archive, Paper 2017/891},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/891}},
      url = {https://eprint.iacr.org/2017/891}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.