# Simple way to extend AES to 256-bit block size

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'$.

-
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). –  Matt Nordhoff May 21 at 22:31
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. –  jbms May 21 at 22:54
–  Seth May 22 at 7:48

## 1 Answer

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)$.

-
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? –  jbms May 22 at 3:06
@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. –  poncho May 22 at 19:19