350640 - rsa signature verification ignores garbage bytes (CVE-2006-4340)

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Darin Fisher]

I tested using the following build:

  Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.1b2) Gecko/20060825 BonEcho/2.0b2

Details from a co-worker:

On 8/29/06, Philip Mackenzie <[e-mail]> wrote:
> Hi Darin and Ben,
> 
> Marius and Manoj told me you two were the people that would know how to
> handle this...
> 
> We were just following up on some results presented by Daniel Bleichenbacher
> at the Crypto conference, and found that firefox is not properly checking
> its rsa signature padding, resulting in a vulnerability in which one can
> easily generate a certificate that firefox accepts as valid.  As an example,
> use firefox to go to
> https://philmac.corp.google.com:9977/testpage.html
> For fun, you can check out the signature on the certificate that is used.
> 
> We're still trying to determine the extent of this problem, and this
> probably shouldn't be announced publicly until fixes are available for
> everything are available.  So far, it seems that openssl and Sun's java
> crypto library are also vulnerable.  
>
<snip/>
>
>  And to tell you the problem:
> PKCS 1 padding should be:
> 
> [ 00 01 FF ... FF 00 (der encoded hash) ]
> 
> but it seems that the following is accepted:
> 
> [ 00 01 FF ... FF 00 (der encoded hash) (garbage) ]
>  
> which makes it very easy to do cube roots.
> 
> Let us know if we can provide you with more details, or if you want to
> discuss this.
> 
> Thanks,
> -Phil

Comment 1

[Darin Fisher]

Sorry, I cannot easily share the test case.

Comment 2

[Nelson Bolyard (seldom reads bugmail)]

