Cryptography
RSA in Practice
RSA has been deployed for 47 years, and attackers have had just as long to find weaknesses. Bleichenbacher's 1998 attack on PKCS#1 v1.5 was rediscovered in 2017 as ROBOT, affecting 27 of the top 100 HTTPS sites. Hastad's broadcast attack exploits mathematically correct RSA with wrong parameters. The math is secure; the implementations are not.
- **ROBOT attack (2017)**: Bleichenbacher's 1998 PKCS#1 v1.5 oracle attack rediscovered against Facebook, PayPal, and Cisco hardware. 27 of top-100 HTTPS sites vulnerable.
- **TLS 1.3**: mandates RSA-PSS for signatures, eliminates PKCS#1 v1.5 from the handshake entirely.
- **FIPS 186-5 (2023)**: prohibits RSA key generation with d smaller than certain bounds; mandates PSS for signatures.
- **Coppersmith attacks**: Sage library implementations recover RSA private keys when implementation leaks partial information about d or p.
OAEP: Secure RSA Padding
Textbook RSA is deterministic and malleable. OAEP (Optimal Asymmetric Encryption Padding, PKCS#1 v2) adds randomness using a hash-based Feistel structure, making RSA encryption semantically secure (IND-CCA2).
PKCS#1 v1.5 encryption is vulnerable to Bleichenbacher's padding oracle attack (1998): an attacker who can query whether a ciphertext has valid padding can decrypt arbitrary ciphertexts in ~1 million queries. This broke SSL 2.0 and is still exploitable in legacy systems (ROBOT attack, 2017).
Why is PKCS#1 v1.5 encryption deprecated in favor of OAEP?
RSA-PSS: Probabilistic Signature Scheme
RSA-PSS (Probabilistic Signature Scheme) adds randomness to RSA signing via a salt. PKCS#1 v1.5 signatures are deterministic and have known malleability. PSS provides a security proof in the random oracle model, making it the recommended RSA signature scheme.
RSA-PSS is mandated by FIPS 186-5 (2023) for all new RSA signatures. TLS 1.3 uses RSA-PSS (not PKCS#1 v1.5) for certificate signatures. The salt_length=MAX_LENGTH setting maximizes security margin.
What property does RSA-PSS provide that PKCS#1 v1.5 signatures lack?
Small Exponent Attack
If the same message M is encrypted to three recipients using e=3 with different moduli n1,n2,n3, an attacker can use the Chinese Remainder Theorem to recover M^3 over the integers, then take the integer cube root to get M. This is Hastad's broadcast attack.
e=3 is dangerous without OAEP padding and prohibited by modern standards. e=65537 mitigates small-exponent attacks. OAEP randomizes M, making CRT-based attacks infeasible regardless of e.
Why does Hastad's broadcast attack fail when RSA uses OAEP padding?
Wiener's Attack: Small d
If the RSA private exponent d is too small (d < n^0.25/3), Wiener's attack recovers d using continued fraction expansion of e/n. This limits safe private exponent size and explains why generating RSA keys with artificially small d is dangerous.
CRT decryption uses dp=d mod (p-1) and dq=d mod (q-1) as optimized private key components. Both must be large to prevent attacks: dp < p^0.5 or dq < q^0.5 are vulnerable to extensions of Wiener's attack.
What is the condition under which Wiener's attack recovers the RSA private key?
Key Ideas
- **OAEP**: randomized RSA encryption via Feistel structure. Mandatory for new systems. PKCS#1 v1.5 is deprecated (ROBOT attack).
- **RSA-PSS**: randomized signatures with security proof. Mandated by FIPS 186-5 and TLS 1.3.
- **Small e attacks**: Hastad's broadcast attack recovers M when e=3 and same message sent to 3+ recipients without OAEP.
- **Wiener's attack**: recovers d when d < n^0.25/3 using continued fractions. Standard key generation produces safe d automatically.
Related Topics
RSA attacks connect mathematical theory to real-world vulnerabilities:
- RSA Mathematics — Key generation and correctness proof underpinning these practical attacks.
- Security Models (CPA/CCA) — OAEP achieves IND-CCA2 security; PKCS#1 v1.5 fails IND-CCA2 due to the padding oracle.
- Asymmetric Attacks — Lattice attacks, Coppersmith, and algebraic attacks on RSA explored in depth.
Вопросы для размышления
- The ROBOT attack exploited PKCS#1 v1.5 in production TLS in 2017, 19 years after Bleichenbacher's paper. Why did so many implementations remain vulnerable?
- Why does OAEP add a random salt at the start of encryption rather than at the end?
- A developer wants 'fast RSA decryption' and generates keys with small d. What is the maximum safe d for a 2048-bit RSA key?