AES-CBC based hashing This question is purely hypothetical.

The idea is to generate variable sized hashes (multiple AES block sizes) like so:


encrypt plain text
encrypt plain text + cipher text from 1.
XOR cipher text blocks over hash blocks.


Step 1 and 2 can be programmatically done as one step.

Step 2 causes at least the second half of the cipher text to be different for each different plain text even if only the last block of plain text is different (changes in the plain text have no effect on cipher text blocks from before the change).

The key and IV are the same for each message.

Apart from being slow, is this a valid way to generate secure hashes?
If I understood the description correctly, with a 4-block (512-bit) hash output $H_0\ldots H_3$, message $M_0\ldots M_3$ of the same size, a fixed public value of the AES key, and all-zero IVs and initializations (because comments allow that), the steps are


$C_0\gets E(M_0)$
$C_1\gets E(M_1\oplus C_0)$
$C_2\gets E(M_2\oplus C_1)$
$C_3\gets E(M_3\oplus C_2)$
$C'_0\gets E(C_0\oplus C_3)$
$C'_1\gets E(C_1\oplus C'_0)$
$C'_2\gets E(C_2\oplus C'_1)$
$C'_3\gets E(C_3\oplus C'_2)$
$H_0\gets C_0\oplus C'_0$
$H_1\gets C_1\oplus C'_1$
$H_2\gets C_2\oplus C'_2$
$H_3\gets C_3\oplus C'_3$


I have noted AES block encryption and decryption with the key $X\mapsto Y=E(X)$, and $Y\mapsto X=D(Y)$.

I'll show that knowing $H_0$, $M_0$, $M_1$, $M_3$, we can find $M_2$, which counts as a break of a model of the hash as a Random Oracle, and is tantamount to a first-preimage attack.


$C_0\gets E(M_0)$, per 1.
$C_1\gets E(M_1\oplus C_0)$, per 2.
$C'_0\gets C_0\oplus H_0$, by inverting 9.
$C_3\gets D(C'_0)\oplus C_0$, by inverting 5.
$C_2\gets D(C_3)\oplus M_3$, by inverting 4.
$M_2\gets D(C_2)\oplus C_1$, by inverting 3.


$H_1\ldots H_3$ can be recomputed trivially since we have $M_0\ldots M_3$.



That hash truncated to its first 256-bits is insecure against collision. That's contrary to a good 512-bit hash like SHA-512, which we can truncate to 256-bit and still get collision-resistance with work for the best known attack about $2^{128}$ compression functions. Sketch of that partial collision: we start from an arbitrary message, change $M_2$, then $M_3$ so that $C_3$ is restored to what it was. These message changes leave $C_0$, $C_1$, $C'_0$, $C'_1$ unchanged, therefore $H_0$ and $H_1$ unchanged.

That attack can be extended to work with the padding and hash size described in comment, to obtain a collision in the first 3712 bits of a 4096-bit hash. Sketch: message and hash are 32-block, we alter $M_{29}$, and $M_{30}$ to return $C_{30}$ to what it was. That leave $H_0\ldots H_{28}$ unchanged.

What's the point of making a wide hash, if most of it is insecure against collision?

Another issue with the construction is that it requires memory size about as the message size in order to keep the result of the first pass. Something requiring about as much memory as the hash size is desirable in many applications.



Making the message a few times the hash size gives more freedom, and I'll walk back from speculating what it might allow.