Re: Removing 1 modular exponentiation

[Mike Perry <mikepery@xxxxxxxxxx>]

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:

Round 2: Ricky picks positive integer b=rk. Let h=g^b = g^rk = y^r
Key calculation: Ricky computes the session key as s = f^r = y^ar = g^kar.
Alice computes the session key as s = h^a = g^ba = g^rka

All is well and good until Echelon Eve drops in for a spell. Having
recently upgraded her interception points to both evesdrop AND inject
traffic, Eve has her way with Ricky and Alice in the following racy
3-way secenario (hide the kids):


Alice and Eve:
R1: Alice picks her f=y^a
Alice sends to Ricky, intercepted by Eve.
R2: Eve picks a random number e. Let h_e=y^e. Sends to Alice
Key caluclation: Eve computes the session key as s=f^e=y^ae
Alice computes the key as h_e^a=y^ea


Eve and Ricky:
R1: Eve picks her f_e=y^v
Eve sends to Ricky.
R2: Ricky picks his random number r. let h=y^r=g^rk. Sends to "Alice" (Eve)
Key calculation: Ricky computes the session key as s=f_e^r=y^vr
Eve computes the session key as h^v=y^rv

Eve then happily relays traffic for Alice and Ricky. 


The fundamental problem is that all you've done is created a new (yet
equivalent) generator y for the exact same group G (since the group is
finite, cyclic and of prime order). Thus the same MITM authentication
problems with DH still exist, our demonic overlords win, begin reading 
your "improved" Tor traffic, and start executing whistleblowers
for exposing their satanic sex rings again. :(

Plus a few kittens probably die too.

-- 
Mike Perry
Mad Computer Scientist
fscked.org evil labs