Hard-to-Find Bugs in Public-Key Cryptographic Software: Classification and Test Methodologies

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.