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

, University of Surrey, Guildford, United Kingdom

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 of 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 DSSs that do not contradict any security guarantees but could appear counter-intuitive. Finally, we compare this methodology with a traditional fuzzing campaign against LibOQS and SUPERCOP, observing that traditional fuzzing harnesses appear less effective in surfacing software and logical bugs.

Note: Full version of the paper.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Published by the IACR in TCHES 2026
Keywords: cryptographic implementation testing metamorphic testing implementation correctness
Contact author(s): giacomo fenzi @ epfl ch
jan gilcher @ inf ethz ch
f virdia @ surrey ac uk
History: 2025-10-14: revised; 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}
}