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  	fips140.RecordApproved()
   141  	// This procedure is equivalent to Key Pair Generation by Testing
   142  	// Candidates, specified in NIST SP 800-56A Rev. 3, Section 5.6.1.2.2.
   143  
   144  	for {
   145  		key := make([]byte, len(c.N))
   146  		if err := drbg.ReadWithReader(rand, key); err != nil {
   147  			return nil, err
   148  		}
   149  		// In tests, rand will return all zeros and NewPrivateKey will reject
   150  		// the zero key as it generates the identity as a public key. This also
   151  		// makes this function consistent with crypto/elliptic.GenerateKey.
   152  		key[1] ^= 0x42
   153  
   154  		// Mask off any excess bits if the size of the underlying field is not a
   155  		// whole number of bytes, which is only the case for P-521.
   156  		if c.curve == p521 && c.N[0]&0b1111_1110 == 0 {
   157  			key[0] &= 0b0000_0001
   158  		}
   159  
   160  		privateKey, err := NewPrivateKey(c, key)
   161  		if err != nil {
   162  			continue
   163  		}
   164  
   165  		// A "Pairwise Consistency Test" makes no sense if we just generated the
   166  		// public key from an ephemeral private key. Moreover, there is no way to
   167  		// check it aside from redoing the exact same computation again. SP 800-56A
   168  		// Rev. 3, Section 5.6.2.1.4 acknowledges that, and doesn't require it.
   169  		// However, ISO 19790:2012, Section 7.10.3.3 has a blanket requirement for a
   170  		// PCT for all generated keys (AS10.35) and FIPS 140-3 IG 10.3.A, Additional
   171  		// Comment 1 goes out of its way to say that "the PCT shall be performed
   172  		// consistent [...], even if the underlying standard does not require a
   173  		// PCT". So we do it. And make ECDH nearly 50% slower (only) in FIPS mode.
   174  		fips140.PCT("ECDH PCT", func() error {
   175  			p1, err := c.newPoint().ScalarBaseMult(privateKey.d)
   176  			if err != nil {
   177  				return err
   178  			}
   179  			if !bytes.Equal(p1.Bytes(), privateKey.pub.q) {
   180  				return errors.New("crypto/ecdh: public key does not match private key")
   181  			}
   182  			return nil
   183  		})
   184  
   185  		return privateKey, nil
   186  	}
   187  }
   188  
   189  func NewPrivateKey[P Point[P]](c *Curve[P], key []byte) (*PrivateKey, error) {
   190  	// SP 800-56A Rev. 3, Section 5.6.1.2.2 checks that c <= n – 2 and then
   191  	// returns d = c + 1. Note that it follows that 0 < d < n. Equivalently,
   192  	// we check that 0 < d < n, and return d.
   193  	if len(key) != len(c.N) || isZero(key) || !isLess(key, c.N) {
   194  		return nil, errors.New("crypto/ecdh: invalid private key")
   195  	}
   196  
   197  	p, err := c.newPoint().ScalarBaseMult(key)
   198  	if err != nil {
   199  		// This is unreachable because the only error condition of
   200  		// ScalarBaseMult is if the input is not the right size.
   201  		panic("crypto/ecdh: internal error: nistec ScalarBaseMult failed for a fixed-size input")
   202  	}
   203  
   204  	publicKey := p.Bytes()
   205  	if len(publicKey) == 1 {
   206  		// The encoding of the identity is a single 0x00 byte. This is
   207  		// unreachable because the only scalar that generates the identity is
   208  		// zero, which is rejected above.
   209  		panic("crypto/ecdh: internal error: public key is the identity element")
   210  	}
   211  
   212  	k := &PrivateKey{d: bytes.Clone(key), pub: PublicKey{curve: c.curve, q: publicKey}}
   213  	return k, nil
   214  }
   215  
   216  func NewPublicKey[P Point[P]](c *Curve[P], key []byte) (*PublicKey, error) {
   217  	// Reject the point at infinity and compressed encodings.
   218  	if len(key) == 0 || key[0] != 4 {
   219  		return nil, errors.New("crypto/ecdh: invalid public key")
   220  	}
   221  
   222  	// SetBytes checks that x and y are in the interval [0, p - 1], and that
   223  	// the point is on the curve. Along with the rejection of the point at
   224  	// infinity (the identity element) above, this fulfills the requirements
   225  	// of NIST SP 800-56A Rev. 3, Section 5.6.2.3.4.
   226  	if _, err := c.newPoint().SetBytes(key); err != nil {
   227  		return nil, err
   228  	}
   229  
   230  	return &PublicKey{curve: c.curve, q: bytes.Clone(key)}, nil
   231  }
   232  
   233  func ECDH[P Point[P]](c *Curve[P], k *PrivateKey, peer *PublicKey) ([]byte, error) {
   234  	fipsSelfTest()
   235  	fips140.RecordApproved()
   236  	return ecdh(c, k, peer)
   237  }
   238  
   239  func ecdh[P Point[P]](c *Curve[P], k *PrivateKey, peer *PublicKey) ([]byte, error) {
   240  	if c.curve != k.pub.curve {
   241  		return nil, errors.New("crypto/ecdh: mismatched curves")
   242  	}
   243  	if k.pub.curve != peer.curve {
   244  		return nil, errors.New("crypto/ecdh: mismatched curves")
   245  	}
   246  
   247  	// This applies the Shared Secret Computation of the Ephemeral Unified Model
   248  	// scheme specified in NIST SP 800-56A Rev. 3, Section 6.1.2.2.
   249  
   250  	// Per Section 5.6.2.3.4, Step 1, reject the identity element (0x00).
   251  	if len(k.pub.q) == 1 {
   252  		return nil, errors.New("crypto/ecdh: public key is the identity element")
   253  	}
   254  
   255  	// SetBytes checks that (x, y) are reduced modulo p, and that they are on
   256  	// the curve, performing Steps 2-3 of Section 5.6.2.3.4.
   257  	p, err := c.newPoint().SetBytes(peer.q)
   258  	if err != nil {
   259  		return nil, err
   260  	}
   261  
   262  	// Compute P according to Section 5.7.1.2.
   263  	if _, err := p.ScalarMult(p, k.d); err != nil {
   264  		return nil, err
   265  	}
   266  
   267  	// BytesX checks that the result is not the identity element, and returns the
   268  	// x-coordinate of the result, performing Steps 2-5 of Section 5.7.1.2.
   269  	return p.BytesX()
   270  }
   271  
   272  // isZero reports whether x is all zeroes in constant time.
   273  func isZero(x []byte) bool {
   274  	var acc byte
   275  	for _, b := range x {
   276  		acc |= b
   277  	}
   278  	return acc == 0
   279  }
   280  
   281  // isLess reports whether a < b, where a and b are big-endian buffers of the
   282  // same length and shorter than 72 bytes.
   283  func isLess(a, b []byte) bool {
   284  	if len(a) != len(b) {
   285  		panic("crypto/ecdh: internal error: mismatched isLess inputs")
   286  	}
   287  
   288  	// Copy the values into a fixed-size preallocated little-endian buffer.
   289  	// 72 bytes is enough for every scalar in this package, and having a fixed
   290  	// size lets us avoid heap allocations.
   291  	if len(a) > 72 {
   292  		panic("crypto/ecdh: internal error: isLess input too large")
   293  	}
   294  	bufA, bufB := make([]byte, 72), make([]byte, 72)
   295  	for i := range a {
   296  		bufA[i], bufB[i] = a[len(a)-i-1], b[len(b)-i-1]
   297  	}
   298  
   299  	// Perform a subtraction with borrow.
   300  	var borrow uint64
   301  	for i := 0; i < len(bufA); i += 8 {
   302  		limbA, limbB := byteorder.LEUint64(bufA[i:]), byteorder.LEUint64(bufB[i:])
   303  		_, borrow = bits.Sub64(limbA, limbB, borrow)
   304  	}
   305  
   306  	// If there is a borrow at the end of the operation, then a < b.
   307  	return borrow == 1
   308  }
   309
View as plain text