Subject: [Hipsec] Issue #5: state machine bug

From: [email-masked] (Julien Laganier)
Date: Tue Dec 9 09:58:00 2003

--Boundary_(ID_Pv4SwYj7PzIwH41YCU7y+g)
Content-type: text/plain; charset=us-ascii
Content-transfer-encoding: 7BIT
Content-disposition: inline

Folks,

Getting back to issue #5, I've tried to add a new substate to the state 
machine (E4-resync) to be able to receive R2 when the corresponent node 
rebooted and send R1 in reply to an ESP packet with unknown SPI. I also 
renamed E4 in E4-rekey to avoid creating to much substates, as per Pekka's 
suggestion. Let's try to describe the approach:

The new state machine transitions to E4-resync while in E3 or E4-rekey, upon 
recept of a valid R1 which succesfully passed through SA and birthday check. 
The new substate E4-resync is pretty similar to E3, except that R2 is 
accepted. A counter is fired when transitionning to E4-resync, and when 
timeout is occuring the state machine go back to E3.

Note that E4-rekey and E4-resync might be better named E3-rekey and 
E3-resync... I dunno.

The remaining question is whether or not a state machine need to go back to 
E4-rekey while in E4-resync and timeout. If it is the case, I guess we need 
to split E4-resync in E4-resync and E4-resync-while-rekey, both reached upon 
recept of a R1 while being in resp. E4-rekey and E3.

If we split E4-resync, perhaps we can keep the original E4 state (rekeying), 
and then name the new two substates E3-resync (resync when in E3) and 
E4-rekey (resync when rekeying in E4).

If you a few spare minutes, please take a look at the attached modified state 
machine describing the first approach, compare it with the original one, and 
let me know your thoughts about it.

Thanks,

--julien

--Boundary_(ID_Pv4SwYj7PzIwH41YCU7y+g)
Content-type: text/plain; charset=us-ascii; name=STATE
Content-transfer-encoding: 7BIT
Content-disposition: attachment; filename=STATE

5.4.1 HIP States

   E0 State machine start

   E1 Initiating HIP

   E2 Waiting to finish HIP

   E3 HIP SA established

   E4-rekey HIP SA established, rekeying
   
   E4-resync HIP SA established, resynchronizing with rebooted correspondent

   E-FAILED HIP SA establishment failed

