535931 - ECC wrong signatures for curves with field size != base point order

Status: RESOLVED FIXED

(NSS :: Libraries, defect)

Description

[Konstantin Andreev]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 6.0; ru; rv:1.9.1.5) Gecko/20091102 Firefox/3.5.5 (.NET CLR 3.5.30729)
Build Identifier: 3.12.4

The following method is used in the ECC sign/verify routines to derive 'e' integer from a digest:

----( begin cite )----
    /* In the definition of EC signing, digests are truncated
     * to the length of n in bits.
     * (see SEC 1 "Elliptic Curve Digit Signature Algorithm" section 4.1.*/
    if (digest->len*8 > ecParams->fieldID.size) {  /* u1 = HASH(M') */
        mpl_rsh( &u1, &u1, digest->len*8 - ecParams->fieldID.size );
    }
----( end   cite )----

See the same at cvs blame:

  http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/security/nss/lib/freebl/ec.c&rev=1.20&mark=758-763,979-984#751
  http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/security/nss/lib/freebl/ec.c&rev=1.20&mark=758-763,979-984#972

In the code above, the field size is used instead of base point order length. For most curves they are the identical, not not for all.

The signatures produced by this code do not conform SEC1 standard and aren't compatible with other implementations.

Reproducible: Always

Comment 1

[Nelson Bolyard (seldom reads bugmail)]

Thanks, for the bug report.  It's a shame the FIPS review didn't catch this.
Would you care to submit a patch ?

Comment 2

[Douglas Stebila]

I'll submit a patch for this in the new year.

Comment 3

[Douglas Stebila]

Attachment: Patch to use order length, not field length

The attached patch switches ECDSA signature generation and verification to truncate the size of the hash by the order size, not the field size.

I was unable to produce a test case that demonstrated the bug.  This is because the bug can only occur when (a) the output size of the hash function is greater than the field length or order length and (b) the order length is at least one bit longer than the field length.  Since the ECDSA in the certutil command in NSS uses only SHA-1, we're restricted to curves of size less than 160 bits to try to find a test case.  There are only a few such standardized curves (secp112r1, secp112r2, secp128r1, secp128r2), none of which satisfy (b).

By the way, since NSS only ships with Suite B curves by default and (b) is not satisfied for all Suite B curves this bug could not have been manifested in deployed versions of NSS.

Regardless, it does appear to be more correct than it was before, and example certificates I generated using this code were verified with OpenSSL (but so were example certificates generated using the previous code since I wasn't able to find a test case as noted above).

Comment 4

[Wan-Teh Chang]

Comment on attachment 422144 [details] [diff] [review]
Patch to use order length, not field length

Douglas, thanks for the patch.  Could you regenerate
the patch using "cvs diff -pu8"?  The -u option (for
unified diffs) is the most important.  Thanks.

Comment 5

[Douglas Stebila]

Attachment: Revised patch with cvs diff -pu8

Comment 6

[Konstantin Andreev]

Hello, Douglas.

1) Nay, this patch does not do what intended.

You are using { olen = ecParams->order.len; }, which is in bytes, not bits.

As you correctly noted, <base point> ord_len differ from fld_len mostly by 1-2 bits. This difference can disappear when length is counted in bytes.

2) IMO, conditions when the bug occures:

   a) [bits]  hash_len > min(ord_len,fld_len) 
              (is it what you mean ?)
and
   b) [bits]  ord_len != fld_len (regardless of > or <)

3) Yes, none of "Basic ECC" curves (secp256r1,secp384r1,secp521r1) trigger this bug.

   But it seems you overlooked for an "Extended ECC" curve, which is eligible for test case even with SHA1 and ord_len > fld_len: WTLS-8.
   Given that the bug should also be triggered by ord_len < fld_len, there are a lot of curves eligible for test case with SHA1: SECP-112R2 SECP-128R2 SECT-113R1 SECT-113R2 SECT-131R1 SECT-131R2 WTLS-1.

P.S.: for those interested, the normative reference:
  SEC1, section 4.3.1 Signing operation, action 5.2
  [http://www.secg.org/download/aid-780/sec1-v2.pdf]

Comment 7

[Douglas Stebila]

Attachment: Revised patch with bits, not bytes

(In reply to comment #6)

> You are using { olen = ecParams->order.len; }, which is in bytes, not bits.

You're right, here's the change.

> 2) IMO, conditions when the bug occures:
> 
>    a) [bits]  hash_len > min(ord_len,fld_len) 
>               (is it what you mean ?)
> and
>    b) [bits]  ord_len != fld_len (regardless of > or <)

Yes.

> 3) Yes, none of "Basic ECC" curves (secp256r1,secp384r1,secp521r1) trigger this
> bug.
> 
>    But it seems you overlooked for an "Extended ECC" curve, which is eligible
> for test case even with SHA1 and ord_len > fld_len: WTLS-8.
>    Given that the bug should also be triggered by ord_len < fld_len, there are
> a lot of curves eligible for test case with SHA1: SECP-112R2 SECP-128R2
> SECT-113R1 SECT-113R2 SECT-131R1 SECT-131R2 WTLS-1.

Ah, great, thanks!  I was able to exhibit the bug with secp112r2: self-signed secp112r2 certificates generated by NSS with the ECDSA code using the bytes of the order (olen or olen*8) fail to verify in OpenSSL, but do correctly verify when using the new  patch, with the bits of the order (obits).

Comment 8

[Konstantin Andreev]

Thank you for your work, Douglas. The patch looks great.

There is a couple of related questions:

1) Could you provide a test case, which covers this issue, to the NSS test suite ?

2) I am seriously confused by giant switches in libnss3.so`cryptohi/seckey.c, which re-enumerate fld_len and ord_len for all softoken-supported curves. Look:

----( begin cite )-----
int
SECKEY_ECParamsToBasePointOrderLen(const SECItem *encodedParams) {
...
    switch (tag) {
    case SEC_OID_SECG_EC_SECP112R1:
        return 112;
    case SEC_OID_SECG_EC_SECP112R2:
        return 110;

... even more 56 cases ...
}

int
SECKEY_ECParamsToKeySize(const SECItem *encodedParams) {
...
    switch (tag) {
    case SEC_OID_SECG_EC_SECP112R1:
    case SEC_OID_SECG_EC_SECP112R2:
        return 112;

... even more 56 cases ...
}

Could we reorganize/refactor the code, and carry out (to nssutils) the ECC-related parts, which are common to libsoftokn3.so and libnss3.so ?

http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/security/nss/lib/cryptohi/seckey.c&rev=1.51&mark=1185-1458#1185

Comment 9

[Douglas Stebila]

(In reply to comment #8)

> 1) Could you provide a test case, which covers this issue, to the NSS test
> suite ?

I don't believe so.  The only way I was able to confirm the bug was using an independent library.  I can't think of a way to do it with NSS, because NSS is expected to be self-consistent -- it shouldn't be able to generate a certificate that won't verify or vice versa, and that's the type of operation that needs to occur to detect the bug.  But if you have a suggestion, by all means, go ahead.

> 2) I am seriously confused by giant switches in libnss3.so`cryptohi/seckey.c,
> which re-enumerate fld_len and ord_len for all softoken-supported curves.
>
> Could we reorganize/refactor the code, and carry out (to nssutils) the
> ECC-related parts, which are common to libsoftokn3.so and libnss3.so ?

I came across those as well while trying to diagnose the bug.  They puzzled me too -- I don't remember writing them in the original development.  It seems like getting rid of it is abstractly a good idea, but I don't know if other issues would arise, such as changing a public API, changing code inside the FIPS boundary (which is undesirable?), etc.  Perhaps one of the core NSS developers could weigh in on this.

Comment 10

[Konstantin Andreev]

(In reply to comment #9)
> (In reply to comment #8)
> > 1) Could you provide a test case, which covers this issue, to the NSS test suite ?
> 
> I don't believe so.  The only way I was able to confirm the bug was using an independent library.  I can't think of a way to do it with NSS, because NSS is expected to be self-consistent -- it shouldn't be able to generate a certificate that won't verify or vice versa, and that's the type of operation that needs to occur to detect the bug.  But if you have a suggestion, by all means, go ahead.

I would suggest to write a small C test program, that 

1) calls libfreebl3.so`FREEBL_GetVector->ECDSA_SignDigestWithSeed() with some predefined "digest" and "random seed" (not really random)
2) check returned signature is equal to predefined correct signature.

This test case may even be extended to test various digest length and all supported curves.

Comment 11

[Douglas Stebila]

Instead of writing a new command line utility for this test (which would be lots of work to integrate into the build process), I wanted to try using an utilities, namely p7sign and p7verify.  I'm having trouble getting them working.  I think that this sequence of commands is reasonable:

> certutil -N -d .
> certutil -S -x -k ec -q nistp256 -s "CN=testnistp256" -n "testnistp256" -d . -t "C,C,C"
> p7sign -k testnistp256 -d . -i test.txt -e -o testnistp256.p7
> p7verify -s testnistp256.p7 -c test.txt -d .

But the p7verify call gives the following error:

> Signature is invalid (Reason: security library: improperly formatted DER-encoded message.).

Anyone have any ideas?

Comment 12

[Konstantin Andreev]

I believe this is not a good test.

Test pass will assert: this particular build is self-consistent. Even w/o your patch NSS should pass this test.

But what we really want to assert: this particular build is consistent with some fixed data, which are believed to be true: digest[in], seed[in], signature[out].

These data should be fixed/hardcoded somewhere in test for future reference.

Comment 13

[Douglas Stebila]

(In reply to comment #12)
> I believe this is not a good test.
> 
> Test pass will assert: this particular build is self-consistent. Even w/o your
> patch NSS should pass this test.
> 
> But what we really want to assert: this particular build is consistent with
> some fixed data, which are believed to be true: digest[in], seed[in],
> signature[out].
> 
> These data should be fixed/hardcoded somewhere in test for future reference.

What I wanted to do was generate some examples using p7sign which we have good reason to believe are correct (i.e., independently confirmed using OpenSSL or some other library), store these, and then have the test suite call verify on these to see if they verify correctly.  

But even just getting started -- generating a signature using p7sign and then verifying it using p7verify -- is a problem: on my system, things generated by p7sign aren't verifying with p7verify.

Comment 14

[Wan-Teh Chang]

Comment on attachment 422674 [details] [diff] [review]
Revised patch with bits, not bytes

r=wtc.  Thanks, Douglas.  I will check this in on the SOFTOKEN_3_13_BRANCH
after running our test suite.  Because of the FIPS validation, the following
directories are frozen on the NSS trunk:
  mozilla/dbm
  mozilla/security/dbm
  mozilla/security/nss/lib/freebl
  mozilla/security/nss/lib/softoken
Changes to these directories can only be made on the SOFTOKEN_3_13_BRANCH.

We don't need to check for the failure of mpl_significant_bits.
mpl_significant_bits can only fail if the input argument is NULL.
None of the existing code checks for the failure of mpl_significant_bits:
http://mxr.mozilla.org/security/ident?i=mpl_significant_bits

Comment 15

[Wan-Teh Chang]

I checked in the patch on the SOFTOKEN_3_13_BRANCH (NSS 3.13).

Checking in ec.c;
/cvsroot/mozilla/security/nss/lib/freebl/ec.c,v  <--  ec.c
new revision: 1.20.8.1; previous revision: 1.20
done

Douglas, do you still have your Mozilla CVS account?

Glen, Bob, please reopen this bug if you need to backport this
fix to NSS 3.12.x for FIPS validation.

Comment 16

[Wan-Teh Chang]

(In reply to comment #8)
Konstantin, Douglas, I believe I wrote the two giant switch
statements.  I hope you can come up with a better way to
implement those two functions.  I remember that with no
access to the lib/freebl/ecl library, I had to resort to
a table lookup.

Re: writing a C test program: take a look at
http://mxr.mozilla.org/security/source/security/nss/cmd/fipstest/fipstest.c
which calls ECDSA_SignDigest and ECDSA_VerifyDigest directly.
You can imitate it to write a test that calls
ECDSA_SignDigestWithSeed.

Let me know if you want me to reopen this bug until you
have added a test.

Comment 17

[Douglas Stebila]

(In reply to comment #16)

> Konstantin, Douglas, I believe I wrote the two giant switch
> statements.  I hope you can come up with a better way to
> implement those two functions.  I remember that with no
> access to the lib/freebl/ecl library, I had to resort to
> a table lookup.

Is there no way to access the blapi or softoken libraries from cryptohi?  The most natural way to do it would be to call EC_FillParams to convert the DER-encoded curve OID into the actual parameters and then pull the field and order size out of that.

Comment 18

[Wan-Teh Chang]

Right.  There is a layer between cryptohi and blapi/softoken: PKCS #11
(lib/pk11wrap).

Unless there is a PKCS #11 function that returns the EC params, we
can't get that info in cryptohi.  I wonder if we can get the EC params
through the PKCS #11 function C_GetAttributeValue.

Comment 19

[Douglas Stebila]

C_GetAttributeValue can be used to get the EC parameters using attribute value CKA_EC_PARAMS.  However, this could return either a data structure with the explicit parameters or just a curve identifier.  And in the named curve case, we're almost certainly going to be getting back just the curve identifier, which puts us right back where we started.  It seems that, without access to blapi/softoken, this is approximately the best we can do.

Comment 20

[Konstantin Andreev]

(In reply to comment #15)
> I checked in the patch on the SOFTOKEN_3_13_BRANCH (NSS 3.13).

Wan, do I understand right, all softoken enhancements should be contributed to SOFTOKEN_3_13_BRANCH ?

Comment 21

[Wan-Teh Chang]

Konstantin: Yes.  You need to check out your NSS source tree
like this:

cvs co NSS
cvs co -r SOFTOKEN_3_13_BRANCH mozilla/dbm mozilla/security/dbm
cvs co -r SOFTOKEN_3_13_BRANCH mozilla/security/nss/lib/freebl
cvs co -r SOFTOKEN_3_13_BRANCH mozilla/security/nss/lib/softoken

Those four directories make up our software crypto module.
They are frozen on the trunk for the FIPS validation of
NSS 3.12.x.  So we have to make changes to those four
directories on the SOFTOKEN_3_13_BRANCH.