304360 - ECC private key could be bigger than group order

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Douglas Stebila]

When a new ECC private key is generated in EC_NewKeyFromSeed and EC_NewKey in mozilla/security/
nss/lib/freebl/ec.c, the private key is not checked to make sure that it is between 0 and (group 
order)-1.

Comment 1

[Douglas Stebila]

Attachment: Patch to generate ECC key with valid group order using SHA-512 randomization

The technique I chose for ensuring the private key is not more than the group
order is as follows.

1) Use SHA-512 to hash the seed.
2) If the hash output is smaller than the group order, use that as the private
key.
3) Otherwise, zero out all bits of the hash output greater than the most
significant bit of the order.  If this value is smaller than the group order,
use this as the private key.
4) If the order is of the form 100000...0000012345, zero out all those bits of
the key.
5) If this value is smaller than the group order,  use this as the private key.
 Otherwise, set the seed to be the original output of the hash function and go
to 1).

Comment 2

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 193497 [details] [diff] [review]
Patch to generate ECC key with valid group order using SHA-512 randomization

Here is some unsolicited review feedback.

>+    SHA512Context *sha512;
>+    unsigned char shahash[64];
>+    int shahashlen;

Instead of 64, use SHA512_LENGTH

>+     /* initialize hash, key, and order */
>+    sha512 = SHA512_NewContext();
>+    if (sha512 == NULL) {
>+	rv = SECFailure;
>+	goto cleanup;
>     }

>+    while (1) {
>+	/* hash the current seed value */
>+	SHA512_Begin(sha512);
>+	SHA512_Update(sha512, seed, seedlen);
>+	SHA512_End(sha512, shahash, &shahashlen, 64);

>+    SHA512_DestroyContext(sha512, PR_TRUE);

Instead of dynamically allocating a SHA512Context, and destroying
it, and making 3 calls to process it (for a total of 5), I suggest
that you replace the Begin-Update-End trio with a call to 
SHA512_HashBuf, and eliminate the NewContext and DestroyContext 
calls.	HashBuf takes 3 arguments, source buf, source length,
destination buf (which is assumed to be SHA512_LENGTH bytes long).
It uses a context on the stack, avoiding the malloc and free.

Comment 3

[Wan-Teh Chang]

Comment on attachment 193497 [details] [diff] [review]
Patch to generate ECC key with valid group order using SHA-512 randomization

Douglas:

Your technique will result in non-uniformity of
the private keys, at least in the case len > shahashlen.
In that case, the private key should be len bit but
you will generate a 512 (shahashlen) bit private key.

In the other cases, it's not obvious if your technique
will result in a uniformly distributed private key.
Could you provide an argument to show that?

Does ANSI X9.62 specify how the private key should be
generated?

Is 0 disallowed to be the value of a private key?

I reviewed the code briefly.  The variable sha512 needs
to be initialized:

    SHA512Context *sha512 = NULL;

Under the cleanup label, it is better to test sha512 for
NULL before destroying it:

    if (sha512) {
	SHA512_DestroyContext(sha512, PR_TRUE);
    }

In the code below:

+	/* if the necessary key length is shorter than the output of the hash,
we need to trim the hash value down */
+	} else {
+	    /* first get rid of any bits greater than the msb of the order */
+	    memcpy(key->privateValue.data, shahash, len);
+	    CHECK_MPI_OK( mp_read_unsigned_octets(&k, key->privateValue.data,
(mp_size) len) );
+	    for (i = mpl_significant_bits(&k) - 1; i >=
mpl_significant_bits(&o); i--) {
+		CHECK_MPI_OK( mpl_set_bit(&k, i, 0) );
+	    }
+	    /* if k is less than group order, then done */
+	    if (mp_cmp(&k, &o) < 0) {
+		break;
+	    }

After you zero the bits in k, if you break out of the while
loop, k will not be equal to key->privateValue, but it is
key->privateValue that we return as the private key.

Finally, could you provide an argument that the while (1)
loop will terminate?  Otherwise it is safer to add a fixed
maximum loop count.

Comment 4

[Wan-Teh Chang]

Another question: what does 100000...0000012345 mean?
Does it mean 100000...00000xxxxx?

Comment 5

[Douglas Stebila]

Attachment: Patch to generate key using FIPS 186-2-change-1

Patch to generate ECC key with private key value randomly chosen from valid
values (i.e., < group order) with best practice as defined in FIPS
186-2-change-1.  If len=ceil(log[2](group order)), then the key generator uses
the global random number generator to generate 2*len random bits, then computes
the value mod (group order).  Does not depend on bug 294106.

Also changes structure of EC key generation functions to match the scheme used
in dsa.c.

Note that until bug 298511 is resolved, the effective size of the key space for
elliptic curve keys is upper-bounded by 2^160, even if the elliptic curve group
is of large order (e.g., nistp384).

Comment 6

[Wan-Teh Chang]

Comment on attachment 193978 [details] [diff] [review]
Patch to generate key using FIPS 186-2-change-1

Douglas, thank you for writing this patch and sorry
for the very late review.

I found some minor problems with the comments and
error handling.  I will attach a new patch that addresses
these problems.

1. In the comments describing the RNG algorithm used,
"algorithm A.3.1 of FIPS 186-2" is now out of date
because I have implemented the revised algorithm in
Change Notice 1 for FIPS 186-2.  So the comments need
to be updated or be less precise about the RNG algorithm.

2. In EC_NewKey, in order for the "cleanup" code to work
under all conditions, privKeyBytes needs to be initialized
to NULL, and we need to add MP_DIGITS(&privKeyVal) = 0 and
MP_DIGITS(&order) = 0 before any CHECK_MPI_OK macros.

Comment 7

[Wan-Teh Chang]

Attachment: Patch to generate key using FIPS 186-2-change-1, v2

Douglas, while writing this patch, I fixed two other
problems.  One is pre-existing -- when freeing memory,
we should test that the pointer is not NULL, rather than
testing that it is NULL.  The other one is in how we
reduce modulo the group order.	You do exactly as FIPS
186-2 Change Notice 1.	The problem is that the output
is from 0 to order-1, so you'll need to discard value 0.
ANSI X9.62 A.4.1 uses a different method; it reduces
modulo order-1 and then add 1.	The output is from 1 to
order-1.  No need to discard an output of 0.

Comment 8

[Wan-Teh Chang]

Attachment: Differences between Douglas's patch and Wan-Teh's patch

Comment 9

[Wan-Teh Chang]

Comment on attachment 198648 [details]
Differences between Douglas's patch and Wan-Teh's patch

I accidentally hit the return key when attaching this patch.

Douglas, this patch shows the my modifications to your patch
and should help you review my patch.

Comment 10

[Wan-Teh Chang]

Douglas, I'm assuming that the private key cannot be 0.
That is, the private key should be between 1 and
(group order)-1.  Is this correct?

Comment 11

[Douglas Stebila]

(In reply to comment #10)
> Douglas, I'm assuming that the private key cannot be 0.
> That is, the private key should be between 1 and
> (group order)-1.  Is this correct?

Yes, that's correct according to ANSI X9.62 Alg. 5.2.1.

Comment 12

[Wan-Teh Chang]

Patch checked in.