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
data_20.xlsx
Description: MS-Excel 2007 spreadsheet
_______________________________________________ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
