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

golang / go

The Go programming language

https://go.dev

BSD 3-Clause "New" or "Revised" License

122.67k stars 17.49k forks source link

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

Closed gopherbot closed 9 years ago

gopherbot commented 12 years ago

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 commented 12 years ago

Comment 1:

-> agl for triage

Owner changed to @agl.

Status changed to Accepted.

agl commented 12 years ago

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 commented 12 years ago

Comment 3:

Status changed to LongTerm.

rsc commented 12 years ago

Comment 4:

Labels changed: added priority-someday.

rsc commented 11 years ago

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 commented 11 years ago

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 commented 11 years ago

Comment 8:

Labels changed: added feature.

gopherbot commented 11 years ago

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 commented 11 years ago

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.