CBC variant: why encrypt the nonce with a different key? 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)
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.