Re: AES-based PRF for IKEv2

[Hugo Krawczyk <hugo@ee.technion.ac.il>]

Uri,

Dave Wagner answered the main questions here.
Essentially, I was not claiming that I know of an attack against this
construction when you use AES, but rather that your claim that the
pseudo-randomness of the output is ensured by AES being a family of
pseudo-random permutations is incorrect. I do not know what assumptions
will make this construction "provably secure", and I also don't know how
you are going to get confidence on the fact that AES satisfies these
assumptions.

Moreover, ikev2 already offers a solution to the problem of how to get a
prf key out of the DH key g^xy (see page 25 of the draft). 
And ikev2 does not really have a need to deal with too-short keys.
The only places where this could potentially be an issue is when 
(1) you key the prf with Ni|Nr and (2) when authenticating with a
pre-shared key. 
The first is solved by mandating the nonces to be of the length at least
half of the key size (i.e. at least 64 bits each in the case of AES); 
the second by mandating the pre-shared key to be (at least) of the length
of the prf key (i.e. 128 bits for AES). These are not only reasonable
requirements, but without them you'd be weakening the protocol
unnecessarily. As for using a password as a pre-shared key, that's the
problem of an application doing so. Paswords SHOULD NOT be used as
preshared keys. Whoever wants to use password authentication in the ikev2
setting, has the EAP extension of ikev2.

Regarding the rationale of the derivation of the prf key SEEDKEY from the
DH key g^xy in the ikev2 specification: this will be explained in more
detail in the next version of the SIGMA paper. I provided some clues to
the rationale in past postings. Basically, we are using a prf family in
lieu of a family of pairwise independent hash functions (UH). If we used
the latter then we could "provably" argue the security of KEYSEED. 
But then ikev2 implementers should also implement a real family of UH
functions. Assuming that no one would want to do that I settled for the
replacement of UH with a prf family. This does not give you a general
provable construction (I can show pathological examples of prf's that do 
not behave as UH functions), yet it is plaussible that actual
constructions of prfs (such as HMAC or AES) do achieve this property. 
And, in any case, it gives you a well defined "clue" as for what extra
properties you are assuming.

Hugo

PS: there is more to say about these issues,  but luckily this
discussion seems to have moved already to the more appropriate forum
of the cfrg (the IETF's "cryptography forum research group").

On Sun, 23 Mar 2003, Uri Blumenthal wrote:

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