diff options
author | David Leon Gil <coruus@gmail.com> | 2015-01-26 23:00:21 -0800 |
---|---|---|
committer | Adam Langley <agl@golang.org> | 2015-01-28 01:39:51 +0000 |
commit | a8049f58f9e3336554da1b0a4f8ea3b9c5cd669c (patch) | |
tree | 3aa6eb1a7d11fa1226145f9d147515d3d3dd8b12 /src/crypto/ecdsa/ecdsa.go | |
parent | f4a2617765273add97fb52c101baaf071fdb9705 (diff) | |
download | go-a8049f58f9e3336554da1b0a4f8ea3b9c5cd669c.tar.gz go-a8049f58f9e3336554da1b0a4f8ea3b9c5cd669c.zip |
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.
Fixes #9452
--
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"
New 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.
Updated "golden" KATs in crypto/tls/testdata that use ECDSA suites.
Change-Id: I55337a2fbec2e42a36ce719bd2184793682d678a
Reviewed-on: https://go-review.googlesource.com/3340
Reviewed-by: Adam Langley <agl@golang.org>
Diffstat (limited to 'src/crypto/ecdsa/ecdsa.go')
-rw-r--r-- | src/crypto/ecdsa/ecdsa.go | 59 |
1 files changed, 58 insertions, 1 deletions
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{} |