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.
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 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.
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.