Subject: RE: [Hipsec] proposal for a few small changes to puzzle mechanism

From: "Henderson, Thomas R" <[email-masked]>
Date: Thu, 24 Jun 2004 19:52:36 -0700

> -----Original Message-----
> From: Tim Shepard [mailto:[email-masked]]
> Sent: Tuesday, June 22, 2004 5:06 AM
> To: Jan Mikael Melen
> Cc: [email-masked]; Henderson, Thomas R
> Subject: Re: [Hipsec] proposal for a few small changes to puzzle
> mechanism 
> 
> So I do not think that telling the client what delay to expect in the
> processing of its I2 is useful.
> 
> TCP retransmits SYN packets much more aggressively than that.

Even in the case of a NOTIFY that "acks" the I2, TCP is still going 
to be retransmitting waiting for the SYN to be acked (and these SYNs 
will pile up internally in the local buffer or be dropped).  This is 
unless HIP implementation has some cross-layer ability to reach into 
TCP and adjust its RTO.

> 
> 
> Note that a lost I2, if not recovered via a quick retransmission, may
> cause a solved puzzle to soon become useless, causing the client
> (perhaps an energy-limited client) to have to start over and solve a
> new puzzle.  That seems to be a severe penalty for a single dropped
> packet.
>

This might be why a NOTIFY (I2-ACK) with expected R2 sending time-- 
after puzzle verification-- might be more useful than a delay parameter 
in the R1, since if you suppress the retransmission of I2, you do not 
know whether the first I2 actually arrived (or whether R2 was lost).

Tom
_______________________________________________
Hipsec mailing list
[email-masked]
http://honor.trusecure.com/mailman/listinfo/hipsec

---

From: Tim Shepard <[email-masked]>
Date: Thu, 24 Jun 2004 23:18:54 -0400

> Even in the case of a NOTIFY that "acks" the I2, TCP is still going=20
> to be retransmitting waiting for the SYN to be acked (and these SYNs=20
> will pile up internally in the local buffer or be dropped).  This is=20
> unless HIP implementation has some cross-layer ability to reach into=20
> TCP and adjust its RTO.

Yes.   I believe some cross layer ability would be a good thing here.

> This might be why a NOTIFY (I2-ACK) with expected R2 sending time--=20
> after puzzle verification-- might be more useful than a delay parameter=20
> in the R1, since if you suppress the retransmission of I2, you do not=20

I agree.  The delay paramter in an R1 would not be useful.
If we imlement an I2-ACK NOTIFY of some sort, then it seems it would
be useful to include the expected delay in sending the R2.   Perhaps
just a number of seconds after receipt of the I2-ACK NOTIFY that the
initiator should retransmit the I2 if it has not yet received an R2.

Now for the hard part, what (if any) new denial of service attacks
would such a mechanism open up that weren't there before?   We'll have
to think about that.

			-Tim Shepard
			 [email-masked]

---

From: Pekka Nikander <[email-masked]>
Date: Fri, 25 Jun 2004 13:11:32 +0300

As a summary of the discussion so far, how about

- Using one byte of the puzzle opaque field to denote
   the puzzle lifetime, in exponential seconds notification.
   I think the time denoted should be the time that the
   puzzle is valid, at minimum, after it has been sent, i.e.
   the time it is still accepted while a new puzzle is
   being distributed.  Consequently, the actual lifetime
   of the puzzle is typically in the range <TTL>..<2*TTL>,
   but may, of course, be longer than <2*TTL>.

   Zero defines the default lifetime, that needs to be
   decided and documented.  How about 128 seconds by default?

- Adding an OPTIONAL I2-ACK packet that a Responder MAY
   send once it has verified the puzzle solution.  That
   packet contains a payload that indicates how long
   the Initiator SHOULD wait before resending I2.  Note that
   since this packet is not crypto-protected, it can be
   potentially forged.  To require that the potential
   attacker can't send such packets without being able
   to eavesdrop the corresponding I2, the packet should
   reflect pack some part of the I2 being acked, e.g.,
   the puzzle solution payload.

To me, the above mechanism seems simple enough, but still
potentially helps in some situations.  IMHO, we should not
go for anything that is much more complex; if someone thinks
about something simpler, the better.  We still don't know
now usual these kinds of congestion situations will be, and
therefore need to get some experience.

Alternative mechanisms would be good, just to get experience
that allows the mechanisms to be compared against each other.

--Pekka

---

From: Tim Shepard <[email-masked]>
Date: Fri, 25 Jun 2004 08:47:55 -0400

Pekka,

Thanks for trying to summarize.

Missing from your summery is any mention of what we identified as a
need for a mechanism for the responder to tell an initiator that even
though it has solved the puzzle, it's puzzle solution has been dropped
as part of a load shedding at the server.  

