834116 - RSA PKCS#1 v1.5 decryption is not constant time

Status: RESOLVED DUPLICATE of bug 577498

(NSS :: Libraries, defect)

Description

[Ryan Sleevi]

The decryption of PKCS#1 v1.5 formatted blocks in softoken is not performed in constant time. This allows an attacker to distinguish the various error conditions involved and mount a variant of Bleichenbacher's attack.

From RFC 3447, 7.2.2 (RSAES-PKCS1-V1_5-DECRYPT (K, C) )

   Note.  Care shall be taken to ensure that an opponent cannot
   distinguish the different error conditions in Step 3, whether by
   error message or timing.  Otherwise an opponent may be able to obtain
   useful information about the decryption of the ciphertext C, leading
   to a strengthened version of Bleichenbacher's attack [6]; compare to
   Manger's attack [36].

Comment 1

[Ryan Sleevi]

The decode also does not correctly validate that the padding string is at least 8 octets.

Comment 2

[Daniel Veditz [:dveditz]]

Is there enough timing difference to mount this attack remotely? How bad a problem is it for a browser in practice?

Comment 3

[Ryan Sleevi]

I've not investigated how significant the timing distinction is, but it is a clear point that the NSS PKCS#1 v1.5 operation is non-constant-time, so it means it is possible to mount a Bleichenbacher attack.

The existing implementation has the following issues
1) Non-constant comparison of the first two bytes
2) Short-circuits (goto done) if the first two bytes are not correct
3) Non-constant search for the end of the padding string
4) short-circuits if the padding string terminator is not found
5) Non-constant time copy into the caller's buffer

These are all enough to provide enough distinguishers for a Bleichenbacher attack. Whether the difference is enough to observe remotely, I don't know, but when considering other consumers of NSS (including potential Web Crypto), it's enough to be 'an issue'.

This is further exacerbated by the fact that libssl doesn't pre-generate the random key used to defend against TLS-layer Bleichenbacher attacks, which means there are even more distinguishing differences between valid and invalid PKCS#1v1.5 messages. See http://mxr.mozilla.org/security/source/security/nss/lib/ssl/ssl3con.c?mark=7935-7936,7943-7948#7929

Note that this results in the acquisition of several mutexes and non-constant-time operations, which may make it even more practical to mount an attack against NSS servers.

Comment 4

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

See also bug 577498, especially comment 9.