Cryptography in the research: broken algorithms, leaky implementations, and the quantum threat

Modern cryptography has a reputation for being nearly unbreakable: AES-128 has never been broken in practice, and factoring a 2048-bit RSA modulus is still beyond any computer. Yet the last three decades are full of cryptographic systems that failed. The pattern is consistent: what breaks is almost never the core math, but algorithms kept in service too long, protocols that leak a little at a time, careless implementations, and developers using APIs the wrong way.

This post summarizes what applied cryptography research has found: which attacks have actually been demonstrated, the real incidents that followed, and what it means for developers. It complements the technical notes on Fernet and RSA-PSS in the browser, which show how some of the lessons below look in code.

Broken hash functions: MD5 and SHA-1

A cryptographic hash function is supposed to be collision resistant: it should be practically impossible to find two different inputs with the same hash. Once that property is gone, digital signatures over that hash lose their meaning too.

• Wang, Feng, Lai, and Yu announced MD5 collisions at the CRYPTO 2004 rump session, and Wang and Yu later published the method in How to Break MD5 and Other Hash Functions (EUROCRYPT 2005). Collisions once considered theoretical can now be produced in seconds on a laptop.
• Stevens and colleagues (Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate, CRYPTO 2009) turned collisions into a real attack. Using a cluster of about 200 PlayStation 3 consoles, they created a rogue CA certificate trusted by browsers, because a commercial CA was still signing certificates with MD5.
• The Flame malware (2012) used a variant of the same chosen-prefix attack to forge a Microsoft code-signing certificate, letting it masquerade as a Windows update. It was the first hash-collision attack recorded in the wild, carried out by a nation-state attacker.
• SHAttered (Stevens, Bursztein, Karpman, Albertini, and Markov, CRYPTO 2017) produced two different PDFs with the same SHA-1 hash. It cost about 2⁶³ SHA-1 computations, roughly 6,500 CPU-years and 110 GPU-years.
• Leurent and Peyrin (SHA-1 is a Shambles, USENIX Security 2020) brought the cost of a SHA-1 chosen-prefix collision down to about US$45,000 of rented GPU time, then demonstrated it by impersonating an identity in the PGP web of trust.

The gap between the first theoretical attack on SHA-1 (Wang et al., 2005) and a practical collision was 12 years, and throughout that time SHA-1 remained widely used in TLS certificates, Git, and PGP signatures. NIST has only now set the end of 2030 as the deadline for phasing SHA-1 out completely.

Padding oracles: one leaked bit is enough

The most persistent class of attack in applied cryptography is the oracle: a server that, through its error messages or response times, tells an attacker whether a tampered ciphertext has a valid format. One bit of information per attempt, repeated enough times, is enough to decrypt a message without the key.

• Bleichenbacher (CRYPTO 1998) showed that RSA PKCS#1 v1.5 padding can be broken with about a million modified ciphertexts if the server distinguishes valid from invalid padding. It became known as the million message attack.
• Vaudenay (EUROCRYPT 2002) found the symmetric version for CBC mode: if a server leaks padding validity, each plaintext byte can be guessed in an average of 128 attempts.
• AlFardan and Paterson (Lucky Thirteen, IEEE S&P 2013) showed that a timing difference of a few microseconds while TLS checks padding and the MAC is already enough of an oracle, even when the error messages are identical.
• POODLE (Möller, Duong, and Kotowicz, 2014) exploited CBC padding in SSL 3.0 and was the main reason the protocol was switched off in every browser.
• ROBOT (Böck, Somorovsky, and Young, USENIX Security 2018) found that Bleichenbacher's oracle was still alive 19 years later in many TLS implementations, including devices from major vendors and sites such as Facebook and PayPal.

The lesson shows in modern designs. TLS 1.3 removes RSA key exchange and CBC mode entirely, keeping only authenticated encryption (AEAD) such as AES-GCM and ChaCha20-Poly1305. Formats like Fernet use encrypt-then-MAC: the HMAC is verified first, so a tampered ciphertext is rejected before the padding is ever checked and no oracle can form.

Randomness: the quietest failure point

Almost all cryptography depends on unpredictable random numbers: keys, IVs, nonces, salts. When the randomness source fails, the algorithm still appears to work normally. No errors, no failing tests, just keys that can be guessed.

