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