Subject: [IPsec] Restarting the discussion about the puzzle

From: Yoav Nir <[email-masked]>
Date: Thu, 7 May 2015 16:52:09 +0300

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

---

From: Yaron Sheffer <[email-masked]>
Date: Sat, 09 May 2015 19:32:12 +0300

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

---

From: Yoav Nir <[email-masked]>
Date: Mon, 11 May 2015 18:01:42 +0300

> On May 9, 2015, at 7:32 PM, Yaron Sheffer <[email-masked]> wrote:
> 
> 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.
> 

I’m sure that less variance is better than more variance, but that comes at the expense of more work for the responder. So do we set the number of returned results to 1, with minimal work for the responder and maximum variance?  Do we set it to 8, with a nice balance between fairness and responder work?  Do we set it to 64, with a huge packet, a lot of responder work and maximum fairness?  Or do we let the responder decide and communicate through the challenge, which has some complexity cost?

Yoav

---

From: Yaron Sheffer <[email-masked]>
Date: Mon, 11 May 2015 18:19:34 +0300

IMO we should choose a reasonable balance and fix it in the document. We 
should care about packet size for sure, but 64 hashes are not that much 
work.

Thanks,
	Yaron

---

From: "Valery Smyslov" <[email-masked]>
Date: Wed, 20 May 2015 16:13:11 +0300

Hi Yaron,

> 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.

> 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.

> > • 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:
> >
> 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
>
>
>