# Why Authenticated Encryption the same message again is not secure?

It is the Exercise 9.14 (9.1) from the book A graduate course in applied cryptography by Boneh and Shoup.

Let $$(E, D)$$ be an AE-secure cipher.

a. $$E_1(k,m):=(E(k,m), E(k,m));$$ $$D_1(k,(c_1,c_2)):= \begin{cases} D(k,c_1) & & \text{ if } D(k,c_1)=D(k,c_2),\\ \text{ reject } & & otherwise \end{cases}$$

b. $$E_2(k,m):=\{c \leftarrow E(k,m),\text{ output } (c,c) \};$$ $$D_2(k,(c_1,c_2)):= \begin{cases} D(k,c_1) & & \text{if } c_1=c_2,\\ \text{reject} & &otherwise \end{cases}$$

Show that part (b) is AE-secure, but part (a) is not.

--

I know that the different of (a) and (b) is that $$E(k,m)$$ use again will product different cipher.

I do the follow:

let the algo use XOR,

let R is the random of algo,

$$c_1 = E(m)\oplus R_1; c_2 = E(m)\oplus R_2$$

$$c_1 \oplus c_2 = R_1 \oplus R_2 = R_3$$

let $$B=u \oplus v$$, where u is the origin header and v is my header.

$$c_1 \oplus B \oplus R_3 = E(m) \oplus B \oplus R_2$$

then the message is changed by me, so it is not an AE-secure.

But my teacher ask me don't assume the algo, and I don't know how can I do now.

I guess the HMAC use same key twice maybe is point, but I still don't know how can I do now.

Thanks!

• Hint: What happens in a) if you ask for an encryption and then swap the ciphertext parts $c_1$ and $c_2$? – SEJPM May 24 '20 at 10:44
• Thanks for your answer. – Sam May 24 '20 at 13:10

Recall the definition: a cipher is AE-secure iff it is secure against chosen ciphertext attacks and has ciphertext ingegrity. Try going through the attack games with $$(E_1,D_1)$$ and $$(E_2,D_2)$$: if the adversary succeeds, can he succeed for $$(E,D)$$?

It's fairly easy to see that $$(E_1,D_1)$$ and $$(E_2,D_2)$$ are CPA-secure. If the adversary can distinguish between the encryption of two messages under either cipher, then he can play the CPA game against the original cipher, submit all the outputs of $$E$$ from the original game, and win the CPA game against the original cipher. This means that the CPA security of $$(E_1,D_1)$$ and $$(E_2,D_2)$$ reduces to that of $$(E,D)$$.

Let's look at the ciphertext integrity game for $$(E_2,D_2)$$. If the adversary can craft a valid ciphertext $$(c,c)$$, then $$(c,c)$$ is not any of the previously obtained ciphertexts by definition of the attack game, which means that the adversary has obtained a new ciphertext $$c$$ for the original cipher $$(E,D)$$. So the ciphertext integrity of $$(E_2,D_2)$$ reduces to that of $$(E,D)$$.

Now let's look at the ciphertext integrity game for $$(E_1,D_1)$$. Suppose the adversary has obtained a valid ciphertext $$(c^1,c^2)$$ by encrypting one message $$m$$. Recall that the objective of the adversary is to create a valid ciphertext that he hasn't seen before. Can he do that?

Yes, easily: $$(c^2,c^1)$$ is a valid ciphertext, and with overwhelming probability $$c^1 \ne c^2$$ so this is a distinct ciphertext from the one the adversary has already seen.

Now suppose the adversary submits $$m$$ again, and obtains a second valid ciphertext $$(c^3,c^4)$$ for the same plaintext $$m$$. Can the adversary create a new valid ciphertext?

Yes: mix and match. For example $$(c^1,c^3)$$ is another valid ciphertext which is distinct from the previous ones with overwhelming probability.

The first counterexample is easily fixable: you could modify $$E_1$$ into $$E_3$$ which

sorts the two ciphertexts, and $$D_1$$ into $$D_3$$ which checks whether the ciphertexts are in the correct order. The cipher $$(E_3,D_3)$$ doesn't suffer from the first counterexample, but is still vulnerable to the second counterexample (either $$(c^1,c^3)$$ or $$(c^3,c^1)$$ is a new valid ciphertext).

The second counterexample is more interesting because it shows that both $$(E_1,D_1)$$ and $$(E_3,D_3)$$ are fundamentally broken. Their weakness is that they allow the adversary to test whether two ciphertexts are the encryption of the same plaintext. Suppose that the adversary wants to know what a certain message $$m$$ is for a given ciphertext $$(c^1,c^2)$$, and they manage to guess that the message is in a small set $$\{m_1,\ldots,m_n\}$$. He can submit each of the $$m_i$$'s for encryption, getting ciphertexts $$\{(c_1^1,c_1^2), \ldots, (c_n^1,c_n^2)\}$$. If he can then test which of the ciphertexts $$\{(c_1^1,c^2), \ldots, (c_n^1,c^2)\}$$ (or the appropriate swapping of each pair for $$(E_3,D_3)$$) is valid, for example by observing the result or the timing of an attempted decryption, that lets the adversary find out what the message was.