From 8d7bf2291b095d3a2ecaa2609e1101be46d80deb Mon Sep 17 00:00:00 2001 From: David Leon Gil Date: Tue, 6 Jan 2015 22:10:24 -0800 Subject: [PATCH] crypto/ecdsa: make Sign safe with broken entropy sources ECDSA is unsafe to use if an entropy source produces predictable output for the ephemeral nonces. E.g., [Nguyen]. A simple countermeasure is to hash the secret key, the message, and entropy together to seed a CSPRNG, from which the ephemeral key is derived. -- This is a minimalist (in terms of patch size) solution, though not the most parsimonious in its use of primitives: - csprng_key = ChopMD-256(SHA2-512(priv.D||entropy||hash)) - reader = AES-256-CTR(k=csprng_key) This, however, provides at most 128-bit collision-resistance, so that Adv will have a term related to the number of messages signed that is significantly worse than plain ECDSA. This does not seem to be of any practical importance. ChopMD-256(SHA2-512(x)) is used, rather than SHA2-256(x), for two sets of reasons: *Practical:* SHA2-512 has a larger state and 16 more rounds; it is likely non-generically stronger than SHA2-256. And, AFAIK, cryptanalysis backs this up. (E.g., [Biryukov] gives a distinguisher on 47-round SHA2-256 with cost < 2^85.) This is well below a reasonable security-strength target. *Theoretical:* [Coron] and [Chang] show that Chop-MD(F(x)) is indifferentiable from a random oracle for slightly beyond the birthday barrier. It seems likely that this makes a generic security proof that this construction remains UF-CMA is possible in the indifferentiability framework. -- Many thanks to Payman Mohassel for reviewing this construction; any mistakes are mine, however. And, as he notes, reusing the private key in this way means that the generic-group (non-RO) proof of ECDSA's security given in [Brown] no longer directly applies. -- [Brown]: http://www.cacr.math.uwaterloo.ca/techreports/2000/corr2000-54.ps "Brown. The exact security of ECDSA. 2000" [Coron]: https://www.cs.nyu.edu/~puniya/papers/merkle.pdf "Coron et al. Merkle-Damgard revisited. 2005" [Chang]: https://www.iacr.org/archive/fse2008/50860436/50860436.pdf "Chang and Nandi. Improved indifferentiability security analysis of chopMD hash function. 2008" [Biryukov]: http://www.iacr.org/archive/asiacrypt2011/70730269/70730269.pdf "Biryukov et al. Second-order differential collisions for reduced SHA-256. 2011" [Nguyen]: ftp://ftp.di.ens.fr/pub/users/pnguyen/PubECDSA.ps "Nguyen and Shparlinski. The insecurity of the elliptic curve digital signature algorithm with partially known nonces. 2003" Fixes #9452 Tests: TestNonceSafety: Check that signatures are safe even with a broken entropy source. TestINDCCA: Check that signatures remain non-deterministic with a functional entropy source. Change-Id: Ie7e04057a3a26e6becb80e845ecb5004bb482745 Reviewed-on: https://go-review.googlesource.com/2422 Reviewed-by: Adam Langley --- src/crypto/ecdsa/ecdsa.go | 59 +++++++++++++++++++++++++++- src/crypto/ecdsa/ecdsa_test.go | 72 ++++++++++++++++++++++++++++++++++ 2 files changed, 130 insertions(+), 1 deletion(-) diff --git a/src/crypto/ecdsa/ecdsa.go b/src/crypto/ecdsa/ecdsa.go index d6135531bf..59902014df 100644 --- a/src/crypto/ecdsa/ecdsa.go +++ b/src/crypto/ecdsa/ecdsa.go @@ -4,6 +4,10 @@ // Package ecdsa implements the Elliptic Curve Digital Signature Algorithm, as // defined in FIPS 186-3. +// +// This implementation derives the nonce from an AES-CTR CSPRNG keyed by +// ChopMD(256, SHA2-512(priv.D || entropy || hash)). The CSPRNG key is IRO by +// a result of Coron; the AES-CTR stream is IRO under standard assumptions. package ecdsa // References: @@ -14,12 +18,19 @@ package ecdsa import ( "crypto" + "crypto/aes" + "crypto/cipher" "crypto/elliptic" + "crypto/sha512" "encoding/asn1" "io" "math/big" ) +const ( + aesIV = "IV for ECDSA CTR" +) + // PublicKey represents an ECDSA public key. type PublicKey struct { elliptic.Curve @@ -123,6 +134,38 @@ func fermatInverse(k, N *big.Int) *big.Int { // pair of integers. The security of the private key depends on the entropy of // rand. func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) { + // Get max(log2(q) / 2, 256) bits of entropy from rand. + entropylen := (priv.Curve.Params().BitSize + 7) / 16 + if entropylen > 32 { + entropylen = 32 + } + entropy := make([]byte, entropylen) + _, err = rand.Read(entropy) + if err != nil { + return + } + + // Initialize an SHA-512 hash context; digest ... + md := sha512.New() + md.Write(priv.D.Bytes()) // the private key, + md.Write(entropy) // the entropy, + md.Write(hash) // and the input hash; + key := md.Sum(nil)[:32] // and compute ChopMD-256(SHA-512), + // which is an indifferentiable MAC. + + // Create an AES-CTR instance to use as a CSPRNG. + block, err := aes.NewCipher(key) + if err != nil { + return nil, nil, err + } + + // Create a CSPRNG that xors a stream of zeros with + // the output of the AES-CTR instance. + csprng := cipher.StreamReader{ + R: zeroReader, + S: cipher.NewCTR(block, []byte(aesIV)), + } + // See [NSA] 3.4.1 c := priv.PublicKey.Curve N := c.Params().N @@ -130,7 +173,7 @@ func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err err var k, kInv *big.Int for { for { - k, err = randFieldElement(c, rand) + k, err = randFieldElement(c, csprng) if err != nil { r = nil return @@ -187,3 +230,17 @@ func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool { x.Mod(x, N) return x.Cmp(r) == 0 } + +type zr struct { + io.Reader +} + +// Read replaces the contents of dst with zeros. +func (z *zr) Read(dst []byte) (n int, err error) { + for i := range dst { + dst[i] = 0 + } + return len(dst), nil +} + +var zeroReader = &zr{} diff --git a/src/crypto/ecdsa/ecdsa_test.go b/src/crypto/ecdsa/ecdsa_test.go index 0c06431932..169944dfb2 100644 --- a/src/crypto/ecdsa/ecdsa_test.go +++ b/src/crypto/ecdsa/ecdsa_test.go @@ -72,6 +72,78 @@ func TestSignAndVerify(t *testing.T) { testSignAndVerify(t, elliptic.P521(), "p521") } +func testNonceSafety(t *testing.T, c elliptic.Curve, tag string) { + priv, _ := GenerateKey(c, rand.Reader) + + hashed := []byte("testing") + r0, s0, err := Sign(zeroReader, priv, hashed) + if err != nil { + t.Errorf("%s: error signing: %s", tag, err) + return + } + + hashed = []byte("testing...") + r1, s1, err := Sign(zeroReader, priv, hashed) + if err != nil { + t.Errorf("%s: error signing: %s", tag, err) + return + } + + if s0.Cmp(s1) == 0 { + // This should never happen. + t.Errorf("%s: the signatures on two different messages were the same") + } + + if r0.Cmp(r1) == 0 { + t.Errorf("%s: the nonce used for two diferent messages was the same") + } +} + +func TestNonceSafety(t *testing.T) { + testNonceSafety(t, elliptic.P224(), "p224") + if testing.Short() { + return + } + testNonceSafety(t, elliptic.P256(), "p256") + testNonceSafety(t, elliptic.P384(), "p384") + testNonceSafety(t, elliptic.P521(), "p521") +} + +func testINDCCA(t *testing.T, c elliptic.Curve, tag string) { + priv, _ := GenerateKey(c, rand.Reader) + + hashed := []byte("testing") + r0, s0, err := Sign(rand.Reader, priv, hashed) + if err != nil { + t.Errorf("%s: error signing: %s", tag, err) + return + } + + r1, s1, err := Sign(rand.Reader, priv, hashed) + if err != nil { + t.Errorf("%s: error signing: %s", tag, err) + return + } + + if s0.Cmp(s1) == 0 { + t.Errorf("%s: two signatures of the same message produced the same result") + } + + if r0.Cmp(r1) == 0 { + t.Errorf("%s: two signatures of the same message produced the same nonce") + } +} + +func TestINDCCA(t *testing.T) { + testINDCCA(t, elliptic.P224(), "p224") + if testing.Short() { + return + } + testINDCCA(t, elliptic.P256(), "p256") + testINDCCA(t, elliptic.P384(), "p384") + testINDCCA(t, elliptic.P521(), "p521") +} + func fromHex(s string) *big.Int { r, ok := new(big.Int).SetString(s, 16) if !ok { -- 2.50.0