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

[Robert Ransom]

On 8/9/12, aniket kate <aniketpkate at gmail.com> wrote:
>> Date: Thu, 9 Aug 2012 00:22:59 +0000
>> From: Robert Ransom <rransom.8774 at gmail.com>
>>
>> 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?

>> * 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.)
>
> I went through A-DHKE-1 description (Page 36 of Eprint 1999/012). I
> find that A-DHKE-1 also requires one online signature generation on
> the server side along with one online exponentiation. Therefore,
> A-DHKE-1 is computationally more expensive than the discussed protocol
> and probably even the ntor protocol based on the employed signature
> scheme.

For a short-term keypair, Ed25519 session secret keys can be generated
by applying a PRF to a counter; the corresponding public keys can be
computed offline.  This leaves only a few hash computations and a
multiplication in the exponent field to be done online for the
signature generation; neither of these is as expensive as EC point
multiplication.

The server's Diffie-Hellman keypair can be reused for more than one
protocol run (keeping it for up to 5 minutes is very unlikely to
reduce forward secrecy) if either (a) the server performs replay
detection for client keys or (b) the protocol includes the signature
system's session key in the material fed to the KDF (along with the DH
shared secret).

So, A-DHKE-1 can indeed be performed with one offline exponentiation
(for the Ed25519 session key) and one online exponentiation (to
compute the DH shared secret) on the server side.


Robert Ransom