I’ll try that later, but suppose we give the client 16 puzzles to solve, then we expect solving all of them to take 16 times as long, so they can be 16 times easier. So instead of 22 bits, they can be 18 bits. I’m not sure if that increased the chance of getting “stung” by a bad outlier or that it averages better.
But one effect is obvious. If we require the client to solve all puzzles, the server has to check all 16 parts of the solution, and that makes it 16x harder for the server. OTOH if we required to solve just one of the 16, the client could try all 16 at the same time, and have a better chance of finding a “good” outlier. Again, I’m not sure which is the dominant effect. Yoav > On Jan 30, 2015, at 1:27 PM, Valery Smyslov <sva...@gmail.com> wrote: > > Hi, > > I also had some concerns on the variance of the times. But then > another thought came to me. Let's look on this issue from the other side. > The responder will use puzzles only when it feels that it is under attack. > It means, that there are a lot of (thouthands, tens of thouthands) > half-open connections. If responder requests that number of puzzles, > then some of them will appear to be easier to solve than the others. > Every initiator is different from another in terms of computing power and > each of them may receive more or less hard puzzle. > It's like an exam - some tasks are more easy to solve, some are harder. > Some clients will be more lucky, some less. That's a lottery. > But all those differences will be averaged for the responder, so why bother? > > Also if we require initiator to solve several puzzles, than it will need > to send back all the solutions, that will noticeably increase > IKE message size. > > So, while the idea is interesting, I think that the problem it solves > is not important, so why should we bother? > > But it would be nice, if Yoav (as a person who already has > test bed) could check, that if we solve puzzle for 100 > (or better 1000) different cookies, and average the times, > that the results will be less erratic (it would also be great > to measure the deviation of times for each level, not only average). > > Regards, > Valery. > > >> ----- Original Message ----- >> From: Yoav Nir <mailto:ynir.i...@gmail.com> >> To: Yaron Sheffer <mailto:yaronf.i...@gmail.com> >> Cc: IPsecME WG <mailto:ipsec@ietf.org> >> Sent: Friday, January 30, 2015 2:41 AM >> Subject: Re: [IPsec] DDoS puzzle: PRF vs Hash >> >> Interesting. I’ve tried with a few different “cookies”. >> >> Cookie: 4f331b879f6d02322aa894942f66473d8a1949625c488aa0f4f943b441cfd6f4 >> Key=…00003db1 PRF=…4c82f8b80000 #zeros=19 time=0.025 >> Key=…0002ea6c PRF=…5faafb800000 #zeros=23 time=0.250 >> Key=…0124159c PRF=…9136e5000000 #zeros=24 time=26.013 >> >> Cookie: 6756a2fee7047eb87030b5cd7eb97ee24579371f54fecd3bc71f8b028f8c18b1 >> #zeros=14 time=0.016 >> #zeros=15 time=0.035 >> #zeros=19 time=0.134 >> #zeros=20 time=0.837 >> #zeros=21 time=1.932 >> #zeros=22 time=5.646 >> #zeros=24 time=16.790 >> #zeros=27 time=17.477 >> >> Cookie: 61a3a14b02580773234b8a773305aefed61c067775cea9c4797a406cd30fb14f >> #zeros=15 time=0.016 >> #zeros=17 time=0.434 >> #zeros=21 time=1.034 >> #zeros=22 time=1.230 >> #zeros=23 time=16.213 >> #zeros=24 time=25.554 >> #zeros= >> >> Seems like the big issue here is inconsistency. Set the puzzle level to 22 >> bits, and it could be solved in a quarter second or in 5.6 seconds or in >> 1.230. And these are not just outliers - they’re the first three values I >> picked at this length. >> >> 20 bits seems an acceptable difficulty level, but beyond that it becomes too >> erratic. >> >> Yoav >> >>> On Jan 29, 2015, at 11:57 PM, Yaron Sheffer <yaronf.i...@gmail.com >>> <mailto:yaronf.i...@gmail.com>> wrote: >>> >>> Looking at the timing table, there is obviously significant variance in the >>> time to solve each puzzle, compared to the ideal exponential curve. For >>> example, for 28 bits we have 250s, whereas for 29 bits it's 1240s. >>> >>> Would it make sense to require the initiator to return 4 or 8 solved >>> puzzles of the given strength? Of course, the responder would request 2-3 >>> bits of strength less. The net effect should be a lower variance in run >>> times, i.e. more deterministic run time for any particular type of client. >>> >>> Thanks, >>> Yaron >>> >>> On 01/29/2015 11:27 PM, Yoav Nir wrote: >>>> Hi all. >>>> >>>> Following Valery’s suggestion, I’ve created a pull request for replacing >>>> the puzzle mechanism: >>>> >>>> OLD: appending a string to the cookie so that the hash of the extended >>>> string has enough zero bits at the end. >>>> NEW: finding a PRF key such that PRF(k, cookie) has enough zero bits at >>>> the end. >>>> >>>> The source files and change are available at >>>> https://github.com/ietf-ipsecme/drafts/pull/3 >>>> <https://github.com/ietf-ipsecme/drafts/pull/3> >>>> >>>> The relevant section is appended below >>>> >>>> Please let us know what you think. Also about Valery’s pull request >>>> about negotiation. >>>> >>>> Yoav >>>> >>>> 3. Puzzles >>>> >>>> The puzzle introduced here extends the cookie mechanism from RFC >>>> 7296. It is loosely based on the proof-of-work technique used in >>>> BitCoins ([bitcoins]). Future versions of this document will have >>>> the exact bit structure of the notification payloads, but for now, I >>>> will only describe the semantics of the content. >>>> >>>> A puzzle is sent to the Initiator in two cases: >>>> >>>> o The Responder is so overloaded, than no half-open SAs are allowed >>>> to be created without the puzzle, or >>>> o The Responder is not too loaded, but the rate-limiting in >>>> Section 5 prevents half-open SAs from being created with this >>>> particular peer address or prefix without first solving a puzzle. >>>> >>>> When the Responder decides to send the challenge notification in >>>> response to a IKE_SA_INIT request, the notification includes three >>>> fields: >>>> >>>> 1. Cookie - this is calculated the same as in RFC 7296. As in RFC >>>> 7296, the process of generating the cookie is not specified. >>>> 2. Algorithm, this is the identifier of a PRF algorithm, one of >>>> those proposed by the Initiator in the SA payload. >>>> 3. Zero Bit Count. This is a number between 8 and 255 that >>>> represents the length of the zero-bit run at the end of the >>>> output of the PRF function calculated over the Keyed-Cookie >>>> payload that the Initiator is to send. Since the mechanism is >>>> supposed to be stateless for the Responder, the same value is >>>> sent to all Initiators who are receiving this challenge. The >>>> values 0 and 1-8 are explicitly excluded, because the value zero >>>> is meaningless, and the values 1-8 create a puzzle that is too >>>> easy to solve for it to make any difference in mitigating DDoS >>>> attacks. >>>> >>>> Upon receiving this challenge payload, the Initiator attempts to >>>> calculate the PRF using different keys. When a key is found such >>>> that the resulting PRF output has a sufficient number of trailing >>>> zero bits, that result is sent to the Responder in a Keyed-Cookie >>>> notification, as described in Section 3.1. >>>> >>>> When receiving a request with a Keyed-Cookie, the Responder verifies >>>> two things: >>>> >>>> o That the cookie part is indeed valid. >>>> o That the PRF of the transmitted cookie calculated with the >>>> transmitted key has a sufficient number of trailing zero bits. >>>> >>>> Example 1: Suppose the calculated cookie is >>>> fdbcfa5a430d7201282358a2a034de0013cfe2ae (20 octets), the algorithm >>>> is HMAC-SHA256, and the required number of zero bits is 18. After >>>> successively trying a bunch of keys, the Initiator finds that the key >>>> that is all-zero except for the last three bytes which are 02fc95 >>>> yields HMAC_SHA256(k, cookie) = >>>> 843ab73f35c5b431b1d8f80bedcd1cb9ef46832f799c1d4250a49f683c580000, >>>> which has 19 trailing zero bits, so it is an acceptable solution. >>>> >>>> Example 2: Same cookie, but this time the required number of zero >>>> bits is 22. The first key to satisfy that requirement ends in >>>> 960cbb, which yields a hash with 23 trailing zero bits. Finding this >>>> requires 9,833,659 invocations of the PRF. >>>> >>>> >>>> _______________________________________________ >>>> IPsec mailing list >>>> IPsec@ietf.org >>>> https://www.ietf.org/mailman/listinfo/ipsec >>>> >> >> >> >> _______________________________________________ >> IPsec mailing list >> IPsec@ietf.org >> https://www.ietf.org/mailman/listinfo/ipsec
_______________________________________________ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
