0
$\begingroup$

This question is purely hypothetical.

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

  1. encrypt plain text
  2. encrypt plain text + cipher text from 1.
  3. 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?

$\endgroup$
  • 3
    $\begingroup$ This is a two pass protocol to implement a message authentication code (not a hash, a hash is not using a secret key). There are already good message authentication codes based on CBC such as AES-CMAC or AES-EAX for a full fledged authenticated cipher based on it. Your protocol isn't well defined enough to make any in-depth comments about it, but in general using XOR is dangerous as an adversary only has to create one specific block to alter the result to their liking (or alter two and get to the same result using different ciphertext). $\endgroup$ – Maarten Bodewes Jun 11 at 12:48
  • $\begingroup$ Missing from description: during steps 1 and 2, how is the CBC IV setup, and is it made part of the ciphertext? $\endgroup$ – fgrieu Jun 15 at 9:19
  • 1
    $\begingroup$ @fgrieu - The IV can be anything at all as long as it's always the same and is not part of the cipher text. I would just use all zeros for both the IV and the key because it doesn't seem to matter for hashing. $\endgroup$ – Thorham Jun 15 at 9:31
  • $\begingroup$ In step 2, what is +? If it is concatenation, I don't see how encryption of "cipher text from 1" could start before step 1 is completed, because the CBC chaining variable is not known until then. What's "hash blocks" initialized to when step 3 starts? What is their number, relative to plaintext? Is the key secret? If yes, that's a MAC, not a hash. Also, please clarify if any ciphertext is output (or if on the contrary these are just intermediary variables). $\endgroup$ – fgrieu Jun 15 at 10:03
  • 1
    $\begingroup$ @fgrieu - The + is a concatenation. The programmatic merging of step 1 and 2 is done by simply continuing to encrypt when the plain text is done by seeing the cipher text as more plain text. That way the chain stays intact. The hash blocks can be initialized to zero, or any other constants as long as they are always the same. The number of hash blocks should be smaller than the number of plain text blocks (typically you just want a few, say 4096 bits worth). The key isn't secret. Only the hash blocks are output. $\endgroup$ – Thorham Jun 15 at 10:28
2
$\begingroup$

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

  1. $C_0\gets E(M_0)$
  2. $C_1\gets E(M_1\oplus C_0)$
  3. $C_2\gets E(M_2\oplus C_1)$
  4. $C_3\gets E(M_3\oplus C_2)$
  5. $C'_0\gets E(C_0\oplus C_3)$
  6. $C'_1\gets E(C_1\oplus C'_0)$
  7. $C'_2\gets E(C_2\oplus C'_1)$
  8. $C'_3\gets E(C_3\oplus C'_2)$
  9. $H_0\gets C_0\oplus C'_0$
  10. $H_1\gets C_1\oplus C'_1$
  11. $H_2\gets C_2\oplus C'_2$
  12. $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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Yes, that's how it works. I expect that no part of the message can be obtained from the hash if the message is at least twice the size of the hash, although I'm mostly interested in the collision resistance (reversibility doesn't matter for my use case because it's not security related). $\endgroup$ – Thorham Jun 15 at 13:00
  • $\begingroup$ @Thorham: you have not told how we handle a hash shorter than the message, e.g. only 2 blocks instead of 4 in my answer. To exhibit collisions, it helps to have a large message. $\endgroup$ – fgrieu Jun 15 at 13:03
  • 1
    $\begingroup$ The message could simply be padded like SHA2, although my use case is larger messages of several dozens of kilobytes that get compressed to sizes like 4096 bits and can be truncated to smaller sizes such as 256 bits or 512 bits (it's for seeding big state general purpose PRNGs with varying state sizes). $\endgroup$ – Thorham Jun 15 at 13:09
  • $\begingroup$ @Thorham: padding as in SHA-2, note taken, that's part of the last $M_i$. But how do we handle hashes much shorted than message? E.g. in my example if we want three $H_i$ instead of four? Do we just drop $H_0$, or what? $\endgroup$ – fgrieu Jun 15 at 13:48
  • 1
    $\begingroup$ For shorter hashes you just keep XORing more cipher text blocks over the hash blocks until you've XORed all cipher text blocks. In your example that would be h0 = c0 xor c3 xor c'2, h1 = c1 xor c'0 xor c'3, h2 = c2 xor c'1. Because the third hash block only gets two cipher text blocks XORed over it, you may want to pad the message to a length that's a multiple of the number of hash blocks. $\endgroup$ – Thorham Jun 15 at 14:16

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.