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

[Ian Goldberg]

On Wed, May 11, 2011 at 03:42:30PM -0400, Nick Mathewson wrote:
> 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.

You're totally right.  No sense stressing about how many hash blocks
we're processing.

Remember also that if you have non-black-box access to the
exponentiation routine, the server can compute X^y and X^b
simultaneously.  That will make a bigger difference in time, but is not
really relevant from a spec-level standpoint.

   - Ian