CS 4803 Computer and Network SecurityAlexandra (Sasha) BoldyrevaSymmetric encryption1Symmetric encryption schemesA scheme SE is specified by a key generation algorithm K, an encryption algorithm E, and a decryption algorithm D.Sender SAKKEKCMDKC MSE=(K,E,D) It is required that for every M󲰉MsgSp and every Kthat can be output byK, D(K,E(K,M))=MMsgSp-message spaceReceiver Ror 󲰥or 󲰥2•Often the key generation algorithm simply picks a random string from some key space KeySp (e.g. {0,1}k for some integer k).•In this case we will say that a scheme SE is defined by KeySp and two algorithms: SE=(KeySp,E,D) •The encryption algorithm can be either •randomized (take as input a random string)•or stateful (take as input some state (e.g. counter) that it can update)3Block cipher modes of operation•Modes of operation define how to use a block cipher to encrypt long messages•We will often assume that the message space consists of messages whose length is multiple of a block length4Electronic Code Book (ECB) modeM[1]EKC[1]M[2]EKC[2]M[m]EKC[m]Encryption algorithm E Let E:{0,1}k!{0,1}n!{0,1}n be a block cipher. ECB=({0,1}k,E,D):C[1]EKM[1]C[2]EKM[2]C[m]EKM[m]-1-1 -1Decryption algorithm D 5Electronic Code Book (ECB) modeBellare and Rogaway 5algorithm EK(M)if (|M| mod n != 0 or |M | = 0) then return ⊥Break M into n-bit blocks M[1] · · · M[m]for i ← 1 to m doC[i] ← EK(M[i])C ← C[1] · · · C[m]return Calgorithm DK(C)if (|C| mod n != 0 or |C| = 0) then return ⊥Break C into n-bit blocks C[1] · · · C[m]for i ← 1 to m doM[i] ← E−1K(C[i])M ← M [1] · · · M [m]return MFigure 4.1: ECB mode.did not make any random choices. (That does not mean it is not, technically, arandomized algorithm; it is simply a randomized algorithm that happened not tomake any random choices.)The next scheme, cipher-block chaining (CBC) with random initial vector, is themost popular block-cipher mode of operation, used pervasively in practice.Scheme 4.4 [CBC$ mode] Let E: K × {0, 1}n→ {0, 1}nbe a block cipher.Operating it in CBC mode with random IV yields a stateless symmetric encryptionscheme, SE = (K, E, D). The key generation algorithm simply returns a randomkey for the block cipher, K$← K. The encryption and decryption algorithms aredepicted in Fig. 4.2. The IV (“initialization vector”) is C[0], which is chosen atrandom by the encryption algorithm. This choice is made independently each timethe algorithm is invoked.For the following schemes it is useful to introduce some notation. If n ≥ 1 and i ≥ 0are integers then we let [i]ndenote the n-bit string that is the binary representationof integer i mod 2n. If we use a number i ≥ 0 in a context for which a stringI ∈ {0, 1}nis required, it is understood that we mean to replace i by I = [i]n. Thefollowing is a counter-based version of CBC mode, whose security is considered inSection 4.5.3.Scheme 4.5 [CBCC mode] Let E: K × {0, 1}n→ {0, 1}nbe a block cipher.Operating it in CBC mode with counter IV yields a stateful symmetric encryptionBellare and Rogaway 5algorithm EK(M)if (|M| mod n != 0 or |M| = 0) then return ⊥Break M into n-bit blocks M [1] · · · M [m]for i ← 1 to m doC[i] ← EK(M[i])C ← C[1] · · · C[m]return Calgorithm DK(C)if (|C| mod n != 0 or |C| = 0) then return ⊥Break C into n-bit blocks C[1] · · · C[m]for i ← 1 to m doM[i] ← E−1K(C[i])M ← M [1] · · · M [m]return MFigure 4.1: ECB mode.did not make any random choices. (That does not mean it is not, technically, arandomized algorithm; it is simply a randomized algorithm that happened not tomake any random choices.)The next scheme, cipher-block chaining (CBC) with random initial vector, is themost popular block-cipher mode of operation, used pervasively in practice.Scheme 4.4 [CBC$ mode] Let E: K × {0, 1}n→ {0, 1}nbe a block cipher.Operating it in CBC mode with random IV yields a stateless symmetric encryptionscheme, SE = (K, E, D). The key generation algorithm simply returns a randomkey for the block cipher, K$← K. The encryption and decryption algorithms aredepicted in Fig. 4.2. The IV (“initialization vector”) is C[0], which is chosen atrandom by the encryption algorithm. This choice is made independently each timethe algorithm is invoked.For the following schemes it is useful to introduce some notation. If n ≥ 1 and i ≥ 0are integers then we let [i]ndenote the n-bit string that is the binary representationof integer i mod 2n. If we use a number i ≥ 0 in a context for which a stringI ∈ {0, 1}nis required, it is understood that we mean to replace i by I = [i]n. Thefollowing is a counter-based version of CBC mode, whose security is considered inSection 4.5.3.Scheme 4.5 [CBCC mode] Let E: K × {0, 1}n→ {0, 1}nbe a block cipher.Operating it in CBC mode with counter IV yields a stateful symmetric encryption6Cipher-block chaining (CBC) mode with random IVM[1]EKC[1]M[2]EKC[2]M[m]EKC[m]C[1]EKM[1]C[2]EKM[2]C[m]EKM[m]Encryption algorithm E -1-1 -1Let E:{0,1}k!{0,1}n!{0,1}n be a block cipher. CBC$=({0,1}k,E,D):Decryption algorithm D IVIV"{0,1}n󲰟 󲰟 󲰟󲰟 󲰟 󲰟IVIV$7Cipher-block chaining (CBC) mode with random IV6 SYMMETRIC ENCRYPTIONalgorithm EK(M)if (|M | mod n != 0 or |M| = 0) then return ⊥Break M into n-bit blocks M[1] · · · M [m]C[0] ← IV$← {0, 1}nfor i ← 1 to m doC[i] ← EK(C[i − 1] ⊕ M [i])C ← C[1] · · · C[m]return &IV, C'algorithm DK(&IV, C')if (|C| mod n != 0 or |M | = 0) then return ⊥Break C into n-bit blocks C[1] · · · C[m]C[0] ← IVfor i ← 1 to m doM[i] ← E−1K(C[i]) ⊕ C[i − 1])M ← M [1] · · · M[m]return MFigure 4.2: CBC$ mode.scheme, SE = (K, E, D). The key generation algorithm simply returns a randomkey for the block cipher, K$← K. The encryptor maintains a counter ctr which isinitially zero. The encryption and decryption algorithms are depicted in Fig. 4.3.The IV (“initialization vector”) is C[0], which is set to the current value of thecounter. The counter is then incremented each time a message is encrypted. Thecounter is a static variable, meaning that its value is preserved across invocationsof the encryption algorithm.The CTR (counter) modes that follow are not much used, to the best of our knowl-edge, but perhaps wrongly so. We will see later that they have goo d privacy prop-erties. In contrast to CBC, the encryption procedure is parallelizable, which can beexploited to speed up the process in the presence of hardware support. It is