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

From: "Liqiang(Larry) Zhu" <[email-masked]>
Date: Sun, 26 Sep 2004 23:14:42 -0700

1) there is no assurance in kcrypto that PRF(k, x) != PRF(k, y) with
high probability if x != y

 Sam indicated that this property can be implied by the word
"cryptographically-strong": failing to do so the PRF is not a
cryptographic PRF. 

2) the PRF for AES-256-CTS in particular is a bad one (as defined
draft-raeburn-krb-rijndael-krb):

    pseudo-random function    tmp2 = SHA-1(octet-string)
                              PRF = E(protocol-key, tmp2, zero-IV)

This is because the output of this PRF is only 160 bits long, which is
not suitable for use in generating a 256 bit key.

An improved version would be

    pseudo-random function    tmp1 = SHA-1(0x00 | input-octet-string) |
SHA-1(0x01 | input-octet-string) | ...  
                              tmp2 = truncate tmp1 to 256 bits
                              PRF = E(protocol-key, tmp2, zero-IV)

This esentially means that the PRF output should be no shorter than the
key generation seed length K.

3) With the improved PRF definition, Paul and I would like to propose

   the reply key k = raondom-to-key(PRF(k_dh, g^xy | n_c | n_k))

here k_dh is obtained by truncating the MSBs.

We believe it is worth the trouble delaying publication for kcrypto: it
is just an unfortunate reality when the rubber meets the road. Folks
from Microsoft are under time-pressure no worse than any other
interested parties here.

-- Larry

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]] On Behalf Of Jeffrey
Altman
Sent: Saturday, September 25, 2004 4:38 PM
To: [email-masked]
Subject: Re: Concern: Does kcrypto imply that PRF is really a PRF

Sam Hartman wrote:

> Does the working group agree that it is our intent that PRFs used for 
> kcrypto be cryptographically strong PRFs meeting with generally 
> accepted definitions?

Under what circumstances would be appropriate for the kcrypto PRF to not
be cryptographically strong?

Given our intended uses I agree that the kcrypto PRF must be
cryptographically strong.

Jeffrey Altman

---

From: Ken Raeburn <[email-masked]>
Date: Mon, 27 Sep 2004 05:31:03 -0400

> not suitable for use in generating a 256 bit key.

There is nothing that says that the output of one invocation of the PRF 
is big enough to produce a key.  Multiple invocations may be needed.  
For a 256-bit key, obviously, more than one 160-bit string has to be 
generated.

>                               PRF = E(protocol-key, tmp2, zero-IV)

If the PRF were specified as a key generation function, perhaps.  It's 
not.  It's for producing pseudo-random data.  One intended application 
for it is in generation of keys, but that's not the same thing.

Your suggestion doesn't seem very different from what you'd get by doing

     X = PRF(key, 0x00|input-string) | PRF(key, 0x01|input-string) | ...

under the current PRF definition, which is probably how I'd go about 
trying to produce a key using the PRF.

Ken

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 27 Sep 2004 11:43:42 -0500

> "cryptographically-strong": failing to do so the PRF is not a

This should be easy enough to fix, for AES at least.  I don't really
care if the other enctypes' PRFs are not strong :)

> not suitable for use in generating a 256 bit key.

This does not mean that the AES PRF is not cryptographically strong
though.

>                               PRF = E(protocol-key, tmp2, zero-IV)

You're constructing a sort of PRF+, which the caller to PRF can also do.

> key generation seed length K.

That would be nice, but I don't see why it must be so or what that has
to do with the cryptographic strength of the PRF.

> here k_dh is obtained by truncating the MSBs.

Isn't there a type problem with k_dh?  You still have to random-to-key
the k_dh if you want a protocol key to feed to the PRF().

Perhaps this:

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

Here we don't need truncation and we don't care that the PRF produces
too few bits, but if we did we could still plug-in a PRF+().

> from Microsoft are under time-pressure no worse than any other

I think it would be nice to update kcrypto to include the words
"cryptographically strong" to describe the PRF and/or a normative
reference for the meaning of that should be added.  But I don't think we
must update it.

The fact of the matter is that we probably don't want to change any of
the kcrypto PRFs, even if any non-AES enctypes' PRFs are found to be
wanting.  And future enctypes (e.g., based on counter modes, such as
GCM) are likely not to fit the simplified profile anyways.

Nico
--

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 27 Sep 2004 12:07:09 -0500

> care if the other enctypes' PRFs are not strong :)

To clarify: I do care though about the strength of the kcrypto PRF
construction, as it's the one that' used for AES, but I don't care if
the other enctypes' resulting PRFs are weak -- they are, at least the
1DES enctypes', compared to AES'.

I'm curious though, why does the AES enctype use an HMAC-based PRF for
its string-to-key construction?  This is not the PRF defined in
kcrypto...

Cheers,

Nico
--

---

From: Sam Hartman <[email-masked]>
Date: Mon, 27 Sep 2004 14:28:07 -0400

>>>>> "Liqiang(Larry)" == Liqiang(Larry) Zhu <[email-masked]> writes:

    Liqiang(Larry)> 2) the PRF for AES-256-CTS in particular is a bad
    Liqiang(Larry)> one (as defined draft-raeburn-krb-rijndael-krb):

    Liqiang(Larry)>     pseudo-random function tmp2 =
    Liqiang(Larry)> SHA-1(octet-string) PRF = E(protocol-key, tmp2,
    Liqiang(Larry)> zero-IV)

    Liqiang(Larry)> This is because the output of this PRF is only 160
    Liqiang(Larry)> bits long, which is not suitable for use in
    Liqiang(Larry)> generating a 256 bit key.

And AES generates 128-bit blocks.  All you have shown is that the PRF
uses at most 160-bits of entropy from the functional input.  Put
another way, you should not call this PRF more than 2**80 times with a
given key.  That seems acceptable to me; if you believe it is not
acceptable you should have brought it up during the last call of
either AES or kcrypto.

--Sam

---

From: Ken Raeburn <[email-masked]>
Date: Mon, 27 Sep 2004 15:30:04 -0400

> acceptable you should have brought it up during the last call of

As an aside, the lack of any discussion of limiting the numbers of 
calls, blocks, bytes, whatever, is one thing I'm not too happy with in 
the Kerberos crypto and protocol documents.  Not that I have any 
interesting ideas what to say about it besides "oops"... :-(

Ken