Subject: [Hipsec] Arch Issue #1: Clarification on the role of the HIP exchange vs. ESP policies

From: [email-masked] (Pekka Nikander)
Date: Wed Oct 8 09:46:00 2003

Tom Henderson (thanks Tom) has privately raised the question
on how we should interpret the HIP exchange wrt. IPsec SAs.
He writes:

> The state machine currently seems to permit at most one HIP
> association/SA between two given host identities.  ...
> Is this an intentional restriction?  I don't know enough
> about current IPsec policy rules to answer that question
> (whether you might want multiple SAs between hosts).

My personal opinion is that yes, this is intentional.
In theory, one could have multiple parallel SAs between
a pair of HITs, and then use e.g. ports to make the
choice of which SA to use.  However, HIP lacks the
ability to negotiate the required policies.

I would suppose that the right way of having several
parallel SAs for policy purposes would be to define an
extension to HIP, allowing the required policy negotiation.
The only restriction would be that all the SAs share the
same KEYMAT.  If there is a need to have several sets of
KEYMAT between a pair of two hosts, there would need to
be several HITs, in parallel.

My suggestion is that we move the current Section 11 of
the base protocol draft,

 > 11. ESP with HIP
 >
 > HIP sets up a pair of Security Associations (SA) to enable ESP in an
 > end-to-end manner that can span addressing realms (i.e. across NATs).
 > ...

to the architecture draft, and modify it appropriately.
The section is already now architectural in nature, and
doesn't really add anything to the actual base protocol
specification.   Almost all of the issues in the section
have been explained elsewhere, too, and the few that
haven't can be easily moved to better locations, e.g.
into Section 8. Packet processing.

Once the section is moved, I could add a new subsection
explaining the issue with policies, and the possibility
of new extensions that allow policy negotiation.

Opinions?

--Pekka Nikander

---

From: [email-masked] (Jari Arkko)
Date: Wed Oct 8 10:01:01 2003

> be several HITs, in parallel.

In IPsec, I believe, the multiple SA pairs between two
hosts can appear for three reasons:

1) Policy is different per flow, e.g., per port.

2) Colliding negotiations may result in two SA pairs
    for the same purpose. That is, when both parties
    initiate at the same time, they would normally both
    succeed and result in different SAs.

3) Re-key can result in parallelly existing
    SAs for the same purpose, at least for a short
    period of time.

For #1, I think we should avoid having such a policy.
No policy is good policy, and simplies the usage
of the system. But how are #2 and #3 handled in HIP?
What happens if two hosts initiate at the same time?

--Jari

---

From: [email-masked] (Pekka Nikander)
Date: Wed Oct 8 10:10:03 2003

> For #1, I think we should avoid having such a policy.

Agreed.  If someone wants to have some per port policy,
they can define a HIP extension for that.

> But how are #2 and #3 handled in HIP?

The state machine has been designed in such a way that
if two hosts initiate at the same time, it should
result in only one state and one pair of SAs.  However,
I think that it has never been tested in practise.

I think that Kimmo Nieminen has been doing some simulations
on the state machines.  Kimmo, do you remember the results
of this from your simulations?

With regard to re-keying, I have tried to design the
NES procedure so that it will always lead to replacing
the SAs in rough synchrony, even if both ends initiate
re-keying at the same time.  However, I think that nobody
has studied what happens in practise, i.e., there may be
packet sequences that I haven't considered.  For natural,
reasons there must exist two incoming SAs for a brief
period of time, but there should always be only one active
outgoing SA.

The situation becomes more complicated when multi-homing
is introduced, but that is a subject for another thread.

--Pekka Nikander

---

From: [email-masked] (Tim Shepard)
Date: Wed Oct 8 10:21:01 2003

While I could be convinced otherwise, I think leaving HIP with the
limitation of only supporting a single pair of security associations
(one in each direction) is OK becasue host identities can be created
as needed.  If multiple IPSEC security association pairs are needed
between the same computers, they can do it using multiple identities.
Identities in HIP can be created as needed and can be ephemeral.

If an application using one of these ephemeral identities needs to tie
it to some other longer-term identity, I suppose it could do so.  But
I expect in many situations, either the single security association
pair between identities will be sufficient, or if a single security
association is not enough, ephemeral use-once-and-forget identities
will be sufficient.    Any other situation will be complicated enough
that the overhead of having to explicitly handle multiple HIP
identities and tie them together at the application layer (perhaps by
one issuing a certificate for the other) will not be a big deal.

