Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base

On Mon, Jan 5, 2015 at 3:07 PM, Andrey Jivsov <crypto@brainhub.org> wrote:
> Thank you, Mike, this is helpful. This brings a few thoughts, below.
<snip>
>
>
> Unfortunately, the conversion between representations costs ~10% due to F(p)
> inverse. Decompression costs about the same. We also know that the
> performance difference between Montgomery/Edwards operations is in the
> similar range. Therefore, selection of the format on the wire determines the
> implementation. If we are sending a Montgomery x, we are committing to
> Montgomery ladder implementation. Is this justified?

Yes. Despite claims earlier in your email that certification stops the
problem, invalid point attacks are a real threat. In RFC 4492,
ECDH_ECDSA authentication of servers to clients involves one signed
point and one unsigned point, the unsigned point being sent by the
client.  An attacker can extract the private key relatively quickly
from a vulnerable implementation, which do exist: I've found some, and
I believe Kenny Patterson has a student or two working on finding more
now, as well as attacking other protocols. RFC 6090 doesn't mention
the need for point validation, for instance.

Point compression doesn't solve this issue: there is a presentation by
Adrian Antipa, Dan Brown, Alfred Menezes, Rene Struik, and Scott
Vanstone at PKCS 2003 which demonstrates attacks even when point
compression is mandatory. DJB has also found a patent on point
validation, which may mean we have a problem. (This is why RFC 6090
doesn't mention point validation: the relevant patent is US7215773)

That's why NUMS switched to x-coordinate only Montgomery: the security
issues associated with invalid point attacks go away. The Montgomery
ladder is so simple that adding it to an Edwards form implementation
adds very little complexity. The architectural issues being claimed
are in my view irrelevant: most protocol implementations are able to
integrate RSA and ECC, which are radically different: an x-coordinate
only key exchange isn't much harder to integrate, and if it was,
people wouldn't be doing it.

The consequences of these attacks are losing one's private key, and
telling implementors to check inputs isn't stopping them.

Sincerely,
Watson Ladd

>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin