Subject: RE: PRF's and PKINIT: status

From: "Paul Leach" <[email-masked]>
Date: Mon, 27 Sep 2004 20:01:50 -0700

I'm not trying to avoid PRF+ construction. 

I basically agree with your PRF+ construction:

PRF+(k, input, N) = truncate(N, PRF(k, 0 | input) | PRF(k, 1 | input) |
...)

Where N is the required output length in bits (not iterations...).

However, lets forget about PRF+ for now. Assume we just need a 128 bit
AES key, so that the output of the AES PRF is enough without using PRF+.

The problem is with the PRF itself, as I see it. It takes a key whose
length is determined by the krypto suite. How do we get a hash of k_dh
to use as the input of the PRF -- there are no hash functions in
kcrypto. And even if we have a hash, how do we get it to be the
appropriate length if it isn't long enough? 

For PKINIT and k_dh, the following would work (ignoring type safety)
given the current AES PRF (or any PRF that is cryptographically strong):

	k = PRF(some-128-bit-constant-key, g^xy | n_c | n_k)

That seems weird, however.

IMO, it would be better if PRFs took arbitrary length keys.

E.g., for the AES PRF:
	PRF(k, i) {
		kt = SHA1(k)
		t = SHA1(i)
		return (E(kt, t, zero-IV)
	}

Then for PKINIT and k_dh, we'd have
	k = PRF(k_dh, n_c | n_k)
which seems intuitively just right -- k_dh ought to be the key for the
PRF.

Even better would be the following PRF for AES (and everything else with
key length less that 160 bits):

	PRF(k, i) == HMAC-SHA1(k, i)

Or, if SHA1 is too weak, then HMAC-SHA256 for keys up to 256 bits,
HMAC-SHA512 for larger keys.

---

From: Sam Hartman <[email-masked]>
Date: Mon, 27 Sep 2004 23:38:49 -0400

>>>>> "Paul" == Paul Leach <[email-masked]> writes:

I'm explicitly avoiding discussing the pkinit issues until the AES PRF
is resolved.  I believe I have an answer to the pkinit problem that
will satisfy the entire working group.  I'll deliver that answer once
we get done with the AES discussion.
    Paul> However, lets forget about PRF+ for now. Assume we just need
    Paul> a 128 bit AES key, so that the output of the AES PRF is
    Paul> enough without using PRF+.

    Paul> The problem is with the PRF itself, as I see it. It takes a
    Paul> key whose length is determined by the krypto suite. How do
    Paul> we get a hash of k_dh to use as the input of the PRF --
    Paul> there are no hash functions in kcrypto. And even if we have
    Paul> a hash, how do we get it to be the appropriate length if it
    Paul> isn't long enough?

    Paul> For PKINIT and k_dh, the following would work (ignoring type
    Paul> safety) given the current AES PRF (or any PRF that is
    Paul> cryptographically strong):

    Paul> 	k = PRF(some-128-bit-constant-key, g^xy | n_c | n_k)

    Paul> That seems weird, however.

The security of a PRF depends on its key being well chosen.  The AES
PRF in particular will devolve to sha-1 with a constant key.

I don't say that isn't appropriate for key generation, but it is not a
PRF and the theoretical arguments about PRFs do not apply to it.

--Sam

---

From: Nicolas Williams <[email-masked]>
Date: Tue, 28 Sep 2004 00:22:56 -0500

> appropriate length if it isn't long enough? 

Ok, now we're talking.  Yes, I pointed out earlier that we really ought
to have an octetstring2key() or bitstring2key() or whatever you want to
call it (KDF, I think, is what CFRG is calling it).  Larry agrees.

So, I think we need such a thing.  The problem is not in the kcrypto/AES
PRF, but in the lack of a general function for mapping random,
unstructured inputs to keys.  String2key won't do because it's limited
to UTF-8 inputs and because its s2kparams are about slowing it down (so
as to slow down dictionary attacks), whereas we want a fast one function
here (as the DH secret is not subject to dictionary attacks).

> That seems weird, however.

No, that wouldn't work.  For our current PRF that makes assumptions
about the underlying hash functions that are not be safe to make any
more.

> 		return (E(kt, t, zero-IV)

Yes, this is better.

> which seems intuitively just right -- k_dh ought to be the key for the

I agree that it seems right.  Even with octestring2key() we'd still
want, I think, to use the resulting key as an input to a PRF with the
nonces as the other input.

> HMAC-SHA512 for larger keys.

I think so too, and the recent hash function news doesn't make me too
nervous about this, but I think Sam pointed out that HMAC is find for
authentication, but maybe not so safe for PRFs -- the jury seems to be
out on that one (the discussions I've seen have not focused too much on
HMAC-as-PRF).

Nico
--

---

From: Ken Raeburn <[email-masked]>
Date: Tue, 28 Sep 2004 01:54:25 -0400

> AES key, so that the output of the AES PRF is enough without using 

Okay, I think this is where one problem starts.

The PRF in the AES specification (rather, the simplified-profile-based 
specification) is for generating pseudo-random data suitable for key 
generation given an existing AES key.  The combine-keys operation 
discussed some time back is one case where it might be desirable; 
generating secondary encryption keys for use related to an existing 
authentication context is another.

Put another way, the association of a PRF definition in the Kerberos 
crypto framework with a particular encryption system has to do only 
with the type of secret (not published!) key you're feeding it; it has 
nothing to do with the kind of key you want to generate.  That's what 
random-to-key is for.  If you don't already have a key, the only 
operations you can use out of kcrypto are string-to-key, which takes a 
UTF-8 input, or random-to-key, which takes a fixed-size input -- and if 
your input is not of that size, it's your problem.

For getting a Kerberos key out of PKINIT, you need to come up with a 
random bit string of the appropriate length.  For this, yes, a 
pseudo-random function is desirable.  But not the one in the Kerberos 
crypto profile.  That's not how it was designed to be used (insofar as 
it can be said to have been designed).  Perhaps that means we did it 
wrong, or solved the wrong problem, and what we did is useless.  We 
thought we had some uses for it in that form.

You need a PRF, or a PRF+ construction, and for this usage, kcrypto 
doesn't help you.

If this functionality needs to be in kcrypto, well, then I think we're 
back to talking about asking the IESG to send it back to us.

> appropriate length if it isn't long enough?

These, and the general problem of taking a long bit string and boiling 
it down -- or expanding it -- to the right size, are outside the scope 
of kcrypto.

"no hash functions in kcrypto" -- we do have two unkeyed checksum 
types, and I'm supposed to be writing up SHA1 for PKINIT.  But I 
suspect what you mean is that we have no way of saying "I need to 
generate this key type with so many bits, give me a hash function to 
use"?  And which is it, key type or number of bits?  Should 128-bit and 
256-bit AES use different hash functions?  What about 3DES?

> IMO, it would be better if PRFs took arbitrary length keys.

I think these "arbitrary length keys" are not the same "keys" as the 
encryption-system-specific things we talk about in kcrypto.  If the 
PRFs in kcrypto took arbitrary length secret inputs instead of 
cryptosystem keys, then they would be PRFs, but they would not be 
associated with the cryptosystems.

---

From: Jeffrey Altman <[email-masked]>
Date: Tue, 28 Sep 2004 07:04:29 -0400

>out on that one (the discussions I've seen have not focused too much on
The limited references I have been able to find, such as "The Handbook 
of Applied Cryptography",
make statements that HMACs and hash functions should not be used for 
PRFs.  Unfortunately.
they fail to state what they believe would make a good PRF.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 28 Sep 2004 12:49:33 -0400

On Monday, September 27, 2004 20:01:50 -0700 Paul Leach 
<[email-masked]> wrote:

> kcrypto.

Well, that's not quite true.  One of the parameters to the simplified 
profile is an unkeyed hash; ironically, this is used not only for integrity 
checks on encrypted data but also in constructing the PRF.  The 
non-simplified enctypes we currently have also make use of an unkeyed hash, 
and that is likely to be true for new enctypes in the future.  So if we 
need to add "unkeyed hash" as a parameter to an enctype, we can do so. 
IMHO this is another example of a case where we could defer the text change 
until kcrypto goes to draft, but take advantage of the property immediately.

> And even if we have a hash, how do we get it to be the

We still have this problem.  But there are still something like 10 messages 
I haven't read yet, so maybe someone has the answer.

Note that we don't just have this problem for the static-static case.  Much 
of this discussion has been based on the assumption that k_dh is derived by 
truncation, as described in pkinit-20, and that for the static-static case 
we need an additional operation involving a PRF in order to incorporate the 
nonces.

However, it now seems that deriving k_dh by truncation may not be a good 
idea, and that it would be better to use some construction involving an 
unkeyed hash.  If that is the case, then a second level of derivation is 
not necessary at all -- the nonces can simply be appended to the DH secret 
as input to the hash.

Now, we still have the question of what to do if the hash output is not 
large enough to serve as the input to random-to-key...

-- Jeff

---

From: Sam Hartman <[email-masked]>
Date: Tue, 28 Sep 2004 13:14:59 -0400

>>>>> "Jeffrey" == Jeffrey Hutzelman <[email-masked]> writes:

    Jeffrey> On Monday, September 27, 2004 20:01:50 -0700 Paul Leach
    Jeffrey> <[email-masked]> wrote:

    >> The problem is with the PRF itself, as I see it. It takes a key
    >> whose length is determined by the krypto suite. How do we get a
    >> hash of k_dh to use as the input of the PRF -- there are no
    >> hash functions in kcrypto.

    Jeffrey> Well, that's not quite true.  One of the parameters to
    Jeffrey> the simplified profile is an unkeyed hash; ironically,
    Jeffrey> this is used not only for integrity checks on encrypted
    Jeffrey> data but also in constructing the PRF.  The
    Jeffrey> non-simplified enctypes we currently have also make use
    Jeffrey> of an unkeyed hash, and that is likely to be true for new
    Jeffrey> enctypes in the future.  So if we need to add "unkeyed
    Jeffrey> hash" as a parameter to an enctype, we can do so. IMHO
    Jeffrey> this is another example of a case where we could defer
    Jeffrey> the text change until kcrypto goes to draft, but take
    Jeffrey> advantage of the property immediately.

I would object to this class of change being deferred to draft
standard.

---

From: Sam Hartman <[email-masked]>
Date: Tue, 28 Sep 2004 13:19:13 -0400

>>>>> "Jeffrey" == Jeffrey Altman <[email-masked]> writes:

    Jeffrey> Nicolas Williams wrote:
    >> I think so too, and the recent hash function news doesn't make
    >> me too nervous about this, but I think Sam pointed out that
    >> HMAC is find for authentication, but maybe not so safe for PRFs
    >> -- the jury seems to be out on that one (the discussions I've
    >> seen have not focused too much on HMAC-as-PRF).
    >> 
    >> 
    Jeffrey> The limited references I have been able to find, such as
    Jeffrey> "The Handbook of Applied Cryptography", make statements
    Jeffrey> that HMACs and hash functions should not be used for
    Jeffrey> PRFs.  Unfortunately.  they fail to state what they
    Jeffrey> believe would make a good PRF.

I can point to papers describing what to do if you want a HMAC-based
PRF.  But as far as I can tell kcrypto gives us a perfectly good PRF,
so I see no need to change it.

I'm still not speaking to pkinit.

---

From: Nicolas Williams <[email-masked]>
Date: Tue, 28 Sep 2004 12:19:05 -0500

> I'm still not speaking to pkinit.

We await eagerly.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 28 Sep 2004 13:59:11 -0400

> I would object to this class of change being deferred to draft

But you would not object to actually making the change, right?

Can you explain why you find it acceptable to defer the PRF requirement
but not this change?

In my mind, the PRF requirement is adding text to state something that was 
clearly already the intent of the WG, and so doing it now is not a big deal 
but deferring it probably isn't either.  But this change is adding a new 
requirement not previously considered, which happens to be already met by 
all existing enctypes and which will likely be met by any enctypes defined 
in the future.  The "new requirement" bit is why I'm concerned about being 
able to make the change now (I don't object to it; I'm just concerned Russ 
might).

-- Jeff

---

From: Sam Hartman <[email-masked]>
Date: Tue, 28 Sep 2004 14:13:33 -0400

>>>>> "Jeffrey" == Jeffrey Hutzelman <[email-masked]> writes:

    Jeffrey> But you would not object to actually making the change,
    Jeffrey> right?

I think I would object to making the change.

I would not be surprised if future enctypes use some of the
authenticated encryption modes that do not require a hash.

--Sam

---

From: Jeffrey Altman <[email-masked]>
Date: Tue, 28 Sep 2004 14:30:13 -0400

Here is what I propose for the IETF process part of this discussion.
I really hope there are no disagreements:

The current kcrypto document remains in the RFC Editors queue and is 
published as is.

For the purposes of changing the PRF description text and adding 
whatever new functionality
the working group believes is needed for PK-INIT and Extensions will be 
done in a revised
Kcrypto document which will be recycled at "Proposed Standard".

The revised Kcrypto document will be submitted at the same time as PK-INIT.

Jeffrey Altman

---

From: Nicolas Williams <[email-masked]>
Date: Tue, 28 Sep 2004 13:41:08 -0500

> Kcrypto document which will be recycled at "Proposed Standard".

If there any any references to analysis of the kcrypto PRF construction,
these could be added as informative in author's 48.  Otherwise I agree,
make no changes to kcrypto now, please.

Nico
--