105185 - bug in ultraSparc Montgomery multiplication code

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Nelson Bolyard (seldom reads bugmail)]

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.

Comment 1

[Nelson Bolyard (seldom reads bugmail)]

Attachment: proposed patch

Comment 2

[Nelson Bolyard (seldom reads bugmail)]

I do not yet know whether this bug warrants a respin of NSS 3.3.x or not.

Comment 3

[Nelson Bolyard (seldom reads bugmail)]

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.

Comment 4

[Wan-Teh Chang]

Nelson, have you checked in the fix on the NSS_3_3_BRANCH?

Comment 5

[Nelson Bolyard (seldom reads bugmail)]

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.

Comment 6

[Nelson Bolyard (seldom reads bugmail)]

I have now made the NSS_3_3_BRANCH version of the montmulf.* files 
match the trunk.

Comment 7

[Nelson Bolyard (seldom reads bugmail)]

I guess I can go ahead and mark this bug fixed, even thought it 
"depends on" another bug that is not yet fixed.