RSA private key operations (such as generating RSA signatures) commonly employ a shortcut that uses the Chinese Remainder Theorem (CRT) and the prime factors p and q of the RSA modulus n to speed up the computation. For this reason, in addition to the private exponent "d", RSA private keys nearly always include p and q and 3 other values computed from p, q, and d: d mod (p-1), d mod (q-1), and q^-1 mod p. The shortcut performs separate modular exponentiations using p and q respectively, (instead of n), and combines the results using the 3 other values. As reported in http://theory.stanford.edu/~dabo/papers/faults.ps.gz if any error occurs during the course of an RSA private key operation that affects only one side of the computation (e.g affects the computation using p, but not the computation using q, or vise versa), and the resultant signature is sent out together with information from which the signed value can be determined, (such as happens in all signed S/MIME messages, and in some SSL handshakes), a party that observes the flawed signature and the data on which it was computed can compute one of the factors of the modulus from that data, and hence factor the modulus, and compute the sender's private key. Any error that affects only one side of the CRT computation, including a hardware error, or a software error, or an error in one of the values described above, will result in the potential revelation of the private key. While such an error may have very slight probabilty, and while there may be no known way for a would-be attacker to provoke such an error, still the downside risk is so great that NSS should guard against it. Any of several checks may be done on the result of the private key operation to determine if the result is erroneous. The paper cited above suggestions some checks. NSS should check RSA signatures to detect such errors and avoid sending out flawed signatures. Note that it is not necessary to check the result of RSA private key operations if the result is not going to be sent out (e.g. as in decrypting SSL pre-master secrets). So, the check should be done at a higher level than inside the CRT private key operation itself. When importing a private key (e.g. from a PKCS#12 file) NSS should check the imported values to ensure that they are mathematically correct, e.g. that n == p * q and that the values given for d mod (p-1), d mod (q-1) and q^-1 mod p are correct. PSM should notify the user if a newly imported value is incorrect so that the user will be able to mitigate the damage of a flawed copy of his private key. My thanks to Dr. Keith Henson for sending me the reference to the latest update to this paper.

Nelson, are you going to fix this in 3.3?

No. I'd like to see it fixed for 3.4, but am not sure there will be time.

Bug 105185 demonstrates the need for this check!! The probability of failure is much higher than I had thought. Note that this double-check is only needed when the result of the private key op will be made available to the attacker. That is, it is an issue for signatures (which become available), but not when doing private key decryption. So, not all RSA private key ops need to be double checked. We don't want to waste CPU cycles double-checking when it's unnecessary. So, I'd suggest that, rather than always double checking in RSA_PrivateKeyOp(), instead we might implement a new function RSA_PrivateKeyOpDoubleChecked(), and call the latter function, rather than the former, when computing signatures. We also need to carefully consider how to deal with failures. I suspect that simply redoing the failed computation will result in an identical failure, so retries must be limited, and the higher layer code should be sure to detect them. We don't want erroneous signatures getting out of the token. I'm marking this bug as blocking 105185 on the grounds that double-checking the CRT results is the only way to be really sure that we are protected against anny remaining bugs in that floating point montgomery code.

Ian, I'd appreciate your thoughts on this bug.

All signature operations go through RSA_Sign or RSA_RawSign in softoken/rsawrapr.c. We could verify the signature operations there. bob

It would be more efficient to do it inside the private key op call where the contents of the private key have already been parsed and converted to bignums, and so don't have to be parsed and converted again, I think.

I fully agree with Nelson's suggestion. The check suggested by Shamir should be easy to implement. Nelson, would you like me to take this bug?

Yes, please. I'm swamped.

I have a working patch and a question. Normal RSA CRT is specified as follows: s1 = M**d mod p s2 = M**d mod q s1, s2 --> S, the signature The exponentiations can be sped up by using M**d ~= M**(d mod p-1) mod p, where p is prime. (using ~= to signify "is congruent to") This is in fact what we do, key->exponent1 = d mod p-1, and key->exponent2 = d mod q-1. However, this property is not applicable in Shamir's remedy. Shamir suggests: choose random r s1 = M**d mod p*r s2 = M**d mod q*r Obviously, p*r and q*r are not prime, so we must use the original value of d. When testing my patch, I recomputed d from e, p, and q. I verified several private key ops using the self-test. Then I modified a bit of s1, and verified that it failed Shamir's test. However, there is an open issue. Should d be stored with the private key, to avoid recomputation every time RSA_PrivateKeyOpDoubleChecked is executed? Or not? The answer depends on how many times that function will be called. Actually, I vote for storing it irregardless, it's only a few bytes of memory. -Ian