Jake Beal and I found that the responder, in order to defend itself
against DOS attacks, will need to implement some sort of persistent
dropping mechanism when it needs to shed load by dropping I2s.
Otherwise, an attacker (who has control of some zombies which are
solving puzzles as fast as they can and pretending to have as many
identities as they can) will be motivated to retransmit their puzzle
solutions aggressively in an attempt to give their puzzle solutions a
better chance of occupying a spot in the server's queue than the
legitimate clients.

So, when a responder has decided to drop a valid puzzle solution,
should we have a mechanism to let the initiator know that this has
happened to them?  (And can we have such a mechanism without creating
yet another DOS vulnerability?)

I'm not sure if you deliberately or accidently omitted that mechanism
from your summary.

			-Tim Shepard
			 [email-masked]

---

From: Pekka Nikander <[email-masked]>
Date: Sat, 26 Jun 2004 13:51:56 +0300

> as part of a load shedding at the server.

I see, but see below.

> I'm not sure if you deliberately or accidently omitted that mechanism

Well, it definitely wasn't deliberate in the sense that I would
have considered that case; I'm sorry that I forgot this aspect.

> dropping mechanism when it needs to shed load by dropping I2s.

While I agree with this, I am not sure if it is wise to solve
puzzles and *then* drop packets.  To me, it seems better to drop
packets as early as possible, long before the puzzle solution
gets checked.  It might be a good idea to allow rate limited
ICMP messages to be generated if packets need to be dropped.

> better chance of occupying a spot in the server's queue than the

We still have the Appendix D recommendation, which should limit
the zombies' possibility to select multiple identities, as the
local function f is supposed to be secret and randomly changing.

What comes to retransmitting valid puzzle solutions, AFAIK there
is no way to initially make a difference between valid clients
and zombies who behave like valid clients and generate valid I2.

My current gut feeling is that we will need to give a complete
revisit to the puzzle mechanism anyway before trying to go to
Proposed Standard (if we ever get there).  Hence, I am reluctant
to device too complex mechanisms at this point of time, before we
have any deployment experience.  Adding text, especially appendices,
to the text  is good and fine.  But not to complex behaviour.
Actually, I would prefer either conference papers or IRTF drafts
in this area, preferably with simulations, formal models, or
clearly spelled out analysis.

--Pekka

---

From: gabriel montenegro <[email-masked]>
Date: Mon, 28 Jun 2004 15:14:59 +0200

> clearly spelled out analysis.

Some comments from a lurker's point of view:

- The initial observation of different clients having different processing
speed have led others to search for work functions which are more egalitarian
For example, some memory-bound computations as per:

   http://www.isoc.org/isoc/conferences/ndss/03/proceedings/papers/2.pdf

- Whatever mechanism is chosen, these "proofs of work" are not currently
well-enough understood, it seems (implementors may have other comments here).

- The cookie puzzle mechanism may have IPR implications. Anybody know? Based on the
original publication in NDSS'99 it seems probable. At any rate, this might be
an issue for basic HIP.

Because of the above, would it be out of the question to simply jettison the
cookie puzzle mechanism out of basic HIP and pursue it (and any variants
thereof) instead in the research group? The HIP WG could perhaps work on a
simpler IKEv2-style DoS protection mechanism.

-gabriel

---

From: Pekka Nikander <[email-masked]>
Date: Mon, 28 Jun 2004 21:28:23 +0300

>   http://www.isoc.org/isoc/conferences/ndss/03/proceedings/papers/2.pdf

