> On Feb 1, 2015, at 8:38 PM, Scott Fluhrer (sfluhrer) > >
<[email protected]> wrote:
>
> 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).
>
Hi, Scott.
Thanks for the suggestion. Let me see if I understand it correctly:
Responder has a fixed AES key (let’s call it K).
Let’s assume that N is a COOKIE calculated as in RFC 5996.
The responder Calculates S1||S2||…||Sm = AES(K, COOKIE). COOKIE can
be any length,
but for simplicity let’s assume 128-bit so that we don’t have to deal
with IVs, ICs or any other artifacts
of modes of operation. Also, let’s set m=8 and all Si as 16-bit.
So the responder now calculates 8 hashes: for each i Hi =
SHA256(COOKIE || Si) or better yet, Hi = PRF(Si, COOKIE).
The responder sends to the initiator:
- The COOKIE
- Hi for all i.
- The number k, although that can be deduced from the number of His
- An identifier for the PRF algorithm chosen.
The initiator needs to find Si values such that Hi = PRF(Si, COOKIE).
The silly way to do this is to solve run
through all 2^16 possible Si values once for each Hi (8 times), but a
better way would be to run once through
the possible Si-s and find all of them. There is a small chance of
making an error if two 16-bit values produce
the same result when using the PRF on the cookie. The initiator
repeats the request along with the nonce and Si for all i.
The responder now needs to do the following:
- Verify the COOKIE
- Encrypt the COOKIE, resulting (hopefully) in the concatenation of
the Si values.
With the numbers I used in the example, k=16 resulting in 2^16 PRF
calculations on the client.
The puzzle can be made harder by increasing k and breaking the
encrypted COOKIE into larger chunks.
Did I get this correctly?
Thanks
Yoav
