Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Finding Bugs in Cryptographic Hash Function Implementations

Published

Author(s)

Nicky W. Mouha, Mohammad Raunak, David R. Kuhn, Raghu N. Kacker

Abstract

Cryptographic hash function implementations can be particularly difficult to test, and bugs can remain unnoticed for a very long time. We revisit the NIST SHA-3 hash function competition, 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 types of tests. The Bit-Contribution Test checks if changes in the message affect the final hash value, and the Bit-Exclusion Test checks that changes beyond the last bit of the message leave the hash value unchanged. We also develop the Metamorphic 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 that is returned by the implementation. We will explain how to easily detect this type of bug, using a simple and fully-automated testing approach.
Citation
IEEE Transactions on Reliability
Volume
67
Issue
3

Keywords

Cryptographic Algorithm, Cryptographic Hash Function, Combinatorial Testing, Metamorphic Testing, SHA-3 Competition

Citation

Mouha, N. , Raunak, M. , Kuhn, D. and Kacker, R. (2018), Finding Bugs in Cryptographic Hash Function Implementations, IEEE Transactions on Reliability, [online], https://doi.org/10.1109/TR.2018.2847247 (Accessed April 21, 2024)
Created July 6, 2018, Updated November 10, 2018