329575 - EC_ValidatePublicKey gives false positives for NIST Koblitz (K-ddd) curves

Status: RESOLVED FIXED

(NSS :: Libraries, defect)

Description

[Wan-Teh Chang]

When running the NIST ECDSA Public Key Validation Test,
we found that NSS's EC_ValidatePublicKey function gives
false positives for all and only NIST Koblitz (K-ddd)
curves.

I will attach a test input REQUEST file, and the test
output RESPONSE files generated by NSS and Wei Dai's
Crypto++ Library 5.2.3.

Comment 1

[Wan-Teh Chang]

Attachment: Patch to make NSS use the same output format as Crypto++

Crypto++ does not print the comment and blank lines in
the test input REQUEST file, so I need to apply this
patch to NSS to match that output format.

Comment 2

[Wan-Teh Chang]

Attachment: Test input REQUEST file PKV.req

Comment 3

[Wan-Teh Chang]

Attachment: Test output RESPONSE file generated by NSS

This file was generated using this command line:

  fipstest ecdsa pkv PKV.req > PKV.rsp.nss

Comment 4

[Wan-Teh Chang]

Attachment: Test output RESPONSE file generated by Crypto++

This file was generated using this command line:

  cryptest a ECDSA PKV.req > PKV.rsp.cryptopp

Comment 5

[Wan-Teh Chang]

Attachment: Differences between the test outputs of NSS and Crypto++

The first test output is NSS.  The second test output is Crypto++.

You can see that the results differ for all the K- curves and only
for the K- curves, and the differences are false positives.

Comment 6

[Douglas Stebila]

