Example $3.$ Using these notions of security, we now have a very firm and clear basis to show why ECB mode is not chosen$-$plaintext

secure$,$ and hence should be avoided whenever possible. In particular, consider the following adversary definition:

$A_1^E(1^{})$:$\frac{,}{\frac{?}{?}}$ Block size $$ bits

$p_0$larr$\frac{0^{}}{\frac{?}{?}}$ A block of $0^{\text{'}}s$

$p_1$larr$\frac{1^{}}{\frac{?}{?}}$ A block of all $1^{\text{'}}s$

return $(p_0,p_1)$

$A_2^E(c)$:

if $c=E(0^{})$ then

return $0$

else

return $1$

Since ECB mode is deterministic, the call to the encryption oracle in $E(0^{})$ will return the same ciphertext $c$ as the game oracle

produced for input to $A_2$ if and only if the oracle was playing the game with $b=0,$ so the adversary will always win the game! Since

the probability that the adversary wins is $1,$ the advantage of the adversary is $\frac{1}{2},$ which is clearly a non$-$negligible probability.

Therefore this adversary breaks the security of ECB mode, and shows that ECB mode is not secure against chosen plaintext attacks.

This adversary in fact wins against any deterministic encryption scheme, meaning that no deterministic encryption scheme can be

secure against chosen$-$plaintext attacks! This surprises a lot of people who tend to think of encryption schemes as deterministic:

feed in plaintext, and you get the same ciphertext each time $($although it looks like incomprehensible gibberish$).$ This observation is

the theoretical justification that has led to the way encryption is used in practice: no encryption scheme is typically used in practice

without adding some randomization. Block ciphers use modes $($like CBC mode$)$ that introduce a random initialization vector $($IV$),$

and in$-$practice use of RSA $($which we'll study later$)$ includes randomized padding techniques such as OAEP.

Question $4.$ In Example $3,$ it was shown that ECB mode is insecure with respect to chosen$-$plaintext attacks using an adversary that

made a single call to the encryption oracle. It is actually possible to define an adversary that breaks chosen$-$plaintext security

without using the encryption oracle directly at all! Define such an adversary. $($Hint: Make the challenge plaintexts multiple blocks so

that you can look for block$-$to$-$block patterns in the ciphertext.$)$

Chosen$-$Ciphertext Game and Non$-$Malleable Security

In the last section we defined a game for chosen$-$plaintext security. In this section, we consider giving the adversary access to a

decryption oracle as well as an encryption oracle, resulting in the chosen$-$ciphertext game:

$)b$

In addition to adding access to the decryption oracle, there is one complication: If the adversary has unrestricted access to the

decryption oracle after the challenge ciphertext $c$ is known, then the adversary could just decrypt $c$ and find which of the challenge

plaintexts was encrypted. To avoid this obvious problem, we make a simple change: once ciphertext $c$ has been produced, we

simply don't allow $A_2$ to call the decryption oracle with this ciphertext. There are no other restrictions on the oracles calls, and all

other notions such as advantage are the same as in IND$-$CPA security. The result is what we call IND$-$CCA$2$ security $($the $"2"$ isn't a

typo, and is important, but since this handout doesn't cover the other style of CCA security we don't need to go into what makes

this the second style of CCA security$).$

Solve $$Question $4$ Your presentation is as important as coming up with the solution here. Your solution should be similar to what is in Example $3$ of the reading: clearly define the adversary algorithms, with pseudocode, and analyze probabilities.