Perhaps it would have been better to take what we call a host identity
and name it something that doesn't have the word host in it.  We could
imagine using identities in HIP that are identified with particular
services that remain tied with the services and not the hosts that
they are implemented on, or even identities that are associated with
individual users.  But changing the name now is probably not worth it,
and the one-to-one mapping between computers and HIP identities will
probably be a very common case.

			-Tim Shepard
			 [email-masked]

---

From: [email-masked] (Jari Arkko)
Date: Wed Oct 8 10:22:04 2003

> of this from your simulations?

A simple (?) state exploration of two machines
running together should expose such bugs, if any?
Has anyone done that?

> period of time, but there should always be only one active

Yes, that's the thing. There may be packets in flight
even if you succeed in making a synchronous change at the
peers. But when you say there can be two incoming SAs
for a brief period of time, how exactly do we handle that
if we don't allow more than one SA pair between two HITs?

> is introduced, but that is a subject for another thread.

Interesting.

--Jari

---

From: [email-masked] (Pekka Nikander)
Date: Wed Oct 8 10:32:00 2003

[A side note:  I completely agree with what Tim wrote
in his message.  The current architecture draft RECOMMENDS
that hosts do have multiple identities.]

Pekka Nikander wrote:
>>... For natural,

> if we don't allow more than one SA pair between two HITs?

Well, the restriction is a *conceptual* one.  During the
re-keying transition, there are two incarnations of the
same SA.  One is the old one and the other one is the new one.

In the IPsec level, these two SAs are most probably two
completely separate SAs, and IPsec doesn't have any idea
that they actually "represent" the same conceptual SA at
the HIP level.

--Pekka Nikander

---

From: [email-masked] (Kimmo Nieminen)
Date: Wed Oct 8 12:56:00 2003

> of this from your simulations?