We discussed the memory bound functions briefly after NDSS, but back
at that time decided to stick to hash based things.  There are also
newer results in the queue, to be published somewhere sometime.
(Not my papers but papers that I've seen for some reason before
publication, and most probably others that I haven't seen.)

> well-enough understood, it seems (implementors may have other comments 

 From an operational point of view, I do agree.

> original publication in NDSS'99 it seems probable. At any rate, this 

Good point.  However, at least

C. Dwork and M. Naor. Pricing via processing or combatting junk mail.
In Ernest F. Brickell, editor, CRYPTO ’92, pages 139–147. Springer-
Verlag, 1992.

exists, and that may represent prior art.

> simpler IKEv2-style DoS protection mechanism.

I think the current cookie mechanism is pretty well thought, 
simultaneously
fairly simple and fairly flexible.  IMHO, getting some operational 
experience
would be quite important at this point of time.

--Pekka

---

From: Jan Mikael Melen <[email-masked]>
Date: Wed, 30 Jun 2004 10:27:47 +0300

Hi,

Here is proposed text in a form of context diff (Comments?):

diff -c draft-ietf-hip-base-00.xml draft-ietf-hip-base-01-pre1.xml
*** draft-ietf-hip-base-00.xml	Wed Jun 30 10:17:48 2004
--- draft-ietf-hip-base-01-pre1.xml	Wed Jun 30 10:17:48 2004
***************
*** 607,615 ****
            <t>
              To generate a proper number J, the Initiator will have to
              generate a number of Js until one produces the hash target
!             of zero.  The Initiator SHOULD give up after trying 2^(K+2)
!             times, and start over the exchange.  (See <xref
!             target="cookie-probability" />.)  The Responder needs to
              re-create the concatenation of I, the HITs, and the provided
              J, and compute the hash once to prove that the Initiator did
              its assigned task.
--- 607,614 ----
            <t>
              To generate a proper number J, the Initiator will have to
              generate a number of Js until one produces the hash target
!             of zero.  The Initiator SHOULD give up after exceeding the
!             puzzle lifetime received in PUZZLE TLV.  The Responder needs to
              re-create the concatenation of I, the HITs, and the provided
              J, and compute the hash once to prove that the Initiator did
              its assigned task.
***************
*** 1945,1951 ****
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |             Type              |             Length            |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!    | K, 1 byte     | Opaque, 3 bytes                               |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     | Random # I, 8 bytes                                           |
     |                                                               |
--- 1944,1950 ----
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |             Type              |             Length            |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!    | K, 1 byte     |    Lifetime   |        Opaque, 2 bytes        |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     | Random # I, 8 bytes                                           |
     |                                                               |
***************
*** 1954,1974 ****
     Type           5
     Length         12
     K              K is the number of verified bits
     Opaque         Data set by the Responder, indexing the puzzle
     Random #I      random number
  
              </artwork>
            </figure>
            <t>
!             Random #I is represented as 64-bit integer, K as 8-bit
!             integer, all in network byte order.
            </t>
            <t>
              The PUZZLE parameter contains the puzzle difficulty K and an
!             64-bit puzzle random integer #I.  A puzzle MAY be augmented
!             by including an ECHO_REQUEST parameter to an R1.  The
!             contents of the ECHO_REQUEST are then echoed back in
!             ECHO_RESPONSE, allowing the Responder to use the included
              information as a part of puzzle processing.
            </t>
  
--- 1953,1978 ----
     Type           5
     Length         12
     K              K is the number of verified bits
+    Lifetime       Puzzle lifetime 2^(value-32) seconds
     Opaque         Data set by the Responder, indexing the puzzle
     Random #I      random number
  
              </artwork>
            </figure>
            <t>
!             Random #I is represented as 64-bit integer, K and Lifetime 
!             as 8-bit integer, all in network byte order.
            </t>
            <t>
              The PUZZLE parameter contains the puzzle difficulty K and an
!             64-bit puzzle random integer #I.  Puzzle Lifetime indicates 
!             the time during which the puzzle solution is valid and 
!             sets a time limit for initiator which it should not exceed 
!             while trying to solve the puzzle.  The lifetime is indicated 
!             as power of 2 using formula 2^(lifetime-32) seconds.  A puzzle 
!             MAY be augmented by including an ECHO_REQUEST parameter to an
!             R1.  The contents of the ECHO_REQUEST are then echoed back in 
!             ECHO_RESPONSE, allowing the Responder to use the included 
              information as a part of puzzle processing.
            </t>
  
***************
*** 1986,1992 ****
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |             Type              |             Length            |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!    | K, 1 byte     | Opaque, 3 bytes                               |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     | Random #I, 8 bytes                                            |
     |                                                               |
--- 1990,1996 ----
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |             Type              |             Length            |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!    | K, 1 byte     |   Reserved    |        Opaque, 2 bytes        |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     | Random #I, 8 bytes                                            |
     |                                                               |
***************
*** 1998,2003 ****
--- 2002,2008 ----
     Type           7
     Length         20
     K              K is the number of verified bits
+    Reserved       zero when sent, ignored when received
     Opaque         Copied unmodified from the received PUZZLE TLV
     Random #I      random number
     Puzzle solution
***************
*** 2735,2740 ****
--- 2740,2762 ----
        for some policy reason (e.g. received HIT is NULL 
        and policy does not allow opportunistic mode).
        
+    SERVER_BUSY_PLEASE_RETRY                  44
+ 
+       The resonder is unwilling to set up an association
+       as it is suffering under some kind of overload and
+       has chosen to shed load by rejecting your request.
+       You may retry if you wish, however you MUST find 
+       another (different) puzzle solution for any such 
+       retries. Note that you need to obtain a new puzzle 
+       with a new I1/R1 exchange.
+ 
+    I2_ACKNOWLEDGEMENT                        46
+ 
+       The responder has received your I2 but had to queue 
+       the I2 for processing. The puzzle was correctly solved
+       and the responder is willing to set up an association 
+       but has currently a number of I2s in processing queue.
+       R2 will be sent after the I2 has been processed.

     NOTIFY MESSAGES - STATUS TYPES           Value

---

From: Jake Beal <[email-masked]>
Date: Wed, 30 Jun 2004 07:51:48 -0400

I only see one small problem, in the definition of the
SERVER_BUSY_PLEASE_RETRY message:

...

A new I1/R1 exchance is only necessary if the puzzle's timelimit
has expired. Otherwise, the initiator can simply continue searching
for more solutions to the current puzzle. 

I would propose changing the language to:
+       retries. Note that you may need to obtain a new puzzle 
+       with a new I1/R1 exchange.

Thanks,
-Jake