Subject: Re: [MSEC] Session ID and Group ID

From: Adrian Perrig <[email-masked]>
Date: Sun, 01 Apr 2001 21:47:15 -0700

Hi Lakshminath,

> About revision (and it needs a version number to go with it) numbering,
> as I explained earlier in another message, we can use it and not
> send a new SA/SPI/notification during join rekeying in LKH+ and similar
> algorithms.

This is interesting. If I correctly understand, the proposal is to
compute a one-way function on all keys that the new member receives,
right? However, this approach still requires to send out
version/revision numbers of keys, so that the receivers know which
keys need to be updated.

We recently worked on a new key distribution protocol which took a
more drastic approach: We update all the keys in the entire key tree
in each time interval. This approach trades off computation with
communication. It does not require sending any information to anybody,
since all group members update the key tree independently. We assume
that the key server can update the key tree efficiently with a fast
one-way function.

The main focus of our work, however, was to provide reliability for
key updates without using underlying reliable multicast protocols. We
present a number of mechanisms. In case you're interested, a summary
of the paper is available at:
http://www.perrig.net/projects/elk/elksummary.html

We will present the paper at this year's Oakland conference. The paper
is available at:
http://www.perrig.net/projects/elk/elk.ps

Greetings,
  Adrian

_______________________________________________
msec mailing list
[email-masked]
http://www.pairlist.net/mailman/listinfo/msec

---

From: Mark Baugher <[email-masked]>
Date: Mon, 02 Apr 2001 05:57:07 -0800

Hi Thomas

At 10:18 AM 3/31/2001 -0500, Thomas Hardjono wrote:

>i think we did agree somewhere along the line that a draft(s) is needed
>to cover the "group key determination algorithms",
>which is my formal way of saying lkh, oft, ofc, etc. (ie. key trees
>in general).
>
>are we limited to simply providing a variable-length payload
>for a flattened key-tree, or is there sufficient similarity
>among the algorithms that we can provide a finer granularity
>standard payload?
>
>also, is there a "standard" that describes how (say) the lkh algorithm
>works (in the same way that there is, say, a des standard document)?
>i know lkh isn't an algorithms in the sense of des, but really
>a standard is this sense is just a step-by-step description of
>how to manipulate the bits (be they keys or data).

I think that we need to have 1 specification for every n implementations.
The implementations will be specific to the protocol framework.
GSAKMP already has LKH+ specified - it's more of a complete system
than a single protocol.  For GDOI, we need to have an LKH
specification.  GDOI is useful without LKH, OFT, AMESP,
and TESLA, but it needs them to offer a complete specification for
a wide variety of application environments.  So for GDOI, I'd like
to see separate specifications for each membership management
algorithm of interest.

Mark

