Finding Bugs and Features Using Cryptographically-Informed Functional Testing

Giacomo Fenzi; Jan Gilcher; Fernando Virdia

Paper 2024/1122

Finding Bugs and Features Using Cryptographically-Informed Functional Testing

Giacomo Fenzi

, Computational Security Lab, EPFL, Lausanne, Switzerland

Jan Gilcher

, Applied Cryptography Group, ETH Zurich, Zurich, Switzerland

Fernando Virdia

, NOVA LINCS, Universidade NOVA de Lisboa, Caparica, Portugal

Abstract

In 2018, Mouha et al. (IEEE Trans. Reliability, 2018) performed a post-mortem investigation of the correctness of reference implementations submitted to the SHA3 competition run by NIST, finding previously unidentified bugs in a significant portion of them, including two of the five finalists. Their innovative approach allowed them to identify the presence of such bugs in a black-box manner, by searching for counterexamples to expected cryptographic properties of the implementations under test. In this work, we extend their approach to key encapsulation mechanisms (KEMs) and digital signature schemes (DSSs). We perform our tests on multiple versions of the LibOQS collection of post-quantum schemes, to capture implementations at different points of the recent Post-Quantum Cryptography Standardization Process run by NIST. We identify multiple bugs, ranging from software bugs (segmentation faults, memory overflows) to cryptographic bugs, such as ciphertext malleability in KEMs claiming IND-CCA security. We also observe various features of KEMs and DSS that do not contradict any security guarantees, but could appear counter-intuitive.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Keywords: implementation testing metamorphic testing public-key cryptography
Contact author(s): giacomo fenzi @ epfl ch
jan gilcher @ inf ethz ch
f virdia @ fct unl pt
History: 2024-07-10: approved; 2024-07-09: received; See all versions
Short URL: https://ia.cr/2024/1122
License: CC BY-SA

BibTeX

@misc{cryptoeprint:2024/1122,
      author = {Giacomo Fenzi and Jan Gilcher and Fernando Virdia},
      title = {Finding Bugs and Features Using Cryptographically-Informed Functional Testing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1122},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1122}
}