• Debian OpenSSL (CVE-2008-0166). In 2006 a package maintainer removed two lines of code that a memory analysis tool complained about. As a result, the only entropy left was the process ID, so there were just 32,768 possible keys for each type and size. For nearly two years, SSH keys and TLS certificates generated on Debian and Ubuntu could be guessed from a small list.
• Heninger, Durumeric, Wustrow, and Halderman (Mining Your Ps and Qs, USENIX Security 2012) scanned the entire internet and computed the GCD (greatest common divisor) between pairs of RSA moduli. Embedded devices such as routers, which generate keys right after boot while entropy is still very low, often shared one of their prime factors. The researchers recovered private keys for about 0.5% of TLS hosts. Lenstra and colleagues (Ron was wrong, Whit is right, CRYPTO 2012) found a similar problem independently.
• Sony PlayStation 3 (fail0verflow, 2010). ECDSA signatures require a fresh random nonce for every signature. Sony reused the same value every time, and from just two signatures the firmware signing private key could be computed with simple algebra.
• Bitcoin wallets on Android (2013). A flaw in Android's SecureRandom made some wallet apps repeat ECDSA nonces, and funds at the affected addresses were stolen the same way as in the PS3 case.
• Breitner and Heninger (Biased Nonce Sense, Financial Cryptography 2019) showed that nonces don't have to repeat to be dangerous. Nonces that are only slightly biased, for example with a few top bits always zero, were enough to recover hundreds of private keys from the Bitcoin and Ethereum blockchains using lattice attacks.

Side channels: it's not the data that leaks, it's the behavior

An algorithm that is mathematically correct can still leak its key through execution time, power consumption, or memory access patterns.

• Kocher (CRYPTO 1996) introduced the timing attack: RSA and Diffie-Hellman operations whose duration depends on key bits can be broken just by measuring how long they take. Three years later, Kocher, Jaffe, and Jun (CRYPTO 1999) introduced differential power analysis, which reads keys from the power fluctuations of smart cards.
• Brumley and Boneh (Remote Timing Attacks are Practical, USENIX Security 2003) proved that timing attacks work over a network: they recovered an RSA private key from an OpenSSL server on a local network.
• Bernstein (2005) showed that table-lookup AES implementations leak the key through cache timing, because which table addresses are accessed depends on the key. This is one of the reasons modern processors provide AES-NI instructions.
• TPM-Fail (Moghimi and colleagues, USENIX Security 2020) recovered ECDSA keys from Intel's fTPM and from a Common Criteria–certified STMicroelectronics TPM chip, because signing time depended on the nonce.
• KyberSlash (2024) found timing leaks from division operations in many implementations of Kyber, the post-quantum candidate that became ML-KEM. New algorithms are not automatically immune to old classes of attack.

The answer from this research is constant-time programming: no branches, memory indexes, or variable-time instructions that depend on secret data. For application developers, its simplest form is comparing MACs or tokens with a dedicated function such as Python's hmac.compare_digest() or Node.js's crypto.timingSafeEqual(), not with ==.

Protocols: downgrades, export crypto, and implementation bugs

Most of the big breakages in TLS did not come directly from weak algorithms, but from backward compatibility and the code that handles it.

The Logjam paper (Adrian and colleagues, Imperfect Forward Secrecy, ACM CCS 2015) also estimated that a nation-state attacker could economically afford the precomputation for a few of the most common 1024-bit Diffie-Hellman primes, making much of the VPN and SSH traffic that used them passively decryptable. Export crypto policies repealed decades earlier had still left exploitable code behind.

Dual_EC_DRBG: when the standard itself is the problem

Dual_EC_DRBG is an elliptic-curve random number generator that NIST standardized in SP 800-90 in 2006. A year later, Shumow and Ferguson (CRYPTO 2007 rump session) showed that anyone who knew a secret relationship between the two constant points P and Q in the standard could predict all of the generator's output after seeing a small amount of it. Where those constants came from was never explained.

The Snowden documents in 2013 indicated that the NSA had a hand in pushing the standard, and NIST withdrew it in 2014. Checkoway and colleagues (On the Practical Exploitability of Dual EC in TLS Implementations, USENIX Security 2014) then measured that, with knowledge of the backdoor, TLS sessions from several libraries could be recovered in seconds to hours. In 2015, Juniper discovered that someone had replaced the Q constant in its ScreenOS firmware, handing the backdoor to an unknown party.

