Skip to content

is my code constant time?

Jump to bottom
Sun Yimin edited this page Feb 2, 2024 · 18 revisions

Non-constant time crypto code is dangerous.

  1. Dude, is my code constant time?
  2. proposal: math/big: support for constant-time arithmetic
  3. crypto/elliptic: deprecate big.Int interface
  4. proposal: a new crypto/ecdh package that exposes a safe, []byte-based API for ECDH
  5. cmd/compile: use devirtualization in escape analysis
  6. cmd/compile: inlining after devirtualization
  7. crypto/elliptic: automatically upgrade CurveParams for known curves and deprecate custom ones
  8. PLANNING GO 1.20 CRYPTOGRAPHY WORK
  9. crypto/internal/bigmod: add amd64 assembly core
  10. The Marvin Attack
  11. CVE-2023-45287 Detail
  12. Vulnerability Report: GO-2023-2375

ECDH & SM2 Key Exchange

SM2 Key Exchange要去除big.Int依赖，看起来比ECDH困难得多，主要是第三、四和五步。

image

来自ipp-crypto的实现可供参考，待十月份取消golang 1.15后再考虑实现一个用于TLCP的不用big.Int的SM2 Key Exchange。

/**
 * @brief
 * reduction for the SM2 Key Exchange standard
 * x` = 2^w + (x & (2^w – 1))
 * when
 * w = log2(n)/2 - 1, n - number bytes order
 * @param[out] r   reduction value x`
 * @param[in]  a   value x
 * @param[in]  pEC context Elliptic Curve
 */
__INLINE void cpSM2KE_reduction_x2w(BNU_CHUNK_T *r, const BNU_CHUNK_T *a, const IppsGFpECState *pEC)
{
   const gsModEngine *pME = GFP_PMA(ECP_GFP(pEC));

   const int elemBits = GFP_FEBITLEN(pME); /* size Bits */
   const int elemSize = GFP_FELEN(pME);    /* size BNU_CHUNK */
   /* compute w = [log2(n)/2 - 1] */
   const int w = ((elemBits + 1) / 2 - 1);

   /* compute copy BNU_CHUNK */
   const int num_copy_bc   = (w + (BNU_CHUNK_BITS - 1)) / BNU_CHUNK_BITS; // 2, 假定BNU_CHUNK_BITS=64
   const int num_bit_shift = (w - (num_copy_bc - 1) * BNU_CHUNK_BITS);  // 63
   const BNU_CHUNK_T vadd  = (BNU_CHUNK_T)(1ULL << num_bit_shift); // 1<<63 = 0x8000000000000000
   const BNU_CHUNK_T mask  = (BNU_CHUNK_T)(vadd - 1); // 0x7fffffffffffffff

   ZEXPAND_COPY_BNU(r, elemSize, a, num_copy_bc);  // copy 2 64 bits from a to r
   r[num_copy_bc - 1] = (r[num_copy_bc - 1] & mask) + vadd;
   return;
}

相对而言，第四步计算tB运算需要实现素数为Order n的montgomery运算:

  1. 纯golang可以通过代码生成。
  2. amd64/arm64，至少需要实现加法，乘法已经有了。
type Curve interface {
	// ECDH performs a ECDH exchange and returns the shared secret.
	//
	// 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. In particular, if the result is the point at
	// infinity, ECDH returns an error. (Note that for NIST curves, that's only
	// possible if the private key is the all-zero value.)
	//
	// 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.
	ECDH(local *PrivateKey, remote *PublicKey) ([]byte, error)

	// SM2MQV performs a SM2 specific style ECMQV exchange and return the shared secret.
	SM2MQV(sLocal, eLocal *PrivateKey, sRemote, eRemote *PublicKey) (*PublicKey, error)

	// SM2SharedKey performs SM2 key derivation to generate shared keying data, the uv was generated by SM2MQV.
	SM2SharedKey(isResponder bool, kenLen int, uv, sPub, sRemote *PublicKey, uid []byte, remoteUID []byte) ([]byte, error)
        
	// GenerateKey generates a new PrivateKey from rand.
	GenerateKey(rand io.Reader) (*PrivateKey, error)

	// NewPrivateKey checks that key is valid and returns a PrivateKey.
	//
	// For NIST curves, this follows SEC 1, Version 2.0, Section 2.3.6, which
	// amounts to decoding the bytes as a fixed length big endian integer and
	// checking that the result is lower than the order of the curve. The zero
	// private key is also rejected, as the encoding of the corresponding public
	// key would be irregular.
	//
	// For X25519, this only checks the scalar length. Adversarially selected
	// private keys can cause ECDH to return an error.
	NewPrivateKey(key []byte) (*PrivateKey, error)

	// NewPublicKey checks that key is valid and returns a PublicKey.
	//
	// For NIST curves, this decodes an uncompressed point according to SEC 1,
	// Version 2.0, Section 2.3.4. Compressed encodings and the point at
	// infinity are rejected.
	//
	// For X25519, this only checks the u-coordinate length. Adversarially
	// selected public keys can cause ECDH to return an error.
	NewPublicKey(key []byte) (*PublicKey, error)

	// privateKeyToPublicKey converts a PrivateKey to a PublicKey. It's exposed
	// as the PrivateKey.PublicKey method.
	//
	// This method always succeeds: for X25519, it might output the all-zeroes
	// value (unlike the ECDH method); for NIST curves, it would only fail for
	// the zero private key, which is rejected by NewPrivateKey.
	//
	// The private method also allow us to expand the ECDH interface with more
	// methods in the future without breaking backwards compatibility.
	privateKeyToPublicKey(*PrivateKey) *PublicKey
}

其实，sm2 key exchange和SEC 1, Version 2.0, Section 3.4 Elliptic Curve MQV Primitive 描述的方法类似，只是最后取shared secret方法不同: ECMQV和DH一样，都只取X轴值。

相关代码

https://github.com/emmansun/gmsm/commit/8f7a7626baba61ba9c44371a71cd8bec0dbedc6f

Clone this wiki locally