Subject: [Hipsec] a state machine proposal for mm-03

From: Miika Komu <[email-masked]>
Date: Mon, 3 Apr 2006 18:54:01 +0300 (EEST)

Simplified State Machine without Peer Initiated Rekeying
========================================================

Note1: since there are no other HIP header types for mobility and
multihoming (other than UPDATE), the actual packet processing depends
on the parameters in the HIP packet.

Note2: the state machine is simpler to design if we leave out the peer
initiated rekeying (section 3.2.1.2 in the draft). This way, we can
assume that the UPDATE exchange consists of three packets and that
each packet can be distinguished from each other by the precence of
LOCATOR, ECHO_REQUEST or ECHO_RESPONSE.

Note3: reusing the same state variables on both hosts. At the mobile
host (the sender of LOCATOR) it is related to the data structures of
the source IP. On the corresponding node (receiver of LOCATOR), it is
related to the destination IP.

Note4: need some fresh eyes to verify that this is actually sensible :)

Send UPDATE with LOCATOR:
  - Triggered at the MN depending on changes in network attachments
    and according to local policies
  - Removed addresses are DEPRACATED (and not included in the
    LOCATOR)
  - All other addresses are UNVERIFIED (and included in the LOCATOR)
  - Set preferred LOCATOR depending on local policies
  - Send UPDATE with LOCATOR for the CN

Receive HIP UPDATE:
- Verify the HIP packet: HMAC, SIG, the presence, dependencies and
  validity of the parameters.
  - If the result is failure, goto DROP.
  - If success, proceed based on presence of LOCATOR, ECHO_REQUEST or
    ECHO_RESPONSE (only one of them can be contained in the packet)

Received LOCATOR:
- For each MN address in the received LOCATOR
  - State is DEPRACATED or UNKNOWN
    - Goto UNVERIFIED and send ECHO_REQUEST
  - State is UNVERIFIED
    - Resend ECHO_REQUEST and decrease retransmission timeout
  - Any other state, DROP

Received ECHO REQUEST:
- For each MN address in the corresponding LOCATOR
  - State is UNVERIFIED
    - Goto ACTIVE and send ECHO_RESPONSE
  - Any other state, DROP

Received ECHO_RESPONSE:
- Goto DEPRACATED for all old addresses not present in LOCATOR
- For each MN address in the corresponding LOCATOR
  - State is UNVERIFIED
    - Otherwise goto ACTIVE
    - Change preferred LOCATOR when necessary
  - Any other state, DROP

Receive ESP:
- For the ESP address
  - State is UNVERIFIED
    - Verify ESP validity. Goto DROP if failed
    - Change preferred LOCATOR when necessary
    - Process ESP if there are credits left, and decrease credits.
    - Otherwise DROP
  - State is ACTIVE
    - Process ESP
  - Any other state, DROP

Send ESP:
  - Increase credits

UPDATE retransmission timeout for LOCATOR (at MN):
  - State is UNVERIFIED
    - Resend and decrease retransmission counter
  - Any other state
    - DROP and zero retransmission counter

UPDATE retransmission timeout for ECHO_REQUEST (at CN):
  - State is UNVERIFIED
    - Resend and decrease retransmission counter
  - Any other state
    - DROP and zero retransmission counter

UPDATE retransmission timeout for ECHO_RESPONSE (occurs at the MN when no
ESP was received from the CN from a new address?):
  - State is ACTIVE
    - Resend and decrease retransmission counter
  - Any other state
    - DROP and zero retransmission counter

Handling of CLOSE with ESP_INFO:
- TBD

-- 
Miika Komu              [email-masked]          http://www.iki.fi/miika/

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

---

From: Pekka Nikander <[email-masked]>
Date: Mon, 10 Apr 2006 07:24:45 +0300

> Note2: the state machine is simpler to design if we leave out the  
> peer initiated rekeying (section 3.2.1.2 in the draft). This way,  
> we can assume that the UPDATE exchange consists of three packets  
> and that each packet can be distinguished from each other by the  
> precence of LOCATOR, ECHO_REQUEST or ECHO_RESPONSE.

Unfortunately I don't have time to really consider this in detail,  
but my earlier understanding was that, at least in principle, you  
could make the mobility and re-keying state machines completely  
separate.

Anyway, from the overall architectural design point of view the idea  
was to use UPDATEs as a semi-reliable retransmission and  
acknowledgement sub-layer, on the top of which you can implement any  
state machine.  The UPDATE-layer would signal the state machine above  
about any eventual events where packets don't get acknowledged even  
after multiple retries.  Furthermore, the idea was that you could  
have multiple parallel state machines running at the same time.   
Their messages (payloads) would just be transmitted and acknowledged  
at once at the UPDATE layer, without needing any co-ordination  
between the above state machines.

