Re: How good are Davis-Meyer type hash functions made from block ciphers like AES?
- From: Adam Ierymenko <adam.ierymenko@xxxxxxxxx>
- Date: Thu, 18 Feb 2010 18:53:19 -0800 (PST)
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
padding:
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
key
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
integer]
; 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.
--
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:
http://en.wikipedia.org/wiki/CMAC
I assume that your comments apply there too... that the security of
this depends on the security of full-round AES against related key
attacks.
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.
.
- Follow-Ups:
- Re: How good are Davis-Meyer type hash functions made from block ciphers like AES?
- From: Adam Ierymenko
- Re: How good are Davis-Meyer type hash functions made from block ciphers like AES?
- References:
- How good are Davis-Meyer type hash functions made from block ciphers like AES?
- From: Adam Ierymenko
- How good are Davis-Meyer type hash functions made from block ciphers like AES?
- Prev by Date: How good are Davis-Meyer type hash functions made from block ciphers like AES?
- Next by Date: Re: How good are Davis-Meyer type hash functions made from block ciphers like AES?
- Previous by thread: How good are Davis-Meyer type hash functions made from block ciphers like AES?
- Next by thread: Re: How good are Davis-Meyer type hash functions made from block ciphers like AES?
- Index(es):
Relevant Pages
|