5.4.2 HIP State Processes

   +---------+
   |    E0   |  Start state
   +---------+

   Datagram to send, send I1 and go to E1
   Receive I1, send R1 and stay at E0
   Receive I2, process
        if successful, send R2 and go to E3
        if fail, stay at E0
   Receive ESP for unknown SA, send R1 and stay at E0
   Receive ANYOTHER, drop and stay at E0

   +---------+
   |    E1   |  Initiating HIP
   +---------+

   Receive I1, send R1 and stay at E1
   Receive I2, process
        if successful, send R2 and go to E3
        if fail, stay at E1
   Receive R1, process
        if successful, send I2 and go to E2
        if fail, go to E-FAILED
   Receive ANYOTHER, drop and stay at E1
   Timeout, increment timeout counter
        If counter is less than I1_RETRIES_MAX, send I1 and stay at E1
        If counter is greater than I1_RETRIES_MAX, go to E-FAILED

   +---------+
   |    E2   | Waiting to finish HIP
   +---------+

   Receive I1, send R1 and stay at E2
   Receive I2, process
        if successful, send R2 and go to E3
        if fail, stay at E2
   Receive R2, process
        if successful, go to E3
        if fail, go to E-FAILED
   Receive ANYOTHER, drop and stay at E2
   Timeout, increment timeout counter
        If counter is less than I2_RETRIES_MAX, send I2 and stay at E2
        If counter is greater than I2_RETRIES_MAX, go to E-FAILED

   +---------+
   |    E3   | HIP SA established
   +---------+

   Receive I1, send R1 and stay at E3
   Receive I2, process with Birthday check
        if successful, send R2, drop old SA and cycle at E3
        if fail, stay at E3
   Receive R1, process with SA and Birthday check
        if successful, send I2, prepare to drop old SA and go to E4-resync
        if fail, stay at E3
   Receive R2, drop and stay at E3

   Receive ESP for SA, process and stay at E3
   Receive NES, process
        if successful, send NES and stay at E3
        if failed, stay at E3
   Need rekey,
        send NES and go to E4-rekey

   +---------+
   |E4-rekey | HIP SA established, rekey pending
   +---------+

   Receive I1, send R1 and stay at E4-rekey
   Receive I2, process with Birthday check
        if successful, send R2, drop old SA and go to E3
        if fail, stay at E4-rekey
   Receive R1, process with SA and Birthday check
        if successful, send I2, prepare to drop old SA and go to E4-resync
        if fail, stay at E4-rekey
   Receive R2, drop and stay at E4-rekey

   Receive ESP for SA, process and stay at E4-rekey
   Receive NES, process
        if successful, replace SAs and go to E3
        if failed, stay at E4-rekey
   Timeout, increment timeout counter
        If counter is less than NES_RETRIES_MAX, send NES and stay at E4-rekey
        If counter is greater than NES_RETRIES_MAX, go to E-FAILED

   +---------+
   |E4-resync| HIP SA established, resync pending
   +---------+

   Receive I1, send R1 and cycle at E4-resync
   Receive I2, process with Birthday check
        if successful, send R2, drop old SA and go to E3
        if fail, stay at E4-resync
   Receive R1, process with SA and Birthday check
        if successful, send I2, prepare to drop old SA and cycle at E4-resync
        if fail, stay at E4-resync
   Receive R2, process with SA and Birthday check
        if successful, go to E3
        if fail, stay at E4-resync

   Receive ESP for SA, process and go to E3
   Receive NES, process
        if successful, send NES and go to E3
        if failed, stay at E4-resync
   Timeout, increment timeout counter
        If counter is less than RESYNC_RETRIES_MAX, send I2 and stay at E4-resync
        If counter is greater than RESYNC_RETRIES_MAX, go to E3

5.4.3 Simplified HIP State Diagram

   Receive packets cause a move to a new state.

   +---------+
   |    E0   |>---+
   +---------+    |
    | ^ |         |
    | | | Dgm to  |
    +-+ | send    |
     I1 |         |  (note: ESP- means ESP with unknown SPI)
   ESP- |         |
        v         |
   +---------+    |
   |    E1   |>---|----------+
   +---------+    |          |
        |         |          |
        | R1      |          |
        |         |I2        |I2
        v         |          |
   +---------+    |          |
   |    E2   |>---|----------|-----+
   |         |    |          |     |
   +---------+    |          |     |
        |         |          |     |
        | R2      |          |     |I2
        |         |          |     |
        v         |          |     |
   +---------+<---+          |     |
   |         |               |     |
   |    E3   |<--------------+     |
   |         |<--------------------+
   |         |<--------------------+
   |         |---------------+     |
   |         |<-------+      |     |
   |         |----+   |      |     |
   +---------+    |   |      |     |
    |  ^  ^       |   |      |     |
    |  |  |       |   |      |     |
    +--+  |       |   |      |     |
    ESP,  |  rekey|   |I2    |     |
    NES,  |       |   |      |     |
    I1,   |NES    |   |      |     |
    I2    |       |   |      |     |
          |       |   |      |     |
          |       |   |      |     |
   +---------+    |   |      |     |
   |         |<---+   |      |     |
   |E4-rekey |>-------+      |     |
   +---------+               |     |
    |  ^   v                 |     | I2, R2, ESP
    |  |   |              R1 |     | NES, Timeout 
    +--+   |                 |     |
    ESP,   |                 |     |
    I1     |                 |     |
           |                 v     ^
           |    R1         +---------+
           +-------------->|         |
                           |E4-resync|
                           +---------+
                              |  ^   
                              |  |     
                              +--+       
                              I1,
                              R1

