[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: Removing 1 modular exponentiation

Mike Perry wrote: 
Thus spake Watson Ladd (watsonbladd@xxxxxxxxx):

Hello!
Tor currently uses RSA encrypted DH exchanges. This requires that the
server and client both make 3 exponentiations: Two for DH, One for RSA.
But we can reduce this significantly. I've already presented this
before, but now I think I can justify security. Sanity checks are assumed.

Cryptographic Personae: Anonymous Alice and Ricky the Onion Router.
Protocol Paramaters: A group with a "generator" g that takes on m
values. DDH is hard in the group. I put generator in quotes because a
lot of the time it's not a mathematical generator. The group is written
multiplicatively.
Setup: Ricky picks a random positive integer k less then m. Let y be
Ricky's public key. Then y=g^k.
Protocol round 1: Alice picks a random positive integer a. Let f=y^a.
Alice sends f to Ricky.
Protocol round 2: Ricky picks a random positive integer b. Let h=g^b.
Key calculation: Ricky computes the key as f^(b/k) where
(g^(k))^(1/k)=g. Alice computes the key as h^a. Note that both Ricky and
Alice perform 2 group exponentiations.


Well, one immediate problem is that b/k has to be an integer.. So b=rk
for some random r and b is thus not completely random.. To clarify the
effects of this, you should rewrite your protocol as follows from
Round 2 on:

that's not really a problem. all computations are done in the group ZZ_p. 1/k really means the inverse of k modulo the order of g in ZZ_p. So b/k does not have to be an integer.

putting the security of the scheme aside, one question that comes to mind is how Alice (the OP) is going to get an authentic copy of Ricky's DH public key, y. One way to do this is to include it in the router descriptors. But then we have to ask if it's worth adding a new public key for each OR to the Tor PKI to just save one exponentiation during session key agreement.

-James