> On Feb 1, 2015, at 8:38 PM, Scott Fluhrer (sfluhrer) <sfluh...@cisco.com> > 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 _______________________________________________ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
