A more detailed version

Encryption Modes with Almost Free Message
Integrity
Charanjit S. Jutla
IBM T. J. Watson Research Center,
Yorktown Heights, NY 10598-704
Abstract. We define a new mode of operation for block ciphers which
in addition to providing confidentiality also ensures message integrity. In
contrast, previously for message integrity a separate pass was required to
compute a cryptographic message authentication code (MAC). The new
mode of operation, called Integrity Aware Parallelizable Mode (IAPM),
requires a total of m+1 block cipher evaluations on a plain-text of length
m blocks. For comparison, the well known CBC (cipher block chaining)
encryption mode requires m block cipher evaluations, and the second
pass of computing the CBC-MAC essentially requires additional m + 1
block cipher evaluations. As the name suggests, the new mode is also
highly parallelizable.
Keywords: Block Ciphers, Encryption, Authentication, Pairwise Independent,
Parallelizable
1
Introduction
Symmetric key encryption has become an integral part of today’s world of communication. It refers to schemes and algorithms used to secretly communicate
data over an insecure channel between parties sharing a secret key. It is also used
in other scenarios such as data storage.
There are two primary aspects of any security system: confidentiality and
authentication. In its most prevalent form, confidentiality is attained by encryption of bulk digital data using block ciphers. The block ciphers (e.g. DES [26],
AES[1]), which are designed to encrypt fixed length data, are used in various
chaining modes to encrypt bulk data. One such mode of operation is cipher block
chaining (CBC) ([2, 27]). The security of CBC has been well studied [3].
Cipher block chaining of block ciphers is also used for authentication between parties sharing a secret key. The CBC-MAC (CBC Message Authentication Code) is an international standard [14]. The security of CBC-MAC was
demonstrated in [6]. Authentication in this symmetric key setting is also called
Message Integrity.
Despite similar names, the two CBC modes, one for encryption and the other
for MAC are different, as in the latter the intermediate results of the computation
of the MAC must be kept secret. In fact in most standards (TLS, IPsec [30, 29]),
as well as in proprietary security systems, two different passes with two different
keys, one each of the two modes is used to achieve confidentiality and message
integrity.
2
Nevertheless, it is enticing to combine the two passes into one so that in a
single cipher block chaining pass, both confidentiality and message integrity are
ensured. Many such attempts have been made, which essentially use a simple
checksum or manipulation detection code (MDC) in the chaining mode ([28, 23,
9]). Unfortunately, all such previous schemes are susceptible to attacks (see e.g.
[32]).
We mention here that there are two alternative approaches to authenticated
encryption [7], i.e. encryption with message integrity. The first is to generate a
MAC using universal hash functions [8] as in UMAC ([5]). UMACs on certain
architectures can be generated rather fast. However, UMAC suffers from requiring too much key material or a pseudorandom number generator to expand the
key. (For comparison sake, on a message of size n, UMAC requires a key of size
n for similar efficiency and security.) In another scheme, block numbers are embedded into individual blocks to thwart attacks against message integrity ([18]).
However, this makes the cipher-text longer.
In this paper, we present a new mode of operation for block ciphers, which in
a single pass achieves both confidentiality and message integrity. In one variant,
to encrypt a message of length m blocks, the new mode requires a total of
m + 1 block cipher evaluations. All other operations are simple operations, like
exclusive-or. To contrast this with the usual CBC mode, the encryption pass
requires m block cipher evaluations, and the CBC-MAC computation on the
ciphertext requires another m + 1 block cipher evaluations.
Our new mode of operation is also simple. To illustrate, a simpler (though not
as efficient) version of the mode starts by performing a usual CBC encryption
of the plain-text appended with checksum (MDC). As required in CBC mode, it
uses a random initial vector r. As already mentioned, such a scheme is susceptible
to message integrity attacks. However, if one “whitens” the complete output
with a random sequence, the scheme becomes secure against message integrity
attacks. Whitening just refers to xor-ing the output with a random sequence.
The random sequence could be generated by running the block cipher on r, r +1,
r + 2,..., r + m (but with a different shared key). This requires m + 1 additional
cryptographic operations, and hence is no more efficient than generating a MAC.
The efficiency of the new mode comes from proving that the output whitening
random sequence need only be pair-wise independent. In other words, if the
output whitening sequence is s0 , s1 , s2 ,...,sm , then each si is required to be
random, but only pairwise-independent of the other elements. Such a sequence
is easily generated by performing only log m cryptographic operations like block
cipher evaluations. A simple algebraic scheme can also generate such a sequence
by performing only two cryptographic operations.
In fact, an even weaker condition than pair-wise independence suffices. A
sequence of uniformly distributed n-bit random numbers s0 , s1 ,...,sm , is called
XOR-universal [19] if for every n-bit constant c, and every pair i, j, i 6= j,
probability that si ⊕ sj equals c is 2−n . We show that the output whitening
sequence need only be XOR-universal. A simple algebraic scheme can generate
such a sequence by performing only one cryptographic operation.
The XOR-universal sequence generated to ensure message integrity can also
be used to remove chaining from the encryption mode while still ensuring confidentiality. This results in a mode of operation for authenticated encryption
3
which is highly parallelizable, and we call this mode IAPM (for Integrity Aware
Parallelizable Mode).
It is known (see [7], [18]) that for symmetric key encryption, confidentiality
under chosen plaintext attacks (CPA), along with integrity of ciphertexts, implies
confidentiality under chosen ciphertext attacks (CCA). In this paper we prove
the schemes secure for confidentiality under CPA, and secure for integrity of
ciphertexts.
Concurrently to our work, Gligor and Donescu ([10]) have also described a
mode of operation similar to CBC (but not the parallelizable mode) which has
built-in message integrity, although with a slightly weaker security bound than
our construction. Subsequently, and based on these results, a new authenticated
encryption mode OCB was described in [31]. The mode OCB was designed to
also handle plaintexts of irregular lengths, i.e. bit lengths which are not multiple
of the block length.
It has also been shown ([17]) that any scheme to encrypt m blocks of size n
bits each, that assures message integrity, is linear in (GF 2)n , and uses m+k invocations of random functions (from n bits to n bits) and v blocks of randomness,
must have k + v at least Ω(log m).
Pairwise independent random number generators (also called universal hash
functions [8]) have been used extensively in cryptography. In particular, Goldreich, Krawczyk and Luby [11] used them to build pseudorandom generators
from regular one-way functions, and Naor and Yung [25] used them in the construction of universal one-way hash functions. In the context of symmetric key
encryption, pairwise independent random permutations were used to construct
pseudo-random permutations from pseudo-random functions [24]. In the context
of de-randomization, Luby had demonstrated how the random choices needed
in a randomized parallel algorithm for maximal independent set problem need
only be pairwise independent [21].
The rest of the paper is organized as follows. Section 2 formalizes the notions
of security, for both confidentiality and message integrity. Section 3 describes
the new mode of operation IAPM. We also formalize the mode in the random
permutation model. In section 4 we prove that the new scheme is secure for
message integrity. In section 5 we prove the secrecy theorem for IAPM.
2
Authenticated Encryption Schemes
We give definitions of schemes which explicitly define the notion of secrecy of
the input message. In addition, we also define the notion of message integrity.
Moreover, we allow arbitrary finite length input messages as long as they are
multiple of the block size of the underlying block cipher.
Let Coins be the set of infinite binary strings. Let K⊆ {0, 1}∗ be the key
space, and D be a distribution on the key space.
Definition A (probabilistic, symmetric, stateless) authenticated encryption scheme,
with block size n, key space K, and distribution D, consists of the following:
– initialization: All parties exchange information over private lines to establish a private key x ∈ K. All parties store x in their respective private
memories.
4
– message sending with integrity:
Let E : K × Coins × {{0, 1}n}∗ → {{0, 1}n}∗
D : K × {{0, 1}n}∗ → {{0, 1}n}∗ ∪ {⊥}
be polynomial time computable function ensembles. The functions E and D
must have the property that for all x ∈ K, for all P ∈ {{0, 1}n}∗ , c ∈ Coins
Dx (Ex (c, P )) = P
We will usually drop the random argument to E as well, and just think of
E as a probabilistic function ensemble. The security of such a scheme is given
by the following two definitions, the first defining confidentiality under chosen
plaintext attacks, and the second defining message integrity.
Definition (Security under Find-then-Guess [22], [3])
Consider an adaptive probabilistic adversary A which runs in two stages:
find and guess. The two stages will be called A1 and A2. It is given access to
the encryption oracle Ex . In the find stage it tries to come up with two equal
length messages P 0 and P 1 . It also retains a state C1 for the next stage. In the
guess stage it is given the encryption C2 of P b , where b is chosen randomly to
be 0 or 1. The value C2 can really be seen as result of another oracle query P b ,
except that b is hidden from the adversary. This “oracle call” will also be called
the “choice” stage. The adversary’s success is reflected in how well it guesses b.
Formally,
AdvA = | Pr[x ←D K; (P 0 , P 1 , C1) ← A1Ex (·) ; b ←R {0, 1}; C2 ← Ex (P b ) :
A2Ex (·) (C1, C2) = b] − 1/2 |
An authenticated encryption scheme is said to be (t, q, µ, ǫ)-secure against chosen
plaintext attack if for any adversary A as above which runs in time at most t
and asks at most q queries of Ex , these totalling at most µ blocks, its advantage
AdvA is at most ǫ.
The following notion of security is also called integrity of ciphertext ([7]).
Definition (Message Integrity): Consider an adaptive probabilistic adversary A
running in two stages. In the first stage (find) A asks r queries of the oracle
Ex . Let the oracle replies be C 1 , ..., C r . Subsequently in the second stage, A
produces a cipher-text C ′ , different from each C i , i ∈ [1..r]. The adversary’s
success probability is given by
def
Succ = Pr[Dx (C ′ ) 6=⊥]
where the probability is over the choice of x from K according to D, other
randomness used by E, and the probabilistic choices of A.
An authenticated encryption scheme is (t, q, µ, ǫ)-secure for message integrity
if for any adversary A running in time at most t and making at most q queries
totalling µ blocks, its success probability is at most ǫ.
3
The New Modes of Operation
We begin by defining XOR-universal hash function families [19].
5
3.1
XOR-Universal Distributions
Definition We denote by F (m → n) the set of all functions from m bits to n
bits. We denote by P(n → n) the set of all permutations from n bits to n bits.
Definition (Hash Function Family): An (m, n)-family of hash functions H is a
collection of functions that map the set of binary strings of length m bits into
the set of binary strings of length n, i.e. a subset of F (m → n).
Definition (XOR-Universal Hash Function Family) [19] An (m, n)-family of
hash functions H is called an XOR-Universal hash function family, if for every
m-bit value M , and every n-bit value c, Prh [h(M ) = c] is 2−n , and further if
for every pair of distinct m-bit values M 1 and M 2, and every n-bit value c,
Prh [h(M 1) ⊕ h(M 2) = c] is 2−n , where the probabilities are over choosing h
uniformly from H.
An (m, n) hash function family H can be given by a single function H, which
takes a ⌈log |H|⌉-bit value, called seed, as another argument.
Definition (XOR-universal sequence): A probability distribution over sequences
of n-bit numbers s0 , s1 ,...,sm−1 , is called XOR-universal if each si is uniformly
distributed and for every n-bit constant c, and every pair i, j, i 6= j, the probability that si ⊕ sj is c is 2−n .
An XOR-universal sequence of length 2m can be generated using an XORUniversal (m, n)-hash function family H and seed k by, si = H(k, i).
3.2
The New Mode - IAPM
We now describe the new mode of operation for block ciphers, which along
with confidentiality also guarantees message integrity. The new mode is also
highly parallelizable, as will be clear from the description. It is called IAPM
for integrity aware parallelizable mode. There are many variants of this mode,
depending on how the XOR-universal sequence is generated, and even on how
the initial vectors are chosen. One variant is described in Fig 1. We now give
more details for IAPM and its many variants.
Let n be the block size of the underlying block cipher (or pseudo-random permutation). For now, we assume that if the block cipher requires keys of length k,
then this mode of operation requires two keys of length k, chosen independently.
Let these keys be called K1 and K2. From now on, we will use fx to denote the
block cipher encryption function under key x.
The message to be encrypted, P , is divided into blocks of length n each. Let
these blocks be P1 , P2 ,..., Pm . A random initial block, also called initial vector
(IV), of length n (bits) is chosen. As we discuss later, the IV need not be random,
as long as it is unique (that is never reused). The IV is expanded using the key
K2, used as a secret seed, to produce an XOR-Universal sequence S0 , ..., Sm+1 .
There are various methods to achieve this, which we will discuss shortly. The
cipher-text message C = < C0 , C1 , ..., Cm+1 > is then generated as follows (see
Figure 1). The encryption pseudo-code follows:
C0 = IV
for j = 1 to m do
Mj = Pj ⊕ Sj
Nj = fK1 (Mj )
6
P2
P1
IV
IV
S2
S1
Pm
Sm
checksum
Sm+1
f
K2
f
f
K1
K1
....
f
f
K1
K1
W
S1
Galois Field
Constrution
C0
S2
C1
S0
Sm
C2
Cm
Cm+1
S0 , S1 , ..., Sm+1
Fig. 1. Parallelizable Encryption with Message Integrity (IAPM)
Cj = Nj ⊕ Sj
end for
Lm
checksum = j=1 Pj
Mm+1 = checksum ⊕ Sm+1
Nm+1 = fK1 (Mm+1 )
Cm+1 = Nm+1 ⊕ S0
Note that S0 is used in the last step. The xor-ing of Sj with Pj before applying
the function f is commonly called pre-whitening. Similarly, xor-ing of Sj to Nj
to obtain Cj is called post-whitening.
It is easy to see that the above scheme is invertible. The inversion process
yields blocks P1 , P2 , ..., Pm+1 . The decrypted plain-text is < P1 , P2 , ..., Pm >.
Message integrity is verified by checking Pm+1 = P1 ⊕ P2 ⊕ ... ⊕ Pm .
Generation of XOR-Universal Sequences. We now focus on how the XORuniversal sequence used above is generated. We first describe methods which
employs the block cipher itself. The block IV is first expanded into t = O(log m)
new random blocks W1 , ..., Wt using the block cipher and key K2 as follows:
W1 = fK2 (IV)
for i = 2 to t do
Wi = fK2 (W1 + i − 2)
end for
The t blocks are then used to produce m + 2 new XOR-universal random blocks
S0 , S1 , ..., Sm+1 . In other words, the t blocks W1 , ..., Wt combined serve as the
seed into an XOR-Universal Hash Function family H. There are several such
XOR-Universal families, some requiring t to be only one. Such a family will be
described later. For now, consider the following elementary method using subsets
(t = ⌈log(m + 2)⌉):
7
for i = 1 to 2t do
Let < a1L
, a2 , ...at > be the binary representation of i
t
Si−1 = j=1 (aj · Wj )
end for
Galois Field Constructions of XOR-Universal Sequences. There are
several algebraic XOR-Universal Hash families. Firstly, one could consider a
pairwise independent hash function family H using an algebraic construction
in GF(p) as follows: generate two random blocks W1 , and W2 , and then let
Sj = H(hW1 , W2 i, j) = (W1 + W2 ∗ j) mod p, where p is a prime of appropriate
size. For example, if the block cipher has block size 128 bits, p could be chosen to
be 2128 −159. This leads to a faster implementation than the subset construction.
A sequence of 2n − 1 uniformly distributed n-bit random numbers, which are
XOR-universal, can also be generated by viewing the n-bit numbers as elements
of GF(2n ). Consider, H(W, j) = j · W , where multiplication is in GF(2n ). It is
easy to see that H is an (n, n)-XOR-universal hash family (except for the value
j = 0). Now, let Sj = H(W, e(j)), where e(j) is any one to one function from
Z2n −1 to non-zero elements of GF(2n ). Then, it is easy to see that S0 , ..., S2n −2
is an XOR-universal sequence. Note that this requires generation of only a single
W , i.e. t = 1 (see fig 1).
It is worth noting that in a serial implementation of IAPM, and particularly
in a resource constrained system, generation of Sj from W or from Sj−1 may
influence the efficiency of the mode. In particular, if e(j) = g j , where g is a
generator of the field GF(2n ), it takes at least one multiplication to get Sj from
Sj−1 . If e(j) is the binary representation of j + 1, then a basis of the field GF(2n )
over GF 2 (times W ) maybe initialized in n vectors, and then Sj can be computed
by exclusive-or operations of these vectors. In fact, e(j) can be the (j + 1)-th
gray code vector, in which case, only one n-bit exclusive-or operation is required
to get Sj from Sj−1 (see e.g. [15, 31]), as long as the n precomputed vectors are
maintained.
In some situations, even maintaining n vectors in active memory maybe too
taxing on the system. In such a situation, a GF(p) based solution as described
in the next section may be advantageous.
Safe Initial Vectors. Till now we have focused on construction of XORuniversal sequences using fresh seeds for each message, e.g. using W = fK2 (IV)
as seed into an XOR-universal hash family. Halevi [12] has observed that the
XOR-universal sequences can be generated using non-cryptographic operations,
i.e. by avoiding fK2 (IV). A careful setup and analysis shows that one can use
the same seed for all messages, and hence this “global” seed can just be the
independently chosen n-bit key K2. To this end, we define a set of initial vectors
to be safe as follows.
Definition. For a sequence of messages P i , i = 1 to z, each of length mi n-bit
blocks, a sequence of n-bit initial vectors IVi (i = 1 to z) is called safe if (a) for
all i ∈ [1..z], IVi + mi + 1 < 2n − 1, where the addition is integer addition, and
(b) for all i, i1 ∈ [1..z], i 6= i1, for all j ∈ [0..mi + 1], for all j1 ∈ [0..mi1 + 1],
IVi + j 6= IVi1 + j1.
8
The j-th whitening value for the i-th message, Sji (j ∈ [0..mi + 1]), is then
generated as Sji = H(K2, IVi + j), where H is any XOR-Universal hash family.
We will show the surprising result that if the initial vectors are safe, then regardless of how the adversary choses the n-bit initial vector for its adversarial
message, its (success) probability for attaining message integrity is negligible.
There are many ways to implement safe initial vectors, including a random
choice for the initial vector. Alternatively, one could require the initial vector
to be a multiple of 2n/2 , and assuming the length of each message is less than
2n/2 − 1, this leads to a sequence of safe initial vectors. However, with this
scheme, some of the optimizations mentioned above for computing Sj from Sj−1
do not work when switching to a new message. For the same optimizations to
work even across messages, one can set IVi = IVi−1 + mi−1 + 2 (see fig 2), and
it is easy to see that this leads to safe initial vectors.
prev
Sm+1
IV = IVprev + lenprev + 2
f
f
Incremental GF
Construction
(keyless or K2
K1
S1
C0
Pm
K1
S2
C1
....
f
f
K1
K1
S0
Sm
C2
checksum
Sm+1
Sm
S2
S1
S0 , S1 , ..., Sm+1
P2
P1
Cm
Cm+1
Fig. 2. IAPM with Safe Initial Vectors
The intuition behind why safe initial vectors are secure is that while encrypting genuine messages, the value IVi + mi + 1 is never used for calculating
a post-whitening value. Now, suppose an adversary, attacking the message integrity of the scheme, tries to use an initial vector different from IVi , but one
which is close enough, say IVi + s, where s ≤ mi . Then, the above fact and the
asymmetry in the last block whitening values forces the adversary to end up
using “wrong” whitening value (either post-whitening or pre-whitening value)
for at least one block. We defer complete details of the proof to section 4.
3.3
Integrity Aware Parallelizable Mode (IAPM) using a prime
number
The GF(p) construction with only a single W , instead of two, is not XORuniversal (as opposed to the previous construction in GF(2n )). However, it is
9
XOR-universal in GF(p). Such a sequence can be used securely in a slight variant
of the mode described above where “whitening” now refers to addition modulo
2n . We now give more details of this variant.
Let p be a prime close to 2n . For example, for 128 bit block ciphers p could
be 2128 − 159, which is known to be a prime. This prime will be fixed for all
invocations of this mode using block ciphers of block size 128 bit. For 64-bit
ciphers p = 264 − 257 is a close prime.
Let K2 be an additional independently chosen key (in addition to key K1
for the block cipher). Now, the sequence S0 , S1 , ..., Sm+1 is generated by the
following procedure:
procedure xor universal gfp sequence(input IV,m, K2; output S)
{
S0 = IV ∗ K2 mod p
for j = 1 to m + 1 do
Sj∗ = (Sj−1 + K2) mod 2n
if (K2 > Sj∗ ) Sj = Sj∗ + (2n − p) else Sj = Sj∗ .
end for
}
We assume that the initial vectors IV are chosen to be safe, e.g. by requiring
them to be multiple of 2⌈n/2⌉ , or by incrementing them appropriately as in the
previous section.
In the above code, the condition (K2 > Sj∗ ) is equivalent to n-bit integer
addition overflow in the previous step. Essentially, we are computing Sj to be
(j + 1) ∗ K2 mod p, except that we use a lazy representation. In other words, we
do not reduce modulo p if (Sj−1 + K2) < 2n , but we do compensate by 2n − p
if (Sj−1 + K2) ≥ 2n , as in the latter case, (Sj−1 + K2) = Sj−1 + K2 − p =
(Sj−1 + K2 − 2n ) + (2n − p) (mod p). We prove in lemma 9 that there is no
overflow when compensating by (2n − p).
IV
∗K2 mod p
S0 , S1 , ..., Sm+1
f
f
K1
K1
S1
C0
S2
C1
Pm
Sm
S2
S1
mod p construction
P2
P1
IV
....
Sm+1
f
f
K1
K1
S0
Sm
C2
checksum
Cm
Cm+1
Fig. 3. Integrity Aware Parallelizable Mode (IAPM) in GF(p) using Safe IVs
10
In this mode, the pre- and post-whitening is done by n-bit integer addition.
The ciphertext message C =< C0 , C1 , ..., Cm+1 > is generated as follows (see fig
3):
C0 = IV
for j = 1 to m do
Mj = (Pj + Sj ) mod 2n
Nj = fK1 (Mj )
Cj = (Nj + Sj ) mod 2n
end for
checksum = P1 ⊕ P2 ⊕ ... ⊕ Pm
Mm+1 = (checksum + Sm+1 ) mod 2n
Nm+1 = fK1 (Mm+1 )
Cm+1 = (Nm+1 + S0 ) mod 2n
Note that for computing the checksum we use exclusive-or instead of addition
modulo 2n . Note that S0 is used in the last step. The above scheme is invertible.
3.4
IAPM in Random Permutation Model
Since the description of IAPM in section 3.2 was for block ciphers, we formally
define the authenticated encryption scheme IAPM in the random permutation
model here. In the following, the operator “+” will stand for integer addition,
and “⊕” for n-bit exclusive-or.
Definition. Given a permutation f from n bits to n bits, and a function g from
n bits to n bits, the (deterministic) function E-IAPMf,g : {0, 1}n × {{0, 1}n}∗ →
{{0, 1}n}+ is defined as follows:
- Let the input to E-IAPMf,g be an n bit IV (denoting initial vector), and
an mn-bit string P (2n > m ≥ 0), such that IV+m + 1 < 2n − 1, which is
divided into m n-bit strings P1 , P2 , ..., Pm .
Lm
- Define C0 = IV , and checksum = 0 ⊕ j=1 Pj .
- For notational convenience, we will also refer to checksum as Pm+1 .
- Define for j = 1 to m: Cj = g(IV + j) ⊕ f (Pj ⊕ g(IV + j)).
- Define Cm+1 = g(IV ) ⊕ f (Pm+1 ⊕ g(IV + m + 1)).
- The output of the function E-IAPMf,g is the (m+2)n-bit string C0 , C1 , ..., Cm , Cm+1 .
Definition. Given a permutation f from n bits to n bits, and a function g
from n bits to n bits, the (deterministic) function D-IAPMf,g : {{0, 1}n}+ →
{{0, 1}n}∗ ∪ {⊥} is defined as follows:
- Let the input to D-IAPMf,g be an (m + 2)n-bit string C (2n ≥ m ≥ 0),
which is divided into (m + 2) n-bit strings C0 , C1 , ..., Cm , Cm+1 .
- Define IV = C0 .
- If IV+m + 1 ≥ 2n − 1, the output of the function is ⊥.
- Define for j = 1 to m: Pj = g(IV + j) ⊕ f −1 (Cj ⊕ g(IV + j)).
- Define Pm+1 = g(IV + m + 1) ⊕ f −1 (Cm+1 ⊕ g(IV )).
Lm
- if 0 ⊕ j=1 Pj is not same as Pm+1 , return ⊥, otherwise the output of the
function D-IAPMf,g is the mn-bit string P1 , ..., Pm .
11
Definition. (IAPM in random permutation model) Let G be a (n, n)family of XOR-universal hash functions. The authenticated encryption scheme
IAPM(G) with block size n is given by the following key space, distribution,
encryption function and decryption function:
- The set K of keys is the set of pairs f and g, where f is in P(n→n) (i.e. a
permutation), and g is in G.
- the distribution D on K is given by choosing f uniformly from P(n→n), and
choosing g independently and uniformly from G.
- The encryption function under key (f , g) is given by E-IAPMf ,g .
- The decryption function under key (f , g) is given by D-IAPMf ,g .
It is easy to see that D-IAPMf ,g (E-IAPMf ,g (IV, hP1 , ..., Pm i)) = hP1 , ..., Pm i.
4
Message Integrity of IAPM
In this section we will prove the message integrity of IAPM in the random
permutation model. The proof can be extended to strong (super) pseudo-random
permutations ([22]) by standard techniques1 .
For simplicity, we will assume that the initial vectors (IVs) are chosen deterministically as a function of the previous ciphertexts (which includes the previous
initial vectors and the lengths of the previous ciphertexts). As shown in section
3.2, there are several deterministic schemes to achieve safe initial vectors, and
the following theorem assumes any such scheme. If, on the other hand, the initial
vectors are chosen randomly (and completely independent of f and g), a slight
modification of the proof below shows that the adversary’s success probability is
marginally higher, i.e. by (z +u)(z +1)∗2−n (where z and u are as in the theorem
below). In the proof, we will mention the changes required for this random IV
case.
Theorem 1. Let A be an adaptive adversary attacking the message integrity of
IAPM(G) (in the random permutation model). Let A make at most z queries in
the first stage, totalling at most µ blocks. Let u = µ+z. Moreover, assume that the
initial vectors for the queries in the first stage are chosen using a deterministic
scheme such that they are safe. Let v be the maximum number of blocks in the
second stage. If 4u2 < 2n , and 4v 2 < 2n , then for adversary A,
Succ < (u2 + 2u + 3v + 4z + 1) ∗ 2−n
Proof:
We first note that we allow arbitrary functions as adversaries and not just
computable functions. Then without loss of generality, we can assume that the
adversary is deterministic, as every probabilistic adversary is just a probability
distribution over all deterministic adversaries [20].
1
Even if the function g was chosen as an application of another random permutation
from the same pseudo-random permutation class from which f is chosen (as opposed
to g being chosen independently of f ), a standard hybrid argument shows that g
can still be considered independent of f .
12
Note that, in the message integrity attack, the adversary’s success probability
is measured under the key chosen from K according to distribution D. Thus by
definition of IAPM(G), the space for the probability distribution is the set of
pairs f and g. Any variable which is a function of f and g, will be called a
random variable, and for clarity will be in bold-face. We will refer to f as the
permutation, and g as the whitening function.
Fix an adaptive adversary. Since the adversary is deterministic, the first
1
query’s plaintext (say P 1 = hP11 , ..., Pm
i) is fixed for that adversary. Thus, the
1
first query’s output, say C , is only a function of f and g. Note that the IV for
the first message (which is the first block of C 1 ) is also chosen deterministically,
and is in fact fixed. The adversary being adaptive, its second query is a function
of C 1 . But, since C 1 is only a function of f and g, the second query’s plaintext
and IV can also be considered just as a function of f and g. Thus, C 2 is only a
function of f and g, and so forth.
For all variables corresponding to a message (query), we will use superscripts
to denote the message number, and subscripts to denote blocks in a particular
message. We will use C to denote the whole transcript of sequence of ciphertext
outputs C1 , ..., Cz . Thus, Cij is a variable denoting the jth block in the ith
ciphertext message. More precisely, this variable C should be written C(f , g),
as it is a function of f and g, as argued in the previous paragraph.
We will use ci to denote prospective values for Ci . We will use c to denote the prospective ciphertext transcript c1 , ..., cz . The function | · | is used
to represent length of a message in n-bit blocks. Let l() be the length of the
first ciphertext (determined by the adversary A). Given a sequence of ciphertext
messages c1 , ..., ci , i < z, let l(c1 , ..., ci ) be the length of the (i + 1)th ciphertext
(which is determined by the adversary, and therefore is a deterministic function
of c1 , ..., ci ). We will use the shorthand li for |ci |. If the adversary makes less
than z queries in the first stage, say z ′ ≤ z, we assume, for convenience, that
l(c1 , ..., ci ) = 1 for all i ≥ z ′ , as the ciphertext transcript includes the initial vectors ci0 . Note that if a query is a null message, then IAPM generates two blocks
of ciphertext, the initial vector and the block produced from the checksum. Thus
for all i ≤ z ′ , li ≥ 2, whereas, for all i > z ′ , li = 1. We will use the function
Z(c) to determine the largest i (≤ z) such that li (c) ≥ 2. Similarly, the random
variable Z will denote Z(C(f , g)). Note, Z ≤ z.
We will also refer to ci0 as IVi (c), or just IVi when clear from context.
Let the adversary’s query in the second stage, the attempted forgery, be
cipher-text C′ , different from all ciphertexts in the first stage. We will refer
to C′ as the forged ciphertext. Since, C′ is a deterministic function of C, given
c1 , ..., cz let the ciphertext in the second stage be c′ with length l′ , i.e. c′ = C′ (c).
We will also refer to c′0 as IV′ (c), or just IV′ when clear from context.
Let Li = l(C1 , ..., Ci−1 ) be the random variable representing the length of
ciphertext Ci (i.e. the checksum block has index Li −1). Similarly, L′ will denote
the length of C′ .
As per the definition of IAPM in random permutation model (also see fig. 4),
the whitening function g is applied before and after the application of the permutation f . For each block j in message i, the pre-whitening is done with g
applied to IVi offset by j. Similarly for the post-whitening, except when j is
the last block, in which case the post-whitening is done with g applied to IV i
13
P1
M1
M2
f
Pm+1
gm+1
gm
g2
g1
Pm
P2
Mm+1
Mm
f
f
f
........
N2
N1
g1
g2
C1
Nm
gm
C2
Nm+1
g0
Cm
Cm+1
Fig. 4. IAPM in Random Permutation Model
offset with zero. Motivated by this, for each i in [1..z], define σji (c) to be the
post-whitening offset in the jth block of the ith message, namely σji (c) = j if
j < li − 1, and σji (c) = 0 if j = li − 1. Similarly, define σj′ (c) = j if j < l′ − 1
and σj′ (c) = 0 if j = l′ − 1.
For a fixed ciphertext transcript c, the plaintext block Pji (being chosen adaptively) can be viewed as only a function of c, and we will write it as Pji (c). Thus,
instead of writing Pji as a function of the permutation f and the whitening function g, we will be considering it as a function of prospective ciphertext transcript
c. The random variable Pij can still be expressed as Pji (C) = Pji (C(f , g)).
For any prospective ciphertext transcript c, and whitening function g ∈ G,
for i ∈ [1..z], j ∈ [1..li − 1], define Mji (c, g) = Pji (c) ⊕ g(ci0 + j). Similarly,
define Nji (c, g) = cij ⊕ g(ci0 + σji (c)). We will use Mij to denote the random
variable Mji (C, g), and use Nij to denote the random variable Nji (C, g). In other
words, Mij is the actual input to the permutation f (for ith message’s jth block)
and Nij is the output of f on that input. We will refer to Mij s as the whitened
plaintext blocks, and Nij s as the raw ciphertext blocks. Just as for C, we will
use P (c), M (c, g) and N (c, g) to denote the whole sequence. Note that although
Nij = f (Mij ), there is no such relationship between Nji (c, g) and Mji (c, g). In
particular, Nji (c, g) = f (Mji (c, g)) only if the transcript c and whitening function
g are such that cij = f (Mji (c, g)) ⊕ g(ci0 + σji (c)).
Moving on to the forged ciphertext, again for a fixed c, as c′ is fixed, for
j ∈ [1..l′ − 1], define Nj′ (c, g) = c′j ⊕ g(c′0 + σj′ (c)). Note that as c′ is picked by
the adversary, p′ is not just a function of c, and hence M ′ (as opposed to Mji )
cannot be defined as a function of just c and g. Thus, for j ∈ [1..l′ − 1], and
any permutation f , and g ∈ G, define Mj′ (c, g, f ) = f −1 (Nj′ (c, g)). As before N′j
will stand for the random variable Nj′ (C, g), and M′j for Mj′ (C, g, f ). We will
refer to N′j s as the whitened forged ciphertext blocks, and M′j as the raw forged
plaintext blocks.
14
Also, for j ∈ [1..l′ −1], define Pj′ (c, g, f ) = M ′ (c, g, f )⊕g(c′0 +j). By definition
of IAPM(G) (see D-IAPM), the random variable P′j (= Pj′ (C, g, f )) is M′j ⊕
g(C′0 + j) .
For future reference, we list all these definitions and equalities here.
Pij = Pji (C), for j ∈ [1..Li − 2]
Cij
=
g(Ci0
+ j) ⊕
f (Pij
⊕
g(Ci0
(1)
i
+ j)), for j ∈ [1..L − 2]
(2)
i
PiLi −1 = 0 ⊕
LM
−2
Pij
(3)
j=1
CiLi −1 = g(Ci0 ) ⊕ f (PiLi −1 ⊕ g(Ci0 + Li − 1))
Mji (c, g)
Nji (c, g)
Mij
Nij
Nj′ (c, g)
N′j
Mj′ (c, g, f )
M′j
′
Pj (c, g, f )
P′j
=
=
=
=
=
=
=
=
=
=
Pji (c) ⊕ g(ci0 + j)
cij ⊕ g(ci0 + σji (c))
Mji (C, g)
Nji (C, g) = f (Mij )
c′j ⊕ g(c′0 + σj′ (c))
Nj′ (C, g)
f −1 (Nj′ (c, g))
Mj′ (C, g, f )
M ′ (c, g, f ) ⊕ g(c′0 +
M′j ⊕ g(C′0 + j)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
j)
(13)
(14)
Below we define events E0, E1 and E2 which are random variables (being
functions of the permutation f and the whitening function g). We prove that
either the adversary forces the events E0 or E1, or the event E2 happens with
high probability. In either case we show that the checksum validates with low
probability. The events E0 and E1 describe attacks in which the forged ciphertext is copied from one of the previous legitimate ciphertexts, possibly with
re-arrangement and deletion of blocks. The event E0 is called deletion attempt,
as the adversary in this case just truncates an original ciphertext, but retains
the last block. The event E1 can be seen as a rotation attempt by the adversary.
Event E0 (deletion attempt): There is an i ∈ [1..Z], such that 2 ≤ L′ < Li , and
(i) ∀j ∈ [0..L′ − 2] : C′j = Cij and (ii) C′L′ −1 = CiLi −1
Event E1 (rotation attempt)2 : There is an i ∈ [1..Z], and a t, 1 ≤ t ≤ Li − L′ ,
such that
(i) C′0 = Ci0 + t, (ii) ∀j ∈ [1..L′ − 1] : C′j = Ciσ′ (C)+t
j
2
If we only consider initial vectors chosen with a nice structure, e.g. with enough
zeroes in the least significant bits to unambiguously embed block numbers, then
the event E1 need not be considered. In that case, one can show that either the
adversary forces event E0 or event E2 happens with high probability.
15
In other words, C′1 = Cit+1 , C′2 = Cit+2 ,...,C′L′ = Cit . Also, (i) is same as
requiring the initial vector of the forged ciphertext to be same as the initial
vector of the i-th ciphertext offset by t.
Event E2 says that there is a block x in the forged ciphertext C′ , such that
its (whitened forged ciphertext block) N′x variable is different from all previous
(raw ciphertext variables) Ns, and also different from all other N′ s.
Event E2: There is an x ∈ [1..L′ − 1] such that
(i) ∀t ∈ [1..z] ∀j ∈ [1..Lt − 1] : N′x 6= Ntj
and (ii) ∀j ∈ [1..L′ − 1], j 6= x : N′x 6= N′j
The adversary’s success probability is upper bounded by (a) the probability
of event E0 or E1 or E2 not happening, plus (b) the probability of the checksum
validating along with events E0 or E1 or E2 happening. Intuitively, when E0
or E1 holds, a pre-whitening value will have a discrepancy, whereas if E2 holds,
a post-whitening value will have a discrepancy. These discrepancies lead to a
bound on the latter probability (b), though proving the bound requires a few
lemmas.
As for bounding the probability (a), the event E2 not happening translates
i
i1
i
into a disjunction of events of the type gij ⊕ gi1
j1 = Cj ⊕ Cj1 , where gj stands
for g(IV i + j). Naively, since G is XOR-universal, one would think that the
probability of each of these events is 2−n . However, it is not guaranteed that
the whitening function g is independent of the ciphertext C, as the ciphertext
satisfies Cij = Nij ⊕gij . Intuitively, if all the whitened plaintexts Mij were distinct
and Cij = Nij ⊕ gij were the only relations between C and g, then indeed g would
be independent of C (as g and f are independently chosen). But, requiring all
Mij to be distinct implies another relation between C and g.
However, it can be shown that, on every fixed outcome of the ciphertext C
(i.e. C = c for some constant transcript c), requiring the M variables to be
distinct (and the N variables to be distinct), rules out only a negligible fraction
of functions in G as a potential value for g, and moreover leaves the remaining
functions in G equi-probable.
So, consider the following predicate PD (pairwise different). For any constant
c and function g ∈ G, define PD(c, g) to be
∀i, i1 ∈ [1..z], ∀j ∈ [1..li − 1], ∀j1 ∈ [1..li1 − 1], (i, j) 6= (i1, j1) :
i1
i1
(Mji (c, g) 6= Mj1
(c, g)) ∧ (Nji (c, g) 6= Nj1
(c, g))
Again, we will use PD to denote the random variable PD(C(f , g), g). If a
random schedule is used to pick the initial vectors, then we must include in this
predicate the condition that {ci0 }i are safe.
The rest of the proof of the theorem is organized as follows. To start with, we
will formalize in lemma 1 the equi-probability of the allowed g, given a constant
transcript C = c and conditioned on the event PD(c, g). We use this lemma
to prove in lemma 6 that the probability of the event PD and the negation of
(E0 or E1 or E2) is low. We also use lemma 1 to prove in lemma 3 that event
PD itself happens with high probability. Finally, we prove that the checksum
validating along with events E0 or E1 or E2 is a small probability event as well
16
(lemmas 7 and 8), which would lead to the proof of the theorem. We first state
all the lemmas, and use them to prove the theorem. The proofs of the lemmas
follow later.
We need to characterize the set of prospective ciphertexts with safe IVs for
this particular adversary A. Before that, recall the (adversarial) ciphertext length
function l from above. Also, recall that the predicate “safe” applies to a set of
initial vectors. Now, for 0 ≤ i < z, define
L(c1 , ..., ci ) = {ci+1 : |ci+1 | = l(c1 , ..., ci ) and {cj0 }j∈[1..i+1] safe}
Let,
C = {c : ∀i ∈ [1..z] ci ∈ L(c1 , ..., ci−1 )}
Thus, C can be seen as the space of prospective ciphertext transcripts for this
particular adversary A. Note that when we sum over c ranging from C, it really
means the following telescopic sum
X
X
X
X
=
...
...
c∈C
c1 ∈L()
ci ∈L(c1 ,...,ci−1 )
cz ∈L(c1 ,...,cz−1 )
Remark: If a random schedule is used to choose the IVs, then we exclude the
safety condition from C, and include it in the predicate PD. Moreover, in all
the lemmas and the proof of the theorem below, the probability will be over
choosing (f , g) according to D, as well as choosing the initial vectors randomly
and independently. The only change will be in the analysis of lemma 2, as the
safety condition will incur an additional cost of (z + u)(z + 1) ∗ 2−n .
In the following lemmas, the adversary A is fixed to be as in Theorem 1
statement. The quantities n, z, µ, u, and v are as stipulated in Theorem 1
statement.
Lemma 1. For every prospective ciphertext transcript c ∈ C, and for any function g ∈ G such that PD(c, g),
Pr(f ,g)∈D K [g = g|C = c ∧ PD(c, g)] =
Pr(f ,g)∈D K [g = g]
Pr(f ,g)∈D K [PD(c, g)]
Lemma 2. For every prospective ciphertext transcript c ∈ C,
Pr (f ,g)∈D K [¬PD(c, g)] < u2 ∗ 2−n
Lemma 3.
Pr (f ,g)∈D K [¬PD ] < u2 ∗ 2−n
The following lemma follows from lemmas 1 and 2, and is used to prove
lemmas 6 and 8.
Lemma 4. For every triple of n-bit constants a, b, and d, such that a 6= b, and
every prospective ciphertext transcript c ∈ C
Pr(f ,g)∈D K [g(a) ⊕ g(b) = d ∧ C = c ∧ PD(c, g)] ≤ 2−n+1 ∗ Pr(f ,g)∈D K [C = c]
17
The following lemma is also used to prove lemma 6.
Lemma 5. For every prospective ciphertext transcript c ∈ C, and its corresponding forged transcript c′ , either E0 or E1 holds for c, or
∃x ∈ [1..l′ −1]∀t ∈ [1..z]∀j ∈ [1..lt −1] : (IV ′ (c)+σx′ (c) = IV t (c)+σjt (c)) ⇒ (c′x 6= ctj )
Lemma 6. Let events E0, E1, E2 be as in Theorem 1. Then,
Pr(f ,g)∈D K [¬(E0 ∨ E1 ∨ E2) ∧ PD ] < (2u + 2v) ∗ 2−n
Lemma 7. Pr(f ,g)∈D K [
LL′ −1
Lemma 8. Pr(f ,g)∈D K [
j=1
LL′ −1
j=1
P′j = 0 | E2 ] ≤
v
2n −(u+v)
P′j = 0 ∧ (E0 ∨ E1) ∧ PD ] ≤ z ∗ 2−n+2
Proof of Theorem 1 (cont’d):
Pr(f ,g)∈D K [
′
L
−1
M
P′j = 0]
j=1
′
L
−1
M
P′j = 0 ∧ PD] + Pr[¬PD]
′
L
−1
M
P′j = 0 ∧ (E0 ∨ E1 ∨ E2) ∧ PD]
≤ Pr[
j=1
≤ Pr[
j=1
+Pr[
′
L
−1
M
P′j = 0 ∧ ¬(E0 ∨ E1 ∨ E2) ∧ PD] + Pr[¬PD]
j=1
≤ Pr[
′
L
−1
M
P′j
= 0 ∧ (E0 ∨ E1) ∧ PD] + Pr[
′
L
−1
M
P′j = 0 ∧ E2]
j=1
j=1
+Pr[¬(E0 ∨ E1 ∨ E2) ∧ PD] + Pr[¬PD]
v
≤ z ∗ 2−n+2 + n
+ (u + v) ∗ 2−n+1 + u2 ∗ 2−n (by lemma 8, 7, 6, and 3 resp.)
2 − (u + v)
≤ (u2 + 2u + 3v + 4z) ∗ 2−n + O(u + v) ∗ v ∗ 2−2n
4.1
Proofs of the lemmas
Lemma 1. For every prospective ciphertext transcript c ∈ C, and for any function g ∈ G such that PD(c, g),
Pr(f ,g)∈D K [g = g|C = c ∧ PD(c, g)] =
Pr(f ,g)∈D K [g = g]
Pr(f ,g)∈D K [PD(c, g)]
Proof: Now,
Pr(f ,g)∈D K [g = g|C = c ∧ PD(c, g)]
=
Pr[g = g ∧ C = c ∧ PD(c, g)]
Pr[C = c ∧ PD(c, g)]
18
We first consider the numerator:
Pr[g = g ∧ C = c ∧ PD(c, g)]
X
=
Pr[g = g ∧ f = f ′ ∧ C = c ∧ PD(c, g)]
f′
= Pr[g = g ∧ f ∈ Fc,g ∧ C = c ∧ PD(c, g)]
= Pr[g = g ∧ f ∈ Fc,g ]
where Fc,g is the set of permutation defined as follows: since PD(c, g) holds, all
the raw ciphertext block variables N (c, g) are distinct. Similarly, all whitened
plaintext block variables M (c, g) are distinct. These M (c, g) and N (c, g) values
determine a unique permutation fc,g projected on a number of blocks given by c
(i.e. |c| − z). Thus, for c, g s.t. PD(c, g), define Fc,g to be the set of permutations
with the projection on these blocks equal to fc,g , and with no other restrictions
on other blocks. If c, g are such that ¬PD(c, g), then we let Fc,g to be the empty
set.
The last equality above follows as the two events are identical. To see that
g = g and f ∈ Fc,g implies C = c, first note that since f is in Fc,g , the set Fc,g
is non-empty, and hence PD(c, g) holds, which implies PD(c, g). Now note that
the first plaintext message p1 is fixed, and moreover the first initial vector c10 is
fixed, which fixes M1 to M 1 (c, g) by equations (7) and (5). Since N1 = f (M1 )
(by (8)), this fixes N1 to f (M 1 (c, g)) which is fc,g (M 1 (c, g)) by definition of Fc,g
and fc,g . But, fc,g (M 1 (c, g)) is same as N 1 (c, g) by definition of fc,g . Thus, C1
is fixed to c1 by (2) and (6). This in turn, fixes P2 = P 2 (c) by (1), and fixes C20
to c20 as the initial vectors are chosen as a deterministic function of the previous
ciphertexts, and so forth inductively.
We now consider the denominator:
Pr[C = c ∧ PD(c, g)]
XX
=
Pr[g = g ′ ∧ f = f ′ ∧ C = c ∧ PD(c, g)]
′
g ′ ∈G f
X
=
Pr[g = g ′ ∧ f ∈ Fc,g′ ∧ C = c ∧ PD(c, g)]
g′ ∈G :P D(c,g′ )
X
=
Pr[g = g ′ ∧ f ∈ Fc,g′ ]
g′ ∈G :P D(c,g′ )
The above follows because as before, when PD(c, g ′ ) holds, there is a fixed set of
permutations Fc,g′ with a unique projection (on |c| − z blocks) compatible with
g = g ′ and C = c.
Since g and f are independent, we have from the above analysis:
Pr[g = g|C = c ∧ PD(c, g)]
Pr[g = g ∧ f ∈ Fc,g ]
= P
′
′
g′ ∈G :P D(c,g′ ) Pr[g = g ∧ f ∈ Fc,g ]
= P
Pr[g = g] ∗ Pr[f ∈ Fc,g ]
′
′
g′ ∈G :P D(c,g′ ) Pr[g = g ] ∗ Pr[f ∈ Fc,g ]
19
=
Pr[g = g]
Pr[P D(c, g)]
The last equality follows because in distribution D, f is chosen uniformly, and
Fc,g is non-empty by hypothesis of the lemma, and Fc,g′ is non-empty as PD(c, g ′ )
holds, and further |Fc,g | = |Fc,g′ |.
Lemma 2. For every prospective ciphertext transcript c ∈ C,
Pr (f ,g)∈D K [¬PD(c, g)] < (u2 ) ∗ 2−n
Proof: Recall that event PD(c, g) is
∀i, i1 ∈ [1..z], ∀j ∈ [1..li − 1], ∀j1 ∈ [1..li1 − 1], (i, j) 6= (i1, j1) :
i1
i1
(Mji (c, g) 6= Mj1
(c, g)) ∧ (Nji (c, g) 6= Nj1
(c, g))
Then ¬ PD(c, g) can be written as
∃i, i1 ∈ [1..z], ∃j ∈ [1..li − 1], ∃j1 ∈ [1..li1 − 1] : (i, j) 6= (i1, j1) ∧
i1
i1
(c, g))]
(c, g)) ∨ (Nji (c, g) = Nj1
[(Mji (c, g) = Mj1
Since we have a constant ciphertext transcript c, and hence a constant plaini1
text P (c) as well, the probability of any event Mji (c, g) = Mj1
(c, g) is just
−n
i
2 , as each Mj (c, g) is just a function of g, the latter being chosen from an
XOR-universal set G, and given that the initial vectors are safe. Similarly for
i1
Nji (c, g) = Nj1
(c, g). The lemma follows by union bound.
Lemma 3.
Pr (f ,g)∈D K [¬ PD] < (u2 ) ∗ 2−n
P
Proof: For c = c1 , c2 , ..., ci , i ≤ z, define #(c) to be (2n )!/(2n − ij=1 (|cj | − 1))!.
In other words, #(c) is the ratio of number of permutations on 2n blocks and
|Fc,g | (as defined in lemma 1, and which is same irrespective of g, as long as
PD(c, g) holds).
Recall from the proof of lemma 1, for c ∈ C,
Pr[C = c ∧ PD(c, g)]
X
=
Pr[g = g ′ ∧ f ∈ Fc,g′ ]
g′ ∈G :P D(c,g′ )
We use this to get,
Pr[PD(C, g)]
X
=
Pr[C = c ∧ PD(c, g)]
c∈C
X
X
=
Pr[g = g ′ ∧ f ∈ Fc,g′ ]
c∈C g′ ∈G :PD(c,g′ )
X
X
=
Pr[g = g ′ ] ∗ Pr[f ∈ Fc,g′ ]
c∈C g′ ∈G :PD(c,g′ )
20
=
X
X
c∈C
Pr[g = g ′ ] ∗
1
#(c)
g′ ∈G :PD(c,g′ )
X 1
∗ Pr[PD(c, g]
=
#(c)
c∈C
X 1
≥ minc∈C {Pr[PD(c, g)]} ∗
#(c)
c∈C
X 1
≥ (1 − u2 ∗ 2−n ) ∗
(by lemma 2)
#(c)
c∈C
≥ (1 − u2 ∗ 2−n )
The last inequality follows by
X 1
c∈C
=
≥
#(c)
X
...
c1 ∈L()
X
ci ∈L(c1 ,...,ci−1 )
X
X
...
...
...
c1 ∈L()
ci ∈L(c1 ,...,ci−1 )
X
cz ∈L(c1 ,...,cz−1 )
X
1
#(c1 ; ...; cz )
cz−1 ∈L(c1 ,...,cz−2)
1
#(c1 ; ...; cz−1 )
≥ ...
X
1
≥
#(c1 )
c1 ∈L()
≥1
where we used the fact that the number of cz in L(c1 , ..., cz−1 ) is 2n(|c
so on.
z
|−1)
, and
We will need the following lemma to prove lemma 6 and lemma 8.
Lemma 4. For every triple of n-bit constants a, b, and d, such that a 6= b, and
every prospective ciphertext transcript c ∈ C
Pr(f ,g)∈D K [g(a) ⊕ g(b) = d ∧ C = c ∧ PD(c, g)] ≤ 2−n+1 ∗ Pr(f ,g)∈D K [C = c]
Proof:
Pr[g(a) ⊕ g(b) = d ∧ C = c ∧ PD(c, g)]
= Pr[g(a) ⊕ g(b) = d | C = c ∧ PD(c, g)]
∗ Pr[C = c ∧ PD(c, g)]
≤ Pr[g(a) ⊕ g(b) = d | C = c ∧ PD(c, g)]
∗ Pr[C = c]
The first factor is upper bounded by 2−n / Pr[PD(c, g)] by using lemma 1. To
see this,
Pr(f ,g)∈D K [g(a) ⊕ g(b) = d | C = c ∧ PD(c, g)]
21
=
X
Pr[g = g ∧ g(a) ⊕ g(b) = d | C = c ∧ PD(c, g)]
X
Pr[g = g | C = c ∧ PD(c, g)] ∗ Pr[g(a) ⊕ g(b) = d | g = g ∧ C = c ∧ PD(c, g)]
g∈G
=
g∈G
=
X
Pr[g = g | C = c ∧ PD(c, g)]
g∈G :g(a)⊕g(b)=d
≤
X
g∈G :g(a)⊕g(b)=d
=
1
∗
Pr[PD(c, g)]
Pr(f ,g)∈D K [g = g]
Pr[ PD(c, g)]
X
(by lemma 1)
1
|G|
g∈G :g(a)⊕g(b)=d
1
=
∗ Prg∈G [g(a) ⊕ g(b) = d]
Pr[PD(c, g)]
2−n
=
Pr[PD(c, g)]
Now by lemma 2, and the hypothesis of Theorem 1 that 4u2 < 2n , we have
Pr[PD(c, g)] > 1/2, and hence the lemma follows.
Lemma 5. For every prospective ciphertext transcript c ∈ C, and its corresponding forged transcript c′ , either E0 or E1 holds for c, or
∃x ∈ [1..l′ −1]∀t ∈ [1..z]∀j ∈ [1..lt −1] : (IV ′ (c)+σx′ (c) = IV t (c)+σjt (c)) ⇒ (c′x 6= ctj )
Proof: Since the initial vectors are safe, by definition, for all t ∈ [1..z], IV t + lt −
1 < 2n − 1. Also, IV ′ + l′ − 1 < 2n − 1 (see step 3 of D-IAPM).
Recall that σjt (c) is the post-whitening offset for block j in message t. As it
is clear from context, we will drop the argument c from σ and σ ′ .
If for all message indices t ∈ [1..z], the forged initial vector IV ′ is not equal
to IV t (along with their offsets), i.e. for all t: IV ′ 6∈ IV t + [0..lt − 2], then we can
take x = l′ − 1, in which case σx′ = 0, and hence IV ′ + σx′ = IV ′ . Now, note that
σjt ranges from 0 to lt − 2, and hence this x satisfies the lemma vacuously.
Next, consider the case where there exists a t ∈ [1..z] such that IV ′ equals
t
IV with some offset, i.e. IV ′ ∈ IV t + [0..lt − 2]. As the initial vectors are safe,
there can be at most one such t. Also, note that t ≤ Z(c), as for i > Z(c), li = 1.
There are two main sub-cases.
(a) For every x ∈ [1..l′ − 1], IV ′ + σx′ ∈ IV t + [0..lt − 2] (i.e. the set IV′ along with
its offsets is contained in set IVt along with its offsets). Again, as the initial
′
′
vectors are safe, IV ′ + σx′ cannot equal IV t + σjt′ , for some other t′ 6= t. Also,
since σx′ ranges over values from 0 to l′ − 2, we have IV ′ + l′ − 2 ≤ IV t + lt − 2.
There are two further sub-cases.
(a1) (IV ′ = IV t : truncation attempt). Here, l′ ≤ lt . If c′ is a (strict) prefix
of ct , then we pick the last block of c′ , i.e. we let x = l′ − 1. Since it
is the last block, the post-whitening offset is zero, i.e. σx′ = 0. Since,
IV ′ = IV t , the value IV ′ + σx′ will be same as IV t + σjt (for some j) only
if σjt = σx′ = 0, or in other words only if j = lt − 1. Now, c′ being a prefix
22
of ct , if c′x = ctlt −1 then it forces event E0 (the deletion attempt) for c
(note t ≤ Z(c)).
Otherwise, if c′ is not a prefix of ct , let x be the least index in which c′
and ct differ. If for some j, σjt = σx′ , then either σjt = σx′ = 0, or j = x.
In the latter case, c′x ⊕ ctj = c′x ⊕ ctx , which is non-zero as x is the index
in which c′ and ct differ. In the former case, j = lt − 1, and x = l′ − 1.
In this case, c′x ⊕ ctj = c′l′ −1 ⊕ ctlt −1 . If this quantity is zero, then since
x (= l′ − 1) was the least index in which ct and c′ differed, event E0
would hold for c.
(a2) (IV ′ 6= IV t : rotation attempt) Note that, if instead of general safe intitial
vectors we had required the initial vectors to have enough least significant
bits to be zero, so that the offsets could be embeded un-ambiguously,
then this case would not arise. In other words, with this restriction,
IV ′ + σx′ ∈ IV t + [0..lt − 2] could only happen if IV ′ = IV t . However,
in the case of general safe initial vectors, this case could certainly arise.
We will show that for each x, there is a unique jx ∈ [1..lt − 1], such that
IV ′ + σx′ = IV t + σjtx . Recall that σx′ = x except for x = l′ − 1, in which
case it drops to zero, i.e. x− (l′ − 1). Hence for the above jx to exist, jl′ −1
must drop by (l′ − 1) as well (we formalize this in the next paragraph).
Next, we will show that either for some x, c′x 6= ctjx or event E1 holds
(i.e. c′ is a rotation of a portion of ct ).
To be more precise, we first note that IV ′ ≥ IV t + 1, as IV ′ is in IV t +
[0..lt − 2]. Thus from IV ′ ≤ IV t + lt − l′ it follows that IV ′ = IV t + s, for
some s such that 1 ≤ s ≤ lt − l′ (thus satisfying E1(i)). Thus, for every
x ∈ [1..l′ − 1], IV ′ + σx′ = IV t + σx′ + s. Note that 1 ≤ σx′ + s ≤ lt − 2,
as 0 ≤ σx′ ≤ l′ − 2, and 1 ≤ s ≤ lt − l′ . Hence, for each x ∈ [1..l′ − 1],
σσt x′ +s = σx′ +s, and hence IV ′ +σx′ = IV t +σx′ +s = IV t +σσt x′ +s . Thus, for
each x, there is a unique jx , namely σx′ +s, such that IV ′ +σx′ = IV t +σjtx .
Now, suppose for all x ∈ [1..l′ − 1], c′x ⊕ ctjx = 0, i.e. c′x = ctσx′ +s . But
this implies that E1 holds for c. Otherwise, we have an x such that
c′x ⊕ ctjx 6= 0, and the lemma follows as t and jx are the only values for
which IV ′ + σx′ = IV t + σjtx .
(b) (extension attempt) There exists an x ∈ [1..l′ − 1] such that IV ′ + σx′ 6∈
IV t + [0..lt − 2]. Since, IV ′ ∈ IV t + [0..lt − 2], it follows that there exists an
x ∈ [1..l′ − 2] such that IV ′ + σx′ 6∈ IV t + [0..lt − 2]. For the least such x (and
note σx′ = x), we have IV ′ + x = IV t + lt − 1. Since the initial vectors are
′
′
′
safe, there is no other t′ , j ′ such that IV ′ + σx′ = IV t + σjt′ , j ′ in [1..lt − 1].
Thus this x satisfies the lemma vacuously. The key observation here is that
for every t ∈ [1..Z(c)], the value IV t + lt − 1 is never used as a post-whitening
index in the first stage of the attack.
Lemma 6. Let events E0, E1, E2 be as in Theorem 1. Then,
Pr(f ,g)∈D K [¬(E0 ∨ E1 ∨ E2) ∧ PD] < (2u + 2v) ∗ 2−n
Proof:
To begin with, we have
Pr[¬(E0 ∨ E1 ∨ E2) ∧ PD] =
X
c∈C
Pr[¬(E0 ∨ E1 ∨ E2) ∧C = c ∧ PD] (15)
23
Focusing on the negation of E2, the inside expression above (see the definition
of E2) is the probability of the conjunction (one for each x) of disjunctions.
Hence, it is upper bounded by the least (over x) of the probabilities of the
disjunctions, which in turn is upper bounded by the sum of the probability of
each disjunct. Thus, for any fixed ciphertext transcript c,
Pr[¬(E0 ∨ E1 ∨ E2) ∧ C = c ∧ PD]
X
Pr[(N′x = Ntj ) ∧ C = c ∧ ¬(E0 ∨ E1) ∧ PD]
≤ minx∈[1..l′ −1]
t∈[1..z],j∈[1..|ct|−1]
X
+
Pr[(N′x = N′j ) ∧ C = c ∧ PD]
j∈[1..l′ −1],j6=x
Since each of the summands in the expression above has a conjunct C = c
for some constant string c, it follows that Ntj = Njt (c, g), and N′x = Nx′ (c, g).
Thus, each of the summands in the first sum can be written (by equation (6))
as
Pr[(g′σx′ ⊕ gtσt = c′x ⊕ ctj ) ∧ C = c ∧ ¬(E0 ∨ E1) ∧ PD(c, g)],
j
where is shorthand for g(IV′ (c)+j), and gtj is shorthand for g(IVt (c)+j). Now,
by lemma 4, each of these probabilities is upper bounded by 2−n+1 ∗Pr[C = c]
as long as IV ′ + σx′ (c) 6= IV t + σjt (c). However, if IV ′ + σx′ (c) = IV t + σjt (c),
then by lemma 5 either (E0 or E1) holds for c, or c′x ⊕ ctj 6= 0, which would
make this probability zero. For the summands in the second sum, lemma 4 is
unconditionally applicable as σx′ (c) 6= σj′ (c).
From equation (15), we then get
g′j
Pr[¬(E0 ∨ E1 ∨ E2) ∧ PD] ≤ (u + v) ∗ 2−n+1
LL′ −1 ′
v
Lemma 7. Pr(f ,g)∈D K [ j=1
Pj = 0 | E2] ≤ 2n −(u+v)
Proof: For each x in [1..v − 1], let E2(x) denote the event E2 holding with this
x. First note that
Pr[
′
L
−1
M
P′j
= 0 | E2] ≤
X
x
j=1
Pr[
′
L
−1
M
P′j = 0 | E2(x)]
(16)
j=1
which follows from Pr[A|B ∨ C] ≤ Pr[A|B] + Pr[A|C] for arbitrary events A, B
and C.
LL′ −1 ′
Now, for any x in [1..L′ − 1], we have j=1
Pj = 0 iff
f
−1
(N′x )
=
M′x
=
′
L
−1
M
(M′j ⊕ g(C′0 + j)) ⊕ g(C′0 + x)
j=1,j6=x
The first equation follows from equations (12), (11), and (10), and the “iff” claim
follows by equation (14). Under the condition E2(x), and given any value of the
RHS of (16), we will show that the LHS of (16) can take (at least) 2n −(µ+v −2)
24
values, each with equal probability, and hence the probability of LHS being equal
to RHS is at most 1/(2n − (u + v)).
To this end, we calculate the above probability by fixing g, each Ntj , and
each M′j (j 6= x), and summing the probability over all the fixings:
Pr[f −1 (N′x ) =
′
L
−1
M
(M′j ⊕ g(C′0 + j)) ⊕ g(C′0 + x) | E2(x)]
j=1,j6=x
X
=
Pr[g = g ∧
j6=x
g,ntj ,m′j (j6=x)
=
X
Pr[f
−1
^
^
M
(Ntj = ntj ) ∧
(M′j = m′j ) ∧ f −1 (N′x ) =
... | E2(x)]
(Nx′ (C, g))
=
M
... | E2(x) ∧ g = g ∧
^
(Ntj = ntj ) ∧
^
(M′j = m′j )] ∗
j6=x
^
^
Pr[g = g ∧ (Ntj = ntj ) ∧
(M′j = m′j ) | E2(x)]
(17)
j6=x
We now show that event E2(x) and C′0 are completely determined by (i)
the whitening function g, and (ii) Ntj (t ∈ [1..z], j ∈ [1..Lt − 1]). First, by
equations (2), (4), (5), (7), and (8), Ntj and g completely determine C. Hence,
the adversarial choice of C′0 , L′ , and in fact the whole of C′ is determined by
these quantities. On fixing g to g, and fixing Ntj to ntj , say the ciphertext C
fixes to c, the plaintext P fixes to p, and the whitened plaintext Mtj fixes to mtj .
Further, say L′ fixes to l′ , and C′j fixes to c′j , j ∈ [0..l′ − 1].
Further, note that for all j ∈ [1..L′ − 1], N′j = C′j ⊕ g(C′0 + σj′ (C)) (by
equations (10) and (9)). Thus, for each j (including x), N′j fixes to a constant
value, say n′j . Thus, the conjunction of the conditions (g = g), (Ntj = ntj ), and
E2(x) is equivalent to the conjunction of (g = g), (Ntj = ntj ), and the condition
that n′x is different from all other n′j , and from all ntj .
The first factor in the above summation (17) now simplifies to
M
Pr[f −1 (n′x ) =
(m′j ⊕ g(c′0 + j)) ⊕ g(c′0 + x) |
^
^
^
^
(n′x 6= n′j )]
(18)
(g = g) ∧ (Ntj = ntj ) ∧
(M′j = m′j ) ∧ (n′x 6= ntj ) ∧
j6=x
t,j
j: j6=x
V
Now note that (g = g) ∧ (Ntj = ntj ) is implied by (g = g) ∧ (f −1 (ntj ) =
mtj ), where mtj is as fixed above. This follows by induction, noting that m1
is determined by g, the fixed adversarial value P 1 , and C10 (also see second
paragraph of proof of lemma 1 for a similar argument). The conditioning in the
above probability 18 is then same as (by (8), (12), and (11))
^
^
^
^
(n′x 6= n′j )
(g = g) ∧ (f −1 (ntj ) = mtj ) ∧
(f −1 (n′j ) = m′j ) ∧ (n′x 6= ntj ) ∧
V
j6=x
t,j
j: j6=x
Since the permutation f is independent of the whitening function g, the above
probability (18) (i.e. the first factor of summation (17)) is at most 1/(2n −(µ+v)).
The lemma follows by summing over all x.
Lemma 8. Pr(f ,g)∈D K [
LL′ −1
j=1
P′j = 0 ∧ (E0 ∨ E1) ∧ PD] ≤ z ∗ 2−n+2
25
Proof: In the following, we will drop the argument C from σ and σ ′ , as it will
be clear from context. We will also use gij as shorthand for g(Ci0 + j).
We first consider the event E0 happening. Since E0(i) implies that for some
′
i
message i : C′0 = Ci0 , it also implies, along with E0(ii) and σL
′ −1 = σ i
L −1 = 0,
′
i
′
i
that NL′ −1 = NLi −1 , and hence ML′ −1 = MLi −1 . Further, E0(i) also implies
N′j = Nij (for j = 1 to L′ − 2), which in turn implies M′j = Mij , and hence also
P′j = Pij . Thus, we have
′
L
−1
M
P′j = 0) ∧ E0
(
j=1
′
L
−1
M
P′j = 0) ∧ E0 ∧ ∃i (M′L′ −1 = MiLi −1 )
′
L
−1
M
P′j = 0) ∧ E0 ∧ ∃i (P′L′ −1 ⊕ giL′ −1 = MiLi −1 )
⇒(
j=1
⇒(
j=1
′
L
−2
M
(Pij ) ⊕ MiLi −1 ⊕ giL′ −1 = 0)
⇒ ∃i (
j=1
′
L
−2
M
(Pij )
≡ ∃i(
⊕
i
L
−2
M
(Pij ) ⊕ giLi −1 ⊕ giL′ −1 = 0)
j=1
j=1
Since G is XOR-universal and L′ < Li , and the initial vectors are safe, we have
Pr[
′
L
−1
M
P′j = 0 ∧ E0 ∧ PD]
j=1
′
L
−2
M
(Pij )
≤ Pr[PD ∧ ∃i(
⊕
j=1
=
=
i
LM
−2
(Pij ) ⊕ giLi −1 ⊕ giL′ −1 = 0)]
j=1
c∈C
′
L
−2
M
X
′
L
−2
M
X
(Pij )
Pr[C = c ∧ PD ∧ ∃i(
⊕
j=1
(Pji (c))
Pr[C = c ∧ PD ∧ ∃i(
(Pij ) ⊕ giLi −1 ⊕ giL′ −1 = 0)]
j=1
⊕
X
i
L
−2
M
(Pji (c)) ⊕ giLi −1 ⊕ giL′ −1 = 0)]
j=1
j=1
c∈C
≤ z · 2−n+1 ·
i
LM
−2
Pr[C = c]
c∈C
where the last inequality follows by lemma 4, and the union bound.
Now, consider the event E1 happening. We have that for some message i :
C′0 = Ci0 + t, with 1 ≤ t ≤ Li − L′ . Note that, for j ∈ [1..L′ − 1], σj′ + t ≤ Li − 2.
For j ∈ [1..L′ − 1], from E1(ii), we then have
N′j = C′j ⊕ g(C′0 + σj′ ) = Ciσ′ +t ⊕ g(Ci0 + t + σj′ ).
j
26
Since σj′ + t ≤ Li − 2, we get N′j = Niσ′ +t , and hence M′j = Miσ′ +t . Now, for
j ∈ [1..L′ − 2], since σj′ = j, we have
j
j
M′j = P′j ⊕ g(C′0 + j) = P′j ⊕ g(Ci0 + t + j).
Since, Mij+t = Pij+t ⊕ g(Ci0 + t + j), we have P′j = Pij+t .
′
′
i
′
i
Also, M′L′ −1 = Mit , as σL
′ −1 = 0. Thus, PL′ −1 ⊕ g(C0 + t + L − 1) = Mt .
Hence,
′
L
−1
M
(
P′j = 0) ∧ E1
j=1
′
L
−1
M
⇒(
P′j = 0) ∧ E1 ∧ ∃i (P′L′ −1 ⊕ git+L′ −1 = Mit )
j=1
′
L
−2
M
(Pij+t ) ⊕ Mit ⊕ git+L′ −1 = 0)
⇒ ∃i (
j=1
′
L
−2
M
(Pij+t ) ⊕ Pit ⊕ git ⊕ git+L′ −1 = 0)
≡ ∃i(
j=1
As L′ ≥ 2, as before using lemma 4, we get an upper bound of z · 2−n+1 .
4.2
Modes using GF(p)
We now prove Theorem 1 for the IAPM scheme as in Fig 3 (section 3.3), i.e
using the mod p construction. We first show that for each i, j, Sji (as defined in
section 3.3) is uniformly distributed in GF(p).
When it is clear from context, we will drop i from the superscript.
Lemma 9. For every j, Sj is uniformly distributed in GF(p).
Proof: First we prove that there is no overflow in the last step of the for-loop,
i.e. while adding (2n − p).
If S0 < (2n − p), then let t be the least j such that Sj ≥ (2n − p), other-wise
t = 0. Clearly, for j ≤ t, the condition (K2 > Sj∗ ) could not have been satisfied,
as K2 < p.
We next show by induction that for j ≥ t, Sj ≥ (2n − p). Clearly, for j = t
it is true by definition of t. If for some j > t, (K2 ≤ Sj∗ ), then Sj = Sj−1 + K2,
and there was no overflow in this addition, hence by induction Sj ≥ (2n − p). If
for some j > t, (K2 > Sj∗ ), then Sj∗ < p, as K2 < p. Thus, there is no overflow
while adding (2n − p), and hence Sj ≥ (2n − p).
Finally, we show that Sj = K2 ∗ (j + IV) mod p, which proves the lemma.
Clearly, this is true for j = 0. Suppose it is true for j − 1, then we show that
Sj = K2 ∗ (j + IV) mod p. Suppose (Sj−1 + K2) < 2n , then Sj = Sj−1 + K2,
and hence Sj = K2 ∗ (j + IV) mod p, by induction. If (Sj−1 + K2) ≥ 2n then,
Sj = (Sj−1 + K2) − 2n + (2n − p), since there is no overflow while adding (2n − p)
as shown in the previous paragraph, and the lemma follows.
27
Lemma 10. For any constant c ∈ [0..2n − 1], and every i, j, i1, j1 such that
j + IVi 6= j1 + IVi1 ,
i1
PrK2∈GF p [Sji − Sj1
= c mod p] ≤ 1/p
Proof: Since from the proof of the previous lemma, Sji = K2 ∗ (j + IVi ) mod p,
the lemma follows.
In the following theorem α(n) denotes the smallest t such that 2n − t is a
prime. For modes of practical interest, the quantity α(n) in the following theorem
is less than 2n. For example, for 128 bit block ciphers, if we let p = 2128 − 159,
this quantity is 159.
Theorem 2. Let A be an adversary attacking the message integrity of IAPM
(t = 1) with the GF(p) construction (fig 3), with f chosen uniformly from set
of permutations, and K2 chosen uniformly from GFp. Let A make at most z
queries in the first stage, totalling at most µ blocks. Let u = µ + z. Let v be
the maximum number of blocks in the second stage. Also, assume that the initial
vectors are chosen safe. If 2v < 2n and 4u2 < 2n , then for adversary A,
Succ < 2 ∗ (u2 + z 2 + 2(u + v + z) + 1 + o(1) + (z + 1) ∗ α(n)) ∗ 2−n
The proof is similar to theorem 1, except that lemma 10 is used in probability
calculations.
5
Message Secrecy
We now prove security in the find-then-guess model, which implies that the
IAPM scheme (figures 1 and 2) is secure for message secrecy. A similar theorem
holds for the mod p version of IAPM (fig 3). We will again be proving our theorem
for the IAPM mode in the random permutation model as in subsection 3.4.
Theorem 3. Let A be a chosen plaintext attack adversary of the encryption
scheme IAPM(G) making at most z queries, these totaling at most u blocks. If
2u2 < 2n , then
3 ∗ u2 + z(2z + u) −n
·2
AdvA ≤
2
Proof:
Let the z queries be divided into y queries in the find stage, one query in the
“choice” stage, and y ′ queries in the guess stage. If IAPM chooses initial vectors
(IVs) randomly (uniformly and independently), then the adversary’s success
probability increases by at most (2z + u) ∗ z ∗ 2−(n+1) , which is the probability
of IVs not being safe.
As in theorem 1, we consider the event PD, under which all the M variables
are pairwise different. However, there is a small difference here. The event PD
in theorem 1 was defined as a function of c and s, as c completely determined
the plaintexts for all the blocks. Here, we have two variants (corresponding to b
being 0 or 1). Thus, we define two variants of the predicate PD, namely PD0 ,
and PD1 , where the predicate PD0 (PD1 ) uses (y + 1)-th plaintext according
to b = 0 (b = 1 resp.).
As in proof of lemma 3, for c = c1 , c2 , ..., ci , i ≤ z, define #(c) to be
P
(2n )!/(2n − ij=1 (|cj | − 1))!.
28
Lemma 11. For every prospective ciphertext c, and bit b
Pr[C = c ∧ PDb (c, g) ∧ b = b] =
1
1
∗ Pr[PDb (c, g)] ∗
#(c)
2
Proof: As in proof of lemma 1, for b, c, g such that PDb (c, g), define F b (c, g) just
like F (c, g) except that the (y + 1)-th plaintext is chosen according to b = b.
Then as argued in lemma 1, the above probability (on left) is
X
Pr[C = c ∧ g = g ′ ∧ PDb (c, g ′ ) ∧ f ∈ F b (c, g ′ ) ∧ b = b]
g′
Again, as argued in lemma 1, C = c is implied by other conjuncts, and the
lemmas follows since b, f , g are independent.
Now, a straightforward variant of lemma 2 follows, i.e. for any b and c,
probability of PDb (c, g) not holding is at most u2 ∗2−n . Similarly, using lemma 11
in the proof of lemma 3 we also have a variant of lemma 3, i.e. for any b,
probability of PDb not holding, conditioned on b = b, is at most u2 ∗ 2−n .
Define ∆ to be the sum, over all c ∈ C, of (1/#(c)). We need an upperbound on
∆. Now, in the statement of lemma 11, summing over C, we get that probability
of PDb conditioned on b = b is at least ∆ times minimum (over all c ∈ C)
probability of PDb (c, g). But, since Pr[PDb | b = b] can be at most 1, we get
that ∆ is at most 1/(1 − u2 ∗ 2−n ), which is at most 2, since 2 ∗ u2 < 2n .
To prove the theorem, we will bound 1/4-th times the following quantity:
X
Prb,(f ,g)∈D K [A(C) = b | b = b] − Prb,(f ,g)∈D K [A(C) 6= b | b = b] |
|
b∈[0..1]
For any c, define δ(c) to be (Pr[A(c) = 1] − Pr[A(c) = 0]). It is clear that
|δ(c)| = 1. We note that for any constant c, probability of A(c) = t is independent
of b, f and g. Thus, we have
X X
Pr[A(C) = b ∧ C = c| b = b] − Pr[A(C) 6= b ∧ C = c| b = b]|
|
c∈C b∈[0..1]
X
=|
δ(c) ∗ (Pr[C = c| b = 1] − Pr[C = c| b = 0])
c
≤|
X
δ(c) ∗ (Pr[C = c ∧ PDb (c, g) | b = 1] − Pr[C = c ∧ PDb (c, g) | b = 0])|
c
X
+
b∈[0..1]
≤|
X
|
X
δ(c) ∗ Pr[C = c ∧ ¬PDb (c, g) | b = b]|
c
δ(c) ∗ (1/#(c)) ∗ (Pr[PD1 (c, g)] − Pr[PD0 (c, g)])|
c
+ Pr[¬PDb | b = 1] + Pr[¬PDb | b = 0]
X
≤|
δ(c) ∗ (1/#(c)) ∗ (Pr[¬PD1 (c, g)] − Pr[¬PD0 (c, g)])| + 2 ∗ u2 ∗ 2−n
c
≤
X
(1/#(c)) ∗ (Pr[¬PD1 (c, g)] + Pr[¬PD0 (c, g)]) + 2 ∗ u2 ∗ 2−n
c
≤ 6 ∗ u2 ∗ 2−n
29
where we have used variant of lemma 2 and (∆ < 2) in the last inequality, and
variant of lemma 3 in the ante-penultimate inequality.
6
Acknowledgements
The author is extremely grateful to Shai Halevi and Pankaj Rohatgi for help
with the proof of message integrity. The author thanks J. Håstad for suggesting
Lemma 1 and the current form of the event PD, which made the proofs more
transparent.
The author also thanks Don Coppersmith, Nick Howgrave-Graham, J.R. Rao,
Ron Rivest, Phil Rogaway, referees of Eurocrypt 2001, and reviewers of this
journal for helpful suggestions. Finally, the author thanks Pau-Chen Cheng for
introducing him to the problem.
References
1. Advanced Encryption Standard, National Institute of Standards and Technology,
U.S. Department of Commerce, FIPS 197 (2001).
2. ANSI X3.106, “American National Standard for Information Systems - Data Encryption Algorithm - Modes of Operation”, American National Standards Institute,
1983.
3. M. Bellare, A. Desai, E. Jokipii, P. Rogaway, “A Concrete Security Treatment
of Symmetric Encryption: Analysis of the DES Modes of Operation”, Proc. 38th
IEEE FOCS, 1997
4. M. Bellare and C. Namprempre, “Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm”, LNCS Vol. 1976, Proc.
Asiacrypt 2000.
5. J. Black, S. Halevi, H. Krawczyk, T. Krovetz and P.Rogaway, “UMAC: Fast and
secure message authentication”, Proc. Advances in Cryptology-CRYPTO 99, LNCS
1666, 1999.
6. M. Bellare, J. Kilian, P. Rogaway, “The Security of Cipher Block Chaining”, JCSS,
Vol. 61, No. 3, Dec 2000, pp. 362-399.
7. M. Bellare, C. Namprempre, “Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm”, Proc. Asiacrypt 2000, T.
Okamoto ed., Springer Verlag 2000.
8. J. Carter, M. Wegman, “Universal Classes of Hash Functions”, JCSS, Vol. 18,
1979, pp 143-154.
9. V.D. Gligor, P.Donescu, “Integrity Aware PCBC Encryption Schemes”, Proc. 7th
Intl. Work. on Security Protocols, Cambridge, LNCS 1796, 1999, pp. 153-171.
10. V.D. Gligor, P. Donescu, “Fast Encryption Authentication: XCBC Encryption and
XECB Authentication Modes”,
http://csrc.nist.gov/encryption/modes/workshop1
11. O. Goldreich, H. Krawczyk, M. Luby, “On the Existence of Pseudorandom Generators”, Proc. FOCS 1988, pp 12-14. Also in SIAM J. of Computing, Vol. 22, No.
6, pp. 1163-75.
12. S. Halevi, “An observation regarding Jutla’s modes of operation”,
http://eprint.iacr.org/2001/015/
13. J. Håstad, “ Message Integrity of IAPM and IACBC”,
http://csrc.nist.gov/CryptoToolkit/modes/proposedmodes/iapm/integrity
proofs.pdf
30
14. ISO/IEC 9797, “Data cryptographic techniques - Data integrity mechanism using
a cryptographic check function employing a block cipher algorithm”, International
Organization for Standardization, Geneva, Switzerland, 1989.
15. C. S. Jutla, “ Encryption Modes with Almost Free Message Integrity”,
http://csrc.nist.gov/CryptoToolkit/modes/workshop1/, July 2000.
16. C. S. Jutla, “ Encryption Modes with Almost Free Message Integrity”, Proc. Eurocrypt 2001, LNCS 2045, 2001.
17. C. S. Jutla, “Tight Lower Bound on Linear Authenticated Encryption”, Proc.
Selected Areas in Cryptography 2003, LNCS 3006, 2003.
18. J. Katz and M. Yung, “Unforgeable Encryption and Adaptively Secure Modes of
Operation”, Proc. Fast Software Encryption, LNCS 1978, 2000.
19. Hugo Krawczyk, “LFSR-based Hashing and Authentication”, Proc. Crypto 94,
LNCS 839, 1994
20. H.W. Kuhn, “Extensive games and the problem of information” in Contributions
to the Theory of Games II, H.W. Kuhn and A. W. Tucker eds., Annals of Mathematical Studies No. 28, Princeton Univ. Press, 1950.
21. M. Luby, “A Simple Parallel Algorithm for the Maximal Independent Set Problem”, SIAM Journal on Computing, Vol. 15:4, pp 1036-55, 1986.
22. M. Luby, “Pseudorandomness and Cryptographic Applications”, Princeton Computer Science Notes, Princeton Univ. Press, 1996.
23. C.H. Meyer, S. M. Matyas, “Cryptography: A New Dimension in Computer Data
Security”, John Wiley and Sons, New York, 1982.
24. M. Naor and O. Reingold, “On the construction of pseudo-random permutations:
Luby-Rackoff revisited”, Proc. 29th ACM STOC, 1997, pp 189-199.
25. M. Naor, and M. Yung, “Universal Hash Functions and their Cryptographic Applications”, Proc. STOC, 1989, pp 33-43.
26. National Bureau of Standards, Data Encryption Standard, U.S. Department of
Commerce, FIPS 46 (1977)
27. National Bureau of Standards, “DES modes of operation”, U.S. Department of
Commerce, FIPS 81, 1980.
28. RFC 1510, “The Kerberos network authentication service (V5)”, J. Kohl and B.C.
Neuman, Sept 1993.
29. RFC 2401,
Security
Architecture
for
the
Internet
Protocol,
http://www.ietf.org/rfc/rfc2401.txt
30. RFC 2246, The TLS Protocol, http://www.ietf.org/rfc/rfc2246.txt
31. P. Rogaway, M. Bellare, J. Black and T. Krovetz, “OCB: A block-cipher mode of
operation for efficient authenticated encryption”, Proc. 8th ACM Conf. Comp. and
Comm. Security (CCS), ACM, 2001.
32. S.G. Stubblebine and V.D. Gligor, “On message integrity in cryptographic protocols”, Proc. 1992 IEEE Comp Soc Symp on Research in Security and Privacy,
1992.