74226 - NSS needs to double check RSA signatures

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Nelson Bolyard (seldom reads bugmail)]

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.

Comment 1

[Wan-Teh Chang]

Nelson, are you going to fix this in 3.3?

Comment 2

[Nelson Bolyard (seldom reads bugmail)]

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

Comment 3

[Nelson Bolyard (seldom reads bugmail)]

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.

Comment 4

[Nelson Bolyard (seldom reads bugmail)]

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

Comment 5

[Robert Relyea]

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

bob

Comment 6

[Nelson Bolyard (seldom reads bugmail)]

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.

Comment 7

[Ian McGreer]

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?

Comment 8

[Nelson Bolyard (seldom reads bugmail)]

Yes, please.  I'm swamped.

Comment 9

[Ian McGreer]

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

Comment 10

[Ian McGreer]

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

Comment 11

[Ian McGreer]

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.

Comment 12

[Ian McGreer]

Attachment: "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?

Comment 13

[Wan-Teh Chang]

Set target milestone NSS 3.3.2.

Comment 14

[Ian McGreer]

Attachment: 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

Comment 15

[Ian McGreer]

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.

Comment 16

[Ian McGreer]

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

Comment 17

[Ian McGreer]

Attachment: 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).

Comment 18

[Wan-Teh Chang]

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

Comment 19

[Ian McGreer]

marking fixed.