Subject: [IPsec] DDoS puzzle: PRF vs Hash

From: Yoav Nir <[email-masked]>
Date: Thu, 29 Jan 2015 23:27:00 +0200

Hi all.

Following Valery’s suggestion, I’ve created a pull request for replacing the puzzle mechanism:

OLD: appending a string to the cookie so that the hash of the extended string has enough zero bits at the end.
NEW: finding a PRF key such that PRF(k, cookie) has enough zero bits at the end.

The source files and change are available at https://github.com/ietf-ipsecme/drafts/pull/3 <https://github.com/ietf-ipsecme/drafts/pull/3>

The relevant section is appended below

Please let us know what you think. Also about Valery’s pull request about negotiation.

Yoav

3.  Puzzles

   The puzzle introduced here extends the cookie mechanism from RFC
   7296.  It is loosely based on the proof-of-work technique used in
   BitCoins ([bitcoins]).  Future versions of this document will have
   the exact bit structure of the notification payloads, but for now, I
   will only describe the semantics of the content.

   A puzzle is sent to the Initiator in two cases:

   o  The Responder is so overloaded, than no half-open SAs are allowed
      to be created without the puzzle, or
   o  The Responder is not too loaded, but the rate-limiting in
      Section 5 prevents half-open SAs from being created with this
      particular peer address or prefix without first solving a puzzle.

   When the Responder decides to send the challenge notification in
   response to a IKE_SA_INIT request, the notification includes three
   fields:

   1.  Cookie - this is calculated the same as in RFC 7296.  As in RFC
       7296, the process of generating the cookie is not specified.
   2.  Algorithm, this is the identifier of a PRF algorithm, one of
       those proposed by the Initiator in the SA payload.
   3.  Zero Bit Count.  This is a number between 8 and 255 that
       represents the length of the zero-bit run at the end of the
       output of the PRF function calculated over the Keyed-Cookie
       payload that the Initiator is to send.  Since the mechanism is
       supposed to be stateless for the Responder, the same value is
       sent to all Initiators who are receiving this challenge.  The
       values 0 and 1-8 are explicitly excluded, because the value zero
       is meaningless, and the values 1-8 create a puzzle that is too
       easy to solve for it to make any difference in mitigating DDoS
       attacks.

   Upon receiving this challenge payload, the Initiator attempts to
   calculate the PRF using different keys.  When a key is found such
   that the resulting PRF output has a sufficient number of trailing
   zero bits, that result is sent to the Responder in a Keyed-Cookie
   notification, as described in Section 3.1.

   When receiving a request with a Keyed-Cookie, the Responder verifies
   two things:

   o  That the cookie part is indeed valid.
   o  That the PRF of the transmitted cookie calculated with the
      transmitted key has a sufficient number of trailing zero bits.

   Example 1: Suppose the calculated cookie is
   fdbcfa5a430d7201282358a2a034de0013cfe2ae (20 octets), the algorithm
   is HMAC-SHA256, and the required number of zero bits is 18.  After
   successively trying a bunch of keys, the Initiator finds that the key
   that is all-zero except for the last three bytes which are 02fc95
   yields HMAC_SHA256(k, cookie) =
   843ab73f35c5b431b1d8f80bedcd1cb9ef46832f799c1d4250a49f683c580000,
   which has 19 trailing zero bits, so it is an acceptable solution.

   Example 2: Same cookie, but this time the required number of zero
   bits is 22.  The first key to satisfy that requirement ends in
   960cbb, which yields a hash with 23 trailing zero bits.  Finding this
   requires 9,833,659 invocations of the PRF.

---

From: Yaron Sheffer <[email-masked]>
Date: Thu, 29 Jan 2015 23:57:03 +0200

Looking at the timing table, there is obviously significant variance in 
the time to solve each puzzle, compared to the ideal exponential curve. 
For example, for 28 bits we have 250s, whereas for 29 bits it's 1240s.

Would it make sense to require the initiator to return 4 or 8 solved 
puzzles of the given strength? Of course, the responder would request 
2-3 bits of strength less. The net effect should be a lower variance in 
run times, i.e. more deterministic run time for any particular type of 
client.

Thanks,
	Yaron

On 01/29/2015 11:27 PM, Yoav Nir wrote:
> The source files and change are available at
> https://github.com/ietf-ipsecme/drafts/pull/3
>
> _______________________________________________
> IPsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ipsec
>

