Subject: [Hipsec] Issue 3: NES and REA

From: [email-masked] (Pekka Nikander)
Date: Sun Sep 14 09:49:02 2003

The goal of this mail is to try to clarify the NES/REA
situation.  Currently I think that there are some
problems, but I'd like to get comments from those that
really have implemented NES (we haven't).

This mail is somewhat long but an important one, that is,
if we want to get the base protocol finished before
Minneapolis.  I think this NES thing is the largest
unresolved issue in the base protocol.  All of the other
hard parts we have either solved or moved to separate
drafts.

Once you have read the mail (it will take 10 minutes
at most), please answer to the following two questions.
If you don't care, a personal note indicating so would
be appreciated.

   1. Is the new NES scheme, described at the end,
      acceptable?  If yes, no more questions.

   2. If the new scheme is not OK, please explain why,
      and where there is a flaw in my analysis, if any.

Background example
------------------

   After the base exchange, before any NES packets are
   sent, all keys all derived from a single piece of
   keying material:

     K1 = SHA1( g^xy | HITs | 0x01 )
     K2 = SHA1( g^xy | K1   | 0x02 )
     ...
     K  = K1 | K2 | ...

   The ESP SAs used to send traffic between the parties,
   say SPI1 and SPI2, use keys derived from this keying
   material.

   Let's now assume that the first party sends a NES,
   thereby replacing its public Diffie-Hellman key g^x
   with a new key, say g^z.  As a result, the second
   party must now generate a new piece of keying material.
   The first party has to have this keying material
   ready when it sends the NES, since it must be prepared
   to receive packets using this new keymat.

     K1' = SHA1( g^zy | HITs | 0x01 )
     ...
     K'  = K1' | K2' | ....

   As a result of this, the keys for the new SPI used
   for sending packets to the first party, SPI1', is
   derived from this new keymaterial, KEYMAT K'.  At this
   point, the SPI used for sending packets to the second
   party remains the earlier one, SPI2, and is still
   based on KEYMAT K.

   Let's suppose further that the second party's policy
   states that it is also to update its Diffie-Hellman
   whenever it receives a new Diffie-Hellman key.  It
   generates a new Diffie-Hellman public key, say g^t,
   and sends it in another NES to the first party.  The
   first party has to generate another piece of keying
   material, this time using both of the new D-H keys:

     K1'' = SHA1(g^zt | HITs | 0x01 )
     ...
     K''  = K1'' | K2'' | ....

   As a result, the first-to-second-party SPI is now
   SPI1', based on K', and the second-to-first-party SPI
   is SPI2', based on K''.

Problem statement
-----------------

   If suspect that the following two hold.  If they do
   not, the rest of this message is false and I must start
   my thinking process anew.

     1. It is desirable to update the SAs in both
        directions so that they use keys from the
        same KEYMAT.

     2. In the majority of cases, there will be a
        pair of D-H updates and not just a single one.

   If these hold, there are two basic variants of
   NES exchanges, the latter being more common than
   the former:

     Simplex NES exchange:

               NES including D-H
        ------------------------------->
               NES without D-H
        <-------------------------------

     Duplex NES exchange:

               NES including D-H
        ------------------------------->
               NES including D-H
        <-------------------------------
               NES without D-H
        ------------------------------->

   As a consequence of this setting, I see the
   following problems:

     P1. Using the current processing rules, the
         sender of the first NES usually needs
         to generate two new KEYMAT sets.

	It needs to generate the first set before
         sending the NES, using its own new
         D-H key and its peer's old D-H key.
         This must be there so that if the peer
         opts for the simplex exchange, the host
         is ready to receive packets.

         It needs to generate the second set after
         receiving the D-H containing NES from its
         peer.

         This is a performance problem.

     P2. It is possible that both parties become
         unable to receive data due to crossing
         NESes.

         Consider the following scenario, with NES
         packets crossing each other:

              ----------   ----------
                        \ /
                         X
                        / \
              <--------/   \-------->

         In this case, both parties will consider
         the receives NES packets be replies to
         the ones they previously sent, and
         start sending packets with g^tz.  At the
         same time, they will expect the peer to
         send packets with half-updated (g^zy or g^xt)
         associations, until the final NES packets
         without D-H arrive.  According to the current
         rules, this will break the communications,
         at least temporarily.

Proposal
--------

   I would propose that we add an acknowledgement to
   the NES, and make the exchange always exactly
   two messages long.  This seems to solve the above
   mentioned problems.   Let the ack be called NESA, and
   consider the following.

   Simplex NES exchange:

     Generate g^z.
     Do not generate
     KEYMAT yet.

               NES: SPI1', D-H (g^z)
        ------------------------------->

                                    Continue using SPI1.
                                    Generate KEYMAT K'.
                                    Prepare SPI2'.
               NESA: SPI2'
        <-------------------------------

     Generate KEYMAT K'.
     Prepare SPI1'.
     Switch over from SPI2 to SPI2'.

               ESP: SPI2'
        ------------------------------->

                                    Switch over from SPI1
                                    to SPI1'

   Duplex NES exchange:

     Generate g^z.
     Do not generate
     KEYMAT yet.

               NES: SPI1', D-H (g^z)
        ------------------------------->

                                    Continue using SPI1.
                                    Generate g^t.
                                    Generate KEYMAT K''.
                                    Prepare SPI2'.

               NESA: SPI2', D-H (g^t)
        <-------------------------------

     Generate KEYMAT K''.
     Prepare SPI1'.
     Switch over from SPI2 to SPI2'.

               ESP: SPI2'
        ------------------------------->

                                    Switch over from SPI1
                                    to SPI1'.

   Crossing NES exchange:

     Generate g^z.                  Generate g^t.
     Do not generate                Do not generate
     KEYMAT yet.                    KEYMAT yet:

         SPI1', g^z       SPI2', g^t
        --------------   ---------------
                      \ /
                       X
                      / \
        <------------/   \------------->

     Continue using SPI2.           Continue using SPI1.
     Generate KEYMAT K''.           Generate KEYMAT K''.
     Prepare SPI1'.                 Prepare SPI2'.

         NESA: ack        NESA: ack
        --------------   ---------------
                      \ /
                       X
                      / \
        <------------/   \------------->

     Switch over from SPI2          Switch over from SPI1
     to SPI2'.                      to SPI1'.

     Note that even if the NESAs don't cross, or
     if just one of them is passed, the party first
     receiving the NESA will swich to the new SA,
     and as the other one starts receiving data on
     it, it will switch over too.

Further work
------------

   Depending on the outcome of this consideration, I will
   continue working on unifying REA and NES.  In a way,
   the NES acknowledgement would correspond to the current
   AC, and it may be possible to remove ACR.

--Pekka Nikander

---

From: [email-masked] (Andrew McGregor)
Date: Sun Sep 14 21:40:02 2003

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

>       acceptable?  If yes, no more questions.

It looks fine to me.

>       and where there is a flaw in my analysis, if any.

<snip>

>          This is a performance problem.

It would be, except my code doesn't do this; instead, it delays any DH work 
until receiving an NES, and continues to use the old SA until then, in 
which case it is delaying the work until it knows what to do.  However...

>          unable to receive data due to crossing

I had not realised why, but I have seen this happen (and the hosts recover 
at the next rekey where the NES did not cross).

The proposal makes plenty of sense in this light.

May I suggest a generic HIP ACK with a field indicating what packet type is 
being ACKed?  So we can have ACK(AC) or ACK(NES) (or anything else that may 
be needed).  I guess type-specific additional fields can be added if 
necessary.

Andrew

- --------
Andrew McGregor
Director, Scientific Advisor
IndraNet Technologies Ltd
http://www.indranet.co.nz/
Office: +64 3 3656485
Mobile: +64 21 898856

---

From: [email-masked] (Pekka Nikander)
Date: Mon Sep 15 03:42:03 2003

>>      acceptable?  If yes, no more questions.

Good.  I am still waiting for replies from others.

> be needed).  I guess type-specific additional fields can be added if 

Well, I am planning to see if it would be possible to revise
the REA procedure so that it would also consist of only two
packets.   If that is possible, then REA would basically be just
NES + NESA, with one or more additional REA_INFO parameters.
However, I haven't had time to analyse the situation, and therefore
I don't have a proposal.

This is also related to Issue 5: Rules for extensions.
My aim is to propose a way where any packet could include
additional parameters, not just NES/NESA.  That would
allow embedding REA_INFO also in I2 and R2, making it easier
to establish the initial multihoming/mobility situation
already during the base exchange.  However, there are
some security problems related to such practise, and I haven't
had time to properly think about them yet.

In this light, I don't think it would be good to have a generic
ack.  While such practise might be good from a basic protocol
design point of view, there might be security complications.
It looks like that in most cases where you would benefit from
a simple ACK, you can do the same by changing your SPI and wait
for data to start appearing on the new SPI.

--Pekka Nikander

---

From: [email-masked] (Andrew McGregor)
Date: Tue Sep 16 22:44:01 2003

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

- --On Monday, September 15, 2003 11:07:26 AM +0300 Pekka Nikander 
<[email-masked]> wrote:

>> May I suggest a generic HIP ACK with a field indicating what packet type
>> is  being ACKed?  So we can have ACK(AC) or ACK(NES) (or anything else
>> that may  be needed).  I guess type-specific additional fields can be
>> added if  necessary.
>

Well, my implementation manages to do it in two every time, except that it 
doesn't work in the NES packets cross case.  I think if NESs have a 
timestamp, sequence number, or a nonce in them so we can tell that any 
given NES is or is not a reply to one we sent previously then we can solve 
this case.  What I do is flag that I've sent an NES, and incoming NESs are 
processed slightly differently if the flag is set or not, but this doesn't 
work in the crossing case.  By the way, it's easy to test these things; 
just set a short rekey timeout, and crossing can be tested by setting it 
the same at both ends.  The window for a cross is actually quite large (a 
second or so, I think).

> had time to properly think about them yet.

Hmm.  Yes, that could be messy.

> for data to start appearing on the new SPI.

Of course you can.  Silly me :-)

Andrew

- --------
Andrew McGregor