54939 - RSA private key ops are not "blinded"

Status: RESOLVED FIXED

(NSS :: Libraries, enhancement, P3)

Description

[Nelson Bolyard (seldom reads bugmail)]

Paul Kocher, the contributor of NSS's SHA-1 implementation,
developed a "timing attack" against an device that does RSA
private key operations. This chosen ciphertext attack makes 
it possible to determine the private key by measuring 
variations in the amount of time it takes to perform the RSA
private key operation.  

The countermeasure to this attack is known as "blinding". 
See 11.118-11.119 in the Handbook of Applied Cryptography.

To do blinding, a pair of blinding values is computed for 
the private key.  First, a random number k (< n) is chosen.
Then compute 
    f = k**e mod n 
and g = k**-1 mod n. 
Save these values.  
Then, instead of computing
    M = c**d mod n (perhaps using CRT)
compute
    c' = c*f mod n
    M' = c'**d mod n  (perhaps using CRT)
    M  = M'*g mod n

The values f and g can be reused some number of times 
before a new pair of values needs to be computed.  
Kocher suggested 50 times.

In the past, we kept a linked list of blinding info,
protected by a lock.  Each entry in the list contained
a) the modulus n,
b) the two blinding factors
c) the count of remaining uses of this pair (50 or less)
When the function was called to do an RSA private key op,
it looked for an entry in the list with the same modulus.
If one was found, the use count was decremented.  If 
zero, it is deleted.  If none was found, a new pair is 
computed and entered into the list.  The list was 
volatile.  It disappeared when the program was done.

Comment 1

[Ian McGreer]

Attachment: proposed patch which implements blinding

Comment 2

[Ian McGreer]

checkin made based on nelsonb's review:

http://bonsai.mozilla.org/cvsview2.cgi?diff_mode=context&whitespace_mode=show&root=/cvsroot&subdir=mozilla/security/nss/lib/freebl&command=DIFF_FRAMESET&root=/cvsroot&file=rsa.c&rev1=1.18&rev2=1.19


will leave this bug open until it has been through a few rounds of
QA/performance testing.

Comment 3

[Ian McGreer]

Marking as fixed, has been through QA for several weeks now.