---

From: Yoav Nir <[email-masked]>
Date: Fri, 30 Jan 2015 01:41:49 +0200

Interesting. I’ve tried with a few different “cookies”.

Cookie: 4f331b879f6d02322aa894942f66473d8a1949625c488aa0f4f943b441cfd6f4
Key=…00003db1  PRF=…4c82f8b80000  #zeros=19  time=0.025
Key=…0002ea6c  PRF=…5faafb800000  #zeros=23  time=0.250
Key=…0124159c  PRF=…9136e5000000  #zeros=24  time=26.013

Cookie: 6756a2fee7047eb87030b5cd7eb97ee24579371f54fecd3bc71f8b028f8c18b1
#zeros=14   time=0.016
#zeros=15   time=0.035
#zeros=19   time=0.134
#zeros=20   time=0.837
#zeros=21   time=1.932
#zeros=22   time=5.646
#zeros=24   time=16.790
#zeros=27   time=17.477

Cookie: 61a3a14b02580773234b8a773305aefed61c067775cea9c4797a406cd30fb14f
#zeros=15   time=0.016
#zeros=17   time=0.434
#zeros=21   time=1.034
#zeros=22   time=1.230
#zeros=23   time=16.213
#zeros=24   time=25.554
#zeros=

Seems like the big issue here is inconsistency. Set the puzzle level to 22 bits, and it could be solved in a quarter second or in 5.6 seconds or in 1.230. And these are not just outliers - they’re the first three values I picked at this length.

20 bits seems an acceptable difficulty level, but beyond that it becomes too erratic.

Yoav

> On Jan 29, 2015, at 11:57 PM, Yaron Sheffer <[email-masked]> wrote:
> 
> Looking at the timing table, there is obviously significant variance in the time to solve each puzzle, compared to the ideal exponential curve. For example, for 28 bits we have 250s, whereas for 29 bits it's 1240s.
> 
> Would it make sense to require the initiator to return 4 or 8 solved puzzles of the given strength? Of course, the responder would request 2-3 bits of strength less. The net effect should be a lower variance in run times, i.e. more deterministic run time for any particular type of client.
> 
> Thanks,
> 	Yaron
>

---

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 30 Jan 2015 14:27:28 +0300

Hi,

I also had some concerns on the variance of the times. But then
another thought came to me. Let's look on this issue from the other side.
The responder will use puzzles only when it feels that it is under attack.
It means, that there are a lot of (thouthands, tens of thouthands)
half-open connections. If responder requests that number of puzzles,
then some of them will appear to be easier to solve than the others.
Every initiator is different from another in terms of computing power and 
each of them may receive more or less hard puzzle.  
It's like an exam - some tasks are more easy to solve, some are harder.
Some clients will be more lucky, some less. That's a lottery.
But all those differences will be averaged for the responder, so why bother?

Also if we require initiator to solve several puzzles, than it will need
to send back all the solutions, that will noticeably increase
IKE message size.

So, while the idea is interesting, I think that the problem it solves
is not important, so why should we bother?

But it would be nice, if Yoav (as a person who already has 
test bed) could check, that if we solve puzzle for 100 
(or better 1000) different cookies, and average the times,
that the results will be less erratic (it would also be great
to measure the deviation of times for each level, not only average).

Regards,
Valery.

  ----- Original Message ----- 
  From: Yoav Nir 
  To: Yaron Sheffer 
  Cc: IPsecME WG 
  Sent: Friday, January 30, 2015 2:41 AM
  Subject: Re: [IPsec] DDoS puzzle: PRF vs Hash

  Yoav

    Thanks,
    Yaron

      Hi all.

      Following Valery’s suggestion, I’ve created a pull request for replacing
      the puzzle mechanism:

      OLD: appending a string to the cookie so that the hash of the extended
      string has enough zero bits at the end.
      NEW: finding a PRF key such that PRF(k, cookie) has enough zero bits at
      the end.

      Please let us know what you think. Also about Valery’s pull request
      about negotiation.

      Yoav

      3.  Puzzles

------------------------------------------------------------------------------

---

From: Tero Kivinen <[email-masked]>
Date: Fri, 30 Jan 2015 14:04:13 +0200

> But all those differences will be averaged for the responder, so why bother?

Yes, it is lottery, as the execution time is randomly distributed over
some max time. I agree that it does not really matter for this case,
as we are protecting server sending the puzzles, and clients do not
have way of knowing which puzzles are hard and which are easy.

Also if client decides it will only try to solve the puzzle for 0.5
seconds and then get new one, that will not help it, as the one he
already has might have been solved by just doing one more try, and the
re is no guarantee that the new one he got is easier.

> to send back all the solutions, that will noticeably increase

Not that much. The client could find number where:

0x01 + cookie + count1
0x02 + cookie + count2
0x03 + cookie + count3
0x04 + cookie + count4

and send back count cookie + count1-4 or something. The counters
should be smaller than cookie, most likely something that can be
expressed in 32 or 64 bits...

The execution time of the above should be not randomly over the whole
time, but binomial distribution over the time (or something like that,
it is way too long when I have been doing anything like this).

> is not important, so why should we bother?

Agree.

-- 
[email-masked]

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 30 Jan 2015 14:39:30 +0200

To clarify: I am NOT suggesting that the responder should generate 8 
puzzles (8 cookies). I am suggesting that the initiator should send 8 
different solutions to the same puzzle, using something like Tero's 
proposal.

It is true that the execution time (a.k.a. client-side cost) will 
average out among many clients, so we would be fine WRT DoS protection. 
But it is still worthwhile to reduce the variance, in order to have a 
more deterministic user experience (for VPN clients) and to avoid 
client-side timeouts.

Thanks,
	Yaron

---

From: Yoav Nir <[email-masked]>
Date: Fri, 30 Jan 2015 14:42:31 +0200

I’ll try that later, but suppose we give the client 16 puzzles to solve, then we expect solving all of them to take 16 times as long, so they can be 16 times easier. So instead of 22 bits, they can be 18 bits. I’m not sure if that increased the chance of getting “stung” by a bad outlier or that it averages better.

But one effect is obvious. If we require the client to solve all puzzles, the server has to check all 16 parts of the solution, and that makes it 16x harder for the server.

OTOH if we required to solve just one of the 16, the client could try all 16 at the same time, and have a better chance of finding a “good” outlier. Again, I’m not sure which is the dominant effect.

Yoav

> On Jan 30, 2015, at 1:27 PM, Valery Smyslov <[email-masked]> wrote:
> 
> Hi,
>  
>> From: Yoav Nir <mailto:[email-masked]>
>> To: Yaron Sheffer <mailto:[email-masked]>
>> Cc: IPsecME WG <mailto:[email-masked]>
>>> On Jan 29, 2015, at 11:57 PM, Yaron Sheffer <[email-masked] <mailto:[email-masked]>> wrote:
>>> 
>>>> https://github.com/ietf-ipsecme/drafts/pull/3 <https://github.com/ietf-ipsecme/drafts/pull/3>
>>>>

---

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 30 Jan 2015 15:51:50 +0300

> different solutions to the same puzzle, using something like Tero's 

I understand it exactly as you described.
But then the initiatot need to include all 8 solutions in its second try.
Even with Tero's approach it will increase the message size.
And as Yoav has pointed out - the responder should then check
all that 8 solutions.

So for now I think it is not justified.

Valery.

> It is true that the execution time (a.k.a. client-side cost) will average 
> out among many clients, so we would be fine WRT DoS protection. But it is 
> still worthwhile to reduce the variance, in order to have a more 
> deterministic user experience (for VPN clients) and to avoid client-side 
> timeouts.
>
> Thanks,
> Yaron
>

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 30 Jan 2015 15:37:54 +0200

