Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

crypto/elliptic: incorrect operations on the P-224 curve #43786

Closed
rolandshoemaker opened this issue Jan 19, 2021 · 4 comments
Closed

crypto/elliptic: incorrect operations on the P-224 curve #43786

rolandshoemaker opened this issue Jan 19, 2021 · 4 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. release-blocker Security
Milestone

Comments

@rolandshoemaker
Copy link
Member

The P224() Curve implementation can in rare circumstances generate incorrect outputs, including returning invalid points from ScalarMult.

The crypto/x509 and golang.org/x/crypto/ocsp (but not crypto/tls) packages support P-224 ECDSA keys, but they are not supported by publicly trusted certificate authorities. No other standard library or golang.org/x/crypto package supports or uses the P-224 curve.

The incorrect output was found by the elliptic-curve-differential-fuzzer project running on OSS-Fuzz and reported by Philippe Antoine (Catena cyber).

This issue is CVE-2021-3114.

@JasonGross
Copy link

Would #40171 solve the issue? (I can point at the relevant Go code in fiat-crypto if that would help with integration/testing.)

@mdempsky
Copy link
Member

I think the issue is already fixed in today's security fix releases for Go 1.14 and Go 1.15; e.g., 5c8fd72. Presumably the same fix will be ported forward for Go 1.16.

Looking at the fix, it does seem like #40171 would have prevented it.

@dmitshur dmitshur added NeedsFix The path to resolution is known, but the work has not been done. release-blocker labels Jan 20, 2021
@gopherbot
Copy link

Change https://golang.org/cl/284779 mentions this issue: crypto/elliptic: fix P-224 field reduction

@gopherbot
Copy link

Change https://golang.org/cl/315271 mentions this issue: crypto/elliptic: import fiat-crypto P-521 field implementation

