Removing 1 modular exponentiation

Watson Ladd watsonbladd at
Tue Feb 20 04:28:46 UTC 2007

Mike Perry wrote:
> Thus spake Watson Ladd (watsonbladd at
>> James Muir wrote:
>>> You may already know that the current scheme has a security reduction
>>> (Goldberg, PET 2006), so I imagine there would have to be a comparable
>>> argument before the powers that be would consider a new scheme.
>>> Out of curiosity, what is it about your scheme that makes you say it is
>>> insecure?
>>> -James
>> Mike Perry had an MITM attack. It wasn't due to a problem with my proof
>> but a problem in that what I proved wasn't sufficient to insure
>> security. Basically Alice was performing DH with y the generator. So Eve
>> could easily perform an MITM attack. And Eve can connect to Ricky
>> easily. Still, a more efficient and still *secure* protocol would be a win.
> Ah, right. My proof should still apply because even though b/k is not
> an integer, it can still be written as b = r*k mod p. r is the
> exponent of g you get when you do (g^b)^(1/k) after finding (1/k) mod
> p using the Eucliean Algorithm as James pointed out. Right?
> It's all coming back to me now (maybe). ;)
Yes. But what makes your attack work is that Alice can't tell the
difference between a DH negotiation with generator y and a normal
protocol round. So Eve can perform a MITM attack by fooling Alice and
connecting to Ricky normally. I should have realized this would be an
issue, esp. as it was cited as such in the paper on MQV. If we could
modify MQV for our purposes it would be nice. Making Alice generate a
temporary MQV key would work *I think*. Someone with more
experience/time then me should look into it. Unfortunately, MQV is patented.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 249 bytes
Desc: OpenPGP digital signature
URL: <>

More information about the tor-talk mailing list