What I would suggest is: we give the client a single puzzle, and ask it 
to return 16 different solutions. Indeed each puzzle then should be 16X 
easier. The nice thing is, the server should only check *one* of them, 
at random. The client would still need to solve all of them because it 
doesn't want to risk the exchange being rejected because some solutions 
are invalid (the game theory is probably more complex than that, but I 
think what I'm saying is still close to the truth).

So: the client does the same amount of work, the server does the same 
amount of work, but the client run-time is still much more deterministic.

Thanks,
	Yaron

On 01/30/2015 02:42 PM, Yoav Nir wrote:
> I’ll try that later, but suppose we give the client 16 puzzles to solve,
> then we expect solving all of them to take 16 times as long, so they can
> be 16 times easier. So instead of 22 bits, they can be 18 bits. I’m not
> sure if that increased the chance of getting “stung” by a bad outlier or
> that it averages better.
>
> But one effect is obvious. If we require the client to solve all
> puzzles, the server has to check all 16 parts of the solution, and that
> makes it 16x harder for the server.
>
> OTOH if we required to solve just one of the 16, the client could try
> all 16 at the same time, and have a better chance of finding a “good”
> outlier. Again, I’m not sure which is the dominant effect.
>
> Yoav
>
>> On Jan 30, 2015, at 1:27 PM, Valery Smyslov <[email-masked]
>> <mailto:[email-masked]>> wrote:
>>
>> Hi,
>>> *From:* Yoav Nir <mailto:[email-masked]>
>>> *To:* Yaron Sheffer <mailto:[email-masked]>
>>> *Cc:* IPsecME WG <mailto:[email-masked]>
>>> *Sent:* Friday, January 30, 2015 2:41 AM
>>> *Subject:* Re: [IPsec] DDoS puzzle: PRF vs Hash
>>>
>>> Seems like the big issue here is inconsistency. Set the puzzle level
>>> to 22 bits, and it could be solved in a quarter second or in 5.6
>>> seconds or in 1.230. And these are not just outliers - they’re the
>>> first three values I picked at this length.
>>>
>>>> Looking at the timing table, there is obviously significant variance
>>>> in the time to solve each puzzle, compared to the ideal exponential
>>>> curve. For example, for 28 bits we have 250s, whereas for 29 bits
>>>> it's 1240s.
>>>>
>>>> puzzles of the given strength? Of course, the responder would
>>>> request 2-3 bits of strength less. The net effect should be a lower
>>>> variance in run times, i.e. more deterministic run time for any
>>>> particular type of client.
>>>>
>>>> Thanks,
>>>> Yaron
>>>>
>>>>> [email-masked] <mailto:[email-masked]>
>>> ------------------------------------------------------------------------
>>>
>>> [email-masked] <mailto:[email-masked]>

---

From: Yoav Nir <[email-masked]>
Date: Sat, 31 Jan 2015 00:35:12 +0200

> On Jan 30, 2015, at 3:37 PM, Yaron Sheffer <[email-masked]> wrote:
> 
> What I would suggest is: we give the client a single puzzle, and ask it to return 16 different solutions. Indeed each puzzle then should be 16X easier. The nice thing is, the server should only check *one* of them, at random. The client would still need to solve all of them because it doesn't want to risk the exchange being rejected because some solutions are invalid (the game theory is probably more complex than that, but I think what I'm saying is still close to the truth).
> 
> So: the client does the same amount of work, the server does the same amount of work, but the client run-time is still much more deterministic.

OK, I’ve tried that. 

But first, I found an inefficiency in my code, so I’ve fixed it and ran the tests again. Here are the results:

             cookie set
#bits     1          2          3      
===== =========  =========  =========
 15     0.016
 16     0.031      0.065      0.057
 17     0.087      0.820      0.250
 18                           0.289
 19     0.420
 20     5.965                 0.401
 21    14.055      0.916
 22    19.065      2.074
 23    23.753      3.067      6.688
 24                5.414     48.045
 25    29.924
 26    60.088    130.753
 27
 28                          87.437
 29   111.921

So still pretty much all over the place.  So I tried Yaron’s suggestion of calculating until I find 16 keys that produce at least so many zero bits. Here are the results for 16 keys each time:

             cookie set
#bits     1          2          3          4      
===== =========  =========  =========  =========
 15      0.780      0.954      0.678      0.778
 16      1.734      2.056      1.575      1.162
 17      3.090      4.161      2.932      2.832
 18      4.981      7.463      4.766      4.380
 19     11.612     10.069     14.525      8.486
 20     22.789     21.111     30.961     24.146 
 21     40.066     39.875     57.930     53.785
 22     92.264    116.453    123.352    139.584

Note that these are still single core results, and most laptops can do twice or four times as much. Now, I know that what I SHOULD be doing is to randomly generate 100 “cookies” and then calculate the times for different bit lengths for each of them, and then calculate mean and standard deviation. But just by looking, it looks like it’s much closer to what we want. 16 bits would be a fine puzzle level for my laptop. No idea about a phone, although I could try to compile this and run it on an ARM-based appliance, which should match phones.

Yoav