Subject: [IPsec] DDoS Protection - single vs multiple solutions

From: Yoav Nir <[email-masked]>
Date: Wed, 17 Feb 2016 18:09:59 +0200

Hi

As we’re nearing WGLC for the DDoS protection draft, there is a question we’ve left open in the past that should be resolved.

The issue is with the variability of the time it takes to solve a puzzle. To demonstrate it, I ran a simulation of trying to solve a 20-bit puzzle 1000 times on some specific hardware [1]. The results are available in ODS [2] and XSLX [3] formats, and also summarized below:

    Average                     1.3226669
    Min                         0.0001190
    Max                         7.9450660
    Standard Deviation          1.2873387
    5th percentile              0.0843579
    95th percentile             3.8978098
    95th / 5th percentiles          46.2
    Max / Min                    66765.3

So an “unlucky” initiator, defined here as the 95th percentile for solution time, takes 46x as long to solve the puzzle as a “lucky” one (defined as the 5th percentile). This introduces delays that are visible to human users, whether they are looking at a dialog box on a remote access client or are waiting for their networked application to work.

A while ago Scott Fluhrer suggested a way to make this more fair [4]. The puzzle we were discussing then was a little different, but his method can be adapted to the puzzle that is in the current draft. Instead of requiring just one solution, require the client to find several solutions. The puzzle can be made correspondingly easier. The expected time for finding one solution for a 20-bit puzzle should be the same as the time to find four solutions to an 18-bit puzzle, or 16 solutions to a 16-bit puzzle. The results in [2] and [3] bear this out.

While the expected time is pretty similar, the different between worst case and average case is much better:

    Test Parameters       20x1         18x4         16x16
    Average             1.3226669    1.3400430    1.3445518
    Min                 0.0001190    0.1013960    0.5210680
    Max                 7.9450660    3.9507410    3.0532380
    Standard Deviation  1.2873387    0.6568984    0.3353262
    5th percentile      0.0843579    0.4548676    0.8529980
    95th percentile     3.8978098    2.5217214    1.9443243
    95th / 5th perc.        46.2          5.5          2.3
    Max / Min            66765.3         39.0          5.9

In my opinion the right thing to do is to choose a multi-solution puzzle and adjust the difficulty accordingly. This adds a little complexity but provides a more consistent delay. There have been two arguments against it so far. 

1. The Initial request will become larger with multiple solutions. This is not necessarily true, since the initiator is still limited in the number of possible keys it can try. We can have PRF keys be all zeros except for the last 32 or 64 bits. This is good enough, because no current hardware is able to test 2^32 keys in a reasonable time, and 64-bits gives us protection for the foreseeable future. So a single result can be as low as 4 or 8 octets.

2. The Responder will need to spend more resources verifying more solutions. This is not necessarily true either, because the Responder can just pick one or two solutions at random and only verify them. Not that a single run of the HMAC function takes that many resources.

Yoav

[1] 2.4 GHz Intel Core i5. The CPU in a late 2013 13-inch MacBook Pro.
[2] https://trac.tools.ietf.org/wg/ipsecme/trac/raw-attachment/wiki/TempDocs/puzzle_stats.ods
[3] https://trac.tools.ietf.org/wg/ipsecme/trac/raw-attachment/wiki/TempDocs/puzzle_stats.xslx
[4] https://mailarchive.ietf.org/arch/msg/ipsec/30_tZekTBxdYPFVc6B1bXaEMtEQ

---

From: Yoav Nir <[email-masked]>
Date: Wed, 17 Feb 2016 21:17:34 +0200

On 17 Feb 2016, at 6:09 PM, Yoav Nir <[email-masked]> wrote:

> A while ago Scott Fluhrer suggested a way to make this more fair

As it turns out, this was first suggested by Yaron:
https://mailarchive.ietf.org/arch/msg/ipsec/_JUTE8p5H6bhFOA1HCuaYX1NCKQ

Scott’s idea was a little different.

Sorry for the confusion.

Yoav

---

From: Yaron Sheffer <[email-masked]>
Date: Wed, 17 Feb 2016 21:53:01 +0200

Scott's idea was different, and possibly better. At the cost of some 
Responder compute work, his idea makes the Initiator's effort nearly 
deterministic.

https://mailarchive.ietf.org/arch/msg/ipsec/30_tZekTBxdYPFVc6B1bXaEMtEQ

Thanks,
     Yaron

On 02/17/2016 09:17 PM, Yoav Nir wrote:
> _______________________________________________
> IPsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ipsec

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 17 Feb 2016 20:03:14 +0000

On the other hand (since we're complementing each other's ideas), with Yavon's idea, it's easy to have puzzle N+1 depend on the solution to puzzle N.  That may limit (to some small extent) the advantage that a highly parallel system would have in solving puzzles - while parallelism might be able to speed any individual puzzle, they would still have to solve the sequence of puzzles sequentially.

> -----Original Message-----
> From: IPsec [mailto:[email-masked]] On Behalf Of Yaron Sheffer
> Sent: Wednesday, February 17, 2016 2:53 PM
> To: Yoav Nir; [email-masked] WG
> Subject: Re: [IPsec] DDoS Protection - single vs multiple solutions
> 
> https://mailarchive.ietf.org/arch/msg/ipsec/_JUTE8p5H6bhFOA1HCuaYX1NC
> K
> > Q
> >

---

From: "Valery Smyslov" <[email-masked]>
Date: Thu, 18 Feb 2016 15:58:47 +0300

Hi,

