1067214 - (CVE-2014-1570) Certificate (and other) RSA PKCS#1 signature verification doesn't enforce a minimum of 8 padding bytes

Status: RESOLVED FIXED

(NSS :: Libraries, defect)

Description

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

+++ This bug was initially created as a clone of Bug #1064636 +++

See http://tools.ietf.org/html/rfc3447#section-8.2.2, in particular:

      EMSA-PKCS1-v1_5 encoding: Apply the EMSA-PKCS1-v1_5 encoding
      operation (Section 9.2) to the message M to produce a second
      encoded message EM' of length k octets:

            EM' = EMSA-PKCS1-V1_5-ENCODE (M, k).

      If the encoding operation outputs "message too long," output
      "message too long" and stop.  If the encoding operation outputs
      "intended encoded message length too short," output "RSA modulus
      too short" and stop.

The description of EMSA-PKCS1-V1_5-ENCODE includes:

  3. If emLen < tLen + 11, output "intended encoded message length too
      short" and stop.

Although this is a very poorly-worded way of stating the requirement, what this is really saying is that a signature with less than 8 bytes of 0xFF padding bytes must be rejected. NSS's implementation enforces this requirement for RSA *decryption*, but *not* for signature verification.

Actually, RSA_CheckSign does do this check:

      if (dataLen > modulusLen - (3 + RSA_BLOCK_MIN_PAD_LEN))
        goto failure;

However, the function that is used for certificate verification and most (all?) other things is RSA_CheckSignRecover, which is missing that check.

The server using the forged certificate linked to in bug 1064636 exploits the fact that this check is missing, in addition to exploiting bug 1064670. Consequently, some other implementations will refuse to connect to the test site, not because they are doing the ASN.1 decoding correctly, but because there isn't enough padding (i.e. they may still be have vulnerabilities similar to bug 1064670, but that particular certificate doesn't work because they don't have *this* vulnerability).

Comment 1

[Daniel Veditz [:dveditz]]

Severity of this on its own is unclear, resetting for now.

Comment 2

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

I'm planning to open this bug report this weekend.

Comment 3

[Daniel Veditz [:dveditz]]

before you do, care to hazard a guess at an appropriate security rating for this issue on its own?

Comment 4

[Daniel Veditz [:dveditz]]

I guess sec-low on its own?

Comment 5

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

The largest hash value we support is SHA-512 bits (64 bytes), and the DigestInfo prefix for that is 19 bytes. There are 3 bytes of overhead (0x00 0x01 .... 0x00) in a PKCS#1 signature. 64 + 19 + 3 = 86 bytes.

The minimum padding size is 8 bytes. 86 + 8 = 92 bytes. 92 bytes * 8 bits per byte = 736 bits. So, as long as the application only accepts RSA PKCS#1 signatures of 736 bits or longer, it will implicitly require at least 8 bytes of padding. According to [1], RSA 768 was broken over 4 years ago.

(I still have yet to find a reference that explains why 7 bytes of padding for PKCS#1 signatures is too little and why 9 bytes is more than enough. Separately from that, I have worked out mathematically the numbers for ensuring that the low-exponent attack cannot occur, regardless regardless of the encoded value of the DigestInfo structure, which I'll share when I have some time to write it up. If somebody knows where the number 8 in the PKCS#1 spec came from, though, I'd love to hear about it.)

[1] http://arstechnica.com/security/2010/01/768-bit-rsa-cracked-1024-bit-safe-for-now/

Comment 6

[J.C. Jones [:jcj] (he/they)]

Please audit and, assuming we're correct, close.

Comment 7

[Kevin Jacobs [:kjacobs]]

The correctness issue still exists. It's not really a problem in practice (due to the reasons laid out in comment 5), but this is signature verification code and the patch is trivial. Let's fix it.

Comment 8

[Kevin Jacobs [:kjacobs]]

Attachment: Bug 1067214 - Check minimum padding in RSA_CheckSignRecover.

This patch adds a check to RSA_CheckSignRecover enforcing a minimum padding length of 8 bytes for PKCS #1 v1.5-formatted signatures. In practice, RSA key size requirements already ensure this requirement is met, but smaller (read: broken) key sizes can be used via configuration overrides, and NSS should just follow the spec.

Comment 9

[Kevin Jacobs [:kjacobs]]

https://hg.mozilla.org/projects/nss/rev/e5324bd5a88553e2fe721a6ba196f3759002ba1d