1128140 - Arithmetic error in ec_GFp_sub_5 and ec_GFp_sub_6 functions ecl_gf.c softoken

Status: RESOLVED FIXED

(NSS :: Libraries, defect)

Description

[MiW CryptoCurrency]

Attachment: ec_GFp_sub_5&ec_GFp_sub_6-bug.patch

User Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:35.0) Gecko/20100101 Firefox/35.0
Build ID: 20150122214805

Steps to reproduce:

While implementing bug 943639 [Support for Brainpool ECC Curve (rfc5639)] I have discovered an implementation error in ecl_gf.c (softoken).
This off-by-one implementation error of Algorithm 2 from (Brown, Hankerson, J.Lopez, & Menezes, 2000) is in the ec_GFp_sub_5 and ec_GFp_sub_6 functions.
These low level field subtraction functions can be called many times during field and point arithmetic on 384 bit prime curves.

The functions ec_GFp_sub_5 and ec_GFp_sub_6 are missing an additional:

MP_ADD_CARRY(b4, r4, r4, borrow, borrow)

and

MP_ADD_CARRY(b5, r5, r5, borrow, borrow)

in the 	/* Do quick 'add' if we've gone under 0
	 * (subtract the 2's complement of the curve field) *
check.

This will cause these functions to return an incorrect subtraction result if the most significant 64 bits of prime are not 0xFFFFFFFFFFFFFFFF.
brainpoolP384r1 was only curve directly impacted by this bug, as larger curve will use mpi_sub (subtraction on the mp_int directly).
It could impact any generic 256 or 384 bit GFp curves using QWORD optimised sub function for field arithmetic.

In the case of prime256v1 (Suite-B P256), there are additional routines that use curve optimized functions instead of the ec_GFp_sub_5.
This would prevent this from introducing arithmetic errors under P256. Additionally, it is also of the form starting with 0xFFFFFFFFFFFFFFFF.

The Suite-B curve P384 does call ec_GFp_sub_6 for its field sub arithmetic but is not directly impacted by this bug.
Practically, the ec_GFp_sub_6 function fails to add the most significant 64 bit word from the prime to the result in the event of sub_borrow carry.

In practice this does not trigger for P384 because p is:
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF
x is a 64 bit integer
x + FFFFFFFFFFFFFFFF = x

This bug was introduced in 3.11.1 as optimised GFp arithmetic functions. It may never have operated correctly for any curve other than the NIST curves.

This fix will add an additional ADD to field subtractions on curve P384; 
The current form, while not a correct implementation, returns the correct result for this curve.

My discovery process of this bug is documented here: 
'Or Why wont brainpoolP384r1 work in NSS?'
https://github.com/MiWCryptoCurrency/CertificatesInBrowsers/raw/master/Or%20why%20wont%20brainpoolP384r1%20work%20in%20NSS.pdf

ref
Brown, M., Hankerson, D., J.Lopez, & Menezes, A. (2000). Software Implementation of the NIST Elliptic Curves Over Prime Fields. 


Actual results:

Example execution:
(least significant digit first)
ec_GFp_sub_6(a, b, r, meth)
a:
0e b1 40 7d b7 fd 3e 81 a8 7c 4a 4c 0d 16 d5 47 62 2b 64 ec 56 e1 02 23 58 b7 48 9f b7 2b 70 95 a4 06 fb d5 37 4f 80 98 2d 33 a3 0a c9 52 99 0a
b:
a0 a2 14 d6 2e 2e 00 0d b9 01 9a 99 6f b7 49 d5 80 ee 80 4f 2c 6b dc cb 25 63 48 05 d0 a0 8c 45 26 77 00 5f 52 b6 89 e1 8d 32 d0 04 fe cd 4a 12
r:
c1 fa 33 d8 9b cf 85 fb 60 95 cd 42 c7 05 5f 1f 05 4e 9a 1c 44 50 d8 69 e6 aa 54 87 f1 fb 12 65 5d d1 e0 c7 63 08 54 c6 9f 00 d3 05 cb 84 4e f8
meth->irr:
53 ec 07 31 13 00 47 87 71 1a 1d 90 29 a7 d3 ac 23 11 b7 7f 19 da b1 12 b4 56 54 ed 09 71 2f 15 df 41 e6 50 7e 6f 5d 0f 28 6d 38 a3 82 1e b9 8c



r: 0xF84E84CB05D3009FC6540863C7E0D15D6512FBF18754AAE669D850441C9A4E051F5F05C742CD9560FB85CF9BD833FAC1


Expected results:

r: 0x8507A34DA90B6DC7C6540863C7E0D15D6512FBF18754AAE669D850441C9A4E051F5F05C742CD9560FB85CF9BD833FAC1

Comment 1

[Watson Ladd]

I've confirmed this bug exists, or at least I can't see why it doesn't. The fix looks right, but I will want to examine it closely. Is there a reason we aren't using the mpi code in these methods?

Comment 2

[Watson Ladd]

Attachment: Fixes this bug, reuploaded so splinter will work

Comment 3

[Franziskus Kiefer [:franziskus]]

Comment on attachment 8763647 [details] [diff] [review]
Fixes this bug, reuploaded so splinter will work

Review of attachment 8763647 [details] [diff] [review]:
-----------------------------------------------------------------

thanks for the patch. I ran into this with scan-build as well.

Comment 4

[Franziskus Kiefer [:franziskus]]

https://hg.mozilla.org/projects/nss/rev/d81d6127781e