> 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.
OK, I’ve tried that.
But first, I found an inefficiency in my code, so I’ve fixed it and ran the
tests again. Here are the results:
cookie set
#bits 1 2 3
===== ========= ========= =========
15 0.016
16 0.031 0.065 0.057
17 0.087 0.820 0.250
18 0.289
19 0.420
20 5.965 0.401
21 14.055 0.916
22 19.065 2.074
23 23.753 3.067 6.688
24 5.414 48.045
25 29.924
26 60.088 130.753
27
28 87.437
29 111.921
So still pretty much all over the place. So I tried Yaron’s suggestion of
calculating until I find 16 keys that produce at least so many zero bits. Here
are the results for 16 keys each time:
cookie set
#bits 1 2 3 4
===== ========= ========= ========= =========
15 0.780 0.954 0.678 0.778
16 1.734 2.056 1.575 1.162
17 3.090 4.161 2.932 2.832
18 4.981 7.463 4.766 4.380
19 11.612 10.069 14.525 8.486
20 22.789 21.111 30.961 24.146
21 40.066 39.875 57.930 53.785
22 92.264 116.453 123.352 139.584
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.
Yoav
_______________________________________________
IPsec mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/ipsec