This case created the demand for nothing-up-my-sleeve constants: parameters whose origin can be publicly verified, such as the digits of π or the hash of an obvious string. It is also why Curve25519 was designed with every parameter choice documented and explainable.

The biggest problem: developers misusing APIs

When researchers looked at applications instead of libraries, the picture got even bleaker.

• Egele, Brumley, Fratantonio, and Kruegel (An Empirical Study of Cryptographic Misuse in Android Applications, ACM CCS 2013) analyzed 11,748 Android apps that used cryptographic APIs. About 88% made at least one mistake, the most common being ECB mode, which encrypts identical blocks into identical ciphertext so the data's patterns stay visible.
• Lazar, Chen, Wang, and Zeldovich (Why Does Cryptographic Software Fail?, APSys 2014) examined 269 cryptographic vulnerabilities in the CVE database. About 83% were misuse in applications; only 17% came from bugs in the cryptographic libraries themselves.
• Fischer and colleagues (Stack Overflow Considered Harmful?, IEEE S&P 2017) found that about 15% of 1.3 million Android apps contained security-related code copied from Stack Overflow, and almost 98% of those included at least one insecure snippet: a TrustManager that accepts every certificate, hard-coded keys, or ECB mode.
• Acar and colleagues (Comparing the Usability of Cryptographic APIs, IEEE S&P 2017) tested Python developers with several libraries. Participants using simple APIs such as cryptography.fernet produced secure code far more often than those using low-level APIs, although poor documentation remained an obstacle.

The collective conclusion: secure cryptography is an API design problem. Libraries that make developers choose the mode, IV, padding, and MAC order themselves will produce mistakes at scale. Misuse-resistant libraries such as libsodium, Fernet, or Tink deliberately don't offer those choices.

Quantum computers and post-quantum cryptography

The next big threat has been known since 1994. Shor's algorithm (FOCS 1994) factors integers and computes discrete logarithms in polynomial time on a quantum computer, so RSA, Diffie-Hellman, and elliptic-curve cryptography will collapse completely once a large and stable enough quantum computer exists. Grover's algorithm (1996) only gives a quadratic speedup for search, so symmetric cryptography can be kept safe with longer keys, such as AES-256.

No such computer exists yet, but the threat already applies today through harvest now, decrypt later: encrypted traffic recorded now can be decrypted years later. That is why NIST ran a standardization competition starting in 2016, and in August 2024 published the first three standards:

The competition itself was a lesson in humility. SIKE, an isogeny-based candidate that had made it to the fourth round, was broken by Castryck and Decru in 2022 in about an hour on a single ordinary CPU core. Rainbow, a signature finalist, was broken by Beullens (Breaking Rainbow Takes a Weekend on a Laptop, CRYPTO 2022). Two schemes studied for years fell to classical math, with no quantum computer involved at all.

That is why the first deployments are hybrid: session keys are derived from classical X25519 and ML-KEM together, so an attacker has to break both. Signal added PQXDH in 2023, Apple launched PQ3 for iMessage in 2024, and Chrome and other modern browsers now negotiate X25519MLKEM768 in TLS 1.3 by default. The draft NIST IR 8547 targets deprecating RSA and ECC at the 112-bit security level by 2030 and disallowing them by 2035.

What it means for developers

Don't design your own cryptography

