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
_______________________________________________
IPsec mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/ipsec
