Security Considerations
96 RSA BSAFE Crypto-C Developer’s Guide
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 = m
d
mod n
pick a random value r and compute:
m' = mr
e
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(mr
e
)
d
mod n = (r
–1
)(m)
d
(r
e
)
d
= (r)(r
ed
)(m
d
)
