CBC variant: why encrypt the nonce with a different key?

Question

I am a newbie at cryptography. I understand the CBC encryption, somewhat. You don't want to use the same "IV" for every message because then the ciphers are not very random. My question is regarding the nonce-based CBC. My main question is why does the nonce needs to be encrypted with a different key than the rest of the message?

And a side question is does the nonce needs to be different? Or can it be predictable and reusable?

Below is a picture of what I am referring to. This image shows excellently the point I am referring to but does not explain it. Why can't k1 = k?

(From A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup, problem 5.14)

Answer 1

I believe that it has to do with the model of nonce selection, in particular, that the attacker is allowed to choose the nonce (as long as it is unique).

If we assume that such an attacker is plausible, then if the nonce is encrypted with the same key as everythine else, then attacker can perform a chosen nonce/plaintext attack which serves as a distinguisher, as well as allows an attacker to decrypt low-entropy plaintext.

Here's how it works: suppose the attacker has a ciphertext where he has a guess $t$ to the value $m[i]$, and (of course, the ciphertext values $c[i-1]$ and $c[i]$). Then, the attacker constructs a message with the first block being $c[i] \oplus t \oplus c[i-1]$, and asks it to be encrypted with the nonce value $t \oplus c[i-1]$. He then examines the first block of the resulting ciphertext; if it happens to be the value $c[i]$, then (with high probability) his guess is correct.

If his guess of $t$ was correct, that is if $t = m[i]$, then we have $c[i] = E_k( t \oplus c[i-1])$ (as that's the formula the encryptor used to create $c[i]$)

So, here is what the encryption process would do: the mode would first encrypt the nonce; the nonce is $t \oplus c[i-1]$, and so the result of the encryption would be $c[i]$. That is then exclusive or'ed with the first block of the plaintext message, which is $c[i] \oplus t \oplus c[i-1]$; the result of that xor is $t \oplus c[i-1]$. That is then encrypted; again, the result of that encryption is $c[i]$; and that is the first block of the encryption.

If $t \ne m[i]$, it is quite unlikely that the result of the two encryptions will happen to be the value $c[i]$.

Having the process that initially encrypts the nonce use a distinct key foils this attack.

Now, if we assume that the attacker cannot arbitrarily choose the nonce (e.g. the nonces are sequential), then this attack does not apply; reusing the same key is safe.

Answer 2

The scheme you describe is also presented here, where it is called CBC1. The attack presented there also assumes the attacker can supply the nonce but is not allowed to reuse a nonce. The goal of the attacker is to determine whether the encryption oracle is encrypting the actual plaintext that is supplied or returning random bits as the ciphertext. It works like this:

Attacker begins by supplying a nonce of 0 (i.e., a bitstring the length of the block size of all zeros), and a plaintext that is two blocks long of 0||0. The returned ciphertext will be two blocks long, $c_1^1$||$c_1^2$. The attacker then supplies another query, this time setting the nonce to be $c_1^1$ and the plaintext to be $c_1^1\oplus c_1^2$. This results in a single block of ciphertext, called $c_2^1$.

If $c_2^1\equiv c_1^2$, then the attacker knows that the real plaintexts are being encrypted. If they are not equal, then random plaintexts are being encrypted by the oracle. In otherwords, there is a distinguisher.

The attack works by noticing that if the real encryption is used (instead of just returning random bits), $c_1^1$ is actually the double encryption of 0, or $e^2(\textbf{0})$ and $c_1^2$ is the triple encryption of $0$, or $e^3(\textbf{0})$. So the second query uses a nonce of $e^2(\textbf{0})$, which is encrypted to get $e^3(\textbf{0})$. That value is xor'd with the block of plaintext, which is $e^2(\textbf{0})\oplus e^3(\textbf{0})$. But $e^3(\textbf{0})\oplus e^2(\textbf{0})\oplus e^3(\textbf{0})$ is just $e^2(\textbf{0})$, so $c_2^1=e(e^2(\textbf{0}))=e^3(\textbf{0})$.