Subject: Re: [IPsec] DDoS puzzle: PRF vs Hash

From: Yoav Nir <[email-masked]>
Date: Sun, 1 Feb 2015 11:45:33 +0200

> On Jan 31, 2015, at 12:35 AM, Yoav Nir <[email-masked]> wrote:
> 
> 
>> 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.

<snip />

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

OK. Now I have done it right. See attached. The data suggests that 15 or 16 bits is the level of puzzle that for this kind of hardware is challenging but not too onerous. Add another bit if we assume (probably correctly) that the vast majority of laptops have dual cores at least.

I would like to run a similar test on an ARM processor, though. The capabilities of phones and tablets are all over the place, what with different versions of ARM processors and devices having anything from dual to octo-core, but it would be nice to get ballpark figures.

Yoav

---

From: Yoav Nir <[email-masked]>
Date: Sun, 1 Feb 2015 11:46:31 +0200

And now it’s really attached.

> On Feb 1, 2015, at 11:45 AM, Yoav Nir <[email-masked]> wrote:
> 
>

---

From: Yaron Sheffer <[email-masked]>
Date: Sun, 01 Feb 2015 19:36:41 +0200

Hi Yoav,

This is good, but I'm not sure if it's good enough. The ratio between 
min and max (which I trust more than the "mean +/- 3s" rule, because 
this is not a normal distribution) is consistently around 4. So if you 
have to design your timeouts on a particular machine, you would still 
have a lot of uncertainty. For comparison, could you try again with 64 
replacing the 16 tries, and with lower bit lengths?

Thanks,
	Yaron

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Sun, 1 Feb 2015 18:38:44 +0000

If you want to tighten up the time between worse case and average case time taken by the problem solver, might I suggest this:

- When the verifier is asked to generate a problem, it pick a nonce N, and use it to compute m k-bit values S_1, S_2, ..., S_m (for example, S_1 || S_2 || ... || S_m =  AES_key(N), where the AES key is secret to the verifier), and publish k, N, HASH(N, S_1), HASH(N, S_2), ..., HASH(N, S_m)

- To solve the problem, the solver needs to produce the values S_1, S_2, ..., S_m, and send back N, S_1, S_2, ..., S_m

