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 testingmetamorphic testingpublic-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
Creative Commons Attribution-ShareAlike
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},
      note = {\url{https://eprint.iacr.org/2024/1122}},
      url = {https://eprint.iacr.org/2024/1122}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.