Subject: Changing the key deriveration

From: "Theodore Ts'o" <[email-masked]>
Date: Fri, 13 Feb 2004 01:18:09 -0500

In a recent message, Steve Kent made the following statement:

>When I last spoke with Russ, he indicated that he was prepared to
>tolerate another delay on the IKE v2 document to incorporate the
>change that Hugo suggested, to incorporate bits from an key-based EAP
>method into the PRF for the keys used for encryption & integrity.

This presumably is referring to Hugo's proposal of January 13th, which
I've included below.  On a recent concall of the IPSEC management team,
we discussed on how to handle this, given that (a) there has been no
response or discussion to Hugo's proposal on the mailing list to date,
and (b) a number of us get hives with the thought of making changes to
something as critical as IKEv2's cryptographic core at the last minute
without some adequate and thoughtful review.

So we propose the following path forward.  First, that we ask the Hugo
to clarify his objection.  It appears to be mainly a certificational
weakness in that it may make it harder to prove correctness at least
when using normal crypto algorithms.  Is this a fair characterization,
or is there a fundamental problem in normal usage?

Secondly, we'd like to ask the Crypto Forum Research Group in the IRTF,
whose charter it is to provide a resource to IETF working group to
review uses of cryptographic mechanisms if they might be willing to give
us review of the current key agreement mechanisms found in sections
2.14, 2.15, and 2.16 of draft-ietf-ipsec-ikev2-12.txt as well as the
proposed change by Hugo.  Ran and David: Is this a good use of the CFRG,
and would you be willing to ask them to engage in this review?

Based on the answers from Hugo and the CFRG, the working group will
hopefully have sufficient information in order to quickly come to
consensus about whether we need to make any changes to ikev2-12.

Does this seem a reasonable way forward?  I don't want to unduly prolong
an already very long process, but it seems to us that it is better to
put examine this issue and put it to rest now, instead of waiting until
Russ finishes reviewing the document (it is in his queue) and starts
IETF last call.  

					- Ted

------------------

Date: Tue, 13 Jan 2004 22:10:50 +0200 (IST)
From: Hugo Krawczyk <[email-masked]>
Subject: Keing the prf
To: Theodore Ts'o <[email-masked]>
cc: Russ Housley <[email-masked]>, [email-masked],
        Charlie Kaufman <[email-masked]>,
        IPsec WG <[email-masked]>

There is one issue that was subject of discussion in the last weeks and I
believe requires a better resolution. I refer to the problem that ikev2
(including -12) defines two uses of the prf function (in sections 2.15 and
2.16)  where the prf is keyed with SK_a. This is problematic since SK_a is
defined as a key to the "integrity algorithm" which may be different than
the prf. Indeed the integrity algorithm and prf have different transform
types (#3 and #2) respectively, and then are negotiated independetly (in
particular they may use different algorihms).

Why is this a problem?

First, because the two transforms may require keys of different lengths,
in particular SK_a may be too short to key the prf.

Second, it is a wrong cryptographic practice to use the same key with two
different algorithms. This may or may not translate into actual attacks,
but it certainly spoils the otherwise sound design of the protocol.
It will also invite "attacks" from future formal analysts (beyond the
operational issues referred to in the first item).

