Subject: RE: Promoting PRF_AES128_CBC and AUTH_AES_XCBC_96 from SHOULD to SHOULD+

From: David Blaker <[email-masked]>
Date: Wed, 4 Jun 2003 12:47:57 -0400

Although I have seen discussions of using AES for a PRF function on 
the IPSec mailing list, I am unaware of a formal definition that is 
documented in a draft. draft-ietf-ipsec-ciph-aes-cbs-05.txt makes no 
mention of a prf function, as far as I can tell. If PRF_AES128_CBC
is to be either a SHOULD or a SHOULD+, then someone first needs to
define it somewhere. Would one of the proposers of this algorithm please
provide a draft?

David Blaker, VP System Engineering
CyberGuard Corporation

-----Original Message-----
From: Paul Hoffman / VPNC [mailto:[email-masked]]
Sent: Tuesday, June 03, 2003 7:35 PM
To: [email-masked]
Subject: Promoting PRF_AES128_CBC and AUTH_AES_XCBC_96 from SHOULD to
SHOULD+

Greetings again. draft-ietf-ipsec-algorithms lists the following 
pseudo-random functions:

4.1.4. IKEv2 Transform Type 2 Algorithms

Transfer Type 2 Algorithms are pseudo-random functions used to generate
random values when needed.

      Name                 Number Defined In Status
      RESERVED             0
      PRF_HMAC_MD5         1          [RFC2104]    MAY
      PRF_HMAC_SHA1        2          [RFC2104]    MUST
      PRF_HMAC_TIGER       3          [RFC2104]    MAY
      PRF_AES128_CBC       4          [CIPH-AES] SHOULD

It lists the following for integrity algorithms:

4.1.5. IKEv2 Transform Type 3 Algorithms

Transfer Type 3 Algorithms are Integrity algorithms used to protect
data against tampering.

       Name                  Number     Defined In       Status
       NONE                  0
       AUTH_HMAC_MD5_96      1          [RFC2403]        MAY
       AUTH_HMAC_SHA1_96     2          [RFC2404]        MUST
       AUTH_DES_MAC          3                           MAY
       AUTH_KPDK_MD5         4          [RFC1826]        MAY
       AUTH_AES_XCBC_96      5                           SHOULD

Some implementers have said that they would like to use 
PRF_AES128_CBC and AUTH_AES_XCBC_96 when they use AES for encryption 
in constrained hardware. Basically, why implement PRF_HMAC_SHA1 and 
AUTH_HMAC_SHA1_96 when PRF_AES128_CBC is good enough and it will 
clearly take less silicon. I followed this logic when I specified 
PRF_AES128_CBC and AUTH_AES_XCBC_96 in the VPN-2 UI suite.

I propose that PRF_AES128_CBC be listed as SHOULD+ instead of SHOULD 
so that implementers know that they should be implementing it soon. 
Otherwise, I should change the VPN-2 UI suite to use PRF_HMAC_SHA1 
and AUTH_HMAC_SHA1_96.

Does anyone object to raising these two uses of AES to SHOULD+?

--Paul Hoffman, Director
--VPN Consortium

---

From: "Theodore Ts'o" <[email-masked]>
Date: Fri, 6 Jun 2003 15:52:03 -0400

> define it somewhere. Would one of the proposers of this algorithm please

Good catch.  It appears that ikev2-algorithms-01 is in error:
PRF_AES128_CBC is not defined in draft-ietf-ipsec-aes-cbc-05, and I
don't see any drafts where it is defined.  So we need to modify
ikev2-algorithms to point at a (currently non-existent) I-D, and we
need to find a volunteer to quickly gin up an I-D which defines
PRF_AES128_CBC.

Barbara and I believe that this shouldn't hold up the IETF last call
for draft-ietf-ipsec-algorithms, since writing up this PRF AES I-D
should be something that can be done quickly, however, with the
dangling reference the algorithms document will stall when it hits the
RFC editor, so we will need to plug this reference quickly.

					- Ted

