bug in ultraSparc Montgomery multiplication code

RESOLVED FIXED in 3.3.2

Status

NSS
Libraries
P1
normal
RESOLVED FIXED
16 years ago
16 years ago

People

(Reporter: Nelson Bolyard (seldom reads bugmail), Assigned: Nelson Bolyard (seldom reads bugmail))

Tracking

3.3.2
Sun
Solaris

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment)

The author of the UltraSparc floating point Montgomery multiplication code
wrote me that he found a bug in the original c code at 

http://lxr.mozilla.org/mozilla/source/security/nss/lib/freebl/mpi/montmulf.c#199
The line, which reads:
     for(i=len-1; i>=0; i++)
should be
     for(i=len-1; i>=0; i--)

The two hand-optimized assembly language versions of this file, used in NSS,
http://lxr.mozilla.org/mozilla/source/security/nss/lib/freebl/mpi/montmulfv8.s
http://lxr.mozilla.org/mozilla/source/security/nss/lib/freebl/mpi/montmulfv9.s
also contain this bug.  So, changing the .c file won't actually fix NSS.

It appears to me that this bug could possibly cause a crash (invalid memory
reference), or at the very least an incorrect computed result.  Apparently
none of our QA tests have ever discovered this bug, perhaps because the 
tests generally use the same libraries in both SSL clients and servers, and
do not test one platform's clients with another platform's servers.

I will attach a patch for all 3 files named above, one that I believe fixes
the problem.  I am concerned, however, that without a test that can reproduce
and detect the problem, we will not be 100% certain that it is completely 
fixed.
(Assignee)

Comment 1

16 years ago
Created attachment 53899 [details] [diff] [review]
proposed patch
(Assignee)

Updated

16 years ago
Summary: bug in Sparc Montomery multiplication code → bug in Sparc Montgomery multiplication code
(Assignee)

Comment 2

16 years ago
I do not yet know whether this bug warrants a respin of NSS 3.3.x or not.
Priority: -- → P1
Target Milestone: --- → 3.3.2
(Assignee)

Comment 3

16 years ago
The author of that code wrote :

> The problem that may be caused by this bug is that in a Montgomery 
> multiplication, the result can stay bigger than the modulus. This can
> be corrected, however, in the next step of the exponentiation.

> The circumstances under which there is an error in the result of the
> whole modular exponentiation are extremely rare. A not-too-long check with
> random input (in prime generation code) showed that out of 20.6 million
> Montgomery multiplications 49 took the path that could have lead to error
> but all were corrected by the time the whole exponentiation finished.

However, the author was testing his code with OpenSSL, not with NSS, so it
is unknown to me whether the problem is indeed corrected by the time the 
whole exponentiation is finished in NSS.
Summary: bug in Sparc Montgomery multiplication code → bug in ultraSparc Montgomery multiplication code

Comment 4

16 years ago
Nelson, have you checked in the fix on the NSS_3_3_BRANCH?
Assignee: wtc → nelsonb
(Assignee)

Comment 5

16 years ago
No, not yet.  

BTW, this multiplication bug has convinced me that bug 
http://bugzilla.mozilla.org/show_bug.cgi?id=74226
is also a crucial P1 bug for 3.3.2.  

Bug 74226 points out that when an RSA private key operation (e.g. signature) 
is done using the Chinese Remainder Theorem (CRT), if either (not both) of 
the two modular exponentiations produces the wrong answer, then the 
entire private key can be trivially computed from that flawed signature
and the public key.  So, it's really important to double-check that the 
answer from a CRT private key op is correct.  

Prior to the discovery of this bug (105185), I thought the probability 
of there ever being a wrong answer from either of the two mod-exp's
was infinitesimally small.  Now, I think that the probability is too
high to risk continued use of this montmulf code without double checking.

Because of the extreme liability of such a problem, I now think that 
the double-check MUST be done in any new NSS releases that include that
montmulf code, and probably simply in any new NSS releases.

The paper cited in bug 74226 suggests several low-cost ways of double-
checking the CRT computation.  I'll add more comments to that bug.
(Assignee)

Updated

16 years ago
Depends on: 74226
(Assignee)

Comment 6

16 years ago
I have now made the NSS_3_3_BRANCH version of the montmulf.* files 
match the trunk.
Status: NEW → ASSIGNED
(Assignee)

Comment 7

16 years ago
I guess I can go ahead and mark this bug fixed, even thought it 
"depends on" another bug that is not yet fixed.
Status: ASSIGNED → RESOLVED
Last Resolved: 16 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.