I believe that the problem is best solved by deriving an additional pair
of keys from SKEYSEED (call them SK_pi and SK_pr) for keying the prf in the
above two cases. It is certainly easy to specify and to implement
(and easier than to justify why this wasn't done).

Specifically add the pair SK_pi, SK_pr to the key derivation formula in
2.14. Change prf(SK_ar,IDr') to prf(SK_pr,IDr') and prf(SK_ai,IDr') to
prf(SK_pi,IDr') in section 2.15. Change "SK_ai and SK_ar" in the next to
last paragraph of section 2.16 with "SK_pi and SK_pr"

I suggest that this be solved before the official last call (otherwise you
can see this as a comment provided in the last call phase).

Hugo

---

From: Stephen Kent <[email-masked]>
Date: Fri, 13 Feb 2004 13:11:47 -0500

Ted,

I think this is a good proposal on how to proceed.

Steve

---

From: Hugo Krawczyk <[email-masked]>
Date: Sat, 14 Feb 2004 03:21:00 +0200 (IST)

This msg is being sent to both ipsec and cfrg (apologies for all those --
like me -- that will get this by duplicate)

Some background (for the cfrg audience): In a msg from earlier today
(appended below) to the ipsec WG and cfrg chairs (David and Ran),
Ted Tso (IPsec WG chair) proposed to bring up before the cfrg forum a
crypto design issue in ikev2 that was raised over the ipsec list.
I recommend that you read Ted's note. David (McGrew)  answered that I
should send this note to cfrg with an explanation of the issues.
So this is what I am doing.

"Executive summary:" ikev2 currently specifies the use of two different
algorithms (or "transforms") with the same key. The IPsec chairs ask the
cfrg to provide expert opinion on the need to change this specification
(as I propose below).

Now, a page long expansion of this summary for those who want more
details.

But before, let me say that I am really glad to see that this issue is
being brought to the attention of the cfrg. I hope this is the first of an
eventually long tradition of using this forum for validating (or
de-validating) cryptographic designs needed/proposed/used by other WGs in
the ietf.

Specifically, Ted refers to a point I raised, in a msg to the ipsec list
from Jan 13th, regarding a specification issue in ikev2. That msg is
appended at the end of Ted's note (below). I consider the problem a
no-brainer but the fact that it was not immediately accepted as an obvious
and easy fix requires some explanation. Here is a succint statement of the
problem.

The current IKEv2 draft (ready for last call
draft-ietf-ipsec-ikev2-12.txt)  specifies the use of two DIFFERENT
transforms, prf and integrity-algorithm, but also specifies
keying them with the SAME key!
The prf is used for key derivation as well as for the "mac" that the SIGMA
design (SIGn-and-MAc) requires and for an additional mac in ikev2's
password-based (or EAP-based) protocol.
The second transform, the integrity-algorithm, is used for integrity
purposes and is always computed on top of encrypted data (ciphertext); its
functionality is to provide authenticated encryption (and CCA security).

The obvious fix to this problem is to derive different keys for the
different algorithms. Fortunately, this is easy in ikev2 which has a very
modular key derivation procedure. All is needed is to derive two more keys
(in addition to the 5 derived now) which will be used to key the prf (two
keys to be consistent with "uni-directionality" of other keys in ikev2).
This frees the already specified "authentication keys" (SK_ai and SK_ar)
for exclusive use by the integrity algorithm.

I am sure that I do not need to explain to the cfrg-fans the dangers of
the (fundamentally wrong) practice of using the same key for two different
algorithms. Nor do I think that the ipsec audience will disagree with that
either. So the only question is whether there is any real cost associated
with the proposed change.  In this case, however, there is zero cost. No
real specification or implementation complexity. No performance issue at
all.  No delay in advancing the document (a two-minute change to the
draft).  And no damage to implementations of ikev2 running in the
marketplace since there are none (certainly not "standard-compliant" ones
as this standard is not finalized). Finally, other solutions (such as
unifying the prf and mac into a single transform) have more drawbacks than
the trivial solutions of extracting two more keys in the key derivation
process (currently there are 5 keys derived by this process).

I do buy, however, Ted's argument that making last minute changes,
especially to the cryptography is dangerous. This is why I welcome this
request for advise from the cfrg.  For those that follow the ipsec
discussions there is enough material in that list about the issue.
And for those that do not follow ipsec, then the problem does not require
more description than what I wrote above (and further described in the
appended message).

In any case, just to make the point clear let me re-re-iterate the issue
with some more detail:

(1) The "integrity algorithm" and "prf" are different transforms in ikev2
(see section 3.3 of ikev2), and as such they are negotiated separately and
therefore may be set to different algorithms.

(2) In two applications of the prf function in ikev2 (sections 2.14 and
2.16) the prf function is keyed with a key (called SK_a) that is defined
as a key to the integrity algorithm, not to the prf algorithm.

(3) I propose that in addition to the 5 keys currently derived by the
protocol (see  sec 2.14), namely SK_d,SK_ai,SK_ar,SK_ei,SK_er, two more keys
will be derived (called SK_pi,SK_pr) that will be used exclusively to key
the prf in the above two applications.

Let me also add: not only is the use of different algorithms with the same
key an obvious cryptographic flaw, but also raises an operational issue
since the keys required by the integrity and prf algorithms may have
different size.

FOR those who care: If all you have to say is that the need for this
change is OBVIOUS, it may still be worth saying it (over the list).

Hugo

On Fri, 13 Feb 2004, Theodore Ts'o wrote:

> I've included below.On a recent concall of the IPSEC management team,
> So we propose the following path forward.First, that we ask the Hugo
> to clarify his objection.It appears to be mainly a certificational
> when using normal crypto algorithms.Is this a fair characterization,
> proposed change by Hugo.Ran and David: Is this a good use of the CFRG,
> Does this seem a reasonable way forward?I don't want to unduly prolong
> 2.16)where the prf is keyed with SK_a. This is problematic since SK_a is
> particular they may usedifferent algorihms).
>
> Why is this a problem?
>

---

From: "The Purple Streak, Hilarie Orman" <[email-masked]>
Date: Mon, 16 Feb 2004 13:18:30 -0700

On Sat, 14 Feb 2004 at 03:21:00 +0200 (IST) Hugo Krawczyk
commented:

> In this case, however, there is zero cost. No
> draft). 

I've spent more than 15 minutes trying to find out exactly where the
objectionable material resides.  Previous messages have referred to
sections 2.14, 2.15, and 2.16.  In draft-ietf-ipsec-ikev2-12.txt, the
only case of the cross-algorithm keying seems to be in section 2.15,
"Authentication of the IKE_SA", first paragraph.

In defense of the mechanism, we see that the value never appears on
the wire.  It's unlikely to create any problems.

