A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS 1 v2.0.pdf

(126 KB) Pobierz
A Chosen Ciphertext Attack on RSA Optimal
Asymmetric Encryption Padding (OAEP) as
Standardized in PKCS #1 v2.0
James Manger
Telstra Research Laboratories,
Level 7, 242 Exhibition Street, Melbourne 3000, Australia
James.H.Manger@team.telstra.com
Abstract.
An adaptive chosen ciphertext attack against PKCS #1 v2.0
RSA OAEP encryption is described. It recovers the plaintext – not the
private key – from a given ciphertext in a little over log
2
n
queries of an
oracle implementing the algorithm, where
n
is the RSA modulus. The
high likelihood of implementations being susceptible to this attack is
explained as well as the practicality of the attack. Improvements to the
algorithm to defend against the attack are discussed.
Keywords:
chosen ciphertext attack, RSA, OAEP, PKCS
1
Introduction
At CRYPTO ’98 Daniel Bleichenbacher presented an adaptive chosen cipher-
text attack against PKCS #1 v1.5 RSA block type 2 padding [1]. The attack
needs roughly one million oracle queries to succeed for a 1024-bit RSA key. He
concluded that RSA encryption should include an integrity check and that the
phase between decryption and integrity verication is crucial, because any infor-
mation leaking from this phase can present a security risk. Version 2.0 of PKCS
#1 introduced a new algorithm RSAES- OAEP that uses Optimal Asymmetric
Encryption Padding (OAEP) to counteract this attack [2][5]. It says, “a chosen
ciphertext attack is ineective against a plaintext-aware encryption scheme such
as RSAES-OAEP”. However, the design of RSAES-OAEP makes it highly likely
that implementations will leak information between the decryption and integrity
check operations making them susceptible to a chosen ciphertext attack that re-
quires many orders of magnitude less eort than similar attacks against PKCS
#1 v1.5 block type 2 padding. The attack needs roughly one thousand oracle
queries to succeed for a 1024-bit RSA key.
Section 2 summarizes RSA Optimal Asymmetric Encryption Padding as de-
ned in PKCS #1 v2.0 .
1
Section 3 describes a chosen ciphertext against this
algorithm. Section 4 explores the practicality of the assumptions necessary for
1
The same algorithm is standardized in IEEE 1363, where the relevant message en-
coding method for encryption is called EME1 [4]
the attack to proceed. Section 5 discusses approaches for changing the algorithm
or its implementation to prevent the attack and restore the intended security
properties.
2
RSAES-OAEP
RSAES-OAEP encryption starts by encoding a seed, a hash, padding octets and
the secret (typically a session key) into an octet string. Masking operations ef-
fectively randomize these octets before they are treated as the unsigned binary
representation of an integer – the integer used in the RSA modular exponenti-
ation operation. The number of padding octets is chosen so that the encoding
consumes one less octet than required for a unsigned binary representation of
the modulus. This ensures the integer is less than the modulus as required in
RSA. Alteratively, the encoded messages can be considered as an octet string
the same length as the modulus, but with the most signicant octet set to ‘00’h.
Figure 1 shows the RSAES-OAEP decryption and decoding process. The
ciphertext is converted to the plaintext by modular exponentiation with the
private exponent followed by integer-to-octet translation. A mask generation
function (MGF) uses the least signicant portion of the plaintext to unmask
the seed. A mask generated from the seed unmasks a hash, padding and the
condential message. The integrity of the ciphertext is veried by comparing
the unmasked hash to an independently calculated hash of the parameters (and
by checking the padding).
§
¤
HASH
¥
¦
Padding
Hash
Parameters
j
=
?
Seed
6
6
j
Mask1
@
@
§ ¤
MGF
¦ ¥
@
R
@
I
@
@
§ ¤
MGF
¦ ¥
@
@
Hash
Secret
6
j
Mask2
00
Plaintext
Ciphertext
§
6
¤
RSA
¦ ¥
Fig. 1.
RSAES-OAEP Decoding
After the private key operation the decryption operation can fail in the
integer-to-octet translation (e.g. the integer is too large to t in one fewer octets
than the modulus) or in the OAEP-decoding (e.g. integrity check fails). In both
instances PKCS #1 v2.0 says to output “decryption
error”
and stop.
3
Chosen Ciphertext Attack
Let
n
be an RSA modulus, with
e
and
d
the public and private exponents
respectively. Let
k
= log
256
n
be the byte length of
n
and let
B
= 2
8(k−1)
.
2
Assume an attacker knows the public key (n,
e)
and has access to an oracle
that for any chosen ciphertext
x
indicates whether the corresponding plaintext
y
≡
x
d
(mod
n)
is less than
B
or not — returning “y
< B”
or “y
≥
B”.
For
the last assumption to hold it is sucient for the oracle to distinguish a failure
in the integer-to-octets conversion (in which case “y
≥
B”
is returned) from any
subsequent failure, e.g. of the integrity check.
The attacker wishes to determine the plaintext
m
≡
c
d
(mod
n)
corre-
sponding to a captured ciphertext
c.
The basic step is to choose a multiple
f
and send
f
e
·
c
(mod
n)
to the oracle. This ciphertext corresponds to the plain-
text
f
·
m.
3
The oracle indicates if this is in the range [0,
B)
or (B,
n)
modulo
n,
thus providing a mathematical relationship about
m
that reduces the range
(or ranges) in which it must lie. The aim is to reduce this range with successive
oracle queries until just one value is left —
m.
The approach of the attack described in this paper is to choose values of
f
such that the range where
f
·
m
could lie spans exactly one boundary between
a region where
f
·
m < B
(mod
n)
and a region where
f
·
m
≥
B
(mod
n).
The oracle response narrows the range to one of these regions.
Initially we know
m
∈
[0,
B),
as all valid messages are in this range by
construction. One point to note is that since
m < B
there is always a multiple
of
m
that lies in any region of width
B.
For instance, for any integer
i
there is
always some integer
f
such that
f
·
m
∈
[in,
in
+
B).
The following attack assumes 2B
< n.
This assumption will usually be sat-
ised as RSA moduli are typically chosen to be exact multiples of 8 bits long
making
n
between 128 and 256 times larger than
B.
Situations where this as-
sumption does not hold are discussed toward the end of this section.
Step 1:
Try multiples of 2, 4, 8,
. . .
2
i
, . . .
in turn until the oracle returns “≥
B”.
For each multiple
f
1
the possible values of
f
1
·
m
span a single boundary point
at
B.
1.1 We know
m
∈
[0,
B).
Let
f
1
= 2.
e
1.2 So
f
1
·
m
∈
[0, 2B). Try
f
1
with the oracle, i.e. send
f
1
·
c
2
3
(mod
n).
Any number less than
B
encoded into
k
octets will start with a ‘00’h octet.
(f
e
·
c)
d
≡
f
ed
·
c
d
≡
f
·
m
(mod
n)
1.3a If the oracle indicates “<
B”:
This implies
f
1
·
m
∈
[0,
B),
so 2f
1
·
m
∈
[0, 2B).
Set
f
1
←
2f
1
and go back to step 1.2.
1.3b If the oracle indicates “≥
B:
This implies
f
1
∈
[B, 2B) for a known (even) multiple
f
1
. Rephrasing this
gives
f
2
1
·
m
∈
[
B
, B)
for a known multiple
f
2
1
. Now move to the next step.
2
Step 2:
Start with a multiple
f
2
such that
f
2
·
m
is just less than
n
+
B
for
the maximum possible
m.
Keep increasing this multiple until the oracle returns
“<
B”.
For each multiple
f
2
the possible values of
f
2
·
m
span a single boundary
point at
n.
2.1 We have
f
2
1
·
m
∈
[
B
, B).
Let
f
2
=
n+B
·
f
2
1
.
2
B
2.2 So
f
2
·
m
∈
[
n
, n
+
B).
Try
f
2
with the oracle.
2
2.3a If the oracle indicates “≥
B”:
This implies
f
2
·
m
∈
[
n
, n),
so (f
2
+
f
2
1
)
·
m
∈
[
n
, n
+
B).
2
2
Set
f
2
←
f
2
+
f
2
1
and go back to step 2.2.
2.3b If the oracle indicates “<
B”:
This implies
f
2
·
m
∈
[n,
n
+
B)
for a known multiple
f
2
. Now move to the
next step.
As
f
2
increases at iterations through step 2.3a the lower bound on
f
2
·
m
increases, eventually exceeding
n
when
f
2
=
2n
·
f
2
1
. Branch 2.3b must occur
B
at or before this multiple. That is, step 2 will always terminate — taking at most
n
B
oracle queries.
Step 3:
Try multiples
f
3
that give a range for
f
3
·
m
about 2B integers wide
and spanning a single boundary point. Each oracle response will half the range
back to a width of about
B
integers, so the next multiple is approximately twice
the previous value.
3.1 We have
f
2
·
m
∈
[n,
n
+
B).
Rephrasing, we have a multiple
f
2
and a range [m
min
, m
max
) of possible
m
n
values, where
m
min
=
f
2
,
m
max
=
n+B
and
f
2
·
(m
max
−
m
min
)
≈
B.
f
2
3.2 Choose a multiple
f
tmp
such that the width of
f
tmp
·
m
is approximately 2B.
2B
f
tmp
=
m
max
−m
min
. This value is about double the previous multiple.
3.3 Select a boundary point,
in
+
B,
near the range of
f
tmp
·
m.
f
·m
i
=
tmp
n
min
.
3.4 Choose a multiple
f
3
such that
f
3
·m
spans a single boundary point at
in+B.
f
3
=
min
. This gives
f
3
·
m
∈
[in,
in
+ 2B) (though the upper bound is
min
only approximate).
f
3
is approximately equal to
f
tmp
. Try
f
3
with the oracle.
3.5a If the oracle indicates “≥
B”:
This implies
f
3
·
m
∈
[in +
B, in
+ 2B).
Set
m
min
←
in+B
and go back to step 3.2.
f
3
3.5b If the oracle indicates “<
B”:
This implies
f
3
·
m
∈
[in,
in
+
B).
Set
m
max
←
in+B
and go back to step 3.2.
f
3
Each answer from the oracle in step 3 selects either the top or bottom half
(approximately) of the
f
3
·
m
range, halving the range of possible
m
values.
Eventually the range in which
m
lies narrows to a single number, which is the
desired plaintext. At this point
f
3
≈
B
= 2
8(k−1)
.
The description of step 3 above does not provide a proof that those particular
choices of multiples, boundary points and interval widths will always work for
any key or message. Minor variations on these choices can make the attack
algorithm marginally more ecient. See [1] for a more mathematically rigorous
analysis of a closely related problem.
3.1
Complexity
Steps 1 and 3 approximately halve the range of possible
m
values with each
iteration so between them they take about log
2
B
= 8(k
−
1) oracle queries.
4
n
Step 2 takes at most
B
oracle queries (which must be
≤
256), and half this
number on average.
RSA moduli are typically chosen to be exact multiples of 8 bits long, e.g.
1024-bit moduli are far more prevalent than, say, 1021-bit moduli. Hence, for
n
typical keys
B
is in the range (128, 256], so step 2 will typically take on the
order of 100 oracle queries.
For a 1024-bit RSA key the attack requires about 1100 oracle queries, for a
2048-bit key about 2200.
3.2
When
n <
2B
The attack procedure described above assumes 2B
< n.
If this is not the case,
an indication from the oracle of “<
B”
when
f
= 2 narrows the range in which
f
·
m
lies not to a single region, but to a pair of regions:
f
·
m
∈
[0,
B)
[n, 2B).
The range in which
m
is known to lie is reduced is total size, but is no longer
conned to a single interval. This somewhat complicates the decision about
which multiples to try but an adaptive chosen ciphertext attack will still work.
The chosen ciphertext attack against RSA block type 2 padding had a similar
issue — see [1] for a full analysis.
3.3
Comparison to the RSA Block Type 2 Attack
Analysis in [1] of the number of oracle queries required for a chosen ciphertext
attack found an expression with two terms: the rst term inversely proportional
to the probability that a random integer from [0,
n)
conforms to the encoding
format; the second term proportional to log
2
n.
The rst term dominates for RSA
block type 2 padding (making the number of required queries quite dependent
4
Reduction of the range of possible
m
values in step 2 slightly reduces the number of
oracle queries required during steps 1 and 3, but this number also slightly increases
(by a few percent) as the ranges in step 3 not being exactly centred on boundary
points.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin