On Wed, May 11, 2011 at 2:19 PM, Ian Goldberg iang@cs.uwaterloo.ca wrote:
Thanks! I think the git version has most of the trivial stuff cleaned up now (thanks for a patch from George Kadianakis). I've also made notes for most of your suggestions.
On Wed, May 11, 2011 at 01:33:17PM -0400, Nick Mathewson wrote:
[...]
generates a keypair of y, Y=EXP(g,y) and computes
secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PROTOID KEY_SEED = H(secret_input, t_key) verify = H(secret_input, t_verify)
Depending on the lengths involved, the above may be doing some unnecessary work.
What would you suggest instead?
[...]
where t_expand1..N are tweaks for the hash.
Krawczyk has a paper on how to do this crypto-correctly:
http://eprint.iacr.org/2010/264
See section 8 for an explanation of why the above is not ideal. Note that our "KEY_SEED" is approximately his "PRK", not his "SKM", as it's already been hashed. So if t_expand = PROTOID | ":expand", what's he's suggesting is
K = K_1 | K_2 | ... where K_1 = H(t_expand | 0, KEY_SEED) K_(i+1) = H(K_i | t_expand | i, KEY_SEED)
Note that KEY_SEED is used as the HMAC *key*, not the *message*.
Changed.
[...]
Note that each H operation is 2 underlying hashes.
RIght. If we can get away with something faster than HMAC_SHA256 here, I'd love to move to it. SHA3 is right around the corner, and most of the candidates seem to allow better constructions for "tweakability" than HMAC.
Would this make a difference, actually? Let's see. Looking at the numbers from my desktop and doing some back-of-the-envelope calculations.
I would expect the old handshake to take, total, about 3500 microseconds. (This is counting both client and server crypto.)
If we tried to do that with 2048-bit keys, it would take, total, about 14700 microseconds.
And I would expect the new handshake to take, total, something like 830 microseconds. That's more than 4x faster than the old one, and more than 17x faster than the old one using keys with equivalent security. (Nice!)
Of that 830 microseconds, I'd spend something like 3-5% doing SHA256 hashes. So it might not be worthwhile spending too much time optimizing the number of hashes here.
thoughts?