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