[Cryptography] Why is ECC secure?

[Ray Dillinger]

On 08/16/2015 05:56 PM, Bill Cox wrote:

> In particular, we're leaning towards P256 as the default.  What do we know
> about this curve?  Should there be any concern that there may be a back
> door of any kind?  For example, what happens if the prime modulus minus 1
> has factors that are only known to the NSA?  What if they are purposely
> small?  Do we know enough about P256 to know this sort of thing is not the
> case?
> 
> Thanks,
> Bill
> 
Actually we specifically don't know that about P256.

http://safecurves.cr.yp.to/rigid.html raises a concern that the P256
curve may be manipulatable by an attacker. There is a large unexplained
input to the curve parameters, and it comes from NIST which has been
subverted by attackers before.


Also....

http://safecurves.cr.yp.to/complete.html raises a concern that the P256
curve has properties that make standard Weierstrass addition formulas
not work on this curve (fails doublings) and that there are identity
points (positive vs. negative values of identical absolute value) for
some parameters that produce the same results, which increases the
attack surface. (not by much if I'm reading it right, but it may be
one of the contributing factors to the next concern).

http://safecurves.cr.yp.to/ind.html raises a concern that the normal
method of making elliptic-curve strings indistinguishable from random
is not defined on NIST P256.  Distinguishability today leaves open an
increased probability of an attack tomorrow.

I highly recommend poking around safecurves.cr.yp.to a lot if you're
selecting elliptic curves for widespread use.  I think it's the most
comprehensive collection of specific information about the security
and efficiency properties of particular elliptic curves available.

They may (or may not) be overly concerned with relatively minor issues
that can be mitigated by careful coding.  But these "relatively minor"
issues do sometimes lead to later attacks. And even if the "lead" or
"killer" application driving adoption of the curve is carefully and
correctly coded, hundreds of people out there will be programming
things that are intended for compatibility with it, and some of them
won't be as careful or as capable.

					Bear





-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150817/c840bf25/attachment.sig>