320038 - NSS generates private keys for the NIST curve K-233 with the wrong length.

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Wan-Teh Chang]

The private keys that NSS generates for the NIST curve
K-233 are 30-byte long.  But the correct length is 29 bytes.
The reason is that in lib/freebl/ec.c, function EC_NewKey,
we incorrectly assume the private key is the same length as
the base point order, but the private key may be shorter:
1 <= d <= n-1, where d is the private key and n is the base
point order.  To make matters worse, we specify the base point
order of curve K-233 with two unecessary leading hex 0 digits,
which makes the base point order one byte too long.

Comment 1

[Wan-Teh Chang]

Attachment: Proposed patch

ec.c: the number of bytes that are actually copied to
      the privKeyBytes buffer is the return value of
      the mp_to_unsigned_octets function.  The CHECK_MPI_OK
      macro stores the return value fo the function in the
      local variable err.  So we need to set len to err.
ecl-ecl-curve.h: remove the unnecessary two leading 0's.
      You can find the base point order for curve K-233 on
      SEC 2 (http://www.secg.org/download/aid-386/sec2_final.pdf),
      Section 3.6.1, page 31, but hopefully it is obvious
      that the two leading 0's are not necessary.

Comment 2

[Robert Relyea]

Comment on attachment 205664 [details] [diff] [review]
Proposed patch

r=relyea

Comment 3

[Wan-Teh Chang]

Attachment: Proposed patch v2

I found that I can also fix the bug by using
mp_to_fixlen_octets.  This is more readable than
"len = err".  I reviewed all the other uses of
mp_to_unsigned_octets in NSS and found that they
all call mp_unsigned_octet_size first to get the
length, so they are all good.

I reviewed the parameters for all the NIST recommended
curves and found that we also have two unnecessary leading
0's for curve K-409.  So I fixed that, too.  I suspect
that the unnecessary leading 0's were there to pad the
base point order to the same length as the other parameters,
so in this patch I maintain the alignment using white
spaces (outside the strings).

Comment 4

[Douglas Stebila]

Comment on attachment 205681 [details] [diff] [review]
Proposed patch v2

Looks okay to me.  For background, the reason the extra "00" was at the front of the constant strings in the header file was because it was that way in our OpenSSL code.  The reason it was that way in OpenSSL was because their hex_to_big_int routines checked to see if the top bit was 1, and if it was, treated it as a negative number.  I checked NSS' mpi library and it doesn't do that, so removing the extra "00" is okay.

Comment 5

[Wan-Teh Chang]

Douglas: is mp_read_radix
(http://lxr.mozilla.org/security/ident?i=mp_read_radix)
the counterpart of OpenSSL's hex_to_big_int function?

Comment 6

[Wan-Teh Chang]

Comment on attachment 205681 [details] [diff] [review]
Proposed patch v2

Douglas,

The most significant bit of the base point order for
curve K-409 is 0 (the most significant byte is 7F),
so you shouldn't need a leading zero byte for OpenSSL's
hex_to_big_int routines.  On the other hand, the
base point orders for the curves P-xxx all have a
most significant bit of 1 (their most significant byte
is FF), but you didn't add a leading zero byte to any
of them.

I checked in this patch on the NSS trunk (NSS 3.12).

Checking in ec.c;
/cvsroot/mozilla/security/nss/lib/freebl/ec.c,v  <--  ec.c
new revision: 1.10; previous revision: 1.9
done
Checking in ecl/ecl-curve.h;
/cvsroot/mozilla/security/nss/lib/freebl/ecl/ecl-curve.h,v  <--  ecl-curve.h
new revision: 1.3; previous revision: 1.2
done

Comment 7

[Douglas Stebila]

(In reply to comment #5)
> Douglas: is mp_read_radix
> (http://lxr.mozilla.org/security/ident?i=mp_read_radix)
> the counterpart of OpenSSL's hex_to_big_int function?

Yes.

Comment 8

[Wan-Teh Chang]

Patch checked in on the NSS_3_11_BRANCH (3.11.1).

Comment 9

[Wan-Teh Chang]

Attachment: Allow the hex strings to have leading 00's

I'd like to propose a better fix for this bug, which
allows us to pad the hex strings with leading 00's so
that they look nice.

When we convert a hex string to an array of bytes,
we skip the leading 00's unless the hex string is
"00".  (Otherwise, "00" would become "".)

This patch also backs out my previous fix.

Comment 10

[Wan-Teh Chang]

Attachment: Allow the hex strings to have leading 00's, v2

The only change in this version is the comments.

Comment 11

[Robert Relyea]

Comment on attachment 213350 [details] [diff] [review]
Allow the hex strings to have leading 00's, v2

r=relyea

Comment 12

[Wan-Teh Chang]

Attachment: Allow the hex strings to have leading 00's (as checked in)

I checked in the patch "Allow the hex strings to have leading 00's"
with a minor change on the NSS trunk (3.12) and NSS_3_11_BRANCH
(3.11.1).

Checking in softoken/ecdecode.c;
/cvsroot/mozilla/security/nss/lib/softoken/ecdecode.c,v  <--  ecdecode.c
new revision: 1.6; previous revision: 1.5
done
Checking in freebl/ecl/ecl-curve.h;
/cvsroot/mozilla/security/nss/lib/freebl/ecl/ecl-curve.h,v  <--  ecl-curve.h
new revision: 1.4; previous revision: 1.3
done

Checking in softoken/ecdecode.c;
/cvsroot/mozilla/security/nss/lib/softoken/ecdecode.c,v  <--  ecdecode.c
new revision: 1.4.30.2; previous revision: 1.4.30.1
done
Checking in freebl/ecl/ecl-curve.h;
/cvsroot/mozilla/security/nss/lib/freebl/ecl/ecl-curve.h,v  <--  ecl-curve.h
new revision: 1.2.28.2; previous revision: 1.2.28.1
done