- The verifier verifies that the value N was what was originally given (for example, the nonce might include the solver's IP address and a timestamp), and that the values S_1 ||  S_2 || ... || S_m  = AES_key(N||0), (or alternatively, that those values produces the hashes it sent).

The solver can always solve the problem by computing 2**k hashes; with moderate m, we can make it unlikely that it can be done with significantly fewer hashes; I would suggest m=4.

Of course, the cost of doing this is a) larger messages, and b) larger up-front cost generating the problem (which, IMHO, isn't too bad -- one AES encryption, and m hash computations; however, you are free to disagree).

-----Original Message-----
From: IPsec [mailto:[email-masked]] On Behalf Of Yaron Sheffer
Sent: Sunday, February 01, 2015 12:37 PM
To: Yoav Nir
Cc: IPsecME WG; Valery Smyslov
Subject: Re: [IPsec] DDoS puzzle: PRF vs Hash

Hi Yoav,

This is good, but I'm not sure if it's good enough. The ratio between min and max (which I trust more than the "mean +/- 3s" rule, because this is not a normal distribution) is consistently around 4. So if you have to design your timeouts on a particular machine, you would still have a lot of uncertainty. For comparison, could you try again with 64 replacing the 16 tries, and with lower bit lengths?

Thanks,
	Yaron

On 02/01/2015 11:46 AM, Yoav Nir wrote:
> And now it's really attached.
>
>
>
>
>>> 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.
>>

_______________________________________________
IPsec mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/ipsec

---

From: Yoav Nir <[email-masked]>
Date: Mon, 2 Feb 2015 08:31:37 +0200

The three-sigma rule applies even with a non-normal distribution.

Anyway, I tried the 64-key sample. Results are slightly better.

Yoav

> On Feb 1, 2015, at 7:36 PM, Yaron Sheffer <[email-masked]> wrote:
> 
> Hi Yoav,
>

---

From: Yaron Sheffer <[email-masked]>
Date: Mon, 02 Feb 2015 10:53:49 +0200

Results are actually way better, with the 4X changed into 2X. However it 
seems to me that Scott's proposal is better - slightly more complex but 
certainly more deterministic.

Thanks,
	Yaron

---

From: "Valery Smyslov" <[email-masked]>
Date: Mon, 2 Feb 2015 15:06:41 +0300

Are we going into the right direction?
Is it worth to solve the task of making
puzzle difficulties less erratic if the computing power
of clients may differ by the order of magnitude (or even magnitudes)?

Can we make the process more flexible?
For example - the server may indicate two difficulty levels in puzzle
request - the desired one and the acceptable one.
For example, the desired level is 20 bits and the acceptable level is 16 
bits.
It means, that if client is able to find the solution with 20 bits of zeroes
it will reserve the right to be served. But if it cannot (for any reason -
insufficient power or the puzzle is by chance too hard), then any
solution with the number of zero bits higher than 16 will be accepted.
But it doesn't mean that the server will immediately serve this
request if the solution contains less that 20 zero bits - depending
on the number of zero bits the client managed to get,
the amount of time it takes it to solve, the number of puzzles this
client has already solved and the current server's load the server
may issue new puzzle to such client. The process continues
until the server decides that the client spent enough resources
and it can be served now taking into consideration current server's load.

The advantage of such approach is that it makes the whole process
more adjustable to varying factors, including the wide variety of
clients and their computational power. The disadvantage is the higher
server load (it needs to prepare and verify more puzzles) and
the higher network bandwidth consumption. But unlike the previously
suggested approaches it doesn't increase the size of a single message,
that is very good as it decreases the chance for IP fragmentation.

Valery.

>>>>>>> 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.
>>>>>
>>>>> <snip />
>>>>>
>>>>>> 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.
>>>>>
>>>>> OK. Now I have done it right. See attached. The data suggests that 15 
>>>>> or 16 bits is the level of puzzle that for this kind of hardware is 
>>>>> challenging but not too onerous. Add another bit if we assume 
>>>>> (probably correctly) that the vast majority of laptops have dual cores 
>>>>> at least.
>>>>>
>>>>> I would like to run a similar test on an ARM processor, though. The 
>>>>> capabilities of phones and tablets are all over the place, what with 
>>>>> different versions of ARM processors and devices having anything from 
>>>>> dual to octo-core, but it would be nice to get ballpark figures.
>>>>>
>>>>> Yoav
>>>>>
>>>>
>>

---

From: Michael Richardson <[email-masked]>
Date: Mon, 02 Feb 2015 10:53:22 -0500

> For example, the desired level is 20 bits and the acceptable level is 16

You are describing a situation where the server simply has multiple queues, I
think.  One for 20 bits, and probably one for each of 19,18,17,16, and then
one for all solutions <16, including not supporting puzzles at all.

If one further creates various queues based upon initiator IP, it seems like
one can rather effectively adjust to situations of attack or not.

One concern: is the gateway, in selecting the complexity of the puzzle giving
out information about it's current state of health? (Do we care?)

    > that is very good as it decreases the chance for IP fragmentation.

Over time Internet protocols seem to evolve towards the pseudo-technology
of William Gibson's Neuromancer series... which he wrote on a typewriter in
the 1980s :-)
{In this case: bad guys need bigger computers to pull off bigger scams :-)}

--
Michael Richardson <[email-masked]>, Sandelman Software Works
 -= IPv6 IoT consulting =-

---

From: "Valery Smyslov" <[email-masked]>
Date: Tue, 3 Feb 2015 09:53:48 +0300

Hi Michael,

> one for all solutions <16, including not supporting puzzles at all.

Yes, but the queues are virtual, the server is still stateless.
The server just takes a desicion on each request based on the
number of zero bits the client was able to get, the amount of time
it took the client, the number of puzzles the client has already
solved and the current server load.

> one can rather effectively adjust to situations of attack or not.

Yes, but again, the queues are virtual. All this information
must be encoded in cookie, so that the server remains stateless.

> out information about it's current state of health? (Do we care?)

Yes, it reveals some information. But do we care and can we
avoid this? Even the sole fact that the server asks for puzzles reveals
the information that it feels itself under attack.

Regards,
Valery.

---

From: Tero Kivinen <[email-masked]>
Date: Tue, 3 Feb 2015 15:48:41 +0200

