Subject: DH Key Agreement for Pkinit

From: Sam Hartman <[email-masked]>
Date: Wed, 29 Sep 2004 18:23:07 -0400

so until fairly recently we thought that truncating a DH key was a
reasonable solution to taking the result of DH and getting a bitstring
for random to key.  That is, we thought that DH results were evenly
distributed within the group and that the members of the group were
sufficiently well distributed in the prime field that we could pretend
they were uniformly distributed.  Larry points out that we were
confused when we believed we had evidence for this assumption.  That's
unfortunate; truncation is easy and if the DH results were uniformly
distributed it would clearly be the right thing to do.

So, we're left without any theoretical basis for what we do to speak
of.  PRFs are not useful to us because they only work assuming a
random key.  We really have no particular theoretical basis for any
solution to this problem.  Intuitively we should throw raround a bunch
of hashes and hmacs and stuff and pray that we do not fall prey to
advances in cryptanalysis.  People have been discussing such
solutions; they all sound relatively good and I don't think any of the
active working group participants have the necessary skill to
distinguish between them.

Fortunately we don't have to: the IETF has chosen to solve this
problem for us in a best current practice document.  I'd like to draw
your attention to section 4.5 of RFC 3766, which describes how to
convert asymmetric key exchange output into symmetric keys.

Not surprisingly the construction there (hashing with a counter) has
been discussed on this list.  We should use it.  That RFC is a BCP; it
represents how the IETF has chosen to solve this problem.  We need to
have a good reason for doing something different.

I don't claim that solution is good; I don't even claim it makes
sense.  I do claim it is what other IETF protocol should be/are doing.
I do claim it is what we do unless we can come up with a good
justification why what we are doing is better.

In particular I don't think we have such a justification for something
involving HMAC.

                           Changing Kcrypto

Some people have argued that kcrypto should be changed to add a
function to convert a bitstring into a key.  I disagree for two
reasons.

First, I think kcrypto is fast approaching publication.  I don't want
to delay it.  We don't need to delay it.  The best argument I've seen
that this needs to go into kcrypto is that we should leverage
kcrypto's enctype negotiation to figure out what unkeyed hash to use.
Except any time we're going to do DH, we're also going to need to
negotiate a group.  Why not negotiate the function used to pull a
uniform distribution out of a DH result at the same time using a
similar mechanism.  Why does this have anything to do with kcrypto?

The second reason I don't think this belongs in kcrypto is that I
don't think we have a good answer to the general problem of how to
convert a non-random bitstring into a key.  Hashes are what we use
because when we finish all the hand waiving they feel right and we
can't think of good ways to attack them for this use.  Secption 4.5 of
RFC 3766 attempts to justify its use of hashes.  Its justification is
somewhat unimpressive in that it starts with the false claim that a
cryptographic hash will not give out any information about its input.
We can show limits on how much information a good hash can leak about
its input,but those limits are much more permissive than zero.
Assuming that hashes are random oracles is a reasonable way to think
about some aspects of protocol security, especially when you have no
better ideas.  However there is significant concern in the
cryptography community about the truth of this assumption.  I think
this is still an open problem and I suspect future solutions may be
better than today's solutions.

--Sam

---

From: "Liqiang(Larry) Zhu" <[email-masked]>
Date: Wed, 29 Sep 2004 16:46:36 -0700

> Except any time we're going to do DH, we're also going to need to
negotiate a group.

This is the best argument against changing kcrypto and I buy it.

> Why does this have anything to do with kcrypto?

You already answered the question: kcrypto == negotiation

> Why not negotiate the function used to pull a 
> uniform distribution out of a DH 
> result at the same time using a similar mechanism.  

Can you provide more details, or even the text for the key derivation in
the form of a proposal? 

Overall, I am very much pleased with the rapid progress we made in the
PKINIT I-D recently.

-- Larry

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]] On Behalf Of Sam Hartman
Sent: Wednesday, September 29, 2004 3:23 PM
To: [email-masked]
Subject: DH Key Agreement for Pkinit

so until fairly recently we thought that truncating a DH key was a
reasonable solution to taking the result of DH and getting a bitstring
for random to key.  That is, we thought that DH results were evenly
distributed within the group and that the members of the group were
sufficiently well distributed in the prime field that we could pretend
they were uniformly distributed.  Larry points out that we were confused
when we believed we had evidence for this assumption.  That's
unfortunate; truncation is easy and if the DH results were uniformly
distributed it would clearly be the right thing to do.

So, we're left without any theoretical basis for what we do to speak of.
PRFs are not useful to us because they only work assuming a random key.
We really have no particular theoretical basis for any solution to this
problem.  Intuitively we should throw raround a bunch of hashes and
hmacs and stuff and pray that we do not fall prey to advances in
cryptanalysis.  People have been discussing such solutions; they all
sound relatively good and I don't think any of the active working group
participants have the necessary skill to distinguish between them.

Fortunately we don't have to: the IETF has chosen to solve this problem
for us in a best current practice document.  I'd like to draw your
attention to section 4.5 of RFC 3766, which describes how to convert
asymmetric key exchange output into symmetric keys.

I don't claim that solution is good; I don't even claim it makes sense.
I do claim it is what other IETF protocol should be/are doing.
I do claim it is what we do unless we can come up with a good
justification why what we are doing is better.

                           Changing Kcrypto

Some people have argued that kcrypto should be changed to add a function
to convert a bitstring into a key.  I disagree for two reasons.

First, I think kcrypto is fast approaching publication.  I don't want to
delay it.  We don't need to delay it.  The best argument I've seen that
this needs to go into kcrypto is that we should leverage kcrypto's
enctype negotiation to figure out what unkeyed hash to use.
Except any time we're going to do DH, we're also going to need to
negotiate a group.  Why not negotiate the function used to pull a
uniform distribution out of a DH result at the same time using a similar
mechanism.  Why does this have anything to do with kcrypto?

The second reason I don't think this belongs in kcrypto is that I don't
think we have a good answer to the general problem of how to convert a
non-random bitstring into a key.  Hashes are what we use because when we
finish all the hand waiving they feel right and we can't think of good
ways to attack them for this use.  Secption 4.5 of RFC 3766 attempts to
justify its use of hashes.  Its justification is somewhat unimpressive
in that it starts with the false claim that a cryptographic hash will
not give out any information about its input.
We can show limits on how much information a good hash can leak about
its input,but those limits are much more permissive than zero.
Assuming that hashes are random oracles is a reasonable way to think
about some aspects of protocol security, especially when you have no
better ideas.  However there is significant concern in the cryptography
community about the truth of this assumption.  I think this is still an
open problem and I suspect future solutions may be better than today's
solutions.

--Sam