Suppose Alice is a client of Bob’s stockbrokering firm. She needs to send Bob on

Question

Suppose Alice is a client of Bob’s stockbrokering firm. She needs to send Bob one of two messages: BUY or SELL. The attacker, Cathy, enciphers both mes- sages with Bob’s public key. When Alice sends her message, Cathy compares it with her messages and sees which one it matches. A) consider the case of Alice and her stockbroker, Bob. Suppose they decide not to use a session key. Instead, Alice pads the message (BUY or SELL) with random data. Explain under what conditions this approach would be effective. Discuss how the length of the block affects your answer. B) show how Cathy attacks in the case. Then, show why using random pads can defeat the attack. Then, discuss how the length of the random pads affects the security.

Explanation / Answer

We now sketch Vaudenay’s attack from [Vau02]
which will serve as a warm-up for later discussion.
We also show an improvement which deterministically
finds the length of the padding in lg(b) oracle
queries, where b is the number of bytes per block.
CBC-PAD. The well-known CBC-PAD function
[BR96] is byte-oriented: CBCPAD : ({0, 1}8)+
({0, 1}n)+. Assume |M| is a multiple of 8, and let
n = 8b (for virtually all real block ciphers, b is at
most 32). Let p = ||M|| mod b, so p is the number
of bytes we must pad (assuming we wish to add the
least possible amount of padding). If p = 0, we set
p = b. Finally, we write p as a byte and append it p
times to the end of M. So if there is one byte left to
pad, we append a single 01 to M; if there are two
bytes of pad needed we append 02 02 to M, and
so forth. Clearly this method is reversible: given
CBCPAD(M) we can uniquely recover M.
Although CBCPAD(·) is reversible, it is not bijective:
what should the receiver do after decryption
if he finds that the recovered plaintext is not in the
function’s range? That is, what is the proper action
if the padding is invalid? This of course depends on
an implementation detail. Some protocols specify
that the session be torn down (SSL/TLS), others
just log the error (ESP [KA98]), and others return
an error message (WTLS [Wir01]). Vaudenay recently
made the observation that if one can ascertain
somehow the padding error status, it can be
used as a side-channel to mount a chosen-ciphertext
attack in the symmetric-key setting [Vau02]. He
showed how, given an oracle O which accepts a ciphertext
and returns either VALID or INVALID depending
on whether the corresponding plaintext is
properly padded, one can recover the underlying
plaintext. His attack requires a single ciphertext,
and a number of oracle queries proportional to the
number of bytes in the padded message.


EK EK
M
C1 C
Figure 1: CBC Mode Decryption. Fixing C and flipping any bit of C1 flips the corresponding bit
of M.
The Attack. Let’s say we have an oracle O as
described above: O accepts ciphertexts, decrypts
using CBC under the secret key K, and recovers
the corresponding plaintext M. If M is correctly
padded (ie, M = CBCPAD(M) for some M), then
O returns VALID. Otherwise O returns INVALID.
We now mount a chosen-ciphertext attack on CBC
Mode encryption. (A point of clarification: normally
a “chosen-ciphertext attack” implies that we
have access to a decryption oracle which supplies
the plaintexts for ciphertexts of our choice. Here
we have something different: an oracle which does
accept ciphertexts but returns only a bit. It is important
to keep this distinction in mind.)
The attack works as follows: we obtain some ciphertext
C under the secret key K. For simplicity,
suppose C is two blocks (IV, C1). (The attack generalizes
easily to longer ciphertexts.) As shown in
Figure 1, the oracle will compute the CBC Mode decryption
of C in the standard way, and any changes
to IV will cause changes to the plaintext block M1.
Initially, M1 is a correctly-padded block of plaintext.
However, by manipulating the bits of IV we
can cause predictable changes within M1 and infer
a great deal about its contents.
Vaudenay’s attack works in two phases. First he
randomly flips bits in IV until O(C) = VALID.
Once this occurs, we know we must have induced
an M
1 with a proper CBC-PAD. That is, our induced
M
1 must end in 01, or 02 02, or 03 03
03, etc. The probability that each occurs is 1/28,
or 1/216, or 1/224, etc., respectively. The event
O(C) = VALID should therefore occur in at most
128 expected queries, and once it does it is highlylikely
that we induced a 01 in the final byte of M
1.
(The less-probable cases can be detected with a few
additional oracle queries.) And once we know the
value of the final byte in the induced M
1, we know
the value of the final byte in M1: say IV is the IV
which induced a 01 in the final byte ofM
1. Then the
final byte of M1 is simply the final byte of IV 01.
Vaudenay then iterates the method using the above
technique as a subroutine. He therefore decrypts a
block in about 128b expected oracle queries (recall
b is the number of bytes per block).
An Improvement. While our main aim in this paper
is to show how widely we can generalize the
above ideas, we first note a simple improvement
to the attack above which greatly improves its efficiency
for short messages.
Suppose we again have a padding oracle O and a
ciphertext C = (IV, C1). We know that M1 has
a valid CBC-PAD as before. We mount a binary
search to discover which of the b possible pad-values
was used, as follows: first, notice that inducing a
change in any padding byte (except the final byte)
of M1 will always cause O to return INVALID. Also
notice that inducing a change in any message byte
(ie, a non-padding byte) of M1 always causes O to
return VALID. We may therefore perform a binary
search by altering a single byte at a time. Number
the bytes of IV starting from the right end, beginning
from 1. That is, write IV = ibib1 · · · i2i1,
where each ij is a byte. Let IVm be equal to IV but
with its m-th byte complemented (complementation
is an arbitrary choice; any change to the m-th byte
will do). That is, IVm = ib · · · im+1imim1 · · · i1,
where im denotes bit complementation. We use values
of m from b down to 2 to find the length of the
padding in M1. Variables IV, C1, and O are assumed
to be global, and the algorithm is initially
invoked with Find-Len(b, 1).
Find-Len(i, j)
if i = j then return i
m i+j
2

