### Elliptic curves don't work either (08 Apr 2008)

(For context, see my previous post on OTCP)

In any Diffie-Hellman exchange based on elliptic curves, we have
*Q=aP* where *P* and *Q* are points on an elliptic curve. The
operation of multiplying a point and a scalar is well defined, but unimportant
here. The problem facing the attacker is, given *Q* and *P*, find
*a*. If they can do that, we're sunk.

If you could find a pair of numbers such that: *cP + dQ = eP + fQ* then
you're done because: *(c-e)P = (f-d)Q = (f-d)aP*, then *a =
(c-e)/(f-d) mod n*, where

*n*is the size of the field underlying the curve.

Finding such a point by picking random examples is never going to work
because of the storage requirements. However, if you define a step function
which takes a pair *(c, d)* and produces a new pair *(c', d')* you
have defined a cycle through the search space. (It must be a cycle because the
search space is finite. At some point you must hit a previous state and loop
forever.) Now you can use Floyd's cycle finding
algorithm to find a collision with constant space. This is an √n
algorithm for breaking this problem and is well known as Pollard's rho method.

Now, if you have many of these problems you get a big speed up by using some
storage. Assume that you do the legwork to solve an instance of the problem and
that you record some fraction of the points that you evaluated. (How you choose
the points isn't important so long as it's a function of the point; say pick
all points where the first *m* bits are zero.)

Now, future attempts to break the problem can collide with one of the
previous points. If you find *cP + dQ = eP + fR* (note that P is a
constant of the elliptic curve system) and also that *R = bP* (because we
solved this instance previously) then *cP + dQ = cP + adP = (e+fb)P* and
so *(c-(e+fb)) / d = a* (and we know all the values on the left-hand side).

Now, 2^{112} (14 bytes) is about as big an elliptic curve point as we can fit
in a TCP header. The maximum options payload is 40 bytes, of which 20 are
already taken up in modern TCP stacks. We need 2 bytes of fluff per option and,
unless we want this to be the last TCP header ever, we need to leave at least 4
bytes. That's where the 14 byte limit comes from.

We give the attacker 2^{50} bytes of space. I believe that
each point will take 3*14 bytes of space for the (c,d,Y) triple, where
*Y = cP+dQ*. Thus they can store 2^{44} distinguished points. Thus
one in 2^{56-44=12} points are distinguished. Additionally, generating those
2^{44} points isn't that hard, computationally. This suggests that an
attacker can find a collision in only 2^{12} iterations., or about
2^{13} field multiplications.

So, again, a reasonable attacker can break our crypto in real time.

This scheme becomes much harder to sell if we have to do evil things to the TCP header in order to make it work.