Now, I agree that there might be problems if you want to synchronise  
these state machines, e.g., for privacy reasons.  However,  
fortunately or not, in the particular case of privacy you need to do  
also other tricks (such as having a changing HIT-blinding algorithm)  
that basically make the whole update mechanism half-unnecessary for  
the strong privacy case.

Some minor comments below, made without _proper_ understanding of the  

>   - All other addresses are UNVERIFIED (and included in the LOCATOR)

Why these need to be UNVERIFIED.  Maybe some of those have been  
verified earlier?

>     ECHO_RESPONSE (only one of them can be contained in the packet)

I don't agree that only one of them can be included; see above.  You  
seem to be making unnecessary limitations.

>   - State is DEPRACATED or UNKNOWN

Why?  See above.

>     - Goto ACTIVE and send ECHO_RESPONSE

I don't understand the logic here.  IMHO you should always answer  
with ECHO_RESPONSE when you get an ECHO_REQUEST on any of your  
addresses, independent of what you are doing with your peer's address  
verification.  Completely separate this out.

> - Goto DEPRACATED for all old addresses not present in LOCATOR

Hmm.  Sounds like a sensible place of doing that.  But there may be  
dragons around, beware.

> - For each MN address in the corresponding LOCATOR

But you can't do that for other than the address that you just  
verified?  Are you saying that one ECHO pair is enough to make all  
addresses verified?  Definitely NOT!

>     - Change preferred LOCATOR when necessary

Did we specify this?  May make sense sometimes, but again,  
beware....  ESP doesn't protect IP source...

>     - Process ESP if there are credits left, and decrease credits.
<no other comments, must run>

--Pekka

---

From: Miika Komu <[email-masked]>
Date: Mon, 10 Apr 2006 16:50:17 +0300 (EEST)

> that basically make the whole update mechanism half-unnecessary for

It is good to have a high level architectural design in the draft. My
state machine proposal was an initial attempt to map the high level design
to a more concrete proposal that will perhaps not fulfill all of the high
level goals of the draft. However, it will be more easier to implement and
make interoperable.

I have observed in practice that the current draft, or at least the
earlier versions, were quite difficult implement even though the draft has
been improving all the time. As a result of the complexity of the draft,
at least our mobility code is looking too complex now and needs some
rewriting (and I think we are not the only one). Also, I think there has
not been many successful interops for m&m either, even though I admit that
having the ever-changing base exchange interops haven't made things any
easier :)

> Why these need to be UNVERIFIED.  Maybe some of those have been

Compare to my notes in the beginning of the email:

"Note3: reusing the same state variables on both hosts. At the mobile
host (the sender of LOCATOR) it is related to the data structures of
the source IP. On the corresponding node (receiver of LOCATOR), it is
related to the destination IP."

There could be a new state for this at the sender of LOCATOR to make this
more clear if that is necessary?

> seem to be making unnecessary limitations.

See my comment in the other email:

* Mainly, no new features. In fact, I suggest removing one feature /
  use-case (readdress with peer-initiated rekey) in favour of
  simplifying state machine, interaction with middle-boxes and
  interoperable implementations. Suggest removal of it from this draft and
  adding to a follow-up draft.

I am proposing the "artificial" restrictions on the draft to make it more
concrete and to support interoperable implementations in the very near
future. I think it is just too modular as it is now :) In addition, I
think the explicit state machine for m&m could make a security analysis of
the UPDATE easier in the future.

If my opinion is going to be ruled out by rough concensus, I'd like to
hear also other opinions. Anyway, I hope at least some of my comments are
useful.

> verification.  Completely separate this out.

So the peer could doing some additional address verification? That is
fine.

> But you can't do that for other than the address that you just verified?
> Are you saying that one ECHO pair is enough to make all addresses
> verified?  Definitely NOT!

I think I might have confused something here. This would be the new rule:

Received ECHO REQUEST:
  - Goto ACTIVE and send echo response

> beware....  ESP doesn't protect IP source...

This was the CBA optimization. Maybe it should be mentioned explicitly.

> <no other comments, must run>

Thanks Pekka. Other comments?

---

From: Pekka Nikander <[email-masked]>
Date: Mon, 10 Apr 2006 18:15:40 +0300

Miika,

I have a feeling that you are imposing the complexity on the design  
yourself.  You seem to be making assumptions that seem unnecessary  
and complicating to me.  For example, why do you attempt to have some  
kind of mirrored and identical state machines at both ends?  I see no  
need for that.  You also seem to try too hard or achieve a too strong  
consistency between the hosts.  Try to think simple, and have address- 
based rather than host-based state machines.

For example, a minimal implementation might do as follows:

- When a host gets a new local address or deprecates an old one, it  
simply sends an update to its active peers (if it can) and lets the  
UPDATE layer to take care of ACKs and retransmission.  If one peer  
does not get the info, let it be in that way, do not try any harder.   
If there is active communication with the peer, it will get the new  
address later on, or resort to using RVS.

- When a host receives a new peer address, it simply enters it into  
its local database.  Only if it needs to use it, e.g. due to that new  
address being the new preferred one or the old preferred one failing,  
initiate reachability check (with CBA).

I'd rather keep those two "state machines" completely separate.

It is a well known fact that when you combine multiple simple  
parallel state machines into a single one you get a complicated one;  
google e.g. for "state space explosion".  Hence, in implementation  
terms, it is much better to implement several parallel state machines  
than a single big one.

> related to the destination IP."

See above.  That assumption is unnecessary and likely to complicate  
your design.

>   adding to a follow-up draft.

See above.  Decomposing your big state machine into several parallel  
ones is likely to simplify your design more than sufficiently.

> future. I think it is just too modular as it is now :)

I think the reverse.  In this case I think complete state-machine  
modularity is good; see the argumentation above.

> In addition, I

I agree, but OTOH such a explicit complete state machine should be  
composed by an analysis tool that is able to automatically generate  
the compound state machine from the multiple parallel ones.

>   - Goto ACTIVE and send echo response

See above.  There is no need to keep track what the other end thinks  
about the state of your addresses.  That only complicates things.   
Furthermore, there is a strong theoretical result that says that it  
is _impossible_ to have complete synchrony between states in an  
asynchronous system.  Google e.g. for "common knowledge" and "modal  
logic".

> This was the CBA optimization. Maybe it should be mentioned  

OK; I haven't been following the details of CBA.  I thought it was  
being applied only for new preferred address candidates as  
_indicated_ by the peer (or necessitated by the previous peer  
address'es failure.)

--Pekka

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Mon, 10 Apr 2006 13:34:11 -0700

Miika, I am catching up on this email, and I will respond inline below,
trying to consider the other exchanges you've had with Pekka. 

> -----Original Message-----
> From: Miika Komu [mailto:[email-masked]] 
> Sent: Monday, April 03, 2006 8:54 AM
> To: [email-masked]
> Subject: [Hipsec] a state machine proposal for mm-03
> 

Agreed.

> LOCATOR, ECHO_REQUEST or ECHO_RESPONSE.

I agree that this scenario can be eliminated from the overview section,
since it may not frequently occur in practice, but I don't know whether
we want to strictly forbid it.

I also think that you should avoid treating these parameters as
surrogates for a pseudo-mobility HIP type (i.e., LOCATOR == mobile I1,
ECHO_REQUEST == mobile R1, etc.).  

LOCATOR is just sent to the peer based on local mobility/policy
decision, and the UPDATE is ACKed for reliability's sake.
ECHO_REQUEST/RESPONSE is a nonce exchange, used by the peer for
reachability test.  We describe some scenarios where these parameters
can be piggybacked on the same UPDATE message, but there is no
requirement to do so, and I would prefer not to constrain it in that
way.  For instance, we should not require that the peer send the
ECHO_REQUEST, nor should we require that the ACK of the LOCATOR also
contain an ECHO_REQUEST rather than be in a separate packet.

I am agreeing with Pekka's point on decoupling, in general.

> related to the destination IP.

I agree with Pekka-- I do not see requirement for this and think that it
may actually be constraining.

>   - Send UPDATE with LOCATOR for the CN

I disagree with your proposal to try to guess what states the peer will
assign to the different addresses-- I do not see the requirement to do
it this way.

>     ECHO_RESPONSE (only one of them can be contained in the packet)
as stated above, disagree that only one parameter type can be contained
in these messages 

>     - Goto UNVERIFIED and send ECHO_REQUEST

sending ECHO_REQUEST is based on local policy decision and shouldn't be
automatic.  There may be lots of announced addresses that the receiver
may not care about checking immediately.

Also, DEPRECATED to UNVERIFIED state change requires peer to send a new
lifetime to a DEPRECATED address.  Your description does not have the
notion of locator lifetimes.

>     - Resend ECHO_REQUEST and decrease retransmission timeout

(same comment about sending the nonce applies).  I do not understand
about decreasing (rather than increasing) timeout.  Shouldn't possibly
the retransmissions for the address check be decoupled from receiving a
new LOCATOR?

>   - Any other state, DROP

There may be addresses in ACTIVE state that are not changed-- I think
you want to add "- State is ACTIVE and address hasn't changed (do
nothing)"

You also should mention that any address *not* in LOCATOR is DEPRECATED
immediately.  

>     - Goto ACTIVE and send ECHO_RESPONSE