if O(IVm, C1) = INVALID then
Find-Len(i,m)
else
Find-Len(m 1, j)
The algorithm finds the length of the padding in
lg(b) steps where b is the length of a block in bytes
and lg() is log2(). So our improved algorithm first
finds the length of the padding as above, then uses
Vaudenay’s method on the remainder of the block.
If we assume the length of the padding is uniformly
distributed between 1 and b, this new algorithm
finds the plaintext associated to a padded block in
an expected 64b + lg(b) oracle queries. This is a
substantial improvement for short messages only.
4 Other Padding Methods
While CBC-PAD is certainly a common byteoriented
method, there are several other schemes in
common use, and some natural ones not in use. We
now survey the most natural schemes and classify
their vulnerabilities to this type of attack. The purpose
here is to demonstrate that virtually all common
padding schemes are vulnerable to some kind of
attack based on “valid padding” side-channels under
unauthenticated CBC Mode encryption. Our
results are summarized in Figure 2.
For each scheme listed here, we focus on attacking
single block messages where the ciphertext looks like
(IV, C1). This generalizes easily to multi-block messages
since we can attack each block individually by
using the prior block of ciphertext as an IV. That
is, given ciphertext (IV, C1, C2, · · ·), we attack block
Cj by attacking the two-block ciphertext (Cj1, Cj )
where here Cj1 is acting as the IV.
ESP Padding (ESP-PAD). The padding scheme
for IPSec’s Encapsulated Security Payload is similar
to the CBC-PAD method we saw above. It is a
reversible byte-oriented padding scheme; if we have
to pad p > 0 bytes, we append the bytes 01 02 ...
up to p. As mentioned in [Vau02], a valid-padding
oracle for this method also allows recovery of the
plaintext; our improvement from Section 3 works
here as well.
XY Padding (XY-PAD). This byte-oriented
method uses two distinct public constant bytevalues
X and Y . We transform M by first appending
X one time (mandatory), then adding the necessary
number of Y values. Clearly this method is
reversible: M is easily recovered after padding by
removing all trailing Y bytes and the last trailing
X byte. And once again, this method succumbs to
the attacks described above, including our improvement
from Section 3, although in this case we must
take care to avoid converting X to Y when we perform
the IV alteration; since we are not constrained
in how we make this alteration, and since we know
the public values X and Y , we can simply avoid this
problem.
Obligatory 10 Padding (OZ-PAD). The socalled
“obligatory 10 padding” is a bit-oriented
padding scheme; it works as follows: append a 1-
bit to M (mandatory) and then zero or more 0-bits
as necessary to fill out the block. This is the bitoriented
version of the XY padding method above,
and is similarly reversible: remove all trailing 0-bits
and the last 1-bit.
But suddenly it seems the attacks we discussed
above no longer apply. The key difference is this:
virtually every plaintext string is a correctly-padded
string since the only requirement for validity is that
there is a 1-bit somewhere.
This is encouraging in some sense: many standards
recommend obligatory 10 padding and therefore
seem more robust against these side-channel attacks.
However, there is one plaintext block which
is invalid under this padding definition: 0n. Suppose
O were an oracle which accepts CBC-encrypted
ciphertext and returns VALID whenever the final
block of the corresponding plaintext contained at
least one 1-bit, and INVALID when it was

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.