What is the best way to use standard AES with a 128-bit block size to act as a 256-bit block cipher? I am aware of CMC and EME which seem to serve this purpose, but they seem to be more complicated than necessary for the 256-bit block case. (I would like to avoid relying on the uniqueness of a nonce.)

Is the following variant of CBC secure?

Let $(P_1, P_2)$ be the two 128-bit blocks of the 256-bit plaintext $P$, and $I$ be the 128-bit (public) IV (which might not be unique). The secret AES key is $k$.

To encrypt, set $C_0 = E_k(I)$, $C_1 = E_k(P_1 \oplus C_0)$, $C_2 = E_k(P_2 \oplus C_1)$, $C_3 = E_k(P_1 \oplus C_2)$. The result is $(C_2, C_3)$.

To decrypt, set $C_0 = E_k(I)$, $P_1 = D_k(C_3) \oplus C_2$, $C_1 = E_k(P_1 \oplus C_0)$, $P_2 = D_k(C_2) \oplus C_1$.

Both encryption and decryption require just 4 AES block encryptions/decryptions (just 3 if $I$ can be used as $C_0$ directly).

The key question is whether this is secure even if $I$ may not be unique. If both $P$ and $P'$ are encrypted using the same value of $I$, an attacker should not be able to determine anything about $P$ and $P'$ other than whether they are equal (in their entirety). For regular CBC mode, this is not the case, since if $P_1 = P_1'$, then $C_1 = C_1'$.

  • 2
    $\begingroup$ FYI, Rijndael was originally defined with multiple block sizes, including 256 bits; this was left out of the AES specification, as NIST was uninterested. I'm not sure these variants have received enough cryptanalysis, and I'm not implicitly endorsing this endeavor (or dis-endorsing it either). $\endgroup$ – Matt Nordhoff May 21 '14 at 22:31
  • 2
    $\begingroup$ I'm aware that Rijndael is defined for other block sizes, but it would be convenient to be able to just rely on AES as a black box. $\endgroup$ – jbms May 21 '14 at 22:54
  • $\begingroup$ possible duplicate of Is it possible to construct a secure block cipher of size $2n$ given a secure block cipher of size $n$? $\endgroup$ – Seth May 22 '14 at 7:48

It turns out that this "mode" is distinguishable with two chosen messages; one in decrypt mode, and one in encrypt mode.

The first query is in decrypt mode, it is of the ciphertext $(C, 0)$ (where $C$ can be any nonzero value), and with an arbitrary IV.

Because of how decrypt works, $P_1$ of the resulting plaintext is $D_k(0) \oplus C$; this gives us the 128 bit value $Z = P_1 \oplus C$ with $E_k(Z) = 0$.

Our second query is in encrypt mode, it is of the plaintext $(Z, Z)$ with $IV=Z$. If you go through how encryption works, we see that $C_0 = 0$, $C_1=0$, $C_2=0$, $C_3=0$, and so the resulting ciphertext is $(0,0)$.

  • $\begingroup$ In the weaker attack model where the adversary can see only ciphertexts (and I values), and cannot request encryptions or decryptions, is any information leaked? For full security, is CMC a good choice? $\endgroup$ – jbms May 22 '14 at 3:06
  • $\begingroup$ @jbms: I don't understand the reason you're asking whether a mode which is known to be insecure in one model is secure in another -- there are modes that are known to be secure even in chosen ciphertext models. As for CMC, I believe that would be a good choice. $\endgroup$ – poncho May 22 '14 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.