Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Hard-to-Find Bugs in Public-Key Cryptographic Software: Classification and Test Methodologies
STEINBACH, Matteo; GROSZSCHÄDL, Johann; ROENNE, Peter
2025 • In Karfa, Chandan; Navid, Asadi; Chattopadhyay, Anupam (Eds.) Security, Privacy, and Applied Cryptography Engineering, 15th International Conference, SPACE 2025, Guwahati, India, December 16–19, 2025, Proceedings
[en] Programming bugs and flaws can have fatal consequences for the security of cryptographic software and may allow an attacker to bypass authentication, forge signatures, decrypt sensitive data, or even completely reveal secret keys. Certain categories of bugs, such as subtle carry-propagation flaws in large-integer or prime-field arithmetic carried out by many public-key cryptosystems, manifest only under very specific and, therefore, extremely rare input conditions, which makes them hard to detect with conventional software testing methodologies. While there exist a few papers that describe such Hard-to-Find Bugs (HFBs) and study their security implications, a more comprehensive treatment and systematization are still lacking. The present paper aims to fill this gap and analyzes the challenges posed by HFBs in software implementations of public-key cryptosystems. More concretely, we define and categorize HFBs, provide a survey of HFBs that have been found in widely-used open-source cryptography libraries (some of which remained undetected for up to 10 years), and discuss the benefits and limitations of common testing and prevention techniques, including differential testing, static analysis, fuzzing, formal verification, and Known Answer Tests (KATs) tailored to HFBs. Raising awareness of HFBs is important for software developers and security auditors who implement and test cryptographic algorithms for mission-critical systems where correctness and robustness are paramount. By shedding light on subtle implementation flaws and how to reduce their occurrence, this paper contributes to improving the real-world security of public-key cryptosystems.
Almeida, J.B., Barbosa, M., Barthe, G., et al.: Jasmin: high-assurance and high-speed cryptography. In: 24th ACM Conference on Computer and Communications Security (CCS 2017), pp. 1807–1823. ACM (2017)
Almeida, J.B., Barbosa, M., Barthe, G., et al.: The last mile: high-assurance and high-speed cryptographic implementations. In: 41st IEEE Symposium on Security and Privacy (S &P 2020), pp. 965–982. IEEE (2020)
Aranha, D.F., Novaes, F.R., Takahashi, A., et al.: LadderLeak: breaking ECDSA with less than one bit of nonce leakage. In: 27th ACM Conference on Computer and Communications Security (CCS 2020), pp. 225–242. ACM (2020)
Barthe, G., Grégoire, B., Zanella-Béguelin, S.: Formal certification of code-based cryptographic proofs. In: 36th ACM Symposium on Principles of Programming Languages (POPL 2009), pp. 90–101. ACM (2009)
Bhargavan, K., Blanchet, B., Kobeissi, N.: Verified models and reference implementations for the TLS 1.3 standard candidate. In: 38th IEEE Symposium on Security and Privacy (S &P 2017), pp. 483–502. IEEE (2017)
Blanchet B Degano P Guttman JD Security protocol verification: symbolic and computational models Principles of Security and Trust 2012 Heidelberg Springer 3 29 10.1007/978-3-642-28641-4_2 7215
Blessing, J., Specter, M.A., Weitzner, D.J.: Cryptography in the wild: an empirical analysis of vulnerabilities in cryptographic libraries. In: 19th ACM Asia Conference on Computer and Communications Security (ASIACCS 2024), pp. 605–620. ACM (2024)
Boston B et al. Silva A Leino KRM et al. Verified cryptographic code for everybody Computer Aided Verification 2021 Cham Springer 645 668 10.1007/978-3-030-81685-8_31 12759
Bressana, P., Zilberman, N., Soulé, R.: Finding hard-to-find data plane bugs with a PTA. In: 16th International Conference on emerging Networking EXperiments and Technologies (CoNEXT 2020), pp. 218–231. ACM (2020)
Brumley BB Barbosa M Page D Vercauteren F Dunkelman O Practical realisation and elimination of an ECC-related software bug attack Topics in Cryptology – CT-RSA 2012 2012 Heidelberg Springer 171 186 10.1007/978-3-642-27954-6_11 7178
Chen, Y., Su, Z.: Guided differential testing of certificate validation in SSL/TLS implementations. In: 10th Joint Meeting on Foundations of Software Engineering (ESEC/FSE 2015), pp. 793–804. ACM (2015)
Chudnov A et al. Chockler H Weissenbacher G et al. Continuous formal verification of amazon s2n Computer Aided Verification 2018 Cham Springer 430 446 10.1007/978-3-319-96142-2_26 10982
De Ruiter, J., Poll, E.: Protocol state fuzzing of TLS implementations. In: 24th USENIX Security Symposium (USS 2015), pp. 193–206. USENIX Association (2015)
Fail0verflow. Console hacking 2010: PS3 epic fail. Presentation at the 27th Chaos Communication Congress (27C3) (2010)
Google. OSS-Fuzz: Continuous fuzzing for open source software (2020). https://github.com/google/oss-fuzz
Hax Team. Hax: A Rust verification toolchain for security-critical software (2023). https://github.com/hax-rust/hax
Hwang, V.: Formal verification of emulated floating-point arithmetic in Falcon. In: Advances in Information and Computer Security — IWSEC 2024. Springer (2024)
Jero, S., Pacheco, M.L., Goldwasser, D., Nita-Rotaru, C.: Leveraging textual specifications for grammar-based fuzzing of network protocols. In: 31st Conference on Innovative Applications of Artificial Intelligence (IAAI 2019), pp. 9478–9483. AAAI Press (2019)
Kasak, D.: Rust vs. C: a performance comparison in systems programming. Blog post (2018). https://deniskasak.github.io/rust-vs-c-perf
Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Advances in Cryptology — CRYPTO 1996, pp. 104–113. Springer (1996)
Lazar, D., Chen, H., Wang, X., Zeldovich, N.: Why does cryptographic software fail? A case study and open problems. In: 5th Asia-Pacific Workshop on Systems (APSys 2014), pp. 7:1–7:7. ACM (2014)
Libcrux Team. Libcrux: A formally verified cryptographic library for Rust (2023). https://github.com/cryspen/libcrux
McConnell, S.: Code Complete, 2nd edn. Microsoft Press (2004)
Mouha N Raunak MS Kuhn DR Kacker R Finding bugs in cryptographic hash function implementations IEEE Trans. Reliab. 2018 67 3 870 884 10.1109/TR.2018.2847247
National Security Agency. Software memory safety. Cybersecurity information sheet, NSA (2022). https://media.defense.gov/2022/Nov/10/2003112742/-1/-1/0/CSI_SOFTWARE_MEMORY_SAFETY.PDF
Rukhin, A., Soto, J., Nechvatal, J., et al.: A statistical test suite for random and pseudorandom number generators for cryptographic applications. Special Publication 800-22, National Institute of Standards and Technology (NIST) (2010)
Seaborn, T.: Performance analysis of RustCrypto: AES implementations in Rust vs. C (2019). https://rustcrypto.org/performance
Smith, B.: Ring: Safe, fast, small crypto using Rust (2023). https://briansmith.org/rustdoc/ring/
Steinbach, M.: Wycheproof-C: A C cryptographic test suite (2025). https://github.com/mattc-try/wycheproof-c/
Vranken, G.: Differential fuzzing of cryptographic libraries (2019). https://archive.is/https://guidovranken.com/2019/05/14/differential-fuzzing-of-cryptographic-libraries/
