[tor-dev] Another key exchange algorithm for extending circuits: alternative to ntor?

[Robert Ransom]

On 8/8/12, Nick Mathewson <nickm at freehaven.net> wrote:

> Michael Backes, Aniket Kate, and Esfandiar Mohammadi have a paper in
> submission called, "An Efficient Key-Exchange for Onion Routing".
> It's meant to be more CPU-efficient than the proposed "ntor"
> handshake.  With permission from Esfandiar, I'm sending a link to the
> paper here for discussion.
>
> http://www.infsec.cs.uni-saarland.de/~mohammadi/owake.html
>
> What do people think?

* This paper has Yet Another ‘proof of security’ which says nothing
about the protocol's security over any single group or over any
infinite family of groups in which (as in Curve25519) the Decision
Diffie-Hellman problem is (believed to be) hard.

* The protocol requires that EC points be either transmitted in or
converted from and to a form in which point addition is efficient.
(ntor does not require point addition, so it can be implemented
initially using curve25519-donna.)

* If you finish my implementation of the Ed25519 group operations
(which you would need in order to implement this protocol), you can
use them to implement a signature-based protocol (specified as
A-DHKE-1 in http://eprint.iacr.org/1999/012), which requires only one
precomputed and one on-line exponentiation per protocol run on the
server when implemented with a slightly modified version of Ed25519.
(The client's performance is much less important than the server's.)


Robert Ransom