Cryptography Reference
In-Depth Information
covered by the adversary, one bit at a time. There are several ways of preventing this
attack, a simple one being to perform a 'dummy' multiplication after each squaring
corresponding to a '0' bit. There are also more sophisticated versions of this attack
that we shall not describe here.
Another important attack that may be regarded as side-channel is Bleichenbacher's
attack against PKCS #1 v1.5, which is discussed below. In this attack, the side
channel provides information—in the form of message errors—about the result of
RSA decryptions.
8.3.5 RSA with Probabilistic Encryption
Plain RSA is, as we have seen, insecure, and this is primarily a consequence of the
fact that its encryption algorithm is deterministic. Because of this, RSA is not IND-
CPA secure and, if one analyzes the specific attacks we have presented, it is easy to
notice that determinism plays a determinant role in most of them. Thus the basic idea
to try to make RSA IND-CPA or even IND-CCA secure is to use random padding of
messages before encryption in order to make the process probabilistic. The simplest
way to do this is just to choose a random string of bits of appropriate length (which
will usually depend on the key size), concatenate it to the message and interpret the
result as an element of
Z
n
which is then encrypted with the RSA function. However,
it is convenient to point out that this procedure does not guarantee that a CPA secure
scheme will be obtained as there is no proof of security for such a loosely defined
scheme and in fact, in some situations in which certain additional conditions are met,
even a randomly padded version of RSA may be shown to be insecure.
For example, there is a variant of the attack against short encryption exponent,
called
Coppersmith's short pad attack
, which works even with some random padding
appended at the end of the message. Suppose that Alice sends Bob a ciphertext
obtained from a properly padded message and Eve intercepts it, preventing Bob
from receiving it. Since Bob does not answer, Alice re-encrypts the message and
sends it again to Bob. But Eve gets also the second ciphertext and now she has two
ciphertexts corresponding to two encryptions of the message with different random
pads. Then Eve might be able to decrypt the message because of the following result
of Coppersmith [54] (see also [33] for a detailed description which includes an attack
by Franklin and Reiter on which Coppersmith's attack is based):
e
2
Theorem 8.2
Let
(
n
,
e
)
be an RSA public key with
len
(
n
)
=
s and let t
=
s
/
∈ Z
n
2
t
m
2
t
m
and m
a message of at most s
−
t bits. Let m
1
=
+
r
1
and m
2
=
+
r
2
,
2
t
. Then m can be
where r
1
and r
2
are distinct integers such that
0
≤
r
1
,
r
2
<
efficiently recovered from
(
n
,
e
)
, and the ciphertexts c
1
and c
2
corresponding to m
1
and m
2
.
n
1
/
9
the
Note that this implies, in particular, that when
e
=
3, then if
r
1
,
r
2
<
attack succeeds. Thus, when
e
=
3, the pad length should not be less than 1
/
9of
