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.