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

From: Tim Shepard <[email-masked]>
Date: Fri, 18 Jun 2004 15:07:10 -0400

Jake Beal (CC: above) and I have been thinking about the puzzle
mechanisms and how to implement a server in a way that allows it to
defend itself against attack.  (We are working on a paper.)

We believe there are a few minor things about the way the puzzle
mechanism is described in draft-ietf-hip-base-00.txt that need to be
improved to allow for robust implementation of the puzzle mechanism.

Use elapsed time, not number of solutions tried
-----------------------------------------------

In section 4.1.1 HIP Cookie Mechanism, it says the client SHOULD
give up after trying 2^(K+2) different numbers for J.  Appendix C
describes the probabilities for finding a solution given a number of
tries.

Since different clients may have widely differing processing speeds,
we believe it would be better if the client should try for a given
amount of time before giving up.  Otherwise, allowing sufficient
time for slow clients to submit solutions impedes the servers
deprecation of old puzzles.

Note that giving up and retrying with a new puzzle does not increase
the total expected time (or cycles) spent finding a valid puzzle
solution. (For example, 50 tries with one puzzle and 50 tries with
another puzzle is just as likely to produce a solution as 100 tries
with one puzzle.)

What a client needs to know is not how many tries it should make,
but rather for how long in the future will a solution to this puzzle
be accepted by the server.

So either the protocol should deliver a number of seconds with a
puzzle to tell the client how much time it may spend trying to solve
this puzzle, or a fixed amount of time (one minute?, two minutes?)
should be specified in the protocol.

Note that this could obviate the need for the R1 counter mechanism,
and we believe that a time-remaining mechanism is simpler and more
reliable than a counter mechanism.  (Note that a time-remaining
mechanism is significantly less demanding than the timestamp
mechanism considered earlier.)

Note this still will leave many options for the server.  The server
could continue to issue or accept the same puzzle far beyond the
explicit or implicit timeout implied by delivering the puzzle in any
particular R1 packet.  A client that that tried to solve a puzzle
and ran out of time will perform a new I1-R1 exchange, and then
continue to search for a puzzle solution with whatever puzzle
arrives in the new R1.  The server may have reissued the same
puzzle, in which case the client should make sure that it will not
retry the same set of J values that failed to find a solution last
time.  (A little randomness here would suffice.)

So if you like our proposal to use elapsed time instead of number of
J values tried, we need to decide whether how long the puzzle should
be valid is carried explicitly in the R1 packet or is simply written
into the protocol specification (and carried implicitly by the
delivery of a puzzle in an R1 packet).

Appendix C should be revised (or perhaps removed?) if this proposal
is adopted.

Dropping I2s to shed load
-------------------------

Servers need to be able to shed load.  Even with the puzzle
mechanism, it is possible for a server to be overwhelmed with valid
I2s and some of those I2s will need to be dropped (as they overflow
the queue for processing of the DH exponentiation).

How the server should tune the puzzle difficulty remains an
interesting research question.  No matter what mechanism is used to
tune the difficulty of the puzzle, we believe there will still be
scenarios where the arrival rate of I2s exceeds the server's capacity
to process them (e.g. flash crowds).

It must not be the case that aggressive retransmission of puzzle
solutions improves the chances of an attacker's puzzle solutions being
serviced.  Therefore the server will need to remember (with perhaps a
Bloom filter) what legitimate puzzle solutions have already been
submitted, so that they can be persistantly dropped.

When the server sheds load by choosing to persisitantly drop the
puzzle solution presented in an I2, we need a mechanism to say to the
client:

   Your puzzle solution was recevied by the server and was valid.
   However, the server 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 may need to obtain a
   new puzzle with a new I1/R1 exchange (e.g. if there is not
   sufficient time left or if the puzzle and/or puzzle difficulty has
   been changed).

It seems like a new NOTIFY parameter (e.g. SERVER_BUSY_PLEASE_RETRY)
would satisfy this need.   

Acknowledge I2s before sending R2s?
-----------------------------------

When the server's queue for processing I2s is long, and the network
path has a significant drop rate, then there is no good way for the
client to set the timer for retransmission of the I2 packet.  If there
was some way to separate the communication delay from the server's
queueing and processing delay, then the client could set the
retransmission timer for the I2 more appropriately.

