MPC 缺点：RFC6979

·v1 | 👀403
Crypto

现在 Ethereum 消息签名基本都是使用的 Deterministic ECDSA，确定性 ECDSA 签名，跟原始 ECDSA 签名的区别是原始的 ECDSA 算法，会随计选择一个 k 值，R = k*G 计算 r,s，而 RFC6979 指出了一种安全的根据消息选择确定随机数的算法 k = hmac\_sha256(d + sha256(msg))，只要 sha256 还是安全的私钥就不会被泄漏。

这个算法主要使用在消息签名时，针对同一消息，每次签名的结果都是一致的，有些 Dapp 会利用这个一致性做自己的业务，比如 dYdX。

RFC6979 Go 实现

package main

import (
	"bytes"
	"crypto/hmac"
	"hash"
	"math/big"
)

// mac returns an HMAC of the given key and message.
func mac(alg func() hash.Hash, k, m, buf []byte) []byte {
	h := hmac.New(alg, k)
	h.Write(m)
	return h.Sum(buf[:0])
}

// https://tools.ietf.org/html/rfc6979#section-2.3.2
func bits2int(in []byte, qlen int) *big.Int {
	vlen := len(in) * 8
	v := new(big.Int).SetBytes(in)
	if vlen > qlen {
		v = new(big.Int).Rsh(v, uint(vlen-qlen))
	}
	return v
}

// https://tools.ietf.org/html/rfc6979#section-2.3.3
func int2octets(v *big.Int, rolen int) []byte {
	out := v.Bytes()

	// pad with zeros if it's too short
	if len(out) < rolen {
		out2 := make([]byte, rolen)
		copy(out2[rolen-len(out):], out)
		return out2
	}

	// drop most significant bytes if it's too long
	if len(out) > rolen {
		out2 := make([]byte, rolen)
		copy(out2, out[len(out)-rolen:])
		return out2
	}

	return out
}

// https://tools.ietf.org/html/rfc6979#section-2.3.4
func bits2octets(in []byte, q *big.Int, qlen, rolen int) []byte {
	z1 := bits2int(in, qlen)
	z2 := new(big.Int).Sub(z1, q)
	if z2.Sign() < 0 {
		return int2octets(z1, rolen)
	}
	return int2octets(z2, rolen)
}

var one = big.NewInt(1)

// https://tools.ietf.org/html/rfc6979#section-3.2
func generateSecret(q, x *big.Int, alg func() hash.Hash, hash []byte, test func(*big.Int) bool) {
	qlen := q.BitLen()
	holen := alg().Size()
	rolen := (qlen + 7) >> 3
	bx := append(int2octets(x, rolen), bits2octets(hash, q, qlen, rolen)...)

	// Step B
	v := bytes.Repeat([]byte{0x01}, holen)

	// Step C
	k := bytes.Repeat([]byte{0x00}, holen)

	// Step D
	k = mac(alg, k, append(append(v, 0x00), bx...), k)

	// Step E
	v = mac(alg, k, v, v)

	// Step F
	k = mac(alg, k, append(append(v, 0x01), bx...), k)

	// Step G
	v = mac(alg, k, v, v)

	// Step H
	for {
		// Step H1
		var t []byte

		// Step H2
		for len(t) < qlen/8 {
			v = mac(alg, k, v, v)
			t = append(t, v...)
		}

		// Step H3
		secret := bits2int(t, qlen)
		if secret.Cmp(one) >= 0 && secret.Cmp(q) < 0 && test(secret) {
			return
		}
		k = mac(alg, k, append(v, 0x00), k)
		v = mac(alg, k, v, v)
	}
}

Sign

签名时的区别在于一个 k 是确定的，一个 k 是随机的。

func sign(msg string, privateKey *big.Int, rfc6979 bool) (*big.Int, *big.Int, *big.Int) {
	if rfc6979 {
		var r, s, k *big.Int
		generateSecret(N, privateKey, sha256.New, []byte(msg), func(i *big.Int) bool {
			k = i
			r, s = signWithK(msg, privateKey, k)
			return r.Sign() != 0 && s.Sign() != 0
		})
		return r, s, k
	} else {
		var err error
		// random K
		k, err := rand.Int(rand.Reader, math.MaxBig256)
		if err != nil {
			panic(err)
		}
		r, s := signWithK(msg, privateKey, k)
		return r, s, k
	}

}

func signWithK(msg string, privateKey *big.Int, k *big.Int) (*big.Int, *big.Int) {
	// msgHash = sha256(msg)
	h := sha256.Sum256([]byte(msg))
	msgHash := new(big.Int).SetBytes(h[:])
	// R = k*G
	Rx, _ := curve.ScalarBaseMult(k.Bytes())
	// r = Rx
	r := Rx
	// s = K^-1 * (msgHash + r*d) mod N
	rd := new(big.Int).Mul(privateKey, r)
	s := new(big.Int).Mod(new(big.Int).Mul(new(big.Int).Add(msgHash, rd), new(big.Int).ModInverse(k, N)), N)
	return r, s
}

Test case

package main

import (
	"fmt"
	"math/big"
	"strings"
	"testing"

	"github.com/starkbank/ecdsa-go/ellipticcurve/point"
)

func TestRFC6979(t *testing.T) {
	testCases := `(e4aa80b1720275bbb6017a2b1e216c6f0698e466ac9ce426dde8e99c776cf962,naiba,3044022079a7cb841ce1b7e89eeca135c83f34cc98962b3880e1dd74611459493b5b917f0220772a48416f4fa0a2789b7761a842fb3776b696f210baa81f1d6cc6ef2204910c)
(34c3f7bf319350be4567a9b87af5696a1453b987273ab6c959c794fd22fb612a,奶爸,30440220821400f2ca5e3a4237786acf3e614f31aec8e5ffc8aad300a3c1483c22aaccd302207292ff16c7def65fa77a902f23015009c3660487113a3489b28a6e1fc1b166be)`

	lines := strings.Split(testCases, "\n")
	for _, line := range lines {
		cols := strings.Split(line[1:len(line)-1], ",")
		pkStr := cols[0]
		pk, ok := new(big.Int).SetString(pkStr, 16)
		if !ok {
			t.Fatal("failed to parse pk")
		}
		msg := cols[1]
		expect := strings.ToLower(cols[2])
		t.Logf("pk: %s, bn: %s, msg: %s, expect: %s", pkStr, pk.String(), msg, expect)
		r, s, _ := sign(msg, pk, true)
		sig := fmt.Sprintf("%x", serializeSignatureToDERFormat(r, s))
		pX, pY := curve.ScalarBaseMult(pk.Bytes())
		t.Logf("verified: %v, publicKey: %x", verify(msg, r, s, point.Point{
			X: pX,
			Y: pY,
		}), curve.Marshal(pX, pY))
		if expect != sig {
			t.Fatalf("expect %s, got %s", expect, sig)
		}
	}
}

为什么是 MPC 的缺点

MPC 无私钥钱包基本原则是 keyless，不能在 MPC 的 keygen / sign 过程中出现完整私钥。基于这一基本原则，无法使用 RFC6979 定义的从私钥和消息中派生出 k，需要采用其他方式去派生确定的 k。

Resources

本文中关于 RFC6979 的实现来自下面的 GitHub Repo，完整代码请参考本系列第一篇博文《ECDSA》。

Comments