Subject: RE: static-static DH proposal

From: "Liqiang(Larry) Zhu" <[email-masked]>
Date: Fri, 24 Sep 2004 16:00:47 -0700

Ken Raeburn wrote:

> For the moment.  If Something Bad happens, like AES gets broken 
> in six months, and we come up with a new cryptosystem based on 
> CCM mode or something and not using the simplified profile, then 
> Kerberos 5.3 might not require an n-fold implementation.

The n-fold is not than hard to implement, certainly not hard to 
keep it around when AES-CTS is removed

> We don't have a lot of analysis at this point in terms of 
> how the secrecy or entropy of the result should or does relate 
> to the inputs for compliant Kerberos cryptosystem PRFs in general. 

I would have more confidence if one method has been used in practice. 
Do you know anything else is using the truncated DH shared secret?

> That seems like a poor way to approach it.  The spec for the PRF
> should indicate what properties it should have (and maybe we should've

> done a better job of that?), and the use of the PRF in PKINIT or 
> anything else should be based on those properties, not based on 
> additional properties inferred from examination of all existing 
> instances at a given point in time.

I think the kcrypto spec on PRF is pretty weak, and this is the first
instance 
where the PRF is used, the spec should be updated or we should come up 
with the next version right away to make sure the PRF meets the need
here.

From a more philosophic perspective, nobody says HMAC has the property 
that the hash of a secret has no less entropy/secrecy than that of the
key, 
but it is widely used in key derivation and the method is believed to be
secure.  

--Larry
-----Original Message-----
From: Ken Raeburn [mailto:[email-masked]] 
Sent: Friday, September 24, 2004 3:12 PM
To: Liqiang(Larry) Zhu
Cc: <[email-masked]>
Subject: Re: static-static DH proposal

On Sep 24, 2004, at 17:55, Liqiang(Larry) Zhu wrote:

> 1) I thought AES is a MUST.

For the moment.  If Something Bad happens, like AES gets broken in six
months, and we come up with a new cryptosystem based on CCM mode or
something and not using the simplified profile, then Kerberos 5.3 might
not require an n-fold implementation.

> 2) I do not rely on n-fold, that is why I feed the whole g^xy into the

> PRF.

You're using it to generate the key for calling the PRF, aren't you?

We don't have a lot of analysis at this point in terms of how the
secrecy or entropy of the result should or does relate to the inputs for
compliant Kerberos cryptosystem PRFs in general.

> Sam Hartman wrote:
>> I know you can do worse.  So you need to show that  your proposal 
>> does not end up doing worse.
>
> I can see with all existing/defined PRFs in kcrypto, I am not doing 
> worse (I can argue with you if you disagree with this one), but I can 
> not foresee the future. If such PRF is created in the future, the KDC 
> can just forbid the use of the corresponding enctype with PKINIT.

That seems like a poor way to approach it.  The spec for the PRF should
indicate what properties it should have (and maybe we should've done a
better job of that?), and the use of the PRF in PKINIT or anything else
should be based on those properties, not based on additional properties
inferred from examination of all existing instances at a given point in
time.

Ken

---

From: Nicolas Williams <[email-masked]>
Date: Fri, 24 Sep 2004 18:10:33 -0500

> Do you know anything else is using the truncated DH shared secret?

Proof of the security of truncation was posted.

Nico
--

---

From: Sam Hartman <[email-masked]>
Date: Fri, 24 Sep 2004 19:35:44 -0400

I think the PRF property is well understood and is sufficient for our
needs.  I don't know what the canonical citation for a PRF definition
is.

Let a_f be an adversary with oracle access to some function f. Let r
be a random function.  Roughly p(key, index)-> value is a PRF if there
exists no adversary a_f and for k chosen from the set of all possible
keys, such that a_f can determine with probability better than
0.5+epsilon the difference between a_r and a_p(k).

Epsilon is some vanishingly small polynomial in the lengths of the
inputs of p.  Actually, I guess you probably want to choose r after
choosing the adversary in that definition as well.

If the prf satisfies that definition, what I'm doing is safe.

--Sam

---

From: Sam Hartman <[email-masked]>
Date: Fri, 24 Sep 2004 19:47:38 -0400

Hmm, it's been too long since I've looked at formal definitions.
Typically oracle access to a function would be a^f not a_f.  Of course
I was playing loose with notation in many other ways as well.

---

From: Ken Raeburn <[email-masked]>
Date: Fri, 24 Sep 2004 20:05:02 -0400

> keep it around when AES-CTS is removed

Yes, I don't think this is a very big deal.

> Do you know anything else is using the truncated DH shared secret?

Haven't really looked.  So, no, but that doesn't mean much.

I've stared at n-fold enough to be uncomfortable with using it for 
anything more than assuring equal contributions by each input bit.  
Generating collisions is easy if you control the input.  Assuring 
yourself that there aren't likely to be collisions under certain 
circumstances is hard.  (Of course, we can't assure the absence of 
collisions for sha1 either, but we're confident the probability is low, 
and we have no reason to be so confident with n-fold.)

Oh, and by the way: You still have a type mismatch error in your 
proposal.  n-fold takes a bit string input, and g^xy is a number; you 
need to specify the format of the bit string.

If we assume the number is converted to an octet string representation, 
MSB first, and if in some cases the length is a multiple of K, then 
n-fold starts to resemble modular arithmetic.  Given that we're 
starting with math to get to g^xy in the first place, I'd be a bit 
concerned that this could simplify an attacker's estimation of the 
result in some way.  (It may not, and I don't see how it would.  But 
it's an angle I'd want to see someone investigate a little more.)

> but it is widely used in key derivation and the method is believed to 

HMAC is a specific approach that's been looked at a lot, and there are 
statements that can be made about its use if you can make certain 
assumptions about the hash function.  Even if certain statements cannot 
be made, its resistance to attacks has given people some confidence.  
Our PRF is a place for a cryptosystem author to drop in a function of 
his choosing, so we can't say much.

I kind of assumed that strong key generation would be the key (so to 
speak) to having a good PRF that you could get keying material out of.  
You're using a key generation function which may or may not be strong, 
and relying on having lots of unpredictable material in the octet 
string.  There's nothing in the PRF spec that says the output can't 
reveal parts of the octet string input, as long as the random-to-key 
operation isn't significantly weakened by doing so.

Ken