Subject: [Hipsec] Cookies

From: [email-masked] (Pekka Nikander)
Date: Fri Apr 2 09:06:00 2004

Jon,

[Sorry for the delayed response.]

> I'm getting familiar with HIP, and I was wondering
> about the design rational behind the way cookies
> are currently defined. I am curious why something
> like SCTP's cookie method wasn't chosen.

IIRC, there were a number of goals behind for
the current design:

- To include the puzzle.  This makes it impractical
   to have SCTP like opaque cookies.

- To make it possible for the Initiator to check
   that the puzzle has really been generated by the
   right Responder.  This may be desirable for the
   harder puzzle difficulty levels.

- To give the Responder still various options to
   implement the cookies in different ways.  I think
   there is still an appendix explaining some of the
   things that you can do.  The goal is to allow the
   responder to make the choice of how much state vs.
   CPU it would like to use for cookie handling.

- And of course, still keep the Responder stateless.

Note also that in the later stages, we wanted to
explicitly include the HITs into the puzzle, in order
to make it impossible to replay the same puzzle solution
with different HITs, and to allow the responder to select
a suitable cookie based on the initiator IP address,
thereby making it impossible to replay a single puzzle
solution from multiple IP addresses.

I'm too tired right now to be able to figure out
if you could achieve these goals with opaque cookies.
Maybe.  Feel free to propose an alternative cookie
design.  If it is more flexible, IPR free, and provides
at least the same benefits, I don't personally see any
reasons why we couldn't adopt one.

> Another issue I see with the current mechanism is that
> the puzzle I is precomputed, since it is protected by
> the signature presumably. This means that an attacker
> can solve the puzzle once and then try to pound the
> responder by forcing it to do lots of work verifying signatures
> and such. This window of opportunity for attack lasts for
> the lifetime of the precomputed cookie.

Yes, but there are ways to mitigate this.  See the
appendix.

> The root problem here seems to be that I is protected by
> the signature, so responders can't hand out a new I in
> each R1. So just how important is it that the I is protected
> by the signature?

Well, now that we have the WG it is up to the WG to
decide how important that is.  However, the rationale
behind that is that you would like to support use cases
where the puzzle is very hard, and there you may want
to check that you are solving the right puzzle before
you start solving that...

--Pekka

---

From: [email-masked] (Jonathan Wood)
Date: Fri Apr 2 19:00:01 2004

> reasons why we couldn't adopt one.

OK, I'll write something up and send it to the list.

> Yes, but there are ways to mitigate this.  See the

I did - which is why I started thinking "Is there a simpler
way to do this?" :)

Jon

---

From: [email-masked] (JW)
Date: Tue Apr 6 06:27:05 2004

There are two changes proposed. Each is somewhat independant of the 
other.

1. Make the birthday cookie TLV variable-length. All other fields are
    identical. The responder MAY put some additional data in this field
    to help it verify that it has received an answer to the exact puzzle
    it proposed, and that the sender of the I2 is the same as the sender
    of the I1. If there is any additional data in the cookie received in
    the R1, the initiator MUST copy this data unchanged to the cookie
    it includes in the I2.

    The rational for this is that implementations can opt to not use
    the opaque field in favor of something akin to the approach described
    in the appendix. However, it offers greater flexibility to
    implementations that wish to use another approach (such as the one
    I describe below).

2. For the cookie included in an R1, the signature field does not cover
    the I or K values. If there is any additional data in the cookie's
    opaque field, the signature also does not cover that data. When
    computing the signature, these fields MUST be set to zero. Before
    verifying the signature, these fields must be saved, set to zero,
    and then restored after verifying the signature. For the cookie
    included in an I2, the signature covers the entire cookie (this
    should simplify processing).

    The idea here is that if an implementation has a cheap source of
    random numbers, the responder can hand out a new puzzle to each
    I1 without needing to recompute a signature. The K is also left
    outside the signature since if a responder is experiencing heavy
    load and wishes to slow down initiators by increasing K, the last
    thing it wants to do is to undertake an expensive signing operation.
    I can't see any security problems with this right now, but if
    there are any, this suggestion is weakened.

The new cookie TLV would look like this:

6.2.4 BIRTHDAY_COOKIE

        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                            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       | Birthday, 8 bytes                                             |
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       | Random # I, 8 bytes                                           |
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       | K or Random # J, 8 bytes                                      |
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                             Opaque                            /
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       /                                               |    Padding    |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

       Type           3 (in R1) or 5 (in I2)
       Length         length in octets, excluding Type, Length, and 
padding
       Reserved       Zero when sent, ignored when received
       Birthday       System boot counter
       Random # I     random number
       K              K is the number of verified bits (in R1 packet)
       Random # J     random number (in I2 packet)
       Opaque         opaque bytes (possible zero), set by responder and
                      returned unchanged by initiator.

    Birthday, Random #I, K, and Random #J are represented as 64-bit
    integers, in network byte order.

An Example: Handling Cookies with Opaque Data

On startup, a HIP implementation pre-computes and signs an R1 with an
empty cookie (i.e. the I, K, and opaque fields are zero). It also
creates a new random secret.

Upon receiving an I1, the responder randomly generates a new I, sets K
according to its load and trust of the initiator, and places these
values in the cookie in the pre-computed R1. It then concatenates
the initiator's HIT, and the I, and K values from the cookie, and
creates a MAC using this data and the secret as the key. The MAC and
K are placed in the cookie's opaque field.

When the responder receives an I2, it first ensures that the opaque
field is large enough to contain the K and the MAC, dropping the
packet if not. The responder then recreates the MAC by combining the
initiator's HIT, the I, and the K from the opaque data, using the
same secret as above. If the MAC matches, the responder proceeds with
verification of the puzzle solution.

A HIP implementation should periodically change its secret. When doing
so, it should store the previous value of the secret for a short time
in case the secret change occured in between sending an R1 and receiving
an I2. If the MAC verification fails with the current secret, the
responder should retry the verification with the previous secret.

---

From: [email-masked] (Pekka Nikander)
Date: Tue Apr 6 13:44:03 2004

Jon,

(Please subscribe with the address you want to post with,
or let me know your alternate posting addresses so that
I can add them explicitly to the list filters.  Makes posting
faster.)

>    identical.

Sounds good to me, on first reading.

>    the I or K values.

I'm not convinced, but I'll consider this more.  I'll just need
some flow time, and can't foresee when I'll have it.  Anyone else,
a security analysis/comparison, even a straw man one?

--Pekka