Subject: Re: [Cfrg] Re: Changing the key deriveration
From: Greg Rose <[email-masked]>
To: Hugo Krawczyk <[email-masked]>
Cc: "Theodore Ts'o" <[email-masked]>, IPsec WG <[email-masked]>, <[email-masked]>, <[email-masked]>, Ran Canetti <[email-masked]>
Date: Sat, 14 Feb 2004 13:32:23 +1100
List-Id: Crypto Forum Research Group <cfrg.ietf.org>

FWIW, I strongly agree that the change should be made. Three reasons:

In 3GPP2 (CDMA2000 mobile phones) we have adopted as a working principal 
that no key should be used in two ways. This has been a rule of thumb for a 
long time now. It is just good practise.

That the primitives might accept keys of different lengths should also 
instantly raise flags. Suppose they are of (different) lengths A and B, 
where wlog we assume A>B. Then either A's key must be padded from B's, in 
which case it has less entropy than A would imply, or B's must be truncated 
from A's. But this means that A's key can be attacked (classic 
divide-and-conquer) by brute-forcing B's, then brute forcing (the rest of) 
A's. So instead of having strength O(2^A), it now only has strength 
O(2^(max(B, A-B)). In other words, in both cases, you've reduced the 
strength of both primitives to that of the weaker.

Thirdly, any provability of security of the overall system almost certainly 
includes an assumption of independence of the cryptographic transforms. If 
they have the same keys, such an assumption might still be true in the real 
world, but a priori you just can't rely on it.

Hope that helps...
Greg.

At 03:21 AM 2/14/2004 +0200, Hugo Krawczyk wrote:
>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:
>
> >
> > 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 usedifferent 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
> >
>
>
>
>
>_______________________________________________
>Cfrg mailing list
>[email-masked]
>https://www1.ietf.org/mailman/listinfo/cfrg

Greg Rose                                       INTERNET: [email-masked]
Qualcomm Australia          VOICE:  +61-2-9817 4188   FAX: +61-2-9817 5199
Level 3, 230 Victoria Road,                http://people.qualcomm.com/ggr/
Gladesville NSW 2111    232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C

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