So should receipt of a valid I2 be acknowledged, perhaps optionally
depending upon the anticipated delay before the server can produce
an R2?

If there should be this acknowledgement mechanism, should it also be
done with a NOTIFY paramater?

	-Tim Shepard
	 [email-masked]

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

---

From: Tim Shepard <[email-masked]>
Date: Sun, 20 Jun 2004 13:14:00 -0400

> mechanism considered earlier.)

Well, we weren't thinking of the replay protection that the R1 counter
mechanism is supposed to provide when we said that.

So ignore that paragraph.

Our motivation for the time-remaining mechanism is to replace the
2^(K+2) tries since there is no good way to tune for how long
solutions to a given puzzle should be accepted if the clients have
widely varrying processing speeds.

Man in the middle attacks aimed at denial of service are difficult
(impossible?) to defend against with end-to-end protocols.   So I'm
not sure that there is any effective mechanism for defending against a
MITM attack which wants to reply old R1 packets.

			-Tim Shepard
			 [email-masked]

---

From: Pekka Nikander <[email-masked]>
Date: Mon, 21 Jun 2004 11:59:11 +0200

Tim,

> widely varrying processing speeds.

I think that (at least) this part of your proposal is very
worth of adopting.  (I haven't had time to really think about
the rest.)

Do you have a any preference whether to use a global value or
add an option to the base protocol now?   Remember that such
an option could always be added later, now that we have this
extensible protocol.

--Pekka

---

From: Jan Mikael Melen <[email-masked]>
Date: Mon, 21 Jun 2004 15:11:02 +0300

Hi,

> an option could always be added later, now that we have this

I think that this should be optional TLV in the R1 and if present one should 
not try to solve the puzzle longer than the time-remaining indicates or 
2^(K+2) times.

What do others think?

> > Dropping I2s to shed load

If we would have a server busy notification wouldn't that be a way for the 
attacker to know that she has succeeded, if she is trying to just overload 
the server?

> > Acknowledge I2s before sending R2s?

I don't think this is really necessary nor wise. I think this just adds 
complexity that really is not needed. What would the initiator do when he 
receives this notification? Double the timer for waiting R2? Would these 
notifications be sent periodically until the R2 is sent?

   Regards,
	Jan

---

From: Julien Laganier <[email-masked]>
Date: Mon, 21 Jun 2004 14:12:18 +0200

On Sunday 20 June 2004 19:14, Tim Shepard wrote:
> > Note that this could obviate the need for the R1 counter
> > mechanism, and we believe that a time-remaining mechanism is
> > simpler and more reliable than a counter mechanism.  (Note that a
> > time-remaining mechanism is significantly less demanding than the
> > timestamp mechanism considered earlier.)
>
> Well, we weren't thinking of the replay protection that the R1
> counter mechanism is supposed to provide when we said that.
>

I agree with the proposed changes... Indeed, my implementation gave up 
after 10 seconds of failed attempts to solve the puzzle.

Tnx,

--julien

---

From: Kristian Slavov <[email-masked]>
Date: Thu, 24 Jun 2004 10:54:13 +0300

> not try to solve the puzzle longer than the time-remaining indicates or 

The time-remaining parameter sounds reasonbale.
I think the 2^(K+2) limit is a bit artificial. I don't think that the 
probability of succeeding to solve the puzzle increases if we have to fetch
another cookie. Also, it should be impossible to create a puzzle that has no
correct solution.
The initiator wants to make the connection, so he is willing to do some work.
I think it is in the best interest of the initiator to solve the puzzle as fast 
as possible, regardless of the tries required to solve a single puzzle.

> notifications be sent periodically until the R2 is sent?

What if an attacker sends many of these notifications that double the timer?

Perhaps it would be better (or at least more simple) to just drop the I2s, if 
there is too much load and have the initiator employ some kind of backoff 
algorithm when resending I2s.

-- 
Kristian Slavov, Researcher
Helsinki Institute for Information Technology
Gsm: +358-40-7220960
_______________________________________________
Hipsec mailing list
[email-masked]
http://honor.trusecure.com/mailman/listinfo/hipsec