Subject: [Hipsec] Issue 12: Birthday check badly defined

From: [email-masked] (Henderson, Thomas R)
Date: Mon May 3 21:24:01 2004

> > In essence, this R1 counter is only needed
> > because R1s are precomputed and stateless with respect
> > to the I1.  If my thinking is wrong, it would be useful
> > to document the attack scenario clearly.  And if people
> > agree with the above, then we need to make some changes
> > to R1 processing, and to the I2 processing perhaps when
> > in state R2-SENT (because a new I2 based on newer R1
> > may be forthcoming).  "Birthday" may be the wrong term
> > for this counter.
>=20
> We seem to mostly agree.  I think that "R1 generation counter"
> might be a better name for the value.  There seems to be
> two rules governing it:
>=20
>    - it must be strictly incremented (never decrease)
>    - it must be incremented every time old R1s cease
>      to be valid
>=20
> Could you suggest modifications to the current text?
>=20
> --Pekka

Here is an initial cut at the main changes-- if agreeable, I can=20
propose other alignment of the text to Petri.

4.1.3 HIP replay protection
    =20
   The HIP protocol includes the following mechanisms to protect against
   malicious replays.  Responders are protected against replays of I1
   packets by virtue of the stateless response to I1s with presigned
   R1 messages.  Initiators are protected against R1 replays by a
   monotonically increasing "R1 generation counter" included in the R1.
   Responders are protected against replays or false I2s by the cookie
   mechanism (Section 4.1.1 above), and optional use of opaque data. =20
   Hosts are protected against replays to R2s and UPDATEs by use
   of a less expensive HMAC verification preceding HIP signature
   verification.

   The R1 generation counter is a monotonically incrementing 64-bit
   counter that MUST be initialized to zero.  It is a system-wide=20
   counter that keeps state across system reboots and invocations of=20
   the HIP signaling process.  This counter indicates the current=20
   generation of valid cookie puzzles.  It MUST be incremented at=20
   least as often as every time old R1s cease to be valid, and=20
   SHOULD never be decremented, lest the implementation expose itself=20
   to the replay of previously generated, higher numbered R1s. =20

   A host may receive more than R1, either due to sending multiple I1s
   (Section 8.4.1) or due to a replay of an old R1.  When sending=20
   multiple I1s, an initiator SHOULD wait for a small amount of time
   after the first R1 reception to allow possibly multiple R1s to=20
   arrive, and it SHOULD respond to an R1 among the set with the=20
   largest R1 generation counter.  If an initiator is processing
   an R1 or has already sent an I2 (still waiting for R2) and it=20
   receives another R1 with a larger R1 generation counter, it MAY
   elect to restart R1 processing with the fresher R1, as if it were
   the first R1 to arrive.

6.2.4 R1_COUNTER

      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |             Type              |             Length            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      | Reserved, 4 bytes                                             |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      | R1 generation counter, 8 bytes                                |
      |                                                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      Type           3
      Length         16
      R1 generation counter   The current generation of valid puzzles

   The R1_COUNTER parameter contains an 64-bit unsigned integer in =
network
   byte order, indicating the current generation of valid puzzles.  The
   sender is supposed to increment this counter periodically.  It
   is RECOMMENDED that the counter value is incremented at least as
   often as old PUZZLE values are deprecated so that SOLUTIONs to them
   are no more accepted.

Open issues:
i) is R1_COUNTER an optional or mandatory parameter to include in R1?
ii) is 64 bits still the right length for this?
iii) is there any value in putting this parameter in the I2 (may be=20
useful if initiator sends two I2s, in determining whether responder=20
bothers with subsequent received I2s or ignores them)?
iv) how to address modulo sequence number comparisons-- what is the=20
acceptable window of R1 counter values-- what do you do if you get two=20
R1s with vastly different counters (is this even an issue)?
v) should we specify that R1 counter values are not cached-- are flushed
after a HIP association goes away?

---

From: [email-masked] (Pekka Nikander)
Date: Tue May 4 02:32:00 2004

> Here is an initial cut at the main changes-- if agreeable, I can

Looks very good.  Minor issues and some nits below.

>    mechanism (Section 4.1.1 above), and optional use of opaque data.
>    counter that MUST be initialized to zero.  It is a system-wide
                  SHOULD

I don't see any reason why it should be initialised to zero.
That prevents one from using date&time, which is a viable option
for some implementations.

I think the scope MAY be system-wide but SHOULD be per HI?

>    counter that keeps state across system reboots and invocations of
>    the HIP signaling process.  This counter indicates the current
>    generation of valid cookie puzzles.  It MUST be incremented at
     generation(s)

>    least as often as every time old R1s cease to be valid, and
>    SHOULD never be decremented, lest the implementation expose itself

"expose itself" or "expose its peers" ?

>    to the replay of previously generated, higher numbered R1s.

>    (Section 8.4.1) or due to a replay of an old R1.  When sending
>    after the first R1 reception to allow possibly multiple R1s to
>    arrive, and it SHOULD respond to an R1 among the set with the
>    an R1 or has already sent an I2 (still waiting for R2) and it

I think the text above is very good, very balanced.  Most probably
we want to tighten it up, but only later, with experience.  Or at
least I don't know how to tighten it without unnecessarily killing
various interesting implementation options.

>    The R1_COUNTER parameter contains an 64-bit unsigned integer in 
> network
                                        generation(s)

>    often as old PUZZLE values are deprecated so that SOLUTIONs to them

     Note that an implementation MAY accept several generations of 
puzzles at
     any given time.  It is RECOMMENDED that an implementation accepts at
     least two consequent generations of puzzles.

> i) is R1_COUNTER an optional or mandatory parameter to include in R1?

Optional and non-critical but RECOMMENDED sounds right to me.  Some
implementations may not be able to implement it since they don't have
stable storage.  When included, it is covered with the signature, and
therefore one can't create spoofed R1s without it when the real host
would be providing it.  Non-critical since some hosts may opt not to
pay any attention to it.

> ii) is 64 bits still the right length for this?

IMHO, 32 bits is not enough.  Something like 40 or 48 bits might
be sufficient, but going directly to 64 is as easy.

> iii) is there any value in putting this parameter in the I2 (may be
> useful if initiator sends two I2s, in determining whether responder

Hmm.  I don't have any strong opinion.  A sane initiator would include
the relevant information in the Opaque/#I fields in the puzzle, or if
not sufficient, to the ECHO_REQUEST.  Hence, I don't think it is needed.
But if someone wants to include it there, why not.  In that case I think
we should require the implementations to echo back also the reserved
field.

> iv) how to address modulo sequence number comparisons-- what is the
> acceptable window of R1 counter values-- what do you do if you get two

I added above the recommendation that at least two consequent 
generations
of puzzles are accepted.  Hence, the window size would be 2.

I don't see any issues with vastly different counters.  The smaller one
is just very old replay.

> after a HIP association goes away?

Yes, I think the counter values SHOULD be flushed.  A local policy MAY
override this on per-HIT bases, though.  The default MUST be to flush
them.  That's erring on robustness on the cost of security, which IMHO
is the right way here.  But YMMV.

--Pekka