Cryptography Reference
In-Depth Information
that the simple CCA attack we have seen against plain RSA no longer works if the
plaintext is randomly padded before encryption, because the padding destroys the
multiplicative property on which this attack was based. However, using randomized
padding does not guarantee that IND-CCA security will be attained and, in fact, we
are going to see an example of an RSA-based encryption scheme that is believed—
although not proved—to be CPA secure but against which there is a practical CCA
attack. This scheme is the one used in the PKCS #1 v1.5 standard, which belongs to
a family of standards (
Public Key Cryptography Standards
) published by RSA Labs
that have become part of many other standards, including the SSL/TLS protocol used
by web browsers in their transactions.
8.3.5.1 Bleichenbacher's CCA Attack Against PKCS #1 v1.5
PKCS #1 v1.5 uses a version of padded RSAwhich pads messages before encryption
in the following way. Suppose that
is an RSA public key, where the modulus
n
isassumedtobea
t
-byte integer, i.e., 2
8
(
t
−
1
)
≤
(
n
,
e
)
2
8
t
.Let
m
be a message, which
n
<
is assumed to have
s
bytes, where
s
11. The message is then padded to obtain
a
t
-byte formatted plaintext block as follows:
≤
t
−
b
=
00
||
02
||
padding string
||
00
||
m
.
Here, a 00 byte (in hexadecimal notation) is followed by a 02 byte, then a random
padding string consisting of
t
−
−
3 nonzero bytes, then another 00 byte and, finally,
the original message
m
(note that, since
t
s
−
s
≥
11, the length of the padding string
is
∈ Z
n
in the standard way and
encrypted with RSA, producing the ciphertext
x
e
mod
n
. A formatted data block
b
is called
PKCS conforming
if it has the above format. If we let
B
≥
8). Then this block
b
is converted to an element
x
2
8
(
t
−
2
)
, then 2
B
=
is represented by the following byte string:
2
B
=
00
||
02
||
00
||
00
||
...
||
00
,
t
−
2 times
and, similarly, the byte string corresponding to 3
B
is:
3
B
=
00
||
03
||
00
||
00
||
...
||
00
.
t
−
2 times
The data blocks formatted by the method indicated above range from00
||
02
||
00
||
00
||
...
||
ff
and hence we see that if a data block
b
is PKCS
conforming then the corresponding integer
x
00 to 00
||
02
||
ff
||
ff
||
...
||
∈ Z
n
satisfies:
2
B
≤
x
<
3
B
.
