crypto/elliptic: not constant time and no validation in unmarshall

[gopherbot]

by watsonbladd:

Looking at the code for crypto/elliptic I see that there are several branches in
Jacobian addition. These branches leak state on most systems. In addition there is no
validation of points in the unmarshall function, and no documentation indicating that
validation is required.

Suggested fix: add to documentation that validation of all points sent and received is a
good idea and use addition laws without special cases.

[rsc]

Comment 1:

-> agl for triage

Owner changed to @agl.

Status changed to Accepted.

[agl]

Comment 2:

Absolutely, neither crypto/elliptic nor crypto/rsa is constant time (although the latter
uses blinding.)
Writing constant time implementations is a lot of work. I've written a constant time
P224 in C++, which could be ported:
http://src.chromium.org/viewvc/chrome/trunk/src/crypto/p224.cc?revision=108903&view=markup
(although it's simple rather than fast.)
The constant time P256 and P521 that I wrote are the OpenSSL implementations
(crypto/ec/ecp_nistp256.c). However, they're designed for 64-bit machines and use a
64-bit full-mult, which Go doesn't have native support for. (math/big uses asm to get at
it on platforms that support it.)

Labels changed: added priority-low, packagechange, removed priority-medium.

[rsc]

Comment 3:

Status changed to LongTerm.

[rsc]

Comment 4:

Labels changed: added priority-someday.

[rsc]

Comment 6:

FWIW, constant time P224 was in Go1.1 and constant time P256 will be in Go1.2.
No comment on the unmarshal bit but maybe you should create a separate issue for that.

[agl]

Comment 7:

I'll do a change this week to add a comment on Unmarshal that verification may be
needed. In the most common case it's not needed at all, and in some cases one needs to
verify subgroup membership (which is very expensive), so I don't think one size can fit
all.

Labels changed: added go1.2, removed priority-someday.

Status changed to Started.

[rsc]

Comment 8:

Labels changed: added feature.

[gopherbot]

Comment 9 by watsonbladd:

For the NIST curves subgroup membership verification is automatic with validating curve
membership. The lack of validation of curve membership, together with the fact that the
Jacobian addition formula and doubling formula do not depend on the curve, lead to an
easy attack on Diffie-Hellman implementations using them without validation, by picking
points on curve of smooth orders.

[agl]

Comment 10:

crypto/elliptic is not limited groups with a small cofactor w.r.t. subgroups. But, on
the other hand, all current uses of ECDH in the Go code are ephemeral so picking a
different curve isn't useful for an attacker.
So I can't prescribe a validation that's sufficient and minimal for everyone. At this
level of the code, some understanding is required.
Higher-level, friendly APIs are implemented in go.crypto/nacl/box.

[robpike]

Comment 11:

Labels changed: added go1.3maybe, removed go1.2.

[robpike]

Comment 12:

Labels changed: removed go1.3maybe.

[rsc]

Comment 13:

Labels changed: added go1.3maybe.

[rsc]

Comment 14:

Labels changed: removed feature.

[rsc]

Comment 15:

Labels changed: added release-none, removed go1.3maybe.

[rsc]

Comment 16:

Labels changed: added repo-main.

[coruus]

See https://go-review.googlesource.com/#/c/2421/

[gopherbot]

CL https://golang.org/cl/2421 mentions this issue.