this again seems to be an instance of trying to mirror state variables,
which I disagree with, and Pekka seems to have objected to also.  I
would rather describe it as "Received ECHO_REQUEST, send ECHO_RESPONSE"
and leave it at that.

> - Goto DEPRACATED for all old addresses not present in LOCATOR

This step is done upon receiving LOCATOR-- see above.

>     - Change preferred LOCATOR when necessary

Would rephrase the above as " - Move the address whose reachability was
confirmed by the ECHO_RESPONSE from UNVERIFIED to ACTIVE; do not change
any other states"

> This was the CBA optimization. Maybe it should be mentioned 

I think that what is being referred to here is that a successful
decryption of ESP on a new SPI is itself a reachability check, as
discussed in paragraph four of Section 5.4.  This is an optional
optimization.

>     - Process ESP if there are credits left, and decrease credits.

I think you want to increase credits?  Or are you trying to mirror the
peer's credit variable (which I wouldn't understand)?

>   - Increase credits

(decrease credits?)  Actually, decrease only if in UNVERIFIED state;
otherwise, no-op.

>     - DROP and zero retransmission counter

again, address states are not relevant here.

>     - DROP and zero retransmission counter

I would assume that UPDATE is trying to confirm an UNVERIFIED address,
and that if the UPDATE is overcome-by-events (OBE), this timer would
have been cancelled.

>     - DROP and zero retransmission counter

this can just be handled by normal UPDATE mechanisms

> Handling of CLOSE with ESP_INFO:

The other opinions seemed to be to not use CLOSE for this purpose.

Tom

---

From: Miika Komu <[email-masked]>
Date: Mon, 10 Apr 2006 23:37:46 +0300 (EEST)

> yourself.  You seem to be making assumptions that seem unnecessary and
> complicating to me.  For example, why do you attempt to have some kind
> of mirrored and identical state machines at both ends?  I see no need
> for that.  You also seem to try too hard or achieve a too strong

Maybe the state machines are now perhaps separated now better. I revised
it based your nits online and also Tobias Heer gave some offline comments.
They could be used even as simplified, example models instead of forcing
them to be mandatory if the flebility/parallelity is the issue. For
example, the processing rules of section 5 could be illustrated and
summarized in section 5.7 with the simplified state machine.

Pekka, thanks for references. I have some background reading to do. Please
decide as you think is best for the draft. Other tasks await me already.

== Common state machine ==

Receive HIP UPDATE in ESTABLISHED:

== MN example state machine ==

Send UPDATE with LOCATOR:
  - Triggered at the MN depending on changes in network attachments
    and according to local policies
  - Removed addresses are DEPRECATED (and not included in the
    LOCATOR)
  - All other addresses are ACTIVE
  - Set preferred LOCATOR depending on local policies
  - Send UPDATE with LOCATOR for the CN

Received ECHO REQUEST:
    - Send ECHO_RESPONSE

UPDATE retransmission timeout for LOCATOR:
  - State is UNVERIFIED
    - Resend and decrease retransmission counter
  - Any other state
    - DROP and zero retransmission counter

== CN example mobility state machine ===

Received LOCATOR:
- For each MN address not present anymore in the locator
  - Goto DEPRECATED
- For each old MN address (already known) in the received LOCATOR
  - State is DEPRECATED
    - Goto UNVERIFIED and send ECHO_REQUEST
  - State is ACTIVE
    - Stay in ACTIVE
- For each new MN address in the received LOCATOR
  - State is UNVERIFIED
    - Send ECHO_REQUEST

Received ECHO_RESPONSE:
- For each MN address in the corresponding LOCATOR
  - State is UNVERIFIED or ACTIVE
    - Goto ACTIVE
    - Change preferred LOCATOR when necessary
  - Any other state, DROP

Receive ESP:
- For the ESP address
  - State is UNVERIFIED

Send ESP:
  - Increase credits

UPDATE retransmission timeout for ECHO_REQUEST (at CN):
  - State is UNVERIFIED
    - If retransmission counter is zero, goto DEPRECATED
    - Otherwise, resend and decrease retransmission counter
  - Any other state
    - DROP and zero retransmission counter

====

---

From: Miika Komu <[email-masked]>
Date: Tue, 11 Apr 2006 19:38:48 +0300 (EEST)

> contain an ECHO_REQUEST rather than be in a separate packet.

Tried to loosen up the rules in favour of modularity. See if it is now
better. Not sure if it covers the peer initiated rekey case. Feel free to
modify the latest proposal accordingly. If you'd still like to discard it,
I think section 5 could still use some kind of summary that gathers up all
of the pieces, even the optional CBA.

> <rest of the comments>

Agree (based on a quick look). Feel free to modify the text accordingly
based on the latest version I sent.

> The other opinions seemed to be to not use CLOSE for this purpose.

Agree.