356215 - FF1507 RSA signature forgery: unchecked padding length (CVE-2006-5462)

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Daniel Veditz [:dveditz]]

[e-mail] received the following from Ulrich Kuehn:

Dear Security Group,

I've found an implementation bug in handling a certain RSA signature
padding format that allows a man-in-the-middle attack on SSL and TLS
connections under certain circumstances. I'll go into details below.

The bug seems to be present in versions 1.5.0.7 and earlier of firefox
and potentially of other mozilla software that uses the nss subsystem.
I noticed that the problem is resolved in the firefox 2.0 since beta 1
(on the ftp server marked as of Aug 29, 2006).

However, I ask you to backport a patch to the current version 1.5.0.7 as
I believe that users should not be forced to do a major version upgrade
due to a security bug that could easily be fixed. And the fix is really
easy, see attached diff. Maybe the maintainer updating the code did not
notice that this seemingly small bug has some severe consequences?

Now for the technical details. This bug is somewhat related on a
mathematical level to the recent bug that Daniel Bleichenbacher found
for PKCS#1 signature verification. Nevertheless, it does not involve any
ASN.1 parsing.

The problem is in security/nss/lib/softoken/rsawrapr.c, function
RSA_CheckSign():

    /*
     * check the padding that was used
     */
    if (buffer[0] != 0 || buffer[1] != 1)
        goto loser;
    for (i = 2; i < modulus_len - hash_len - 1; i++) {
        if (buffer[i] == 0)
            break;
        if (buffer[i] != 0xff)
            goto loser;
    }

    /*
     * make sure we get the same results
     */
    if (PORT_Memcmp(buffer + modulus_len - hash_len, hash, hash_len) != 0)
        goto loser;

This code runs over the PKCS#1 padding, but would accept an early 0
byte, so that a padding of
          00 || 01 || 00 || g || hash
