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.

- Similar pages