Re: How good are Davis-Meyer type hash functions made from block ciphers like AES?

On Feb 18, 9:02 pm, g...@xxxxxxxxxxxxx (Greg Rose) wrote:
In article <99875640-65ae-4567-aad8-40c4081ca...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Adam Ierymenko  <adam.ieryme...@xxxxxxxxx> wrote:

The the following pseudo-code for example, which is a Davis-Meyer
constructed hash function from AES-128 with Merkle-Damgård length

 byte digest[16] = { 0,0,... }
 byte block[16] = { 0,0,... }
 byte previous_digest[16]
 integer block_counter = 0

 ; digest message
 for each byte b of message
   block[block_counter] = block[block_counter] xor b
   block_counter = block_counter + 1
   if block_counter == 16 then
     block_counter = 0
     save digest[] in previous_digest[]
     encrypt digest[] with aes-128 using block[] as 128-bit aes-128
     xor digest[1..16] with previous_digest[1..16]

 ; 8 bytes of Merkle-Damgård length padding
 for each byte b of [length of message as a big-endian 64-bit
   ; same as above... we just digest 8 bytes of length too...

 ; do final block if there is remaining undigested data
 if block_counter != 0
   save digest[] in previous_digest[]
   encrypt digest[] with aes-128 using block[] as 128-bit aes-128 key
   xor digest[1..16] with previous_digest[1..16]

 ; digest[] now contains message digest

How good are these kinds of compression functions in terms of
collision resistance, unpredictability, etc.? I would tend to think
that any significant flaw in the above would also be a flaw in AES. Is
this correct?

You need to check your padding pseudo-code a
bit... you want to make sure that the length
counter is right at the end of a block, no matter
what. If is isn't, it might be possible to find
other messages that have the same hash. You also
need to add some sort of marker at the end of the
provided input; typically a single 1 bit followed
by enough zeros is what is used.

The security of this construct depends upon the
properties of the block cipher against related key
attacks, and there have recently been related key
attacks against AES, so I wouldn't recommend it.
But if the block cipher is resistant against such
attacks (as well as the usual ones) the M-D
construct is mostly secure... it would be as good
as SHA-256 is hoped to be. (Except, of course,
that a 128-bit digest is considered too short.)


Greg Rose
232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C

Thanks! After reading a bit more on hash construction, I think a
better construct might be to hash the entire message, hash the
remaining bytes, and then hash a single block consisting of 8 bytes of
some arbitrary constant (e.g. 0x8000000000000000) followed by 8 bytes
of length in *little endian* byte order so that the most variable bits
tend to be at the end of the last block. So basically you'd swap the
last two sections and ensure that the length was at the end of the
last block.

I know that 16 bytes is shorter than recommended, but the purpose of
this hash is primarily unique identification. I'm more concerned with
the improbability of collisions than with the possibility that with a
ton of computing power you might be able to generate one. In the
protocol I'm designing, if you *could* generate collisions on this
hash the worst you could do would be a fairly minor DOS attack... and
it would be a heck of a computationally expensive DOS attack.

BTW, my spec also uses CMAC-AES (also known as OMAC1-AES) for MAC.
This is a documented algorithm, see here:

I assume that your comments apply there too... that the security of
this depends on the security of full-round AES against related key

So basically by doing this I'm betting on AES being fairly secure. I
suppose if major flaws were found in AES a whole lot of stuff would be
at risk.

Relevant Pages

  • [REVS] Denial of Service via Algorithmic Complexity Attacks
    ... both binary trees and hash tables can degenerate to linked lists with ... demonstrate attacks against the hash table implementations in two versions ... Bro server to its knees; after six minutes of carefully chosen packets, ...
  • Re: Authentication (was Re: Autentication)
    ... I used the same password routines used by OpenVMS. ... the original data fill was done by copying the hash and SALT directly from SYSUAF. ... such as dictionary attacks, and off-line attacks against exposed password hashes. ...
  • Re: Looking for a fast implementation of a hash algorithim
    ... collisions can be generated in seconds to hours ... Two files can be generated that have the same md5 hash. ... And the known attacks on MD4 won't work on MD5. ...
  • Re: risk of crypt(3) + [NT]LM hashes?
    ... >Has any analysis been performed on the risk of using the same password ... how about the risks of encrypting it under Windows hash alone? ... that's one of the attacks described at the URL above. ...
  • Re: Rainbow Tables
    ... I guess what I should have asked was what is the best program or method of creating hash tables since I doubt I'll remember the name since I say it in passing.... ... Hackers are concentrating their efforts on attacking applications on your website. ... Up to 75% of cyber attacks are launched on shopping carts, forms, login pages, dynamic content etc. Firewalls, SSL and locked-down servers are futile against web application hacking. ... Check your website for vulnerabilities to SQL injection, Cross site scripting and other web attacks before hackers do! ...