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. Security justification: The goal of this protocol is to authenticate Ricky to Alice. We have 2 values that can be modified by an attacker: f and h. If the attacker modifies f, Ricky will compute a different key then Alice. Likewise, if the attacker modifies h then Alice will compute a different key then Ricky. His one option remaining is to make equal changes to both. But if Ricky and Alice reject bad values, then it is the same as if Alice and Ricky had picked different nonces, and the attacker still needs to solve the same problem. If k is reveled, then the attacker needs to break a Diffie-Hellman exchange, so forwards secrecy is preserved. We can also reduce DDH to this problem by letting k equal 1. I'll keep on working on this, and comments are welcome. Thanks, Watson Ladd
Attachment:
signature.asc
Description: OpenPGP digital signature