>thomas
>------
>
>
>at 3/31/01||03:53 am, mark baugher wrote:
>>hi lakshminath
>>    i think that we need to have a separate draft document
>>that describes how an lkh security protocol should
>>operate.  what we have in the gdoi draft is our first
>>take on what the security-association traffic encryption key
>>(sa tek) payload needs to be to support an lkh security
>>protocol.  i would not be surprised if we need to change
>>this by the time we finish an lkh security protocol
>>document.  it hope that the security association key
>>encrypting key (sa kek) won't need any changes -
>>if we find that we need to change sa kek for new
>>security protocols, then there's something wrong.  the
>>sa kek needs to be general wrt security protocols.
>>
>>best regards, mark
>>at 01:52 pm 3/30/2001 -0500, lakshminath dondeti wrote:
>>>mark,
>>>
>>>thanks for the explanation.  it makes sense.  i am looking for
>>>opinions on incorporating version and revision numbers with
>>>keys.  particularly in case of lkh+ and similar key determination
>>>algorithms it makes life easy.  for example, in lkh+, when a join
>>>occurs, the gcks need not even notify current membership.  when
>>>data comes with a new "revision number", the members "update" the
>>>corresponding sa appropriately.
>>>
>>>i am bringing this up so we can discuss and decide whether it is
>>>worthwhile to add this to gdoi i-d key payloads.
>>>
>>>best regards,
>>>lakshminath
>>>
>>>ps:  i want to reiterate the disclaimer that this was an idea proposed
>>>in the literature (not by me, see below).
>>>
>>>
>>>mark baugher wrote:
>>> >
>>> > lakshminath,
>>> >
>>> > at 06:20 pm 3/29/2001 -0500, lakshminath dondeti wrote:
>>> > >brian,
>>> > >
>>> > >i am not getting into this sid discussion at this time.
>>> > >
>>> > >but, i am concerned about having a single "active" tek.  i believe
>>> > >in reality a member needs to maintain a list of teks.  consider
>>> > >data going over a reliable multicast channel.  it is plausible
>>> > >that a member receives two (e.g.) versions of teks before she
>>> > >receives any encrypted data.  when the data eventually arrives,
>>> > >the first few packets could be encrypted with tek 1.0 and the rest
>>> > >with tek 2.0, or vice versa.
>>> >
>>> > we use an spi for this purpose.
>>> >
>>> > mark
>>> >
>>> > >i propose that both key and data packets should have "version" and
>>> > >"revision" tags.  the terminology and idea comes from the versakey
>>> > >paper in jsac 1999/2000 by m. waldvogel, g. caronni, b. plattner and
>>> > >others.  as i recall each time a new key is generated, the version
>>> > >number is increased, and when a one-way function is used on the current
>>> > >tek/kek for rekeying (ala lkh+), the revision number is increased.
>>> > >
>>> > >
>>> > >
>>> > >best regards,
>>> > >lakshminath
>>> > >
>>> > >brian weis wrote:
>>> > > >
>>> > > > hi thomas,
>>> > > >
>>> > > > thomas hardjono wrote:
>>> > > > >
>>> > > > > recently we had a discussion with some folks who wanted to
>>> > > > > do group key management in wireless, and a number of questions 
>>> arose
>>> > > > > regarding the gsa model and definition, and in particular
>>> > > > > about the notion of group ids (gid).
>>> > > > >
>>> > > > > so we all know that we need some way to identify a group
>>> > > > > other than using the (s, g) pair.  gsakmp uses the notion
>>> > > > > of a group id (gid) which can identify a group a high level
>>> > > > > and which is included in all the gsakmp messages/headers.
>>> > > > > in gsakmp the gid is a 32-bit number (though i think we may
>>> > > > > need a bigger number).
>>> > > > >
>>> > > > > this notion of a gid is also being carried-over into the gdoi work
>>> > > > > (at least implicitly).
>>> > > > >
>>> > > > > so here is the scenario:  there is one control channel (cat-2)
>>> > > > > and there is multiple data channel (cat-3), say one for audio and
>>> > > > > one for video.
>>> > > > >
>>> > > > > the question is, if i was a receiver and was in the process of
>>> > > > > receiving a key-update (rekey pack) through the push/control sa,
>>> > > > > how do i identify which key-packs are to be applied to the
>>> > > > > 2 data channels?  in gdoi the update will consist of 2 kek sas,
>>> > > > > but the question still arises: how do i know how to match the keks
>>> > > > > to the multiple cat-3 sas.
>>> > > >
>>> > > > i followed you up until the last paragraph. in the scenario you 
>>> mention,
>>> > > > there could be one kek sa (not two as you say in this paragraph), and
>>> > > > two tek sas. maybe you meant that the "update will consist of 2 tek
>>> > > > sas"?
>>> > > >
>>> > > > in gdoi, the push message includes an sa payload containing the 
>>> policy
>>> > > > for the two data channels, and the kd payload contains the new 
>>> keys for
>>> > > > the two channels. the sa payload identifies the (s,g) of the data
>>> > > > channel along with a new spi (assuming ipsec encapsulation). the kd
>>> > > > payload includes the new spi and the new key. it will be obvious 
>>> which
>>> > > > key is associated with which data channel.
>>> > > >
>>> > > > or, if you really considering confusion between the two keks, the 
>>> only
>>> > > > confusion between would be between the current kek and a new one sent
>>> > > > down in the push message.
>>> > > > however, the new one replaces the current kek after the push message
>>> > > > processing has completed -- only one should be active at a time per
>>> > > > group.
>>> > > >
>>> > > > > one answer is using a session-id (sid) in conjunction with the gid.
>>> > > > > thus, each kek and tek would need to identify the gid & sid
>>> > > > > to which the kek/tek applies.
>>> > > >
>>> > > > the gdoi, there is already a unique value associated with each 
>>> kek. the
>>> > > > cookie-pair in the ike header is used as the "spi" for the kek. 
>>> if a new
>>> > > > kek is sent in a push message, the sa payload sends a new cookie-pair
>>> > > > for the new kek.
>>> > > >
>>> > > > i don't see where a sid is needed for either a tek or kek.
>>> > > >
>>> > > > brian weis
>>> > > > [email-masked]
>>> > > >
>>> > > > > would it be possible, say, to have a 32-bit gid and a 32-bit sid,
>>> > > > > (assuming that 32-bits of gid is enough)?  if a 32-bit gid is 
>>> too much,
>>> > > > > perhaps we can re-use some of the bits (least significant 8 bit)
>>> > > > > for the sid?
>>> > > > >
>>> > > > > does this whole sid thing make any sense?
>>> > > > >
>>> > > > > thomas
>>> > > > > ------
>>> > > > >

