Subject: Re: [Hipsec] Recovery from state loss

From: Erik Nordmark <[email-masked]>
Date: Thu, 1 Jul 2004 16:15:40 -0700 (PDT)

So here is my attempted approach and a close handshake that
can apply to HIP as well as NOID. The goal is to remove the case when
one end retains association state and the other end has discarded it,
since this seems to open up some DoS opportunity.

Comments appreciated.

  Erik

This scheme is robust against arbitrary network partitioning and loss,
whether in both directions or one direction, through the use of timers
plus a "close" and "closeack" message.

The underlying observation is that the network doesn't spontaenously
generate packets, thus for a packet to be received it must have
been sent by the peer, and if the host does not send a packet
no packet will be received by the peer.
(But packets might be sent and never received.)

In the basic analysis we assume that the network delay
(propagation and queuing) is zero that is a packet
is received by the peer either immediately when sent, or
never (in the case of loss).

The mechanism uses a time constant: X minutes.

The mechanism works as follows:
1. When no packet has been received on the association for X minutes
   the association transitions to "closing" state.
   A "close" message is transmitted to the peer.

   When in "closing" state the host must not send any data packets
   using the association. If there is a need to send a data packet
   a new association must be created by starting by sending an I1.

2. When the host receives a "close" message it discards the
   association state and responds with a "closeack" message.
   (The authenticity of the "close" message can be verified
   the same way data messages are verified.)
   This processing applies whether or not the state is "closing"
   in order to handle "close" messages from both ends crossing
   in flight.

   Once the association state has been discarded any need to
   send data packets will trigger establishing a new association, starting
   with sending an I1.

3. A "close" message which is received when there is no association state
   can not be verified but will result in a "closeack" response
   to speed up the peer discarding the state in the precense of
   packet loss.

4. The "close" message is retransmitted until either a "closeack"
   message is received, or it has been retransmitted for a total of
   X minutes. When either occurs the association state is discarded.

5. When a host receives a "closeack" message it verifies
   that it is in "closing" state and that the "closeack" was in
   response to the "close" (using e.g. a nonce).

   It is possible to use stronger verification of the "closeack"
   based on secrets tied to the association state, but only
   for the first "close" message since the state is discarded
   on its reception. Thus if the "closeack" response to the first
   "close" is lost, the host would need to wait for the full X minutes
   until discarding its state.

Due to packet loss the two sides can have different views
of when the last packet might have been sent, but because no
received packets in X minutes causes a state transition, this
difference can not be larger than X. Since the "close" messages
are retransmitted for X minutes (during which the peer can not
possibly receive any data packets) the peer will transition to
"closing" and stop sending data packets before the host will
discard its state. Example 2 shows a case when this happens.

Example 1: working communication in both directions

Time T: A sends a packet to B. While A doesn't know it yet, this is
the last packet A will send using the association.
B continues to send packets to A.

Time T+X: B has not received any packets from A for X seconds.
B marks the association as "closing", that is, it will not use the
state to transmit any more. B sends a "close" message to A.

Time T+X: A receives a "close" message from A.
Discards the association state and responds with a "closeack" message.

Time T+X: B receives the "closeack" message and discards the association
state.

Example 2: Unidirectional failure; A->B packets are all dropped.

Time T: A sends a packet to B. While A doesn't know it, this is
the last packet B will receive from A.

Time T+1 etc: A sends a packet to B which is lost.

Time T+X: B has not received any packets from A for X seconds.
B marks the association as "closing", that is, it will not use the
state to transmit any more. B sends a "close" message to A.

Time T+X: A receives a "close" message from A.
Discards the association state and responds with a "closeack" message.
The "closeack" message is lost.

Time T+X+1 etc: B retransmits the "close" message.

Time T+X+1 etc: A receives the "close" message, has no association state,
and responds with a "closeack" message.
The "closeack" message is lost.

Time T+2X: B stops retransmitting the "close" message and
discards the session state.

Example 2: Bidirectional failure; all packets are dropped.

Time T1: A sends a packet to B. While A doesn't know it, this is
the last packet B will receive from A.

Time T2: B sends a packet to A. While B doesn't know it, this is
the last packet A will receive from B.

Time T1+1 etc: A sends a packet to B which is lost.
Time T2+1 etc: B sends a packet to A which is lost.

Time T1+X: B has not received any packets from A for X seconds.
B marks the association as "closing", that is, it will not use the
state to transmit any more. B sends a "close" message to A.
The "close" message is lost.

Time T2+X: A has not received any packets from B for X seconds.
A marks the association as "closing", that is, it will not use the
state to transmit any more. A sends a "close" message to B.
The "close" message is lost.

Time T1+X+1 etc: B retransmits the "close" message, which is lost.
Time T2+X+1 etc: A retransmits the "close" message, which is lost.

Time T1+2X: B stops retransmitting the "close" message and
discards the session state.

Time T2+2X: A stops retransmitting the "close" message and
discards the session state.

Since the difference between T1 and T2 can't be more than X,
we know that the session state can not be discarded
before the other end has transitioned to "closing".

AFAIK the above examples generalize to arbitrary packet loss;
in no case will a data packet be received when there is no
association state. Hence data packet that are received and have no
matching session state can be silently dropped; no need to send
an error or an I1.

Intuitively it seems like network delays can be handled
to make the period for the retransmission of the "close" message
be X+MSL (Maximum segment lifetime) instead of X, but I haven't
verified this.

---

_______________________________________________
Hipsec mailing list
[email-masked]
http://honor.trusecure.com/mailman/listinfo/hipsec

---

From: Julien Laganier <[email-masked]>
Date: Thu, 15 Jul 2004 13:25:14 +0200

On Friday 02 July 2004 01:15, Erik Nordmark wrote:
> can apply to HIP as well as NOID. The goal is to remove the case
> when one end retains association state and the other end has
> discarded it, since this seems to open up some DoS opportunity.
>
> Comments appreciated.

Hi Erik,

IMHO, this scheme fills a hole in the HIP specification, particularly 
since we removed the RESYNC-related stuff. Hence, I am strongly in 
favor of adopting (and adapting) the proposed approach. 

There's  a remaining question, though: Does it belongs to the base 
protocol spec, or rather to an extension? I would vote for the first 
but I'm not 100% sure...

What do other people think?

--julien

---

From: Pekka Nikander <[email-masked]>
Date: Fri, 16 Jul 2004 20:00:46 +0300

> What do other people think?

I don't have any strong opinion.  If someone makes a good write up for
the base spec, I don't have anything against including it.  On the other
hand, I'm afraid that getting all the details (like various race 
conditions)
right might take some time and effort.

--Pekka