Nearly every attack above hit systems built by competent people. Use high-level, audited constructions (libsodium, Fernet, Tink, or your platform's built-in AEAD), and avoid assembling AES, a mode, padding, and a MAC yourself unless you have a very strong reason.

Pick the right algorithm for the job

Reject unauthenticated messages before processing them

Verify the MAC or AEAD tag first, use a constant-time comparison, and return the same single error for every decryption failure. That closes most doors to padding oracles.

Plan for crypto agility

SHA-1 took more than a decade to retire because it was baked into file formats, protocols, and databases. Store the algorithm identifier or format version alongside the data (like the 0x80 version byte in a Fernet token), don't hard-wire a single algorithm forever, and inventory where RSA and ECC are used so the post-quantum migration doesn't start from scratch.

Conclusion

Three decades of applied cryptography research send a consistent message. Modern primitives such as AES, SHA-256, and Curve25519 remain solid; what fails again and again is everything around them. Hashes stay in use years after the first warnings, protocols leak one bit in every error message, randomness fails silently, execution time leaks keys, standards can be subverted, and developers often use APIs the wrong way. At the same time, the same research gave us TLS 1.3, AEAD, misuse-resistant libraries, and post-quantum standards that are now being widely deployed. For developers, the lesson is simple: use high-level libraries, follow current recommendations, and design systems so their algorithms can be replaced before they fall.

References

• Shor, P. W. (1994). Algorithms for Quantum Computation: Discrete Logarithms and Factoring. IEEE FOCS.
• Kocher, P. (1996). Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. CRYPTO.
• Bleichenbacher, D. (1998). Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1. CRYPTO.
• Kocher, P., Jaffe, J., & Jun, B. (1999). Differential Power Analysis. CRYPTO.
• Vaudenay, S. (2002). Security Flaws Induced by CBC Padding: Applications to SSL, IPSEC, WTLS. EUROCRYPT.
• Brumley, D., & Boneh, D. (2003). Remote Timing Attacks are Practical. USENIX Security Symposium.
• Wang, X., & Yu, H. (2005). How to Break MD5 and Other Hash Functions. EUROCRYPT.
• Bernstein, D. J. (2005). Cache-timing attacks on AES.
• Debian Security Advisory (2008). DSA-1571-1 openssl: predictable random number generator.
• Stevens, M., et al. (2009). Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate. CRYPTO.
• Heninger, N., Durumeric, Z., Wustrow, E., & Halderman, J. A. (2012). Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices. USENIX Security Symposium.
• Lenstra, A. K., et al. (2012). Ron was wrong, Whit is right. CRYPTO.
• AlFardan, N. J., & Paterson, K. G. (2013). Lucky Thirteen: Breaking the TLS and DTLS Record Protocols. IEEE Symposium on Security and Privacy.
• Egele, M., Brumley, D., Fratantonio, Y., & Kruegel, C. (2013). An Empirical Study of Cryptographic Misuse in Android Applications. ACM CCS.
• Checkoway, S., et al. (2014). On the Practical Exploitability of Dual EC in TLS Implementations. USENIX Security Symposium.
• Lazar, D., Chen, H., Wang, X., & Zeldovich, N. (2014). Why Does Cryptographic Software Fail? A Case Study and Open Problems. APSys.
• Möller, B., Duong, T., & Kotowicz, K. (2014). This POODLE Bites: Exploiting the SSL 3.0 Fallback.
• Adrian, D., et al. (2015). Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. ACM CCS.
• Aviram, N., et al. (2016). DROWN: Breaking TLS Using SSLv2. USENIX Security Symposium.
• Stevens, M., Bursztein, E., Karpman, P., Albertini, A., & Markov, Y. (2017). The First Collision for Full SHA-1. CRYPTO.
• Fischer, F., et al. (2017). Stack Overflow Considered Harmful? The Impact of Copy&Paste on Android Application Security. IEEE Symposium on Security and Privacy.
• Acar, Y., et al. (2017). Comparing the Usability of Cryptographic APIs. IEEE Symposium on Security and Privacy.
• Böck, H., Somorovsky, J., & Young, C. (2018). Return Of Bleichenbacher's Oracle Threat (ROBOT). USENIX Security Symposium.
• Breitner, J., & Heninger, N. (2019). Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies. Financial Cryptography.
• Leurent, G., & Peyrin, T. (2020). SHA-1 is a Shambles. USENIX Security Symposium.
• Moghimi, D., Sunar, B., Eisenbarth, T., & Heninger, N. (2020). TPM-Fail: TPM meets Timing and Lattice Attacks. USENIX Security Symposium.
• Castryck, W., & Decru, T. (2022). An efficient key recovery attack on SIDH.
• Beullens, W. (2022). Breaking Rainbow Takes a Weekend on a Laptop. CRYPTO.
• NIST (2024). FIPS 203, 204, and 205: the first post-quantum cryptography standards.
• Bernstein, D. J., et al. (2024). KyberSlash: Exploiting secret-dependent division timings in Kyber implementations.
• NIST (2024). IR 8547 (draft): Transition to Post-Quantum Cryptography Standards.