Cryptography Reference
In-Depth Information
message expansion (e..g, [14]). In fact, message expansion can be reduced to a
constant number of bits, and hence these improved probabilistic encryption systems
are comparable to RSA, both in terms of performance and message expansion. They
are not addressed in this topic.
14.3.2
Optimal Asymmetric Encryption Padding
As mentioned in Section 14.2.1.4, the multiplicative structure (or homomorphic
property) of the RSA function leads to a vulnerability of the RSA asymmetric
encryption system that can be exploited with an adaptive chosen-ciphertext attack.
One possibility to eliminate this vulnerability is to randomly pad the plaintext
message prior to encryption. The public key cryptography standard (PKCS) #1 is
a standardized and widely deployed padding scheme for RSA.
In 1998, Daniel Bleichenbacher found a chosen-ciphertext attack against
PKCS #1 version 1.5 that also applied to Web servers implementing the SSL
v3.0 protocol [15]. The Bleichenbacher attack basically refers to a failure analysis,
as introduced in Section 1.2.3. In short, the adversary sends adaptively chosen
ciphertexts to an SSL server, and the server responds for every ciphertext with one
bit saying whether the decrypted data structure conforms to PKCS #1 version 1.5.
So the Web server basically acts as a one-bit oracle for PKCS #1 conformance. If
the adversary can query the oracle a sufficiently large number of times, then he or
she can illegitimately perform one operation with the private key of the server (e.g.,
an RSA decryption or digital signature generation). This operation can then be used,
for example, to decrypt a session key that was previously transmitted from a client to
the server in encrypted form. The Bleichenbacher attack is theoretically interesting
and has had a deep impact on the way people think about formal security arguments
in general, and encryption systems that can be shown to be secure against chosen-
ciphertext attacks in particular.
Before Bleichenbacher published his attack, Mihir Bellare and Philip Rog-
away had developed and proposed a padding scheme that protects against chosen-
ciphertext attacks [16]. As already mentioned in Section 14.1, this scheme is
acronymed OAEP. It is illustrated in Figure 14.1. In this figure,
h
and
g
represent
cryptographic hash functions,
m
represents the plaintext message, and
r
represents
a random(ly chosen) binary string that is used to mask the message. The output of
the OAEP padding scheme are two binary strings—
s
and
t
—that are concatenated
to form the output of the OAEP padding scheme. So the OAEP padding scheme can
be formally expressed as follows:
