650338 - mp_exptmod() gives incorrect results for NIST-P521 prime.

Status: RESOLVED DUPLICATE of bug 536389

(NSS :: Libraries, defect)

Description

[Owen Kirby]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2.16) Gecko/20110319 Firefox/3.6.16 (.NET CLR 3.5.30729)
Build Identifier: nss-3.12.8-with-nspr-4.8.6.tar.gz

I'm using the Elliptic Curve and MPI libraries from NSS to build an embedded cryptographic package, and I've been having some trouble getting the NIST-P521 curve to work correctly with some functions. So far I have managed to narrow the problem down to the mp_exptmod() function producing incorrect results when computing an exponent modulus the NIST-P521 prime.

Unfortunately, my expertise is lacking with regards to the implementation of mp_exptmod in the NSS library, and I'm running out of ideas on how to identify and fix the problem.

I have attached a simple program that demonstrates the error. It works by computing 2^k using mp_2expt, taking the modulus using mp_mod and then comparing the result to the same computation done using mp_exptmod. This simple test passes for all of the NIST primes, but fails for P521.

Reproducible: Always

Steps to Reproduce:
1. Build the MPI library: cd mozilla/security/nss/lib/freebl/mpi; make libmpi.a
2. Build the example program: gcc exptmodtest.c libmpi.a -Wall -O2
3. Run the program, it will print to stdout whenever mp_exptmod() produces an incorrect answer.
Actual Results:  
[osk@rayon mpi]$ gcc exptmodtest.c libmpi.a -Wall -O2 -o etest 
[osk@rayon mpi]$ ./etest
mp_exptmod() agrees with mp_2expt() for p = PRIME_P192
mp_exptmod() agrees with mp_2expt() for p = PRIME_P224
mp_exptmod() agrees with mp_2expt() for p = PRIME_P256
mp_exptmod() agrees with mp_2expt() for p = PRIME_P384
Error computing 2**466 mod p
  p = PRIME_P521
  2**466 mod p = 400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
  mp_exptmod() = 0
mp_exptmod() agrees with mp_2expt() for p = PRIME_HUGE1
mp_exptmod() agrees with mp_2expt() for p = PRIME_HUGE2

Comment 1

[Owen Kirby]

Attachment: Small C program that reproduces the problem with mp_exptmod.

Comment 2

[Konstantin Andreev]

This bug disappears if patch for bug 536389 is applied to the 3.12.8 sources.

Either 3.12.8 is too old, or bug 536389 wasn't checked in the 3_12 branch for some reason.

Comment 3

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

Reopening because this must be fixed in 3.12.

Comment 4

[Konstantin Andreev]

IIRC, this can't be fixed in 3.12, because this is 'softoken' issue, and softoken is frozen in 3.12, because FIPS certified.

Comment 5

[Konstantin Andreev]

Anyway, this bug is a dup of bug 536389. If you believe this must be fixed in 3.12, it worth to reopen original bug, not a duplicate.

Comment 6

[Wan-Teh Chang]

I verified that Konstantin's patch v4 (attachment 433870 [details] [diff] [review]) in bug 536389
(omitting the changes to mozilla/security/nss/lib/freebl/ecl/ecp_mont.c)
makes Owen Kirby's test program pass.  So this bug is a duplicate.

To fix this bug in NSS 3.12.x, we should check in Konstantin's patch in
bug 536389 on the NSS_3_12_BRANCH, ideally after a second code review.