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