> As we’re nearing WGLC for the DDoS protection draft, there is a question we’ve left
> open in the past that should be resolved.
>
> The issue is with the variability of the time it takes to solve a puzzle. To demonstrate it,
> I ran a simulation of trying to solve a 20-bit puzzle 1000 times on some specific hardware [1].
> The results are available in ODS [2] and XSLX [3] formats, and also summarized below:
>
>    Average                     1.3226669
>    Min                         0.0001190
>    Max                         7.9450660
> So an “unlucky” initiator, defined here as the 95th percentile for solution time, takes 46x as long
> to solve the puzzle as a “lucky” one (defined as the 5th percentile). This introduces delays that are visible
> to human users, whether they are looking at a dialog box on a remote access client or are waiting
> for their networked application to work.
>
> A while ago Scott Fluhrer suggested a way to make this more fair [4]. The puzzle we were discussing
> then was a little different, but his method can be adapted to the puzzle that is in the current draft.
> Instead of requiring just one solution, require the client to find several solutions. The puzzle can be made
> correspondingly easier. The expected time for finding one solution for a 20-bit puzzle should be the same
> as the time to find four solutions to an 18-bit puzzle, or 16 solutions to a 16-bit puzzle. The results in [2]
> and [3] bear this out.
>
> In my opinion the right thing to do is to choose a multi-solution puzzle and adjust the difficulty accordingly.
> This adds a little complexity but provides a more consistent delay. There have been two arguments against it so far.

I tend to support this idea, but I think in this case the sub-puzzles must be chained to deal with parallel solving.
Something like the following:

Puzzle_data[0] = cookie
Puzzle_data[1] = Puzzle_solution[0] | cookie
Puzzle_data[2] = Puzzle_solution[1] | cookie
...
Puzzle_data[n] = Puzzle_solution[n-1] | cookie

Or probably someone could suggest more clever construction?

Note, that the draft already supports multiple puzzles by allowing the responder
to request another puzzle after verifying the received solution. However, this is different
from the proposed mechanizm and is more focused on solving the problem
of wide range of initiators' capabilities. The two mechanisms would complement
each other.

Should the number of sub-puzzles be fixed in the protocol or should we allow
the responder to specify it in the PUZZLE notification? It seems that after 4 (or 8?)
sub-puzzles an effect of sub-puzzling becomes less and less visible.

> 1. The Initial request will become larger with multiple solutions. This is not necessarily true, since the initiator 
> is still
> limited in the number of possible keys it can try. We can have PRF keys be all zeros except for the last 32 or 64 
> bits.
> This is good enough, because no current hardware is able to test 2^32 keys in a reasonable time, and 64-bits gives
> us protection for the foreseeable future. So a single result can be as low as 4 or 8 octets.

The size of the request will be larger in any case. Currently Puzzle Solution payload
may contain as few bytes of the key as needed (for PRFs with variable-size keys).
But I don't think the number of sub-puzzles should be more than 4 (or 8), so that's
not such a big problem.

> 2. The Responder will need to spend more resources verifying more solutions. This is not necessarily true either,
> because the Responder can just pick one or two solutions at random and only verify them. Not that a single run
> of the HMAC function takes that many resources.

It's true, however there is a tradeoff. If the number of sub-puzzles is small (say 4), then verifying
a single solution gives an attacker that solves a single sub-puzzle a 25% chance to pass through.
Is it always acceptable for responder? I think the responder SHOULD verify all (or at least half).

> Yoav

Regards,
Valery.

---

From: Yoav Nir <[email-masked]>
Date: Thu, 18 Feb 2016 15:51:01 +0200

> Or probably someone could suggest more clever construction?

I’m not really against this, but is parallel solving really an issue? It does give an advantage to an 8-core desktop or 16-core server over a 2-core laptop. OTOH it might mitigate the power disparity between smartphones and laptops because phones have 4, 6, or 8 cores, while most laptops tend to have 2. 

Yoav

---

From: "Valery Smyslov" <[email-masked]>
Date: Thu, 18 Feb 2016 17:20:02 +0300

> I’m not really against this, but is parallel solving really an issue?
> It does give an advantage to an 8-core desktop or 16-core server over a 2-core laptop.
> OTOH it might mitigate the power disparity between smartphones and laptops because
> phones have 4, 6, or 8 cores, while most laptops tend to have 2.

The primary goal of sub-puzzling (as I see it) is not to make puzzle equally
hard for all clients, but to make puzzle hardness more predictable.
As far as I understand you got the figures from your previous message
by sequential solutions of a given number of puzzles, didn't you?
Did you experimented with parallel puzzle solving on multicore CPUs?
Probably the effect of sub-puzzling in this case would be a bit different.
It's interesting to compare the results.

Regards,
Valery.

---

From: Yoav Nir <[email-masked]>
Date: Thu, 18 Feb 2016 16:57:39 +0200

> On 18 Feb 2016, at 4:20 PM, Valery Smyslov <[email-masked]> wrote:
> 

Sure, but I’d rather not make the client disparity problem more severe.

> It's interesting to compare the results.

My tests are single-CPU mostly out of convenience. I iterated over possible keys until 1, 4, or 16 solutions were found. This should be very easily parallelizable and times would be halved if I had used both cores.

With a chain such as you’re suggesting, I could still parallelize. For each step I could still partition the key space and search in parallel until one solution was found before proceeding to the next step. 

Yoav

---

From: "Valery Smyslov" <[email-masked]>
Date: Thu, 18 Feb 2016 18:46:25 +0300

> With a chain such as you’re suggesting, I could still parallelize. For each step I could still
> partition the key space and search in parallel until one solution was found before proceeding to the next step.

Yes. So it seems that the chaining is useless.

Regards,
Valery.