Security 2002 Paper
[Security '02 Tech Program Index]
Pp. 327338 of the Proceedings  
NOTE: If the mathematical symbols on this page are not rendered correctly, please go here for instructions on adjusting your browser settings.
\Large SideChannel Attacks on Symmetric Encryption Schemes:
\The Case for Authenticated Encryption
SideChannel Attacks on Symmetric Encryption Schemes:
The Case for Authenticated Encryption
John Black
University of Nevada, Reno
jrb@cs.unr.edu, http://www.cs.unr.edu/~jrb
Hector Urtubia
University of Nevada, Reno
urtubia@cs.unr.edu, http://mrbook.org
Abstract
Vaudenay recently demonstrated
sidechannel attacks on a common encryption scheme, CBC Mode encryption,
exploiting a
``valid padding'' oracle [Vau02]. Mirroring the sidechannel attacks
of Bleichenbacher [Ble98] and Manger [Man01]
on asymmetric schemes, he showed that symmetric
encryption methods are just as vulnerable to sidechannel weaknesses when
an adversary is able to distinguish between valid and invalid ciphertexts.
Our paper demonstrates that
such attacks are pervasive when the integrity
of ciphertexts is not guaranteed.
We first review Vaudenday's attack and give a slightly more efficient version
of it. We then generalize the attack in several directions, considering
various padding schemes, other symmetric encryption schemes, and other
sidechannels, demonstrating attacks of various strengths against each.
Finally we argue that the best way to prevent all of these attacks
is to insist on
integrity of ciphertexts [BN00] in addition to semantic security
as the ``proper'' notion of privacy for symmetric encryption schemes.
1 Introduction
Following the chosenciphertext attack of Bleichenbacher,
RSA PKCS #1 v.1 was abandoned in favor of a scheme with chosenciphertext
security (CCA) [Ble98,Pub98].
It is now expected that any new publickey cryptosystems will provide
CCA security. However most symmetric
encryption schemes attain, at best, semantic security against
chosen plaintext attacks [BDJR97].
Vaudenay recently demonstrated a sidechannel attack against
CBC Mode encryption with CBCPAD [Vau02,BR96].
Given an oracle
which reveals whether or not the plaintext (corresponding to some altered
ciphertext) is correctly padded, he showed that
one can efficiently recover the plaintext.
A reasonable reaction to this attack is to seek other padding methods
or other
encryption schemes which do not succumb to this particular attack. However,
as we show, this type of weakness is pervasive: it occurs for many
natural padding schemes, and in most common encryption schemes. Vaudenay's
paper focuses on the CBCPAD padding method and comments on a few others.
In this paper
we examine several classes of padding schemes and show it is actually quite
rare for CBC to retain semantic security
in the presence of a ``valid padding'' oracle
when using any of these schemes, including
the commonlyused 10^{*} padding where one pads by appending
a single 1 bit and then zero or more 0 bits.
We also show that all other commonlyused symmetric encryption schemes
are similarly vulnerable in the prescence of a ``valid padding''
oracle.
It is mostlikely possible to get around these weaknesses by ridding
ourselves of
the oracle in one way or another. However one
can easily imagine other oracles which might arise in practice which
would provide similar powers to the adversary if he retains the
ability to to freely induce
predictable changes in the plaintext via modification of the ciphertext.
For example,
imagine a cryptographic relay which accepts ciphertext encrypted by one
scheme and outputs ciphertext under another [JDK^{+}91]. If the
first scheme uses some padding method and the second is lengthrevealing,
we effectively have an oracle which divulges the length of the
padding used by the first scheme.
There are doubtless other examples as well.
Therefore our view is this: these weaknesses are not faults of padding
schemes or relays or anything of this nature; they follow directly from
the fact that an adversary can reliably and efficiently produce valid
ciphertexts which have a predictable
relationship with the underlying plaintext,
even if he knows virtually nothing about the plaintext.
Several schemes have been proposed to provide authenticity of
ciphertexts at a very low cost [BN00,Jut01,RBBK01]. Our hope is that,
similar to the publickey domain, researchers and practitioners will
insist on this stronger notion of security for symmetric encryption to
obviate the simple weaknesses listed above.
CONTRIBUTIONS.
This paper makes a number of observations concerning the power of
possessing a validpadding oracle.
Our starting point is the attack on CBC Mode
encryption with CBCPAD from [Vau02]. We
begin by reviewing this attack. Then
 We describe an improvement to the attack which finds the
length of the padding in lg(b) oracle queries whereas
[Vau02] used an expected 128b queries (here b is the number of
bytes in a block).
 We generalize padding methods by exploring other types
of natural schemes which variously resist and succumb to similar attacks.
 We exhibit a padding method which essentially removes the oracle,
and therefore defeats the attack altogether.
 We generalize the attack to other
encryption schemes showing that other common methods
for symmetric encryption (CTR, OFB, CFB, and stream ciphers) all possess
the required weaknesses which permit this type of attack.
Finally, we argue that such sidechannels are bound to crop up again
and again as long as we allow the adversary to freely manipulate ciphertexts,
and we argue in favor of adopting the combination of
chosenplaintext security and integrity of ciphertexts [BN00]
as the standard requirement for symmetric encryption schemes, even when
privacy is the only goal.
RELATED WORK.
CBC Mode encryption has the property that flipping a particular bit in
the ith block of ciphertext will flip the same bit in the i+1st
block of underlying plaintext. The fact that this property can be
exploited by attackers has been known for some time.
Bellovin published an attack
on CBC where the IV was altered to effect a change in the first block
of the received plaintext [Bel96]. Also in [Bel96], an
attack (very similar to the attacks in
this paper) is described which recovers plaintext bits by
sending altered ciphertexts to a TCP peer which then acts as a validity
oracle for each packet by either dropping it or returning an ACK for it.
A cleaner example of this attack is described in an attack on WEP
by Borisov, Goldberg, and Wagner [BGW01].
Bleichenbacher demonstrated that
sidechannels in the asymmetric setting could be used
to mount a chosenciphertext
attack against RSA PKCS #1 v.1 [Ble98]. Bleichenbacher's sidechannel
was a ``valid formatting'' oracle similar in spirit to the ``valid
padding'' oracle used by Vaudenay.
Manger followed this
by showing how RSA PKCS #1 v.2, a scheme with chosenciphertext security
(in the random oracle model), could be similarly exploited assuming
a different sidechannel
[Man01]. Manger's sidechannel requires an oracle
indicating that an error occurred
between the decryption and integritycheck phases
of the algorithm. In a more theoretical setting, Krawczyk showed how
a stream encryption mode (under an unusual plaintext encoding) combined
with a MAC would yield a sidechannel attack based on message validity
if the order was encode, then authenticate, then encrypt [Kra01].
His goal was to show that this ordering of primitives was not generically
secure.
Vaudenay was the first to show that message padding
might create
similar sidechannels under CBC Mode encryption [Vau02]. His
attack requires an oracle indicating whether or not the padding of an
underlying plaintext is valid.
2 Preliminaries
NOTATION.
For any nonnegative integer n, let {0,1}^{n} represent the set of
bit strings of length n. Let e represent the empty string.
For two strings A and B we write
A  B or simply AB to denote their concatenation.
For the XOR of A and B we write A Å B.
Let A denote the length of A in bytes, and A the
length of A in bits.
We write A[i] to mean the ith bit of A, counting from zero,
starting from the leftmost bit of A. We write A[i¼j] to mean
the substring of A starting at position i and ending at position j.
In general, if S is a set we write S^{+} to mean 1 or more repetitions
of elements from S; that is, the set
{s_{1} s_{2} ¼s_{m}  m > 0, s_{i} Î S, 1 £ i £ m}.
A function family from nbits to nbits is a map
E:K×{0,1}^{n}® {0,1}^{n} where K is
a finite set of strings, typically the set of strings all of some
fixed length. It is a
block cipher if each E_{K}(·) = E(K,·) is a permutation.
We can build an encryption scheme from a block cipher using any
of various standard modes of operation.
CBC MODE ENCRYPTION.
Given
a block cipher E : {0,1}^{k} ×{0,1}^{n} ® {0,1}^{n}, a kbit
blockcipher key K,
and some message M Î ({0,1}^{n})^{+}, we write M as the concatenation
of l strings each nbits long, M=M_{1} M_{2} ¼M_{l}. To encrypt
M under key K, we randomly select an nbit value, the IV, and
set C_{0} ¬ IV. We then compute C_{i} ¬ E_{K}(M_{i} Å C_{i1})
for each 1 £ i £ l. The ciphertext is
(IV, C_{1} C_{2} ¼C_{l}).
In the standard model, CBC is provablysecure against chosenplaintext
attack with good bounds: assuming
the underlying block cipher is ``good,'' an adversary has little
chance to distinguish the CBC Mode encryption of a given plaintext from
the CBC Mode encryption of random bits. (For a precise definition and
proof, see [BDJR97].)
PADDING.
The above description assumes that the length of M is a
multiple of the block size n.
In practice this may not be the case, and therefore
it is common to apply a padding function
PAD: {0,1}^{*} ® ({0,1}^{n})^{+} to M.
We say a padding function is reversible if the function
is injective; in other words, reversible means one can always uniquely
recover M
given PAD(M). Most applications require the padding function to be
reversible.
Often the padding function brings M up to the next multiple of n,
but nothing precludes expanding M even further; indeed, SSL will
sometimes add several blocks of padding when using CBCPAD.
We consider two classes
of padding: byteoriented padding and bitoriented padding.
Byteoriented
padding functions assume
that both n and M are multiples of 8. Bytes are
then appended to the end of M in some welldefined manner to bring
its length up to a multiple of n. Bitoriented padding functions
take a message M of any bitlength and append bits to M to
bring M up to a multiple of n.
3 The Attack of Vaudenay and an Improvement
We now sketch Vaudenay's attack from [Vau02]
which will serve as a warmup 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.
Figure 1: CBC Mode Decryption.
Fixing C_{l} and flipping any bit of C_{l1} flips the
corresponding bit of M_{l}.
CBCPAD.
The wellknown CBCPAD function [BR96] is byteoriented:
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 sidechannel to mount a chosenciphertext
attack in the symmetrickey
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.
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 chosenciphertext
attack on CBC Mode encryption. (A point of clarification:
normally a ``chosenciphertext 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, C_{1}).
(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 M_{1}. Initially, M_{1} is a correctlypadded
block of plaintext. However, by manipulating the bits of IV we can
cause predictable changes within M_{1} 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 CBCPAD. 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/2^{8}, or 1/2^{16}, or
1/2^{24}, 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 lessprobable 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 M_{1}: say IV¢
is the IV which induced a 01 in the final byte of M¢_{1}.
Then the final byte of M_{1} 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, C_{1}). We know that M_{1} has a valid CBCPAD as before.
We mount a binary search to discover which of the b possible
padvalues was used, as follows: first, notice that inducing a change
in any padding byte (except the final byte) of M_{1} will always cause
O to return INVALID.
Also notice that inducing a change in any message byte (ie, a nonpadding
byte) of M_{1} 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
= i_{b} i_{b1} ¼i_{2} i_{1}, where each
i_{j} is a byte. Let IV_{m} be equal to
IV but with its mth byte complemented
(complementation is an arbitrary choice; any change to the mth byte
will do). That is, IV_{m} = i_{b} ¼i_{m+1}[`(i_{m})] i_{m1} ¼i_{1}, where [`(i_{m})] denotes bit complementation.
We use values of m from b down to 2 to find the
length of the padding in M_{1}.
Variables IV, C_{1}, and O are assumed to be global, and the
algorithm is initially invoked with FINDLEN(b,1).
FINDLEN(i,j)
if i=j then return i
m ¬ é[(i+j)/2] ù
if O(IV_{m}, C_{1}) = INVALID then
FINDLEN(i, m)
else
FINDLEN(m1, 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
log_{2}(). 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 CBCPAD 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'' sidechannels 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, C_{1}). This generalizes easily
to multiblock messages since we can attack each block individually
by using the prior block of ciphertext as an IV. That is, given
ciphertext (IV, C_{1}, C_{2}, ¼), we attack
block C_{j} by attacking the twoblock ciphertext (C_{j1}, C_{j})
where here C_{j1} is acting as the IV.
 Bit  Byte  Loss of  # Queries to Find  Exp # Queries to 
Scheme  Oriented  Oriented  Semantic Security?  Padding Length  Recover Plaintext

 CBCPAD   ×  Y  lg(b)  64b + lg(b) 
ESPPAD   ×  Y  lg(b)  64b + lg(b) 
XYPAD   ×  Y  lg(b)  64b + lg(b) 
OZPAD  ×   Y  n/a  2^{8b1} 
BOZPAD   ×  Y  lg(b)  64b + lg(b) 
PAIRPAD   ×  Y  n/a  2^{8b8} 
ABYTPAD   ×  N  n/a  n/a 
ABITPAD  ×   N  n/a  n/a 
Figure 2: Security in the Presence of a ValidPadding Oracle.
For each padding scheme in the paper, we list which induce a loss
of semantic security in the presence of a validpadding oracle. Also, when
the attack first obtains the padding length, we list the number of queries
needed to find it for a single block (in terms of b,
the number of bytes per block). The expectation in the final column is
computed assuming all plaintext lengths are equally likely.
ESP PADDING (ESPPAD).
The padding scheme for IPSec's Encapsulated Security Payload is
similar to the CBCPAD method we saw above. It is a reversible
byteoriented padding scheme; if we have to pad p > 0 bytes, we append
the bytes 01 02 ... up to p.
As mentioned in [Vau02],
a validpadding oracle for this method also allows recovery of the
plaintext; our improvement from Section 3 works here as well.
XY PADDING (XYPAD).
This byteoriented 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 (OZPAD).
The socalled
``obligatory 10^{*} padding'' is a bitoriented padding scheme; it
works as follows: append a 1bit to M (mandatory)
and then zero or more 0bits 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 0bits and the last 1bit.
But suddenly it seems the attacks we
discussed above no longer apply. The key difference is this: virtually every
plaintext string is a correctlypadded string since the only requirement for
validity is that there is a 1bit somewhere.
This is encouraging in some sense: many standards recommend obligatory
10^{*} padding and therefore seem more robust against these sidechannel
attacks. However, there is one plaintext block which is invalid under this
padding definition: 0^{n}. Suppose O were an oracle which accepts
CBCencrypted ciphertext and returns VALID whenever the final block
of the corresponding plaintext contained at least one 1bit, and
INVALID when it was all zeroes. It's clear that this, once again,
enables one to entirely recover the plaintext,
but there is
no efficient method for recovering the plaintext.
The problem is this: in order to get the oracle to report INVALID we
must essentially ask O(IV¢, C_{1}) where IV¢ = IV Å M_{1}. In
other words, we must guess what M_{1} is in order to get
a response of INVALID. Therefore, our oracle is simply answering
``yes'' or ``no'' to our guesses about what the plaintext block is.
If we assume the plaintext is uniform and random, it will take an expected
2^{8b1} guesses to guess correctly.
However, this is not to say that such an oracle is useless. In fact,
in the presence of such an oracle, CBC Mode encryption does not retain
semantic security. One incarnation of semantic security plays the
following game: we submit a value to an oracle and it encrypts either
the value we submitted or some random value. If we can guess which choice
it made with probability much larger than 1/2, we win. Clearly in
the presence of our validpadding
oracle we can win this game for CBC encryption
with probability essentially 1.
We merely ask the encryption oracle to encrypt some random block M_{1},
it returns ciphertext (IV, C_{1}), then if O(IV Å M_{1}, C_{1}) = INVALID
we know M_{1} was (with overwhelming probability) the value encrypted.
But what does this mean in practice? Well, if we have a set of candidate
blocks which we suspect might match the plaintext for a given ciphertext
block, the validpadding oracle will allow us to determine which of them,
if any, is the correct one. This is perhaps not as farfetched as it
sounds: naturallanguage plaintexts commonly contain salutations,
addresses, and other standard sections in their bodies. Structured
documents will often contain headers with a wellknown format. It should
be desirable to hide all of this information!
As a final comment: one could eliminate this problem by simply defining
the block 0^{n} to be a valid block of plaintext and (say) removing it.
But we must then also be careful to define what happens to the preceding
block (if any). Do we also remove padding bits from it or do we stop?
One virtue of 10^{*} padding is that it is simple; adding complexity to
its definition merely increases the chance that we will implement
O via implementation errors.
A BYTEORIENTED VERSION OF 10^{*} PADDING (BOZPAD).
It might be tempting to implement 10^{*} padding in a byteoriented manner
by appending 0x80 once and then as many 00 bytes as
needed to fill out the block.
This is probably how most applications generate padding when they know
the plaintext will already be bytealigned and need to use 10^{*} padding.
If, however, the receiver depends on this, and that dependence
is externally manifested, we once again have a useful validpadding oracle.
In other words, if the receiver somehow indicates whether or not the
padding is 80h followed by zero or more 00 bytes, we
have a specific instance of the XY Padding method mentioned above.
ARBITRARYPAIR PADDING (PAIRPAD).
An interesting try at avoiding the weaknesses involved with XY Padding
is to allow any distinct values X and Y.
The sender is
still free to use whatever values he wishes, and they need not be random
provided they are not fixed public constants. Once the sender decides
on the X and Y values, he pads by appending X once and Y
one or more times to bring the message up to the desired length.
(Here we must require Y be appended at least once else the padding
method is not reversible.)
This padding method is identical to XYPAD;
the difference is in how the padding is removed.
The receiver allows any two distinct values, so
the algorithm to remove the padding is to first remove all matching
trailing byte values at the end of the string, and then also remove
the byte preceding these matching values. This nearly removes the oracle
since, like 10^{*} padding, nearly all plaintext blocks are correctly
padded. However, again like 10^{*} padding, there remains the case where
all bytes are equal in a block. If we have an oracle telling us when
all bytes are equal, we can again mount an attack similar to the one
described for 10^{*} padding. But random guessing will not be efficient
here since, assuming random and uniform plaintexts, it would take an expected
2^{8b8} queries just to get an INVALID response from the oracle.
(Although we cannot tell which byte is repeated in the plaintext
when we get an INVALID from the oracle, we know there
are only 256 possibilities left
for the plaintext andassuming it has some structurewe should
be able to recover the plaintext at this point.)
ARBITRARYTAIL PADDING (ABYTPAD).
A better byteoriented padding method is this:
the sender examines the
last byte X of the message M. He picks an arbitrary distinct
bytevalue Y and uses Y to pad (if M is the empty string, he picks
any bytevalue for Y.) He then pads M with Y, adding one or more
bytes of Y to the end of M as desired (note that he must add at least
one!).
The receiver merely removes all matching trailing bytes until either
a distinct byte is found (which is left intact) or the empty string is
reached.
This method is clearly reversible, and all plaintexts are valid so there
is no attack of the type mentioned in this paper. The oracle has been
removed entirely.
Notice that the sender need not generate random values here:
he may instead follow a welldefined rule such as
 If the final byte of M is 00, pad with 01.
 In all other cases (including M = e) pad with 00.
As before, the receiver cannot depend on any such rule,
since otherwise we may once again implement some oracle suitable for
use in an attack.
A BITORIENTED ANALOG (ABITPAD).
There is an obvious bitoriented analog here as well: the sender
examines the last bit of M and pads with repetitions of the opposite bit,
always adding at least one bit of padding.
For M = e he pads with 0bits. Once again, all plaintexts are valid
and the oracle is removed.
PADDING THE CIPHERTEXT.
Another simple approach to removing the oracle is to use some
lengthpreserving variant of CBC Mode. There are several ways of
doing this, with ``ciphertext stealing'' probably the most wellknown
[BR96]. Since there is no padding, there is no padding oracle,
and the above attacks vanish.
If there is still a need to pad (because, for example,
we require the ciphertext end on an alignment boundary), we could then
pad the ciphertext.
One problem with this approach is that the length of the plaintext is
divulged to a bit granularity and this may be undesirable. (See the
next section for further discussion.)
5 StreamBased Schemes
Thus far we have focussed exclusively on CBC Mode encryption.
While CBC Mode encryption is certainly ubiquitous, it is by no means the
only symmetric encryption scheme used. In fact, the RC4 stream cipher
is often the encryption method of choice for SSL/TLS.
Other blockcipher modes generate streams used as onetime pads as well:
OutputFeedback Mode (OFB), CipherFeedback Mode (CFB), and Counter
Mode (CTR) all fall into this class [MvV96].
It is therefore natural to ask if the padding attacks mounted against CBC apply
to these schemes as well. The answer is: maybe.
The reason we say ``maybe'' is because padding may or may not be used with
streambased encryption schemes. When encrypting with a
pseudorandom bitstream, we are free to use exactly the number of bits
needed; there is no need to pad. However in practice we find it is quite
common to add padding even when using streambased schemes. The motivation
is this: when performing encryption we are normally willing to divulge
two things: (1) communication is taking place, and (2) the length of
this communication.
But for short strings we may wish to slightly obscure the length of the
communication. As an extreme example, if we are encrypting a single
bit, an adversary quickly knows the plaintext is one of only two values.
Padding serves as a way to at least partially obscure the length of the
plaintext.
If padding is used, the potential for a validpadding sidechannel
resurfaces. This arises because streambased encryption is simply
the XOR of the plaintext with a pseudorandom bitstream (Figure 3).
Therefore, as with CBC Mode, we may flip plaintext bits merely by
flipping the corresponding ciphertext bits. The only difference here
is that in CBC Mode we flipped bits in C_{l1} to affect bits in
M_{l}, and here we flip bits in C_{l} instead.
Figure 3: StreamBased Decryption.
Similar to CBC, flipping bits in C_{l} flip the corresponding bits in M_{l}
independent of the key stream used for decryption.
Therefore we see our current collection of attacks is not restricted
solely to CBC Mode encryption but will occur with several common schemes
if the plaintext is padded.
In [Vau02] we find further examples of modes (all CBC variants) which
succumb to padding attacks. The lesson here is that none of these modes
is trying to prevent an adversary from manipulating the ciphertext, and the
fact
there exist attacks against a wide variety of padding schemes and
encryption schemes based on manipulation of the ciphertext should be no
great surprise.
6 Other SideChannels
All prior attacks considered how to exploit a validpadding oracle
to recover the underlying plaintext for any given ciphertext, assuming
the use of a variety of padding methods.
But given the power to
freely and predictably alter the underlying plaintext via manipulations
of the ciphertext, one might expect that a variety of other oracles
would be equally useful to an attacker. In this section we describe
an oracle which divulges the bitlength of an underlying plaintext and
we show that such an oracle would also result in highlyefficient attacks.
A LENGTHREVEALING ORACLE.
A cryptographic relay is a device which accepts ciphertext under one
scheme and outputs ciphertext under another (usually with a different
key). Probably the most natural setup is where the incoming and
outgoing schemes are the same, but it is certainly conceivable that
they might be different. Routers which handle a variety of physicallayer
network
protocols are common, so a secure router might handle a variety of
cryptographic protocols.
Imagine a relay where the incoming scheme pads the plaintext to a
block boundary but the outgoing scheme uses some lengthpreserving
mode (Figure 4). If an adversary can view the ciphertext
on both sides of the relay, he effectively has an oracle which divulges
the length, within a block, of the underlying plaintext. In the presence
of this oracle, even those padding schemes which resisted validpadding
oracle attacks now succumb.
Consider the following example: suppose the incoming ciphertext block
C_{l} is produced by encrypting plaintext which is padded with
10^{*} padding, but the outgoing ciphertext uses some lengthpreserving
scheme such as CTR Mode. Then we can mount an attack, regardless of the
encryption scheme used, more efficient than any we have seen
thus far.
Using our oracle we know the exact position of the last
trailing 1bit in the underlying ciphertext. Suppose it is in bitposition
i of a plaintext block M_{l},
counting bits from 1 starting on the left end. We then flip bit i
by manipulating the ciphertext appropriately, and submit this to the oracle
which divulges the position of the new rightmost 1bit. In this manner,
we collect up the positions of all the 1bits in w(M_{l}) oracle
queries, where w()
denotes the Hamming weight of M_{l}.
Figure 4: A Cryptographic Relay.
Ciphertext blocks C_{l1} and C_{l} enter the relay as full blocks under
some padded scheme on the
left, but exit as blocks C¢_{l1} and C¢_{l}
under a lengthpreserving scheme on the right.
And even our ``perfect'' ArbitraryTail Padding methods from
Section 4 (ABYTPAD, ABITPAD)
fail in the presence of this oracle, which now leads
us to look for new methods which remain secure in this new setting.
And so on.
It is likely that many innocentlooking oracles could give rise to attacks
in the style above, and it is probably difficult to avoid implementing
such oracles in real systems. However, each attack we examined
depended on the adversary's
ability to freely and predictably alter bits of the plaintext via
manipulation of the ciphertext, and this
ability was granted by each of the symmetric encryption schemes
considered. Perhaps the best way to avoid these attacks is not by
attempting to remove all potentiallydamaging oracles,
but rather to remove the adversary's ability to alter plaintext bits
in the first place. One veryeffective way to accomplish this is
with authenticated encryption.
7 An Argument for Authenticated Encryption
Security experts have long been recommending that encryption always be
accompanied by authentication [Bel96]. Vaudenay and
the present paper lend further support to this recommendation. If it were
impossible for the adversary to produce valid ciphertexts other than
those he has already seen, all attacks mentioned in this paper would vanish.
One might object to the assertion here that authentication is truly
required; after all, we have shown methods in Section 4
which demonstrated that it is possible, with care, to remove
the padding oracle altogether. And it is obviously possible to
avoid implementing the lengthrevealing oracle mentioned in the previous
section.
However if we have learned anything
through this exercise it is that sidechannels like these are probably
difficult to avoid when designing cryptographic protocols. It
``feels'' like the simple choice of how to pad a message before encryption
would have absolutely zero impact on security, but as we have seen this
is potentially untrue.
AUTHENTICATED ENCRYPTION.
Each of the encryption schemes we have discussed meets the minimal
security requirement for privacy: it is
computationally infeasible to distinguish the encryption of a given
message from the encryption of a random string of the same length. This
is socalled ``semantic security'' under chosenplaintext attack
for an encryption scheme, usually abbreviated INDCPA [BDJR97].
However, as we have seen, such a guarantee says nothing about the
difficulty of producing new ciphertexts whose plaintexts are related
to those already seen. A scheme which prevents this is called
``nonmalleable'' [DDN00,BDPR98]. In particular, a nonmalleable scheme
does not allow one to flip bits in the ciphertext and induce
flipped corresponding bits in the plaintext; therefore
it is selfevident that our schemes do not meet
this stronger notion of security.
It is disconcerting to see encryption primitives used as if they
guarantee more than INDCPA. A common example in protocols occurs when
a party receives E_{K}(x) and returns E_{K}(x+1) to ``prove'' he
holds the key K (here E() denotes some encryption scheme and
x is a positive integer).
Normal notions of security do not guarantee such
properties. In fact, an adversary with no knowledge of K
can easily produce E_{K}(x+1) given
E_{K}(x) with many common instantiations of E.
For example, if E is a stream cipher we can merely complement the
least significant bit of E_{K}(x) to produce E_{K}(x+1) with
probability about 0.5 (assuming that x is even with probability
about 0.5 and that it is encoded as a string with
its leastsignificant bit rightjustified in the plaintext).
A notion of security strictly stronger than nonmalleability is the
following mouthful: integrity of ciphertexts with semantic security
against chosenplaintext attacks [BN00]. We will simply call this
``authenticated encryption.''
When we use authenticated encryption, we are guaranteed that (with
overwhelming probability) an
adversary will not be able to take a given ciphertext and manipulate
it to produce a new valid ciphertext. Nor will he be able
to combine two ciphertexts to produce a new valid ciphertext. In fact,
the only valid ciphertexts he will be able to produce are (with
overwhelming probability) repetitions of those he's seen generated
as legitimate traffic. He will not be able to produce any new ones
on his own.
Authenticated encryption does provide the adversary with an oracle
which returns VALID and INVALID for any ciphertexts he produces.
However this oracle will (with overwhelming probability) return INVALID
when given any ciphertext he has tampered with, thus rendering the
sidechannel attacks mentioned above (and indeed, any sidechannel attacks
which depend on ciphertext manipulation) ineffective.
COST OF AUTHENTICATED ENCRYPTION.
There are several ways known for achieving authenticated encryption.
Perhaps the most wellknown is to encrypt the plaintext with any
semantically secure scheme (like CBC Mode encryption), then apply
a Message Authentication Code (MAC) to the resulting ciphertext.
Assuming the MAC is ``strongly unforgeable,'' the resulting scheme
will achieve authenticated encryption [BN00,KY00,Kra01].
How much additional
cost is incurred by the authentication step? The fastestknown
MACs can process messages of moderate length (say, 256 bytes) at around
10 cycles per byte [BCK96,BHK^{+}99], so the additional cost
is quite minimal. This approach also has the advantage of being free
of patents.
Recently there have been several modes of operation which perform
simultaneous encryption and authentication [Jut01,RBBK01,GD94].
Their performance is typically quite good; for example,
OCB Mode [RBBK01] is about 6.5% slower than just CBC Mode encryption,
and is fully parallelizable (whereas CBC Mode is not). It requires about
half the cost of running CBC Mode encryption and CBC MAC (under the
encryptthenMAC method above).
AND IT'S STILL POSSIBLE TO GO WRONG.
The mere use of authenticated encryption does not guarantee that a
particular implementation will avoid inducing sidechannel
oracles. We might leak information during the decryption and integrity
check phases which would be useful to an adversary. In fact,
Manger's attack on OAEP [Man01] was based on precisely this idea.
There are doubtless analogous dangers on the symmetric side if one
is not careful.
As a simple example, suppose on the sending side
we pad then encrypt then MAC, but then on the receiving side
we decrypt, strip the padding, and then
check the MAC on the ciphertext last. Using this unusual ordering, we
might send back an error message about invalid padding before checking
to see if the ciphertext was authentic or not; this scheme would of course
be vulnerable to the types of attacks exhibited in this paper.
The message here is clear: check the authenticity first; if a received
message is inauthentic, reject it without any further processing.
8 Conclusion
The cost of authenticated encryption is quite small and, when properly
implemented, promises to
eliminate a wide variety of sidechannel attacks based on manipulation
of ciphertexts.
Authentication has long been thought of as a separate security goal,
used only when one is concerned about such things as message integrity,
authenticity of origin, and nonrepudiation. It is often regarded
as unnecessary in systems which require only privacy.
But as we have seen, the ability to freely manipulate ciphertexts gives
rise to a wide range of possible attacks based on sidechannels which
presumably cannot be exploited without this ability.
These sidechannels are demonstrably
damaging and it is likely very difficult to avoid constructing them in
real systems.
In light of this, perhaps it is time to view
authentication as a stronglydesirable property of any symmetric
encryption scheme, including those where privacy is the only security goal.
9 Acknowledgements
The authors would like to thank Phil Rogaway for
useful comments and suggestions, and Serge
Vaudenay for providing us with an early draft of his paper.
Kindest thanks to David Wagner for bringing our attention to additional
related work.
We would
also like to thank the USENIX Security '02
program committee for their helpful comments.
References
 [BCK96]

M. Bellare, R. Canetti, and H. Krawczyk.
Keying hash functions for message authentication.
In Advances in Cryptology  CRYPTO '96, volume 1109 of
Lecture Notes in Computer Science, pages 115. SpringerVerlag, 1996.
 [BDJR97]

Mihir Bellare, Anand Desai, Eron Jokipii, and Phillip Rogaway.
A concrete security treatment of symmetric encryption: Analysis of
the DES modes of operation.
In Proceedings of 38th Annual Symposium on Foundations of
Computer Sci ence (FOCS 97), 1997.
 [BDPR98]

Mihir Bellare, Anand Desai, David Pointcheval, and Phillip Rogaway.
Relations among notions of security for publickey encryption
schemes.
In H. Krawczyk, editor, Advances in Cryptology  CRYPTO '98,
volume 1462 of LNCS, pages 232249. SpringerVerlag, 1998.
 [Bel96]

S. Bellovin.
Problem areas for the IP security protocols.
Proceedings of the Sixth USENIX Security Symposium, 1996.
 [BGW01]

Nikita Borisov, Ian Goldberg, and David Wagner.
Intercepting mobile communications: The insecurity of 802.11.
In MOBICOM, pages 180189. ACM, 2001.
 [BHK^{+}99]

J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway.
UMAC: Fast and secure message authentication.
In Advances in Cryptology  CRYPTO '99, Lecture Notes in
Computer Science. SpringerVerlag, 1999.
 [Ble98]

D. Bleichenbacher.
Chosen ciphertext attacks against protocols based on the RSA
encryption standard PKCS #1.
In Advances in Cryptology  CRYPTO '98, volume 1462 of
Lecture Notes in Computer Science, pages 112. SpringerVerlag, 1998.
 [BN00]

M. Bellare and C. Namprempre.
Authenticated encryption: Relations among notions and analysis of
the generic composition paradigm.
In Advances in Cryptology  ASIACRYPT '00, volume 1976 of
Lecture Notes in Computer Science. SpringerVerlag, 2000.
 [BR96]

R. Baldwin and R. Rivest.
The RC5, RC5CBC, RC5CBCPad, and RC5CTS algorithms.
RFC 2040, 1996.
 [DDN00]

D. Dolev, C. Dwork, and M. Naor.
Nonmalleable cryptography.
SIAM Journal on Computing, 3(2):391497, 2000.
Earlier version appeared at STOC '91.
 [GD94]

V. Gligor and P. Donescu.
Fast encryption and authentication: XCBC encryption and XECB
authentication modes.
In Fast Software Encryption, LNCS. Springer, Apr 1994.
(Earlier version: manuscript of August 18, 2000, from
http://www.eng.umd.edu/~ gligor/).
 [JDK^{+}91]

D. Johnson, G. Dolan, M. Kelly, A. Le, and S. Matyas.
Common cryptographic architecture cryptographic application.
IBM Systems Journal, 30(2):130149, 1991.
 [Jut01]

Charanjit Jutla.
Encryption modes with almost free message integrity.
In Advances in Cryptology  EUROCRYPT '01, volume 2045 of
Lecture Notes in Computer Science. SpringerVerlag, 2001.
(Earlier version in Cryptology ePrint archive, reference number
2000/039, August 1, 2000, http://eprint.iacr.org/).
 [KA98]

S. Kent and R. Atkinson.
IP Encapsulating Security Payload (ESP).
RFC 2406, Standards Track, The Internet Society, 1998.
 [Kra01]

Hugo Krawczyk.
The order of encryption and authentication for protecting communicat
ions (or: How secure is SSL?).
In Advances in Cryptology  CRYPTO 2001, volume 2139 of
Lecture Notes in Computer Science, pages 310331. SpringerVerlag, 2001.
 [KY00]

J. Katz and M. Yung.
Complete characterization of security notions for probabilistic
privatekey encryption.
In Proceedings of the 32nd Annual Symposium on the Theory of
Computing (STOC). ACM Press, 2000.
 [Man01]

J. Manger.
A chosen ciphertext attack on RSA optimal asymmetric encryption
padding (OAEP) as standardized in PKCS #1 v2.0.
In Advances in Cryptology  CRYPTO '01, volume 2139 of
Lecture Notes in Computer Science, pages 230238. SpringerVerlag, 2001.
 [MvV96]

A. Menezes, P. van Oorschot, and S. Vanstone.
Handbook of Applied Cryptography.
CRC Press, 1996.
 [Pub98]

PublicKey Cryptography Standard (PKCS) #1 v2.0.
RSA cryptography standard.
RSA Laboratories, 1998.
 [RBBK01]

Phillip Rogaway, Mihir Bellare, John Black, and Ted Krovetz.
OCB: A blockcipher mode of operation for efficient authenticated
encryption.
In ACM Conference on Computer and Communications Security
(CCS8), pages 196205. ACM Press, 2001.
 [Vau02]

S. Vaudenay.
Security flaws induced by CBC padding  Applications to SSL,
IPSEC, WTLS...
In Advances in Cryptology  EUROCRYPT '02, volume 2332 of
Lecture Notes in Computer Science, pages 534545. SpringerVerlag,
2002.
 [Wir01]

Wireless Transport Layer Security.
Wireless Application Protocol WAP261WTLS20010406a.
Wirless Application Protocol Forum, 2001.
File translated from
T_{E}X
by
T_{T}H,
version 3.09. On 16 May 2002, 12:43.
