Prev: Call for Papers: The 2010 International Conference of Mechanical Engineering (ICME 2010)
Next: Call for Papers: The 2010 International Conference on Wireless Networks (ICWN'10), USA, July 2010
From: Adam Ierymenko on 18 Feb 2010 20:33
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?
From: Greg Rose on 18 Feb 2010 21:02
In article <99875640-65ae-4567-aad8-40c4081cab9e(a)k41g2000yqm.googlegroups.com>,
Adam Ierymenko <adam.ierymenko(a)gmail.com> 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
From: Adam Ierymenko on 18 Feb 2010 21:53
On Feb 18, 9:02 pm, g...(a)nope.ucsd.edu (Greg Rose) wrote:
> In article <99875640-65ae-4567-aad8-40c4081ca...(a)k41g2000yqm.googlegroups..com>,
> Adam Ierymenko  <adam.ieryme...(a)gmail.com> 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.
From: Adam Ierymenko on 18 Feb 2010 21:58
So to continue above, my pseudocode is now:

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[] with previous_digest[]
end if
next

; 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[] with previous_digest[]
end if

; Merkle-Damgård length padding
fill first 8 bytes of block[] with { 0x80,0x00,0x00,0x00,...,0x00 }
fill last 8 bytes of block[] w/64-bit bytes hashed in little-endian
order
save digest[] in previous_digest[]
encrypt digest[] with aes-128 using block[] as 128-bit aes-128 key
xor digest[] with previous_digest[]

; digest[] now contains message digest
From: Greg Rose on 19 Feb 2010 01:14
In article <23411cad-9c1b-48d4-980a-e48c32cb3b93(a)d27g2000yqf.googlegroups.com>,
Adam Ierymenko <adam.ierymenko(a)gmail.com> wrote:
>On Feb 18, 9:02�pm, g...(a)nope.ucsd.edu (Greg Rose) wrote:
>> 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.)
>
>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.

It shouldn't matter whether the varying bits are
at the end of the block or the middle.

>...
>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.

Except that no-one thought that related-key
attacks mattered for AES when it was adopted. It
doesn't matter for most uses of encryption. It was
only when people started wanting to use it for
hashing that these attacks became worth worrying
about. I don't know anyone who doubts the security
of AES for encryption, but plenty of people who
don't want to use it out of the box for hashing.

Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
 |  Next  |  Last
Pages: 1 2
Prev: Call for Papers: The 2010 International Conference of Mechanical Engineering (ICME 2010)
Next: Call for Papers: The 2010 International Conference on Wireless Networks (ICWN'10), USA, July 2010