My own re-reading of the code doesn't concur with the above analysis.
There are 4 functions that do RSA signature verification, all in 
security/nss/lib/softoken/rsawrapr.c
They are:
RSA_CheckSign           (PKCS#1)
RSA_CheckSignRecover    (PKCS#1)
RSA_CheckSignRaw        (not PKCS#1)
RSA_CheckSignRecoverRaw (not PKCS#1)

So, the two routines of interest are the ones for PKCS#1.
The first one checks that the hash is contained in the right-most
(least significant) bytes of the output of the RSA private key calculation.
So there is no room for garbage to follow it there.

RSA_CheckSignRecover returns the decrypted result, including DER hash
and anything following it to the caller.  It is the caller's duty to 
determine if the result is expected.  That function is called through/from
the PKCS#11 API call C_VerifyRecoverInit, and from a function named
RSA_HashCheckSign, which passes the entire result to a DER decoder,
which should return error if the input is too long.  

I'll have to do more checking of the callers of C_VerifyRecoverInit, to 
see if they check the results properly.  But it surely appears to me that
the (garbage) would be detected by RSA_CheckSign.

Comment 3

[Wan-Teh Chang]

Darin, we would like to discuss this with your co-worker
Philip Mackenzie.

RSA_CheckSignRecover and its caller DecryptSigBlock are
the functions most commonly used to verify an RSA signature.
We should find out whether SEC_ASN1DecodeItem fails if there is
extra input.  Since secasn1d.c doesn't contain the error code
SEC_ERROR_EXTRA_INPUT, it's possible that SEC_ASN1DecodeItem
doesn't detect that error.

Comment 4

[Robert Relyea]

Nelson's correct about the caller duty. Anything below the PKCS #11 layer cannot determine, a priori, how long the signature data is supposed to be, or if it supposed to be DER data, since in some cases it's not (SSL for instance).

We need to check in one of the following places:
sec_vfy.c or SGN_DecodeDigestInfo in util/secdig.c

Our SECASN1_Decoders do not throw errors if you provide more data than it needs, which is reasonable behavior for decodes (be accepting of what you send). In this case, however we will need to verify that there is no additional data in the block.

Comment 5

[Nelson Bolyard (seldom reads bugmail)]

RSA_HashCheckSign calls SGN_DecodeDigestInfo which calls SEC_ASN1DecodeItem 
which doesn't check that the input is entirely consumed.  So there it is.
I think QuickDER decoder does check it.  
If signature hashes are always DER encoded (are they)? then we could just 
call QuickDer instead of SEC_ASN1DecodeItem in SGN)DecodeDigestInfo.

Comment 6

[Julien Pierre]

I added SEC_ERROR_EXTRA_INPUT when I coded QuickDER . IIRC, the original decoder ignores extra input. I don't remember anyone ever reporting that they got that error from QuickDER, so I think it's a reasonable thing to enforce.

Comment 7

[Robert Relyea]

nelson... err almost. We currently don't use the multi-part functions in our verification code. The code that's failing is sec_vfy.c, but it's calling the same SEC_DecodeDigestInfo function in segdig.c.

Julien, is there any reason we didn't update this function when we did the mass change to QuickDecoder? Can signature data be BER decoded (to ask nelson's question in other words)?

Comment 8

[Nelson Bolyard (seldom reads bugmail)]

Bob, RSA_HashCheckSIgn does a RSA_CheckSignRecover call, and then decodes
the result.  Its only caller is sftk_hashCheckSign, which in turn is only
called by NSC_VerifyInit (in several places).  Given that C_VerifyInit 
never returns the result of the verification (it's not C_VerifyRecoverInit),
why does it internally use the blapi RSA_CheckSignRecover function?
Why doesn't it use RSA_CheckSign ?  

How difficult would it be to change NSC_VerifyInit to stop using RSA_CheckSignRecover and start using RSA_CheckSign?

Tonight I will write a patch to SGN_DecodeDigestInfo to switch it to use
the QuickDER decoder.  It will have to copy the input digest data into the
arenapool first, since QuickDER won't do that (unlike the old decoder).

Comment 9

[Julien Pierre]

Bob,

I think this one got skipped because it wasn't a performance win . It cannot be BER encoded.

This change isn't mentioned specifically by name, but I think it is the one in https://bugzilla.mozilla.org/show_bug.cgi?id=178897#c5

This change came up recently in one of Wan-Teh's patches.

See bugzilla 53427 . In particular the attachment from Wan-Teh that says "Use QuickDER in the softoken" - attachment 233665 [details] [diff] [review] .
And my review of it in
https://bugzilla.mozilla.org/show_bug.cgi?id=53427#c23

Comment 10

[Nelson Bolyard (seldom reads bugmail)]

Darin, if Bob MacKenzie has a test attack program for this, I'd surely like
to ask him to test our forcoming patch against it.  Can that be arranged?

Comment 11

[Robert Relyea]

> why does it internally use the blapi RSA_CheckSignRecover function?
> Why doesn't it use RSA_CheckSign ?  

History I suspect. In any case no one actually calls the hashing versions of these functions. All our current callers either call C_VerifyRecoverInit followed by C_VerifyRecover or they call C_VerifyInit (with CKM_RSA_PKCS rather than one of the hashing versions) followed by a single C_Verify (not update, final).

The particular code that is failing is cryptohi, which does the decoding itself.

bob

Comment 12

[Darin Fisher]

> Darin, if Bob MacKenzie has a test attack program for this, I'd surely like
> to ask him to test our forcoming patch against it.  Can that be arranged?

Yes, I can assist with that.

Comment 13

[Nelson Bolyard (seldom reads bugmail)]

Attachment: Use QuickDer decoder, which should detect excess input

Switch to quick DER decoder.  Fix a few lines to match file's coding style.

Comment 14

[Robert Relyea]

Comment on attachment 236002 [details] [diff] [review]
Use QuickDer decoder, which should detect excess input

That should fix it.

bob

Comment 15

[Daniel Veditz [:dveditz]]

More detail about Bleichenbacher's talk mentioned in comment 0: http://www.imc.org/ietf-openpgp/mail-archive/msg14307.html

It seems this issue is more or less public given the link above, and philmac is probably not be the only one who heard the talk and tried it out on Firefox. We should get this into the 1.8 and 1.8.0 branches ASAP, and I'm sure Sun, Novell, etc will want this on the 1.7/aviary branches as well.

Darin: This would defeat any checks added for bug 340198, right?

Comment 16

[Darin Fisher]

> Darin: This would defeat any checks added for bug 340198, right?

If it is possible to make the certificate look like it was issued by anyone, then yes.

Comment 17

[Nelson Bolyard (seldom reads bugmail)]

Here is more information to help understand the scope of this vulnerability.
This vulnerability makes it possible to create forged signatures that pass
the test, IF and only if the signer's public key (the public key in the 
certificate used to verify the signature) contains a public exponent that 
is the value 3.  

Here are two possible scenarios:
a) a CA certificate has a public key with a public exponent of 3.  Then false
certificates can be created with falsified signatures that pass the flawed verification.

b) a victim server has a server certificate with a public key with a public exponent of 3.  Another server performs a MITM attack, pretending to be the victim server, using DHE_RSA cipher suites, generating false signatures that
pass the (flawed) verification test using the victim server's public key.

