The author of the UltraSparc floating point Montgomery multiplication code
wrote me that he found a bug in the original c code at
The line, which reads:
for(i=len-1; i>=0; i++)
for(i=len-1; i>=0; i--)
The two hand-optimized assembly language versions of this file, used in NSS,
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
Created attachment 53899 [details] [diff] [review]
I do not yet know whether this bug warrants a respin of NSS 3.3.x or not.
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.
Nelson, have you checked in the fix on the NSS_3_3_BRANCH?
No, not yet.
BTW, this multiplication bug has convinced me that bug
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.
I have now made the NSS_3_3_BRANCH version of the montmulf.* files
match the trunk.
I guess I can go ahead and mark this bug fixed, even thought it
"depends on" another bug that is not yet fixed.