Private-Key Encryption.pdf

Private-Key Encryption Saravanan Vijayakumaran Department of Electrical Engineering, IIT Bombay August 11, 2023 1 Computational Secrecy Computational Secrecy: Weaker notion of secrecy Perfect secrecy requirement Absolutely no information about an encrypted message is leaked, even to an adversary...

Private-Key Encryption Saravanan Vijayakumaran Department of Electrical Engineering, IIT Bombay August 11, 2023 1 Computational Secrecy Computational Secrecy: Weaker notion of secrecy Perfect secrecy requirement Absolutely no information about an encrypted message is leaked, even to an adversary with unlimited computational power Computational secrecy requirement Information about the encrypted message is leaked with a tiny probability to eavesdroppers with bounded computational power 2 Computational Security Definitions In general, computational security definitions incorporate two relaxations Security is only guaranteed against realistic adversaries that run for some feasible amount of time Adversaries can potentially succeed with some very small probability Precise definitions of the above relaxations are needed Two approaches: concrete and asymptotic 3 The Concrete Approach Upper bounds the success probability of an adversary running for some specified time A concrete definition of security takes the following form A scheme is (t, ϵ)-secure is any adversary running for time at most t succeeds in breaking the scheme with probability at most ϵ. −60 Example: A (200 years, 2 )-secure scheme would guarantee that no adversary running for at most 200 years can break the scheme with probability better than 2−60 More convenient to measure running time in terms of CPU cycles, as in (280 cycles, 2−60 ) 4 Values for t and ϵ How large can t be? How small should ϵ be? Consider an private-key encryption scheme with a n-bit key Key space has size 2 n Brute-force adversary succeeds in breaking scheme with probability at most 2ctn for some constant c ​ For c = 1 and n = 64, a 4 GHz processor with 16 cores requires at most 10 years Minimum recommended key length is n = 128 Estimates of time since Big Bang = 258 seconds An event that occurs with probability 2−60 each second is expected to occur once every 10 billion years 5 The Asymptotic Approach Based on complexity theory Cryptographic schemes are parametrized by an integervalued security parameter n (typically the key length) Running time of the adversary and its success probability are viewed as functions of n This notion of security is asymptotic since it depends on a scheme’s behavior for sufficiently large values of n 6 Efficient Adversaries Realistic adversaries are modeled by probabilistic algorithms running in time polynomial in n An algorithm A runs in polynomial time if there exists a ∈ {0, 1}∗ , the computation of A(x) terminates within at most p(∣x∣) steps where ∣x∣ denotes the length of x polynomial p such that, for every input x An algorithm with polynomial running time is said to be efficient Composition of efficient algorithms is efficient If p1 , p2 are two polynomials, then p(n) is also a polynomial ​ ​ = p1 (p2 (n)) ​ 7 Probabilistic Algorithm Algorithms having access to a sequence of unbiased, independent random bits Random bits can be represented as r ← {0, 1}∗ An algorithm A runs in polynomial time if there exists a ∈ {0, 1}∗ and ∗ r ← {0, 1} , the computation of A(x, r) terminates within at most p(∣x∣ + ∣r∣) steps polynomial p such that, for every input x 8 Negligible Probabilities Small probabilities of success are modeled by probabilities smaller than any inverse polynomial in n Called negligible probabilities Definition: A function f from the natural numbers to the non-negative real numbers is negligible if for every positive polynomial p there is an N such that for all integers n > N it holds that f (n) < 1 . p(n) −n − n Examples: 2 , 2 , − log n ​ n ​ An arbitrary negligible function is denoted by negl 9 Properties of Negligible Probabilities 10 General Framework for Asymptotic Security Definitions A scheme is secure if for every probabilistic polynomialtime adversary A carrying out an attack of a formally specified type, the probability that A succeeds in the attack (where success is also formally specified) is negligible A scheme is secure if for every PPT adversary A carrying out an attack, and every polynomial p, there is an integer N such that when n > N the probability that A succeeds in 1 the attack is less than p(n) ​ 11 Asymptotic Security Example Suppose that a scheme is asymptotically secure Suppose an adversary running for n3 minutes can succeed in “breaking the scheme” with probability ≤ 240 2n ​ ≤ 40, this adversary can run for 403 minutes (about 6 weeks) and break the scheme with probability 1 For n For n 3 = 50, this adversary can run for 50 minutes (about 1 3 months) and break the scheme with probability 1000 ​ = 500, this adversary running for 200 years can −500 break the scheme with probability ≈ 2 For n Security parameter allows us to “tune” the security level of the scheme to a desired level 12 Choices Made in Defining Asymptotic Security 13 Necessity of the Relaxations Both PPT adversaries and negligible probabilities of success are needed to allow practical encryption schemes Consider private-key encryption where ∣K∣ < ∣M∣ Two attacks are always applicable Given ciphertext c, an adversary can decrypt c using all keys k ∈ K. As ∣K∣ < ∣M∣, there is information leakage. Given ciphertexts c1 , c2 , … , cl corresponding to known ​ ​ ​ messages m1 , m2 , … , ml , an adversary can guess a ​ uniform key k ​ ​ ∈ K and check Deck (ci ) = mi for all i. ​ ​ If checks pass, adversary can use k to decrypt ​ 14 Defining Computationally Secure Encryption 16 Private-key Encryption A private-key encryption scheme is a triple of PPT algorithms (Gen, Enc, Dec) such that: 1. k ← Gen(1n ). 2. For m ∈ {0, 1} , c ← Enck (m). 3. Deck (c) ​ ∗ ​ = m or error indicator ⊥. For every m, c, k , we have Deck (Enck (m)) ​ ​ =m 17 Indistinguishability in the presence of an eavesdropper We consider the ciphertext-only attack where the adversary observes a single ciphertext Our definition will resemble perfect indistinguishability definition except for two differences The experiment is parametrized by n We require the adversary to output equal length messages m0 , m1 ​ ​ 18 Why equal length messages? We require ∣m0 ∣ = ∣m1 ∣ because it is impossible to support arbitrary length messages ​ ​ All commonly used encryption schemes reveal length of the plaintext Padding must be used if length of the message has sensitive information 19 Adversarial Indistinguishability Experiment eav Consider the following experiment PrivKA,Π (n): n A is given 1 and outputs arbitrary m0 , m1 ∈ M with ​ ​ ​ ∣m0 ∣ = ∣m1 ∣ ​ ​ A key k is generated using Gen, and a uniform bit b ∈ {0, 1} is chosen Ciphertext c ← Enck (mb ) is computed and given to A ​ ​ This ciphertext c is called the challenge ciphertext A outputs a bit b ′ The output of the experiment is defined to be 1 if b′ and 0 otherwise eav = b, 20 Security Definition A private-key encryption scheme Π = (Gen, Enc, Dec) has indistinguishable encryptions in the presence of an eavesdropper, or is EAV-secure, if for all PPT adversaries A there is a negligible function negl such that, for all n, eav Pr [PrivKA,Π (n) ​ 1 = 1] ≤ + negl(n). 2 ​ An perfectly secure scheme is also EAV-secure 21 Alternative Definition of EAV-Security eav ′ Let outA (PrivKA,Π (n, b)) denote the output b of A ​ ​ when mb is encrypted ​ A private-key encryption scheme Π = (Gen, Enc, Dec) is EAV-secure, if for all PPT adversaries A there is a negligible function negl such that, for all n, ∣Pr [outA (PrivKeav (n, 0)) = 1] A,Π ∣ eav − Pr [outA (PrivKA,Π (n, 1)) = 1]∣∣ ​ ​ ​ ​ ​ ​ ​ ​ ≤ negl(n). Adversary “behaves the same” irrespective of whether it observes an encryption of m0 or of m1 ​ ​ 22 Semantic Security Can we define computationally secure encryption without an experiment? Definition needs to be the analog of perfect secrecy for computationally bounded adversaries Semantic security is that analog First definition of computationally secure encryption to be proposed Difficult to work with EAV-security and semantic security are equivalent 24 Semantic Security Definition A private-key encryption scheme Π = (Enc, Dec) is semantically secure in the presence of an eavesdropper if for every PPT algorithm A there exists a PPT algorithm A′ such that for any PPT algorithm Samp and polynomial-time computable functions f and h, the following is negligible: ∣ n Pr [A (1 , Enck (m), h(m)) = f (m)] ​ ∣ ​ ′ n − Pr [A (1 , ∣m∣, h(m)) = f (m)] ∣ ​ ​ ∣ where k is chosen uniformly from {0, 1} n 25 Semantic Security and EAV-Security are Equivalent A private-key encryption scheme is EAV-secure if and only if it is semantically secure in the presence of an eavesdropper EAV-security is simpler and easier to work with We will follow a similar strategy for other definitions of secure encryption 26 Constructing an EAVSecure Encryption Scheme 28 Strategy 1. Define pseudorandom generators 2. Construct an encryption scheme using a pseudorandom generator 3. Prove that the existence of an attacker that can “break” the encryption scheme implies that the generator is not pseudorandom 29 Pseudorandom Generators A pseudorandom generator is a polynomial-time deterministic algorithm for transforming a short, uniform bitstring called the seed into a longer, “uniform-looking” output string. Pseudorandomness is a property of a distribution on strings Some desirable properties of a pseudorandom generator: Any bit of the output should be equal to 1 with probability close to 12 . ​ The parity of any subset of the output bits should be even with probability close to 12 . ​ 30 Good Pseudorandom Generators A good pseudorandom generator should pass all efficient statistical tests For any efficient statistical test or distinguisher D , the probability that D returns 1 given the output of the pseudorandom generator should be close to the probability that D returns 1 when given a uniform string of the same length. 31 Pseudorandom Generator Definition Let l be a polynomial and let G be a deterministic polynomial-time algorithm such that for any n and s ∈ {0, 1} , we have ∣G(s)∣ = l(n) n G is a pseudorandom generator if the following conditions hold: 1. Expansion: For every n it holds that l(n) > n. 2. Pseudorandomness: For any PPT algorithm D , there is a negligible function negl such that ∣Pr [D (G(s)) = 1] − Pr [D(r) = 1]∣ ≤ negl(n), ​ where 32 Understanding the Definition Example of a non-pseudorandom generator Define G : {0, 1} → {0, 1} n G(s) = n+1 as n s∥ (⊕i=1 si ) ​ ​ The ∥ operator represents string concatenation What happens if remove the restriction that D is polynomial time? 33 Stream Ciphers Stream ciphers are practical systems which behave like pseudorandom generator Example: A5/1 34 A Secure Fixed-Length Encryption Scheme Let G be a PG with expansion factor l Define a private-key encryption scheme for messages of length l as follows: Gen: On input 1n , choose k uniformly from {0, 1}n . Enc: Given k ∈ {0, 1}n and message m ∈ {0, 1}l(n) , output the ciphertext c := G(k) ⊕ m. ​ Dec: Given k ∈ {0, 1}n and ciphertext c ∈ {0, 1}l(n) , output the message m := G(k) ⊕ c. ​ 35 Security of Construction If G is a pseudorandom generator, then the construction is EAV-secure, i.e. for any PPT adversary A there is a negligible function negl such that eav Pr [PrivKA,Π (n) ​ 1 = 1] ≤ + negl(n). 2 ​ ​ 36 Security Proof Overview Note: If a one-time pad is used instead of G(k), the system is EAV-secure Key idea: If a PPT adversary A can distinguish between the encryptions of m0 and m1 , then it can distinguish between ​ ​ G(k) and a uniformly random bitstring We will construct a distinguisher D that uses A as a subroutine 37 Distinguisher Definition D is given a string w ∈ {0, 1}l(n) Run A(1n ) to obtain a pair of messages m0 , m1 ​ {0, 1} ​ ∈ l(n) Choose a uniform bit b ∈ {0, 1}. Set c := w ⊕ mb . Give c to A and get b′ . If b otherwise. ​ = b′ output 1 and output 0 If A succeeds, D decides that w is a pseudorandom string and if A fails D decides w is a random string. 38 View of the Adversary ~ Let Π be the one-time pad scheme with length l(n) When w is chosen uniformly from {0, 1}l(n) , then the view eav ~ (n) of A is identical to the view of A in PrivKA,Π ​ When w generated by choosing k uniformly from {0, 1} n := G(k), then the view of A is identical to eav the view of A in PrivKA,Π (n) and setting w ​ 39 Stronger Security Notions Security for Multiple Encryptions CPA-Security CPA-Security for Multiple Encryptions 41 Multiple-Message Eavesdropping Experiment mult Consider the following experiment PrivKA,Π (n): n ​ A is given 1 and outputs a pair of equal-length lists of messages M0 = (m0,1 , … , m0,t ) and M1 = (m1,1 , … , m1,t ) with ∣m0,i ∣ = ∣m1,i ∣ for all i ​ ​ ​ ​ ​ ​ ​ ​ A key k is generated using Gen, and a uniform bit b ∈ {0, 1} is chosen Ciphertext vector C = (c1 , … , ct ) is given to A where ​ ​ ci ← Enck (mb,i ) ​ ​ A outputs a bit b ​ ′ The output of the experiment is defined to be 1 if b′ and 0 otherwise = b, 42 Security Definition A private-key encryption scheme Π = (Gen, Enc, Dec) has indistinguishable multiple encryptions in the presence of an eavesdropper if for all PPT adversaries A there is a negligible function negl such that, mult Pr [PrivKA,Π (n) ​ 1 = 1] ≤ + negl(n). 2 ​ The one-time pad does not have indistinguishable multiple encryptions in the presence of an eavesdropper 43 Chosen-Plaintext Attacks Adversary can influence the honest parties sharing the key to encrypt messages of its choice and send it over the public channel Chosen-plaintext attacks in the real world In WW2, British placed mines knowing that the Germans would encrypt and transmit the mine locations Battle of Midway How can we model such an adversary? 44 The Encryption Oracle Chosen-plaintext attacks are modeled by giving the adversary A access to an encryption oracle Oracle: a place where people could go to ask the gods for advice and information about the future A has access to Enck (⋅) as a black box for an unknown k ​ When A queries this oracle with a message m as input, the oracle returns a ciphertext c ← Enck (m) ​ 45 CPA Indistinguishability Experiment cpa Consider the following experiment PrivKA,Π (n): n ​ A key k is generated using Gen(1 ) A is given 1n and oracle access to Enck (⋅), and outputs pair of messages m0 , m1 of the same length ​ ​ A uniform bit b Ciphertext c ​ ∈ {0, 1} is chosen ← Enck (mb ) is computed and given to A ​ ​ A continues to have oracle access to Enck (⋅), and outputs a bit b′ ​ The output of the experiment is 1 if b′ otherwise = b, and 0 46 Security Definition A private-key encryption scheme Π = (Gen, Enc, Dec) has indistinguishable encryptions under a chosenplaintext attack, or is CPA-secure, if for all PPT adversaries A there is a negligible function negl such that cpa Pr [PrivKA,Π (n) ​ 1 = 1] ≤ + negl(n). 2 ​ 47 CPA-Security for Multiple Encryptions We could extend the CPA indistinguishability experiment to multiple encryptions using lists of plaintexts We take a different approach that models attackers that can adaptively choose its input to the encryption oracle Instead of Enck (⋅) we give the adversary access to a left-or​ right oracle LRk,b ​ On input m0 , m1 , the oracle gives LRk,b (m0 , m1 ) ​ ​ ​ ​ ​ = Enck (mb ) ​ ​ 48 LR-Oracle Experiment LR-cpa Consider the following experiment PrivKA,Π (n): n ​ A key k is generated using Gen(1 A uniform bit b ) ∈ {0, 1} is chosen A is given 1 and oracle access to LRk,b (⋅, ⋅) n ​ A outputs a bit b′ The output of the experiment is 1 if b′ otherwise = b, and 0 49 Security Definition A private-key encryption scheme Π = (Gen, Enc, Dec) has indistinguishable multiple encryptions under a chosen-plaintext attack, or is CPA-secure for multiple encryptions, if for all PPT adversaries A there is a negligible function negl such that LR-cpa Pr [PrivKA,Π (n) ​ 1 = 1] ≤ + negl(n). 2 ​ 50 Equivalence of CPA-Security Notions We have seen three security notions stronger than EAVsecurity Security for Multiple Encryptions CPA-Security CPA-Security for Multiple Encryptions CPA-Security for Multiple Encryptions Multiple Encryptions Theorem: CPA-Security Encryptions ⟹ Security for ⟹ CPA-Security for Multiple 51 Constructing a CPASecure Encryption Scheme 53 Strategy 1. Define pseudorandom functions 2. Construct an encryption scheme using a pseudorandom function 3. Prove that the existence of an attacker that can “break” the encryption scheme implies that the function is not pseudorandom 54 Pseudorandom Functions Pseudorandom functions are “random-looking” functions In this case, pseudorandomness will be a property of a distribution over functions Given a security parameter n, a keyed function F : {0, 1} lkey (n) ​ × {0, 1} lin (n) ​ → {0, 1} lout (n) ​ is a two-input function, where the first input is called the key and is denoted by k We will only consider efficient keyed functions If the key k is fixed, we get a single-input function Fk : {0, 1} ​ lin (n) ​ → {0, 1} lout (n) ​ 55 Uniformly Choosing a Function Let Funcn be the set of all functions with domain and range ​ equal to {0, 1}n A keyed function F is said to be pseudorandom if the function Fk (for a uniform key k ) is indistinguishable from a ​ function chosen uniformly from Funcn Note that ∣Funcn ∣ ​ =2 ​ n⋅2n For a length-preserving Fk , choosing k ​ ← {0, 1}n induces a distribution over at most 2n functions with domain and range equal {0, 1}n 56 Distinguisher for Pseudorandom Functions The distinguisher should be allowed to query the function D is given access to an oracle O which is either equal to Fk (for uniform k ) or f (for uniform f from Funcn ) ​ ​ D can query the oracle O at any point x ∈ {0, 1}n and the oracle returns O(x) D can adaptively query the oracle but can ask only polynomially many queries. 57 Pseudorandom Function Definition Let F be an efficient, length-preserving, keyed function. F is a pseudorandom function if for all PPT distinguishers D , there is a negligible function negl such that: ∣ ​ ∣ Pr [D Fk (⋅) ​ (1 ) = 1] − Pr [D n f (⋅) (1 ) = 1] n ​ ≤ negl(n), ∣ ​ ∣ ​ where the first probability is taken over uniform choice of k ∈ {0, 1}n and the randomness of D, and the second probability is taken over uniform choice of 58 Distinguisher does not know the Key D is not given access to the key k If k is known, it is easy to construct a distinguisher which succeeds with non-negligible probability 59 Example of a Non-Pseudorandom Function Example of a non-pseudorandom, length-preserving, keyed function F (k, x) = k ⊕ x 60 CPA-Secure Encryption from Pseudorandom Functions Let F be a pseudorandom function Define a private-key encryption scheme for messages of length n as follows: Gen: On input 1n , choose k uniformly from {0, 1}n . Enc: Given k ∈ {0, 1}n and message m ∈ {0, 1}n , choose uniform r ∈ {0, 1}n and output the ciphertext c := ⟨r, Fk (r) ⊕ m⟩. ​ ​ Dec: Given k ∈ {0, 1}n and ciphertext c = ⟨r, s⟩, output the plaintext message m := Fk (r) ⊕ s. ​ 61 ​ Security Claim Theorem: If F is a pseudorandom function, then the above construction is a CPA-secure private-key encryption scheme for messages of length n Security Proof Overview Key idea: If a PPT adversary A can distinguish between message encryptions using f and Fk , then it can be used ​ to distinguish between f and Fk ​ We will construct a distinguisher D that uses A as a subroutine 62 Proof of Security for CPA-Secure Scheme 64 Replacing the Pseudorandom Function with a Random Function Let Π = (Gen, Enc, Dec) be the same as Π = (Gen, Enc, Dec) with Fk replaced with f ← Funcn ​ Gen(1n ) chooses a uniform f from Funcn ​ ​ Not practical but can be defined for the sake of the proof Let A be any PPT adversary which uses at most q(n) encryption oracle queries We will show that ∣ ​ ∣ cpa Pr [PrivKA,Π (n) ​ = 1] − ​ ≤ negl(n), cpa Pr [PrivKA,Π (n) ​ = 1] ∣ ​ ∣ ​ 65 Distinguisher Definition (1/3) D is given 1n and access to an oracle O : {0, 1}n → {0, 1}n . It uses A as a subroutine 1. Whenever A queries the encryption oracle on message m ∈ {0, 1}n , answer as follows i. Choose uniform r ∈ {0, 1}n ii. Query O(r) and obtain response y iii. Return the ciphertext ⟨r, y ⊕ m⟩ to A 66 Distinguisher Definition (2/3) 2. When A outputs messages m0 , m1 ​ uniform bit b ∈ {0, 1}n , choose a ​ ∈ {0, 1} and then i. Choose uniform r ∈ {0, 1} n ii. Query O(r) and obtain response y iii. Return the ciphertext ⟨r, y ⊕ mb ⟩ to A ​ 67 Distinguisher Definition (3/3) 3. Continue answering encryption oracle queries of A ′ 4. Once A outputs a bit b , output 1 if b ′ = b and 0 otherwise. 68 Finishing the Proof We have ∣ ​ ∣ ∣ cpa Pr [PrivKA,Π (n) ​ = Pr [D ∣ ​ ​ Fk (⋅) ​ = 1] − cpa Pr [PrivKA,Π (n) (1 ) = 1] − Pr [D n ​ (1 ) = 1] f (⋅) n ≤ negl(n), = 1] ∣ ​ ∣ We will show that cpa Pr [PrivKA,Π (n) ​ 1 q(n) = 1] ≤ + n 2 2 ​ ​ 69 Upperbound on the Adversary’s Success Probability (1/2) cpa In PrivK ( n) the ciphertext corresponding to m is A,Π ​ ⟨r, f (r) ⊕ m⟩ Let r ∗ be the randomness used when generating the challenge ciphertext ⟨r ∗ , f (r ∗ ) ⊕ mb ⟩ ​ Two possibilities ∗ r is never used when answering any of A’s encryptionoracle queries ∗ r is used when answering at least one of A’s encryption-oracle queries 70 Upperbound on the Adversary’s Success Probability (2/2) ∗ Let repeat denote the event that r was used by the oracle to answer at least one of A’s queries Let repeatc be the complement of repeat. Then we have cpa Pr [PrivKA,Π (n) ​ = ​ = 1] cpa Pr [PrivKA,Π (n) ​ + = 1 ⋂ repeat] cpa Pr [PrivKA,Π (n) ​ q(n) 1 ≤ n + . 2 2 ​ Finally, we have = 1 ⋂ repeat ] c ​ ​ 71 Pseudorandom Permutations In practice, constructions of pseudorandom permutations are used instead of pseudorandom functions We will consider pseudorandom permutations abstractly for now Practical candidate constructions will be described later 73 Pseudorandom Permutations Let Permn be the set of all permutations (bijections) on ​ {0, 1}n ∣Permn ∣ = (2n )! ​ A function F : {0, 1}lkey (n) × {0, 1}lin (n) → {0, 1}lin (n) ​ ​ is called a keyed permutation if for all k ​ ∈ {0, 1}lkey (n) , ​ Fk is a permutation. ​ F −1 is said to be efficient if both Fk (x) and Fk (y) have ​ ​ polynomial-time algorithms for all k, x, y . lin (n) is called the block length of F . ​ 74 Definition of Pseudorandom Permutation A pseudorandom permutation is a permutation which cannot be efficiently distinguished from a random permutation Let F be an efficient, length-preserving, keyed permutation. F is a pseudorandom permutation if for all PPT distinguishers D , there is a negligible function negl such that: ∣ Pr [DFk (⋅) (1n ) = 1] − Pr [Df (⋅) (1n ) = 1] ∣ ​ ​ ∣ ​ where ≤ negl(n), ​ ∣ ​ 75 Strong Pseudorandom Permutations A strong pseudorandom permutation is a permutation which cannot be efficiently distinguished from a random permutation even if the distinguisher is given oracle access to the inverse of the permutation In practice, constructions of strong pseudorandom permutations are called block ciphers 76 Definition of Strong Pseudorandom Permutation Let F be an efficient, length-preserving, keyed permutation. F is a strong pseudorandom permutation if for all PPT distinguishers D , there is a negligible function negl such that: ∣ ​ ∣ ​ Pr [D Fk (⋅),Fk−1 (⋅) ​ ​ − Pr [D (1n ) = 1] f (⋅),f −1 (⋅) ≤ negl(n), (1 ) = 1] n ∣ ​ ​ ∣ where 77 Block Cipher Modes of Operation Our CPA-secure construction has ciphertext length which is double the plaintext length Fortunately, there exist secure constructions based on block ciphers that have lower overheads 79 Electronic Code Book (ECB) Mode Insecure: Should not be used in practice! Let m = ⟨m1 , m2 , … , ml ⟩ where mi ∈ {0, 1}n . ​ ​ ​ ​ Let F be a block cipher with block length n. c := ⟨Fk (m1 ), Fk (m2 ), … , Fk (ml )⟩ ​ ​ ​ ​ ​ ​ ECB is deterministic and cannot be CPA-secure. 80 ECB Example Image encrypted using ECB mode1 1. Encrypted Image Attribution: Larry Ewing, [email protected] 81 Cipher Block Chaining (CBC) Mode Let m = m1 , m2 , … , ml where mi ∈ {0, 1} . n ​ ​ ​ ​ Let F be a length-preserving block cipher with block length n. A uniform initialization vector (IV) of length n is chosen. c0 = IV . For i = 1, … , l, ci := Fk (ci−1 ⊕ mi ) ​ ​ ​ ​ ​ 82 Counter (CTR) Mode Let m = m1 , m2 , … , ml where mi ∈ {0, 1} ​ ​ ​ n ​ Let F be a length-preserving block cipher with length n To encrypt a message of length l <2 n/4 blocks, a uniform IV of length 3n/4 is chosen c0 = IV . For i = 1, … , l, ci := Fk (IV ∥i) ⊕ mi . ​ ​ ​ ​ 83 Further Reading Chapter 3 from Katz & Lindell 84