6 Block ciphers, Modes of operation (KL3.6.3 KL3.6.4) ----------------------------------------------------- A pseudorandom function F() with the additional property that F_k is invertible and the inverse F_k^{-1} is computable in polynomial time is known as *block cipher* or *pseudorandom permutation*. It is not hard to see that in this case, Enc_k(m) = F_k(m) Dec_k(c) = F_k^{-1}(c) is semantically secure (hence the name "block cipher"). While a simple PRG already suffices to build a semantically secure cryptosystem those based on PRF as above enjoy stronger properties as we now explain. With the help of a block cipher it is possible to design encryption schemes for messages of arbitrary length using various *modes of operation* that we now describe. In practice, the underlying block ciphers (or pseudorandom functions) are heuristically designed functions like DES or AES which we we will look at later. In some modes of operation it suffices to have a pseudorandom function rather than permutation. In each mode of operation we divide the message to be encrypted into blocks of size n, where n is the security parameter and hence the size of the messages the pseudorandom function can work with. If the length of the whole message is not a multiple of n we must *pad* the last block in some way, e.g. by adding 1000...0. There are various padding schemes which describe this in detail. We henceforth assume that padding has already taken place and that the message comprises l blocks m_1,...,m_l of length n each. Remark: it is possible to vary l from message to message and in this way to encrypt a *stream* of bits rather than a block. One thus effectively obtains so-called *stream ciphers*. Such stream ciphers are also constructed and studied in their own right, see e.g. KL3.4. In this course, we do not consider stream ciphers. ECB mode (electronic code book) - - - - - - - - - - - - - - - - This is the simplest mode of operation and it is actually not secure at all, hence obsolete and included only for historical reasons. Let F be a block cipher. The encryption of the plaintext m = m1..ml under ECB-mode is given by Enc_k(m) = F_k(m1) F_k(m2) ... F_k(ml) i.e. the encodings F_k(mi) of the blocks mi are simply concatenated. This mode receives its name from the fact that it resembles a code book (which for each short message lists the corresponding code) albeit in electronic form. It is easy to see that ECB is not even secure against an eavesdropper. If, assuming blocklength 3, we choose messages m=000000 and m'=000111 we can tell them apart on the basis of the corresponding ciphertexts c,c' alone because c has the form xyzxyz whereas c' does not. This deficiency of ECB shows in practice when it is used to encode images, see KL (2nd ed) for an example. CBC mode (cipher block chaining) - - - - - - - - - - - - - - - - - Here we choose a random initialisation vector IV:{0,1}^n and encrypt as Enc_k(m) = IV c1 c2 c3 ... cl where c1=F_k(IV+m1), c2=F_k(c1+m2), c3=F_k(c2+m3), ... I.e. each block is xor-ed with the encoding of the previous block prior to sending it through F_k. One can show that CBC-mode is CPA-secure, however it suffers from the disadvantage that the ith ciphertext is needed to compute the i+1-st one so the scheme cannot be parallelized. The following variant of CBC-mode has been used in practice (SSL 3.0, TLS 1.0): Chained CBC-mode (not CPA secure) - - - - - - - - - - - - - - - - - Rather than choosing a fresh initialisation vector each time it has been proposed to use instead the last ciphertext, i.e., c_l as the new initialisation vector. This reduces the size of the subsequent message by one block and should intuitively be as good as CBC-mode proper. However, this scheme is vulnerable to a CPA-attack as follows: Suppose that the attacker knows that m_1 is one out of m_1^0 and m_1^1 and that m = m_1 m_2 m_3 has already been encrypted as IV c_1 c_2 c_3. The attacker could now request the encryption of another message starting with the block m_1' := IV + m_1^0 + c_3 The first ciphertext block c_1' then satisfies c_1' = F_k(c_3+m_1') = F_k(IV + m_1^0) Noticing that c_1 = F_k(IV + m_1) we then have m_1 = m_1^0 iff c_1' = c_1. OFB mode (output feedback) - - - - - - - - - - - - - - Here we only need a pseudorandom function. From a randomly chosen initialisation vector IV we first compute pseudorandom strings r1...rl as follows: r1 = F_k(IV), r2 = F_k(r1), ... and then encrypt using xor: Enc_k = IV m1+r1 m2+r2 m3+r3 ... ml+rl So, in essence, we use F_k as a pseudorandom generator of expansion l(n) = l*n and then apply the earlier construction of an EAV-secure scheme from a PRG. Due to the additional randomization via the initialisation vector OFB-mode is even CPA-secure. CTR mode (counter) - - - - - - - - - This mode is similar to OFB, but we compute the pseudorandom string by successively incrementing IV: r_i = F_k(IV+i) /* this + is binary addition, not XOR */ Enc_k = IV m1+r1 m2+r2 m3+r3 ... ml+rl This has the advantage that the ri and hence the ciphertexts can be computed in parallel. A further advantage that it shares with OFB is that the pseudorandom string IVr1..rl can be computed ahead of time and stored until the message to be encrypted arrives. Furthermore, portions of the ciphertext can be decrypted without computing or decrypting anything else. This property is known as *random access*. Theorem: If F is a pseudorandom function then (randomised) counter mode (as described above) is CPA-secure. Proof: (Unlike KL we make the simplifying assumption that message length l is always the same). Let A be an adversary as in the Priv^cpa experiment. We transform it into a distinguisher D for the underlying pseudorandom function as we did in the proof of the last Theorem. Given security parameter n and oracle access to a function h (which is instantiated as either F_k() or a truly random f()) the distinguisher begins by passing the security parameter n to the adversary. Now, whenever the adversary queries its own oracle which it assumes to be of the form Enc_k() then the distinguisher chooses IV:{0,1}^n at random, computes the sequence ri=h(IV+i) and submits IV m1+r1 ... ml+rl to the adversary. When the adversary enters the second phase and outputs two messages m^0, m^1 to distinguish based on their descriptions the distinguisher then chooses a random bit b:{0,1} and IV:{0,1}^n uniformly at random and returns the encryption of m^b w.r.t. IV to A. Further oracle queries from A are answered as before. When A eventually outputs a bit b' reply 1 if b=b' and 0 otherwise. Let us see what the adversary can do when h is a truly random function. Again, the adversary has a certain advantage which we now try to bound from above. Let us assume that for any two encryptions requested the sequences of the counter values do not overlap, i.e. the sets {IV,IV+1,IV+2,...,IV+l} and {IV',IV'+1,IV'+2,...,IV'+l}, where IV and IV' are the respective initialisation vecotrs chosen, are disjoint. In this case, the ciphertexts follow a uniform random distribution and the adversary cannot glean any information whatsoever, i.e. has success probability 1/2. If they do overlap the adversary may or may not use the extra information but if we can show that the probability of this happening is negligible we are good. So, this is what we now try to do. Let us first consider that the overlap happens between the first and second oracle question. In this case, once IV has been chosen, at most 2l values for IV' are unfavorable (or favorable depending on viewpoint): IV, IV-1 ... IV-l, IV+1, IV+2, ... IV+l. Thus, we have a probability of 2l*2^n. Now, since such a clash can happen anywhere we multiply this with q(n), the number of questions being asked. Thus, we get an overall bound of q(n)*2l/2^n on the probability of an overlap. Even if l is not constant, but polynomial in the security parameter this is negligible (noting of course that in view of the time bounds q(n) is polynomially bounded). As a result, the success probability for the adversary can be bounded by 1/2+negl(n). The rest of the argument is as before: If h is F_k(), then let p be the success probability of the adversary A on our new cryptosystem. It is clear that our distinguisher will output 1 with probability p for we have used A according to the rules of the PrivK^cpa-experiment. Since F was assumed to be a PRF we thus know that |p-(1/2+negl(n))| is itself negligible. It then follows that p is bounded by 1/2 plus a negligible function. Q.E.D. We close by remarking that none of the schemes presented so far is secure against chosen ciphertext attacks (CCA) where one may request the decryption of arbitrary ciphertexts different from the challenge. Consider, e.g. the encryption of m as r || F_k(r)+m. An adversary can prepare messages m0=00..0 and m1=11..1. Upon receiving a ciphertext c= r || s corresponding to one of these two the adversary can flip the first bit of s and ask for the decryption of the resulting ciphertext. This must be either 100..0 or 011..1 according to whether m was 00..0 or 11..1.