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

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

> -----Original Message-----
> From: Nicolas Williams [mailto:[email-masked]]
> Sent: Monday, September 27, 2004 11:38 AM
> To: Paul Leach
> Cc: Ken Raeburn; Liqiang(Larry) Zhu; [email-masked]
> Subject: Re: Concern: Does kcrypto imply that PRF is really a PRF
> 
> On Mon, Sep 27, 2004 at 11:31:37AM -0700, Paul Leach wrote:
> > 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)
> 
> What proposal, simplified accordingly, does this correspond to?  Not
to
> PRF+.
[Paul Leach] Sorry -- I thought it would be clear. It corresponds to
using a PRF to get a bit-string of length less than N and then extending
it with a PRF+ construnction.

> 
> > 2)
> > Ki = SHA1(Kb | R | i)
> > K = truncate(K0 | K1 ... , N)
> 
> This roughly corresponds to PRF+.
[Paul Leach] It corresponds to a combined PRF/PRF+ -- a PRF that can
generate arbitrary length output.

> 
> I insist: you seem to propose a new PRF constructed using PRF+
> techniques and you do so ostensibly to avoid a PRF+.
[Paul Leach] No, I propose a PRF that does not discard entropy in its
input, and generates arbitrary length output.

But I take your point. I've conflated the two issues.

> 
> 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)

[Paul Leach] This is a perfectly fine PRF+. The problem is that the PRF
in question discards entropy. If the PRF were
	output = SHA1(k | input)
Instead of
	t = SHA1(input)
	output = E(k, t, 0)
then I'd be happy.

> 
>     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().
[Paul Leach] I understand -- I elided that for simplicity.

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 27 Sep 2004 14:06:47 -0500

> in question discards entropy. If the PRF were

The PRF must discard entropy as it maps from an infinite set to a finite
one.

Both constructions of PRF that you give discard entropy from one, the
other or both of the inputs, as it must.

And you need a PRF+ with either of those two PRF constructions as the
output is too small (the same) for both.

So, to recap:

a) Is the kcrypto PRF construction cryptographically strong?  I don't
   know, but I don't see why it wouldn't be strong enough in the context
   of PKINIT, where some of the bits of the input string are secret, not
   just the key's bits.

b) Can we add those magic words to kcrypto?  No, I don't think so, not
   without some innormative reference to relevant definition and
   analysis of such a construction.  If such references exist then
   adding them to kcrypto in 48hrs author's review should be feasible
   (since adding the references does not change the spec).

c) Should we change the kcrypto PRF construction so it outputs more
   bits?  I don't see why, short of finding that the kcrypto PRF
   construction is not cryptographically strong (for strong ciphers and
   hashes, of course), since truncation and a PRF+ are sufficient to
   deal with impedance mismatches.

Nico
--

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Mon, 27 Sep 2004 16:05:26 -0400

>    deal with impedance mismatches.

Allow me to clarify something here.

The kcrypto document does two things relevant to this discussion:

(A) It defines the parameters that must be specified for every enctype.
    One of these parameters it the definition of a PRF.  The document
    says the PRF MUST have these properties:

      This pseudo-random function should generate an octet string of
      some size that independent of the octet string input.  The PRF
      output string should be suitable for use in key generation, even
      if the octet string input is public.  It should not reveal the
      input key, even if the output is made public.

    That's three properties:
    - The size of output is not dependent on the input.
    - The output quality must be good enough for keying material, even
      if the input string is public or well-known.  Note that it does
      not say that the output must be a key of any particular type,
      only that it should be "suitable for use in key generation".
    - The output must not reveal the input key.

    We apparently erred here in not saying MUST, but then, this document
    is for writers of future enctypes, not implementors, and writers of
    future standard enctypes have the full powers of IETF concensus.

(B) It describes how to construct enctypes based on a simplified profile.
    Part of this description includes the definition of the PRF for all
    enctypes that use the simplified profile, including AES and 3DES.
    This definition does not apply to the single-DES enctypes.

As near as I can tell, this thread started out with a question as to 
whether (A) required that the PRF be cryptographically strong, thereby 
allowing us to depend upon that property in the construction of protocols 
like PKINIT.  However, it seems to have devolved rather quickly into a 
discussion of the particular PRF defined by (B), and whether it is suitable 
for a variety of uses.

It's not unreasonable to discuss whether the PRF defined by (B) is 
cryptographically strong.  After all, if it is not, then we cannot add that 
requirement to (A) without fixing it.  From the discussion so far, it 
appears to me that the group does agree that the PRF defined by (B) is 
indeed cryptographically strong.  If anyone disagrees with this narrow 
conclusion, please say so now.

It is also not unreasonable to discuss whether the PRF defined for the 
single-DES enctypes is cryptographically strong.  Again, if it is not, then 
we cannot add that requirement to (A) without fixing it.  I have seen _no_ 
discussion on this topic, so I will ask folks to examine this again now. 
If anyone believes that the PRF defined for DES-CBC-{CRC,MD4,MD5} is _not_ 
cryptographically strong, please say so now.

OK.  So now we have a requirement we'd like to specify, and hopefully some 
PRF's which meet the requirement, and a document that is bubbling its way 
to the top of the RFC-Editor's queue.  Where we go from here depends on 
whether we believe the PRF's already in the document meet the requirement, 
or if we have to replace one or both of them.

(1) We can, of course, do nothing at all.

(2) If the PRF's defined in the document meet the requirement, then I
    believe we can add a sentence spelling out the requirement during
    final editing.  I find this acceptable only because it is clear to
    me from discussion, intended uses, and the existing definitions
    that it has always been the intent to have this requirement.  Even
    so, this option is subject to AD approval.

(3) If the PRF's defined in the document do not meet the requirement,
    then we will have to change them in order to add the text which
    states the requirement.  This will require recalling the document
    from the RFC-Editor, obtaining a WG concensus on the changes, and
    re-submitting it.  Again, it is possible the AD will not permit
    us to do this at this late date.

Please allow me to be clear.  This document is OUT OF OUR HANDS.
Getting it back is a significant step, which we should undertake only if it 
is absolutely necessary.  So, please ask yourselves this - is it really 
necessary to change the definitions of these PRF's, or is it merely 
something that would be nice?

-- Jeff

---

From: Sam Hartman <[email-masked]>
Date: Mon, 27 Sep 2004 16:51:30 -0400

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

    Jeffrey> As near as I can tell, this thread started out with a
    Jeffrey> question as to whether (A) required that the PRF be
    Jeffrey> cryptographically strong, thereby allowing us to depend
    Jeffrey> upon that property in the construction of protocols like
    Jeffrey> PKINIT.  However, it seems to have devolved rather
    Jeffrey> quickly into a discussion of the particular PRF defined
    Jeffrey> by (B), and whether it is suitable for a variety of uses.

What I really wanted to say is that it seems obvious to me that we
intended the thing we called a PRF to be a PRF in the cryptographic
sense.  We listed some properties of such a PRF, but we did not list
all such properties.

Do people agree that is what we intended to do?

--Sam

---

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

> Do people agree that is what we intended to do?

I agree that that is, indeed, what the WG intended.

Are there any papers on the kcrypto PRF construction that could be added
as informative references in author's 48?

In any case, I think that the kcrypto PRF meets does possess qualities
stated by kcrypto and suffices for PKINIT purposes.

Nico
--

---

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

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

    Nicolas> I agree that that is, indeed, what the WG intended.

    Nicolas> Are there any papers on the kcrypto PRF construction that
    Nicolas> could be added as informative references in author's 48?

There should be; will go look.