ecdh.go

     1  // Copyright 2024 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package ecdh
     6  
     7  import (
     8  	"bytes"
     9  	"crypto/internal/fips140"
    10  	"crypto/internal/fips140/drbg"
    11  	"crypto/internal/fips140/nistec"
    12  	"crypto/internal/fips140deps/byteorder"
    13  	"errors"
    14  	"io"
    15  	"math/bits"
    16  )
    17  
    18  // PrivateKey and PublicKey are not generic to make it possible to use them
    19  // in other types without instantiating them with a specific point type.
    20  // They are tied to one of the Curve types below through the curveID field.
    21  
    22  // All this is duplicated from crypto/internal/fips/ecdsa, but the standards are
    23  // different and FIPS 140 does not allow reusing keys across them.
    24  
    25  type PrivateKey struct {
    26  	pub PublicKey
    27  	d   []byte // bigmod.(*Nat).Bytes output (fixed length)
    28  }
    29  
    30  func (priv *PrivateKey) Bytes() []byte {
    31  	return priv.d
    32  }
    33  
    34  func (priv *PrivateKey) PublicKey() *PublicKey {
    35  	return &priv.pub
    36  }
    37  
    38  type PublicKey struct {
    39  	curve curveID
    40  	q     []byte // uncompressed nistec Point.Bytes output
    41  }
    42  
    43  func (pub *PublicKey) Bytes() []byte {
    44  	return pub.q
    45  }
    46  
    47  type curveID string
    48  
    49  const (
    50  	p224 curveID = "P-224"
    51  	p256 curveID = "P-256"
    52  	p384 curveID = "P-384"
    53  	p521 curveID = "P-521"
    54  )
    55  
    56  type Curve[P Point[P]] struct {
    57  	curve    curveID
    58  	newPoint func() P
    59  	N        []byte
    60  }
    61  
    62  // Point is a generic constraint for the [nistec] Point types.
    63  type Point[P any] interface {
    64  	*nistec.P224Point | *nistec.P256Point | *nistec.P384Point | *nistec.P521Point
    65  	Bytes() []byte
    66  	BytesX() ([]byte, error)
    67  	SetBytes([]byte) (P, error)
    68  	ScalarMult(P, []byte) (P, error)
    69  	ScalarBaseMult([]byte) (P, error)
    70  }
    71  
    72  func P224() *Curve[*nistec.P224Point] {
    73  	return &Curve[*nistec.P224Point]{
    74  		curve:    p224,
    75  		newPoint: nistec.NewP224Point,
    76  		N:        p224Order,
    77  	}
    78  }
    79  
    80  var p224Order = []byte{
    81  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    82  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x16, 0xa2,
    83  	0xe0, 0xb8, 0xf0, 0x3e, 0x13, 0xdd, 0x29, 0x45,
    84  	0x5c, 0x5c, 0x2a, 0x3d,
    85  }
    86  
    87  func P256() *Curve[*nistec.P256Point] {
    88  	return &Curve[*nistec.P256Point]{
    89  		curve:    p256,
    90  		newPoint: nistec.NewP256Point,
    91  		N:        p256Order,
    92  	}
    93  }
    94  
    95  var p256Order = []byte{
    96  	0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
    97  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    98  	0xbc, 0xe6, 0xfa, 0xad, 0xa7, 0x17, 0x9e, 0x84,
    99  	0xf3, 0xb9, 0xca, 0xc2, 0xfc, 0x63, 0x25, 0x51,
   100  }
   101  
   102  func P384() *Curve[*nistec.P384Point] {
   103  	return &Curve[*nistec.P384Point]{
   104  		curve:    p384,
   105  		newPoint: nistec.NewP384Point,
   106  		N:        p384Order,
   107  	}
   108  }
   109  
   110  var p384Order = []byte{
   111  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
   112  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
   113  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
   114  	0xc7, 0x63, 0x4d, 0x81, 0xf4, 0x37, 0x2d, 0xdf,
   115  	0x58, 0x1a, 0x0d, 0xb2, 0x48, 0xb0, 0xa7, 0x7a,
   116  	0xec, 0xec, 0x19, 0x6a, 0xcc, 0xc5, 0x29, 0x73,
   117  }
   118  
   119  func P521() *Curve[*nistec.P521Point] {
   120  	return &Curve[*nistec.P521Point]{
   121  		curve:    p521,
   122  		newPoint: nistec.NewP521Point,
   123  		N:        p521Order,
   124  	}
   125  }
   126  
   127  var p521Order = []byte{0x01, 0xff,
   128  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
   129  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
   130  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
   131  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfa,
   132  	0x51, 0x86, 0x87, 0x83, 0xbf, 0x2f, 0x96, 0x6b,
   133  	0x7f, 0xcc, 0x01, 0x48, 0xf7, 0x09, 0xa5, 0xd0,
   134  	0x3b, 0xb5, 0xc9, 0xb8, 0x89, 0x9c, 0x47, 0xae,
   135  	0xbb, 0x6f, 0xb7, 0x1e, 0x91, 0x38, 0x64, 0x09,
   136  }
   137  
   138  // GenerateKey generates a new ECDSA private key pair for the specified curve.
   139  func GenerateKey[P Point[P]](c *Curve[P], rand io.Reader) (*PrivateKey, error) {
   140  	fipsSelfTest()
   141  	fips140.RecordApproved()
   142  	// This procedure is equivalent to Key Pair Generation by Testing
   143  	// Candidates, specified in NIST SP 800-56A Rev. 3, Section 5.6.1.2.2.
   144  
   145  	for {
   146  		key := make([]byte, len(c.N))
   147  		if err := drbg.ReadWithReader(rand, key); err != nil {
   148  			return nil, err
   149  		}
   150  		// In tests, rand will return all zeros and NewPrivateKey will reject
   151  		// the zero key as it generates the identity as a public key. This also
   152  		// makes this function consistent with crypto/elliptic.GenerateKey.
   153  		key[1] ^= 0x42
   154  
   155  		// Mask off any excess bits if the size of the underlying field is not a
   156  		// whole number of bytes, which is only the case for P-521.
   157  		if c.curve == p521 && c.N[0]&0b1111_1110 == 0 {
   158  			key[0] &= 0b0000_0001
   159  		}
   160  
   161  		privateKey, err := NewPrivateKey(c, key)
   162  		if err != nil {
   163  			continue
   164  		}
   165  
   166  		// A "Pairwise Consistency Test" makes no sense if we just generated the
   167  		// public key from an ephemeral private key. Moreover, there is no way to
   168  		// check it aside from redoing the exact same computation again. SP 800-56A
   169  		// Rev. 3, Section 5.6.2.1.4 acknowledges that, and doesn't require it.
   170  		// However, ISO 19790:2012, Section 7.10.3.3 has a blanket requirement for a
   171  		// PCT for all generated keys (AS10.35) and FIPS 140-3 IG 10.3.A, Additional
   172  		// Comment 1 goes out of its way to say that "the PCT shall be performed
   173  		// consistent [...], even if the underlying standard does not require a
   174  		// PCT". So we do it. And make ECDH nearly 50% slower (only) in FIPS mode.
   175  		fips140.PCT("ECDH PCT", func() error {
   176  			p1, err := c.newPoint().ScalarBaseMult(privateKey.d)
   177  			if err != nil {
   178  				return err
   179  			}
   180  			if !bytes.Equal(p1.Bytes(), privateKey.pub.q) {
   181  				return errors.New("crypto/ecdh: public key does not match private key")
   182  			}
   183  			return nil
   184  		})
   185  
   186  		return privateKey, nil
   187  	}
   188  }
   189  
   190  func NewPrivateKey[P Point[P]](c *Curve[P], key []byte) (*PrivateKey, error) {
   191  	fipsSelfTest()
   192  
   193  	// SP 800-56A Rev. 3, Section 5.6.1.2.2 checks that c <= n – 2 and then
   194  	// returns d = c + 1. Note that it follows that 0 < d < n. Equivalently,
   195  	// we check that 0 < d < n, and return d.
   196  	if len(key) != len(c.N) || isZero(key) || !isLess(key, c.N) {
   197  		return nil, errors.New("crypto/ecdh: invalid private key")
   198  	}
   199  
   200  	p, err := c.newPoint().ScalarBaseMult(key)
   201  	if err != nil {
   202  		// This is unreachable because the only error condition of
   203  		// ScalarBaseMult is if the input is not the right size.
   204  		panic("crypto/ecdh: internal error: nistec ScalarBaseMult failed for a fixed-size input")
   205  	}
   206  
   207  	publicKey := p.Bytes()
   208  	if len(publicKey) == 1 {
   209  		// The encoding of the identity is a single 0x00 byte. This is
   210  		// unreachable because the only scalar that generates the identity is
   211  		// zero, which is rejected above.
   212  		panic("crypto/ecdh: internal error: public key is the identity element")
   213  	}
   214  
   215  	k := &PrivateKey{d: bytes.Clone(key), pub: PublicKey{curve: c.curve, q: publicKey}}
   216  	return k, nil
   217  }
   218  
   219  func NewPublicKey[P Point[P]](c *Curve[P], key []byte) (*PublicKey, error) {
   220  	// Reject the point at infinity and compressed encodings.
   221  	if len(key) == 0 || key[0] != 4 {
   222  		return nil, errors.New("crypto/ecdh: invalid public key")
   223  	}
   224  
   225  	// SetBytes checks that x and y are in the interval [0, p - 1], and that
   226  	// the point is on the curve. Along with the rejection of the point at
   227  	// infinity (the identity element) above, this fulfills the requirements
   228  	// of NIST SP 800-56A Rev. 3, Section 5.6.2.3.4.
   229  	if _, err := c.newPoint().SetBytes(key); err != nil {
   230  		return nil, err
   231  	}
   232  
   233  	return &PublicKey{curve: c.curve, q: bytes.Clone(key)}, nil
   234  }
   235  
   236  func ECDH[P Point[P]](c *Curve[P], k *PrivateKey, peer *PublicKey) ([]byte, error) {
   237  	fipsSelfTest()
   238  	fips140.RecordApproved()
   239  	return ecdh(c, k, peer)
   240  }
   241  
   242  func ecdh[P Point[P]](c *Curve[P], k *PrivateKey, peer *PublicKey) ([]byte, error) {
   243  	if c.curve != k.pub.curve {
   244  		return nil, errors.New("crypto/ecdh: mismatched curves")
   245  	}
   246  	if k.pub.curve != peer.curve {
   247  		return nil, errors.New("crypto/ecdh: mismatched curves")
   248  	}
   249  
   250  	// This applies the Shared Secret Computation of the Ephemeral Unified Model
   251  	// scheme specified in NIST SP 800-56A Rev. 3, Section 6.1.2.2.
   252  
   253  	// Per Section 5.6.2.3.4, Step 1, reject the identity element (0x00).
   254  	if len(k.pub.q) == 1 {
   255  		return nil, errors.New("crypto/ecdh: public key is the identity element")
   256  	}
   257  
   258  	// SetBytes checks that (x, y) are reduced modulo p, and that they are on
   259  	// the curve, performing Steps 2-3 of Section 5.6.2.3.4.
   260  	p, err := c.newPoint().SetBytes(peer.q)
   261  	if err != nil {
   262  		return nil, err
   263  	}
   264  
   265  	// Compute P according to Section 5.7.1.2.
   266  	if _, err := p.ScalarMult(p, k.d); err != nil {
   267  		return nil, err
   268  	}
   269  
   270  	// BytesX checks that the result is not the identity element, and returns the
   271  	// x-coordinate of the result, performing Steps 2-5 of Section 5.7.1.2.
   272  	return p.BytesX()
   273  }
   274  
   275  // isZero reports whether x is all zeroes in constant time.
   276  func isZero(x []byte) bool {
   277  	var acc byte
   278  	for _, b := range x {
   279  		acc |= b
   280  	}
   281  	return acc == 0
   282  }
   283  
   284  // isLess reports whether a < b, where a and b are big-endian buffers of the
   285  // same length and shorter than 72 bytes.
   286  func isLess(a, b []byte) bool {
   287  	if len(a) != len(b) {
   288  		panic("crypto/ecdh: internal error: mismatched isLess inputs")
   289  	}
   290  
   291  	// Copy the values into a fixed-size preallocated little-endian buffer.
   292  	// 72 bytes is enough for every scalar in this package, and having a fixed
   293  	// size lets us avoid heap allocations.
   294  	if len(a) > 72 {
   295  		panic("crypto/ecdh: internal error: isLess input too large")
   296  	}
   297  	bufA, bufB := make([]byte, 72), make([]byte, 72)
   298  	for i := range a {
   299  		bufA[i], bufB[i] = a[len(a)-i-1], b[len(b)-i-1]
   300  	}
   301  
   302  	// Perform a subtraction with borrow.
   303  	var borrow uint64
   304  	for i := 0; i < len(bufA); i += 8 {
   305  		limbA, limbB := byteorder.LEUint64(bufA[i:]), byteorder.LEUint64(bufB[i:])
   306  		_, borrow = bits.Sub64(limbA, limbB, borrow)
   307  	}
   308  
   309  	// If there is a borrow at the end of the operation, then a < b.
   310  	return borrow == 1
   311  }
   312
View as plain text