Subject: Arguing that the AES PRF is correct

From: Sam Hartman <[email-masked]>
Date: Tue, 28 Sep 2004 17:08:22 -0400

Apparently I never managed to get out a fairly long message I had last
night that I hoped would convince people we don't have a problem with
the AES PRF.  Perhaps this contributes to the lack of responses I got
today.

I don't have the text I wrote last night so I'll try and summarize.

Yesterday, Paul presented a PRF candidate that only had 1024 possible
outputs because it truncated its input to 10 bits.  I forget the
specific form; let's assume this would have been a fine PRF had it not
truncated its input.

I pointed out that this isn't a valid PRF.  Paul was confused because
I also pointed out that the entropy in a PRF comes from its key, not
its seed.

I'd like to take a step back and try and explain what it means for
something to be a PRF.  (As an aside, I think we've found a definition
to cite in kcrypto.)

Here's what happens when you try and show me some function I have is
not a PRF.  I'm going to give you some large but limited time in which
to run an algorithm; this time is polynomial in some parameter--the
size of the key, the size of the output, one of those.  Before you
start, I hand you a black box.  It either has the PRF with a randomly
chosen key or it has a random function.  (We ignore for the moment
that random functions do not actually exist in the world of polynomial
time; we are in the world of
oracle access.)  You can feed inputs into the black box and
get outputs.  When your time runs out, you need to tell me whether
your black box contained a PRF or it contained a random function.  You
win by doing better than guessing.

So, with Paul's proposed PRF, the attacker will quickly find out that
there are only 1024 possible outputs.  Note that these outputs are
fine for use in generating keys; the attacker is not going to be able
to guess which output will come out for an input that has not already
been tried.  So, Paul's construction would be fine if you wanted one
or two keys out.  It would not be good to use this PRF to decide how
to key a fleet of cars; several cars would probably end up with the
same key.

The AES PRF has a similar problem if you call it that.  The strength
of its keys is fairly good; you need to either break AES or guess a
256-bit key in order to know what the output will be for a given
input.  Actually we can say something stronger; you need to break AES
or guess the 256-bit key to know anything at all about the output for
an input you haven't tried.

However the output of the AES PRF is only 128-bits.  That means if you
call the AES PRF more than say 2**64 times you run into the
probability that you will find a collision.

Do we care?  I think not.  I think that the uses of a PRF we
contemplate do not anticipate a large number of calls being made with
a single key.  In particular note that this does not compromise the
quality of 256-bit keys that we produce.  An attacker can guess the
256-bit key for the PRF, but doing so is 256-bits of work.  An
attacker can guess two 128-bit numbers, but as we said previously the
attacker cannot get an advantage in guessing the output even given the
input unless there is a collision.  The attacker can also attempt to
break AES; if successful we'll have bigger problems.

Paul, do you see any problems with this?  If so would you please
explain?

When I talked to Larry, he seemed to be making a different argument.
He seemed to be arguing that reasoning about a composite PRF was harder
than if the output of the original PRF was longer.  I don't think
that's particularly true especially for a constant number of calls to
the PRF.  After all if an attacker with the black box could do better
by making two calls to the PRF for every one operation the attacker
wanted to consider, then the attacker could just make the two calls.

Does this make sense?

--Sam

---

From: "Paul Leach" <[email-masked]>
Date: Tue, 28 Sep 2004 18:31:28 -0700

I'm going on vacation for 3 days, so I probably won't get to this until
I return (next Monday).

I will note that it was only my mistaken belief that there was no hash
function in kcrypto that caused me to try to use the PRF as a hash
function (and therefore getting entangled in the question of whether the
properties guaranteed by a good PRF are sufficient to make it a good
hash function).

I think the right way for PKINIT to generate the key from the DH value
is by using the HMAC based on the kcrypto-defined hash H. The
preconditions for the cryptosystem's PRF being right don't hold here
(the DH value is not a key in the cryptosystem).

Paul

---

From: "Paul Leach" <[email-masked]>
Date: Tue, 28 Sep 2004 19:10:44 -0700

> -----Original Message-----
> From: Sam Hartman [mailto:[email-masked]] 
> Sent: Tuesday, September 28, 2004 2:08 PM
> To: [email-masked]; Paul Leach
> Subject: Arguing that the AES PRF is correct
> 
...

> Paul, do you see any problems with this?  If so would you 
> please explain?

I'm convinced that it's an OK PRF for keys that are the size of the
cryptosystem's key. What was throwing me was trying to use it with the
keying material obtained from DH, where (even if truncation were OK,
which we now know it isn't) it needlessly wastes all the entropy greater
than the cryptosystem's key size.

Paul