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

[Watson Ladd]

On Thu, Aug 9, 2012 at 2:10 PM, Robert Ransom <rransom.8774 at gmail.com> wrote:
> On 8/9/12, Watson Ladd <watsonbladd at gmail.com> wrote:
>> On Wed, Aug 8, 2012 at 8:22 PM, Robert Ransom <rransom.8774 at gmail.com>
>> wrote:
>>> 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.
>>
>> 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 at 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