Against it, we see that (as Greg Rose pointed out), the key was
created for one algorithm and might not have enough entropy to be used
safely for another.  And, as Hugo points out, it is needlessly
unclean.  In fact, wouldn't it be better to use SK_d for the purpose of
generating the not-on-the-wire authenticating value?  This would avoid
having to generate two additional keys --- given that the additional
keys would be generated with the prf and SK_d anyway, the security
analysis seems a toss-up.

I don't see any misuse of keys in section 2.16, "Extended
Authentication Protocol Methods", though it might be implicit in a
formula and I'm just not seeing it.

Hilarie

---

From: Hugo Krawczyk <[email-masked]>
Date: Tue, 17 Feb 2004 21:57:13 +0200 (IST)

On Mon, 16 Feb 2004, The Purple Streak, Hilarie Orman wrote:

> the wire.It's unlikely to create any problems.
>
> Against it, we see that (asGreg Rose pointed out), the key was
> safely for another.And, as Hugo points out, it is needlessly
> unclean.In fact, wouldn't it be better to use SK_d for the purpose of
> generating the not-on-the-wire authenticating value?This would avoid

I cannot blame you.  The usage of prf with SK_a is "hidden" in section
2.16 under the following text:

   If EAP methods that do not generate a
   shared key are used, the AUTH payloads in messages 5 and 6 MUST be
   generated using SK_ai and SK_ar respectively.

Now, the AUTH payload with a shared key (which is the case here) is
defined in Section 2.15 as
AUTH = prf(prf(Shared Secret,"Key Pad for IKEv2"), <message octets>)

Thus combining the above two definitions we get the use of prf(SK_a,...)
in section 2.16.

I hope it is crystal clear now, isn't it? :)

Anyway, replacing SK_ai and SK_ar in the above text (as well as in 2.15,
first paragraph) with SK_d does resolve the problem of using two
algorithms (prf and integrity) with the same key, and it is much better
than what is done now.

I would still prefer the cleaner (from the point of view of design and
analysis) solution that uses different keys for two essentially different
applications of the prf function (as key derivation and as MAC), and I
also prefer to use "directional keys" (i.e. SK_pi and SK_pr).
(The latter may not be essential here but makes the defense against
reflection attacks simpler to argue.)
Yet, Hilarie's suggestion may be an acceptable "compromise" for those
who feel that deriving two more keys is too onerous.

Hugo

---

From: Paul Hoffman / VPNC <[email-masked]>
Date: Fri, 20 Feb 2004 18:09:58 -0800

>algorithms (prf and integrity) with the same key, and it is much better

There have been no more comments on this, and the ADs are still 
waiting for a final draft of this document so they can move all three 
IKEv2 documents to IETF last call.

Charlie: are you OK with this solution? If so, can you get the new 
draft out soon, such as when the Internet Drafts window opens?

--Paul Hoffman, Director
--VPN Consortium

---

From: canetti <[email-masked]>
Date: Mon, 23 Feb 2004 19:18:47 -0500 (EST)

Sorry for the delayed reaction. Let me try to be concise:

1. I strongly support the move to change the spec. Using the same key to
two different algorithms is a big "no no" that, on top of other drawbacks,
does not allow mathematical proofs of security to go through.
(Not being amenable to analysis is a considerable *practical* weakness, 
even if do not see how to turn the weakness into an explicit attack...)

2. Both the solution suggested by Hugo (to derive two more keys from SEEDKEY,
to be used for the PRF by the sender/responder, respectively), and the
solution suggested by Hilarie (to use SK_d, the key meant for deriving the
IPSEC keying material as the key to the PRF) are in principle sound.
However, Hugo's solution seems somewhat more robust: It seems preferable to
keep the ``virginity'' of the derivation key, SK_d, and refrain from using
it inside the protocol. This feeling is compounded by the fact that in the
password-based authentication mode the PRF is applied to messages of a generic 
password-based protocol, so the door may be open to "oracle attacks" that 
use the parties to obtain values of PRF(SK_d,...) on desired values.

So, in conclusion, if we're already changing the spec for better
analyzability/provability, then I think we should play it safe and 
derive two extra keys from SEEDKEY, rather than use SK_d.
(The difference in performance and complexity between the two options
seems minimal.)

Ran

On Fri, 20 Feb 2004, Paul Hoffman / VPNC wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/cfrg
>

---

From: "Theodore Ts'o" <[email-masked]>
Date: Tue, 24 Feb 2004 11:50:35 -0500

> IKEv2 documents to IETF last call.

David and Ran --- is the CFRG currently working on some kind of
official statement that represents the consensus of the group, or
should we use the comments made by CFRG members in our deliberations?
If the former, could you give us a timeline when the official comments
from the CFRG can be expected?  If the latter, please accept the
thanks of the IPSEC working group to those members who took the time
to evaluate Hugo's proposal.

						- Ted

---

From: "David A. McGrew" <[email-masked]>
Date: Tue, 24 Feb 2004 15:24:37 -0500

Ted,

I'll try to wrap up the discussion and move on a summary that we can 
agree on, in a separate mail.

David