gopherbot pushed a commit that referenced this issue May 9, 2021
Fiat Cryptography (https://github.com/mit-plv/fiat-crypto) is a project
that produces prime order field implementations (the code that does
arithmetic modulo a prime number) based on a formally verified model.

The formal verification covers some of the most subtle and hard to test
parts of an elliptic curve implementation, like carry chains. It would
probably have prevented #20040 and #43786.

This CL imports a 64-bit implementation of the P-521 base field,
replacing the horribly slow and catastrophically variable time big.Int
CurveParams implementation.

The code in p521_fiat64.go is generated reproducibly by fiat-crypto,
building and running the Dockerfile according to the README.

The code in fiat/p521.go is a thin and idiomatic wrapper around the
fiat-crypto code. It includes an Invert method generated with the help
of github.com/mmcloughlin/addchain.

The code in elliptic/p521.go is a line-by-line port of the CurveParams
implementation. Lsh(x, N) was replaced with repeated Add(x, x) calls.
Mul(x, x) was replaced with Square(x). Mod calls were removed, as all
operations are modulo P. Likewise, Add calls to bring values back to
positive were removed. The ScalarMult ladder implementation is now
constant time, copied from p224ScalarMult. Only other notable changes
are adding a p512Point type to keep (x, y, z) together, and making
addJacobian and doubleJacobian methods on that type, with the usual
receiver semantics to save 4 allocations per step.

This amounts to a proof of concept, and is far from a mature elliptic
curve implementation. Here's a non-exhaustive list of things that need
improvement, most of which are pre-existing issues with crypto/elliptic.
Some of these can be fixed without API change, so can't.

- Marshal and Unmarshal still use the slow, variable time big.Int
  arithmetic. The Curve interface does not expose field operations, so
  we'll have to make our own abstraction.

- Point addition uses an incomplete Jacobian formula, which has variable
  time behaviors for points at infinity and equal points. There are
  better, complete formulae these days, but I wanted to keep this CL
  reviewable against the existing code.

- The scalar multiplication ladder is still heavily variable time. This
  is easy to fix and I'll do it in a follow-up CL, but I wanted to keep
  this one easier to review.

- Fundamentally, values have to go in and out of big.Int representation
  when they pass through the Curve interface, which is both slow and
  slightly variable-time.

- There is no scalar field implementation, so crypto/ecdsa ends up using
  big.Int for signing.

- Extending this to P-384 would involve either duplicating all P-521
  code, or coming up with some lower-level interfaces for the base
  field. Even better, generics, which would maybe let us save heap
  allocations due to virtual calls.

- The readability and idiomaticity of the autogenerated code can
  improve, although we have a clear abstraction and well-enforced
  contract, which makes it unlikely we'll have to resort to manually
  modifying the code. See mit-plv/fiat-crypto#949.

- We could also have a 32-bit implementation, since it's almost free to
  have fiat-crypto generate one.

Anyway, it's definitely better than CurveParams, and definitely faster.

name                   old time/op    new time/op    delta
pkg:crypto/elliptic goos:darwin goarch:arm64
ScalarBaseMult/P521-8    4.18ms ± 3%    0.86ms ± 2%  -79.50%  (p=0.000 n=10+9)
ScalarMult/P521-8        4.17ms ± 2%    0.85ms ± 6%  -79.68%  (p=0.000 n=10+10)
pkg:crypto/ecdsa goos:darwin goarch:arm64
Sign/P521-8              4.23ms ± 1%    0.94ms ± 0%  -77.70%  (p=0.000 n=9+8)
Verify/P521-8            8.31ms ± 2%    1.75ms ± 4%  -78.99%  (p=0.000 n=9+10)
GenerateKey/P521-8       4.15ms ± 2%    0.85ms ± 2%  -79.49%  (p=0.000 n=10+9)

name                   old alloc/op   new alloc/op   delta
pkg:crypto/elliptic goos:darwin goarch:arm64
ScalarBaseMult/P521-8    3.06MB ± 3%    0.00MB ± 0%  -99.97%  (p=0.000 n=10+10)
ScalarMult/P521-8        3.05MB ± 1%    0.00MB ± 0%  -99.97%  (p=0.000 n=9+10)
pkg:crypto/ecdsa goos:darwin goarch:arm64
Sign/P521-8              3.03MB ± 0%    0.01MB ± 0%  -99.74%  (p=0.000 n=10+8)
Verify/P521-8            6.06MB ± 1%    0.00MB ± 0%  -99.93%  (p=0.000 n=9+9)
GenerateKey/P521-8       3.02MB ± 0%    0.00MB ± 0%  -99.96%  (p=0.000 n=9+10)

name                   old allocs/op  new allocs/op  delta
pkg:crypto/elliptic goos:darwin goarch:arm64
ScalarBaseMult/P521-8     19.8k ± 3%      0.0k ± 0%  -99.95%  (p=0.000 n=10+10)
ScalarMult/P521-8         19.7k ± 1%      0.0k ± 0%  -99.95%  (p=0.000 n=9+10)
pkg:crypto/ecdsa goos:darwin goarch:arm64
Sign/P521-8               19.6k ± 0%      0.1k ± 0%  -99.63%  (p=0.000 n=10+10)
Verify/P521-8             39.2k ± 1%      0.1k ± 0%  -99.84%  (p=0.000 n=9+10)
GenerateKey/P521-8        19.5k ± 0%      0.0k ± 0%  -99.91%  (p=0.000 n=9+10)

Updates #40171

Change-Id: Ic898b09a2388382bf51ec007d9a79d72d44efe10
Reviewed-on: https://go-review.googlesource.com/c/go/+/315271
Run-TryBot: Filippo Valsorda <filippo@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Katie Hockman <katie@golang.org>
Trust: Katie Hockman <katie@golang.org>
Trust: Filippo Valsorda <filippo@golang.org>
@golang golang locked and limited conversation to collaborators May 1, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. release-blocker Security
Projects
None yet
Development

No branches or pull requests

5 participants