Re: [Cfrg] Re: AES-based hash function

[John Viega <viega at securesoftware.com>]

On Sep 7, 2004, at 12:09 PM, Daniel Brown wrote:
> <x-tad-smaller>Sorry: I completely missed your original point that MDC-2 and MDC-4 were length-doubling cipher-to-hash constructions.  I just now looked at the HAC (S. 9.4) to learn about them.</x-tad-smaller> 
>
> <x-tad-smaller>What is the security risk of MDC-2 that the extra ciphering in MDC-4 is meant to avoid?</x-tad-smaller> 

It was just simple conservatism, I believe.  There's really nobody using MDC-4 AFAIK; it certainly seems like overkill.
<x-tad-smaller> </x-tad-smaller>
> <x-tad-smaller> > By the way, the Rijndael-based hash that was proposed to NIST used</x-tad-smaller>
> <x-tad-smaller> > Davies-Meyer, which, of the Preneel family of constructs, is the most</x-tad-smaller>
> <x-tad-smaller> > worrisome if there are related key attacks, since the keying in</x-tad-smaller>
> <x-tad-smaller> > Davies-Meyer is taken from the string being hashed directly.  In other</x-tad-smaller>
>
>
> <x-tad-smaller>As far as I can tell, SHA-1 and the SHA-2 functions use the Davies-Meyer construction, not the MMO. Do your concerns with DM apply to them, or am I missing something (again)?</x-tad-smaller> 

No, you're right.  They're using Davies-Meyer, essentially so that generating subkeys is essentially free.  It definitely seems to me to be more the speedy choice rather than the conservative choice.

> <x-tad-smaller>Are you saying that security proofs are known for MDC-2 and MDC-4 in the ideal cipher model?  (The HAC mentions that DM, MMO, and MP are secure in the ideal cipher model, but I didn't find such a statement for length-doubling hashes like MDC-2 and MDC-4.)  </x-tad-smaller> 

No.  So far as I know, no one has really even attempted a proof for these.  There hasn't been much theoretical work in this space... even recent treatments only cover the basic modes.  Certainly, the bounds for MMO is a lower bound for MDC-2 security.

> <x-tad-smaller>Can such proofs be extended to length-quadrupling hash constructions, and so on to arbitrary length hash functions?  </x-tad-smaller> 
> <x-tad-smaller>In the random oracle model (i.e. ideal hash model), isn't it possible to double any hash length? If H1 is random, then isn't H2 = (H1(0,M),H1(1,M)) also random? There must be some good reasons such a construction is not used. 
> </x-tad-smaller>

Good question. This may come down to one of those things where it's better to be conservative, since we know that we're never going to replace our idealized construct with something that does the same job.

The only unusual thing I can think of, off the cuff: Since we're talking about iterated constructs, with such a simple doubling strategy, if you can find collisions with the right prefix, you can easily extend that to arbitrary lengths.  That is, let's say that H1 were DES in MMO mode.  If you can find a small M such that H1(0, M) == H1(1, M), then you would also have a collision on H2 by simply choosing M' such that it starts with the fully padded version of M.   This isn't a big deal, though, because a brute force on H1 is essentially expected to be the same complexity as a birthday attack on H2.

MDC-2 is somewhat similar to what you suggest, except that the 0 bit vs. 1 bit is realized by starting out the two MMO instances with different IVs, and then there's the swapping at the end.  So, there's probably some other issue that I don't see right away, or they were just trying to be overly conservative in their design.

John
_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg