Another key exchange algorithm for extending circuits: alternative to ntor?
Hi, all! 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? -- Nick
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?
* 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
On Wed, Aug 8, 2012 at 8:22 PM, Robert Ransom <rransom.8774@gmail.com> wrote:
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?
* 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.
Do you think a DDH oracle cracks CDH in Curve25519? If no the theorem says something.
Robert Ransom _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Sincerely, Watson Ladd -- "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither Liberty nor Safety." -- Benjamin Franklin
On 8/9/12, Watson Ladd <watsonbladd@gmail.com> wrote:
On Wed, Aug 8, 2012 at 8:22 PM, Robert Ransom <rransom.8774@gmail.com> wrote:
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?
* 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.
Do you think a DDH oracle cracks CDH in Curve25519? If no the theorem says something.
Do you think a DDH oracle for Curve25519 can be implemented efficiently? Robert Ransom
On Thu, Aug 9, 2012 at 2:10 PM, Robert Ransom <rransom.8774@gmail.com> wrote:
On 8/9/12, Watson Ladd <watsonbladd@gmail.com> wrote:
On Wed, Aug 8, 2012 at 8:22 PM, Robert Ransom <rransom.8774@gmail.com> wrote:
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?
* 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.
Do you think a DDH oracle cracks CDH in Curve25519? If no the theorem says something.
Do you think a DDH oracle for Curve25519 can be implemented efficiently?
I don't see the relevance of this. What matters is how much of a gain a DDH oracle provides on the CDH problem. There may be groups where DDH oracles make it easy to break CDH. Such proofs are nothing new: Schnorr signatures are secure in the random oracle model, meaning they turn an attack that succeeds with a random oracle into a CDH solver. We've already accepted oracle based security reductions. Your argument is that because we don't have a DDH oracle at hand, we can't use the reduction to demonstrate security. But I don't think that's the case. If OWAKE is insecure, and the space aliens drop a DDH oracle on Earth CDH falls. But if OWAKE is secure then the aliens just give us a DDH oracle. This seems to me to be a significant difference, and much better then the situation with random oracle models. (SHA-256 is observably not a random oracle)
Robert Ransom _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Sincerely, Watson Ladd -- "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither Liberty nor Safety." -- Benjamin Franklin
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?
Ohhh-kay, after trying to make sense out of the details of their security claims, I *hope* that they need to re-read and revise the first few paragraphs of section 3.2. (Perhaps while they're at it they can replace the mentions of ‘ppt’ algorithms and attackers throughout their paper with a useful claim about execution time.) Robert Ransom
On 8/8/12, Nick Mathewson <nickm@freehaven.net> wrote:
Also, where does this paper specify that the participants must check that public-key group elements are not equal to the identity element? That's rather important, as Tor's relay protocol is likely to break if an attacker can force a server to open additional circuits to an attacker using the same key material that a legitimate client's circuit has. Robert Ransom
On 8/10/12, Robert Ransom <rransom.8774@gmail.com> wrote:
On 8/8/12, Nick Mathewson <nickm@freehaven.net> wrote:
Also, where does this paper specify that the participants must check that public-key group elements are not equal to the identity element? That's rather important, as Tor's relay protocol is likely to break if an attacker can force a server to open additional circuits to an attacker using the same key material that a legitimate client's circuit has.
It occurred to me later that the server would know that H(g^(x_1*b + x_2*y), g^y) is ‘fresh’, and that the client would know that the server would not use H(g^(x_1*b + x_2*y), g^(x_1), g^(x_2), g^y) as a key with a party that presented some public key other than (g^(x_1), g^(x_2)) to it, so I checked the paper for *that* defense against tampering and found it in Figure 4. (That is a critical detail of this protocol, and not necessary to protect honest clients against key reuse in ntor, so it should have been included in the specifications of the protocol in Figures 3 and 5 and the first two paragraphs of section 3.1. Hopefully the authors will fix that too when they revise their paper.) I don't see any way to attack ‘Ace’ with the client and server ephemeral public keys included in the data passed to the KDF. Robert Ransom
participants (3)
-
Nick Mathewson -
Robert Ransom -
Watson Ladd