Hi Yaron,
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.
The problem is that the server doesn't have enough information either.
Selecting appropriate puzzle difficulty so that weak legitimate clients
are not thrown away and, on the other hand, the server could
effectively defend against DoS attack looks like the main problem
of puzzles.
To answer your question, I think we've already been down this path and
reducing the variance is certainly a good thing.
I agree, that it is a good thing in general, but what the price?
Is the game worth the candle? If the solution for 1 puzzle
is the key for PRF, then its size is the PRF's key size.
For HMAC-SHA2-256 it is 32 bytes. 8 solutions would take
256 bytes, 16 - 512 bytes. Don't you think it is too much
for IKE_SA_INIT messages to be sure it is not fragmented?
Let's look on the problem from another angle. The puzzles are
needed only if the server is under DoS attack, and the most
dangerous scenario is DDoS attack. In this case the server
meets thouthans of clients, most of which are attackers.
All the clients are of different power. In this situation what
would we get by spending efforts to reduce the variance
of puzzles? Imagine we have implemented some mechanism
that guaranties that different puzzles require roughly the same
time to be solved on a single computer. But the diversity
of computing power of clients would make this effort far less
valuable - it would be great if the server could know the power
of any client beforehand and give each client its own puzzle,
but it is impossible.
Regards,
Valery.
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
_______________________________________________
IPsec mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/ipsec
