[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Promoting PRF_AES128_CBC and AUTH_AES_XCBC_96 from SHOULD toSHOULD+

OK. I see now what you mean.
Your phrasing of the question via "pure AES-based prf" confused me.
What you are actually asking is whether the uses of prf in IKE are
"provably secure" on the sole assumption that the prf function is a
pseudorandom function (or, to be more precise, a function randomly chosen
from a family of pseudorandom functions) under the standard definition of 
such functions.

There are two answers to this question: yes and no.

More specifically: the function "prf" in IKE has several uses:

(1) to derive SKEYSEED from the DH value g^ir
(2) to derive further keys (Ka, Kd, Ke, for the IKE-SA and KEYMAT for the
ipsec algorithms) from SKEYSEED
(3) as an integrity algorithm for the IKE-SA (including the essential MAC 
on the signer's identity in the SIGMA design) and for the CHILD-SA.

Uses (2) and (3) (and, in general, the use of prf+) are provably secure
on the sole assumption that prf is a pseudorandom function.

Use (1) is the one you are referrinfg to below, and the answr to it is NO.
That is, if all you assume on prf is that it is a pseudorandom function
then you cannot conclude that SKEYSEED is indistinguishable from random.
Indeed, I can show a family of pseudorandom functions (especially
constructed to serve as a counter-example) under which
SKEYSEED is distinguishable from random. The reason for this, as you note,
is the use of a prf with random but non-secret key. This is a heuristic
use of prf that I introduced for use in IKEv1 and about which I wrote
several times (during the last 6 years) to this list.  

The idea is to use the prf family with random-but-known keys as a universal
hash (UH) family and then to apply the so-called "leftover hash lemma". 
The right (in the sense of provability) design would have been to use an
explicit UH function for this. However, I did not think that the 
introduction of a completely new transform to IKE would have been warmly
welcome (to say the least). Moreover, this is one of the places where I
personally believe that the engineering considerations outweigh the pure
analytic considerations.

Basically, I believe that any reasonable prf family will have enough
statistical strength as to serve as a good replacement for UH for the sake
of "extracting the computational randomness" from a DH key. I can only
wish this to be the "weakest link" in all the cryptography of ike.
Note, btw, that while we need SKEYSEED to be indistinguishable from
random, ,the "distinguishing game" here is far more restricted for the
attacker than in classic uses of prf's: in particular, the attacker 
never gets to see the output SKEYSEED of the prf but (at most) the
output of prf(SKEYSEED,...).

If you want a more academic analytical point of view, then one can phrase
an explicit assumption on the prf family that will ensure the security of
its use in (1). This, with the DDH assumption on the DH group used in IKE,
will give you the required analytical assurance. While these assumptions
on prf do not hold for all pseudorandom families, I expect them to occur
in specific families such as AES (as long, of course, as no new serious
cryptanalytical weaknesses on AES are discovered).

I will not add more here about the technicalities involving these
assumptions since this would get far more technical andacademic than this
list deserves. Moreover, the full analytical details are still "work in
progress" that will hopefully be published in the not-too-far future.

One last thing on this issue: I do not believe (in particular based on the
counter-examples I mentioned above) that one will be able to come with a
use of prf's for "extracting randomness" a la UH which will be based
SOLELY on the pseudorandomness assumption. I will be happy (and surprised)
to see this done.

Finally, regarding the "belt and suspenders" approach you mention below,
there is a simple way to realize it in ike: when deriving SKEYSEED, 
XOR to the result of the prf the n upper bits of the DH value (n being
the output length of prf). If these DH bits are distributed uniformly 
(as more or less expected via DDH) then you have "provable security".
I have not suggested that in the past since it seems to me really
unnecessary (moreover, since the DH value is not really uniformly
distributed in the strings of length |p| then even if DDH holds this is
not a purely provable condition).  BTW, note that in ike's standarized DH
groups the DDH assumption does NOT hold, since the generator is NOT of
prime order. There is more to be said about this but again this is not the
right technical forum for it.


PS: Your feelings (expressed below) that using SHA1 directly or HMAC make
the use of the prf in ike better justified is, in my opinion, incorrect.
All the above reservations on the analytical strength of this use apply
equaly to these other functions (not just to block ciphers). In
particular, it is NOT the case that in SHA1 or HMAC the positioning of the
key vs input is immaterial (not even if you assume the compression
functions to behave as idealized "random oracles"). In some sense the main
contribution of HMAC is in telling you how to position these bits to get
provable guarantees.

On Mon, 9 Jun 2003, Uri Blumenthal wrote:

> Hugo Krawczyk wrote:
>  >>> I see no need for further I-D's. As I said in a recent message all
>  >>> is needed is a pointer to the AES-XCBC-MAC draft for the definition
>  >>> of what ikev2 calls PRF_AES128_CBC. All other issues regarding the
>  >>> use of prf are taken care by the ikev2 draft itself.
>  >>
>  >> Respectfully disagree.
>  >
>  > care to explain?
> Of course.
> First - a fundamental question. The draft (page 26, section 2.14) uses
> Ni | Nr as a key to PRF, and g^ir as data. I understand that for an
> essentially keyless function like SHA1 (and HMAC) it doesn't really
> matter in what sequence to grok the inputs. However when you use a
> keyed algorithm (such as AES), then doesn't it matter what data
> (and of what randomness and secrecy) you use as a key, and
> what - as a plaintext to crunch?
> Second, as far as I know, all the security proofs around block
> ciphers are assuming that the key is secret. If one is using
> AES-XCBC-MAC as PRF, following section 2.14 (page 26), then
> the key is known. What kind of security proofs are you
> getting? How secure is XCBC-MAC with a known key?
> Third, in our public discussion with David Wagner and Ran Canetti,
> David mentioned the "belt and suspenders" approach: a semi-provable
> PRF, based on the assumption that as long as EITHER Decisional
> Diffie-Hellman holds OR hmac behaves as a random oracle - the
> PRF constructed of hmac is secure. What assumptions are
> taken with AES-XCBC-MAC used as PRF?

>  >>> In particular, the draft completely specifies the use of prf's
>  >>> whether with variable length key (such as HMAC-SHA) or fixed
>  >>> length key (such as aes128-cbc).
>  >>
>  >> Except for how to construct a pure AES-based PRF.
>  >
>  > what do you mean by "pure AES-based PRF"? Isnt AES-XCBC
>  > a pure AES-based prf?
> In my understanding, it is "pure AES-based", but under the
> assumptions I see in the draft - not necessarily a PRF due
> to its key being publicly known.
> Uri.