Subject: AES-based PRF for IKEv2

From: Uri Blumenthal <[email-masked]>
Date: Thu, 20 Mar 2003 18:43:48 -0500

Folks,

Here's a proposal for an AES-based PRF that takes variable-length
input and produces variable-length output.

Please comment.

Thank you!

Regards,
Uri.
PROPOSAL: AES-BASED PRF FOR IKEv2.

The goal is to produce requested amount of pseudo
random bits, using AES (or other block cipher) and 
variable-length input for both secret parameter, and
publicly known parameter. Should work with variable
key length, preferably support different block sizes.
Preferably, the construct is provably secure.

The following idea is based on Rijndael submission 
to NIST. It is assumed that AES is the block cipher
that will be used, but the construct is generic
enough to accomodate other block ciphers.

PRF(S, N)  ALGORITHM.

Two parameters - one is secret, the other one may be
known. No assumption on the quality of randomness of
either one is made. Assume that S is secret and N is
known. No limitation on size of S, N.

Outputs pseudo-random stream of bits in 128-bit chunks
(variable-length output).

Block cipher is assumed, with key-buffer for key, and
data-buffer for plaintext. AES is assumed, but any
other un-broken blok cipher should do.

Algorithm:
  
   1. Fill the key-buffer with S. If S is shorter than
      the key-buffer, pad the key buffer with zeroes.
      
   2. If any bits of S are left after step (1), place
      them in the data-buffer. Append parameter N to
      the data-buffer. Pad the data-buffer with zeroes
      if necessary, to make it multiple of cipher block
      size, and at least as long as key-buffer.

   3. Encrypt as many blocks of data-buffer as necessary
      to fill key-buffer. 

   4. Take the output of (3) and fill the key-buffer.
      Continue (3) and (4) for the reminder of the 
      data-buffer.

   5. At this point the encryption engine is ready to produce
      Pseudo-Random stream.  Now run the encryption engine in
      OFB mode (starting with input buffer filled with zeroes)
      using the full block size, until the desired amount of 
      output bits is produced.

RATIONALE.

a. All the theory of block cipher security is based on the
assumption that the key is unknown to the attacker. Thus
we key the encryption engine with the secret parameter.

b. It is preferred to move away from the given secret
parameter (which is likely to be Diffie-Hellman output).
That is why at least one key change is performed.

c. Variable-length input and output is desirable - this is
accomplished.

SECURITY PROPERTIES.

A block cipher being a Pseudo Random Permutation, if the
S parameter is secret, the following hold true:

   - output of (3) is pseudo-random.
   - output of (5) is pseudo-random.

---

From: [email-masked] (David Wagner)
Date: 21 Mar 2003 17:24:18 GMT

>input and produces variable-length output.
[...]
>known. No limitation on size of S, N.
[...]
>      the key-buffer, pad the key buffer with zeroes.
[...]
>   - output of (5) is pseudo-random.

I don't think your security claims are quite right.  You've padded the key
with zeros.  As a result, you need a stronger assumption than that the
block cipher is a pseudorandom permutation.  A pseudorandom permutation
only guarantees that the cipher is strong for uniformly random keys, not
for keys padded with zeros and not for keys with poor-quality randomness.

For instance, suppose E_k(x) is a block cipher with 256-bit key that
acts as the identity function when the last 128 bits of k are zero,
but otherwise acts as a secure block cipher.  Then E_k(x) will be a
pseudorandom permutation (with security parameter 2^-128), but your
construction will be totally insecure when used with E_.(.) if S is
128 bits long (or shorter).

Given your assumptions on S and N, I suspect you're really going to need
to use a hash function.  (Otherwise, you'll have to use some very strong
assumptions about the block cipher -- e.g., the ideal cipher model --
but I definitely do not recommend doing so.)

---

From: Hugo Krawczyk <[email-masked]>
Date: Sat, 22 Mar 2003 01:10:55 +0200 (IST)

>    - output of (5) is pseudo-random.

Unfortunately, this is incorrect.
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).
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). Therefore the stated security properties 
do not provably hold. Specifically one can build examples of perfectly secure
pseudorandom permutations that will induce insecure outputs from (3) and (5).
This was pointed out by Dave Wagner for the case in which S is too short,
and one can also give examples in which S is longer than the key 
(but not uniformly distributed).

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.

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.

Hugo

---

From: Uri Blumenthal <[email-masked]>
Date: Fri, 21 Mar 2003 13:32:39 -0500

David,

First - thank you for the review! I appreciate it!
My answers are inline.

> for keys padded with zeros and not for keys with poor-quality randomness.

Not quite - a key with all zeroes is just as random as any other key.

> 128 bits long (or shorter).

You are basically saying here that the key space is non-linear.
There are ciphers in use like that (especially in the military),
but it is *assumed* that AES keyspace is linear. And yes - for
non-linear keyspace you need special treatment of the key.
Just randomizing it doesn't always help - it all depends
on the keyspace properties.

> but I definitely do not recommend doing so.)

I don't think that linear keyspace assumption is too much.
And so far there were  no weak keys found for AES, were there?

Thanks!

Regards,
Uri.

---

From: Uri Blumenthal <[email-masked]>
Date: Sun, 23 Mar 2003 03:02:03 -0500

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

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

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

> 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

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

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.

> (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?

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

---

From: Russ Housley <[email-masked]>
Date: Fri, 21 Mar 2003 20:22:15 -0500

Uri:

Steps 1 thru 4 are pretty  slow.  You keep computing the AES key schedule 
over and over.  In 802.11, we have found that this is a very expensive 
operation.  Can it be avoided?

Russ

---

From: [email-masked] (David Wagner)
Date: 24 Mar 2003 21:02:44 GMT

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

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.
The process used to generate it might or might not be random; the
term "random" attaches to processes that generate numbers, not to
the numbers themselves.

Imagine I have a six-sided die.  I claim to you that it is fair, i.e.,
all six outcomes are equally likely.  You roll it 100 times and get a
"6" every time.  If you express some skepticism that my die is fair,
I'm going to tell you that the number "6" is just as random as any other
outcome.  Are you convinced?  I certainly hope not!

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

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

(In my experience, this goal is generally agreed upon by both
theoreticians, block cipher designers, and cryptanalysts.  Sometimes block
cipher designers try for other, extra goals, but being a secure PRP is
usually the most important goal and it is usually the one that receives
the most study from cryptanalysts, in my experience.  As a result, among
all unproven security properties, PRP-ness is probably the property taht
we can have the most confidence in.)

---

From: [email-masked] (David Wagner)
Date: 24 Mar 2003 21:17:36 GMT

>random permutation. It is assumed to be true for AES.

I think you're a little confused about the terminology.
The second sentence above is meaningless.  The term "pseudo
random permutation" -- according to its standard usage in
cryptography -- attaches to a family of permutations, not to a
single permutation on its own.  It makes no sense to say
that a particular permutation (e.g., AES when used with a
particular fixed key) is pseudorandom.

>I would like to see it shown for AES.

I'm not sure you understood the point Hugo and I are making.
Maybe I should try to clarify at more length.  I'm not saying
that your construction is definitely insecure when used with
AES.  I'm not saying it is definitely secure, either.

Rather, I'm suggesting it would be premature to accept your
construction for IPSec.  I'm saying that its security analysis
is not well enough developed.  The assumptions about AES needed
(to ensure the security of your construction) are unclear and
non-standard.  In particular, the PRP assumption does not
guarantee that your construction is secure.  This is all about
understanding what security assumptions we have to make, which
I claim ought to be an important part of any act of modern
cryptographic design.

Your construction might be secure when used with AES, or it might
not.  I don't have any idea whether it is or it isn't.  But we can
say this: It's not enough merely to assume that AES is a secure PRP.
If your construction does happen to be secure, it must be because
AES has some additional security properties that not all PRP's
are guaranteed to have.

The natural question then is whether it is reasonable to assume
that these necessary additional properties hold for AES.  Since
those required properties have never been clearly stated, that
question is hard to answer with confidence without knowing precisely
what those additional assumptions might be.  However, I can say
this much: these additional assumptions are going to be at least
a little bit non-standard.  The standard assumption about AES is
that it is a secure PRP.  "PRP-ness" is the standard goal agreed
upon both by block cipher practitioners and by theoreticians
(though sometimes people try for additional goals).  As a result,
we usually have more confidence in "the PRP assumption" than
we would have in any other assumption.

In short, I believe it would be premature to accept your
proposal.  Here's what I would propose: I suggest working out
a formal security analysis for your construction, running the result
by ietf-cfrg, and if it meets approval there, then let's consider
it for inclusion in IPSec at that point.

---

From: Hugo Krawczyk <[email-masked]>
Date: Tue, 25 Mar 2003 06:36:26 +0200 (IST)

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").

---

From: Uri Blumenthal <[email-masked]>
Date: Mon, 24 Mar 2003 18:01:10 -0500

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

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

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

> And the standard security goal for block ciphers is that they be a

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.

---

From: Paul Hoffman / VPNC <[email-masked]>
Date: Tue, 25 Mar 2003 15:14:58 -0800

>(1) you key the prf with Ni|Nr and (2) when authenticating with a

I'm confused by this statement. Where is the preshared key used in 
the SKEYSEED calculation in IKEv2?

--Paul Hoffman, Director
--VPN Consortium

---

From: Hugo Krawczyk <[email-masked]>
Date: Wed, 26 Mar 2003 06:22:35 +0200 (IST)

> the SKEYSEED calculation in IKEv2?

Preshared key is NOT used in the calculation of SKEYSEED.
Sorry if my text gave the wrong impression.

The only thing we need to make sure is that the ikev2 document will
mandate a minimal length for the nonces Ni and Nr (each has to be at least
of half the length of the prf), and a minimal size of the preshared key
(which has to be at least of the length of the prf key).

There is no reason that an implementation will not be able to meet these
requirements. The only case in which this may happen is if someone tries
to use a password as a preshared key. But that should be seen as a
vioaltion of the purpose of pre-shared key mode. Especially in view that
ikev2 explicitly supports password-based authentication methods through
its EAP exchange.

Also, now that we are back to "a la carte", one may want to clarify in the
document that in case that ALice (the initiator) offers more than one prf,
she has to send (in message 1) a nonce which is at least of half the
length of the longest-key prf in her offer (for example: if she offers
HMAC-SHA1 and AES-128 then she has to send a nonce of length 80 bits).

Hugo

---

From: Paul Hoffman / VPNC <[email-masked]>
Date: Wed, 26 Mar 2003 07:01:28 -0800

>(which has to be at least of the length of the prf key).

OK, then I'm still confused. Why does the length of the preshared key 
have to be half the length of the prf key? Why are they linked at all?

>to use a password as a preshared key.

Exactly. This is quite common in the real world.

>  But that should be seen as a

If the preshared key is only used for authentication, not key 
strength, it is not a violation of the spec for someone to have weak 
authentication. If using a password instead of a real preshared key 
weakens the key strength, we need to point that out very clearly in 
the text. (But I still don't see where that happens.)

--Paul Hoffman, Director
--VPN Consortium

---

From: Hugo Krawczyk <[email-masked]>
Date: Wed, 26 Mar 2003 19:35:04 +0200 (IST)

see below

> have to be half the length of the prf key? Why are they linked at all?

This time I am not taking responsibility for your confusion :)
I said that the preshared key "has to be at least of the length of the prf
key". ("half" was used for the nonces since we concatenate them for
creating a key to the prf, not for the pre-shared key).

And the reason we need to specify the above for the length of the
preshared key is that we use it as an input to the prf (section 2.15, 
page 26 of ikev2-05)

> Exactly. This is quite common in the real world.

This is a wrong practice that ikev2 should not officially support
(actually it should officially unsuport). 
Using passwords as pre-shared keys might have been forced upon
applications before because ikev1 did not have any other method to support
password-based authentication. IKEv2 does have this method. So whoever
upgrades from ikev1 to ikev2 should also upgrade from low-entropy
pre-shared key to EAO-based exchange (section 2.16 of ikev2-05)

> authentication. 

I do not agree! Breaking authentication is a much easier (and
realistic) way to BREAK the SECRECY property of the protocol than
cryptanalyzing the DH, the PRF or encryption functions.

 > If using a password instead of a real preshared key 

OK. Please ask Charlie to add to the security considerations section the
something like: 

"The strength of the key exchanged via IKEv2 is not stronger (for the sake of
authentication and secrecy) than the strength of the authentication method
used in the protocol.  This is the case for the signature-based
authentication, the pre-shared key authentication, and the EAP methods. 
In particular, applications that use low-entropy keys (such as passwords)
for authentication should use one of the EAP methods, and must not use the
low-entropy key as a preshared secret. Doing the latter opens the protocol
to dictionary attacks that compromise the strength of authentication and
of the exchanged keys."

Hugo

---

From: Paul Hoffman / VPNC <[email-masked]>
Date: Wed, 26 Mar 2003 10:41:00 -0800

>creating a key to the prf, not for the pre-shared key).

Right.

>preshared key is that we use it as an input to the prf (section 2.15,

It is *part* of the input: it is concatenated with 17 bytes of ASCII 
text. The secret/password doesn't have to be at least the length of 
the prf key, it has to be at least the length of the prf key minus 17 
bytes. If the prf key has to be 128 bits, then the secret/password 
can be of any length, yes? Also, don't all prf functions that we 
allow do padding?

In 2.15, I see the sentence "The pre-shared key SHOULD contain as 
much randomness as the strongest key being negotiated." but I think 
it should say "unpredictability" instead of "randomness".

Of course, we need to warn about the authentication problems with 
using passwords or easily-predictable preshared secrets (such as 
short random strings instead of long random strings), and we should 
explain that they can lead to man-in-the-middle attacks but not 
passive attacks.

>(actually it should officially unsuport).

How are you going to enforce your proposed rule? Each side is 
supposed to somehow deduce that the preshared key that they agreed to 
is not a password? We should not specify rules that cannot be 
enforced by implementations.

>pre-shared key to EAO-based exchange (section 2.16 of ikev2-05)

Yes, they should. And we should encourage them to do so, probably in 
section 2.15. But we cannot force them to.

>cryptanalyzing the DH, the PRF or encryption functions.

This is only true for man-in-the-middle attacks, not passive attacks, 
yes? We need to be clear here.

>used in the protocol.

s/no stronger/no stronger against man-in-the-middle attacks/

>   This is the case for the signature-based

... against man-in-the-middle attacks.

If we are going to say this, we *have* to explain why using passwords 
under EAP is better than using them as preshared secrets. Typical 
implementers will not figure this out and are therefore likely to 
mess it up.

--Paul Hoffman, Director
--VPN Consortium