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