Mitigating factors: AFAIK, few (if any) public CAs use or issue certs with 
public keys with a public exponent of 3.  So, people won't be able to use 
this attack against (say) www.amazon.com, because amazon's cert (and its
issuer's cert) use public keys with public exponents of 65537, not 3.

So, while it remains unfixed, this vulnerability makes some small percentage 
of the SSL certificates in the world vulnerable, but it doesn't make all 
(or even most) of them vulnerable.  This isn't the end of the world for 
SSL, even while it remains unfixed.  

Comment 18

[Nelson Bolyard (seldom reads bugmail)]

Committed on trunk:
Checking in lib/util/secdig.c; new revision: 1.7; previous revision: 1.6

Committed on NSS_3_11_BRANCH
Checking in secdig.c; new revision: 1.5.28.2; previous revision: 1.5.28.1

When verifying a signed digest, ensure that the digest is DER encoded and
that there is no extra stuff after the DER encoded digest.  Bug 350640.
r=julien.pierre,rrelyea

I guess a new NSS tag needs to be made (perhaps NSS_3_11_20060830_TAG ?)
so that the maintainers of the other branches can update their branches
with the difference between the previous tag and this one.  I'm not 
really familiar with that process.

Comment 19

[marius schilder]

(In reply to comment #17)
> Here is more information to help understand the scope of this vulnerability.
> This vulnerability makes it possible to create forged signatures that pass
> the test, IF and only if the signer's public key (the public key in the 
> certificate used to verify the signature) contains a public exponent that 
> is the value 3.  
> 
> Here are two possible scenarios:
> a) a CA certificate has a public key with a public exponent of 3.  Then false
> certificates can be created with falsified signatures that pass the flawed
> verification.
> 
> b) a victim server has a server certificate with a public key with a public
> exponent of 3.  Another server performs a MITM attack, pretending to be the
> victim server, using DHE_RSA cipher suites, generating false signatures that
> pass the (flawed) verification test using the victim server's public key.
> 
> Mitigating factors: AFAIK, few (if any) public CAs use or issue certs with 
> public keys with a public exponent of 3.  So, people won't be able to use 
> this attack against (say) www.amazon.com, because amazon's cert (and its
> issuer's cert) use public keys with public exponents of 65537, not 3.
> 
> So, while it remains unfixed, this vulnerability makes some small percentage 
> of the SSL certificates in the world vulnerable, but it doesn't make all 
> (or even most) of them vulnerable.  This isn't the end of the world for 
> SSL, even while it remains unfixed.  
> 

Nelson,
Surely, the form and shape of existing certs is irrelevant. Due to this bug anyone can mint themselves a 'valid' cert for any domain of their choice. This does affect every domain mozilla users think they're visiting, and we're back to reliance on DNS for security.
Note the various root CAs keys that ship with the standard install that use exponent 3.

Comment 20

[Nelson Bolyard (seldom reads bugmail)]

The exponent of the public key in the CA certs is what matters. 
If we have CAs in the root list with public exponents of 3, 
or if trusted roots have issued intermediates with exponents of 3,
then yes, this is a big deal.  

I haven't done a survey of all the roots in the list.  I have looked at 
some, and have not yet seen any that have exponents of 3.  But it only 
takes one, and probabilistically speaking, there is likely to be at 
least one out there.  

Anyway, the patch is committed.  The branch owners need to propagate it
to their branches, I believe.

Comment 21

[Mike Schroepfer]

Comment on attachment 236002 [details] [diff] [review]
Use QuickDer decoder, which should detect excess input

Want this in the 1.8 branch asap for testing...

Comment 22

[Robert Relyea]

Adding kai to the CC list...

Comment 23

[Kai Engert [:KaiE:]]

The NSS team recommends to take patch v3 in bug 340724 as the fastest way to the target.

Comment 24

[Daniel Veditz [:dveditz]]

Updating the NSS snapshot (bug 340724) is absolutely the right thing for the trunk, probably right for 1.8.1 (though it's really late -- I'll let the 1.8.1 team decide), and really not at all what we should do for the 1.8.0 branch.

Is the standalone patch in this bug appropriate for Firefox 1.5.0.7?

Comment 25

[Kai Engert [:KaiE:]]

Attachment: [wrong file]

This is a version of the above patch that applies cleanly to MOZILLA_1_8_0_BRANCH.

Bob and Wan-Teh are ok to take this patch for the older 1.8.0 branch.

For 1.8 branch and trunk they recommend the patch attached to bug 340724.

Comment 26

[Kai Engert [:KaiE:]]

Attachment: Same patch for 1.8.0 branch

(Correct file this time.)

Comment 27

[Kai Engert [:KaiE:]]

Bug 350640 Patch v3 checked in to Mozilla trunk.

Comment 28

[Kai Engert [:KaiE:]]

Sorry for the bugspam, I meant to say, bug 340724 Patch v3 checked in to trunk, which contains the fix for this bug.

Comment 29

[Daniel Veditz [:dveditz]]

Comment on attachment 236295 [details] [diff] [review]
[wrong file]

approved for 1.8.0 branch, a=dveditz for drivers

Comment 30

[Daniel Veditz [:dveditz]]

Comment on attachment 236297 [details] [diff] [review]
Same patch for 1.8.0 branch

Not that one, this one. a=dveditz

Comment 31

[Mike Schroepfer]

Comment on attachment 236002 [details] [diff] [review]
Use QuickDer decoder, which should detect excess input

a=schrep - approving for 1.8.1 branch so we can get regression testing on the 1.8 branch nighties asap.

Comment 32

[Kai Engert [:KaiE:]]

(In reply to comment #31)
> (From update of attachment 236002 [details] [diff] [review] [edit])
> a=schrep - approving for 1.8.1 branch so we can get regression testing on the
> 1.8 branch nighties asap.

Mike, instead of taking this patch for MOZILLA_1_8_BRANCH (1.8.1 branch), are you willing to approve Patch v3 in bug 340724, which includes this patch?

Comment 33

[Daniel Veditz [:dveditz]]

Fix checked into the 1.8.0 branch

Comment 34

[marius schilder]

Attachment: For testing: a faked cert for 'localhost'

Run an https server, using the key and crt from the attachment.
Mozilla connects successfully. So does 'openssl s_client ..' if it knows about the particular root CA used here.
For fun, inspect the certificate and especially the signature field.

Comment 35

[Nelson Bolyard (seldom reads bugmail)]

Thanks, Marius!  With your cert, I was able to confirm my fix.  

Comment 36

[Mike Beltzner [:beltzner, not reading bugmail]]

(In reply to comment #32)
> (In reply to comment #31)
> > (From update of attachment 236002 [details] [diff] [review] [edit] [edit])
> > a=schrep - approving for 1.8.1 branch so we can get regression testing on the
> > 1.8 branch nighties asap.
> 
> Mike, instead of taking this patch for MOZILLA_1_8_BRANCH (1.8.1 branch), are
> you willing to approve Patch v3 in bug 340724, which includes this patch?

Kai, let's get this patch in on the branch ASAP and consider the bigger NSS update separately, OK? Thanks!

Comment 37

[Robert Relyea]

Hi Mike,

We were just offering the fastest way to get the patch in. The changes in bug 340724, are changes that have been reviewed and tested by multiple NSS reviewers and patch regresssions in FF 2.0 from 1.5. These changes are on the NSS 3.11 branch, which has very similiar checkin rules to the FF 2.0 branch itself (it's not all the changes made to NSS). It was NSS with these changes that Nelson verified the patch, and it would be the NSS teams recommendation for FF 2.0 to pick up these patches anyway. Kaie can make this change in a matter of minutes.

Not picking them up will put FF 2.0 out of sync with any recognizable NSS release, making more work when it come times to actually pick up the changes.

If the review approval is such it is the bottleneck, then we can take the hit of applying two patches with a merge... as long as the tree doesn't stay in that state very long (a couple of days maybe).

Thanks,

bob

Comment 38

[Darin Fisher]

FYI, I tested the latest FF 1.5.0.x build (with this patch included) and found that it correctly blocks philmac's testcase.  Firefox reports that the certificate is invalid or corrupt.

Comment 39

[Kai Engert [:KaiE:]]

Patch landed on MOZILLA_1_8_BRANCH for target 1.8.1 with checkin for bug 340724, "patch v3". Thanks for approving.

In comment 18 Nelson said he checked in the NSS patch to trunk of NSS and stable 3.11 branch, so I'm resolving this NSS bug as fixed.

Comment 40

[marius schilder]

Attachment: different fake cert for localhost

This one forms a valid DER blob, so no extra unparsed bytes.
Instead, the algo sequence has a blob parameter that contains random noise. But the hash is properly located at the least significant bytes.
This could foil your patch (dunno), and or some other implementations.
The forged signature cubed looks like 0001fff..ff0030..xxxx..0410hhhh with xxxx the random but ignored attribute data and hhhh the expected hash.

Comment 41

[Nelson Bolyard (seldom reads bugmail)]

The possibility of a vulnerability due to "grabage" in the DigestInfo's 
AlgID's OID or parameters is the subject of bug 351079.  There is a patch
attached to that bug.  I have just tested it with this second cert, and 
it fixes that vulnerability, too.

Comment 42

[Wan-Teh Chang]

PKCS #1 v2.1 Section 9.2 Note 2 (page 38) says DigestInfo
should be encoded with DER but a cautious implementer of
the signature verification operation may want to decode
DigestInfo with BER.  I have no opinion on whether we need
to be that cautious.

Comment 43

[alice nodelman [:alice] [:anode]]

Using https://bugzilla.mozilla.org/attachment.cgi?id=236352&action=view, tested to see if cert was rejected.  The cert was properly blocked and reported as an error.

1.8.1b2 2006090804

verified 1.8.1

1.8.0.7 20060906

verified 1.8.0.7

Comment 44

[Daniel Veditz [:dveditz]]

Can we un-hide this bug now? What's the status of servers including this code?

Comment 45

[Nelson Bolyard (seldom reads bugmail)]

Heavens, yes.  This is ancient history.

Comment 46

[Nelson Bolyard (seldom reads bugmail)]

Related to or inspired by CVE-2006-4340 : unchecked garbage in PKCS v1.5 blocks