Closed Bug 329575 Opened 19 years ago Closed 19 years ago

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

Categories

(NSS :: Libraries, defect)

3.11
defect
Not set
normal

Tracking

(Not tracked)

RESOLVED FIXED
3.11.1

People

(Reporter: wtc, Assigned: wtc)

Details

Attachments

(8 files)

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.
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.
This file was generated using this command line: fipstest ecdsa pkv PKV.req > PKV.rsp.nss
This file was generated using this command line: cryptest a ECDSA PKV.req > PKV.rsp.cryptopp
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.
(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.
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; }
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".
(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?
I downloaded Crypto++ 5.2.3 from the Crypto++ web site. Here is the URL: http://www.eskimo.com/~weidai/cryptlib.html#fips
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
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?
Attached patch Proposed patchSplinter Review
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.
Attachment #214354 - Flags: superreview?(vipul.gupta)
Attachment #214354 - Flags: review?(douglas)
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+.
Attachment #214354 - Flags: review?(douglas) → review+
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
Attachment #214354 - Flags: superreview?(vipul.gupta) → superreview+
Adding Sheueling to this bug discussion. vipul
(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.
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.
(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.
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
Status: NEW → RESOLVED
Closed: 19 years ago
Resolution: --- → FIXED
Target Milestone: --- → 3.11.1
(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. >
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.
(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
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.
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: