Abstract Details

<< Back to Schedule

9/26/2017  |   10:25 AM - 11:10 AM   |  Track 5 - Test and Verification

Finding Bugs in Cryptographic Hash Function Implementations

Cryptographic algorithms are usually complex, so their implementations often include bugs. Traditional test selection strategies utilizing source code coverage information may not be effective in discovering certain types of bugs related to low-level bit manipulations, which are very common in cryptographic hash function implementations. In this project, we show that implementations of cryptographic hash functions can be effectively tested through systematic selection of test cases. We present an approach combining ideas from specification-based testing, metamorphic testing, and combinatorial testing. We applied our approach over all reference implementations that were submitted to the SHA-3 competition of the National Institute of Standard and Technology (NIST). Out of the 64 submissions to the competitions, 51 were selected for the first round analysis. Over a period of five years, these submitted algorithms and implementations were analyzed in multiple rounds. 14 of the 51 submissions made it to the second round, five of which were chosen for the third and final round. At the end of the process, the algorithm Keccak was selected as the winner, and subsequently became the SHA-3 standard. Between the rounds, the submitters were able to update their submissions. We took all submissions and their updates from the NIST site, a total of 86 implementations, and ran our tests on them. Through the selection of test cases that specifically target potential vulnerabilities in the implementations, we discovered a large number of bugs, many of which have never been discovered before or remained hidden for years. We designed four sets of test cases, two of which were a simple variation of the other, to investigate the effectiveness of the combinatorial approach in discovering bugs. Our test suite looking for collisions identified 19 collision errors out of 86 implementations. We also found 32 implementations that failed to meet an important specification required by the submission. 17 implementations revealed bugs related to improper handling of messages whose bit-lengths were not multiples of a byte. We should note that none of these 65 different bugs were discovered by the test vectors that were designed by NIST for this competition. Ensuring the correctness of cryptographic algorithm implementations is of crucial importance to the security of information systems. To accomplish this goal for NIST-recommended cryptographic algorithms, the NIST Cryptographic Algorithm Validation Program (CAVP) has been established. As the strategy to test the NIST SHA-3 competition submissions was borrowed from the CAVP, our findings suggest several areas of improvement for the testing strategy of the standardized cryptographic algorithms in the CAVP. Our approach provides insights into how to design highly-effective test suites for testing cryptographic algorithms, and to significantly reduce the number of required test cases without sacrificing their fault-finding effectiveness.

Presentation:
This presentation has not yet been uploaded.

Handouts:
No handouts have been uploaded.

M Raunak (Primary Presenter), Loyola University Maryland, raunak@loyola.edu;
Dr. Mohammad Raunak is an Associate Professor of computer science at Loyola University Maryland, Baltimore, MD. He earned his M.S. and Ph.D. from University of Massachusetts Amherst under the supervision of Prof. Lee Osterweil, a pioneer in software process research. Dr. Raunak's research area is software engineering, specifically, verification and validation of software systems. His research interest includes developing and measuring test approaches for 'difficult-to-test' programs such as cryptographic functions, simulation model validation, as well as software and other human-centric process modeling and analysis. He regularly teaches software engineering and software testing at Loyola. During his recent sabbatical in 2016-17, Dr. Raunak worked as a guest researcher in the computer security division of National Institute of Standards and Technology.

Nicky Mouha (Co-Presenter), National Institute of Standards and Technology, nicky@mouha.be;
Dr. Nicky Mouha is a researcher at the Computer Security Division of the Information Technology Laboratory at NIST, United States, and an Associate Member at the CASCADE team of ENS, France. At NIST, he works on the standardization of lightweight cryptography. Previously, he was a Postdoctoral Researcher at the SECRET project-team of Inria of Paris, France, and an FWO Postdoctoral Researcher at the COSIC research group of KU Leuven, Belgium.