Today Hanno Böck, Juraj Somorovsky and Craig Young announced details of new work testing TLS implementations in the wild for Bleichenbacher’s attack on RSA PKCS#1v1.5 encryption. The short summary is the attack, first made public at CRYPTO ’98, still works on almost 3% of the Alexa top million most visited websites thanks to minor details in the way they implement countermeasures.
Updated March 2018 Our Analyzer software now incorporates all of the Wycheproof cryptographic library tests for Java providers. Find out how it works.
Original Post:
Google recently announced a project to produce tests for cryptographic libraries to detect common weaknesses. Piloted by star cryptographers Daniel Bleichenbacher and Thai Duong, this is an exciting development for us at Cryptosense, and not just because they cite our CRYPTO ’12 paper in their RSA tests. It’s a validation of the prevalence and seriousness of security flaws around crypto use, and the need to detect them, which is exactly our mission at Cryptosense.
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.
Cryptosense Analyzer is now available in SaaS edition. Get a free trial.
