Re: [Hipsec] Cookie

jukka.ylitalo@ericsson.fi wrote:
> As I see the case, the responder MUST always calculate the hash over

Well, if the I received in the I2 is bad, the packet can be dropped without checking the hash. As we talked, the trick is to make I bad more often...

>> The Responder starts the cookie exchange when it receives an I1.
>> The Responder supplies a random number I, and requires the
>> Initiator to find a number J. To select a proper J, the Initator
>> must create the concatenation of I, the HITs of the parties, the IP
>> addresses of the parties, and J, and take a SHA-1 hash over this
>> contactenation.

No, it is not guaranteed. But it is not guaranteed even in the old mechanism, since the Initiator may start far away from J and arrive to J after far too many steps. If we wanted to make sure that the Initiator finds a value, we would need to give some hint of a suitable J, and I don't think we want to do that.

In general, if we model the hash function with a random function, the probability that one iteration gives are result with K zero bits is 2^-K. Thus, the probablity that one iteration does *not* give K zero bits is (1 - 2^-K). Consequently, the probablity that 2^K iterations does not give K zero bits is (1 - 2^-K)^(2^K).

Since my calculus starts to be rusty, I made a small experiment and found out that

   lim (1 - 2^-k)^(2^k) = 0.36788    k->inf

   lim (1 - 2^-k)^(2^(k+1)) = 0.13534    k->inf

Do you need help?

In addition to our free technical library, Pantek provides professional IT services to companies who utilize Open Source software: Learn more about Pantek's Technical Support offerings Place an order for 24/7/365 Technical Support here Learn more about Pantek, who we are, and what we do Chat with a Live Operator Related lists.freeswan.org Links 1998-fall 1998-spring 1998-summer 1998-winter 1999-winter announce briefs bugs design freeswan-list hipsec ietf-sectest users users-admin Request more information about Pantek

   lim (1 - 2^-k)^(2^(k+2)) = 0.01832    k->inf

   lim (1 - 2^-k)^(2^(k+3)) = 0.000335    k->inf

Thus, if hash functions were random functions, we would need about 2^(K+3) iterations to make sure that the probability of a failure is less than 1% (actually less than 0.04%). Now, since my perhaps flawed understanding of hash functions is that they are "flatter" than random functions, 2^(K+3) is probably overkill. OTOH, the currently suggested 2^K is clearly too little. I'll change the draft to read 2^(K+2).

Good catch, Jukka. Thanks!

>> To prevent pre-computation attacks, the Responder MUST select I in
>> such a way that the Inititiator cannot guess it. Furthermore, the
>> construction MUST allow the Responder to verify that the values
>> were indeed selected by it and not by the Initiator. For example,
>> the Responder may remember a few recently sent I values, perhaps
>> send them multiple times, and check that the received I value in I2
>> matches with one remembered. ...

No, there is no mistake in the text. The Responder must select also I so that the Initiator cannot guess it. If it could guess it, it would not need to send I1, since the only thing an attacker needs from an I1 is the I (and K). Thus, it could precompute J based on its guess of I, and launch an I2 storm without bothering to send an I1 first.

> In general, storing the cookie values in the responder's end-point

I very much agree with this observation.

> The responder is still vulnerable for the I2 storm. The draft-06

Do you need more help?

In addition to our free technical library, Pantek provides professional IT services to companies who utilize Open Source software: Learn more about Pantek's Technical Support offerings Place an order for 24/7/365 Technical Support here Learn more about Pantek, who we are, and what we do Chat with a Live Operator Related lists.freeswan.org Links 1998-fall 1998-spring 1998-summer 1998-winter 1999-winter announce briefs bugs design freeswan-list hipsec ietf-sectest users users-admin Request more information about Pantek

Again, a very good observation. We can't use the IP addresses in the cookies due to NAT. But HITs we can.

Now, returning to an observation above. I don't remember with home I talked about the cookies (probably Tim), but according to the discussion part of Bob's original plan was to make the cookie I to depend on the sender of I1 in an implementation specific way. This would foil attempts to send I2s with a correctly looking I but spoofed IP addresses.

Generalizing this a bit, we need a method that binds a cookie to the sender of I1 in some implentation dependent and very cheap way, allowing the Responder to very cheaply check whether an I2 is received from a party that it has previously send an I1. The method does not need to be deterministic, since other checks will follow. Thus, all that is needed is a method to drop bad I2s, with a high probability, before checking the puzzle solution. This allows the responder to save one SHA-1 computation if the attacker attempts to send I2s with spoofed IP addresses or other easy-to-check information.

I will specify something along these lines in to the draft. Since this is implementation specific, the concrete method in the draft will just be an example.

--Pekka Nikander