with any garbage in g, provided g is long enough to put the hash into
the correct place for the following memcmp. A word of acknowledgement is
due here, this code was independently found by Hal Finney, however, the
consequences seem not be known to him (see
http://www.mail-archive.com/[e-mail]/msg06693.html)

Producing a fake signature, i.e. a non-signature that is nevertheless
accepted by this code, is rather easy when an RSA exponent 3 is used for
usual key lengths (potentially also some larger exponents with longer
keys), as the unchecked part provides enough play ground for an
adversary. If you are interested I could provide some more detail here
on the mathematics. The key point is that with exponent 3 you can use
computing 3rd roots over the real numbers, not modulo N, the RSA
modulus. The former is easy, while the hardness of the latter is the
usual security assumption for RSA.

So basically, when a certificate uses exponent 3, we can produce a fake
signature that is accepted by this code.

Here is how to exploit that. The function RSA_CheckSign() is called
during SSL/TLS connection setup when the server sends a
serverkeyexchange message. This message contains new keys to be used by
the client for exchange of the premaster secret. The keys are signed by
the key in the server certificate. For validation the firefox client
computes the md5||sha1 combined hash of the key parameters (plus the
public random bytes) and checks that against the signature of the
server, using the RSA_CheckSign() function.

So a man-in-the-middle attack is easy when a site uses a certificate
containing an RSA key with exponent 3: the adversary sends the
certificate (he does not have the private key!) and then also sends a
serverkeyexchange message, containing the fake signature. This can
easily be produced only, the computation is quick.

So basically the certificate chain can be exploited to make the client
believe it is connected to the original server, while it is not.
Phishing etc. is easy now.

If you have any further questions please do not hesitate to contact me.
Attached you will find my gpg key, and a diff of the relevant portion of
1.5.0.7 against 2.0b1 which fixes the problem. Please seriously consider
providing a patch for 1.5.0.7.

With best regards,
Ulrich Kuehn

Comment 1

[Daniel Veditz [:dveditz]]

Attachment: patch provided in mail

Comment 2

[Daniel Veditz [:dveditz]]

Comment on attachment 241882 [details] [diff] [review]
patch provided in mail

This has already been reviewed in bug 330114, but requesting re-review specifically for the 1.8.0 branch as a sanity-check

Comment 3

[Daniel Veditz [:dveditz]]

This appears to be due to bug 330114 not landing on the 1.8.0 branch (the patch here is the same as attachment 214758 [details] [diff] [review]). Anyone supporting the aviary/1.7 branches will also want this fix.

Any other similar NSS 3.11 fixes we need to pull back to the 1.8.0 branch?

Comment 4

[Robert Relyea]

Yeah, when bug 330114 was written, the problem appeared to be a correctness issue, not a security issue. We should pick up the complete patch attachment 214932 [details] [diff] [review]. It has additional correctness fixes (so we aren't blind-sided when correctness again equals security;). Both patches are for version 1.8 of rsawrapper.c, so there should be no problem picking either of them up for the mozilla 1.8.0.x branch. 

The code in question is used in ssl signature checks, (not certificate or s/mime signature checks). In a normal RSA ssl handshake there are no signatures checks, but it's possible to force the client to use a new key by sending a server key exchange message [this is used in the old 'stepdown' protocol].

Nelson, would the ssl/tls protocol allow us to reject server key exchange messages when we are doing RSA and not expecting to step down? or do we already do this? (in which case turning export ciphers off will completely defeat this attack).

One final note: This attack is only possible if the server is using an exponent of '3'. This is already considered weak as the RSA server key is used for key exchange and there are known weaknesses in small exponents and key exchange.

Comment 5

[Alexander Sack]

(In reply to comment #4)
> Yeah, when bug 330114 was written, the problem appeared to be a correctness
> issue, not a security issue. We should pick up the complete patch attachment
> 214932 [edit]. It has additional correctness fixes (so we aren't blind-sided when

So the fix would comprise attachment 214932 [details] [diff] [review] AND attachment 214758 [details] [diff] [review] or just the former?

Comment 6

[Wan-Teh Chang]

Comment on attachment 241882 [details] [diff] [review]
patch provided in mail

r=wtc.  You can also take this diff as Bob suggested:

cvs diff -u -kk -rMOZILLA_1_8_0_BRANCH -r1.8.30.1 rsawrapr.c

Comment 7

[Robert Relyea]

it would be both. Both patches were checked in on a single checking to the NSS tree. (wtc's cvs command will show both patches together).

Comment 8

[Nelson Bolyard (seldom reads bugmail)]

I think it's time for the NSS team to get "tough" again, regarding the 
subject of whether or not it supports branches that other groups create.  
Our message to other groups in the past has been: "Use the tags we create
for you, or else support your own NSS branch all by yourself."  

Others have created branches, and have made their own choices about the 
contents of those branches, resulting in the present situation and this bug.
The NSS group is now forced to maintain those other branches in addition to 
the NSS group's own official supported ones.  This needs correction.  

One more thing: there are 2 patches attached to bug 330114.  
Don't take just one.  Take both.  

Comment 9

[Daniel Veditz [:dveditz]]

Comment on attachment 241882 [details] [diff] [review]
patch provided in mail

the check-in for bug 330114 (not quite this attachment) is approved for the 1.8.0 branch, a=dveditz for drivers

Comment 10

[Wan-Teh Chang]

Attachment: Proposed patch for the NSS 3.10.3 release

These bug fixes need to be included in the NSS 3.10.3 release
because they are already in the NSS source code used by
Firefox 1.5.0.x (the MOZILLA_1_8_0_BRANCH).

The bugs are:
bug 327855
bug 351079
bug 351848
bug 335021
bug 334442
bug 351079
bug 330114 (this bug)
bug 350640

Comment 11

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 242309 [details] [diff] [review]
Proposed patch for the NSS 3.10.3 release

Wan-Teh,  Here is my understanding of my team's position on this request.

NSS 3.11.3 is backwards binary compatible with NSS 3.9.x and 3.10.x.  
Users of those older NSS releases (and older products that use NSS) who 
desire to avail themselves of the latest vulnerability fixes must use 
the latest NSS release to replace their older ones, rather than expecting 
(Sun's) NSS team to cherry pick fixes to older branches.  Sun itself has 
made NSS 3.11.3 available for numerous older products that use NSS.  

If other "down stream" products refuse to take NSS 3.11.3, and want to 
cherry pick fixes for their own branches, they are at liberty to do so
but they incur all support costs from that decision.

Comment 12

[Daniel Veditz [:dveditz]]

Fix checked into MOZILLA_1_8_0_BRANCH last night.

Comment 13

[Marcia Knous [:marcia]]

Nelson: Can you recommend a way for QA to verify this bug fix?

Comment 14

[Daniel Veditz [:dveditz]]

This bug has been assigned CVE-2006-5462

Comment 15

[Nelson Bolyard (seldom reads bugmail)]

This may have its own CVE number, but is actually CVE-2006-4340 in sheep's
clothing.