I have been simulating the state machines, but unfortunately I cannot help
you with this thing. The tool (http://www.cs.tut.fi/ohj/VARG/TVT/) which I
used was not able to handle such a huge state space even though the level
of abstraction was rather high. By using partial parallel composition, the
problem could possibly be solved, but that is quite complicated.

I had modelled all the basic state machine features but I had to limit the
model so that only one host can act as an initiator and the other has to
be the responder. Even at this case, the state space included more than
100 000 states in some cases... Actually, this was the biggest restriction
in my work. Otherwise, based on my simulations the protocol seemed to be
working well.

-- 
[email-masked]
www.kimmo.nieminen.org

---

From: [email-masked] (Michael Richardson)
Date: Sat Oct 11 01:07:01 2003

-----BEGIN PGP SIGNED MESSAGE-----

In general, my suggestion is that HIP permit multiple SAs between
two hosts. The key reason is people who want to do differing QoS.

My opinion is that HIP will become popular in SAN.
Sharing KEYMAT is okay for this.

>>>>> "Pekka" == Pekka Nikander <[email-masked]> writes:

  There are lots of other things other than per-port, but they may
essentially be equivalent to that.

    Pekka> The state machine has been designed in such a way that if two
    Pekka> hosts initiate at the same time, it should result in only one
    Pekka> state and one pair of SAs.  However, I think that it has never
    Pekka> been tested in practise.

  Okay, that's good.

    Pekka> With regard to re-keying, I have tried to design the NES procedure
    Pekka> so that it will always lead to replacing the SAs in rough
    Pekka> synchrony, even if both ends initiate re-keying at the same time.
    Pekka> However, I think that nobody has studied what happens in practise,
    Pekka> i.e., there may be packet sequences that I haven't considered.

  Please look at draft-spencer-ipsec-ike-implementation.txt. Expired right
now, but it is in any freeswan release (ftp.xs4all.nl/pub/crypto/freeswan)
in doc/ dir. I'll find a URL for you when I'm back online.

  oh... why not, I'll just paste the section in here.

4. Basic Keying and Rekeying

4.1. When to Create SAs

   As Tim Jenkins [REKEY] pointed out, there is a potential race
   condition in Quick Mode: a fast lightly-loaded Initiator might start
   using IPsec SAs very shortly after sending QM3 (the third and last
   message of Quick Mode), while a slow heavily-loaded Responder might
   not be ready to receive them until after spending a significant
   amount of time creating its inbound SAs.  The problem is even worse
   if QM3 gets delayed or lost.

   FreeS/WAN's approach to this is what Jenkins called "Responder Pre-
   Setup": the Responder creates its inbound IPsec SAs before it sends
   QM2, so they are always ready and waiting when the Initiator sends
   QM3 and begins sending traffic.  This approach is simple and
   reliable, and in our experience it interoperates with everybody.
   (There is potentially still a problem if FreeS/WAN is the Initiator
   and the Responder does not use Responder Pre-Setup, but no such
   problems have been seen.)  The only real weakness of Responder Pre-
   Setup is the possibility of replay attacks, which we have eliminated
   by other means (see section 3.3).

   With this approach, the Commit Bit is useless, and we ignore it.  In
   fact, until quite recently we discarded any IKE message containing
   it, and this caused surprisingly few interoperability problems;
   apparently it is not widely used.  We have recently been persuaded

Spencer & Redelmeier                                            [Page 7]

Internet Draft          IKE Implementation Issues            26 Feb 2002

   that simply ignoring it is preferable; preliminary experience with
   this indicates that the result is successful interoperation with
   implementations which set it.

4.2. When to Rekey

   To preserve connectivity for user traffic, rekeying of a connection
   (that is, creation of new IPsec SAs to supersede the current ones)
   must begin before its current IPsec SAs expire.  Preferably one end
   should predictably start rekeying negotiations first, to avoid the
   extra overhead of two simultaneous negotiations, although either end
   should be prepared to rekey if the other does not.  There is also a
   problem with "convoys" of keying negotiations: for example, a "hub"
   gateway with many IPsec connections can be inundated with rekeying
   negotiations exactly one connection-expiry time after it reboots, and
   the massive overload this induces tends to make this situation self-
   perpetuating, so it recurs regularly.  (Convoys can also evolve
   gradually from initially-unsynchronized negotiations.)

   FreeS/WAN has the concept of a "rekeying margin", measured in
   seconds.  If FreeS/WAN was the Initiator for the previous rekeying
   (or the startup, if none) of the connection, it nominally starts
   rekeying negotiations at expiry time minus one rekeying margin.  Some
   random jitter is added to break up convoys: rather than starting
   rekeying exactly at minus one margin, it starts at a random time
   between minus one margin and minus two margins.  (The randomness here
   need not be cryptographic in quality, so long as it varies over time
   and between hosts.  We use an ordinary PRNG seeded with a few bytes
   from a cryptographic randomness source.  The seeding mostly just
   ensures that the PRNG sequence is different for different hosts, even
   if they start up simultaneously.)

   If FreeS/WAN was the Responder for the previous rekeying/startup, and
   nothing has been heard from the previous Initiator at expiry time
   minus one-half the rekeying margin, FreeS/WAN will initiate rekeying
   negotiations.  No jitter is applied; we now believe that it should be
   jittered, say between minus one-half margin and minus one-quarter
   margin.

   Having the Initiator lead the way is an obvious way of deciding who
   should speak first, since there is already an Initiator/Responder
   asymmetry in the connection.  Moreover, our experience has been that
   Initiator lead gives a significantly higher probability of successful
   negotiation!  The negotiation process itself is asymmetric, because
   the Initiator must make a few specific proposals which the Responder
   can only accept or reject, so the Initiator must try to guess where
   its "acceptable" region (in parameter space) might overlap with the
   Responder's.  We have seen situations where negotiations would

Spencer & Redelmeier                                            [Page 8]

Internet Draft          IKE Implementation Issues            26 Feb 2002

   succeed or fail depending on which end initiated them, because one
   end was making better guesses.  Given an existing connection, we KNOW
   that the previous Initiator WAS able to initiate a successful
   negotiation, so it should (if at all possible) take the lead again.
   Also, the Responder should remember the Initiator's successful
   proposal, and start from that rather than from his own default
   proposals if he must take the lead; we don't currently implement this
   completely but plan to.

   FreeS/WAN defaults the rekeying margin to 9 minutes, although this
   can be changed by configuration.  There is also a configuration
   option to alter the permissible range of jitter.  The defaults were
   chosen somewhat arbitrarily, but they work extremely well and the
   configuration options are rarely used.

4.3. Choosing an SA

   Once rekeying has occurred, both old and new IPsec SAs for the
   connection exist, at least momentarily.  FreeS/WAN accepts incoming
   traffic on either old or new inbound SAs, but sends outgoing traffic
   only on the new outbound ones.  This approach appears to be
   significantly more robust than using the old ones until they expire,
   notably in cases where renegotiation has occurred because something
   has gone wrong on the other end.  It avoids having to pay meticulous
   attention to the state of the other end, state which is difficult to
   learn reliably given the limitations of IKE.

   This approach has interoperated successfully with ALMOST all other
   implementations.  The only (well-characterized) problem cases have
   been implementations which rely on receiving a Delete message for the
   old SAs to tell them to switch over to the new ones.  Since delivery
   of Delete is unreliable, and support for Delete is optional, this
   reliance seems like a serious mistake.  This is all the more true
   because Delete announces that the deletion has already occurred
   [ISAKMP, section 3.15], not that it is about to occur, so packets
   already in transit in the other direction could be lost.  Delete
   should be used for resource cleanup, not for switchover control.
   (These matters are discussed further in section 5.)

4.4. Why to Rekey

   FreeS/WAN currently implements only time-based expiry (life in
   seconds), although we are working toward supporting volume-based
   expiry (life in kilobytes) as well.  The lack of volume-based expiry
   has not been an interoperability problem so far.

   Volume-based expiry does add some minor complications.  In
   particular, it makes explicit Delete of now-disused SAs more

Spencer & Redelmeier                                            [Page 9]

Internet Draft          IKE Implementation Issues            26 Feb 2002

   important, because once an SA stops being used, it might not expire
   on its own.  We believe this lacks robustness and is generally
   unwise, especially given the lack of a reliable Delete, and expect to
   use volume-based expiry only as a supplement to time-based expiry.
   However, Delete support (see section 5) does seem advisable for use
   with volume-based expiry.

   We do not believe that volume-based expiry alters the desirability of
   switching immediately to the new SAs after rekeying.  Rekeying
   margins are normally a small fraction of the total life of an SA, so
   we feel there is no great need to "use it all up".

4.5. Rekeying ISAKMP SAs

   The above discussion has focused on rekeying for IPsec SAs, but
   FreeS/WAN applies the same approaches to rekeying for ISAKMP SAs,
   with similar success.

   One issue which we have noticed, but not explicitly dealt with, is
   that difficulties may ensue if an IPsec-SA rekeying negotiation is in
   progress at the time when the relevant ISAKMP SA gets rekeyed.  The
   IKE specification [IKE] hints, but does not actually say, that a
   Quick Mode negotiation should remain on a single ISAKMP SA
   throughout.

   A reasonable rekeying margin will generally prevent the old ISAKMP SA
   from actually expiring during a negotiation.  Some attention may be
   needed to prevent in-progress negotiations from being switched to the
   new ISAKMP SA.  Any attempt at pre-expiry deletion of the ISAKMP SA
   must be postponed until after such dangling negotiations are
   completed, and there should be enough delay between ISAKMP-SA
   rekeying and a deletion attempt to (more or less) ensure that there
   are no negotiation-starting packets still in transit from before the
   rekeying.

   At present, FreeS/WAN does none of this, and we don't KNOW of any
   resulting trouble.  With normal lifetimes, the problem should be
   uncommon, and we speculate that an occasional disrupted negotiation
   simply gets retried.

4.6. Bulk Negotiation

   Quick Mode nominally provides for negotiating possibly-large numbers
   of similar but unrelated IPsec SAs simultaneously [IKE, section 9].
   Nobody appears to do this.  FreeS/WAN does not support it, and its
   absence has caused no problems.

Spencer & Redelmeier                                           [Page 10]

Internet Draft          IKE Implementation Issues            26 Feb 2002

---

From: [email-masked] (Julien Laganier)
Date: Mon Oct 13 02:56:01 2003

On Friday 10 October 2003 14:28, Michael Richardson wrote:
> Pekka Nikander wrote:
> > With regard to re-keying, I have tried to design the NES procedure
> > so that it will always lead to replacing the SAs in rough
> > synchrony, even if both ends initiate re-keying at the same time.
> > However, I think that nobody has studied what happens in practise,
> > i.e., there may be packet sequences that I haven't considered.
>

BTW, folks, whatever expired I-D is archived at 
<http://www.watersprings.org/pub/id/index-all.html>

--julien

---

From: [email-masked] (Pekka Nikander)
Date: Mon Oct 20 01:13:01 2003

Michael,

> two hosts. The key reason is people who want to do differing QoS.

Well, there are at least three ways how we could do that.

1. One of the hosts can have multiple HIs.  Each pair of HIs
    will have a different pair of SAs.  That is already supported now.

2. We can extend the HIP base exchange to negotiate multiple SAs.

3. We can separately specify HIP extensions that permit multiple
    SAs between two hosts.

Personally I am pretty reluctant to change the base exchange.
I would like to keep the base exchange as simple as possible,
and IMHO it is now fairly close to that ideal.  Or at least it
is complex enough; we shouldn't make it any more complex.

Extensions for various purposes are a completely different
business.  For example, it looks like that the multi-homing
part of the multi-homing and mobility solution will require
multiple parallel SAs.

> Sharing KEYMAT is okay for this.

If there are multiple needs that require several parallel SAs
(all sharing the same KEYMAT), I think that we need to do
some design and try to introduce a number of generic parameters
that could be used in multiple solutions.  That is, we could
have a kind of "New SPI" parameter that could be used both
for multi-homing and SAN QoS.  Maybe the current NES_INFO
fulfills that need already now?

Anyway, I think that this aspect needs to be clarified in
the architecture draft.  So far nobody has really objected
moving Section 11 from the protocol spec into of the
architecture draft.  Hence, I have now done that.  The new
version of the architecture draft is available at the following
URLs.

http://www.tml.hut.fi/~pnr/HIP/draft-moskowitz-hip-arch-05-pre-Oct20.txt
http://www.tml.hut.fi/~pnr/HIP/draft-moskowitz-hip-arch-05-pre-Oct20.html
http://www.tml.hut.fi/~pnr/HIP/draft-moskowitz-hip-arch-05-pre-Oct20.xml
http://www.tml.hut.fi/~pnr/HIP/draft-moskowitz-hip-arch-05-pre-Oct20-chbar.txt
http://www.tml.hut.fi/~pnr/HIP/draft-moskowitz-hip-arch-05-pre-Oct20-diff.html

>   Please look at draft-spencer-ipsec-ike-implementation.txt.

I did read through the text (actually twice).  Below are some
comments.  However, I don't think that any of this belongs
to the architecture document.

> 4.1. When to Create SAs
>                                       ... there is a potential race
>    amount of time creating its inbound SAs.

In the HIP base exchange, the Initiator computes KEYMAT and prepares
the SAs before it sends I2.  At this stage, the Responder doesn't
even have a state -- it doesn't necessarily remember sending R1 to
the Initiator.  While the Initiator can and does prepare the incoming
SA completely, it cannot complete the outgoing SA, since it doesn't
have the Responders SPI.

The Responder, on the other hand, creates both incoming and
outgoing SAs as it receives I2.  At this time the Initiator
already has a ready-to-use incoming SA.  Hence, the Responder
can start sending traffic.  Once the Responder has both of the
SAs in place, it sends and R2 to the Initiator.  That R2 carries
the SPI, which allows the Initiator to complete the outgoing SA
and start to use it.  Obviously, the Responder has its corresponding
incoming SA ready at that time.

Of course, if an implementation decides to send the I2 or R2
before actually having the KEYMAT ready, then we could see
this problem.  Maybe there should be an appendix or some guidance
in the protocol spec.  Opinions?

>    must begin before its current IPsec SAs expire. ... FreeS/WAN has 
>    the concept of a "rekeying margin" ...  Some random jitter is added
>    to break up convoys...

This is all interesting, but it really relates to configuration policy.
Right now the architecture draft says next to nothing about policy,
and the base protocol spec tries to leave all policy decisions to the
actual implementations.  Do you propose that we should change this,
and include some discussion, perhaps in the base protocol spec?

>    asymmetry in the connection. 

Well, there shouldn't be any asymmetry in HIP after the base
exchange.  Indeed, the spec says that the systems should forget
which one was the initiator and which one was the responder once
the base exchange has been completed.

>    ...  The negotiation process itself is asymmetric, because
>    can only accept or reject

As far as I can see, there is no proposals, or no negotiation
in that sense, in the HIP rekey procedure.  All that a rekey does
is to optionally replace the D-H KEYMAT, and in any case replace
the keys in the ESP SAs.

>    only on the new outbound ones. 

This is (or at least should be) the case in HIP, too.  However,
I am not quite sure if the text expresses this clearly enough.
I really wish that people would read the NES description, and
would propose improvements.

> 4.4. Why to Rekey

HIP is completely open ended on when or why to rekey.
The docs don't say anything specific other than that the
hosts must rekey before the sequence number rolls over.

> 4.5. Rekeying ISAKMP SAs

As someone (Tom?) pointed out, the way a HIP SAs should
be rekeyed is to simulate state loss, increment birthday,
and send an I2.  This will make the other end believe that
the sender has lost state, makes it to generate the new KEYMAT
and SAs, and send an R2.  The current spec says that the old
SAs should be dropped as a part of the I2 processing.  Maybe
this should be changed so that only the outgoing SA is dropped
immediately, and that the incoming one is kept for some time.
Opinions?

Receiving an I2 while rekeying is going on will cause the host
to immediately drop rekeying.  Creating new HIP SAs implies
creating new ESP SAs.  Should we revise this?

--Pekka Nikander