Abstract Details

<< Back to Schedule

9/27/2017  |   2:00 PM - 2:45 PM   |  

Combinatorial Coverage Measurement of Test Vectors used in Cryptographic Algorithm Validation

The Cryptographic Algorithm Validation Program (CAVP) [1], [2] is a joint American-Canadian security accreditation program, providing guidelines for validation testing of NIST recommended cryptographic algorithms. Validation tests include: Known Answer Tests (KAT), designed to verify the components of algorithms (S-boxes, permutation tables, etc); Multi-block Message Test (MMT), that test the ability of the implementation to process multi-block messages, which may require chaining of information from one block to the next; and Monte Carlo Tests (MCT), to identify flaws in the implementation under test (IUT) that were not detected with the controlled input of KATs. NIST [3], in collaboration with the industry and academia, is investigating changes to the CAVP program to improve test efficiency and quality. While fault detection is clearly a desirable goal for test suites, it is also essential to provide measures of testing completeness. To date, the only widely accepted approaches to ensuring thorough testing have involved structural code coverage metrics, as used for example in testing life-critical aviation software. However, if source code is not available, structural coverage metrics are not applicable. Rigorous quantitative measures of test completeness are needed that can be applied in the absence of source code for the IUT. To address the need for such measures, NIST has developed methods and tools for measuring the completeness of a test suite with respect to combinatorial coverage [4].   Determining the level of input or configuration state-space coverage can thus help in understanding the degree of risk that remains after testing. If a high level of coverage of state-space variable combinations has been achieved (e.g. 90% - 100%), for up to 5-way or 6-way combinations, then presumably the risk is small, but if coverage is much lower, then the residual risk may be substantial. We measure the combinatorial coverage of various CAVP test vectors, including the AES KAT Vectors, AES MCT Sample Vectors, AES MCT Intermediate Values, AES MMT Sample Vectors, and the CCM, CMAC, GCM, GMAC, XPN, and Key Wrap block cipher modes. Our coverage measurement reveals 2-way to 4-way interactions that are not being tested thoroughly, so we generate the missing 2-way combinations for the AES test vectors and extend the current AES test suites to provide pairwise coverage. We use the extended test suites for differential testing on the AES implementations OpenSSL, LibreSSL, Crypto++, and PyCrypto to compare their implementation of the requirements in the standard. Our differential testing showed no discrepancies between the implementations, and the implementations produced the same results for the test inputs. Finally, we use the NIST Cryptographic Algorithm Validation System (CAVS) as a reference system against which the AES implementations are tested. Testing with this model revealed that the OpenSSL and LibreSSL command line tool’s AES-128-CFB1, AES-192-CFB1, and AES-256-CFB1 block ciphers do not produce the results found in the AES test suites, demonstrating the potential for using combinatorial coverage measurement to improve the official test suites.

This presentation has not yet been uploaded.

No handouts have been uploaded.

Dimitris Simos (Primary Presenter), SBA Research, dsimos@sba-research.org;
is key researcher at SBA Research working on mathematical aspects of information security and an adjunct lecturer at TU Wien. He is currently leading the combinatorial security testing research team of SBA Research.

Rick Kuhn (), NIST, d.kuhn@nist.gov;
Rick Kuhn is a computer scientist in the Computer Security Division of the National  Institute of Standards and Technology. He has authored two books and more than 150 papers on information security, empirical studies of software failure, and combinatorial methods in software testing, and is a senior member of the Institute of Electrical and Electronics Engineers (IEEE). 

2017 Sponsors: IEEE and IEEE Computer Society