Why PKCS#1v1.5 Signature Should (Also) Be Put Out of Our Misery

Graham Steel
August 8, 2016

In 2014 I wrote a piece for this blog on RSA PKCS#1v1.5 encryption and why we need to get rid of it. At the time, the list of algorithms and padding modes to be included in the W3C WebCrypto API was under discussion, and I wanted to argue for the exclusion of this mode from the API. In the end it was indeed left out.

However, there is a RSA PKCS#1v1.5 signature mode that is present in almost every widely-used crypto API. This mode has long been regarded sniffily by cryptographers, particularly since Daniel Bleichenbacher demonstrated a signature forgery attack at the CRYPTO rump session in 2006.

This attack only works in particular circumstances: the key needs to have a low public exponent (i.e. 3) and the verification code has to be lax in the way it parses the complete signature, ignoring some incorrect padding to the right of the hash that gives the attacker the room to get away with some garbage bytes necessary to make the forgery.

Just like for Bleichenbacher's '98 attack on PKCS#1v1.5 encryption, reaction at the time was limited. There was no assignment of this mode to legacy-only use like there was for the encryption mode. This can be understood because at first sight, it seems like the conditions for the attack (the parser bug and the low-exponent keys) are unlikely to be found in practice. However, since then, other variants of the parsing bug have been found. There's a version from GNU TLS where the garbage bytes can be put in the parameters field of the ASN.1 structure giving the hash to use. In 2014, Antoine Delignat-Lavaud found a bug in Mozilla's crypto library (NSS) that allowed garbage bytes to be hidden in the length field of the same structure. In 2015, Filippo Valsorda discovered another variant in the python crypto library, this time allowing the garbage to be hidden in the 0xFF padding string (it seems this bug was also present in NSS). Filippo just ran a training on this attack at DEF CON, which will no doubt result in more instances being discovered in the coming months.

You can try to avoid parsing bugs by instead recreating what the signature should look like, and the comparing it to the one you received, but it seems nobody is doing this. Even though public keys with exponent 3 represent only 0.37% of X.509 certificates found in the wild (Table 1), isn't it time we moved to a more robust signature mode? RSA PSS, which has well-studied security proofs, has been recommended in PKCS#1 since version 2.1 (2003). It will soon replace PKCS#1v1.5 in TLSv1.3. Let's hope that's the start of a trend.