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

From: "Henderson, Thomas R" <[email-masked]>
Date: Mon, 21 Jun 2004 08:09:45 -0700

> -----Original Message-----
> From: Jan Mikael Melen [mailto:[email-masked]] 
> Sent: Monday, June 21, 2004 5:11 AM
> To: [email-masked]
> Cc: Pekka Nikander; Tim Shepard; Jake Beal
> Subject: Re: [Hipsec] proposal for a few small changes to 
> puzzle mechanism
> 
> 
> Hi,
> 
> On Monday 21 June 2004 12:59, Pekka Nikander wrote:
> >
> > > 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.
> >
> > 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.
> 
> 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?

Basically, this amounts to a mechanism to allow for faster
puzzle rotation in the presence of slow clients.  The tradeoff
is that it may require multiple I1/R1 exchanges for a slow
client to get a solution.  An alternative would be to allow
for a slow host to figure this out on its own when its puzzle
solutions are rejected as being solutions to stale puzzles
(but I see that we presently do not have a NOTIFY code for
"expired puzzle").

If we explicitly signal the puzzle lifetime, we could also 
redefine the Puzzle parameter to include a TTL, either by taking 
a byte from "Opaque" or by putting optional bytes at the end 
of the parameter.  

> 
> > > 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?

In the absence of an explicit overload notification, do you 
think that an attacker would be discouraged from attacking?  

> 
> > > Acknowledge I2s before sending R2s?
> 

Perhaps instead the optional TLV (or another optional TLV, or
the Puzzle) in the R1 has a recommended "server load" time to 
add to the normal I2 retransmission time?  

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

---

From: Jan Mikael Melen <[email-masked]>
Date: Tue, 22 Jun 2004 14:40:50 +0300

Hi,

Solving puzzles issue and I2 retransmission timeout issue:

In R1 we need two timer values TTL for a puzzle and I2 processing delay. Also 
there is a question about adding a NOTIFY.

One byte should be more than enough for puzzle TTL. In the absence of this TTL 
value the puzzle is considered to be valid for next 256 seconds (as it would 
if TTL field would be 0xff+1, same as setting the byte to zero, absence is 
indicated by zero value in this field).

For I2 server delay we would probably need 16 bit value that would indicate 
the value to be added in to normal I2 retransmission time in milliseconds 
which would mean that the range is from 0...65535ms that should be enough?

Now where do we put these?

Proposal: 
- Puzzle TTL in to the puzzle TLV by reducing the size of opaque field with 
one byte. New TLV would be: 1 byte k, 1 byte TTL, 2 bytes Opaque and 8 bytes 
random I.

- Modify the text in section 4.1.1 stating that client should try find a 
solution for a given amount of time before giving up or if time has not been 
specified for 256s. Remove Appendix C completely.

- Add a new NOTIFY SERVER_BUSY_PLEASE_RETRY which the server MAY send to the 
Initiator in case it is under severe load. Not mandatory in which case the 
Initiator would act as if the I2 would have been dropped by the network.

- Add a new optional TLV in R1 for the I2 retransmission timeout called 
I2_PROCESSING_DELAY. This TLV would contain 2 bytes reserved and 2 bytes 
indicating processing delay on the server end.

Is this okay?

> a byte from "Opaque" or by putting optional bytes at the end

	Jan

---

From: Tim Shepard <[email-masked]>
Date: Tue, 22 Jun 2004 08:06:28 -0400

It is not so much the I2 processing delay that we were worried about,
but rather the delay that the proccessing of the I2 will see because a
queue has (perhaps suddenly) built up on the server.  I could imagine
scenarios where the time spent in this queue is many 10s of seconds,
while the round trip time is only 100 ms or less.  When a client is in
this situation, but is behind a lossy link (which, for example, is
dropping 20% of the packets), you leave the client in a situation
where it would have to wait many 10s of seconds to conclude that a
packet had been dropped, if there is no acknowledgement of the I2.

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.

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.

			-Tim Shepard
			 [email-masked]

---

From: Jan Mikael Melen <[email-masked]>
Date: Tue, 22 Jun 2004 16:16:48 +0300

Hi,

Tim, yes you have a point of not introducing the processing delay of the 
server. But let's imagine the following situation:

Initiator has already sent a I2 and received acknowledment for it. 

Now the user behind the computer is beginning to be frustrated as nothing is 
happening after a few seconds. He is already starting to bang the keyboard. 
What should the HIP daemon do?

A) Retransmit the I2 and ignore that it got an acknowledgment from the 
previous I2? This same as if the responder had not sent the acknowledgement 
in the first place.

