Cryptography Reference
In-Depth Information
Then, generate two 2048-bit RSA keys with the same modulus and relatively prime
encryption exponents (once the first key is generated, it is easy to modify it to obtain a
second key satisfying the required conditions). Finally, encrypt a message with both
keys and use
CommonModulusAttack
to compute the plaintext using as input
the two ciphertexts and the public keys.
These attacks show that the use of a common modulus should be avoided in any
RSA implementation. This is not difficult because if the prime factors of the modulus
are randomly chosen for each user, the probability that two users get keys with the
same modulus is negligible.
8.3.4.6 Side-Channel Attacks
Before studying more secure versions of RSA, we are going to briefly mention a
different class of attacks that may be addressed against all versions of the scheme or,
rather, against their implementations. These attacks are called
side-channel attacks
because they exploit information about the private key or the plaintext that may leak
through physical channels such as power consumption, timing behavior or even the
presence of faulty computations. Attacks of this type are not specific to RSA and
may be also addressed against other encryption schemes.
One of the best known side-channel attacks is
Kocher's timing attack
, discovered
by P. Kocher in 1995 (see [121]). Kocher showed how an adversary can find the RSA
decryption exponent bit by bit (from the least significant bit to the most significant
one) by carefully measuring computation times for a series of decryptions—whose
ciphertexts are known to the adversary—and making a statistical analysis of these
times. The attack is based on the hypothesis that decryption uses the binary exponen-
tiation algorithm in which the operations to be performed for each bit of the exponent
vary according to whether it is a 0 bit or a 1 bit. For a detailed description of the
attack we refer to the original article by Kocher [121].
This attack came as a surprise but, once known, is easy to prevent. A simple way
is to make the implementation perform decryptions in constant time. Alternatively,
following an idea of Rivest, the attack may be prevented by using
blinding
, which
consists of multiplying the ciphertext, prior to decryption, by
r
e
mod
n
, where
r
is a randomly chosen element of
Z
n
which, because of the multiplicative property
of RSA, can be factored out from the plaintext after decryption. This defeats the
timing attack because the adversary now does not know the ciphertext which is
being submitted to the binary exponentiation algorithm.
A natural prolongation of the idea behind timing attacks is to analyze how power
consumption of the microprocessor performing a decryption varies over time. The
binary exponentiation method proceeds sequentially by performing a squaring and
a multiplication for each '1' bit of the decryption exponent
d
, and just a squaring
for each '0' bit of
d
. The analysis of the power trace makes it possible to distinguish
between a '1' bit, which corresponds to a longer activity period, and a '0' bit, for
which the activity period is shorter. This way, the decryption exponent can be dis-
