Re: [IPsec] DDoS puzzle: PRF vs Hash

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:ipsec-bounces@ietf.org] 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 <ynir.ietf@gmail.com> wrote:
>>
>>
>>> On Jan 31, 2015, at 12:35 AM, Yoav Nir <ynir.ietf@gmail.com> wrote:
>>>
>>>
>>>> On Jan 30, 2015, at 3:37 PM, Yaron Sheffer <yaronf.ietf@gmail.com> 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
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec