Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 1 down vote favorite

How secure would a hash function be which appends an extra block of 16 zeroed out bytes to the end of the message and then AES-encrypts it with a well-known password (say the first 128 bits of pi) using cipher-block-chaining and then XORs all the encrypted blocks together?

share|improve this question
1  
You can build a MAC with a similar technique (CBC-MAC) but building a good hash function is harder. – CodesInChaos Aug 27 '12 at 21:54
For SHA-3 candidates using AES or similar parts see e.g. this paper. – maaartinus Aug 28 '12 at 23:59

2 Answers

up vote 9 down vote accepted

Not at all secure; generating preimages would be trivial. Here's a demonstration with a three-block message:

Here is your suggested method (limited to three block messages):

$E_0 = Encrypt( IV \oplus P_0 )$

$E_1 = Encrypt( E_0 \oplus P_1 )$

$E_2 = Encrypt( E_1 \oplus P_2 )$

$E_3 = Encrypt( E_2 \oplus 0 )$

$Hash = E_0 \oplus E_1 \oplus E_2 \oplus E_3$

(with the key for Encrypt and the IV fixed).

Here's how you could find a message $(P_0, P_1, P_2)$ that hashes to a preselected value $Hash$:

  • Select an arbitrary value for $P_2$ (which may include the trailing padding for the last block)

  • Select an arbitrary value for $E_2$.

  • Compute $E_3 = Encrypt( E_2 \oplus 0 )$, $E_1 = Decrypt(E_2) \oplus P_2$ and $E_0 = Hash \oplus E_1 \oplus E_2 \oplus E_3$

  • Compute $P_0 = IV \oplus Decrypt( E_0 )$ and $P_1 = Decrypt(E_1) \oplus E_0$

You're done: $(P_0, P_1, P_2)$ hashes to preselected value; it's easy to see that hashing this value will cause the internal $E_0, E_1, E_2, E_3$ values that we have selected, and that exclusive-oring them will produce the preselected hash.

share|improve this answer
Yes of course. I forgot it's easy to decrypt arbitrary strings of bytes in AES. But of course if the plain-text and cipher lengths are always the same than this has to be true – dspyz Aug 27 '12 at 21:34
@dspyz: actually, it's not true that plaintext and ciphertext lengths are the same implies that the function must be easily invertible. If we consider SHA-256 restricted to 256 bit input strings, well, the input and the output are the same size; however, inverting it is somewhat difficult. – poncho Aug 27 '12 at 21:39
Would adding a feedforward step to the AES permutation function like so $\mathrm{Encrypt}(X) = E(X) \oplus X$ fix this vulnerability? – Thomas Aug 28 '12 at 6:26
2  
@Thomas, no, that's not likely to be enough. Lots of people have studied how to build a hash function out of AES, and the consensus view is: it's not a very promising direction. You're probably not going to get something of adequate strength out of AES (at least, not something simple and as fast as AES). We could spend all day going back with various proposed schemes and showing how they're broken, but let's jump past all that to the bottom line: this is not a promising direction to build a hash function. – D.W. Aug 28 '12 at 6:53
up vote 0 down vote

In addition, you would want to use at least 256 bits of "state" for an iterated 128 bit hash function due to the existence of generic attacks to produce state collusions. You might want to google for "wide pipe construction" or "random sponge function".

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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