A Decade After Bleichenbacher '06, RSA Signature Forgery Still Works

Conference:  BlackHat USA 2019



Lessons learned from implementing open standards in cybersecurity
  • Following specifications faithfully is crucial to avoid vulnerabilities
  • Developers should learn from each other's mistakes when implementing the same standard
  • Robustness depends on context and trade-offs between flexibility and complexity should be considered
  • Disseminating information about vulnerabilities to different developers can enforce community learning
The speaker mentioned that cutting corners when implementing open standards is not cool and can lead to ticking time bombs. They also emphasized the importance of developers learning from each other's mistakes and communicating vulnerabilities to enforce community learning.


In the 2006 CRYPTO rump session, Daniel Bleichenbacher gave a talk on how to exploit some implementation bugs of RSA signature verification for forgery attacks against key pairs with a small public exponent. What made his attack successful was that some implementations failed to enforce necessary verification checks required by the PKCS#1 v1.5 signature scheme. In its original form, the Bleichenbacher '06 attack took advantage of the fact that some implementations do not require the PKCS#1 payload to be right-justified with adequate padding. As a follow-up, Kuehn et al. in 2008 demonstrated new and more efficient variants of Bleichenbacher '06, exploiting different flaws where some middle parts of the PKCS#1 payload were ignored by the signature verifier. Subsequent research by Intel Security in 2014 found that Firefox and Google Chrome (both using Mozilla NSS back then) were susceptible to similar forgery attacks, and Valsorda also found similar issues in Python-RSA in 2016.The legacy of Bleichenbacher '06 however did not stop there - more than a decade after the original attack was reported, we revisit the problem of PKCS#1 v1.5 signature verification and discovered even more flaws in the code used by some popular IPSec software as well as TLS and crypto libraries, enabling new variants of the attack. Besides signature forgery, some flaws can even be abused by attackers to launch DoS on the signature verifier. Our investigation leverages dynamic symbolic execution to systematically analyze the signature verification logic in different implementations. We have released our toolchain and relevant artifacts. This research has resulted in 6 new CVEs (3 high and 3 medium severity) being assigned, and vendors were notified to harden their signature verification code. This briefing will conclude with a discussion on why such flaws happened and how to avoid similar mistakes.



Post a comment

Related work

Conference:  RSA Conference 2021

Conference:  Defcon 31
Authors: Tomer Bar VP of security research @ SafeBreach, Omer Attias Security Researcher @ SafeBreach