Cryptography Reference
In-Depth Information
Bleichenbacher's CCA attack against PKCS #1 v1.5, presented in [29], exploits
the peculiarities of the padding method used for RSA encryption in this standard, as
well as the fact that a server returned an error message each time a ciphertext was
received that, after decryption, did not produce a PKCS conforming block. Thus the
server, in some weak sense, acted as a decryption oracle because, although it did not
return the plaintext, it gave some information about it.
So, suppose Eve wants to decrypt a ciphertext
c
obtained by encrypting a PKCS
conforming block
b
. She knows that this block (or, rather, the integer defined by it,
but we shall not distinguish between them in what follows), belongs to the interval
[
and she will proceed in a series of steps. At each of these steps, a set of
subintervals of
2
B
,
3
B
−
1
]
is determined such that
b
belongs to one of them, and
these intervals become shorter after each step. The process ends when a set consisting
of only one interval of length 1 is reached, as this uniquely determines the value of
b
.
The procedure used to find these sets of intervals is based on the malleability of the
scheme that makes it possible to modify
c
to produce ciphertexts whose plaintexts are
related to
b
in a predictable way. It proceeds by choosing integers
s
and computing
the ciphertexts
c
=
[
2
B
,
3
B
−
1
]
cs
e
mod
n
which are then sent to the decryption oracle. If the
oracle says that
c
is PKCS conforming (i.e., if the server does not return an error
message) then Eve knows that
bs
belongs to
and this will allow her to
narrow the interval to which
b
must belong by adaptively choosing the multiplier
s
depending on the output of the previous computations.
We refer to [29] for the details of the attack, which will typically require about
2
20
queries to the oracle in order to be able to decrypt a message encrypted with a
1024-bit key. Although the high number of queries makes it difficult to implement
in practice, this attack came as a surprise when it was discovered in 1998 and the
insecurity is so serious that at the time it provoked an immediate change in web
browser software. The easy way to counter this attack in practice would be to not
allow the server to act as an oracle by severely limiting the number of error messages
returned. But this solution is not very satisfactory because it does not address the
core of the matter, which is the weakness of the padding method used. The goal then
was to find a better padding method that could be proved to be CCA secure and this
search led to OAEP (
Optimal Asymmetric Encryption Padding
), which is currently
the algorithm of choice for obtaining secure RSA encryption.
[
2
B
,
3
B
−
1
]
8.3.6 RSA-OAEP
Bleichenbacher's attack was the reason that the PKCS standard was changed by
adopting a more secure padding method introduced by Bellare and Rogaway in
[19]. This padding method can be combined with a (candidate) one-way trapdoor
permutation such as the RSA function to obtain a public key encryption scheme.
The idea that led to the RSA-OAEP algorithm was to try to reach a compro-
mise between security and efficiency, as experience has shown that practitioners are
reluctant to use more secure systems when they are less efficient. The security goal
was IND-CCA in the
random oracle model
whichwe have alreadymentioned in pass-