--Boundary_(ID_Pv4SwYj7PzIwH41YCU7y+g)
Content-type: application/x-trash; name=STATE.old
Content-transfer-encoding: 7bit
Content-disposition: attachment; filename=STATE.old

5.4.1 HIP States

   E0 State machine start

   E1 Initiating HIP

   E2 Waiting to finish HIP

   E3 HIP SA established

   E4 HIP SA established, rekeying

   E-FAILED HIP SA establishment failed

5.4.2 HIP State Processes

   +---------+
   |    E0   |  Start state
   +---------+

   Datagram to send, send I1 and go to E1
   Receive I1, send R1 and stay at E0
   Receive I2, process
        if successful, send R2 and go to E3
        if fail, stay at E0
   Receive ESP for unknown SA, send R1 and stay at E0
   Receive ANYOTHER, drop and stay at E0

   +---------+
   |    E1   |  Initiating HIP
   +---------+

   Receive I1, send R1 and stay at E1
   Receive I2, process
        if successful, send R2 and go to E3
        if fail, stay at E1
   Receive R1, process
        if successful, send I2 and go to E2
        if fail, go to E-FAILED
   Receive ANYOTHER, drop and stay at E1
   Timeout, increment timeout counter
        If counter is less than I1_RETRIES_MAX, send I1 and stay at E1
        If counter is greater than I1_RETRIES_MAX, go to E-FAILED

   +---------+
   |    E2   | Waiting to finish HIP
   +---------+

   Receive I1, send R1 and stay at E2
   Receive I2, process
        if successful, send R2 and go to E3
        if fail, stay at E2
   Receive R2, process
        if successful, go to E3
        if fail, go to E-FAILED
   Receive ANYOTHER, drop and stay at E2
   Timeout, increment timeout counter
        If counter is less than I2_RETRIES_MAX, send I2 and stay at E2
        If counter is greater than I2_RETRIES_MAX, go to E-FAILED

   +---------+
   |    E3   | HIP SA established
   +---------+

   Receive I1, send R1 and stay at E3
   Receive I2, process with Birthday check
        if successful, send R2, drop old SA and cycle at E3
        if fail, stay at E3
   Receive R1, process with SA and Birthday check
        if successful, send I2, prepare to drop old SA and cycle at E3
        if fail, stay at E3
   Receive R2, drop and stay at E3

   Receive ESP for SA, process and stay at E3
   Receive NES, process
        if successful, send NES and stay at E3
        if failed, stay at E3
   Need rekey,
        send NES and go to E4

   +---------+
   |    E4   | HIP SA established, rekey pending
   +---------+

   Receive I1, send R1 and stay at E4
   Receive I2, process with Birthday check
        if successful, send R2, drop old SA and go to E3
        if fail, stay at E4
   Receive R1, process with SA and Birthday check
        if successful, send I2, prepare to drop old SA and go to E3
        if fail, stay at E4
   Receive R2, drop and stay at E4

   Receive ESP for SA, process and stay at E4
   Receive NES, process
        if successful, replace SAs and go to E3
        if failed, stay at E4
   Timeout, increment timeout counter
        If counter is less than NES_RETRIES_MAX, send NES and stay at E4
        If counter is greater than NES_RETRIES_MAX, go to E-FAILED

