Subject: RE: [Cfrg] New Proofs for NMAC and HMAC: Security Without Collision-Resistance

From: Praveen Gauravaram <[email-masked]>
Date: Wed, 8 Feb 2006 21:32:34 +1000 (EST)

Dear David and cfrg members:
It is my pleasure to introduce myself as Praveen Gauravaram.
In the following draft version 
(http://eprint.iacr.org/2005/390) we have modified Merkle Damgard construction to serve many purposes. We have proved that if f is a PRF then the modified MD construction called 3C is also a PRF. Then it works as a MAC as well. It also serves as a new mode of operation for the MD hash function providing more resistance against multi-block collision attacks demonstrated on MD5 and SHA-1 hash functions by Wang. In fact we are currently working on this draft and a completed version will be released soon. As a hash function the construction avoids extension attacks as well. It is a simple modification to MD hash.

Unfortunately I will be away in the next few days and may not be contribute in replying to this group. I would kindly appreciate for any useful comments. The main point from the point of view of PRF here is using just one key we were able to show that the nested construction works as a PRF. 

I shall catch up with this soon.
Yours sincerely,
Praveen

---- Original message ----
>Date: Tue, 7 Feb 2006 17:58:57 -0500
>From: "Blumenthal, Uri" <[email-masked]>  
>Subject: RE: [Cfrg] New Proofs for NMAC and HMAC: Security Without Collision-Resistance  
>To: "David McGrew" <[email-masked]>
>Cc: [email-masked]
>
>Hi David, 
>
>>> One observation: this paper basically says that we were looking for
>>> wrong properties! Collision resistance (strong or weak) is  
>>> unnecessary: if the underlying compression function is a PRF then
>>> keyed MAC is secure; and if it's not a PRF (Bellare proved that
>>> a slightly weaker assumption is still OK) - then weak collision
>>> resistance won't help.
>>>
>>> So when we specify requirements for crypto hash - what we really
>>> want/need is Pseudo-Randomness. Then we can safely use it in key
>>> derivation, and then keyed MAC is also secure.
>>
>> AFAICT, Mihir's work doesn't address the issue of whether or not
>> NMAC or HMAC is a secure way of deriving symmetric keys from a
>> Diffie-Hellman secret.
>
>True. But *if* the construct is a PRF - and there's a good chance of it
>if the underlying primitive is a PRF - then key derivation using that
>construct to derive keys seems secure enough (yes I realize that DH
>secret may have properties :-).
>
>> The abstract describes the work as showing that the functions
>> are good PRFs (or just good MACs) based on some different
>> assumptions
>
>Hmm... What I read from the paper is something different: in order to
>have a good MAC one _has_ to start with a PRF as a compression function.
>I don't see anything but assumption that SHA (or MDx) in fact _are_ PRFs
>- just the statement that _if_ they are - not only HMAC is secure
>(regardless of presence or absence of collision resistance), but also
>key derivation applications. Consequently - if those hash function are
>in fact _not_ PRFs, then not only key derivation shouldn't be done with
>them - but also MACing may be insecure even using HMAC construct.
>
>> ......... but a DH key derivation function can't be shown
>> to be secure merely because it is a PRF.
>
>Understand, though not quite. We can discuss this.
>
>> Of course, this is not to suggest that HMAC is a bad KDF. 
>> I suspect that it is a good one, but I just don't think
>> that the work cited proves anything in that direction.
>
>:-)
>
>_______________________________________________
>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: David McGrew <[email-masked]>
Date: Tue, 14 Feb 2006 13:45:53 -0800

Hi Praveen,

On Feb 8, 2006, at 3:32 AM, Praveen Gauravaram wrote:

> (http://eprint.iacr.org/2005/390) we have modified Merkle Damgard  
> construction to serve many purposes. We have proved that if f is a  
> PRF then the modified MD construction called 3C is also a PRF. Then  
> it works as a MAC as well. It also serves as a new mode of  
> operation for the MD hash function providing more resistance  
> against multi-block collision attacks demonstrated on MD5 and SHA-1  
> hash functions by Wang. In fact we are currently working on this  
> draft and a completed version will be released soon. As a hash  
> function the construction avoids extension attacks as well. It is a  
> simple modification to MD hash.

yes, it looks interesting.  The most interesting aspect is the  
potential for improved collision resistance, since that's the  
property that has proven more difficult to achieve than was  
originally thought.

David

>
> Unfortunately I will be away in the next few days and may not be  
> contribute in replying to this group. I would kindly appreciate for  
> any useful comments. The main point from the point of view of PRF  
> here is using just one key we were able to show that the nested  
> construction works as a PRF.
>