---

From: "Lakshminath Dondeti" <[email-masked]>
Date: Mon, 02 Apr 2001 10:56:22 -0400

Adrian,

> version/revision numbers of keys, so that the receivers know which

This proposal was published 1-3 years ago in WetICE and JSAC (not by
me).  Actually the GCKS does not need to send the version/revision
numbers to 
all members.  Only the sender(s) need(s) to know this.  It then simply 
uses the version/revision number in the headers while sending future 
data.  In case of the GDOI protocol, this translates to a unicast
"notification" as opposed to a multicast notification to the group.
(Disclaimer:  There is no provision for these notifications currently,
in the GDOI I-D.)

All that during join rekeying only. :-)

I will read your paper.  It sounds interesting!

best regards,
Lakshminath

---

From: "Lakshminath Dondeti" <[email-masked]>
Date: Mon, 02 Apr 2001 11:48:39 -0400

Mark,

Thanks much for your comments.  We probably do need a separate
document for the logical key tree mechanisms.  The stuff I was
proposing is an addition to the GDOI protocol.  They were, in
more abstract terms,

  1) notification messages: unicast/multicast (to support LKH+
and similar mechanisms)
  2) version/revision numbers in data messages (again I made the
case in context of LKH+, but this would apply to OFT+ and any
others, may be future ones.)

You are right, we'll know more once a common framework document 
for tree-based rekeying schemes, as Ran proposed, materializes.

Best regards,
Lakshminath

