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>

1 files changed, 24 insertions, 24 deletions

diff --git a/src/crypto/tls/testdata/Client-TLSv10-ClientCert-ECDSA-RSA b/src/crypto/tls/testdata/Client-TLSv10-ClientCert-ECDSA-RSA
index c0be82491e..72ac3483f2 100644
--- a/src/crypto/tls/testdata/Client-TLSv10-ClientCert-ECDSA-RSA
+++ b/src/crypto/tls/testdata/Client-TLSv10-ClientCert-ECDSA-RSA
@@ -8,11 +8,11 @@
 00000060  19 00 0b 00 02 01 00 00  0d 00 0a 00 08 04 01 04  |................|
 00000070  03 02 01 02 03 ff 01 00  01 00                    |..........|
 >>> Flow 2 (server to client)
-00000000  16 03 01 00 51 02 00 00  4d 03 01 53 04 f1 02 ed  |....Q...M..S....|
-00000010  86 9c 56 84 5a d3 7d d7  f3 4e 6f 2c 69 0d f0 59  |..V.Z.}..No,i..Y|
-00000020  a5 d1 de 2d 03 2f dd 63  c3 ab fa 20 30 d6 5a 24  |...-./.c... 0.Z$|
-00000030  5c 31 67 36 8d 4c 43 e1  64 c4 8a 2c a5 fd 39 92  |\1g6.LC.d..,..9.|
-00000040  c5 6f 58 47 a3 fe 63 14  98 92 11 90 00 05 00 00  |.oXG..c.........|
+00000000  16 03 01 00 51 02 00 00  4d 03 01 37 70 df cf 32  |....Q...M..7p..2|
+00000010  30 86 74 72 84 3a 67 1d  80 2b 28 6b 8f 8a 9c 4a  |0.tr.:g..+(k...J|
+00000020  75 05 aa 5f d5 c7 f1 e0  3f c8 88 20 fa 17 d2 a8  |u.._....?.. ....|
+00000030  5e 03 39 fa ec 72 97 10  44 80 4e 21 3d 4a 06 f2  |^.9..r..D.N!=J..|
+00000040  df db 6f 18 ad 4e 83 89  95 97 65 b4 00 05 00 00  |..o..N....e.....|
 00000050  05 ff 01 00 01 00 16 03  01 02 be 0b 00 02 ba 00  |................|
 00000060  02 b7 00 02 b4 30 82 02  b0 30 82 02 19 a0 03 02  |.....0...0......|
 00000070  01 02 02 09 00 85 b0 bb  a4 8a 7f b8 ca 30 0d 06  |.............0..|
@@ -102,24 +102,24 @@
 00000270  bd 77 82 6f 23 b6 e0 bd  a2 92 b7 3a ac e8 56 f1  |.w.o#......:..V.|
 00000280  af 54 5e 46 87 e9 3b 33  e7 b8 28 b7 d6 c8 90 35  |.T^F..;3..(....5|
 00000290  d4 1c 43 d1 30 6f 55 4e  0a 70 16 03 01 00 90 0f  |..C.0oUN.p......|
-000002a0  00 00 8c 00 8a 30 81 87  02 42 00 c6 85 8e 06 b7  |.....0...B......|
-000002b0  04 04 e9 cd 9e 3e cb 66  23 95 b4 42 9c 64 81 39  |.....>.f#..B.d.9|
-000002c0  05 3f b5 21 f8 28 af 60  6b 4d 3d ba a1 4b 5e 77  |.?.!.(.`kM=..K^w|
-000002d0  ef e7 59 28 fe 1d c1 27  a2 ff a8 de 33 48 b3 c1  |..Y(...'....3H..|
-000002e0  85 6a 42 9b f9 7e 7e 31  c2 e5 bd 66 02 41 4b 49  |.jB..~~1...f.AKI|
-000002f0  c6 cd 02 e3 83 f7 03 50  18 6d b4 c9 51 02 c0 ab  |.......P.m..Q...|
-00000300  87 bc e0 3e 4b 89 53 3a  e2 65 89 97 02 c1 87 f1  |...>K.S:.e......|
-00000310  67 d0 f2 06 28 4e 51 4e  fd f0 01 47 e7 c9 d9 23  |g...(NQN...G...#|
-00000320  21 6b 87 d2 55 e3 c9 f7  eb 86 d5 1e 50 df d5 14  |!k..U.......P...|
-00000330  03 01 00 01 01 16 03 01  00 24 95 62 42 be 90 39  |.........$.bB..9|
-00000340  68 ae f5 77 47 21 14 b9  ac ee 81 2d e3 9e c7 34  |h..wG!.....-...4|
-00000350  3a 00 5c c9 12 1d c0 5a  7c e7 ef e0 cd fd        |:.\....Z|.....|
+000002a0  00 00 8c 00 8a 30 81 87  02 41 09 05 9e 47 eb 66  |.....0...A...G.f|
+000002b0  56 d3 af a6 76 c1 b1 69  5c 13 b0 99 e2 e3 4a 69  |V...v..i\.....Ji|
+000002c0  53 68 a3 5e 44 b0 83 35  f7 40 e9 57 76 98 33 b2  |Sh.^D..5.@.Wv.3.|
+000002d0  ea c4 8b 53 09 b5 97 db  f1 03 fa 07 50 0a 59 74  |...S........P.Yt|
+000002e0  5f 8b f3 3a 1b 8b 7b 09  f2 89 06 02 42 01 4b f4  |_..:..{.....B.K.|
+000002f0  7d aa 99 7b 84 93 c6 7e  a6 2b f7 45 5c c2 4a 29  |}..{...~.+.E\.J)|
+00000300  dc 14 ba 7d 6a 65 9a 0b  59 c2 e7 ab 98 ef 3e 35  |...}je..Y.....>5|
+00000310  26 3d 9a 13 12 51 05 1e  3d da 61 bd 94 b5 9c d2  |&=...Q..=.a.....|
+00000320  0a 28 fe a9 e8 13 3a 87  05 f7 c3 9d f7 56 34 14  |.(....:......V4.|
+00000330  03 01 00 01 01 16 03 01  00 24 55 21 ec 93 1d b2  |.........$U!....|
+00000340  94 4c 4f 45 fd bf f6 88  cd b8 56 ab 11 89 29 13  |.LOE......V...).|
+00000350  9d b1 ad 15 e5 cd b0 8f  4c c3 d3 b8 83 7f        |........L.....|
 >>> Flow 4 (server to client)
-00000000  14 03 01 00 01 01 16 03  01 00 24 ea 98 c0 fb 86  |..........$.....|
-00000010  87 7a 2e e1 c7 68 61 3e  5b cc da 1f d6 7b ab 5a  |.z...ha>[....{.Z|
-00000020  a0 ae a2 cf d0 54 44 19  12 db 75 2b 8c 73 8c     |.....TD...u+.s.|
+00000000  14 03 01 00 01 01 16 03  01 00 24 c7 91 2b 7c dd  |..........$..+|.|
+00000010  13 54 63 81 97 73 03 37  25 ea e1 be 46 a8 37 61  |.Tc..s.7%...F.7a|
+00000020  d5 d0 0f 4f c0 d4 22 b2  be c6 c9 ce ed d7 a6     |...O.."........|
 >>> Flow 5 (client to server)
-00000000  17 03 01 00 1a f3 28 77  31 33 4c b3 7c 4b 75 61  |......(w13L.|Kua|
-00000010  38 69 6b ae c9 36 ab 2e  56 16 29 6a 9a 00 2f 15  |8ik..6..V.)j../.|
-00000020  03 01 00 16 6b ed 68 18  ed ff 44 39 9b 4a e4 a2  |....k.h...D9.J..|
-00000030  cd 79 ef 2a 3e 5a 4d b1  5d 56                    |.y.*>ZM.]V|
+00000000  17 03 01 00 1a f1 4d d5  14 0e 04 b4 31 a3 df dc  |......M.....1...|
+00000010  51 8d 65 33 37 55 31 05  b8 c5 48 c8 0b 18 3b 15  |Q.e37U1...H...;.|
+00000020  03 01 00 16 68 d0 cc 05  4d 85 dd df 6c d6 8d e0  |....h...M...l...|
+00000030  2c df c1 e8 09 8c 61 a1  a2 56                    |,.....a..V|