Re: AES-based PRF for IKEv2

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

Hugo Krawczyk wrote:
>>SECURITY PROPERTIES.
>> 
>>A block cipher being a Pseudo Random Permutation, if the
>>S parameter is secret, the following hold true:

Let me clarify this statement. An [unbroken] block cipher
is a FAMILY of pseudo random permutations INDEXED by the
key. So for any GIVEN key this block cipher is a pseudo
random permutation. It is assumed to be true for AES.

>>   - output of (3) is pseudo-random.
>>   - output of (5) is pseudo-random.
> 
> Unfortunately, this is incorrect.

I would like to see it shown for AES.

I.e. please show how you can distinguish the AES output
of (3) and/or of (5) from a random string, if you don't
know S, but know the rest of the input.

Also, I would like to see how you can distinguish AES
output from random 128-bit string, if you know the
relation between the key bits and some of the
input bits, know the rest of input bits, but
don't know the key.


> If all what you assume about the block cipher is that it
> is a pseudorandom permutation then to be able to get a result 
> as you state you need to assume that all the values used to key
 > the block cipher are random (or pseudo-random, in the
 > complexity-theoretic sense).

Of course I also assume linearity of the key space.

What other assumptions are necessary in your opinion?


> That means that you need to assume S to be secret (as you do) but also
> random (that you don't do) and of at least the length of the cipher's
> keys (what you don't do either).

Please explain why S should be random. In all the literature I'm
aware of, all the analysis of block ciphers made no assumptions
about the key except being unknown to the adversary.


 > Specifically one can build examples of perfectly secure
> pseudorandom permutations that will induce insecure outputs from (3)
 > and (5).

Very well - I'd like to see them for my education (so please
e-mail me an example) - but it doesn't seem to apply to AES.


 > This was pointed out by Dave Wagner for the case in which S is
 > too short,

The adversary cannot know whether the key in use has any specific
property - such as being short, or having x zeroes as suffix.
After all, the bit string of all zeroes is as random as any
other string.

And if the adversary has a good reason to assume that the key is
short - then nothing will help, because no matter what type of
transform you apply to that key, the key itself will remain
the weakest link and will be attacked by brute force. It
applies to any PRF, block cipher-based and hash-based.


 > and one can also give examples in which S is longer than the key
> (but not uniformly distributed).

Again, I think it does not apply to AES (because of its keyspace
properties) - but I personally would like to see an example
e-mailed to me.

If you mean that knowing the properties of the key - such as
knowing in advance that the key is likely to have only 4 bytes
of "juice" and the rest filled with zeroes - makes this approach
insecure, I'll fully agree. And will add - in such a case there's
no way to secure it, because no matter what you do, I'll attack the
weakest link - the short key itself.


> Now, clearly, if you assume that the given value S is already a good
 > random key for the prf then you do not need all the construction.

You need a similar construction to mix in the nonces. And it
seems a good tradition to step further away from the generator
key...

The approach I'm suggesting is taken directly from the Rijndael
submission to NIST (specifically the Hash and PRF sections). If
there are problems with it - why didn't somebody (you for
example :-) write something about it and publish?


> Finally, regarding the use of this method with a DH key S=g^{xy} as you
> suggest. In this case you'd take the first, say, 128 bits of g^{xy} as
 > the key to the block cipher and the rest as data.  Under which
 > assumptions on DH and the block cipher you can claim the proposed
 > key derivation to be secure? Note that the attacker knows g^x, g^y.

The assumptions are:

1. Block cipher is a family of PRP indexed by the key. An unbroken
    block cipher should satisfy this.
2. Block cipher has linear keyspace (there is no class of weak keys),
    so there is no specific property of the key that makes the cipher
    weak. [we aren't discussing idiotic cases like using short keys
    padded with known quantity, so the attacker has to search only
    say 2^32 space because the rest is all 1's or all 0's.]
3. It is practically impossible to determine more than a few bits of
    g^xy when you know both g^x and g^y.

If other assumptions are necessary to consider this approach secure,
please share them (and the justification behind) with me.

Thanks!