Re: Summary of key derivation thread

[Hugo Krawczyk <hugo@ee.technion.ac.il>]

Russ, I have several remarks on your message:

On Tue, 10 Dec 2002, Russ Housley wrote:

> David Wagner wrote:
> >This objection has already been addressed on the list.  Those 1024
> >bits of Diffie-Hellman only have 160 bits of strength (160 bits of
> >"computational entropy"), hence you're not reducing security by hashing
> >it down to 160 bits.
> >
> >Indeed, in some sense you are improving security by hashing the 1024-bit
> >Diffie-Hellman result down to a 160-bit security, just as Hugo's earlier
> >note pointed out.  Can I encourage you to re-read Hugo's earlier emails
> >on this topic?  I hope you will find them persuasive.  (I certainly did.)
> 
> I do not think we can select mandatory-to-implement algorithms without 
> agreement on the level of security that we are attempting to provide.  In 
> my mind, this leads to two interrelated questions.
> 
> First a summary of the consensus.  A 1024-bit Diffie-Hellman result has 160 
> bits of entropy.  HMAC-SHA-1 has a 160-bit output value, so there is a good 
> impedance match here.  This provides 80 bits of strength.  By now, I think 
> that people who have been reading this thread carefully have gotten these 
> points.

Actually the points as you summarize them are not accurate. 

Saying that DH has 160 bits of entropy can be misunderstood to mean that
the best known attack on DH requires 2^160 operations. 
This is of course not true with a 1024-bit modulus.
Today you can fully break a 1024 DH exchange (i.e recover the DH key
g^xy from g^x and g^y) in something between 2^70 to 2^80 operations. 
Thus, by using a 1024-bit modulus you are essentially limited to no
more than 70-80 bits of security. 
And no hashing of g^xy can improve that...
What the hashing is meant to do is to avoid further shortcut attacks that
would leak information on the key at much less than the 2^70 cost of
fully breaking the DH exchange (e.g., if you use a generator of the
group Zp* as your DH basis and do not hash the key then you can find the
lsb of g^xy in less than a millisecond.

> 
> Question 1:  Currently, the mandatory-to-implement requirement is bigger 
> than 1024-bit Diffie-Hellman.  So, with the larger value, is a different 
> PRF needed to obtain a similar impedance match?

The strength of the prf should not be less than the strength of the DH
group, but it doesn't help much to have a stronger prf either (that's why
I referred to all the talking about the insufficiency of a 160-bit prf as
noise, in particular you should use > 5000 bits of DH modulus to match 160
bit security). 
And, btw, there is no (known) feasible attack of the order of 2^80 against
HMAC-SHA1. You can mount an attack in that order if you are allowed to
make 2^80 queries to the prf, which is unrealistic in any application, and
certainly in the key derivation application for which the prf is used here.

> 
> Question 2:  Based on the NIST key management recommendations, a 80 bits of 
> security is adequate for protecting sensitive government information until 
> 2015, and 112 bits of security is adequate until 2030.  Which of these 
> targets is the mandatory-to-implement aiming at?  Or, are we after 
> something in the middle, say 96 bits?

I do not know what the "market answer" to this is.
But even if you take the "NIST minimum" of 80, you need to go for 
a modulus longer than 1024, probably 1200 bits (Hilarie may have precise
estimates). For 96 bits you already need to exceed the 2048-bit keys.

Hugo


> 
> Russ 
> 
>