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