0

is my code constant time?

Sun Yimin edited this page 2024-02-02 10:00:45 +08:00

Table of Contents

• ECDH & SM2 Key Exchange
• 相关代码

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

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困难得多，主要是第三、四和五步。

来自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轴值。

相关代码

8f7a7626ba