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

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

> -----Original Message-----
> From: Nicolas Williams [mailto:[email-masked]]
> Sent: Monday, September 27, 2004 12:07 PM
> To: Paul Leach
> Cc: Ken Raeburn; Liqiang(Larry) Zhu; [email-masked]
> Subject: Re: Concern: Does kcrypto imply that PRF is really a PRF
> 
> 
> The PRF must discard entropy as it maps from an infinite set to a
finite
> one.
[Paul Leach] Duh. But it can waste entropy by discarding more of it than
it intrinsically must.

For example, this is a PRF
	output = SHA1(k | truncate(input, 10))

But it's a stupid one -- it wastes entropy that it could easily capture.
This one
	output = SHA1(k | SHA1(input))
also wastes entropy it could easily capture.
Whereas this one
	output = SHA1(k | input)
keeps as much entropy as the hash function allows (160 bits).

> 
> 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: Sam Hartman <[email-masked]>
Date: Mon, 27 Sep 2004 16:54:44 -0400

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

    Paul> For example, this is a PRF output = SHA1(k | truncate(input,
    Paul> 10))

That's not a PRF.  It discards too much of its input.  You can
construct an adversary that knows two values that have the same
initial 10 bits.