[Cryptography] Attacking Elliptic Curve Crypto on the infinity symbol

[Bill Cox]

Short version: cracking modern ECC, at least in this special case, is
equivalent to adding up arc-lengths on the infinity symbol.  However, the
math is hard, and no one has figured it out.  Do you want to have a try?
:-)

[image: Inline image 1]

Fear mongering disclaimer: Please _do_ continue to use ECC with confidence
(224 bits or more).  I see no reason to believe ECC DH is weaker than
regular DH (2048 bits or more), or the other way around.  I personally
consider the security of the ECDLP assumption to be on-par with the
security of the DLP assumption.  I doubt either will be cracked in my
lifetime.  I also doubt we'll see quantum computers capable of cracking
ECC-224.  Any "crypto expert" who thinks one is obviously easier to crack
than the other is not really a crypto expert, IMO.  Preferences for one or
the other are fine, but no one has a crystal ball that tells them which
problem will fall first.  If you are really paranoid, consider using _both_
so that your security relies on both problems being cracked at the same
time.  This suggestion is from DjB, where I read his recommendation for
using regular DH for long-term keys, and ECDH for ephemeral keys, bound to
the long-term keys.  Also, there is no pending "cryptopocalypse", and
quantum computing at this scale remains comfortably in the far distant
future.  Use either DH or ECC DH depending on the specific needs of your
application.  Don't fall victim to the fear mongering.

Now, back to attacking ECC, just for fun...

For the case of d == -1 on Edwards Curves
<https://en.wikipedia.org/wiki/Edwards_curve>, the "thing being added" when
we add points together in Elliptic Curve Crypto is arc-lengths on the
infinity symbol, called a Lemniscate
<http://mathworld.wolfram.com/Lemniscate.html>.  If we can compute the
following integral, mod p, we can break ECC in this case (-1 is not a
square mod p, or a different p would have been used), and likely gain
insight into how to crack the general ECC case:

    arcLength(x) = integrate 1/sqrt(1  - t^4) dt from 0 to x

Here, x is the x-coordinate of Alice's public key (x, y) which she computed
as m*g, where g is the "generator point" on the infinity symbol.  What we
mean by m*g is the point on the infinity symbol we reach when moving m
times the arc length from the center to g.  By choosing units for the arc
length of g to be 1, rather than using radians or degrees, the arc length
to Alice's point m*g is just m.

There is a problem: the point m*g on the infinity symbol wraps around many
times. There is a solution.  Simply find the point "h" in the group closest
to the origin (0, 0), and convert Alice's point m*g into m*h.  This is done
by multiplying Alice's point m*g by n, where h = n*g.  We find n at the
same time as finding h.  This turns out to be easy, so long as we know the
rational point on the curve used to generate g.  This is the case for my
prefered signature scheme Ed25519.  It is not the case for the curve we
actually use most of the time: ECDSA-P256.  The NSA decided not to tell us
the original rational X-coordinate that they used to compute their
generator point, which means we can't find h, and we can't solve the
wrapping-around problem.  I'm not saying this is strong evidence of a
back-door in ECDSA-P256, but it does make me go "hmmm..."

Other than for NSA designed ECC curves, it is common practice to publish
how the generator point was selected, which is usually to start with a
simple rational X-coordinate on the curve, which enables us to find h.
Using 'h' rather than 'g'.  m*h never wraps all the way around the
lemniscate, so arcLength(m*h) = m in units of arcLength(h).

All we have to do is compute that simple arc-length integral.  If we can do
that, we can reveal m.  However, no one knows how to do this, SFAIK.  We
don't even seem to have promising leads.  We do have strong evidence that
solving this integral is at least as hard as finding x given 2^x mod p.
However, if p is only 256 bits, we can trivially crack that in Python.  The
rest of ECC's security, at least for d == -1, relies on the assumption that
no one will figure out a solution to this very difficult problem, and the
somewhat more difficult ones where d != -1.  However, we have no proof that
it cannot be done, just as we have no proof that we can't solve regular DPL
in polynomial time.  Crypto is based on assumptions that problems are
hard.  We can't "prove" they are hard.  Instead, we get there by having
lot's of people try to solve it and fail.  Want to help out by taking a
crack at it?

Have fun,
Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151022/9dc5fd6a/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image.png
Type: image/png
Size: 5684 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151022/9dc5fd6a/attachment.png>