sorry, last step of Shamir's test is: check s1 == s2

Rubbish. I was looking at the CRT code only, where we store only the CRT parameters. Of course, d is in the privateExponent field. Patch forthcoming.

Created attachment 56157 [details] [diff] [review] "draft" patch to add function (need to decide where it is called, also). Note the #ifdef'ed error value. How do we want to trap this error?

Set target milestone NSS 3.3.2.

Created attachment 57486 [details] [diff] [review] patch that implements double checking with a public key operation The old patch was completely incorrect. This patch is better, however, it is not entirely complete. What this patch does: Defines a function RSA_PrivateKeyOpDoubleChecked. When that function is called, an RSA private key operation is performed, and the result is directly verified by an RSA public key operation. Also defines a function RSA_PrivateKeyCheck. This function tests all of the private key parameters that it can. At a minimum, it tests: p > q (if not, swap) n == p * q gcd(e, p-1) == 1 gcd(e, q-1) == 1 d*e == 1 mod p-1 d*e == 1 mod q-1 If the input key has CRT values, it also checks: d_p = d mod p-1 d_q = d mod q-1 q * qInv == 1 mod p Actually, what happens in this patch is that if any of the CRT values are not present, their integer representation will be zero, the check will fail, and the correct value will be computed. This means that the CRT values will always be set after a call to this function. I see no reason not to allow that behavior. What this patch does not do: Implement Shamir's test. This test has been suggested for large values of e, though we do not know what "large" means at this time. Also, the public key operation test is more complete; it tests the *actual* computed signature. Shamir's test checks the two CRT parts used to compute the signature, but not the actual result. Nelson has suggested that this be accounted for by checking q**-1 once per private key per process. Thus, Shamir's test should only be used if it is a significant performance improvement for "large" values of e. I will have to test to see what "large" is. Nelson says, "I envision that NSS will keep a list of precomputed values for private keys that have been tested for correctness." We already have such a list for blinding parameters, I see no reason why the values for Shamir's test can't tag along there. I will keep working on code to implement Shamir's test, but I wanted to give everyone the opportunity to review this. There seemed to be some desire to see the basic public key test implemented sooner rather than later. -Ian

I have implemented Shamir's test. First, some performance numbers. As always, on my Linux 2.4 dual 400: For all tests, |n| = 1024 bits |input| = 1024 bits operation performed 100 times e - size of RSA public exponent pubkop - time to perform public key operation given (e, n) prkop - time to perform private key operation given (d, n) prkoppb - time to perform private key operation with public key check prkopsh - time to perform private key operation with shamir's check e(bits) pubkop(ms) prkop(ms) prkoppk(ms) prkopsh(ms) 2 103 2573 2662 2763 17 184 2641 2827 2884 32 276 2740 3004 2951 64 450 2912 3181 3096 128 854 3307 4167 3508 256 1670 4139 5816 4329 512 3220 5686 8909 5882 1023 6087 8524 14594 8773 as expected, pubkop ~ e prkoppk ~ pubkop + prkop Nelson has suggested that implementing Shamir's approach is not worthwhile if it doesn't provide a performance improvement for values of e less than or around 32 bits. That seems to be the case. I'm going to attach my implementation anyway, if for no other reason than to show my work.

Created attachment 57788 [details] [diff] [review] patch that implements both public key test and shamir's test This patch implements Shamir's test. Note that the addition of this test really confused the code, due to the extra parameters that needed to be kept. It appears this will not be worthwhile.

Created attachment 57834 [details] [diff] [review] patch that implements double check with public key operation This patch is a cleaner version of attachment 57486 [details] [diff] [review]. It was checked into the 3.3 branch and the tip. The bug is not closed. We need to determine where the new functions should be called from. RSA_PrivateKeyOpDoubleChecked needs to replace RSA_PrivateKeyOp when doing signatures, and RSA_PrivateKeyCheck needs to be call when a new key is imported and stored (e.g., PKCS#12).

Ian, since Bob has checked in calls to the new functions, I think this bug can be closed.

marking fixed.