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
