[tor-dev] New paper by Goldberg, Stebila, and Ostaoglu with proposed circuit handshake

[Nick Mathewson]

On Wed, May 11, 2011 at 2:19 PM, Ian Goldberg <iang at 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?
-- 
Nick