If you want to tighten up the time between worse case and average case time taken by the problem solver, might I suggest this:
- When the verifier is asked to generate a problem, it pick a nonce N, and use it to compute m k-bit values S_1, S_2, ..., S_m (for example, S_1 || S_2 || ... || S_m = AES_key(N), where the AES key is secret to the verifier), and publish k, N, HASH(N, S_1), HASH(N, S_2), ..., HASH(N, S_m) - To solve the problem, the solver needs to produce the values S_1, S_2, ..., S_m, and send back N, S_1, S_2, ..., S_m - The verifier verifies that the value N was what was originally given (for example, the nonce might include the solver's IP address and a timestamp), and that the values S_1 || S_2 || ... || S_m = AES_key(N||0), (or alternatively, that those values produces the hashes it sent). The solver can always solve the problem by computing 2**k hashes; with moderate m, we can make it unlikely that it can be done with significantly fewer hashes; I would suggest m=4. Of course, the cost of doing this is a) larger messages, and b) larger up-front cost generating the problem (which, IMHO, isn't too bad -- one AES encryption, and m hash computations; however, you are free to disagree). -----Original Message----- From: IPsec [mailto:[email protected]] On Behalf Of Yaron Sheffer Sent: Sunday, February 01, 2015 12:37 PM To: Yoav Nir Cc: IPsecME WG; Valery Smyslov Subject: Re: [IPsec] DDoS puzzle: PRF vs Hash Hi Yoav, This is good, but I'm not sure if it's good enough. The ratio between min and max (which I trust more than the "mean +/- 3s" rule, because this is not a normal distribution) is consistently around 4. So if you have to design your timeouts on a particular machine, you would still have a lot of uncertainty. For comparison, could you try again with 64 replacing the 16 tries, and with lower bit lengths? Thanks, Yaron On 02/01/2015 11:46 AM, Yoav Nir wrote: > And now it's really attached. > > > > >> On Feb 1, 2015, at 11:45 AM, Yoav Nir <[email protected]> wrote: >> >> >>> On Jan 31, 2015, at 12:35 AM, Yoav Nir <[email protected]> wrote: >>> >>> >>>> On Jan 30, 2015, at 3:37 PM, Yaron Sheffer <[email protected]> wrote: >>>> >>>> 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. >> >> <snip /> >> >>> Note that these are still single core results, and most laptops can do >>> twice or four times as much. Now, I know that what I SHOULD be doing is to >>> randomly generate 100 "cookies" and then calculate the times for different >>> bit lengths for each of them, and then calculate mean and standard >>> deviation. But just by looking, it looks like it's much closer to what we >>> want. 16 bits would be a fine puzzle level for my laptop. No idea about a >>> phone, although I could try to compile this and run it on an ARM-based >>> appliance, which should match phones. >> >> OK. Now I have done it right. See attached. The data suggests that 15 or 16 >> bits is the level of puzzle that for this kind of hardware is challenging >> but not too onerous. Add another bit if we assume (probably correctly) that >> the vast majority of laptops have dual cores at least. >> >> I would like to run a similar test on an ARM processor, though. The >> capabilities of phones and tablets are all over the place, what with >> different versions of ARM processors and devices having anything from dual >> to octo-core, but it would be nice to get ballpark figures. >> >> Yoav >> > _______________________________________________ IPsec mailing list [email protected] https://www.ietf.org/mailman/listinfo/ipsec _______________________________________________ IPsec mailing list [email protected] https://www.ietf.org/mailman/listinfo/ipsec