5.4.3 Simplified HIP State Diagram

   Receive packets cause a move to a new state.

   +---------+
   |    E0   |>---+
   +---------+    |
    | ^ |         |
    | | | Dgm to  |
    +-+ | send    |
     I1 |         |  (note: ESP- means ESP with unknown SPI)
   ESP- |         |
        v         |
   +---------+    |
   |    E1   |>---|----------+
   +---------+    |          |
        |         |          |
        | R1      |          |
        |         |I2        |I2
        v         |          |
   +---------+    |          |
   |    E2   |>---|----------|-----+
   |         |    |          |     |
   +---------+    |          |     |
        |         |          |     |
        | R2      |          |     |I2
        |         |          |     |
        v         |          |     |
   +---------+<---+          |     |
   |         |               |     |
   |    E3   |<--------------+     |
   |         |<--------------------+
   |         |<-------+
   |         |----+   |
   +---------+    |   |
    |  ^  ^       |   |
    |  |  |       |   |
    +--+  |       |   |
    ESP,  |  rekey|   |R1,I2
    NES,  |       |   |
    I1,   |NES    |   |
    I2,   |       |   |
    R1    |       |   |
          |       |   |
   +---------+    |   |
   |         |<---+   |
   |    E4   |>-------+
   +---------+
    |  ^
    |  |
    +--+
    ESP,
    I1,

--Boundary_(ID_Pv4SwYj7PzIwH41YCU7y+g)--

---

From: [email-masked] (Pekka Nikander)
Date: Wed Dec 10 07:01:05 2003

> rebooted and send R1 in reply to an ESP packet with unknown SPI.

In general, looks very good.

> timeout is occuring the state machine go back to E3.

I think this is the correct approach.  Minor comments:

   - since receiving R1 in E3 already causes the state machine to
     prepare to drop the old SAs, I don't think that we need to do
     that again if we receive another R1 in the E4-resync state.
     Furthermore, since it is possible that the first I2 that was
     sent when going to E4-resync may have been lost, I think that
     the Birthday check should be dropped here.  With these changes,
     the new R1 rule would become as follows:

    Receive R1,
         if similar to one that caused transition to E4-resync,
             resend I2 and cycle at E4-resync
         if passes SA and Birthday checks, send I2, and cycle at 
E4-resync
         otherwise, stay at E4-resync

   - The rule for R2 looks like inaccurate since it does not contain
     a birthday parameter.  I think you need to reword it somehow.

> Note that E4-rekey and E4-resync might be better named E3-rekey and

Yes.  Please make the change.

> recept of a R1 while being in resp. E4-rekey and E3.

Well, I think that if the state machine enters the E4-resync state, the
right thing is to go to E-failed (and not back to E3 or E4-resync) on
timeout.  Anyway, the I2s should trigger an R2 from the peer even if
the peer didn't actually initiate the resync, and that R2 will cause
the host to return to E3.

--Pekka Nikander

---

From: [email-masked] (Pekka Nikander)
Date: Wed Dec 10 07:16:00 2003

Further thoughts after some more consideration:

   - An I2 may not, after all, generate an R2 from the peer since
     if it is still up, it may drop the I2 due to failing birthday
     check.  There are a few ways how to deal with that:

     1. Define that when you go to E4-resync, you increment
        your birthday counter.

     2. Instead of going to E-FAILED from E4-resync on timeout,
        go back to E3.  Especially, if the host continues to
        receive valid ESP traffic from the peer, there is definitely
        no need to go to E-FAILED.

  - A second question is whether we really want to resend the
    I2s on timeouts?  Would it be sufficient to have one fairly
    long timeout?

    The rationale is as follows:  If there is still active
    traffic between the hosts, the host in E4-resync will
    continue to send traffic with the old SA.  That will trigger
    the recipient to send more R1s, with just rate limitation
    limiting the number of them.  The host in E4-resync will
    answer with further I2s.  The first I2 that the crashed
    host receives will cause it to send R2 and move to E3.
    When the host in E4-resync receives the R2, it will move
    to E3, too.  No resending of I2s is needed?

    The only problem seems to be if the R2 gets lost.  I guess
    that in that case the crashed host will send yet another R1,
    and the E4-resync host will reply with I2, which will now be
    dropped since it does not pass the Birthday check.

    But the very same problem seems to be in the initial handshake
    already.  If R2 gets dropped, the Initiator will stay in E2
    while the Responder is already in E3.  The Responder will
    drop the I2s since they don't pass the Birthday check.

I don't know what to do about the lost R2 problem.  Any
thoughts anyone?

--Pekka Nikander