Subject: RE: [Cfrg] RE: Who needs collision-resistance, anyway?

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Mon, 21 Mar 2005 12:13:23 -0800

The h (k || m) construction was rejected I believe because of a message
extension attack that had been discussed at the time. If I know h (k || m)
then I can calculate h (k || m || p || x) where p is the padding appended to
k || m  in the digest iterator construct.

This is one of the reasons why the HTTP Digest authentication mechanism uses
a construction of the form: h ( h ( x) || h (y) ), to eliminate the risk of
an extension attack. I wrote that construct before HMAC was written but I
still think that there is a real value to effectively changing the order of
the compressor function inputs so that the state chaining variables get fed
into the data input slot.

Now that does not say anything about whether the message extension attack
was a risk in the proposed use but that is I believe the reason it was
rejected.

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of [email-masked]
> Sent: Monday, March 21, 2005 1:55 AM
> To: [email-masked]
> Subject: Re: [Cfrg] RE: Who needs collision-resistance, anyway?
> 
> 
> John Wilkinson  wrote:
> >Most of the discussion on this list seems to be centered around
> >creating a TCR hash function by keying SHA1 through the IV using the 
> >construction h(k || m), where k is the key (which is published, once 
> >chosen), m is the message, and || denotes concatenation. 
> Keying through 
> >the IV is explicitly rejected in the paper [1] cited by Dr. Halevi. 
> 
> You're right.  I don't understand why that construction was 
> rejected. I'm at a loss to explain their reasoning.
> 
> Here is the argument given in that paper:
> 
>     Suppose, for example, that one keys MD5 through its 
> 128-bit initial
>     chaining value, IV. Denote the resulting hash function family by
>     MD5*. Then breaking MD5* (in the sense of violating TCR) 
> amounts to
>     finding collisions in an algorithm which is identical to 
> MD5 except
>     that it begins with a random, known IV (as opposed to the 
> published
>     one). It seems unlikely that this task would be harder 
> than finding
>     collisions in MD5 itself. It could even be easier!
> 
> But this seems to confuse two distinct cryptanalytic tasks: 
> (1) given the IV, find M, M' so that MD5*(IV,M) = 
> MD5*(IV,M'); (2) choose M before you know the IV; then, given 
> the IV, find M' so that MD5*(IV,M) = MD5*(IV,M'). I don't see 
> any reason to expect these two tasks to be equivalent, and I 
> would certainly imagine that for some hash functions, task 
> (2) might be much harder than task (1).  Indeed, task (2) is 
> basically the TCR notion, while task (1) is just standard 
> collision-resistance.
> 
> So I don't know why they rejected MD5*.  I don't know why 
> that paper considered it unlikely that breaking MD5*'s TCR 
> property would be any harder than breaking MD5's 
> collision-resistance.  I don't know why they rejected the 
> envelope method, either.  The paragraph discussing the 
> envelope method seems to have made the same mistake, as far 
> as I can tell. I'm puzzled; I confess I don't see where those 
> comments are coming from.
> 
> I definitely wouldn't recommend using MD5 for this purpose.  
> But I'm not aware of any reason to reject SHA1(k || m) or SHA1*(k, m).
> 
> It is true that there are no security guarantees that either 
> of these constructions will be secure, but there is also no 
> guarantee that these constructions will be insecure.  There 
> is some reason to hope that these constructions might be 
> secure even if collisions are found in SHA1.
> 
> >The constructions with security reduction arguments presented in [1] 
> >all have very long keys (much greater than the length of the 
> hash), and 
> >the authors make a comment that the common practice of stretching a 
> >short key into a long one using a PRF is "of no apparent use in this 
> >case". (If anyone can explain why, I'd love to know.)
> 
> I don't have a concrete example of what goes wrong, but this 
> sounds plausible to me.  The definition of security for a PRF 
> makes no guarantees about the pseudorandomness of its output 
> if the key to the PRF is made public, so using a PRF with a 
> public key is a strange thing to do.
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/cfrg
> 

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: [email-masked] (David Wagner)
Date: Mon, 21 Mar 2005 20:41:14 +0000 (UTC)

>k || m  in the digest iterator construct.

I agree that h(k || m) has a length-extension property, just like h(m)
does, but I'm pretty sure that's not what the paper [1] was talking about.
If that is what the authors were thinking of, it's not apparent in the
text of the paper.

Personally, I don't think the length-extension property is sufficient
reason to reject a hash.  If it were, we'd have to reject MD5, SHA1,
SHA-256, SHA-512, and every other MD-style hash out there.  But we don't.
The reason we don't is that it is not *that* hard to work around the
length-extension property.  You can design your protocol so that it can
never get fooled by length-extension attacks (e.g., all inputs to the
hash are of constant and known length).  Or, you can use the hash in a
way that prevents length-extension attacks (e.g., h(len(m) || m)).
It's a pain in the neck, to be sure, but not an intolerable one.

Perhaps what you are thinking of is that h(k || m) was rejected as a
*message authentication code*.   Instead, we chose HMAC, because it
uses the hash function in a way that prevents length-extension attacks.
However, message authentication codes are different from TCR functions,
and when the IETF deliberated about how to turn a hash function into
a MAC, we never considered the TCR application.  Moreover, I'm pretty
sure the paper [1] was not referring to length-extension attacks.

So I don't see this as sufficient reason to reject SHA1* (for example).
And, I don't think it is the reason that the paper was alluding to.

P.S. Of course, if I were designing a new hash function, I would want
to see any new design avoid length-extension properties.  I do consider
the length-extension property a design defect, albeit a minor one.
Eliminating this defect simplifies the construction of secure protocols.