---

From: Hugo Krawczyk <[email-masked]>
Date: Sat, 7 Jun 2003 02:40:27 +0300 (IDT)

> need to find a volunteer to quickly gin up an I-D which defines

that's easy: the right document to point out is
draft-ietf-ipsec-ciph-aes-xcbc-mac-04.txt.

The function defined there is exactly what the algorithms I-D calls
PRF_AES128_CBC (maybe we should rename it to PRF_AES128_XCBC),
except that draft-ietf-ipsec-ciph-aes-xcbc-mac-04.txt mandates the
truncation to 96 bits which is not necessary (nor recommended) here.
Thus one can define PRF_AES128_XCBC by referring to the above I-D and
saying that no truncation takes place (all the 128 bits of output 
from AES128 are output by the prf).
This means ignoring the  text in draft-ietf-ipsec-ciph-aes-xcbc-mac-04.txt
after sec 4.2.

It would be nice if draft-ietf-ipsec-ciph-aes-xcbc-mac-04.txt is
reorganized a bit such as first aes-xcbc-mac is defined with output 
equal to the block length (does this draft refer only to aes128?)
Then a section about truncation is added where aes-xcbc-mac-96 is defined.
A couple of test cases for aes-xcbc-mac could be added.
In this way ikev2 could cleanly refer to aes-xcbc-mac as defined in
draft-ietf-ipsec-ciph-aes-xcbc-mac-04.txt.

Hugo

---

From: Uri Blumenthal <[email-masked]>
Date: Fri, 06 Jun 2003 18:01:46 -0400

I'd volunteer, since I've been working on the thing (on and off)
for a while now. But as the discussion demonstrated, it's not as
simple - if you want to use that PRF in IKEv2.

---

From: Hugo Krawczyk <[email-masked]>
Date: Tue, 10 Jun 2003 01:16:47 +0300 (IDT)

> simple - if you want to use that PRF in IKEv2.

Uri, 

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. 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). The only prf's that
are defined as MUST NOT USE are those whose output is shorter than the key
itself (such as 3DES). All other discussions regarding prf use in ikev2
were resolved and reflected in the ikev2 draft.

Hugo

---

From: Hugo Krawczyk <[email-masked]>
Date: Tue, 10 Jun 2003 02:20:33 +0300 (IDT)

On Mon, 9 Jun 2003, Uri Blumenthal wrote:

> Hugo Krawczyk wrote:
> > taken care by the ikev2 draft itself.
> 
> Respectfully disagree.

care to explain?

> 
>  > In particular, the draft completely
> > 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?

Hugo

---

From: Hugo Krawczyk <[email-masked]>
Date: Tue, 10 Jun 2003 19:45:33 +0300 (IDT)

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.

Hugo

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

---

From: Uri Blumenthal <[email-masked]>
Date: Mon, 09 Jun 2003 18:54:06 -0400

Respectfully disagree.

I understand that HMAC is good, but for some application is may
be preferred to stay within one algorithm (AES).

---

From: Uri Blumenthal <[email-masked]>
Date: Mon, 09 Jun 2003 21:37:12 -0400

Of course.

Uri.

---

From: Paul Hoffman / VPNC <[email-masked]>
Date: Tue, 17 Jun 2003 12:35:33 -0700

>were resolved and reflected in the ikev2 draft.

Based on the fact that the AES-XCBC-MAC-96 draft is in the RFC 
Editor's queue and therefore cannot be changed, I wrote a very short 
Internet Draft embodying what Hugo said here. It is available at 
<http://www.ietf.org/internet-drafts/draft-hoffman-ipsec-aes-prf-00.txt>.

Assuming Hugo agrees that this matches his intent above, would the WG 
chairs please add this as a WG item as soon as possible so that 
Jeff's document and my document can point to it?

--Paul Hoffman, Director
--VPN Consortium