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

[Nick Mathewson]

Crypto people who have been following threads about the
circuit-establishment handshake will be interested in the new paper,
"Anonymity and one-way authentication in key-exchange protocols", by
Goldberg, Stebila, and Ostaoglu. Here's the version they updated
today:

http://www.cacr.math.uwaterloo.ca/techreports/2011/cacr2011-11.pdf

If we're moving to an improved handshake, this might be a good
candidate to consider.  The protocol itself is on page 14.

Some notes, written by a guy who knows less crypto than everybody involved:

  * It's a pure Diffie-Hellman based system, which would lend itself
nicely to use with ECC.

  * It seems to require the same number of exponentiations as our
current system, but Ian Goldberg notes that if you want to compute X^a
and X^b at the same time you can do so more efficiently by taking into
account the shared base.

  * The security proof requires that the Gap DH assumption holds over
the group -- basically, that computing the Decisional DH problem is
easy, but computing the Computational DH problem is hard.  This
assumption isn't true of most basic ECC groups -- I think it means you
need to use a pairing-based system instead for the proof to hold. I'd
bet that the authors aren't seriously suggesting that we use
pairing-based crypto, but I'm wondering how much they were able to
prove in a groups where DDH is hard.

  * I haven't read over the security model closely yet; folks should
review it for reasonableness.

  * I'm hoping to write this up as a proposed spec soon, unless Ian or
somebody wants to give it a shot.

yrs,
-- 
Nick