Hi Yoav,
First, I raised a third concern, which is that allowing the client to
decide on the difficulty of the puzzle it is willing to solve adds
unneeded complexity. Basically the client doesn't have enough
information to make a good decision.
To answer your question, I think we've already been down this path and
reducing the variance is certainly a good thing.
Thanks,
Yaron
On 05/07/2015 04:52 PM, Yoav Nir wrote:
Hi.
As a reminder, there were two concerns about the difficulty of puzzles:
• That some clients are weaker than others and therefore are able to
try less keys in a unit of time
• That individual puzzles might prove more difficult than other
puzzles, so some “unlucky” initiators might take too long to solve the puzzle.
This is about the second issue. I’d be glad if someone could make a measurement
of solving the proposed puzzle on an ARM processor so that we can know how much
of an issue #1 is.
As Tero has mentioned, there are no easy or hard puzzles. Depending on how you
order your guesses you might stumble upon the solution very quickly, or you
might be trying millions of keys before hitting the answer. Choose a different
ordering of your guesses for the same puzzle, and you might get very different
results. Still, we don’t like that luck plays such a role.
One way to reduce the variance is to increase the sample size: instead of
looking for one key for a hard puzzle, we can require the initiator to return
several correct solutions for an easier puzzle. The advantage is that it
indeed reduces the variance. The disadvantage is that the responder’s job
becomes more difficult, as it has to verify not one but several correct
solutions.
I’ve run a test of 20 randomly-generated cookies, and set the puzzle difficulty
to 20 bits when requiring 1 solutions, 19 bits when requiring 2 solutions, 18
bits when requiring 4 solutions, etc. The full results are in the attached
Excel file (all results in seconds), but here’s a summary:
Bits | keys | median | % over twice median
-----+------+--------+--------------------
| 20 | 1 | 0.947 | 30.0%
| 19 | 2 | 1.309 | 15.0%
| 18 | 4 | 1.464 | 5.0%
| 17 | 8 | 1.516 | 1.5%
| 16 | 16 | 1.499 | 0.5%
| 15 | 32 | 1.507 | 0.0%
| 14 | 64 | 1.499 | 0.0%
-----+------+--------+——————————
I could increase the sample to get more accurate results, or look for results
that are 3 times the median or 3 times the average etc. But just looking at
this it seems to me that either 8 or 16 keys is the sweet spot, where an
initiator is not likely to get stuck, a packet is not too big, and the load on
the responder is not too great.
Comments?
Yoav
_______________________________________________
IPsec mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/ipsec
_______________________________________________
IPsec mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/ipsec