Mark Baugher wrote:
> 
> hi Lakshminath
>     I think that we need to have a separate draft document
> that describes how an LKH security protocol should
> operate.  What we have in the GDOI draft is our first
> take on what the Security-Association traffic encryption key
> (SA TEK) payload needs to be to support an LKH security
> protocol.  I would not be surprised if we need to change
> this by the time we finish an LKH security protocol
> document.  It hope that the security association key
> encrypting key (SA KEK) won't need any changes -
> if we find that we need to change SA KEK for new
> security protocols, then there's something wrong.  The
> SA KEK needs to be general wrt security protocols.
> 
> best regards, Mark
> At 01:52 PM 3/30/2001 -0500, Lakshminath Dondeti wrote:
> >Mark,
> >
> >Thanks for the explanation.  It makes sense.  I am looking for
> >keys.  Particularly in case of LKH+ and similar key determination
> >algorithms it makes life easy.  For example, in LKH+, when a join
> >occurs, the GCKS need not even notify current membership.  When
> >corresponding SA appropriately.
> >
> >I am bringing this up so we can discuss and decide whether it is
> >worthwhile to add this to GDOI I-D key payloads.
> >
> >best regards,
> >Lakshminath
> >
> >PS:  I want to reiterate the disclaimer that this was an idea proposed
> >Mark Baugher wrote:
> > > Lakshminath,
> > > At 06:20 PM 3/29/2001 -0500, Lakshminath Dondeti wrote:
> > > >Brian,
> > > >
> > > >I am not getting into this SID discussion at this time.
> > > >
> > > >But, I am concerned about having a single "active" TEK.  I believe
> > > >in reality a member needs to maintain a list of TEKs.  Consider
> > > >data going over a reliable multicast channel.  It is plausible
> > > >that a member receives two (e.g.) versions of TEKs before she
> > > >receives any encrypted data.  When the data eventually arrives,
> > > >the first few packets could be encrypted with TEK 1.0 and the rest
> > > >with TEK 2.0, or vice versa.
> > >
> > > We use an SPI for this purpose.
> > >
> > > Mark
> > >
> > > >I propose that both key and data packets should have "version" and
> > > >"revision" tags.  The terminology and idea comes from the VersaKey
> > > >paper in JSAC 1999/2000 by M. Waldvogel, G. Caronni, B. Plattner and
> > > >others.  As I recall each time a new key is generated, the version
> > > >TEK/KEK for rekeying (ala LKH+), the revision number is increased.
> > > >
> > > >
> > > >
> > > >best regards,
> > > >Lakshminath
> > > >
> > > >Brian Weis wrote:
> > > > >
> > > > > Hi Thomas,
> > > > >
> > > > > Thomas Hardjono wrote:
> > > > > >
> > > > > > Recently we had a discussion with some folks who wanted to
> > > > > > do group key management in wireless, and a number of questions arose
> > > > > > regarding the GSA Model and Definition, and in particular
> > > > > > about the notion of Group IDs (GID).
> > > > > >
> > > > > > So we all know that we need some way to identify a group
> > > > > > other than using the (S, G) pair.  GSAKMP uses the notion
> > > > > > of a Group ID (GID) which can identify a group a high level
> > > > > > and which is included in all the GSAKMP messages/headers.
> > > > > > In GSAKMP the GID is a 32-bit number (though I think we may
> > > > > > need a bigger number).
> > > > > >
> > > > > > This notion of a GID is also being carried-over into the GDOI work
> > > > > > (at least implicitly).
> > > > > >
> > > > > > So here is the scenario:  there is one control channel (Cat-2)
> > > > > > and there is multiple data channel (Cat-3), say one for audio and
> > > > > > one for video.
> > > > > >
> > > > > > The question is, if I was a Receiver and was in the process of
> > > > > > receiving a key-update (rekey pack) through the push/control SA,
> > > > > > how do I identify which key-packs are to be applied to the
> > > > > > 2 data channels?  In GDOI the update will consist of 2 KEK SAs,
> > > > > > but the question still arises: how do I know how to match the KEKs
> > > > > > to the multiple Cat-3 SAs.
> > > > >
> > > > > I followed you up until the last paragraph. In the scenario you
> > mention,
> > > > > there could be one KEK SA (not two as you say in this paragraph), and
> > > > > two TEK SAs. Maybe you meant that the "update will consist of 2 TEK
> > > > > SAs"?
> > > > >
> > > > > In GDOI, the push message includes an SA payload containing the policy
> > > > > for the two data channels, and the KD payload contains the new keys for
> > > > > the two channels. The SA payload identifies the (S,G) of the data
> > > > > channel along with a new SPI (assuming IPSec encapsulation). The KD
> > > > > payload includes the new SPI and the new key. It will be obvious which
> > > > > Or, if you really considering confusion between the two KEKs, the only
> > > > > confusion between would be between the current KEK and a new one sent
> > > > > However, the new one replaces the current KEK after the push message
> > > > > > One answer is using a Session-ID (SID) in conjunction with the GID.
> > > > > > Thus, each KEK and TEK would need to identify the GID & SID
> > > > > > to which the KEK/TEK applies.
> > > > >
> > > > > The GDOI, there is already a unique value associated with each KEK. The
> > > > > cookie-pair in the IKE header is used as the "SPI" for the KEK. If
> > a new
> > > > > KEK is sent in a push message, the SA payload sends a new cookie-pair
> > > > > for the new KEK.
> > > > >
> > > > > I don't see where a SID is needed for either a TEK or KEK.
> > > > >
> > > > > Brian Weis
> > > > > [email-masked]
> > > > >
> > > > > > Would it be possible, say, to have a 32-bit GID and a 32-bit SID,
> > > > > > (assuming that 32-bits of GID is enough)?  If a 32-bit GID is too
> > much,
> > > > > > for the SID?
> > > > > > Does this whole SID thing make any sense?
> > > > > >
> > > > > > thomas
> > > > > > ------
> > > > > >

---

From: Mark Baugher <[email-masked]>
Date: Mon, 02 Apr 2001 10:28:45 -0700

Lakshminath
   What is the benefit of having a common framework for group
membership management?

Mark

---

From: "Lakshminath Dondeti" <[email-masked]>
Date: Mon, 02 Apr 2001 15:28:31 -0400

Mark,

Good question! :-)  Although I am not sure my message below is
proposing a common framework for group membership management.
Let me address both key tree management and group membership
management, to the best of my knowledge :-)

