Re: AES-based PRF for IKEv2

[Uri Blumenthal <uri@bell-labs.com>]

David Wagner wrote:
>>Not quite - a key with all zeroes is just as random as any other key.
> 
> No, no, no.  You're confused.  Keys aren't random; it's the process
> used to create them that might or might not be random.

Yes, precisely. We shouldn't even have this argument - see below.
We were simply misunderstanding each other. Read ahead.

> A number like 000 isn't random, and it isn't uniformly distributed;
> it makes no sense to try to attach the term "random" to simple numbers.

Exactly. I simply was pointing out that the mere presence of
large number of zeroes in the key means nothing either way
from the randomness point of view.

Let us review the assumptions and the algorithm.

I'm taking a secret key. I'm using it to load the PRNG to crank out
more pseudo random data. I've no idea about the structure of the key
and whether its bits are correlated or not. I assume that their
correlation is weak, but that's up to the user of the construct.
In IKE this shouldn't be a problem, as DH output is believed to
be "good enough" and "random enough".

In other uses, which probably are of no interest to IPSEC WG,
the key can be truly random, really bad, really long, really
short - or anything n between. Depending on that, the
security of the construct will be high or low, quite
in compliance with the "manure in - manure out" principle.
I might add that pretty much all the PRNG are subject to this
principle as well - if your initial key is bad and falls into a
known-to-the-adversary class (i.e. 6-character ASCII string),
then no matter what algorithm you use, it will be broken.

Also - the keying material is the same as in the existing
PRF (HMAC). The processing is also very similar. SHA - the
heart of HMAC - has much weaker built-in properties than AES.
So how come you aren't happy with this, but are happy with that?
What makes SHA closer to "random oracle" than AES?


> The point is that we must look at the process used to create the key.
> When using a PRP, that key-creation process must provide outputs that
> are secret, random, and uniformly distributed on the cipher's keyspace.

These are two different areas! One is whether the cipher is
secure for any key from its keyspace. The other one is how
much of the keyspace the key-supplying algorithm covers.
I.e. what kind of structure the enciphering key has.

The cipher itself is still "good", but for the adversary it
became easier to determine what the key is, because of the
structure it has (it doesn't cover the whole keyspace now).

So it's not the "random key" as in "being produced by Random
Number generator" - it's having no preimposed structure that
allows the adversary to make assumptions about the key and
thus cut his work effort.


> The key-creation process you specified does not qualify: the last bit
 > of the AES key is much more likely to be 0 than to be 1, for instance.

Not true. It may be true ONLY in the outside-of-IKE use when
really somebdy decides to employ short keys. Not recommended
practice anyway- but has (IMHO) to be specified for the sake
of completeness.  Nobody proposes implementing short keys in
IKE.


>>There are ciphers in use like that (especially in the military),
>>but it is *assumed* that AES keyspace is linear.
> 
> Assumed by whom?  The assumption that AES is a secure PRP does *not*
> guarantee that its keyspace is "linear" (whatever that means precisely).
> And the standard security goal for block ciphers is that they be a
> secure PRP.

For the sake of this discussion - "linear keyspace" means there are
no weak keys. Do you argue with this, and if so - what's your justification?

For example DES has almost "linear keyspace" - only 4 weak keys
and only 16 semi-weak ones, so the chance to hit them was very
small.

Some ciphers however have significant part of their (large!)
keyspace "weak", for the purpose of non-reuse of the equipment
by unauthorized parties (you're likely to pick a bad key, unless
you're "initiated" and know to select them from a certain class).


> As a result, among all unproven security properties, PRP-ness is
 > probably the property ttat we can have the most confidence in.)

So let's stick to it.

And until weak keys are found, I assume there are none - just
like until an attack against Rijndael is found - I assume it
holds unbroken.