Subject: RE: Concern: Does kcrypto imply that PRF is really a PRF

From: "Paul Leach" <[email-masked]>
Date: Mon, 27 Sep 2004 11:31:37 -0700

I think the core question here is as follows.

Consider the following two ways to create an N bit key K given a base key Kb and a random bit string R whose length is _longer_ than N and a hash whose output length is less than N:

1)
T = SHA1(R)
Kt = SHA1(Kb | T)
Ki = SHA1(Kt | i)
K = truncate(K0 | K1 ... , N)

2)
Ki = SHA1(Kb | R | i)
K = truncate(K0 | K1 ... , N)

IANAC, but the second one looks better at transferring the entropy of R into the output key.

Note that this is a different situation than when starting with less than N bits of entropy and just expanding those bits with a PRF+ -- we've started with more that N bits of entropy and would prefer to preserve them.

> -----Original Message-----
> From: Ken Raeburn [mailto:[email-masked]]
> Sent: Monday, September 27, 2004 11:04 AM
> To: Liqiang(Larry) Zhu
> Cc: Paul Leach; Ken Raeburn; Nicolas Williams; [email-masked]
> Subject: Re: Concern: Does kcrypto imply that PRF is really a PRF
> 
> On Sep 27, 2004, at 13:40, Liqiang((Larry)) Zhu wrote:
> > Nicolas Williams wrote:
> > > You will have key-size impedance mismatches.
> > > You will need a PRF+.
> >
> > that is because I do not think you intended to say you allow
> > applications to generate a 256 bit keys via a PRF of a 56 key-size
> > enctype. no matter how clever your PRF+ is, it is not going to do you
> > any good.
> >
> > do you agree with me on this point before we proceed further.
> 
> I would disagree with that.  The generated key space is still only
> 2^56, but that doesn't mean AES shouldn't be allowed to be used.  It
> would be deceptive to suggest that the full 128- or 256-bit key space
> is available, but that's a different matter.  (If you're going to
> impose that restriction, you might also re-examine whether we should
> allow 256-bit AES keys to be generated from passwords at all.)
> 
> As for key generation, a combine-keys type operation should be possible
> using the PRF -- use the PRF of each key, which keys could be of
> different types and could generate different length PRF output, and
> combine them in some way to provide input to the random-to-key
> function.  (So my comment in the "static-static DH proposal" thread
> Friday night was wrong -- if the PRF reveals part of the input, it's
> clearly unsuitable, because the random-to-key operation eventually used
> may be for another encryption type and may not be wise to use with
> non-random input.)

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 27 Sep 2004 13:37:54 -0500

> K = truncate(K0 | K1 ... , N)

What proposal, simplified accordingly, does this correspond to?  Not to
PRF+.

> K = truncate(K0 | K1 ... , N)

This roughly corresponds to PRF+.

I insist: you seem to propose a new PRF constructed using PRF+
techniques and you do so ostensibly to avoid a PRF+.

I reiterate and expand on my proposal:

 - For PKINIT AES-128 key derivation:

    k = random-to-key(PRF(random-to-key(k_dh), k_dh + n_c | n_k))

 - For PKINIT AES-256 key derivation:

    PRF+(k, n, s) = PRF(k, 0 | s) | PRF(k, 1 | s) | .. | PRF(k, n-1 | s)

    k = random-to-key(PRF+(random-to-key(k_dh), 2, k_dh | n_c | n_k))

Note that PRF does not output a key; its output must still be cast into
a key, thus the use of random-to-key().

Nico
--

---

From: Sam Hartman <[email-masked]>
Date: Mon, 27 Sep 2004 15:27:06 -0400

I'd recommend being careful about the uses of hash functions if you
are assuming anything more than that it is hard to find collisions.  

In particular, assuming that a hash is a random oracle (that is, that
you cannot distinguish hash output from a random function) seems
particularly dubious given recent advances on attacks against hash
functions.  The recent attacks on md4, md5 and sha-0 have all depended
on finding structured inputs that have observable structure in the
output.  IN the case of a complete break, this structure is a
collision.  This is bad for uses of hashes as hash functions.  IT
seems even worse for uses of hashes as random oracles.

So I would be very dubious of any construction that depends on hashes
hiding information or assumes hashes do anything other than make it
hard to find collisions.  The exception to this is HMAC; I don't
understand the theoretical arguments behind why HMAC is secure, but I
think it would be easier if we assume that HMAC-SHA1 is a secure MAC
in this working group.

If you plan to use a hash that is not inside an HMAC in the
construction of a PRF then please explain how your construction relies
only on the hash property.

I can do that for kcrypto.  The point of the hash in kcrypto is to
allow the PRF to work without requiring input be of a certain length.
The PRF would still be secure if we had some oracle that would map the
first call with a given input to 0, , the second input to 1 and so on.
The The hash serves to avoid collisions in the input domain only.

--Sam

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 27 Sep 2004 16:33:52 -0500

>     k = random-to-key(PRF+(random-to-key(k_dh), 2, k_dh | n_c | n_k))

Argh, I forgot that random-to-key()'s input's size is related to the
key's, thus the truncation.

Sam seems to think that there's some other reference about the
randomness of DH secret prefixes.

If that does not pan out you can always hash the k_dh, or use -- ick --
string2key(random-UTF-8(k_dh)) or some such.

Nico
--

---

From: Sam Hartman <[email-masked]>
Date: Mon, 27 Sep 2004 17:50:21 -0400

>>>>> "Nicolas" == Nicolas Williams <[email-masked]> writes:

    Nicolas> Sam seems to think that there's some other reference
    Nicolas> about the randomness of DH secret prefixes.

I wouldn't put it that strongly.  I thought the earlier discussion
concluded something stronger than it seems to.  I'm looking into the
DH truncation issue.

However I'd like to separate the DH truncation issue from the PRF in
kcrypto and from how we generate derived keys for static-static.

--Sam