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