B) Just sit wait for R2 as the user bangs the keyboard? The R2 might as well 
be lost due lossy link and still the Initiator just waits due to fact that it 
has gotten acknowledgement from the responder. R2 message has no timeout 
mechanism that would ensure it's retransmission.

These just might be stupid questions...

  Regards,
	Jan

---

From: Tim Shepard <[email-masked]>
Date: Tue, 22 Jun 2004 09:32:08 -0400

> These just might be stupid questions...

No, those are very good questions.

It makes me think now that if I2s need a seperate acknowledgement,
then R2s also need them.

Here's an idea, if the responder sends an acknowledgement in response
to an I2, it could at that time give a fairly good estimate of how
many seconds it should be until the R2 is sent.

Another piece of an idea: if the initiator is to be the one with a
timer running to cover the case of an R2 being dropped by the network,
then retransmitting the same I2 seems completely reasonable.  The
server should be able to tell that the I2 corresponds to an already
established HIP association (assuming that it has managed to process
the first I2 by the time the second I2 arrives).  This retransmitted
I2 may need to bypass the puzzle solution checking mechanism because
the puzzle may have been deprecated.  Is that a problem?  Does it make
sense to have the check for whether the I2 corresponds to an
already-established HIP association occur before checking the puzzle?
Maybe the I2 should also be checked to see if it corresponds with an
already admitted-for-processing I2 that is still waiting in the queue
for the DH exponentiation before checking to see if the puzzle
solution is valid.

			-Tim Shepard
			 [email-masked]

---

From: Pekka Nikander <[email-masked]>
Date: Tue, 22 Jun 2004 21:45:06 +0300

A quick reaction to some details; still thinking
about the more complete thing in the background.

> indicated by zero value in this field).

I would use exponential interpretation of the value.  I.e.
TTL = 2^(value - 32).  That would allow one to express the
TTL as 2^-32, 2^-31, ..., 1/8, 1/4, 1/2, 1, 2, 4, 8, ... 2^223 seconds.
(2^-32 seconds = 0.2 ns, 2^223 seconds = 10^59 years).

Or maybe not use 2 as the base, but e.g. sqrt(2), to get finer 
granularity
and smaller range.

> specified for 256s. Remove Appendix C completely.

I would still leave App C in some form.  It is useful info.

> Initiator would act as if the I2 would have been dropped by the 

I don't think it is useful to send NOTIFY before the server has
verified the puzzle.

--Pekka

---

From: Tim Shepard <[email-masked]>
Date: Tue, 22 Jun 2004 23:30:56 -0400

> I don't think it is useful to send NOTIFY before the server has

Of course.  If the puzzle does not verify, then there is a silent
drop.  This notification though is needed to handle the case when the
server is dropping the I2 because it is overloaded *and* is
implementing some sort of persistant dropping mechanism to ensure that
an attacker cannot increase the likelyhood of the attacker's puzzle
solutions getting themselves a spot in the queue by retransmitting
them aggressively.  If you are a legit client and you got dropped, you
need to learn this fact so that you know to start finding another
puzzle solution. The puzzle solution you previously submitted will
always be dropped no matter how many times you retransmit it, even if
it still has plenty of lifetime left.

As I said in the original message, this would mean:

> 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.   

			-Tim Shepard
			 [email-masked]

---

From: Kristian Slavov <[email-masked]>
Date: Wed, 23 Jun 2004 14:37:26 +0300

Hi,

> many seconds it should be until the R2 is sent.

Since these acknowledgements need to be light-weight in terms of CPU processing, 
they cannot contain any cryptographic material. An attacker could easily
modify the packet and raise the estimate (or even lower to cause more load for 
the server).
On the other hand, if the attacker has means to intercept packets he could do
a MITM attack as well, so in that sense this is not a problem.

> already-established HIP association occur before checking the puzzle?

I think this is already covered in the base-00 draft:
Section 8.7 Processing incoming I2 packets

3. If the system is in the R2-SENT state, it MAY check if the newly received I2 
is similar to the one that triggered moving to R2-SENT. If so, it MAY retransmit 
a previously sent R2, reset the R2-SENT timer, and stay in R2-SENT.

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

---

From: Jan Mikael Melen <[email-masked]>
Date: Thu, 24 Jun 2004 15:54:37 +0300

> (2^-32 seconds = 0.2 ns, 2^223 seconds = 10^59 years).

This sounds good! 

Is okay for others as well that we take one byte from opaque and dedicate it 
for puzzle TTL?

> I would still leave App C in some form.  It is useful info.

Okay let's leave as informational...

  regards,
	Jan