From 1c0923dcc553f90a927c86889cc45f91fae21847 Mon Sep 17 00:00:00 2001 From: yahtoo Date: Tue, 23 Jan 2018 16:58:32 +0800 Subject: [PATCH] Full BIP32 EdDSA compatibility (#314) --- crypto/ed25519/chainkd/chainkd.go | 317 +++++++++++++++++----------- crypto/ed25519/chainkd/chainkd_test.go | 195 +++++++++++++++-- crypto/ed25519/chainkd/expanded_key.go | 102 +++++++++ crypto/ed25519/chainkd/expanded_key_test.go | 97 +++++++++ crypto/ed25519/chainkd/serialize_test.go | 5 +- 5 files changed, 573 insertions(+), 143 deletions(-) create mode 100644 crypto/ed25519/chainkd/expanded_key.go create mode 100644 crypto/ed25519/chainkd/expanded_key_test.go diff --git a/crypto/ed25519/chainkd/chainkd.go b/crypto/ed25519/chainkd/chainkd.go index a666113b..5d8ca4ea 100644 --- a/crypto/ed25519/chainkd/chainkd.go +++ b/crypto/ed25519/chainkd/chainkd.go @@ -1,26 +1,26 @@ package chainkd import ( + "crypto/hmac" "crypto/rand" "crypto/sha512" - "encoding/binary" - "hash" "io" "github.com/bytom/crypto/ed25519" - "github.com/bytom/crypto/ed25519/internal/edwards25519" + "github.com/bytom/crypto/ed25519/ecmath" ) type ( - // TODO(bobg): consider making these types opaque. See https://github.com/chain/chain/pull/1875#discussion_r80577736 + //XPrv external private key XPrv [64]byte + //XPub external public key XPub [64]byte ) var one = [32]byte{1} -// NewXPrv takes a source of random bytes and produces a new XPrv. If -// r is nil, crypto/rand.Reader is used. +// NewXPrv takes a source of random bytes and produces a new XPrv. +// If r is nil, crypto/rand.Reader is used. func NewXPrv(r io.Reader) (xprv XPrv, err error) { if r == nil { r = rand.Reader @@ -30,89 +30,186 @@ func NewXPrv(r io.Reader) (xprv XPrv, err error) { if err != nil { return xprv, err } - hasher := sha512.New() - hasher.Write([]byte("Bytom seed")) - hasher.Write(entropy[:]) - hasher.Sum(xprv[:0]) - modifyScalar(xprv[:32]) - return xprv, nil + return RootXPrv(entropy[:]), nil } -func (xprv XPrv) XPub() XPub { - var buf [32]byte - copy(buf[:], xprv[:32]) +// RootXPrv takes a seed binary string and produces a new xprv. +func RootXPrv(seed []byte) (xprv XPrv) { + h := hmac.New(sha512.New, []byte{'R', 'o', 'o', 't'}) + h.Write(seed) + h.Sum(xprv[:0]) + pruneRootScalar(xprv[:32]) + return +} + +// XPub derives an extended public key from a given xprv. +func (xprv XPrv) XPub() (xpub XPub) { + var scalar ecmath.Scalar + copy(scalar[:], xprv[:32]) - var P edwards25519.ExtendedGroupElement - edwards25519.GeScalarMultBase(&P, &buf) - P.ToBytes(&buf) + var P ecmath.Point + P.ScMulBase(&scalar) + buf := P.Encode() - var xpub XPub copy(xpub[:32], buf[:]) copy(xpub[32:], xprv[32:]) - return xpub + return } -func (xprv XPrv) Child(sel []byte, hardened bool) (res XPrv) { +// Child derives a child xprv based on `selector` string and `hardened` flag. +// If `hardened` is false, child xpub can be derived independently +// from the parent xpub without using the parent xprv. +// If `hardened` is true, child key can only be derived from the parent xprv. +func (xprv XPrv) Child(sel []byte, hardened bool) XPrv { if hardened { - hashKeySaltSelector(res[:], 0, xprv[:32], xprv[32:], sel) - return res + return xprv.hardenedChild(sel) } + return xprv.nonhardenedChild(sel) +} - var s [32]byte - copy(s[:], xprv[:32]) - var P edwards25519.ExtendedGroupElement - edwards25519.GeScalarMultBase(&P, &s) - - var pubkey [32]byte - P.ToBytes(&pubkey) - - hashKeySaltSelector(res[:], 1, pubkey[:], xprv[32:], sel) - - var ( - f [32]byte - s2 [32]byte - ) - copy(f[:], res[:32]) - edwards25519.ScMulAdd(&s2, &one, &f, &s) - copy(res[:32], s2[:]) +func (xprv XPrv) hardenedChild(sel []byte) (res XPrv) { + h := hmac.New(sha512.New, xprv[32:]) + h.Write([]byte{'H'}) + h.Write(xprv[:32]) + h.Write(sel) + h.Sum(res[:0]) + pruneRootScalar(res[:32]) + return +} - return res +func (xprv XPrv) nonhardenedChild(sel []byte) (res XPrv) { + xpub := xprv.XPub() + + h := hmac.New(sha512.New, xpub[32:]) + h.Write([]byte{'N'}) + h.Write(xpub[:32]) + h.Write(sel) + h.Sum(res[:0]) + + pruneIntermediateScalar(res[:32]) + + // Unrolled the following loop: + // var carry int + // carry = 0 + // for i := 0; i < 32; i++ { + // sum := int(xprv[i]) + int(res[i]) + carry + // res[i] = byte(sum & 0xff) + // carry = (sum >> 8) + // } + + sum := int(0) + + sum = int(xprv[0]) + int(res[0]) + (sum >> 8) + res[0] = byte(sum & 0xff) + sum = int(xprv[1]) + int(res[1]) + (sum >> 8) + res[1] = byte(sum & 0xff) + sum = int(xprv[2]) + int(res[2]) + (sum >> 8) + res[2] = byte(sum & 0xff) + sum = int(xprv[3]) + int(res[3]) + (sum >> 8) + res[3] = byte(sum & 0xff) + sum = int(xprv[4]) + int(res[4]) + (sum >> 8) + res[4] = byte(sum & 0xff) + sum = int(xprv[5]) + int(res[5]) + (sum >> 8) + res[5] = byte(sum & 0xff) + sum = int(xprv[6]) + int(res[6]) + (sum >> 8) + res[6] = byte(sum & 0xff) + sum = int(xprv[7]) + int(res[7]) + (sum >> 8) + res[7] = byte(sum & 0xff) + sum = int(xprv[8]) + int(res[8]) + (sum >> 8) + res[8] = byte(sum & 0xff) + sum = int(xprv[9]) + int(res[9]) + (sum >> 8) + res[9] = byte(sum & 0xff) + sum = int(xprv[10]) + int(res[10]) + (sum >> 8) + res[10] = byte(sum & 0xff) + sum = int(xprv[11]) + int(res[11]) + (sum >> 8) + res[11] = byte(sum & 0xff) + sum = int(xprv[12]) + int(res[12]) + (sum >> 8) + res[12] = byte(sum & 0xff) + sum = int(xprv[13]) + int(res[13]) + (sum >> 8) + res[13] = byte(sum & 0xff) + sum = int(xprv[14]) + int(res[14]) + (sum >> 8) + res[14] = byte(sum & 0xff) + sum = int(xprv[15]) + int(res[15]) + (sum >> 8) + res[15] = byte(sum & 0xff) + sum = int(xprv[16]) + int(res[16]) + (sum >> 8) + res[16] = byte(sum & 0xff) + sum = int(xprv[17]) + int(res[17]) + (sum >> 8) + res[17] = byte(sum & 0xff) + sum = int(xprv[18]) + int(res[18]) + (sum >> 8) + res[18] = byte(sum & 0xff) + sum = int(xprv[19]) + int(res[19]) + (sum >> 8) + res[19] = byte(sum & 0xff) + sum = int(xprv[20]) + int(res[20]) + (sum >> 8) + res[20] = byte(sum & 0xff) + sum = int(xprv[21]) + int(res[21]) + (sum >> 8) + res[21] = byte(sum & 0xff) + sum = int(xprv[22]) + int(res[22]) + (sum >> 8) + res[22] = byte(sum & 0xff) + sum = int(xprv[23]) + int(res[23]) + (sum >> 8) + res[23] = byte(sum & 0xff) + sum = int(xprv[24]) + int(res[24]) + (sum >> 8) + res[24] = byte(sum & 0xff) + sum = int(xprv[25]) + int(res[25]) + (sum >> 8) + res[25] = byte(sum & 0xff) + sum = int(xprv[26]) + int(res[26]) + (sum >> 8) + res[26] = byte(sum & 0xff) + sum = int(xprv[27]) + int(res[27]) + (sum >> 8) + res[27] = byte(sum & 0xff) + sum = int(xprv[28]) + int(res[28]) + (sum >> 8) + res[28] = byte(sum & 0xff) + sum = int(xprv[29]) + int(res[29]) + (sum >> 8) + res[29] = byte(sum & 0xff) + sum = int(xprv[30]) + int(res[30]) + (sum >> 8) + res[30] = byte(sum & 0xff) + sum = int(xprv[31]) + int(res[31]) + (sum >> 8) + res[31] = byte(sum & 0xff) + + if (sum >> 8) != 0 { + panic("sum does not fit in 256-bit int") + } + return } +// Child derives a child xpub based on `selector` string. +// The corresponding child xprv can be derived from the parent xprv +// using non-hardened derivation: `parentxprv.Child(sel, false)`. func (xpub XPub) Child(sel []byte) (res XPub) { - hashKeySaltSelector(res[:], 1, xpub[:32], xpub[32:], sel) + h := hmac.New(sha512.New, xpub[32:]) + h.Write([]byte{'N'}) + h.Write(xpub[:32]) + h.Write(sel) + h.Sum(res[:0]) + + pruneIntermediateScalar(res[:32]) var ( - f [32]byte - F edwards25519.ExtendedGroupElement + f ecmath.Scalar + F ecmath.Point ) copy(f[:], res[:32]) - edwards25519.GeScalarMultBase(&F, &f) + F.ScMulBase(&f) var ( pubkey [32]byte - P edwards25519.ExtendedGroupElement + P ecmath.Point ) copy(pubkey[:], xpub[:32]) - P.FromBytes(&pubkey) - - var ( - P2 edwards25519.ExtendedGroupElement - R edwards25519.CompletedGroupElement - Fc edwards25519.CachedGroupElement - ) - F.ToCached(&Fc) - edwards25519.GeAdd(&R, &P, &Fc) - R.ToExtended(&P2) - - P2.ToBytes(&pubkey) + _, ok := P.Decode(pubkey) + if !ok { + panic("XPub should have been validated on initialization") + } + P.Add(&P, &F) + pubkey = P.Encode() copy(res[:32], pubkey[:]) - return res + return } +// Derive generates a child xprv by recursively deriving +// non-hardened child xprvs over the list of selectors: +// `Derive([a,b,c,...]) == Child(a).Child(b).Child(c)...` func (xprv XPrv) Derive(path [][]byte) XPrv { res := xprv for _, p := range path { @@ -121,6 +218,9 @@ func (xprv XPrv) Derive(path [][]byte) XPrv { return res } +// Derive generates a child xpub by recursively deriving +// non-hardened child xpubs over the list of selectors: +// `Derive([a,b,c,...]) == Child(a).Child(b).Child(c)...` func (xpub XPub) Derive(path [][]byte) XPub { res := xpub for _, p := range path { @@ -129,86 +229,49 @@ func (xpub XPub) Derive(path [][]byte) XPub { return res } +// Sign creates an EdDSA signature using expanded private key +// derived from the xprv. func (xprv XPrv) Sign(msg []byte) []byte { - var s [32]byte - copy(s[:], xprv[:32]) - - var h [64]byte - hashKeySalt(h[:], 2, xprv[:32], xprv[32:]) - - var P edwards25519.ExtendedGroupElement - edwards25519.GeScalarMultBase(&P, &s) - - var pubkey [32]byte - P.ToBytes(&pubkey) - - var r [64]byte - hasher := sha512.New() - hasher.Write(h[:32]) - hasher.Write(msg) - hasher.Sum(r[:0]) - - var rReduced [32]byte - edwards25519.ScReduce(&rReduced, &r) - - var rPoint edwards25519.ExtendedGroupElement - edwards25519.GeScalarMultBase(&rPoint, &rReduced) - - var R [32]byte - rPoint.ToBytes(&R) - - hasher.Reset() - hasher.Write(R[:]) - hasher.Write(pubkey[:]) - hasher.Write(msg) - - var k [64]byte - hasher.Sum(k[:0]) - - var kReduced [32]byte - edwards25519.ScReduce(&kReduced, &k) - - var S [32]byte - edwards25519.ScMulAdd(&S, &kReduced, &s, &rReduced) - - return append(R[:], S[:]...) + return Ed25519InnerSign(xprv.ExpandedPrivateKey(), msg) } +// Verify checks an EdDSA signature using public key +// extracted from the first 32 bytes of the xpub. func (xpub XPub) Verify(msg []byte, sig []byte) bool { return ed25519.Verify(xpub.PublicKey(), msg, sig) } +// ExpandedPrivateKey generates a 64-byte key where +// the first half is the scalar copied from xprv, +// and the second half is the `prefix` is generated via PRF +// from the xprv. +func (xprv XPrv) ExpandedPrivateKey() ExpandedPrivateKey { + var res [64]byte + h := hmac.New(sha512.New, []byte{'E', 'x', 'p', 'a', 'n', 'd'}) + h.Write(xprv[:]) + h.Sum(res[:0]) + copy(res[:32], xprv[:32]) + return res[:] +} + // PublicKey extracts the ed25519 public key from an xpub. func (xpub XPub) PublicKey() ed25519.PublicKey { return ed25519.PublicKey(xpub[:32]) } -func hashKeySaltSelector(out []byte, version byte, key, salt, sel []byte) { - hasher := hashKeySaltHelper(version, key, salt) - var l [10]byte - n := binary.PutUvarint(l[:], uint64(len(sel))) - hasher.Write(l[:n]) - hasher.Write(sel) - hasher.Sum(out[:0]) - modifyScalar(out) -} - -func hashKeySalt(out []byte, version byte, key, salt []byte) { - hasher := hashKeySaltHelper(version, key, salt) - hasher.Sum(out[:0]) -} - -func hashKeySaltHelper(version byte, key, salt []byte) hash.Hash { - hasher := sha512.New() - hasher.Write([]byte{version}) - hasher.Write(key) - hasher.Write(salt) - return hasher +// s must be >= 32 bytes long and gets rewritten in place. +// This is NOT the same pruning as in Ed25519: it additionally clears the third +// highest bit to ensure subkeys do not overflow the second highest bit. +func pruneRootScalar(s []byte) { + s[0] &= 248 + s[31] &= 31 // clear top 3 bits + s[31] |= 64 // set second highest bit } -// s must be >= 32 bytes long and gets rewritten in place -func modifyScalar(s []byte) { - s[0] &= 248 - s[31] &= 127 - s[31] |= 64 +// Clears lowest 3 bits and highest 23 bits of `f`. +func pruneIntermediateScalar(f []byte) { + f[0] &= 248 // clear bottom 3 bits + f[29] &= 1 // clear 7 high bits + f[30] = 0 // clear 8 bits + f[31] = 0 // clear 8 bits } diff --git a/crypto/ed25519/chainkd/chainkd_test.go b/crypto/ed25519/chainkd/chainkd_test.go index 7818f2bb..da3a0023 100644 --- a/crypto/ed25519/chainkd/chainkd_test.go +++ b/crypto/ed25519/chainkd/chainkd_test.go @@ -1,11 +1,115 @@ package chainkd import ( + "bytes" + "encoding/hex" "fmt" "reflect" "testing" ) +func TestVectors1(t *testing.T) { + root := RootXPrv([]byte{0x01, 0x02, 0x03}) + + verifyTestVector(t, "Root(010203).xprv", root.hex(), + "50f8c532ce6f088de65c2c1fbc27b491509373fab356eba300dfa7cc587b07483bc9e0d93228549c6888d3f68ad664b92c38f5ea8ca07181c1410949c02d3146") + verifyTestVector(t, "Root(010203).xpub", root.XPub().hex(), + "e11f321ffef364d01c2df2389e61091b15dab2e8eee87cb4c053fa65ed2812993bc9e0d93228549c6888d3f68ad664b92c38f5ea8ca07181c1410949c02d3146") + + verifyTestVector(t, "Root(010203)/010203(H).xprv", root.Child([]byte{0x01, 0x02, 0x03}, true).hex(), + "6023c8e7633a9353a59bd930ea6dc397e400b1088b86b4a15d8de8567554df5574274bc1a0bd93b4494cb68e45c5ec5aefc1eed4d0c3bfd53b0b4e679ce52028") + verifyTestVector(t, "Root(010203)/010203(H).xpub", root.Child([]byte{0x01, 0x02, 0x03}, true).XPub().hex(), + "eabebab4184c63f8df07efe31fb588a0ae222318087458b4936bf0b0feab015074274bc1a0bd93b4494cb68e45c5ec5aefc1eed4d0c3bfd53b0b4e679ce52028") + + verifyTestVector(t, "Root(010203)/010203(N).xprv", root.Child([]byte{0x01, 0x02, 0x03}, false).hex(), + "705afd25a0e242b7333105d77cbb0ec15e667154916bbed5084c355dba7b0748b0faca523928f42e685ee6deb0cb3d41a09617783c87e9a161a04f2207ad4d2f") + verifyTestVector(t, "Root(010203)/010203(N).xpub", root.Child([]byte{0x01, 0x02, 0x03}, false).XPub().hex(), + "c0bbd87142e7bf90abfbb3d0cccc210c6d7eb3f912c35f205302c86ae9ef6eefb0faca523928f42e685ee6deb0cb3d41a09617783c87e9a161a04f2207ad4d2f") + verifyTestVector(t, "Root(010203)/010203(N).xpub", root.XPub().Child([]byte{0x01, 0x02, 0x03}).hex(), + "c0bbd87142e7bf90abfbb3d0cccc210c6d7eb3f912c35f205302c86ae9ef6eefb0faca523928f42e685ee6deb0cb3d41a09617783c87e9a161a04f2207ad4d2f") + + verifyTestVector(t, "Root(010203)/010203(H)/“”(N).xprv", root.Child([]byte{0x01, 0x02, 0x03}, true).Child([]byte{}, false).hex(), + "7023f9877813348ca8e67b29d551baf98a43cfb76cdff538f3ff97074a55df5560e3aa7fb600f61a84317a981dc9d1f7e8df2e8a3f8b544a21d2404e0b4e480a") + verifyTestVector(t, "Root(010203)/010203(H)/“”(N).xpub", root.Child([]byte{0x01, 0x02, 0x03}, true).Child([]byte{}, false).XPub().hex(), + "4e44c9ab8a45b9d1c3daab5c09d73b01209220ea704808f04feaa3614c7c7ba760e3aa7fb600f61a84317a981dc9d1f7e8df2e8a3f8b544a21d2404e0b4e480a") + verifyTestVector(t, "Root(010203)/010203(H)/“”(N).xpub", root.Child([]byte{0x01, 0x02, 0x03}, true).XPub().Child([]byte{}).hex(), + "4e44c9ab8a45b9d1c3daab5c09d73b01209220ea704808f04feaa3614c7c7ba760e3aa7fb600f61a84317a981dc9d1f7e8df2e8a3f8b544a21d2404e0b4e480a") + + verifyTestVector(t, "Root(010203)/010203(N)/“”(H).xprv", root.Child([]byte{0x01, 0x02, 0x03}, false).Child([]byte{}, true).hex(), + "90b60b007e866dacc4b1f844089a805ffd78a295f5b0544034116ace354c58523410b1e6a3c557ca90c322f6ff4b5e547242965eaed8c34767765f0e05ed0e4f") + verifyTestVector(t, "Root(010203)/010203(N)/“”(H).xpub", root.Child([]byte{0x01, 0x02, 0x03}, false).Child([]byte{}, true).XPub().hex(), + "ca97ec34ef30aa08ebd19b9848b11ebadf9c0ad3a0be6b11d33d9558573aca633410b1e6a3c557ca90c322f6ff4b5e547242965eaed8c34767765f0e05ed0e4f") + + verifyTestVector(t, "Root(010203)/010203(N)/“”(N).xprv", root.Child([]byte{0x01, 0x02, 0x03}, false).Child([]byte{}, false).hex(), + "d81ba3ab554a7d09bfd8bda5089363399b7f4b19d4f1806ca0c35feabf7b074856648f55e21bec3aa5df0bce0236aea88a4cc5c395c896df63676f095154bb7b") + verifyTestVector(t, "Root(010203)/010203(N)/“”(N).xpub", root.Child([]byte{0x01, 0x02, 0x03}, false).Child([]byte{}, false).XPub().hex(), + "28279bcb06aee9e5c0302f4e1db879ac7f5444ec07266a736dd571c21961427b56648f55e21bec3aa5df0bce0236aea88a4cc5c395c896df63676f095154bb7b") + verifyTestVector(t, "Root(010203)/010203(N)/“”(N).xpub", root.XPub().Child([]byte{0x01, 0x02, 0x03}).Child([]byte{}).hex(), + "28279bcb06aee9e5c0302f4e1db879ac7f5444ec07266a736dd571c21961427b56648f55e21bec3aa5df0bce0236aea88a4cc5c395c896df63676f095154bb7b") + + verifyTestVector(t, "Root(010203)/010203(N)/“”(N).xprv", root.Derive([][]byte{[]byte{0x01, 0x02, 0x03}, []byte{}}).hex(), + "d81ba3ab554a7d09bfd8bda5089363399b7f4b19d4f1806ca0c35feabf7b074856648f55e21bec3aa5df0bce0236aea88a4cc5c395c896df63676f095154bb7b") + verifyTestVector(t, "Root(010203)/010203(N)/“”(N).xprv", root.Derive([][]byte{[]byte{0x01, 0x02, 0x03}, []byte{}}).XPub().hex(), + "28279bcb06aee9e5c0302f4e1db879ac7f5444ec07266a736dd571c21961427b56648f55e21bec3aa5df0bce0236aea88a4cc5c395c896df63676f095154bb7b") + verifyTestVector(t, "Root(010203)/010203(N)/“”(N).xpub", root.XPub().Derive([][]byte{[]byte{0x01, 0x02, 0x03}, []byte{}}).hex(), + "28279bcb06aee9e5c0302f4e1db879ac7f5444ec07266a736dd571c21961427b56648f55e21bec3aa5df0bce0236aea88a4cc5c395c896df63676f095154bb7b") +} + +func TestVectors2(t *testing.T) { + seed, _ := hex.DecodeString("fffcf9f6f3f0edeae7e4e1dedbd8d5d2cfccc9c6c3c0bdbab7b4b1aeaba8a5a29f9c999693908d8a8784817e7b7875726f6c696663605d5a5754514e4b484542") + root := RootXPrv(seed) + + verifyTestVector(t, "Root(fffcf9...).xprv", root.hex(), + "0031615bdf7906a19360f08029354d12eaaedc9046806aefd672e3b93b024e495a95ba63cf47903eb742cd1843a5252118f24c0c496e9213bd42de70f649a798") + verifyTestVector(t, "Root(fffcf9...).xpub", root.XPub().hex(), + "f153ef65bbfaec3c8fd4fceb0510529048094093cf7c14970013282973e117545a95ba63cf47903eb742cd1843a5252118f24c0c496e9213bd42de70f649a798") + + verifyTestVector(t, "Root(fffcf9...)/0(N).xprv", root.Child([]byte{0x00}, false).hex(), + "883e65e6e86499bdd170c14d67e62359dd020dd63056a75ff75983a682024e49e8cc52d8e74c5dfd75b0b326c8c97ca7397b7f954ad0b655b8848bfac666f09f") + verifyTestVector(t, "Root(fffcf9...)/0(N).xpub", root.Child([]byte{0x00}, false).XPub().hex(), + "f48b7e641d119b8ddeaf97aca104ee6e6a780ab550d40534005443550ef7e7d8e8cc52d8e74c5dfd75b0b326c8c97ca7397b7f954ad0b655b8848bfac666f09f") + verifyTestVector(t, "Root(fffcf9...)/0(N).xpub", root.XPub().Child([]byte{0x00}).hex(), + "f48b7e641d119b8ddeaf97aca104ee6e6a780ab550d40534005443550ef7e7d8e8cc52d8e74c5dfd75b0b326c8c97ca7397b7f954ad0b655b8848bfac666f09f") + + verifyTestVector(t, "Root(fffcf9...)/0(N)/2147483647(H).xprv", root.Child([]byte{0x00}, false).Child([]byte{0xff, 0xff, 0xff, 0x7f}, true).hex(), + "5048fa4498bf65e2b10d26e6c99cc43556ecfebf8b9fddf8bd2150ba29d63154044ef557a3aa4cb6ae8b61e87cb977a929bc4a170e4faafc2661231f5f3f78e8") + verifyTestVector(t, "Root(fffcf9...)/0(N)/2147483647(H).xpub", root.Child([]byte{0x00}, false).Child([]byte{0xff, 0xff, 0xff, 0x7f}, true).XPub().hex(), + "a8555c5ee5054ad03c6c6661968d66768fa081103bf576ea63a26c00ca7eab69044ef557a3aa4cb6ae8b61e87cb977a929bc4a170e4faafc2661231f5f3f78e8") + + verifyTestVector(t, "Root(fffcf9...)/0(N)/2147483647(H)/1(N).xprv", root.Child([]byte{0x00}, false).Child([]byte{0xff, 0xff, 0xff, 0x7f}, true).Child([]byte{0x01}, false).hex(), + "480f6aa25f7c9f4a569896f06614303a697f00ee8d240c6277605d44e0d63154174c386ad6ae01e54acd7bb422243c6055058f4231e250050134283a76de8eff") + verifyTestVector(t, "Root(fffcf9...)/0(N)/2147483647(H)/1(N).xpub", root.Child([]byte{0x00}, false).Child([]byte{0xff, 0xff, 0xff, 0x7f}, true).Child([]byte{0x01}, false).XPub().hex(), + "7385ab0b06eacc226c8035bab1ff9bc6972c7700d1caede26fe2b4d57b208bd0174c386ad6ae01e54acd7bb422243c6055058f4231e250050134283a76de8eff") + verifyTestVector(t, "Root(fffcf9...)/0(N)/2147483647(H)/1(N).xpub", root.Child([]byte{0x00}, false).Child([]byte{0xff, 0xff, 0xff, 0x7f}, true).XPub().Child([]byte{0x01}).hex(), + "7385ab0b06eacc226c8035bab1ff9bc6972c7700d1caede26fe2b4d57b208bd0174c386ad6ae01e54acd7bb422243c6055058f4231e250050134283a76de8eff") + + verifyTestVector(t, "Root(fffcf9...)/0(N)/2147483647(H)/1(N)/2147483646(H).xprv", root.Child([]byte{0x00}, false).Child([]byte{0xff, 0xff, 0xff, 0x7f}, true).Child([]byte{0x01}, false).Child([]byte{0xfe, 0xff, 0xff, 0x7f}, true).hex(), + "386014c6dfeb8dadf62f0e5acacfbf7965d5746c8b9011df155a31df7be0fb59986c923d979d89310acd82171dbaa7b73b20b2033ac6819d7f309212ff3fbabd") + verifyTestVector(t, "Root(fffcf9...)/0(N)/2147483647(H)/1(N)/2147483646(H).xpub", root.Child([]byte{0x00}, false).Child([]byte{0xff, 0xff, 0xff, 0x7f}, true).Child([]byte{0x01}, false).Child([]byte{0xfe, 0xff, 0xff, 0x7f}, true).XPub().hex(), + "9f66aa8019427a825dd72a13ce982454d99f221c8d4874db59f52c2945cbcabd986c923d979d89310acd82171dbaa7b73b20b2033ac6819d7f309212ff3fbabd") + + verifyTestVector(t, "Root(fffcf9...)/0(N)/2147483647(H)/1(N)/2147483646(H)/2(N).xprv", root.Child([]byte{0x00}, false).Child([]byte{0xff, 0xff, 0xff, 0x7f}, true).Child([]byte{0x01}, false).Child([]byte{0xfe, 0xff, 0xff, 0x7f}, true).Child([]byte{0x02}, false).hex(), + "08c3772f5c0eee42f40d00f4faff9e4c84e5db3c4e7f28ecb446945a1de1fb59ef9d0a352f3252ea673e8b6bd31ac97218e019e845bdc545c268cd52f7af3f5d") + verifyTestVector(t, "Root(fffcf9...)/0(N)/2147483647(H)/1(N)/2147483646(H)/2(N).xpub", root.Child([]byte{0x00}, false).Child([]byte{0xff, 0xff, 0xff, 0x7f}, true).Child([]byte{0x01}, false).Child([]byte{0xfe, 0xff, 0xff, 0x7f}, true).Child([]byte{0x02}, false).XPub().hex(), + "67388f59a7b62644c3c6148575770e56969d77244530263bc9659b8563d7ff81ef9d0a352f3252ea673e8b6bd31ac97218e019e845bdc545c268cd52f7af3f5d") + verifyTestVector(t, "Root(fffcf9...)/0(N)/2147483647(H)/1(N)/2147483646(H)/2(N).xpub", root.Child([]byte{0x00}, false).Child([]byte{0xff, 0xff, 0xff, 0x7f}, true).Child([]byte{0x01}, false).Child([]byte{0xfe, 0xff, 0xff, 0x7f}, true).XPub().Child([]byte{0x02}).hex(), + "67388f59a7b62644c3c6148575770e56969d77244530263bc9659b8563d7ff81ef9d0a352f3252ea673e8b6bd31ac97218e019e845bdc545c268cd52f7af3f5d") +} + +func TestExpandedPrivateKey(t *testing.T) { + root := RootXPrv([]byte{0xca, 0xfe}) + verifyTestVector(t, "Root(cafe).xprv", root.hex(), + "a0cde08fd2ea06e16dd5d21e64ca0609fa1d719b79fed4245a5b8ada0242464cebbc2b9e1e989aca72d9766efd9b63ebcfc968027ef27cb786babb7897f9248a") + verifyTestVector(t, "Root(cafe).xprv.expandedkey", root.ExpandedPrivateKey().hex(), + "a0cde08fd2ea06e16dd5d21e64ca0609fa1d719b79fed4245a5b8ada0242464c1437c8234e21e43eb9c79df0ce370dc82d4c7a952ef317e716b0762146bb61a0") + + child := root.Child([]byte{0xbe, 0xef}, false) + verifyTestVector(t, "Root(cafe)/beef.xprv", child.hex(), + "684df1aa25e0425c48c76392f42abc87a359ef2a2328ad31e53318128242464cf85916f4261b03f71afa64ad4bc2be4f335f15e433e815b45bbd15fcc7d1a864") + verifyTestVector(t, "Root(cafe)/beef.xprv.expandedkey", child.ExpandedPrivateKey().hex(), + "684df1aa25e0425c48c76392f42abc87a359ef2a2328ad31e53318128242464c0abdda57709eff7e9c60e0d4199065a6941122566c0a30ffa3ce0449d0582278") +} + func TestChildKeys(t *testing.T) { rootXPrv, err := NewXPrv(nil) if err != nil { @@ -85,26 +189,91 @@ func doverify(t *testing.T, xpub XPub, msg, sig []byte, xpubdesc, xprvdesc strin } for i := 0; i < 32; i++ { - xpub[i] ^= 0xff - if xpub.Verify(msg, sig) { - t.Fatalf("altered %s should not verify signature from %s", xpubdesc, xprvdesc) + for mask := byte(1); mask != 0; mask <<= 1 { + xpub[i] ^= mask + if xpub.Verify(msg, sig) { + t.Fatalf("altered %s should not verify signature from %s", xpubdesc, xprvdesc) + } + xpub[i] ^= mask } - xpub[i] ^= 0xff } - for i := 0; i < len(msg); i++ { - msg[i] ^= 0xff - if xpub.Verify(msg, sig) { - t.Fatalf("%s should not verify signature from %s against altered message", xpubdesc, xprvdesc) + // permute only 1/7th of the bits to make tests run faster + for i := 0; i < len(msg); i += 7 { + for mask := byte(1); mask != 0; mask <<= 1 { + msg[i] ^= mask + if xpub.Verify(msg, sig) { + t.Fatalf("%s should not verify signature from %s against altered message", xpubdesc, xprvdesc) + } + msg[i] ^= mask } - msg[i] ^= 0xff } for i := 0; i < len(sig); i++ { - sig[i] ^= 0xff - if xpub.Verify(msg, sig) { - t.Fatalf("%s should not verify altered signature from %s", xpubdesc, xprvdesc) + for mask := byte(1); mask != 0; mask <<= 1 { + sig[i] ^= mask + if xpub.Verify(msg, sig) { + t.Fatalf("%s should not verify altered signature from %s", xpubdesc, xprvdesc) + } + sig[i] ^= mask + } + } +} + +func verifyTestVector(t *testing.T, message string, got []byte, want string) { + if !bytes.Equal(got, []byte(want)) { + t.Errorf("ChainKD Test Vector: %s:\n got = %s\n want = %s", message, got, want) + } +} + +func (xpub XPub) hex() []byte { + s, _ := xpub.MarshalText() + return s +} + +func (xprv XPrv) hex() []byte { + s, _ := xprv.MarshalText() + return s +} + +func (key ExpandedPrivateKey) hex() []byte { + hexBytes := make([]byte, hex.EncodedLen(len(key[:]))) + hex.Encode(hexBytes, key[:]) + return hexBytes +} + +func TestBits(t *testing.T) { + for i := 0; i < 256; i++ { + root := RootXPrv([]byte{byte(i)}) + + rootbytes := root.Bytes() + if rootbytes[0]&7 != 0 { + t.Errorf("ChainKD root key must have low 3 bits set to '000'") + } + if (rootbytes[31] >> 5) != 2 { + t.Errorf("ChainKD root key must have high 3 bits set to '010'") + } + + xprv := root + for d := 0; d < 1000; d++ { // at least after 1000 levels necessary bits are survived + xprv = xprv.Child([]byte("child"), false) + xprvbytes := xprv.Bytes() + + if xprvbytes[0]&7 != 0 { + t.Errorf("ChainKD non-hardened child key must have low 3 bits set to '000'") + } + if xprvbytes[31]>>6 != 1 { + t.Errorf("ChainKD non-hardened child key must have high 2 bits set to '10' (LE)") + } + + hchild := xprv.Child([]byte("hardened child"), true) + hchildbytes := hchild.Bytes() + if hchildbytes[0]&7 != 0 { + t.Errorf("ChainKD hardened key must have low 3 bits set to '000'") + } + if (hchildbytes[31] >> 5) != 2 { + t.Errorf("ChainKD hardened key must have high 3 bits set to '010'") + } } - sig[i] ^= 0xff } } diff --git a/crypto/ed25519/chainkd/expanded_key.go b/crypto/ed25519/chainkd/expanded_key.go new file mode 100644 index 00000000..fbc5db13 --- /dev/null +++ b/crypto/ed25519/chainkd/expanded_key.go @@ -0,0 +1,102 @@ +// Package chainkd This is an extension to ed25519.Sign that is compatible with NaCl `crypto_sign` +// function taking 64-byte expanded private key (where the left part is a pre-multiplied +// scalar and the right part is "prefix" used for generating a nonce). +// +// Invariants: +// 1) Expanded(PrivateKey).Sign() == PrivateKey.Sign() +// 2) InnerSign(Expanded(PrivateKey)) == Sign(PrivateKey) +package chainkd + +import ( + "crypto" + "crypto/sha512" + "errors" + "io" + "strconv" + + "github.com/bytom/crypto/ed25519" + "github.com/bytom/crypto/ed25519/internal/edwards25519" +) + +const ( + // ExpandedPrivateKeySize is the size, in bytes, of a "secret key" as defined in NaCl. + ExpandedPrivateKeySize = 64 +) + +// ExpandedPrivateKey is the type of NaCl secret keys. It implements crypto.Signer. +type ExpandedPrivateKey []byte + +// Public returns the PublicKey corresponding to secret key. +func (priv ExpandedPrivateKey) Public() crypto.PublicKey { + var A edwards25519.ExtendedGroupElement + var scalar [32]byte + copy(scalar[:], priv[:32]) + edwards25519.GeScalarMultBase(&A, &scalar) + var publicKeyBytes [32]byte + A.ToBytes(&publicKeyBytes) + return ed25519.PublicKey(publicKeyBytes[:]) +} + +func expandEd25519PrivateKey(priv ed25519.PrivateKey) ExpandedPrivateKey { + digest := sha512.Sum512(priv[:32]) + digest[0] &= 248 + digest[31] &= 127 + digest[31] |= 64 + return ExpandedPrivateKey(digest[:]) +} + +// Sign signs the given message with expanded private key. +// Ed25519 performs two passes over messages to be signed and therefore cannot +// handle pre-hashed messages. Thus opts.HashFunc() must return zero to +// indicate the message hasn't been hashed. This can be achieved by passing +// crypto.Hash(0) as the value for opts. +func (priv ExpandedPrivateKey) Sign(rand io.Reader, message []byte, opts crypto.SignerOpts) (signature []byte, err error) { + if opts.HashFunc() != crypto.Hash(0) { + return nil, errors.New("ed25519: cannot sign hashed message") + } + + return Ed25519InnerSign(priv, message), nil +} + +// Ed25519InnerSign signs the message with expanded private key and returns a signature. +// It will panic if len(privateKey) is not ExpandedPrivateKeySize. +func Ed25519InnerSign(privateKey ExpandedPrivateKey, message []byte) []byte { + if l := len(privateKey); l != ExpandedPrivateKeySize { + panic("ed25519: bad private key length: " + strconv.Itoa(l)) + } + + var messageDigest, hramDigest [64]byte + + h := sha512.New() + h.Write(privateKey[32:]) + h.Write(message) + h.Sum(messageDigest[:0]) + + var messageDigestReduced [32]byte + edwards25519.ScReduce(&messageDigestReduced, &messageDigest) + var R edwards25519.ExtendedGroupElement + edwards25519.GeScalarMultBase(&R, &messageDigestReduced) + + var encodedR [32]byte + R.ToBytes(&encodedR) + + publicKey := privateKey.Public().(ed25519.PublicKey) + h.Reset() + h.Write(encodedR[:]) + h.Write(publicKey[:]) + h.Write(message) + h.Sum(hramDigest[:0]) + var hramDigestReduced [32]byte + edwards25519.ScReduce(&hramDigestReduced, &hramDigest) + + var sk [32]byte + copy(sk[:], privateKey[:32]) + var s [32]byte + edwards25519.ScMulAdd(&s, &hramDigestReduced, &sk, &messageDigestReduced) + + signature := make([]byte, ed25519.SignatureSize) + copy(signature[:], encodedR[:]) + copy(signature[32:], s[:]) + + return signature +} diff --git a/crypto/ed25519/chainkd/expanded_key_test.go b/crypto/ed25519/chainkd/expanded_key_test.go new file mode 100644 index 00000000..355ce1f5 --- /dev/null +++ b/crypto/ed25519/chainkd/expanded_key_test.go @@ -0,0 +1,97 @@ +package chainkd + +import ( + "bytes" + "crypto" + "testing" + + "github.com/bytom/crypto/ed25519" +) + +// Testing basic InnerSign+Verify and the invariants: +// 1) Expand(PrivateKey).Sign() == PrivateKey.Sign() +// 2) InnerSign(Expand(PrivateKey)) == Sign(PrivateKey) + +type zeroReader struct{} + +func (zeroReader) Read(buf []byte) (int, error) { + for i := range buf { + buf[i] = 0 + } + return len(buf), nil +} + +func TestInnerSignVerify(t *testing.T) { + var zero zeroReader + public, private, _ := ed25519.GenerateKey(zero) + expprivate := expandEd25519PrivateKey(private) + + message := []byte("test message") + sig := Ed25519InnerSign(expprivate, message) + if !ed25519.Verify(public, message, sig) { + t.Errorf("valid signature rejected") + } + + wrongMessage := []byte("wrong message") + if ed25519.Verify(public, wrongMessage, sig) { + t.Errorf("signature of different message accepted") + } +} + +func TestExpandedKeySignerInterfaceInvariant(t *testing.T) { + var zero zeroReader + public, private, _ := ed25519.GenerateKey(zero) + expprivate := expandEd25519PrivateKey(private) + + signer1 := crypto.Signer(private) + signer2 := crypto.Signer(expprivate) + + publicInterface1 := signer1.Public() + publicInterface2 := signer2.Public() + public1, ok := publicInterface1.(ed25519.PublicKey) + if !ok { + t.Fatalf("expected PublicKey from Public() but got %T", publicInterface1) + } + public2, ok := publicInterface2.(ed25519.PublicKey) + if !ok { + t.Fatalf("expected PublicKey from Public() but got %T", publicInterface2) + } + + if !bytes.Equal(public, public1) { + t.Errorf("public keys do not match: original:%x vs Public():%x", public, public1) + } + if !bytes.Equal(public, public2) { + t.Errorf("public keys do not match: original:%x vs Public():%x", public, public2) + } + + message := []byte("message") + var noHash crypto.Hash + signature1, err := signer1.Sign(zero, message, noHash) + if err != nil { + t.Fatalf("error from Sign(): %s", err) + } + signature2, err := signer2.Sign(zero, message, noHash) + if err != nil { + t.Fatalf("error from Sign(): %s", err) + } + if !bytes.Equal(signature1[:], signature2[:]) { + t.Errorf(".Sign() should return identical signatures for Signer(privkey) and Signer(Expand(privkey))") + } + if !ed25519.Verify(public, message, signature1) { + t.Errorf("Verify failed on signature from Sign()") + } +} + +func TestInnerSignInvariant(t *testing.T) { + var zero zeroReader + _, private, _ := ed25519.GenerateKey(zero) + expprivate := expandEd25519PrivateKey(private) + + message := []byte("test message") + sig1 := ed25519.Sign(private, message) + sig2 := Ed25519InnerSign(expprivate, message) + + if !bytes.Equal(sig1[:], sig2[:]) { + t.Errorf("InnerSign(Expand(privkey)) must return the same as Sign(privkey)") + } +} diff --git a/crypto/ed25519/chainkd/serialize_test.go b/crypto/ed25519/chainkd/serialize_test.go index f58dbf32..142549d4 100644 --- a/crypto/ed25519/chainkd/serialize_test.go +++ b/crypto/ed25519/chainkd/serialize_test.go @@ -2,11 +2,10 @@ package chainkd import ( "bytes" - "reflect" - "testing" - "encoding/hex" "encoding/json" + "reflect" + "testing" ) func TestMarshalingFuncs(t *testing.T) { -- 2.11.0