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