What I would suggest is: we give the client a single puzzle, and ask it
to return 16 different solutions. Indeed each puzzle then should be 16X
easier. The nice thing is, the server should only check *one* of them,
at random. The client would still need to solve all of them because it
doesn't want to risk the exchange being rejected because some solutions
are invalid (the game theory is probably more complex than that, but I
think what I'm saying is still close to the truth).
So: the client does the same amount of work, the server does the same
amount of work, but the client run-time is still much more deterministic.
Thanks,
Yaron
On 01/30/2015 02:42 PM, Yoav Nir wrote:
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 <[email protected]
<mailto:[email protected]>> 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:[email protected]>
*To:* Yaron Sheffer <mailto:[email protected]>
*Cc:* IPsecME WG <mailto:[email protected]>
*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]
<mailto:[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] <mailto:[email protected]>
https://www.ietf.org/mailman/listinfo/ipsec
------------------------------------------------------------------------
_______________________________________________
IPsec mailing list
[email protected] <mailto:[email protected]>
https://www.ietf.org/mailman/listinfo/ipsec
_______________________________________________
IPsec mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/ipsec