(In reply to comment #5)
> Created an attachment (id=214265) [edit]
> Differences between the test outputs of NSS and Crypto++
> 
> The first test output is NSS.  The second test output is Crypto++.
> 
> You can see that the results differ for all the K- curves and only
> for the K- curves, and the differences are false positives.

Wan-Teh, I downloaded Crypto++ 5.2.1 and have been trying to figure out where the FIPS PKV test code is.  I'm curious to know what particular condition is failing for those examples in Crypto++ that is not failing in NSS.  In NSS, I would want to patch ec_GF2m_validate_point in ecl/ec2_aff.c to output which step fails.  But I can't find the corresponding code in Crypto++.  The best I can see is that part of it is the ValidateElement method in eccrypto.cpp.  And there's some stuff in datatest.cpp in the TestSignatureScheme method, but I never liked C++ and can't figure out what's going on there.

Comment 7

[Wan-Teh Chang]

Douglas, I suggest that you prepare a PKV.req file with
just these four lines:

[K-163]

Qx = 00017ae9b672ded07a56aa4e6eb03c1ac8413a4c0419
Qy = 0004e43508c6a8cbc1245125d7d79db3b9722c83046e

NSS reports a false positive on this test case.  I found
that Crypto++ fails in the second IsIdentity() call below:

[eccrypto.cpp]

template <class EC>
bool DL_GroupParameters_EC<EC>::ValidateElement(unsigned int level, const Element &g, const DL_FixedBasePrecomputation<Element> *gpc) const
{
	bool pass = !IsIdentity(g) && GetCurve().VerifyPoint(g);
	if (level >= 1)
	{
		if (gpc)
			pass = pass && gpc->Exponentiate(this->GetGroupPrecomputation(), Integer::One()) == g;
	}
	if (level >= 2)
	{
		const Integer &q = GetSubgroupOrder();
		pass = pass && IsIdentity(gpc ? gpc->Exponentiate(this->GetGroupPrecomputation(), q) : ExponentiateElement(g, q));  <===== FAILED
	}
	return pass;
}

which is called by the ValidateElement() method below:

[pubkey.h]

	// CryptoMaterial
	bool Validate(RandomNumberGenerator &rng, unsigned int level) const
	{
		bool pass = GetAbstractGroupParameters().Validate(rng, level);
		pass = pass && GetAbstractGroupParameters().ValidateElement(level, this->GetPublicElement(), &GetPublicPrecomputation());  <===== FAILED
		return pass;
	}

I believe the corresponding code in NSS is:

[ec2_aff.c:ec_GF2m_validate_point]

    /* 4: Verify that the order of the curve times the publicValue
     *    is the point at infinity.
     */
    MP_CHECKOK( ECPoint_mul(group, &group->order, px, py, &pxt, &pyt) );
    if (ec_GF2m_pt_is_inf_aff(&pxt, &pyt) != MP_YES) {
        res = MP_NO;
        goto CLEANUP;
    }

Comment 8

[Wan-Teh Chang]

Douglas, to build Crypto++'s FIPS test, you need
to make two changes:

In adhoc.cpp: change "#if 1" to "#if 0".
In fipsalgt.cpp: change "#if 0" to "#if 1".

The idea is that you point the function pointer
AdhocTest to FIPS_140_AlgorithmTest instead of
MyAdhocTest.

The "a" argument we pass to cryptest means "run
adhoc test".

Comment 9

[Douglas Stebila]

(In reply to comment #8)
> Douglas, to build Crypto++'s FIPS test, you need
> to make two changes:
> 
> In adhoc.cpp: change "#if 1" to "#if 0".
> In fipsalgt.cpp: change "#if 0" to "#if 1".

My adhoc.cpp has no #if 1 statement.  I could only find the source for 5.2.1 to download -- where did you get 5.2.3?

Comment 10

[Wan-Teh Chang]

I downloaded Crypto++ 5.2.3 from the Crypto++ web site.
Here is the URL:
http://www.eskimo.com/~weidai/cryptlib.html#fips

Comment 11

[Wan-Teh Chang]

Attachment: Subset of PKV.req containing just the problematic test cases

This is the subset of the test input REQUEST file PKV.req
containing just the test cases that NSS reports false positives.
I confirmed that all of these test cases fail the PKV test
with Crypto++ for the same reason I described in comment 7:

    nQ is not equal to the point at infinity O.

For all of these test cases, the x and y coordinates of nQ
computed by Crypto++ are:
    x = 0
    y = 1

Comment 12

[Wan-Teh Chang]

I found the bug.

The reason NSS thinks nQ = O is that n = 0.

NSS is supposed to multiply Q by the group order.
The group order is not 0.  So how can n be 0?  This
is because of the following code in ECPoint_mul:
(k is the scalar)

 59         /* want scalar to be less than or equal to group order */
 60         if (mp_cmp(k, &group->order) >= 0) {
 61                 MP_CHECKOK(mp_init(&kt));
 62                 MP_CHECKOK(mp_mod(k, &group->order, &kt));
 63         } else {
 64                 MP_SIGN(&kt) = MP_ZPOS;
 65                 MP_USED(&kt) = MP_USED(k);
 66                 MP_ALLOC(&kt) = MP_ALLOC(k);
 67                 MP_DIGITS(&kt) = MP_DIGITS(k);
 68         }

It is kt, not k, that is passed to the actual multiplication
routine.

If I change ">=" to ">", we report "Result = F" on the test
cases on which we used to report false positives.

I think that code is merely an optimization.  The code
should still work if we just keep the code in the "else"
block, right?

Comment 13

[Wan-Teh Chang]

Attachment: Proposed patch

This patch allows NSS to multiply a point by a scalar
equal to the group order faithfully.  The optimization
of reducing the scalar modulo the group order only works
for points in the group.  But when validating a public
key, we need to multiply the public key by the group
order, and an invalid public key may not be in the
group.

This patch relaxes the condition for the optimization
just enough to run the public key validation algorithm.
I'm not sure if the optimization may get in the way of
some other algorithm or protocol.  We may want to consider
removing the optimization altogether, or have a version
of ECPoint_mul without the optimization.

By the way, I verified that for all of the problematic
PKV test cases, NSS computes nQ = (0, 1) just like
Crypto++ does.

Comment 14

[Douglas Stebila]

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

Well done, Wan-Teh: good catch!

I don't think that changing that test will materially affect any part of the code, and of course it makes sense from the perspective of the public key validation tests.  

I was able to confirm that it changes the results of the PKV validation, but since I do not have Crypto++ working, I cannot verify against a Crypto++ output.

Assuming you've verified against Crypto++, review+.

Comment 15

[Vipul Gupta]

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

(In reply to comment #14)
> (From update of attachment 214354 [details] [diff] [review] [edit])
> Well done, Wan-Teh: good catch!

   Well done, indeed. The patch makes sense and should
   be included in the code. However, there are a few things
   I'm still confused about. First, why does this only seem
   to impact Koblitz curves. Second, in both
   ec_GF2m_validate_point and ec_GFp_validate_point,
   the code checks that the point is on the curve before
   trying to multiply by the group order. So why did the
   check for the point being on the curve not fail even earlier.

   vipul

Comment 16

[Vipul Gupta]

Adding Sheueling to this bug discussion.

vipul

Comment 17

[Douglas Stebila]

(In reply to comment #15)
>    Well done, indeed. The patch makes sense and should
>    be included in the code. However, there are a few things
>    I'm still confused about. First, why does this only seem
>    to impact Koblitz curves. 

This I don't know.  My only guess is that they're only testing this because of the Koblitz curves having a and b either 0 or 1.  

>    Second, in both
>    ec_GF2m_validate_point and ec_GFp_validate_point,
>    the code checks that the point is on the curve before
>    trying to multiply by the group order. So why did the
>    check for the point being on the curve not fail even earlier.

I'm not certain, but I can speculate.  The point may be on the curve, but it may not be in the subgroup generated by the base point, so it doesn't satisfy the order constraint.  But that's just a guess, and I have no way of knowing for certain unless I figure out how to solve the discrete logarithm problem or build a quantum computer.

Comment 18

[Wan-Teh Chang]

Attachment: Patch to do point multiplication for all scalars faithfully

I'm attaching this patch just as a reference.  This
patch makes ECPoint_mul multiply the point with the
specified scalar faithfully.  It passed all.sh.

Like Vipul, I also wonder why this bug does not affect
the NIST P- and B- curves.

As for Vipul's second question, I believe the problematic
test cases are valid points on the curves, but they are
not in the subgroups generated by the base points.  Does
this make sense, Vipul?  Perhaps it's easy to construct
such points for the K- curves, but hard to construct them
for the P- and B- curves, which would explain why this bug
only affects the K- curves.

Comment 19

[Douglas Stebila]

(In reply to comment #18)
> Created an attachment (id=214372) [edit]
> Patch to do point multiplication for all scalars faithfully
> 
> I'm attaching this patch just as a reference.  This
> patch makes ECPoint_mul multiply the point with the
> specified scalar faithfully.  It passed all.sh.

I don't think it's necessary to apply this new patch.  The test of multiplying the point by the order of the generator is all that's needed to determined if the point is in the subgroup or not.  If it's in the subgroup, then multiplying by k is the same as multiplying by (k mod order) by the group law.  If it's not in the subgroup, then we should have caught it in the validate step, which, thanks to the earlier work by Wan-Teh, we now will.

> As for Vipul's second question, I believe the problematic
> test cases are valid points on the curves, but they are
> not in the subgroups generated by the base points.  Does
> this make sense, Vipul?  Perhaps it's easy to construct
> such points for the K- curves, but hard to construct them
> for the P- and B- curves, which would explain why this bug
> only affects the K- curves.

This is what I think as well, but just speculation.

Comment 20

[Wan-Teh Chang]

Douglas, I've verified against Crypto++.  (You can find
the output of Crypto++ as an attachment in this bug.)

I checked in the proposed patch on the NSS trunk (3.12)
and NSS_3_11_BRANCH (3.11.1).

Checking in ecl_mult.c;
/cvsroot/mozilla/security/nss/lib/freebl/ecl/ecl_mult.c,v  <--  ecl_mult.c
new revision: 1.5; previous revision: 1.4
done

Checking in ecl_mult.c;
/cvsroot/mozilla/security/nss/lib/freebl/ecl/ecl_mult.c,v  <--  ecl_mult.c
new revision: 1.3.2.2; previous revision: 1.3.2.1
done

Comment 21

[Sheueling Chang]

(In reply to comment #17)
> (In reply to comment #15)
> >    Well done, indeed. The patch makes sense and should
> >    be included in the code. However, there are a few things
> >    I'm still confused about. First, why does this only seem
> >    to impact Koblitz curves. 
> 
> This I don't know.  My only guess is that they're only testing this because of
> the Koblitz curves having a and b either 0 or 1.  

This is still mind buggling for me why only Koblitz curves are impacted. The test of "raising a point by the group-order => infinity" should be applied to all curves that have a co-factor larger than one. Finding points not in the subgroups generated by the base points is not an expensive job for non-Koblitz curves. I can't see why they only apply the test to Koblitz curves.

> >    Second, in both
> >    ec_GF2m_validate_point and ec_GFp_validate_point,
> >    the code checks that the point is on the curve before
> >    trying to multiply by the group order. So why did the
> >    check for the point being on the curve not fail even earlier.
> 
> I'm not certain, but I can speculate.  The point may be on the curve, but it
> may not be in the subgroup generated by the base point, so it doesn't satisfy
> the order constraint.  But that's just a guess, and I have no way of knowing
> for certain unless I figure out how to solve the discrete logarithm problem or
> build a quantum computer.
> 

Comment 22

[Wan-Teh Chang]

I verified that our FIPS ECDSA public key validation (PKV)
test input file only has test cases for the NIST K- curves
that fail the PKV test by failing the nQ=O test.  (n = group
order, Q = purported public key, O = point at infinity.) None
of the test cases for the NIST P- and B- curves fail the PKV
test by failing the nQ=O test.  This could be an area for
improvement for the FIPS ECDSA PKV test input generation.

Comment 23

[Vipul Gupta]

(In reply to comment #22)
> I verified that our FIPS ECDSA public key validation (PKV)
> test input file only has test cases for the NIST K- curves
> that fail the PKV test by failing the nQ=O test.  (n = group
> order, Q = purported public key, O = point at infinity.) None
> of the test cases for the NIST P- and B- curves fail the PKV
> test by failing the nQ=O test.  This could be an area for
> improvement for the FIPS ECDSA PKV test input generation.

Hi Wan-Teh,

   From you email it wasn't completely clear to me which of
the following you were saying:

(1) The FIPS ECDSA PKV tests never check for nQ = O for
curves other than Koblitz curves, or

(2) It is just coincidence that the particular set of tests we
 received from the testing lab performed this check only for
 the Koblitz curves. 

I assume you meant (b) but wanted to confirm.

vipul

Comment 24

[Wan-Teh Chang]

Vipul,

The public key validation (PKV) procedure consists
of four tests.

1. Q != O

2. The x and y coordinates of Q are field elements.

3. Q satisfies the curve equation.

4. nQ = O

A negative PKV test case fails one of the four tests.
The PKV procedure terminates as soon as a test fails.
So, if test 1, 2, or 3 fails, we won't perform test 4.

For the NIST P- and B- curves, the input test file
generated by the testing lab doesn't have any test
case that gets to test 4 and fails test 4.  In other
words, all the test cases either pass all of the four
tests, or fail one of the first three tests.

For the NIST K- curves, the input test file generated
by the testing lab has some test cases that (pass the
first three tests but) fail test 4.