Case for common framework for key tree management:
--------------------------------------------------
As I understand, for join rekeying we can use the "one-way
hash function" technique to cut down on rekeying (communication)
overhead in LKH, OFT(?), and others?  I know of some distributed
key determination schemes that could use this technique.

My guess is that there are other common aspects (similar 
payload formats should help in implementation -- Ran and 
Thomas' opinion/idea) of rekeying mechanisms.  My thinking 
is that the common framework document would glean that 
information.  Out of that, we could figure out what 
needs to be added to the GDOI (or similar) protocol, or
whatever (I am not sure yet).

Group membership management:
----------------------------
The layer-3 thing for this is IGMP.

In our case (may be this was resolved earlier, I am sorry I was not
there), this means a way for the GCKS to get leave "notifications"
from members.  For completeness, SA1 of GDOI is an implicit join
"notification" (request really).  I am sure there will be other
kinds of notifications that will come up (distributed GCKS comes
to mind).

Oh well, that is my stab at that question :-)

best regards,
Lakshminath

---

From: Mark Baugher <[email-masked]>
Date: Tue, 03 Apr 2001 09:43:59 -0700

Hi Lakshminath
    We have a problem with the word "Group" in our group:-)
we use Group ID in GDOI (taken from GSAKMP) and this may
be confused with DH groups in OAKLEY/IKE.  We use
group management and that can be confused with multicast
group management - IGMP.  All of these things are quite
different.  Our groups can encompass zero or more multicast
groups.

   We talk about group management in the context of different
group management algorithms that can use multicast to
efficiently add or remove group members, which may or
may not use multicast communications amongst themselves.
We know of a few good algorithms.  I expect more work
in this area but personally don't see the value in coming up
with a common specification for them.  It would be better
to develop the key management framework to accommodate
them without forcing them to use common payloads.

Mark

---

From: "Lakshminath Dondeti" <[email-masked]>
Date: Tue, 03 Apr 2001 15:22:44 -0400

Mark,

Thanks much for the clarification.  You know we probably should
compile a glossary of terms used in the MSEC context.  There
are others such as PFS in IKE/ISAKMP/IPSEC and PFS in group 
security literature (forward access control in our terminology).

Anyway, as I understand, you are for having something similar to
Appendix B (LKH Data Key Download Definitions) in GDOI I-D,
separately for each of the proposed/future key management schemes.  
Is that correct?

best regards,
Lakshminath

---

From: Mark Baugher <[email-masked]>
Date: Tue, 03 Apr 2001 13:25:51 -0700

Lakshminath,

>separately for each of the proposed/future key management schemes.

Yes.  I think that trying to get 1 spec right for N implementations
will be easier than getting m specs right for N implementations.
I think that there should be separate drafts for LKH, OFT, OFC
and any other group management algorithms.

Mark

---

From: Thomas Hardjono <[email-masked]>
Date: Wed, 04 Apr 2001 04:00:09 -0700

A glossary was in fact intended for the GKM building block document,
but never made it to the final version (ie. there was a short one).

Perhaps now is a good time to start it again, as it is becoming clear
that some words are overloaded with meanings.  btw. This also why we
ended-up with the term "Category" for SAs :).

cheers,

thomas
------

At 4/3/01||03:22 PM, Lakshminath Dondeti wrote:
> > > > > > > > >number is increased, and when a one-way function is used 
> on the
> > > > > current
> > > > > > > > > > > This notion of a GID is also being carried-over into 
> the GDOI
> > > > > work
> > > > > > > > > > > (at least implicitly).
> > > > > > > > > > >
> > > > > > > > > > > but the question still arises: how do I know how to 
> match the
> > > > > KEKs
> > > > > > > > > > In GDOI, the push message includes an SA payload 
> containing the
> > > > > policy
> > > > > > > > > > for the two data channels, and the KD payload contains 
> the new
> > > > > keys for
> > > > > > > > > > Or, if you really considering confusion between the two 
> KEKs,
> > > > > the only
> > > > > > > > > > confusion between would be between the current KEK and 
> a new
> > > > > one sent
> > > > > > > > > > However, the new one replaces the current KEK after the 
> push
> > > > > message
> > > > > > > > > > > One answer is using a Session-ID (SID) in conjunction 
> with
> > > > > the GID.
> > > > > > > > > > The GDOI, there is already a unique value associated 
> with each
> > > > > KEK. The