From 566cf1c1083b26d4a15b94213c21142ecd9a8ca9 Mon Sep 17 00:00:00 2001 From: Filippo Valsorda Date: Thu, 14 Nov 2024 22:02:02 +0100 Subject: [PATCH] crypto/ecdh: move implementation to crypto/internal/fips/ecdh This intentionally gives up on the property of not computing the public key until requested. It was nice, but it was making the code too complex. The average use case is to call PublicKey immediately after GenerateKey anyway. Added support in the module for P-224, just in case we'd ever want to support it in crypto/ecdh. Tried various ways to fix test/fixedbugs/issue52193.go to be meaningful, but crypto/ecdh is pretty complex and all the solutions would end up locking in crypto/ecdh structure rather than compiler behavior. The rest of that test is good enough on its own anyway. If we do the work in the future of making crypto/ecdh zero-allocations using the affordances of the compiler, we can add a more robust TestAllocations on our side. For #69536 Change-Id: I68ac3955180cb31f6f96a0ef57604aaed88ab311 Reviewed-on: https://go-review.googlesource.com/c/go/+/628315 Reviewed-by: Dmitri Shuralyov Reviewed-by: Daniel McCarney Reviewed-by: Russ Cox Auto-Submit: Filippo Valsorda LUCI-TryBot-Result: Go LUCI --- src/crypto/ecdh/ecdh.go | 35 +- src/crypto/ecdh/ecdh_test.go | 13 +- src/crypto/ecdh/nist.go | 255 +++++--------- src/crypto/ecdh/x25519.go | 34 +- src/crypto/internal/boring/ecdh.go | 8 +- src/crypto/internal/fips/ecdh/cast.go | 50 +++ src/crypto/internal/fips/ecdh/ecdh.go | 331 ++++++++++++++++++ src/crypto/internal/fips/ecdh/order_test.go | 26 ++ src/crypto/internal/fipsdeps/fipsdeps_test.go | 3 + src/crypto/internal/fipstest/cast_test.go | 9 +- src/go/build/deps_test.go | 10 +- test/fixedbugs/issue52193.go | 21 -- 12 files changed, 540 insertions(+), 255 deletions(-) create mode 100644 src/crypto/internal/fips/ecdh/cast.go create mode 100644 src/crypto/internal/fips/ecdh/ecdh.go create mode 100644 src/crypto/internal/fips/ecdh/order_test.go diff --git a/src/crypto/ecdh/ecdh.go b/src/crypto/ecdh/ecdh.go index b7c26f91e5..e6bfe7c15c 100644 --- a/src/crypto/ecdh/ecdh.go +++ b/src/crypto/ecdh/ecdh.go @@ -12,7 +12,6 @@ import ( "crypto/subtle" "errors" "io" - "sync" ) type Curve interface { @@ -50,14 +49,6 @@ type Curve interface { // The private method also allow us to expand the ECDH interface with more // methods in the future without breaking backwards compatibility. ecdh(local *PrivateKey, remote *PublicKey) ([]byte, error) - - // privateKeyToPublicKey converts a PrivateKey to a PublicKey. It's exposed - // as the PrivateKey.PublicKey method. - // - // This method always succeeds: for X25519, the zero key can't be - // constructed due to clamping; for NIST curves, it is rejected by - // NewPrivateKey. - privateKeyToPublicKey(*PrivateKey) *PublicKey } // PublicKey is an ECDH public key, usually a peer's ECDH share sent over the wire. @@ -107,11 +98,8 @@ func (k *PublicKey) Curve() Curve { type PrivateKey struct { curve Curve privateKey []byte + publicKey *PublicKey boring *boring.PrivateKeyECDH - // publicKey is set under publicKeyOnce, to allow loading private keys with - // NewPrivateKey without having to perform a scalar multiplication. - publicKey *PublicKey - publicKeyOnce sync.Once } // ECDH performs an ECDH exchange and returns the shared secret. The [PrivateKey] @@ -120,6 +108,8 @@ type PrivateKey struct { // For NIST curves, this performs ECDH as specified in SEC 1, Version 2.0, // Section 3.3.1, and returns the x-coordinate encoded according to SEC 1, // Version 2.0, Section 2.3.5. The result is never the point at infinity. +// This is also known as the Shared Secret Computation of the Ephemeral Unified +// Model scheme specified in NIST SP 800-56A Rev. 3, Section 6.1.2.2. // // For [X25519], this performs ECDH as specified in RFC 7748, Section 6.1. If // the result is the all-zero value, ECDH returns an error. @@ -159,25 +149,6 @@ func (k *PrivateKey) Curve() Curve { } func (k *PrivateKey) PublicKey() *PublicKey { - k.publicKeyOnce.Do(func() { - if k.boring != nil { - // Because we already checked in NewPrivateKey that the key is valid, - // there should not be any possible errors from BoringCrypto, - // so we turn the error into a panic. - // (We can't return it anyhow.) - kpub, err := k.boring.PublicKey() - if err != nil { - panic("boringcrypto: " + err.Error()) - } - k.publicKey = &PublicKey{ - curve: k.curve, - publicKey: kpub.Bytes(), - boring: kpub, - } - } else { - k.publicKey = k.curve.privateKeyToPublicKey(k) - } - }) return k.publicKey } diff --git a/src/crypto/ecdh/ecdh_test.go b/src/crypto/ecdh/ecdh_test.go index 49da4e8120..75d2480775 100644 --- a/src/crypto/ecdh/ecdh_test.go +++ b/src/crypto/ecdh/ecdh_test.go @@ -423,7 +423,8 @@ package main import "crypto/ecdh" import "crypto/rand" func main() { - curve := ecdh.P384() + // Use P-256, since that's what the always-enabled CAST uses. + curve := ecdh.P256() key, err := curve.GenerateKey(rand.Reader) if err != nil { panic(err) } _, err = curve.NewPublicKey(key.PublicKey().Bytes()) @@ -469,20 +470,20 @@ func TestLinker(t *testing.T) { } // List all text symbols under crypto/... and make sure there are some for - // P384, but none for the other curves. + // P256, but none for the other curves. var consistent bool nm := run(goBin, "tool", "nm", "hello.exe") for _, match := range regexp.MustCompile(`(?m)T (crypto/.*)$`).FindAllStringSubmatch(nm, -1) { symbol := strings.ToLower(match[1]) - if strings.Contains(symbol, "p384") { + if strings.Contains(symbol, "p256") { consistent = true } - if strings.Contains(symbol, "p224") || strings.Contains(symbol, "p256") || strings.Contains(symbol, "p521") { - t.Errorf("unexpected symbol in program using only ecdh.P384: %s", match[1]) + if strings.Contains(symbol, "p224") || strings.Contains(symbol, "p384") || strings.Contains(symbol, "p521") { + t.Errorf("unexpected symbol in program using only ecdh.P256: %s", match[1]) } } if !consistent { - t.Error("no P384 symbols found in program using ecdh.P384, test is broken") + t.Error("no P256 symbols found in program using ecdh.P256, test is broken") } } diff --git a/src/crypto/ecdh/nist.go b/src/crypto/ecdh/nist.go index 85b53b4c1a..0a80ca0063 100644 --- a/src/crypto/ecdh/nist.go +++ b/src/crypto/ecdh/nist.go @@ -5,190 +5,126 @@ package ecdh import ( + "bytes" "crypto/internal/boring" - "crypto/internal/fips/nistec" - "crypto/internal/randutil" + "crypto/internal/fips/ecdh" "errors" - "internal/byteorder" "io" - "math/bits" ) -type nistCurve[Point nistPoint[Point]] struct { - name string - newPoint func() Point - scalarOrder []byte +type nistCurve struct { + name string + generate func(io.Reader) (privateKey, publicKey []byte, err error) + importKey func([]byte) (publicKey []byte, err error) + checkPubkey func(publicKey []byte) error + sharedSecret func(privateKey, publicKey []byte) (sharedSecret []byte, err error) } -// nistPoint is a generic constraint for the nistec Point types. -type nistPoint[T any] interface { - Bytes() []byte - BytesX() ([]byte, error) - SetBytes([]byte) (T, error) - ScalarMult(T, []byte) (T, error) - ScalarBaseMult([]byte) (T, error) -} - -func (c *nistCurve[Point]) String() string { +func (c *nistCurve) String() string { return c.name } -var errInvalidPrivateKey = errors.New("crypto/ecdh: invalid private key") - -func (c *nistCurve[Point]) GenerateKey(rand io.Reader) (*PrivateKey, error) { +func (c *nistCurve) GenerateKey(rand io.Reader) (*PrivateKey, error) { if boring.Enabled && rand == boring.RandReader { key, bytes, err := boring.GenerateKeyECDH(c.name) if err != nil { return nil, err } - return newBoringPrivateKey(c, key, bytes) - } - - key := make([]byte, len(c.scalarOrder)) - randutil.MaybeReadByte(rand) - for { - if _, err := io.ReadFull(rand, key); err != nil { + pub, err := key.PublicKey() + if err != nil { return nil, err } - - // Mask off any excess bits if the size of the underlying field is not a - // whole number of bytes, which is only the case for P-521. We use a - // pointer to the scalarOrder field because comparing generic and - // instantiated types is not supported. - if &c.scalarOrder[0] == &p521Order[0] { - key[0] &= 0b0000_0001 - } - - // In tests, rand will return all zeros and NewPrivateKey will reject - // the zero key as it generates the identity as a public key. This also - // makes this function consistent with crypto/elliptic.GenerateKey. - key[1] ^= 0x42 - - k, err := c.NewPrivateKey(key) - if err == errInvalidPrivateKey { - continue + k := &PrivateKey{ + curve: c, + privateKey: bytes, + publicKey: &PublicKey{curve: c, publicKey: pub.Bytes(), boring: pub}, + boring: key, } - return k, err + return k, nil } -} -func (c *nistCurve[Point]) NewPrivateKey(key []byte) (*PrivateKey, error) { - if len(key) != len(c.scalarOrder) { - return nil, errors.New("crypto/ecdh: invalid private key size") + privateKey, publicKey, err := c.generate(rand) + if err != nil { + return nil, err } - if isZero(key) || !isLess(key, c.scalarOrder) { - return nil, errInvalidPrivateKey + + k := &PrivateKey{ + curve: c, + privateKey: privateKey, + publicKey: &PublicKey{curve: c, publicKey: publicKey}, } if boring.Enabled { - bk, err := boring.NewPrivateKeyECDH(c.name, key) + bk, err := boring.NewPrivateKeyECDH(c.name, k.privateKey) if err != nil { return nil, err } - return newBoringPrivateKey(c, bk, key) - } - k := &PrivateKey{ - curve: c, - privateKey: append([]byte{}, key...), + pub, err := bk.PublicKey() + if err != nil { + return nil, err + } + k.boring = bk + k.publicKey.boring = pub } return k, nil } -func newBoringPrivateKey(c Curve, bk *boring.PrivateKeyECDH, privateKey []byte) (*PrivateKey, error) { - k := &PrivateKey{ - curve: c, - boring: bk, - privateKey: append([]byte(nil), privateKey...), +func (c *nistCurve) NewPrivateKey(key []byte) (*PrivateKey, error) { + if boring.Enabled { + bk, err := boring.NewPrivateKeyECDH(c.name, key) + if err != nil { + return nil, errors.New("crypto/ecdh: invalid private key") + } + pub, err := bk.PublicKey() + if err != nil { + return nil, errors.New("crypto/ecdh: invalid private key") + } + k := &PrivateKey{ + curve: c, + privateKey: bytes.Clone(key), + publicKey: &PublicKey{curve: c, publicKey: pub.Bytes(), boring: pub}, + boring: bk, + } + return k, nil } - return k, nil -} -func (c *nistCurve[Point]) privateKeyToPublicKey(key *PrivateKey) *PublicKey { - boring.Unreachable() - if key.curve != c { - panic("crypto/ecdh: internal error: converting the wrong key type") - } - p, err := c.newPoint().ScalarBaseMult(key.privateKey) + publicKey, err := c.importKey(key) if err != nil { - // This is unreachable because the only error condition of - // ScalarBaseMult is if the input is not the right size. - panic("crypto/ecdh: internal error: nistec ScalarBaseMult failed for a fixed-size input") - } - publicKey := p.Bytes() - if len(publicKey) == 1 { - // The encoding of the identity is a single 0x00 byte. This is - // unreachable because the only scalar that generates the identity is - // zero, which is rejected by NewPrivateKey. - panic("crypto/ecdh: internal error: nistec ScalarBaseMult returned the identity") - } - return &PublicKey{ - curve: key.curve, - publicKey: publicKey, - } -} - -// isZero returns whether a is all zeroes in constant time. -func isZero(a []byte) bool { - var acc byte - for _, b := range a { - acc |= b - } - return acc == 0 -} - -// isLess returns whether a < b, where a and b are big-endian buffers of the -// same length and shorter than 72 bytes. -func isLess(a, b []byte) bool { - if len(a) != len(b) { - panic("crypto/ecdh: internal error: mismatched isLess inputs") - } - - // Copy the values into a fixed-size preallocated little-endian buffer. - // 72 bytes is enough for every scalar in this package, and having a fixed - // size lets us avoid heap allocations. - if len(a) > 72 { - panic("crypto/ecdh: internal error: isLess input too large") - } - bufA, bufB := make([]byte, 72), make([]byte, 72) - for i := range a { - bufA[i], bufB[i] = a[len(a)-i-1], b[len(b)-i-1] + return nil, err } - // Perform a subtraction with borrow. - var borrow uint64 - for i := 0; i < len(bufA); i += 8 { - limbA, limbB := byteorder.LeUint64(bufA[i:]), byteorder.LeUint64(bufB[i:]) - _, borrow = bits.Sub64(limbA, limbB, borrow) + k := &PrivateKey{ + curve: c, + privateKey: bytes.Clone(key), + publicKey: &PublicKey{curve: c, publicKey: publicKey}, } - - // If there is a borrow at the end of the operation, then a < b. - return borrow == 1 + return k, nil } -func (c *nistCurve[Point]) NewPublicKey(key []byte) (*PublicKey, error) { +func (c *nistCurve) NewPublicKey(key []byte) (*PublicKey, error) { // Reject the point at infinity and compressed encodings. + // Note that boring.NewPublicKeyECDH would accept them. if len(key) == 0 || key[0] != 4 { return nil, errors.New("crypto/ecdh: invalid public key") } k := &PublicKey{ curve: c, - publicKey: append([]byte{}, key...), + publicKey: bytes.Clone(key), } if boring.Enabled { bk, err := boring.NewPublicKeyECDH(c.name, k.publicKey) if err != nil { - return nil, err + return nil, errors.New("crypto/ecdh: invalid public key") } k.boring = bk } else { - // SetBytes also checks that the point is on the curve. - if _, err := c.newPoint().SetBytes(key); err != nil { + if err := c.checkPubkey(k.publicKey); err != nil { return nil, err } } return k, nil } -func (c *nistCurve[Point]) ecdh(local *PrivateKey, remote *PublicKey) ([]byte, error) { +func (c *nistCurve) ecdh(local *PrivateKey, remote *PublicKey) ([]byte, error) { // Note that this function can't return an error, as NewPublicKey rejects // invalid points and the point at infinity, and NewPrivateKey rejects // invalid scalars and the zero value. BytesX returns an error for the point @@ -199,16 +135,7 @@ func (c *nistCurve[Point]) ecdh(local *PrivateKey, remote *PublicKey) ([]byte, e if boring.Enabled { return boring.ECDH(local.boring, remote.boring) } - - boring.Unreachable() - p, err := c.newPoint().SetBytes(remote.publicKey) - if err != nil { - return nil, err - } - if _, err := p.ScalarMult(p, local.privateKey); err != nil { - return nil, err - } - return p.BytesX() + return c.sharedSecret(local.privateKey, remote.publicKey) } // P256 returns a [Curve] which implements NIST P-256 (FIPS 186-3, section D.2.3), @@ -218,18 +145,14 @@ func (c *nistCurve[Point]) ecdh(local *PrivateKey, remote *PublicKey) ([]byte, e // be used for equality checks and switch statements. func P256() Curve { return p256 } -var p256 = &nistCurve[*nistec.P256Point]{ - name: "P-256", - newPoint: nistec.NewP256Point, - scalarOrder: p256Order, +var p256 = &nistCurve{ + name: "P-256", + generate: ecdh.GenerateKeyP256, + importKey: ecdh.ImportKeyP256, + checkPubkey: ecdh.CheckPublicKeyP256, + sharedSecret: ecdh.ECDHP256, } -var p256Order = []byte{ - 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xbc, 0xe6, 0xfa, 0xad, 0xa7, 0x17, 0x9e, 0x84, - 0xf3, 0xb9, 0xca, 0xc2, 0xfc, 0x63, 0x25, 0x51} - // P384 returns a [Curve] which implements NIST P-384 (FIPS 186-3, section D.2.4), // also known as secp384r1. // @@ -237,20 +160,14 @@ var p256Order = []byte{ // be used for equality checks and switch statements. func P384() Curve { return p384 } -var p384 = &nistCurve[*nistec.P384Point]{ - name: "P-384", - newPoint: nistec.NewP384Point, - scalarOrder: p384Order, +var p384 = &nistCurve{ + name: "P-384", + generate: ecdh.GenerateKeyP384, + importKey: ecdh.ImportKeyP384, + checkPubkey: ecdh.CheckPublicKeyP384, + sharedSecret: ecdh.ECDHP384, } -var p384Order = []byte{ - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xc7, 0x63, 0x4d, 0x81, 0xf4, 0x37, 0x2d, 0xdf, - 0x58, 0x1a, 0x0d, 0xb2, 0x48, 0xb0, 0xa7, 0x7a, - 0xec, 0xec, 0x19, 0x6a, 0xcc, 0xc5, 0x29, 0x73} - // P521 returns a [Curve] which implements NIST P-521 (FIPS 186-3, section D.2.5), // also known as secp521r1. // @@ -258,18 +175,10 @@ var p384Order = []byte{ // be used for equality checks and switch statements. func P521() Curve { return p521 } -var p521 = &nistCurve[*nistec.P521Point]{ - name: "P-521", - newPoint: nistec.NewP521Point, - scalarOrder: p521Order, +var p521 = &nistCurve{ + name: "P-521", + generate: ecdh.GenerateKeyP521, + importKey: ecdh.ImportKeyP521, + checkPubkey: ecdh.CheckPublicKeyP521, + sharedSecret: ecdh.ECDHP521, } - -var p521Order = []byte{0x01, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, - 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfa, - 0x51, 0x86, 0x87, 0x83, 0xbf, 0x2f, 0x96, 0x6b, - 0x7f, 0xcc, 0x01, 0x48, 0xf7, 0x09, 0xa5, 0xd0, - 0x3b, 0xb5, 0xc9, 0xb8, 0x89, 0x9c, 0x47, 0xae, - 0xbb, 0x6f, 0xb7, 0x1e, 0x91, 0x38, 0x64, 0x09} diff --git a/src/crypto/ecdh/x25519.go b/src/crypto/ecdh/x25519.go index 998e7588a6..5147b7e5e0 100644 --- a/src/crypto/ecdh/x25519.go +++ b/src/crypto/ecdh/x25519.go @@ -5,6 +5,7 @@ package ecdh import ( + "bytes" "crypto/internal/edwards25519/field" "crypto/internal/randutil" "errors" @@ -45,32 +46,26 @@ func (c *x25519Curve) NewPrivateKey(key []byte) (*PrivateKey, error) { if len(key) != x25519PrivateKeySize { return nil, errors.New("crypto/ecdh: invalid private key size") } + publicKey := make([]byte, x25519PublicKeySize) + x25519Basepoint := [32]byte{9} + x25519ScalarMult(publicKey, key, x25519Basepoint[:]) + // We don't check for the all-zero public key here because the scalar is + // never zero because of clamping, and the basepoint is not the identity in + // the prime-order subgroup(s). return &PrivateKey{ curve: c, - privateKey: append([]byte{}, key...), + privateKey: bytes.Clone(key), + publicKey: &PublicKey{curve: c, publicKey: publicKey}, }, nil } -func (c *x25519Curve) privateKeyToPublicKey(key *PrivateKey) *PublicKey { - if key.curve != c { - panic("crypto/ecdh: internal error: converting the wrong key type") - } - k := &PublicKey{ - curve: key.curve, - publicKey: make([]byte, x25519PublicKeySize), - } - x25519Basepoint := [32]byte{9} - x25519ScalarMult(k.publicKey, key.privateKey, x25519Basepoint[:]) - return k -} - func (c *x25519Curve) NewPublicKey(key []byte) (*PublicKey, error) { if len(key) != x25519PublicKeySize { return nil, errors.New("crypto/ecdh: invalid public key") } return &PublicKey{ curve: c, - publicKey: append([]byte{}, key...), + publicKey: bytes.Clone(key), }, nil } @@ -134,3 +129,12 @@ func x25519ScalarMult(dst, scalar, point []byte) { x2.Multiply(&x2, &z2) copy(dst[:], x2.Bytes()) } + +// isZero reports whether x is all zeroes in constant time. +func isZero(x []byte) bool { + var acc byte + for _, b := range x { + acc |= b + } + return acc == 0 +} diff --git a/src/crypto/internal/boring/ecdh.go b/src/crypto/internal/boring/ecdh.go index 6a5d174c16..b90e533e7c 100644 --- a/src/crypto/internal/boring/ecdh.go +++ b/src/crypto/internal/boring/ecdh.go @@ -35,8 +35,8 @@ func (k *PrivateKeyECDH) finalize() { } func NewPublicKeyECDH(curve string, bytes []byte) (*PublicKeyECDH, error) { - if len(bytes) < 1 { - return nil, errors.New("NewPublicKeyECDH: missing key") + if len(bytes) != 1+2*curveSize(curve) { + return nil, errors.New("NewPublicKeyECDH: wrong key length") } nid, err := curveNID(curve) @@ -71,6 +71,10 @@ func NewPublicKeyECDH(curve string, bytes []byte) (*PublicKeyECDH, error) { func (k *PublicKeyECDH) Bytes() []byte { return k.bytes } func NewPrivateKeyECDH(curve string, bytes []byte) (*PrivateKeyECDH, error) { + if len(bytes) != curveSize(curve) { + return nil, errors.New("NewPrivateKeyECDH: wrong key length") + } + nid, err := curveNID(curve) if err != nil { return nil, err diff --git a/src/crypto/internal/fips/ecdh/cast.go b/src/crypto/internal/fips/ecdh/cast.go new file mode 100644 index 0000000000..766ca9cad7 --- /dev/null +++ b/src/crypto/internal/fips/ecdh/cast.go @@ -0,0 +1,50 @@ +// Copyright 2024 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package ecdh + +import ( + "bytes" + "crypto/internal/fips" + "crypto/internal/fips/nistec" + "errors" + "sync" +) + +var fipsSelfTest = sync.OnceFunc(func() { + // Per IG D.F, Scenario 2, path (1). + fips.CAST("KAS-ECC-SSC P-256", func() error { + privateKey := []byte{ + 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, + 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, + 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, + 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, + } + publicKey := []byte{ + 0x04, + 0x51, 0x5c, 0x3d, 0x6e, 0xb9, 0xe3, 0x96, 0xb9, + 0x04, 0xd3, 0xfe, 0xca, 0x7f, 0x54, 0xfd, 0xcd, + 0x0c, 0xc1, 0xe9, 0x97, 0xbf, 0x37, 0x5d, 0xca, + 0x51, 0x5a, 0xd0, 0xa6, 0xc3, 0xb4, 0x03, 0x5f, + 0x45, 0x36, 0xbe, 0x3a, 0x50, 0xf3, 0x18, 0xfb, + 0xf9, 0xa5, 0x47, 0x59, 0x02, 0xa2, 0x21, 0x50, + 0x2b, 0xef, 0x0d, 0x57, 0xe0, 0x8c, 0x53, 0xb2, + 0xcc, 0x0a, 0x56, 0xf1, 0x7d, 0x9f, 0x93, 0x54, + } + want := []byte{ + 0xb4, 0xf1, 0xfc, 0xce, 0x40, 0x73, 0x5f, 0x83, + 0x6a, 0xf8, 0xd6, 0x31, 0x2d, 0x24, 0x8d, 0x1a, + 0x83, 0x48, 0x40, 0x56, 0x69, 0xa1, 0x95, 0xfa, + 0xc5, 0x35, 0x04, 0x06, 0xba, 0x76, 0xbc, 0xce, + } + got, err := ecdh(privateKey, publicKey, nistec.NewP256Point) + if err != nil { + return err + } + if !bytes.Equal(got, want) { + return errors.New("unexpected result") + } + return nil + }) +}) diff --git a/src/crypto/internal/fips/ecdh/ecdh.go b/src/crypto/internal/fips/ecdh/ecdh.go new file mode 100644 index 0000000000..66edc8d1f8 --- /dev/null +++ b/src/crypto/internal/fips/ecdh/ecdh.go @@ -0,0 +1,331 @@ +// Copyright 2024 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package ecdh + +import ( + "bytes" + "crypto/internal/fips" + "crypto/internal/fips/drbg" + "crypto/internal/fips/nistec" + "crypto/internal/fipsdeps/byteorder" + "crypto/internal/randutil" + "errors" + "io" + "math/bits" +) + +// point is a generic constraint for the [nistec] point types. +type point[T any] interface { + *nistec.P224Point | *nistec.P256Point | *nistec.P384Point | *nistec.P521Point + Bytes() []byte + BytesX() ([]byte, error) + SetBytes([]byte) (T, error) + ScalarMult(T, []byte) (T, error) + ScalarBaseMult([]byte) (T, error) +} + +// GenerateKeyP224 generates a random P-224 private key for ECDH. +// +// If FIPS mode is disabled, privateKey is generated from rand. If FIPS mode is +// enabled, rand is ignored and the key pair is generated using the approved +// DRBG (and the function runs considerably slower). +func GenerateKeyP224(rand io.Reader) (privateKey, publicKey []byte, err error) { + fipsSelfTest() + fips.RecordApproved() + return generateKey(rand, nistec.NewP224Point, p224Order) +} + +// GenerateKeyP256 generates a random P-256 private key for ECDH. +// +// If FIPS mode is disabled, privateKey is generated from rand. If FIPS mode is +// enabled, rand is ignored and the key pair is generated using the approved +// DRBG (and the function runs considerably slower). +func GenerateKeyP256(rand io.Reader) (privateKey, publicKey []byte, err error) { + fipsSelfTest() + fips.RecordApproved() + return generateKey(rand, nistec.NewP256Point, p256Order) +} + +// GenerateKeyP384 generates a random P-384 private key for ECDH. +// +// If FIPS mode is disabled, privateKey is generated from rand. If FIPS mode is +// enabled, rand is ignored and the key pair is generated using the approved +// DRBG (and the function runs considerably slower). +func GenerateKeyP384(rand io.Reader) (privateKey, publicKey []byte, err error) { + fipsSelfTest() + fips.RecordApproved() + return generateKey(rand, nistec.NewP384Point, p384Order) +} + +// GenerateKeyP521 generates a random P-521 private key for ECDH. +// +// If FIPS mode is disabled, privateKey is generated from rand. If FIPS mode is +// enabled, rand is ignored and the key pair is generated using the approved +// DRBG (and the function runs considerably slower). +func GenerateKeyP521(rand io.Reader) (privateKey, publicKey []byte, err error) { + fipsSelfTest() + fips.RecordApproved() + return generateKey(rand, nistec.NewP521Point, p521Order) +} + +func generateKey[P point[P]](rand io.Reader, newPoint func() P, scalarOrder []byte) (privateKey, publicKey []byte, err error) { + // This procedure is equivalent to Key Pair Generation by Testing + // Candidates, specified in NIST SP 800-56A Rev. 3, Section 5.6.1.2.2. + + for { + key := make([]byte, len(scalarOrder)) + if fips.Enabled { + drbg.Read(key) + } else { + randutil.MaybeReadByte(rand) + if _, err := io.ReadFull(rand, key); err != nil { + return nil, nil, err + } + // In tests, rand will return all zeros and NewPrivateKey will reject + // the zero key as it generates the identity as a public key. This also + // makes this function consistent with crypto/elliptic.GenerateKey. + key[1] ^= 0x42 + } + + // Mask off any excess bits if the size of the underlying field is not a + // whole number of bytes, which is only the case for P-521. + if len(scalarOrder) == len(p521Order) && scalarOrder[0]&0b1111_1110 == 0 { + key[0] &= 0b0000_0001 + } + + publicKey, err := checkKeyAndComputePublicKey(key, newPoint, scalarOrder) + if err != nil { + continue + } + + return key, publicKey, nil + } +} + +func ImportKeyP224(privateKey []byte) (publicKey []byte, err error) { + fips.RecordNonApproved() + return checkKeyAndComputePublicKey(privateKey, nistec.NewP224Point, p224Order) +} + +func ImportKeyP256(privateKey []byte) (publicKey []byte, err error) { + fips.RecordNonApproved() + return checkKeyAndComputePublicKey(privateKey, nistec.NewP256Point, p256Order) +} + +func ImportKeyP384(privateKey []byte) (publicKey []byte, err error) { + fips.RecordNonApproved() + return checkKeyAndComputePublicKey(privateKey, nistec.NewP384Point, p384Order) +} + +func ImportKeyP521(privateKey []byte) (publicKey []byte, err error) { + fips.RecordNonApproved() + return checkKeyAndComputePublicKey(privateKey, nistec.NewP521Point, p521Order) +} + +func checkKeyAndComputePublicKey[P point[P]](key []byte, newPoint func() P, scalarOrder []byte) (publicKey []byte, err error) { + // SP 800-56A Rev. 3, Section 5.6.1.2.2 checks that c <= n – 2 and then + // returns d = c + 1. Note that it follows that 0 < d < n. Equivalently, + // we check that 0 < d < n, and return d. + if len(key) != len(scalarOrder) || isZero(key) || !isLess(key, scalarOrder) { + return nil, errors.New("crypto/ecdh: invalid private key") + } + + p, err := newPoint().ScalarBaseMult(key) + if err != nil { + // This is unreachable because the only error condition of + // ScalarBaseMult is if the input is not the right size. + panic("crypto/ecdh: internal error: nistec ScalarBaseMult failed for a fixed-size input") + } + + publicKey = p.Bytes() + if len(publicKey) == 1 { + // The encoding of the identity is a single 0x00 byte. This is + // unreachable because the only scalar that generates the identity is + // zero, which is rejected above. + panic("crypto/ecdh: internal error: public key is the identity element") + } + + // A "Pairwise Consistency Test" makes no sense if we just generated the + // public key from an ephemeral private key. Moreover, there is no way to + // check it aside from redoing the exact same computation again. SP 800-56A + // Rev. 3, Section 5.6.2.1.4 acknowledges that, and doesn't require it. + // However, ISO 19790:2012, Section 7.10.3.3 has a blanket requirement for a + // PCT for all generated keys (AS10.35) and FIPS 140-3 IG 10.3.A, Additional + // Comment 1 goes out of its way to say that "the PCT shall be performed + // consistent [...], even if the underlying standard does not require a + // PCT". So we do it. And make ECDH nearly 50% slower (only) in FIPS mode. + fips.CAST("ECDH PCT", func() error { + p1, err := newPoint().ScalarBaseMult(key) + if err != nil { + return err + } + if !bytes.Equal(p1.Bytes(), publicKey) { + return errors.New("crypto/ecdh: public key does not match private key") + } + return nil + }) + + return publicKey, nil +} + +func CheckPublicKeyP224(publicKey []byte) error { + fipsSelfTest() + fips.RecordApproved() + return checkPublicKey(publicKey, nistec.NewP224Point) +} + +func CheckPublicKeyP256(publicKey []byte) error { + fipsSelfTest() + fips.RecordApproved() + return checkPublicKey(publicKey, nistec.NewP256Point) +} + +func CheckPublicKeyP384(publicKey []byte) error { + fipsSelfTest() + fips.RecordApproved() + return checkPublicKey(publicKey, nistec.NewP384Point) +} + +func CheckPublicKeyP521(publicKey []byte) error { + fipsSelfTest() + fips.RecordApproved() + return checkPublicKey(publicKey, nistec.NewP521Point) +} + +func checkPublicKey[P point[P]](key []byte, newPoint func() P) error { + // Reject the point at infinity and compressed encodings. + if len(key) == 0 || key[0] != 4 { + return errors.New("crypto/ecdh: invalid public key") + } + + // SetBytes checks that x and y are in the interval [0, p - 1], and that + // the point is on the curve. Along with the rejection of the point at + // infinity (the identity element) above, this fulfills the requirements + // of NIST SP 800-56A Rev. 3, Section 5.6.2.3.4. + if _, err := newPoint().SetBytes(key); err != nil { + return err + } + + return nil +} + +func ECDHP224(privateKey, publicKey []byte) ([]byte, error) { + fipsSelfTest() + fips.RecordApproved() + return ecdh(privateKey, publicKey, nistec.NewP224Point) +} + +func ECDHP256(privateKey, publicKey []byte) ([]byte, error) { + fipsSelfTest() + fips.RecordApproved() + return ecdh(privateKey, publicKey, nistec.NewP256Point) +} + +func ECDHP384(privateKey, publicKey []byte) ([]byte, error) { + fipsSelfTest() + fips.RecordApproved() + return ecdh(privateKey, publicKey, nistec.NewP384Point) +} + +func ECDHP521(privateKey, publicKey []byte) ([]byte, error) { + fipsSelfTest() + fips.RecordApproved() + return ecdh(privateKey, publicKey, nistec.NewP521Point) +} + +func ecdh[P point[P]](privateKey, publicKey []byte, newPoint func() P) ([]byte, error) { + // This applies the Shared Secret Computation of the Ephemeral Unified Model + // scheme specified in NIST SP 800-56A Rev. 3, Section 6.1.2.2. + + // Per Section 5.6.2.3.4, Step 1, reject the identity element (0x00). + if len(publicKey) == 1 { + return nil, errors.New("crypto/ecdh: public key is the identity element") + } + + // SetBytes checks that (x, y) are reduced modulo p, and that they are on + // the curve, performing Steps 2-3 of Section 5.6.2.3.4. + p, err := newPoint().SetBytes(publicKey) + if err != nil { + return nil, err + } + + // Compute P according to Section 5.7.1.2. + if _, err := p.ScalarMult(p, privateKey); err != nil { + return nil, err + } + + // BytesX checks that the result is not the identity element, and returns the + // x-coordinate of the result, performing Steps 2-5 of Section 5.7.1.2. + return p.BytesX() +} + +// isZero reports whether x is all zeroes in constant time. +func isZero(x []byte) bool { + var acc byte + for _, b := range x { + acc |= b + } + return acc == 0 +} + +// isLess reports whether a < b, where a and b are big-endian buffers of the +// same length and shorter than 72 bytes. +func isLess(a, b []byte) bool { + if len(a) != len(b) { + panic("crypto/ecdh: internal error: mismatched isLess inputs") + } + + // Copy the values into a fixed-size preallocated little-endian buffer. + // 72 bytes is enough for every scalar in this package, and having a fixed + // size lets us avoid heap allocations. + if len(a) > 72 { + panic("crypto/ecdh: internal error: isLess input too large") + } + bufA, bufB := make([]byte, 72), make([]byte, 72) + for i := range a { + bufA[i], bufB[i] = a[len(a)-i-1], b[len(b)-i-1] + } + + // Perform a subtraction with borrow. + var borrow uint64 + for i := 0; i < len(bufA); i += 8 { + limbA, limbB := byteorder.LEUint64(bufA[i:]), byteorder.LEUint64(bufB[i:]) + _, borrow = bits.Sub64(limbA, limbB, borrow) + } + + // If there is a borrow at the end of the operation, then a < b. + return borrow == 1 +} + +var p224Order = []byte{ + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x16, 0xa2, + 0xe0, 0xb8, 0xf0, 0x3e, 0x13, 0xdd, 0x29, 0x45, + 0x5c, 0x5c, 0x2a, 0x3d, +} + +var p256Order = []byte{ + 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xbc, 0xe6, 0xfa, 0xad, 0xa7, 0x17, 0x9e, 0x84, + 0xf3, 0xb9, 0xca, 0xc2, 0xfc, 0x63, 0x25, 0x51} + +var p384Order = []byte{ + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xc7, 0x63, 0x4d, 0x81, 0xf4, 0x37, 0x2d, 0xdf, + 0x58, 0x1a, 0x0d, 0xb2, 0x48, 0xb0, 0xa7, 0x7a, + 0xec, 0xec, 0x19, 0x6a, 0xcc, 0xc5, 0x29, 0x73} + +var p521Order = []byte{0x01, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfa, + 0x51, 0x86, 0x87, 0x83, 0xbf, 0x2f, 0x96, 0x6b, + 0x7f, 0xcc, 0x01, 0x48, 0xf7, 0x09, 0xa5, 0xd0, + 0x3b, 0xb5, 0xc9, 0xb8, 0x89, 0x9c, 0x47, 0xae, + 0xbb, 0x6f, 0xb7, 0x1e, 0x91, 0x38, 0x64, 0x09} diff --git a/src/crypto/internal/fips/ecdh/order_test.go b/src/crypto/internal/fips/ecdh/order_test.go new file mode 100644 index 0000000000..772c42c813 --- /dev/null +++ b/src/crypto/internal/fips/ecdh/order_test.go @@ -0,0 +1,26 @@ +// Copyright 2024 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package ecdh + +import ( + "bytes" + "crypto/elliptic" + "testing" +) + +func TestOrders(t *testing.T) { + if !bytes.Equal(elliptic.P224().Params().N.Bytes(), p224Order) { + t.Errorf("P-224 order mismatch") + } + if !bytes.Equal(elliptic.P256().Params().N.Bytes(), p256Order) { + t.Errorf("P-256 order mismatch") + } + if !bytes.Equal(elliptic.P384().Params().N.Bytes(), p384Order) { + t.Errorf("P-384 order mismatch") + } + if !bytes.Equal(elliptic.P521().Params().N.Bytes(), p521Order) { + t.Errorf("P-521 order mismatch") + } +} diff --git a/src/crypto/internal/fipsdeps/fipsdeps_test.go b/src/crypto/internal/fipsdeps/fipsdeps_test.go index 69c804ca5d..1d5ec25a12 100644 --- a/src/crypto/internal/fipsdeps/fipsdeps_test.go +++ b/src/crypto/internal/fipsdeps/fipsdeps_test.go @@ -24,6 +24,9 @@ var AllowedInternalPackages = map[string]bool{ // impl.Register is how the packages expose their alternative // implementations to tests outside the module. "crypto/internal/impl": true, + + // randutil.MaybeReadByte is used in non-FIPS mode by GenerateKey functions. + "crypto/internal/randutil": true, } func TestImports(t *testing.T) { diff --git a/src/crypto/internal/fipstest/cast_test.go b/src/crypto/internal/fipstest/cast_test.go index 9d6483b371..f6620945f4 100644 --- a/src/crypto/internal/fipstest/cast_test.go +++ b/src/crypto/internal/fipstest/cast_test.go @@ -17,6 +17,7 @@ import ( _ "crypto/internal/fips/aes" _ "crypto/internal/fips/aes/gcm" _ "crypto/internal/fips/drbg" + "crypto/internal/fips/ecdh" _ "crypto/internal/fips/hkdf" _ "crypto/internal/fips/hmac" "crypto/internal/fips/mlkem" @@ -25,6 +26,7 @@ import ( _ "crypto/internal/fips/sha512" _ "crypto/internal/fips/tls12" _ "crypto/internal/fips/tls13" + "crypto/rand" ) func findAllCASTs(t *testing.T) map[string]struct{} { @@ -65,9 +67,10 @@ func findAllCASTs(t *testing.T) map[string]struct{} { return allCASTs } -// TestPCTs causes the conditional PCTs to be invoked. -func TestPCTs(t *testing.T) { +// TestConditionals causes the conditional CASTs and PCTs to be invoked. +func TestConditionals(t *testing.T) { mlkem.GenerateKey768() + ecdh.GenerateKeyP256(rand.Reader) t.Log("completed successfully") } @@ -82,7 +85,7 @@ func TestCASTFailures(t *testing.T) { for name := range allCASTs { t.Run(name, func(t *testing.T) { t.Parallel() - cmd := testenv.Command(t, testenv.Executable(t), "-test.run=TestPCTs", "-test.v") + cmd := testenv.Command(t, testenv.Executable(t), "-test.run=TestConditionals", "-test.v") cmd = testenv.CleanCmdEnv(cmd) cmd.Env = append(cmd.Env, fmt.Sprintf("GODEBUG=failfipscast=%s,fips140=on", name)) out, err := cmd.CombinedOutput() diff --git a/src/go/build/deps_test.go b/src/go/build/deps_test.go index 5aac83f95b..b762fd79e1 100644 --- a/src/go/build/deps_test.go +++ b/src/go/build/deps_test.go @@ -440,6 +440,8 @@ var depsRules = ` NET, log < net/mail; + io, math/rand/v2 < crypto/internal/randutil; + STR < crypto/internal/impl; OS < crypto/internal/sysrand @@ -451,7 +453,9 @@ var depsRules = ` # FIPS is the FIPS 140 module. # It must not depend on external crypto packages. - STR, crypto/internal/impl, crypto/internal/entropy, + STR, crypto/internal/impl, + crypto/internal/entropy, + crypto/internal/randutil, crypto/internal/fipsdeps/byteorder, crypto/internal/fipsdeps/cpu, crypto/internal/fipsdeps/godebug @@ -473,6 +477,7 @@ var depsRules = ` < crypto/internal/fips/tls13 < crypto/internal/fips/nistec/fiat < crypto/internal/fips/nistec + < crypto/internal/fips/ecdh < FIPS; FIPS < crypto/internal/fips/check/checktest; @@ -496,9 +501,8 @@ var depsRules = ` < crypto/internal/boring < crypto/boring; - crypto/internal/fips/alias, math/rand/v2, + crypto/internal/fips/alias, crypto/subtle, embed - < crypto/internal/randutil < crypto/internal/edwards25519/field < crypto/internal/edwards25519; diff --git a/test/fixedbugs/issue52193.go b/test/fixedbugs/issue52193.go index 32375d114f..1c42210f08 100644 --- a/test/fixedbugs/issue52193.go +++ b/test/fixedbugs/issue52193.go @@ -6,27 +6,6 @@ package p -import ( - "crypto/ecdh" - "crypto/rand" -) - -func F(peerShare []byte) ([]byte, error) { // ERROR "leaking param: peerShare" - p256 := ecdh.P256() // ERROR "inlining call to ecdh.P256" - - ourKey, err := p256.GenerateKey(rand.Reader) // ERROR "devirtualizing p256.GenerateKey" "inlining call to ecdh.*GenerateKey" - if err != nil { - return nil, err - } - - peerPublic, err := p256.NewPublicKey(peerShare) // ERROR "devirtualizing p256.NewPublicKey" "inlining call to ecdh.*NewPublicKey" - if err != nil { - return nil, err - } - - return ourKey.ECDH(peerPublic) -} - // Test that inlining doesn't break if devirtualization exposes a new // inlinable callee. -- 2.48.1