Variants of Bleichenbacher’s Low-Exponent Attack on PKCS#1 RSA Signatures

Abstract: We give three variants and improvements of Bleichenbacher’s low-exponent attack from CRYPTO 2006 on PKCS#1 v1.5 RSA signatures. For each of these three variants the fake signature representatives are accepted as valid by a flawed imple-mentation. Our attacks work against much shorter keys as Bleichenbacher’s original attack, i.e. even for usual 1024 bit RSA keys. The first two variants can be used to break a certificate chain for vulnerable im-plementations, if the CA uses a public exponent of 3. Such CA certificates are indeed deployed in many browsers like Mozilla, Opera and Konqueror. The third attack works against the Netscape Security Services only, and requires the public exponent 3 to be present in a site’s certificate, not the CA certificate. Using any of these attack vectors, an active adversary can mount a full man-in-the-middle attack on any SSL connection initiated by a vulnerable client.