From 8384fe86a5b7f579a50c7ad423d4dd4eb2d1f117 Mon Sep 17 00:00:00 2001 From: Filippo Valsorda Date: Sat, 30 Oct 2021 00:27:51 -0400 Subject: [PATCH] crypto/ecdsa,crypto/elliptic: update docs and spec references crypto/ecdsa was long overdue a cleanup. Bump the FIPS 186 version, and make sure we consistently reference that and SEC 1, not the paywalled ANSI standard. Change-Id: Idd90bd6c14b334941fdcd829d89b796a60a8b174 Reviewed-on: https://go-review.googlesource.com/c/go/+/352529 Run-TryBot: Filippo Valsorda Trust: Filippo Valsorda TryBot-Result: Gopher Robot Reviewed-by: Roland Shoemaker --- src/crypto/ecdsa/ecdsa.go | 95 +++++++++++++++++---------------- src/crypto/elliptic/elliptic.go | 40 +++++++------- src/crypto/elliptic/p256.go | 8 +-- 3 files changed, 75 insertions(+), 68 deletions(-) diff --git a/src/crypto/ecdsa/ecdsa.go b/src/crypto/ecdsa/ecdsa.go index 282596d2d2..9f9a09a884 100644 --- a/src/crypto/ecdsa/ecdsa.go +++ b/src/crypto/ecdsa/ecdsa.go @@ -3,28 +3,21 @@ // license that can be found in the LICENSE file. // Package ecdsa implements the Elliptic Curve Digital Signature Algorithm, as -// defined in FIPS 186-3. +// defined in FIPS 186-4 and SEC 1, Version 2.0. // -// This implementation derives the nonce from an AES-CTR CSPRNG keyed by: -// -// SHA2-512(priv.D || entropy || hash)[:32] -// -// The CSPRNG key is indifferentiable from a random oracle as shown in -// [Coron], the AES-CTR stream is indifferentiable from a random oracle -// under standard cryptographic assumptions (see [Larsson] for examples). -// -// References: -// [Coron] -// https://cs.nyu.edu/~dodis/ps/merkle.pdf -// [Larsson] -// https://web.archive.org/web/20040719170906/https://www.nada.kth.se/kurser/kth/2D1441/semteo03/lecturenotes/assump.pdf +// Signatures generated by this package are not deterministic, but entropy is +// mixed with the private key and the message, achieving the same level of +// security in case of randomness source failure. package ecdsa -// Further references: -// [NSA]: Suite B implementer's guide to FIPS 186-3 -// https://apps.nsa.gov/iaarchive/library/ia-guidance/ia-solutions-for-classified/algorithm-guidance/suite-b-implementers-guide-to-fips-186-3-ecdsa.cfm -// [SECG]: SECG, SEC1 -// http://www.secg.org/sec1-v2.pdf +// [FIPS 186-4] references ANSI X9.62-2005 for the bulk of the ECDSA algorithm. +// That standard is not freely available, which is a problem in an open source +// implementation, because not only the implementer, but also any maintainer, +// contributor, reviewer, auditor, and learner needs access to it. Instead, this +// package references and follows the equivalent [SEC 1, Version 2.0]. +// +// [FIPS 186-4]: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf +// [SEC 1, Version 2.0]: https://www.secg.org/sec1-v2.pdf import ( "crypto" @@ -41,15 +34,16 @@ import ( "golang.org/x/crypto/cryptobyte/asn1" ) -// A invertible implements fast inverse mod Curve.Params().N +// A invertible implements fast inverse in GF(N). type invertible interface { - // Inverse returns the inverse of k in GF(P) + // Inverse returns the inverse of k mod Params().N. Inverse(k *big.Int) *big.Int } -// combinedMult implements fast multiplication S1*g + S2*p (g - generator, p - arbitrary point) +// A combinedMult implements fast combined multiplication for verification. type combinedMult interface { - CombinedMult(bigX, bigY *big.Int, baseScalar, scalar []byte) (x, y *big.Int) + // CombinedMult returns [s1]G + [s2]P where G is the generator. + CombinedMult(Px, Py *big.Int, s1, s2 []byte) (x, y *big.Int) } const ( @@ -111,7 +105,7 @@ func (priv *PrivateKey) Equal(x crypto.PrivateKey) bool { // // This method implements crypto.Signer, which is an interface to support keys // where the private part is kept in, for example, a hardware module. Common -// uses should use the Sign function in this package directly. +// uses can use the SignASN1 function in this package directly. func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) { r, s, err := Sign(rand, priv, digest) if err != nil { @@ -128,11 +122,13 @@ func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOp var one = new(big.Int).SetInt64(1) -// randFieldElement returns a random element of the field underlying the given -// curve using the procedure given in [NSA] A.2.1. +// randFieldElement returns a random element of the order of the given +// curve using the procedure given in FIPS 186-4, Appendix B.5.1. func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) { params := c.Params() - b := make([]byte, params.BitSize/8+8) + // Note that for P-521 this will actually be 63 bits more than the order, as + // division rounds down, but the extra bit is inconsequential. + b := make([]byte, params.BitSize/8+8) // TODO: use params.N.BitLen() _, err = io.ReadFull(rand, b) if err != nil { return @@ -159,12 +155,9 @@ func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error) { return priv, nil } -// hashToInt converts a hash value to an integer. There is some disagreement -// about how this is done. [NSA] suggests that this is done in the obvious -// manner, but [SECG] truncates the hash to the bit-length of the curve order -// first. We follow [SECG] because that's what OpenSSL does. Additionally, -// OpenSSL right shifts excess bits from the number if the hash is too large -// and we mirror that too. +// hashToInt converts a hash value to an integer. Per FIPS 186-4, Section 6.4, +// we use the left-most bits of the hash to match the bit-length of the order of +// the curve. This also performs Step 5 of SEC 1, Version 2.0, Section 4.1.3. func hashToInt(hash []byte, c elliptic.Curve) *big.Int { orderBits := c.Params().N.BitLen() orderBytes := (orderBits + 7) / 8 @@ -180,10 +173,11 @@ func hashToInt(hash []byte, c elliptic.Curve) *big.Int { return ret } -// fermatInverse calculates the inverse of k in GF(P) using Fermat's method. -// This has better constant-time properties than Euclid's method (implemented -// in math/big.Int.ModInverse) although math/big itself isn't strictly -// constant-time so it's not perfect. +// fermatInverse calculates the inverse of k in GF(P) using Fermat's method +// (exponentiation modulo P - 2, per Euler's theorem). This has better +// constant-time properties than Euclid's method (implemented in +// math/big.Int.ModInverse and FIPS 186-4, Appendix C.1) although math/big +// itself isn't strictly constant-time so it's not perfect. func fermatInverse(k, N *big.Int) *big.Int { two := big.NewInt(2) nMinus2 := new(big.Int).Sub(N, two) @@ -195,11 +189,22 @@ var errZeroParam = errors.New("zero parameter") // Sign signs a hash (which should be the result of hashing a larger message) // using the private key, priv. If the hash is longer than the bit-length of the // private key's curve order, the hash will be truncated to that length. It -// returns the signature as a pair of integers. The security of the private key -// depends on the entropy of rand. +// returns the signature as a pair of integers. Most applications should use +// SignASN1 instead of dealing directly with r, s. func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) { randutil.MaybeReadByte(rand) + // This implementation derives the nonce from an AES-CTR CSPRNG keyed by: + // + // SHA2-512(priv.D || entropy || hash)[:32] + // + // The CSPRNG key is indifferentiable from a random oracle as shown in + // [Coron], the AES-CTR stream is indifferentiable from a random oracle + // under standard cryptographic assumptions (see [Larsson] for examples). + // + // [Coron]: https://cs.nyu.edu/~dodis/ps/merkle.pdf + // [Larsson]: https://web.archive.org/web/20040719170906/https://www.nada.kth.se/kurser/kth/2D1441/semteo03/lecturenotes/assump.pdf + // Get 256 bits of entropy from rand. entropy := make([]byte, 32) _, err = io.ReadFull(rand, entropy) @@ -207,7 +212,7 @@ func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err err return } - // Initialize an SHA-512 hash context; digest ... + // Initialize an SHA-512 hash context; digest... md := sha512.New() md.Write(priv.D.Bytes()) // the private key, md.Write(entropy) // the entropy, @@ -228,12 +233,12 @@ func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err err S: cipher.NewCTR(block, []byte(aesIV)), } - // See [NSA] 3.4.1 c := priv.PublicKey.Curve return sign(priv, &csprng, c, hash) } func signGeneric(priv *PrivateKey, csprng *cipher.StreamReader, c elliptic.Curve, hash []byte) (r, s *big.Int, err error) { + // SEC 1, Version 2.0, Section 4.1.3 N := c.Params().N if N.Sign() == 0 { return nil, nil, errZeroParam @@ -276,16 +281,15 @@ func signGeneric(priv *PrivateKey, csprng *cipher.StreamReader, c elliptic.Curve // SignASN1 signs a hash (which should be the result of hashing a larger message) // using the private key, priv. If the hash is longer than the bit-length of the // private key's curve order, the hash will be truncated to that length. It -// returns the ASN.1 encoded signature. The security of the private key -// depends on the entropy of rand. +// returns the ASN.1 encoded signature. func SignASN1(rand io.Reader, priv *PrivateKey, hash []byte) ([]byte, error) { return priv.Sign(rand, hash, nil) } // Verify verifies the signature in r, s of hash using the public key, pub. Its -// return value records whether the signature is valid. +// return value records whether the signature is valid. Most applications should +// use VerifyASN1 instead of dealing directly with r, s. func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool { - // See [NSA] 3.4.2 c := pub.Curve N := c.Params().N @@ -299,6 +303,7 @@ func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool { } func verifyGeneric(pub *PublicKey, c elliptic.Curve, hash []byte, r, s *big.Int) bool { + // SEC 1, Version 2.0, Section 4.1.4 e := hashToInt(hash, c) var w *big.Int N := c.Params().N diff --git a/src/crypto/elliptic/elliptic.go b/src/crypto/elliptic/elliptic.go index d06a284154..c5c5a906c4 100644 --- a/src/crypto/elliptic/elliptic.go +++ b/src/crypto/elliptic/elliptic.go @@ -2,17 +2,10 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -// Package elliptic implements several standard elliptic curves over prime -// fields. +// Package elliptic implements the standard NIST P-224, P-256, P-384, and P-521 +// elliptic curves over prime fields. package elliptic -// This package operates, internally, on Jacobian coordinates. For a given -// (x, y) position on the curve, the Jacobian coordinates are (x1, y1, z1) -// where x = x1/z1² and y = y1/z1³. The greatest speedups come when the whole -// calculation can be performed within the transform (as in ScalarMult and -// ScalarBaseMult). But even for Add and Double, it's faster to apply and -// reverse the transform than to operate in affine coordinates. - import ( "io" "math/big" @@ -21,12 +14,12 @@ import ( // A Curve represents a short-form Weierstrass curve with a=-3. // -// The output of Add, Double, and ScalarMult when the input is not a point on +// The behavior of Add, Double, and ScalarMult when the input is not a point on // the curve is undefined. // // Note that the conventional point at infinity (0, 0) is not considered on the // curve, although it can be returned by Add, Double, ScalarMult, or -// ScalarBaseMult (but not Unmarshal or UnmarshalCompressed). +// ScalarBaseMult (but not the Unmarshal or UnmarshalCompressed functions). type Curve interface { // Params returns the parameters for the curve. Params() *CurveParams @@ -67,6 +60,13 @@ func (curve *CurveParams) Params() *CurveParams { return curve } +// CurveParams operates, internally, on Jacobian coordinates. For a given +// (x, y) position on the curve, the Jacobian coordinates are (x1, y1, z1) +// where x = x1/z1² and y = y1/z1³. The greatest speedups come when the whole +// calculation can be performed within the transform (as in ScalarMult and +// ScalarBaseMult). But even for Add and Double, it's faster to apply and +// reverse the transform than to operate in affine coordinates. + // polynomial returns x³ - 3x + b. func (curve *CurveParams) polynomial(x *big.Int) *big.Int { x3 := new(big.Int).Mul(x, x) @@ -353,7 +353,8 @@ func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int, err e } // Marshal converts a point on the curve into the uncompressed form specified in -// section 4.3.6 of ANSI X9.62. +// SEC 1, Version 2.0, Section 2.3.3. If the point is not on the curve (or is +// the conventional point at infinity), the behavior is undefined. func Marshal(curve Curve, x, y *big.Int) []byte { byteLen := (curve.Params().BitSize + 7) / 8 @@ -367,7 +368,8 @@ func Marshal(curve Curve, x, y *big.Int) []byte { } // MarshalCompressed converts a point on the curve into the compressed form -// specified in section 4.3.6 of ANSI X9.62. +// specified in SEC 1, Version 2.0, Section 2.3.3. If the point is not on the +// curve (or is the conventional point at infinity), the behavior is undefined. func MarshalCompressed(curve Curve, x, y *big.Int) []byte { byteLen := (curve.Params().BitSize + 7) / 8 compressed := make([]byte, 1+byteLen) @@ -376,9 +378,9 @@ func MarshalCompressed(curve Curve, x, y *big.Int) []byte { return compressed } -// Unmarshal converts a point, serialized by Marshal, into an x, y pair. -// It is an error if the point is not in uncompressed form or is not on the curve. -// On error, x = nil. +// Unmarshal converts a point, serialized by Marshal, into an x, y pair. It is +// an error if the point is not in uncompressed form, is not on the curve, or is +// the point at infinity. On error, x = nil. func Unmarshal(curve Curve, data []byte) (x, y *big.Int) { byteLen := (curve.Params().BitSize + 7) / 8 if len(data) != 1+2*byteLen { @@ -399,9 +401,9 @@ func Unmarshal(curve Curve, data []byte) (x, y *big.Int) { return } -// UnmarshalCompressed converts a point, serialized by MarshalCompressed, into an x, y pair. -// It is an error if the point is not in compressed form or is not on the curve. -// On error, x = nil. +// UnmarshalCompressed converts a point, serialized by MarshalCompressed, into +// an x, y pair. It is an error if the point is not in compressed form, is not +// on the curve, or is the point at infinity. On error, x = nil. func UnmarshalCompressed(curve Curve, data []byte) (x, y *big.Int) { byteLen := (curve.Params().BitSize + 7) / 8 if len(data) != 1+byteLen { diff --git a/src/crypto/elliptic/p256.go b/src/crypto/elliptic/p256.go index 7ff7e33548..e1c6ff4f87 100644 --- a/src/crypto/elliptic/p256.go +++ b/src/crypto/elliptic/p256.go @@ -6,11 +6,11 @@ package elliptic -// This file contains a constant-time, 32-bit implementation of P256. +// P-256 is implemented by various different backends, including a generic +// 32-bit constant-time one in this file, which is used when assembly +// implementations are not available, or not appropriate for the hardware. -import ( - "math/big" -) +import "math/big" type p256Curve struct { *CurveParams -- 2.48.1