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, 27 insertions, 27 deletions

diff --git a/src/crypto/tls/testdata/Client-TLSv12-ClientCert-ECDSA-RSA b/src/crypto/tls/testdata/Client-TLSv12-ClientCert-ECDSA-RSA
index c3b753a7b4..9f256dfb4e 100644
--- a/src/crypto/tls/testdata/Client-TLSv12-ClientCert-ECDSA-RSA
+++ b/src/crypto/tls/testdata/Client-TLSv12-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 03 00 51 02 00 00  4d 03 03 53 04 f1 03 b0  |....Q...M..S....|
-00000010  43 00 97 24 a7 a8 ea b2  24 fe 96 24 a1 49 64 fd  |C..$....$..$.Id.|
-00000020  1c a3 30 35 2d 85 a7 40  42 86 6b 20 af 27 7f ac  |..05-..@B.k .'..|
-00000030  8b 16 89 6c 78 b7 f5 29  02 58 a6 8b 61 43 c2 b0  |...lx..).X..aC..|
-00000040  e0 a8 96 c8 fa 2b 26 ad  9a 5f 2d d6 00 05 00 00  |.....+&.._-.....|
+00000000  16 03 03 00 51 02 00 00  4d 03 03 53 3c e9 55 d3  |....Q...M..S<.U.|
+00000010  d6 ca 67 15 87 73 2e ce  4e d9 ed 6e 1c 57 e9 06  |..g..s..N..n.W..|
+00000020  3c 25 cf 2f 3b ea 6c 46  b8 21 3b 20 82 69 56 30  |<%./;.lF.!; .iV0|
+00000030  47 b1 d3 d3 25 24 79 d7  0a 23 8a 83 15 62 47 11  |G...%$y..#...bG.|
+00000040  21 3e fb c8 fc 8b 2b 53  4c 85 a0 6d 00 05 00 00  |!>....+SL..m....|
 00000050  05 ff 01 00 01 00 16 03  03 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..|
@@ -57,10 +57,10 @@
 000002e0  50 56 5c d5 82 5a 2d 5a  5f 33 c4 b6 d8 c9 75 90  |PV\..Z-Z_3....u.|
 000002f0  96 8c 0f 52 98 b5 cd 98  1f 89 20 5f f2 a0 1c a3  |...R...... _....|
 00000300  1b 96 94 dd a9 fd 57 e9  70 e8 26 6d 71 99 9b 26  |......W.p.&mq..&|
-00000310  6e 38 50 29 6c 90 a7 bd  d9 16 03 03 00 30 0d 00  |n8P)l........0..|
-00000320  00 28 03 01 02 40 00 20  06 01 06 02 06 03 05 01  |.(...@. ........|
+00000310  6e 38 50 29 6c 90 a7 bd  d9 16 03 03 00 2e 0d 00  |n8P)l...........|
+00000320  00 26 03 01 02 40 00 1e  06 01 06 02 06 03 05 01  |.&...@..........|
 00000330  05 02 05 03 04 01 04 02  04 03 03 01 03 02 03 03  |................|
-00000340  02 01 02 02 02 03 01 01  00 00 0e 00 00 00        |..............|
+00000340  02 01 02 02 02 03 00 00  0e 00 00 00              |............|
 >>> Flow 3 (client to server)
 00000000  16 03 03 02 0a 0b 00 02  06 00 02 03 00 02 00 30  |...............0|
 00000010  82 01 fc 30 82 01 5e 02  09 00 9a 30 84 6c 26 35  |...0..^....0.l&5|
@@ -104,24 +104,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 03 00 92 0f  |..C.0oUN.p......|
-000002a0  00 00 8e 04 03 00 8a 30  81 87 02 42 00 c6 85 8e  |.......0...B....|
-000002b0  06 b7 04 04 e9 cd 9e 3e  cb 66 23 95 b4 42 9c 64  |.......>.f#..B.d|
-000002c0  81 39 05 3f b5 21 f8 28  af 60 6b 4d 3d ba a1 4b  |.9.?.!.(.`kM=..K|
-000002d0  5e 77 ef e7 59 28 fe 1d  c1 27 a2 ff a8 de 33 48  |^w..Y(...'....3H|
-000002e0  b3 c1 85 6a 42 9b f9 7e  7e 31 c2 e5 bd 66 02 41  |...jB..~~1...f.A|
-000002f0  4b 49 c6 cd 02 e3 83 f7  03 50 18 6d b4 c9 51 02  |KI.......P.m..Q.|
-00000300  c0 ab 87 bc e0 3e 4b 89  53 3a e2 65 89 97 02 c1  |.....>K.S:.e....|
-00000310  88 5a 97 82 3e 55 6b 7c  d8 db b8 cc 1b 30 84 0a  |.Z..>Uk|.....0..|
-00000320  7a 97 71 e4 10 bb a4 39  8c 2a cf f5 88 c7 d1 95  |z.q....9.*......|
-00000330  73 14 03 03 00 01 01 16  03 03 00 24 9f 1e f0 72  |s..........$...r|
-00000340  92 ea dc f7 56 96 37 e4  69 db db 66 1d f6 94 c4  |....V.7.i..f....|
-00000350  18 31 4f d0 5d c5 f4 53  21 aa 98 b1 dc 08 94 94  |.1O.]..S!.......|
+000002a0  00 00 8e 04 03 00 8a 30  81 87 02 42 00 c9 8f 2e  |.......0...B....|
+000002b0  7e e1 ad 16 94 04 6a 18  8e 45 64 7c 94 b6 02 45  |~.....j..Ed|...E|
+000002c0  a3 c7 7e 01 75 76 f7 ad  9b 10 92 75 6a a1 e3 79  |..~.uv.....uj..y|
+000002d0  45 45 95 cf 43 6e 8e ab  c5 5f b1 1e 89 68 c2 f5  |EE..Cn..._...h..|
+000002e0  c9 91 d1 3c ee d0 ec 9c  d3 a8 a2 85 80 57 02 41  |...<.........W.A|
+000002f0  4e db f6 cd 9e 4e 7d 39  90 5a 86 72 c2 a8 0c 7d  |N....N}9.Z.r...}|
+00000300  1c 12 f8 01 7e d9 43 16  78 bc 42 69 80 6c 1c 56  |....~.C.x.Bi.l.V|
+00000310  5b 73 d8 d7 3b 6f e5 c8  a4 95 b3 22 23 06 77 b2  |[s..;o....."#.w.|
+00000320  1f d9 1a 6c 54 c4 aa 2f  7d 9c f4 76 59 e7 38 a9  |...lT../}..vY.8.|
+00000330  17 14 03 03 00 01 01 16  03 03 00 24 e6 f8 e2 9f  |...........$....|
+00000340  4f de 95 2d b1 80 4a e1  30 09 d2 61 c0 9a b7 47  |O..-..J.0..a...G|
+00000350  2d 84 76 48 b8 79 1a 53  1e 1b 74 34 55 ad 1a 43  |-.vH.y.S..t4U..C|
 >>> Flow 4 (server to client)
-00000000  14 03 03 00 01 01 16 03  03 00 24 ee 68 c1 87 9f  |..........$.h...|
-00000010  d7 90 94 f1 3b 6d 26 0b  3d 89 7a 45 3b 52 5d 3c  |....;m&.=.zE;R]<|
-00000020  dd 7c c1 4e 57 3e a9 ee  91 be cf 2b a3 98 9d     |.|.NW>.....+...|
+00000000  14 03 03 00 01 01 16 03  03 00 24 50 bf 00 cb 22  |..........$P..."|
+00000010  bd 18 5e fd 71 66 84 74  b0 76 8d 68 3c 8e ef 81  |..^.qf.t.v.h<...|
+00000020  ba 0b d7 c8 03 7b ec 2a  69 f7 64 b8 fc 3b 37     |.....{.*i.d..;7|
 >>> Flow 5 (client to server)
-00000000  17 03 03 00 1a 88 33 3e  2b 22 6b 92 d0 bb 8a 1e  |......3>+"k.....|
-00000010  9b f4 9e aa 91 8b 2b 95  ea 53 c8 03 0a 93 58 15  |......+..S....X.|
-00000020  03 03 00 16 c4 67 79 ba  ec cf 90 b1 f9 ac ec 64  |.....gy........d|
-00000030  72 01 08 8f 3a 98 aa 66  25 00                    |r...:..f%.|
+00000000  17 03 03 00 1a ad 19 93  3a 97 fc 8b 23 a6 ab 05  |........:...#...|
+00000010  5f ec 46 09 ce a9 a8 d8  41 c8 b6 71 0d 3b 67 15  |_.F.....A..q.;g.|
+00000020  03 03 00 16 5e 0b 29 64  37 aa be 0e 5e 3f f0 a3  |....^.)d7...^?..|
+00000030  fd 3a 82 91 a8 a2 98 ed  03 05                    |.:........|