RSA Security 5.2.2 manual Pick a random value r and compute, = mre mod n

Security Considerations

parameters, then in theory, an attacker with access to accurate timings can determine unknown values. This is the case for RSA, Diffie-Hellman, and DSA operations. For instance, in an RSA signing operation, purportedly an attacker who knows the message being signed and exactly how long it takes to create the digital signature can determine the signer’s RSA private key.

Currently, there is no known successful implementation of such a procedure. Proposed algorithms under scrutiny either require several absolutely exact timings or thousands of inexact (but still accurate to the millisecond) timings to succeed. However, there are two simple ways to guard against this attack. One is to equalize private key operations, by padding shorter transactions with a few extra milliseconds to make sure that all times are the same. The second method is known as blinding.

For a timing attack to succeed, the eavesdropper must know that the input being processed is only altered before the operation is performed and that the true answer is recovered after the operation by reversing the alteration procedure.

For example, in an RSA signature operation, the input is the BER-encoding of the digest of the data to sign and some pad bytes. To blind the attacker, that input is modular multiplied by a secret random number. Then the product, not the input, is modular exponentiated. To produce the actual signature, the result is modular multiplied by the inverse of the random number.

In mathematical terms, instead of performing the usual RSA encryption process:

sig = md mod n

pick a random value r and compute:

m' = mre mod n

where e is the public exponent. Now find:

s= (m')d mod n

Then to compute the actual signature, find:

sig = (r-1) · s mod n

In this way, the timing attack fails because the attacker does not know what value was exponentiated.

To see that the signature is the same in both cases, note that:

r(mre)d mod n = (r–1)(m)d(re)d= (r)(red)(md)

9 6 R S A B S A F E C r y p t o - C D e v e l o p e r ’s G u i d e