Valery Smyslov writes:
> > You are describing a situation where the server simply has
> > multiple queues, I think. One for 20 bits, and probably one for
> > each of 19,18,17,16, and then one for all solutions <16, including
> > not supporting puzzles at all.
> 

No, server does NOT need to be stateless when it is collecting which
clients to serve. This is already after the checking the cookie, so
client has already proven the point that he is reachable, and is
willing to do work.

So after verifying that cookie is valid, and suitable work is done,
server can put the client to associated queue.

Each queue could be limited to exactly n clients, for example 100
clients for different queues, i.e. for 6 queues (20-, 19, 18, 17, 16,
-15) that would mean 600 entries in queues. If associated queue is
full, the request is dropped.

After collecting entries to queue for some time (for example 0.5
seconds), the server will sort each queue create one combined queue
out from all the queues using suitable algorithms (weighting in the
work done by the client, whether that ip-address as tried before or
not, whether that ip-address is know, whether that ip-address has been
server in last n seconds in such way it didn't result in successfull
authentication etc), and truncate that queue to something manageable.

I.e. if server thinks he can do about 100 request per second, he might
take 100 first from the combined queue, and process them for 0.5
seconds, and then throw rest away.

During that 0.5 seconds he will be collecting new queues as before,
and after 0.5 seconds he will again take those queues and sort them
and create next combined queue.

We need to be stateless as long as clients do not commit real
resources for the attack. After that it is better to have some limited
state so we can do smart decisions.
-- 
[email-masked]

---

From: "Valery Smyslov" <[email-masked]>
Date: Tue, 3 Feb 2015 17:06:04 +0300

> state so we can do smart decisions.

I think this is implementation dependant. You may have these
queues and be statefull, or you may store all the needed
information in the cookies and have some kind of distributed
queue. Both approaches are possible, and RFC should not
mandate any of them. But I agree that some guidance
for implementers should be given.

Valery.

---

From: Yoav Nir <[email-masked]>
Date: Wed, 4 Feb 2015 19:06:34 +0200

OK, now I’ve got a chance to test on an ARM appliance (similar in power to a 2-3 year old phone, I think.

Again these are single-core results, but there’s an extra bit of badness here in that this is a C implementation of SHA256. We could probably gain around 2 extra bits with an assembly-language implementation. As it is, it’s about 4 bits behind the Intel i5.

Yoav

> On Feb 2, 2015, at 8:31 AM, Yoav Nir <[email-masked]> wrote:
> 
> <data64.xlsx>

---

From: "Valery Smyslov" <[email-masked]>
Date: Thu, 5 Feb 2015 09:52:59 +0300

I think this data proves the idea that the difference between
computation power of different clients is significant and
no single puzzle difficulty level would be reasonable for all.
I think we should proceed with the proposal that
client is allowed to return less zero bits than requested.

And in this case we may go further.
The server may even not indicate to the client
how many zero bits it wants to get. The server
could just give the puzzle to the client and
the client would return the best solution that it can
get for a reasonable (from client's point of view) time.
Some clients would be able to get more zero bits, some less.
Then the server would sort all the requests, as described
in Tero's e-mail and serve them accordingly.

Valery.

----- Original Message ----- 
From: "Yoav Nir" <[email-masked]>
To: "Yaron Sheffer" <[email-masked]>
Cc: "Valery Smyslov" <[email-masked]>; "IPsecME WG" <[email-masked]>
Sent: Wednesday, February 04, 2015 8:06 PM
Subject: Re: [IPsec] DDoS puzzle: PRF vs Hash

OK, now I’ve got a chance to test on an ARM appliance (similar in power to a 
2-3 year old phone, I think.

Again these are single-core results, but there’s an extra bit of badness 
here in that this is a C implementation of SHA256. We could probably gain 
around 2 extra bits with an assembly-language implementation. As it is, it’s 
about 4 bits behind the Intel i5.

Yoav

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

>> This is good, but I'm not sure if it's good enough. The ratio between min 
>> and max (which I trust more than the "mean +/- 3s" rule, because this is 
>> not a normal distribution) is consistently around 4. So if you have to 
>> design your timeouts on a particular machine, you would still have a lot 
>> of uncertainty. For comparison, could you try again with 64 replacing the 
>> 16 tries, and with lower bit lengths?
>>
>> Thanks,
>> Yaron
>>
>>>>>> 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.
>>>>
>>>> <snip />
>>>>
>>>>> 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.
>>>>
>>>> challenging but not too onerous. Add another bit if we assume (probably 
>>>> correctly) that the vast majority of laptops have dual cores at least.
>>>>

---

From: Yoav Nir <[email-masked]>
Date: Thu, 5 Feb 2015 12:11:45 +0200

Before I respond, here’s one more data point: I’ve compiled OpenSSL 1.0.2 for ARM and got ~60,500 SHA-256 hashes (it’s close enough to not matter to the result for HMAC-SHA-256) per second.

That says that assuming 1 second as the “reasonable” time to solve a puzzle, we can expect to do about 16-17 bits for one solution, 12 for 16 solutions or 10 for 64. That’s pretty much in line with what I got with “my” code. According to messages on openssl’s dev list, the assembly-language version of SHA-256 is about twice as fast, so respectively that’s 18, 13 or 11 bit puzzles, Still 3 bits behind Intel. This does not take into considerations 2- or 4-core laptops or octo-core Samsung Galaxies.

> On Feb 5, 2015, at 8:52 AM, Valery Smyslov <[email-masked]> wrote:
> 

It’s simpler and safer code to get a request from the initiator, mark it as solved/not-solved, and process if solved or discard if not. Then you don’t have to do any queueing beyond what the UDP stack is doing anyway.

> in Tero's e-mail and serve them accordingly.

This would allow a sufficiently powerful botnet to flood the queues and deny service to phones. Suppose it turns out that phones like to work for 0.5 seconds and usually come up with 15-, 16-, or 17- bit solutions, it should be easy for a botnet to work far less time on each puzzle and solve hundreds of puzzles at these bit lengths. That would effectively block the phones that take a whole half second to calculate just one such solution.

Yoav

---

From: Yoav Nir <[email-masked]>
Date: Thu, 5 Feb 2015 13:27:57 +0200

> On Feb 1, 2015, at 8:38 PM, Scott Fluhrer (sfluhrer) <[email-masked]> wrote:
> 

Hi, Scott.

Thanks for the suggestion. Let me see if I understand it correctly:

Responder has a fixed AES key (let’s call it K).

Let’s assume that N is a COOKIE calculated as in RFC 5996. 

The responder Calculates S1||S2||…||Sm = AES(K, COOKIE). COOKIE can be any length, but for simplicity let’s assume 128-bit so that we don’t have to deal with IVs, ICs or any other artifacts of modes of operation. Also, let’s set m=8 and all Si as 16-bit.
So the responder now calculates 8 hashes: for each i Hi = SHA256(COOKIE || Si) or better yet, Hi = PRF(Si, COOKIE).

The responder sends to the initiator:
 - The COOKIE
 - Hi for all i.
 - The number k, although that can be deduced from the number of His
 - An identifier for the PRF algorithm chosen.

The initiator needs to find Si values such that Hi = PRF(Si, COOKIE). The silly way to do this is to solve run through all 2^16 possible Si values once for each Hi (8 times), but a better way would be to run once through the possible Si-s and find all of them. There is a small chance of making an error if two 16-bit values produce the same result when using the PRF on the cookie. The initiator repeats the request along with the nonce and Si for all i.

The responder now needs to do the following:
 - Verify the COOKIE
 - Encrypt the COOKIE, resulting (hopefully) in the concatenation of the Si values.

With the numbers I used in the example, k=16 resulting in 2^16 PRF calculations on the client. The puzzle can be made harder by increasing k and breaking the encrypted COOKIE into larger chunks.

Did I get this correctly?

Thanks

Yoav

---

From: "Valery Smyslov" <[email-masked]>
Date: Thu, 5 Feb 2015 15:12:08 +0300

> It’s simpler and safer code to get a request from the initiator, mark it 
> as solved/not-solved,
> and process if solved or discard if not. Then you don’t have to do any 
> queueing beyond
> what the UDP stack is doing anyway.

The real queueing is not necessary. You may act exactly the same way,
as you described - get a request, analyze it and either process,
or issue a new request, or discard. The only difference is what
does the word "analyze" mean. In suggested approach it means:

 - Check whether puzzle was ever tried to be solved.
    If not - mark the request with the lowest priority.

 - Check how many zero bits are returned, how much time
    did it take the client (the latter can be learned if
    the cookie was timestamped) and how many puzzles
    it has already been asked (also can be encoded in cookie).
    Mark the request with the priority, that is calculated as

   (zero bits) * (spent time) * (number of solved puzzles)

 - Take a decision whether to process request or not.
    The decision should take into account the server's load and
    the priority of the request, and it should be probabilistic,
    so that even low-priority requests have a chance to be served.

 - If low-priority request is not served than give new puzzle
    for that client. The more puzzles client solve the higher
    would be its request priority.

> This would allow a sufficiently powerful botnet to flood the queues and 
> deny service to phones.

It is always possible. If you require all the clients to solve puzzle with
a single difficulty, then sufficiently powerful botnet would quickly
rase the bar so high, that phone's just won't be able to solve the puzzle
for reasonable time (and reasonable battery consumption).

And the proposed solution tries to avoid this, giving them a chance.

> Suppose it turns out that phones like to work for 0.5 seconds and usually 
> come up with
> 15-, 16-, or 17- bit solutions, it should be easy for a botnet to work far 
> less time on each
> puzzle and solve hundreds of puzzles at these bit lengths. That would 
> effectively block the phones
> that take a whole half second to calculate just one such solution.

Not really. As the decision on whether to serve request
should be probabilistic, than any such request (including phone's)
should have a chance to be processed.

BTW - the formula for priority includes spent time,
so if you get only 16 bits, but spent 0.5 secs for this,
then you will get better chances than somebody,
who solved these 16 bits for 5 ms.

Valery.

---

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 6 Feb 2015 09:30:48 +0300

I can see two drawbacks with this approach.

First, to make it aligned with algorithm agility, we need to
negotiate not only PRF, but also the encryption algorithm.
And the selection criteria would become more complex.

And second - it significantly increases the size of IKE_SA_INIT
response message, as the puzzle must include m hashes.
With SHA256 and m = 8 it is additional 256 bytes.
With SHA512 and m = 16 it is additional 1024 bytes.
That is not good as it increases the chance for IP fragmentation.

Regards,
Valery.

> > If you want to tighten up the time between worse case and average case 
> > time taken by the problem solver, might I suggest this:
> >
> > - When the verifier is asked to generate a problem, it pick a nonce N, 
> > and use it to compute m k-bit values
> S_1, S_2, ..., S_m (for example, S_1 || S_2 || ... || S_m =  AES_key(N), 
> where the AES key is secret to the verifier),
> and publish k, N, HASH(N, S_1), HASH(N, S_2), ..., HASH(N, S_m)
> >
> > - To solve the problem, the solver needs to produce the values S_1, S_2, 
> > ..., S_m, and send back N, S_1, S_2, ..., S_m
> >
> > - The verifier verifies that the value N was what was originally given 
> > (for example, the nonce might include the solver's
> IP address and a timestamp), and that the values S_1 ||  S_2 || ... || S_m 
> = AES_key(N||0), (or alternatively,
> that those values produces the hashes it sent).
> >
> > The solver can always solve the problem by computing 2**k hashes; with 
> > moderate m, we can make it unlikely
> that it can be done with significantly fewer hashes; I would suggest m=4.
> >
> > Of course, the cost of doing this is a) larger messages, and b) larger 
> > up-front cost generating the problem
> (which, IMHO, isn't too bad -- one AES encryption, and m hash 
> computations; however, you are free to disagree).
> >
>
> Hi, Scott.
>
> The responder Calculates S1||S2||…||Sm = AES(K, COOKIE). COOKIE can be any 
> length,
> but for simplicity let’s assume 128-bit so that we don’t have to deal with 
> IVs, ICs or any other artifacts
> of modes of operation. Also, let’s set m=8 and all Si as 16-bit.
> The initiator needs to find Si values such that Hi = PRF(Si, COOKIE). The 
> silly way to do this is to solve run
> through all 2^16 possible Si values once for each Hi (8 times), but a 
> better way would be to run once through
> the possible Si-s and find all of them. There is a small chance of making 
> an error if two 16-bit values produce
> the same result when using the PRF on the cookie. The initiator repeats 
> the request along with the nonce and Si for all i.
>
> With the numbers I used in the example, k=16 resulting in 2^16 PRF 
> calculations on the client.
> The puzzle can be made harder by increasing k and breaking the encrypted 
> COOKIE into larger chunks.
>

---

From: Yoav Nir <[email-masked]>
Date: Fri, 6 Feb 2015 09:49:24 +0200

Thinking it over, you don’t really need AES at all, and in any case it doesn’t matter. The initiator doesn’t know the key and doesn’t know the algorithm, so it’s entirely a local matter.

For example, the responder could pick HMAC-SHA256 with a fixed key, and calculate HMAC-SHA256(K,cookie).  And it’s not even necessary for the initiator to solve all of the response. We can limit it to 8 Si-s (m=8), each 16 bits (k=16) even though the output of HMAC-SHA256 is 256 bits. m only serves to force the initiator to go through most of the 2^k possibilities.

Yoav

> On Feb 6, 2015, at 8:30 AM, Valery Smyslov <[email-masked]> wrote:
> 
>> > On Feb 1, 2015, at 8:38 PM, Scott Fluhrer (sfluhrer) > <[email-masked]> wrote:
>> >
>> > If you want to tighten up the time between worse case and average case > time taken by the problem solver, might I suggest this:
>> >
>> > - When the verifier is asked to generate a problem, it pick a nonce N, > and use it to compute m k-bit values
>> S_1, S_2, ..., S_m (for example, S_1 || S_2 || ... || S_m =  AES_key(N), where the AES key is secret to the verifier),
>> > - To solve the problem, the solver needs to produce the values S_1, S_2, > ..., S_m, and send back N, S_1, S_2, ..., S_m
>> >
>> > - The verifier verifies that the value N was what was originally given > (for example, the nonce might include the solver's
>> IP address and a timestamp), and that the values S_1 ||  S_2 || ... || S_m = AES_key(N||0), (or alternatively,
>> > The solver can always solve the problem by computing 2**k hashes; with > moderate m, we can make it unlikely
>> > Of course, the cost of doing this is a) larger messages, and b) larger > up-front cost generating the problem
>> (which, IMHO, isn't too bad -- one AES encryption, and m hash computations; however, you are free to disagree).
>> >
>> 
>> Hi, Scott.
>> 
>> The responder Calculates S1||S2||…||Sm = AES(K, COOKIE). COOKIE can be any length,
>> but for simplicity let’s assume 128-bit so that we don’t have to deal with IVs, ICs or any other artifacts
>> The initiator needs to find Si values such that Hi = PRF(Si, COOKIE). The silly way to do this is to solve run
>> through all 2^16 possible Si values once for each Hi (8 times), but a better way would be to run once through
>> the possible Si-s and find all of them. There is a small chance of making an error if two 16-bit values produce
>> the same result when using the PRF on the cookie. The initiator repeats the request along with the nonce and Si for all i.
>> 
>> With the numbers I used in the example, k=16 resulting in 2^16 PRF calculations on the client.
>> The puzzle can be made harder by increasing k and breaking the encrypted COOKIE into larger chunks.
>>

---

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 6 Feb 2015 11:22:29 +0300

> Thinking it over, you don’t really need AES at all, and in any case it 
> doesn’t matter.
> The initiator doesn’t know the key and doesn’t know the algorithm, so it’s 
> entirely a local matter.

You are right, it's a local matter.

> For example, the responder could pick HMAC-SHA256 with a fixed key, and 
> calculate HMAC-SHA256(K,cookie).
> And it’s not even necessary for the initiator to solve all of the 
> response. We can limit it to 8 Si-s (m=8), each 16 bits
> (k=16) even though the output of HMAC-SHA256 is 256 bits. m only serves to 
> force the initiator to go through
> most of the 2^k possibilities.

And another drawback of this approach is that the responder must do quite a 
lot of work
to prepare puzzle. It must first calculate S1||S2||…||Sm and then for each 
Si calculate Hi.
That is not an enormous work, but comparing with the current "zero bits" 
proposal,
where the puzzle goes for free, it is non insignificant (especially as we're 
trying
to protect responder against DoS attack).

And again, my main concern is whether we are solving the right problem.
This approah makes time requiring to solve random puzzle more consistent.
But it doesn't help weak clients, unless we allow them to return as many
Si-s, as they can. But in this case I see no significant advantages
of this approach, but I can see its complexity, increased message size
and increased load on responder.

Valery.

>> > - To solve the problem, the solver needs to produce the values S_1, 
>> > S_2, > ..., S_m, and send back N, S_1, S_2, ..., S_m
>> >
>> So the responder now calculates 8 hashes: for each i Hi = SHA256(COOKIE 
>> || Si) or better yet, Hi = PRF(Si, COOKIE).
>>

---

From: Yaron Sheffer <[email-masked]>
Date: Sun, 08 Feb 2015 23:20:50 +0200

I think we've come a full circle. We now have a proposal that makes 
proof-of-work more deterministic for each type of client (which I find 
very useful). But the weaker clients will always lose, no matter what 
POW solution we choose. This has been a problem with this proposal from 
day one and it's a limitation that we as a group need to decide whether 
to accept or not. In a world where some clients are 100X more powerful 
than others, IMHO this result is something we have to live with.

The only partial solution I see to this problem is to recommend using 
RFC 5723 session resumption, so that clients who have recently connected 
can reconnect even in DoS situations.

Thanks,
	Yaron

On 02/06/2015 10:22 AM, Valery Smyslov wrote:
>> The initiator doesn’t know the key and doesn’t know the algorithm, so
>> it’s entirely a local matter.
>
>> For example, the responder could pick HMAC-SHA256 with a fixed key,
>> and calculate HMAC-SHA256(K,cookie).
>> (k=16) even though the output of HMAC-SHA256 is 256 bits. m only
>> serves to force the initiator to go through
> And another drawback of this approach is that the responder must do
> quite a lot of work
> to prepare puzzle. It must first calculate S1||S2||…||Sm and then for
> each Si calculate Hi.
> where the puzzle goes for free, it is non insignificant (especially as
> we're trying
>>> > On Feb 1, 2015, at 8:38 PM, Scott Fluhrer (sfluhrer) > >
>>> <[email-masked]> wrote:
>>> >
>>> > If you want to tighten up the time between worse case and average
>>> case >  > time taken by the problem solver, might I suggest this:
>>> >
>>> > - When the verifier is asked to generate a problem, it pick a nonce
>>> N, >  > and use it to compute m k-bit values
>>> S_1, S_2, ..., S_m (for example, S_1 || S_2 || ... || S_m =
>>> AES_key(N), where the AES key is secret to the verifier),
>>> > - The verifier verifies that the value N was what was originally
>>> given >  > (for example, the nonce might include the solver's
>>> IP address and a timestamp), and that the values S_1 ||  S_2 || ...
>>> || S_m = AES_key(N||0), (or alternatively,
>>> > The solver can always solve the problem by computing 2**k hashes;
>>> with >  > moderate m, we can make it unlikely
>>> > Of course, the cost of doing this is a) larger messages, and b)
>>> larger >  > up-front cost generating the problem
>>> So the responder now calculates 8 hashes: for each i Hi =
>>> SHA256(COOKIE || Si) or better yet, Hi = PRF(Si, COOKIE).
>>>
>>> the possible Si-s and find all of them. There is a small chance of
>>> making an error if two 16-bit values produce
>>> the same result when using the PRF on the cookie. The initiator
>>> repeats the request along with the nonce and Si for all i.
>>>

---

From: Paul Hoffman <[email-masked]>
Date: Sun, 8 Feb 2015 14:02:52 -0800

On Feb 8, 2015, at 1:20 PM, Yaron Sheffer <[email-masked]> wrote:
> I think we've come a full circle. We now have a proposal that makes proof-of-work more deterministic for each type of client (which I find very useful). But the weaker clients will always lose, no matter what POW solution we choose. This has been a problem with this proposal from day one and it's a limitation that we as a group need to decide whether to accept or not. In a world where some clients are 100X more powerful than others, IMHO this result is something we have to live with.
> 
> The only partial solution I see to this problem is to recommend using RFC 5723 session resumption, so that clients who have recently connected can reconnect even in DoS situations.

Can a gateway sanely do session resumption when it is under DoS attack? That is, can the gateway safely allocate CPU resources to a purported session resumption?

--Paul Hoffman

---

From: Yaron Sheffer <[email-masked]>
Date: Mon, 09 Feb 2015 01:21:15 +0200

> Can a gateway sanely do session resumption when it is under DoS attack? That is, can the gateway safely allocate CPU resources to a purported session resumption?

Yes, of course. It just needs to verify the integrity (MAC) of the 
received ticket (as easy or easier than our proposed puzzle 
verification), and then the rest of the exchange is lighter-weight than 
a typical IKE exchange. See 
http://tools.ietf.org/html/rfc5723#section-4.3.2.

Thanks,
	Yaron

---

From: Paul Hoffman <[email-masked]>
Date: Sun, 8 Feb 2015 16:44:07 -0800

On Feb 8, 2015, at 3:21 PM, Yaron Sheffer <[email-masked]> wrote:
> Yes, of course. It just needs to verify the integrity (MAC) of the received ticket (as easy or easier than our proposed puzzle verification), and then the rest of the exchange is lighter-weight than a typical IKE exchange. See http://tools.ietf.org/html/rfc5723#section-4.3.2.

I knew the latter part, but I was more concerned about the former. As long as the verification is no harder than the proposed puzzles, then yes, resumption seems like a good addition. I wanted to be sure that it wasn't harder.

--Paul Hoffman

---

From: Paul Wouters <[email-masked]>
Date: Sun, 8 Feb 2015 21:03:33 -0500 (EST)

On Sun, 8 Feb 2015, Yaron Sheffer wrote:

> proof-of-work more deterministic for each type of client (which I find very 
> useful). But the weaker clients will always lose, no matter what POW solution 
> we choose. This has been a problem with this proposal from day one and it's a 
> limitation that we as a group need to decide whether to accept or not.

I'm not yet convinced this proposal will provide a working solution to
the DDOS problem.

Paul

---

From: Yoav Nir <[email-masked]>
Date: Mon, 9 Feb 2015 16:52:21 +0200

> On Feb 9, 2015, at 4:03 AM, Paul Wouters <[email-masked]> wrote:
> 
>> I think we've come a full circle. We now have a proposal that makes proof-of-work more deterministic for each type of client (which I find very useful). But the weaker clients will always lose, no matter what POW solution we choose. This has been a problem with this proposal from day one and it's a limitation that we as a group need to decide whether to accept or not.
> 

Hi, Paul

“solution” is hard. Whatever we do, an attacker with unlimited resources can throw more at us. 

We could block all regular initiations under load, allowing only RFC 5723 resumptions. But this allows an attacker to force us into this mode and effectively deny service to all initiators that don’t have a saved session. 

So instead we can allow resumptions and also make it more costly for the attacker to mount the attack on regular initiations. Even an easy puzzle, one that my 1.2 GHz single-core ARMv5 with C code can solve in a second is much harder than just the return routability that COOKIE provides. The draft has text about how to make these puzzles a weapon of last resort, so legitimate users hardly ever need to solve them, but even setting the puzzle difficulty to something a strong desktop can do 20 times a second, it’s still better than the two other alternatives: allow the strong desktop to create 1000 half-open SAs in a second, or entirely block the subnet from which the desktop seems to come.

Yoav

---

From: Yaron Sheffer <[email-masked]>
Date: Mon, 09 Feb 2015 18:34:46 +0200

Re: session resumption, I would like to propose the following text:

6.1. Session Resumption

When the Responder is under attack, it MAY choose to prefer previously 
authenticated peers who present a session resumption [RFC 5723] ticket. 
The Responder MAY require such Initiators to include a return 
routability ticket in the IKE_SESSION_RESUME message, as allowed by RFC 
5723, Sec. 4.3.2. Note that the Responder SHOULD cache tickets for a 
short time to reject reused tickets (Sec. 4.3.1), and therefore there 
should be no issue of half-open SAs resulting from replayed 
IKE_SESSION_RESUME messages.

Thanks,
	Yaron

---

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 13 Feb 2015 17:33:21 +0300

Hi all,

I've created new pull request (it fact - updated my previous pull request).
The source file and changes are available at 
https://github.com/ietf-ipsecme/drafts/pull/2

It mostly devoted to using puzzles in IKE_SA_INIT exchange.
I tried to describe it in details, however a few sections
are left blank for now as they are more or less obvious.

This pull request also includes the section describing DoS
protection measures after IKE SA is created and
a short section proposed by Yaron on using resumption
in case of DoS attack. There is also a section describing
the proposed format for the PUZZLE notification.

Regards,
Valery Smyslov.