Fixes #9693

Change-Id: Ibf07199729bfc883b2a7e051cafd98185f912acd
Reviewed-on: https://go-review.googlesource.com/3283Reviewed-by: Russ Cox <rsc@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Using a mutex to protect a single int operation is quite heavyweight.
Using sync/atomic provides much better performance. This change was
benchmarked as such:

BenchmarkSync   10000000       139 ns/op
BenchmarkAtomic 200000000      9.90 ns/op

package blah

import (
        "sync"
        "sync/atomic"
        "testing"
)

type Int struct {
        mu sync.RWMutex
        i  int64
}

func (v *Int) Add(delta int64) {
        v.mu.Lock()
        defer v.mu.Unlock()
        v.i += delta
}

type AtomicInt struct {
        i int64
}

func (v *AtomicInt) Add(delta int64) {
        atomic.AddInt64(&v.i, delta)
}

func BenchmarkSync(b *testing.B) {
        s := new(Int)

        for i := 0; i < b.N; i++ {
                s.Add(1)
        }
}

func BenchmarkAtomic(b *testing.B) {
        s := new(AtomicInt)

        for i := 0; i < b.N; i++ {
                s.Add(1)
        }
}

Change-Id: I6998239c785967647351bbfe8533c38e4894543b
Reviewed-on: https://go-review.googlesource.com/3430Reviewed-by: Dmitry Vyukov <dvyukov@google.com>

This patch was previously sent for review using hg:
golang.org/cl/173930043

Change-Id: I559a2f2ee07990d0c23d2580381e32f8e23077a5
Reviewed-on: https://go-review.googlesource.com/3033Reviewed-by: Ian Lance Taylor <iant@golang.org>

Also:
- use io.ByteScanner rather than io.RuneScanner internally
- minor simplifications in Float.Add/Sub

Change-Id: Iae0e99384128dba9eccf68592c4fd389e2bd3b4f
Reviewed-on: https://go-review.googlesource.com/3380Reviewed-by: Rob Pike <r@golang.org>

Set the minimum heap size to 4Mbytes except when the hash
table code wants to force a GC. In an unrelated change when a
mutator is asked to assist the GC by marking pointer workbufs
it will keep working until the requested number of pointers
are processed even if it means asking for additional workbufs.

Change-Id: I661cfc0a7f2efcf6286b5d37d73e593d9ecd04d5
Reviewed-on: https://go-review.googlesource.com/3392Reviewed-by: Russ Cox <rsc@golang.org>
Reviewed-by: Austin Clements <austin@google.com>

If result of string(i) does not escape,
allocate a [4]byte temp on stack for it.

Change-Id: If31ce9447982929d5b3b963fd0830efae4247c37
Reviewed-on: https://go-review.googlesource.com/3411Reviewed-by: Russ Cox <rsc@golang.org>

Currently we always allocate string buffers in heap.
For example, in the following code we allocate a temp string
just for comparison:

	if string(byteSlice) == "abc" { ... }

This change extends escape analysis to cover []byte->string
conversions and string concatenation. If the result of operations
does not escape, compiler allocates a small buffer
on stack and passes it to slicebytetostring and concatstrings.
Then runtime uses the buffer if the result fits into it.

Size of the buffer is 32 bytes. There is no fundamental theory
behind this number. Just an observation that on std lib
tests/benchmarks frequency of string allocation is inversely
proportional to string length; and there is significant number
of allocations up to length 32.

benchmark                                    old allocs     new allocs     delta
BenchmarkFprintfBytes                        2              1              -50.00%
BenchmarkDecodeComplex128Slice               318            316            -0.63%
BenchmarkDecodeFloat64Slice                  318            316            -0.63%
BenchmarkDecodeInt32Slice                    318            316            -0.63%
BenchmarkDecodeStringSlice                   2318           2316           -0.09%
BenchmarkStripTags                           11             5              -54.55%
BenchmarkDecodeGray                          111            102            -8.11%
BenchmarkDecodeNRGBAGradient                 200            188            -6.00%
BenchmarkDecodeNRGBAOpaque                   165            152            -7.88%
BenchmarkDecodePaletted                      319            309            -3.13%
BenchmarkDecodeRGB                           166            157            -5.42%
BenchmarkDecodeInterlacing                   279            268            -3.94%
BenchmarkGoLookupIP                          153            135            -11.76%
BenchmarkGoLookupIPNoSuchHost                508            466            -8.27%
BenchmarkGoLookupIPWithBrokenNameServer      245            226            -7.76%
BenchmarkClientServerParallel4               62             61             -1.61%
BenchmarkClientServerParallel64              62             61             -1.61%
BenchmarkClientServerParallelTLS4            79             78             -1.27%
BenchmarkClientServerParallelTLS64           112            111            -0.89%

benchmark                                    old ns/op      new ns/op      delta
BenchmarkFprintfBytes                        381            311            -18.37%
BenchmarkStripTags                           2615           2351           -10.10%
BenchmarkDecodeNRGBAGradient                 3715887        3635096        -2.17%
BenchmarkDecodeNRGBAOpaque                   3047645        2928644        -3.90%
BenchmarkGoLookupIP                          153            135            -11.76%
BenchmarkGoLookupIPNoSuchHost                508            466            -8.27%

Change-Id: I9ec01da816945c3329d7be3c7794b520418c3f99
Reviewed-on: https://go-review.googlesource.com/3120Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>

During a concurrent GC stacks are scanned in
an initial scan phase informing the GC of all
pointers on the stack. The GC only needs to rescan
the stack if it potentially changes which can only
happen if the goroutine runs.
This CL tracks whether the Goroutine has run
since it was last scanned and thus may have changed
its stack. If necessary the stack is rescanned.

Change-Id: I5fb1c4338d42e3f61ab56c9beb63b7b2da25f4f1
Reviewed-on: https://go-review.googlesource.com/3275Reviewed-by: Russ Cox <rsc@golang.org>

Change-Id: I369723c7a65f9a72c60b55704cebf40d78cf4f75
Reviewed-on: https://go-review.googlesource.com/3444Reviewed-by: Alan Donovan <adonovan@google.com>

This should fix the race builders.

Change-Id: I9c9e7393d5e29d64ab797e346b34b1fa1dfe6d96
Reviewed-on: https://go-review.googlesource.com/3441Reviewed-by: Dmitry Vyukov <dvyukov@google.com>

net/http/pprof part of tracing functionality:
https://docs.google.com/document/u/1/d/1FP5apqzBgr7ahCCgFO-yoVhk4YZrNIDNf9RybngBc14/pub
Full change:
https://codereview.appspot.com/146920043

Change-Id: I9092028fcbd5e8f97a56f2c155889ccdfb494afb
Reviewed-on: https://go-review.googlesource.com/1453Reviewed-by: Russ Cox <rsc@golang.org>

Currently we allocate a new string during []byte->string conversion
in string comparison expressions. String allocation is unnecessary in
this case, because comparison does memorize the strings for later use.
This change uses slicebytetostringtmp to construct temp string directly
from []byte buffer and passes it to runtime.eqstring.

Change-Id: If00f1faaee2076baa6f6724d245d5b5e0f59b563
Reviewed-on: https://go-review.googlesource.com/3410Reviewed-by: Russ Cox <rsc@golang.org>

Coarse-grained test skips to fix bots.
Need to look closer at windows and nacl failures.

Change-Id: I767ef1707232918636b33f715459ee3c0349b45e
Reviewed-on: https://go-review.googlesource.com/3416Reviewed-by: Aram Hăvărneanu <aram@mgk.ro>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Escape analysis treats everything assigned to OIND/ODOTPTR as escaping.
As the result b escapes in the following code:

	func (b *Buffer) Foo() {
		n, m := ...
		b.buf = b.buf[n:m]
	}

This change recognizes such assignments and ignores them.

Update issue #9043.
Update issue #7921.

There are two similar cases in std lib that benefit from this optimization.
First is in archive/zip:

type readBuf []byte
func (b *readBuf) uint32() uint32 {
	v := binary.LittleEndian.Uint32(*b)
	*b = (*b)[4:]
	return v
}

Second is in time:

type data struct {
	p     []byte
	error bool
}

func (d *data) read(n int) []byte {
	if len(d.p) < n {
		d.p = nil
		d.error = true
		return nil
	}
	p := d.p[0:n]
	d.p = d.p[n:]
	return p
}

benchmark                         old ns/op     new ns/op     delta
BenchmarkCompressedZipGarbage     32431724      32217851      -0.66%

benchmark                         old allocs     new allocs     delta
BenchmarkCompressedZipGarbage     153            143            -6.54%

Change-Id: Ia6cd32744e02e36d6d8c19f402f8451101711626
Reviewed-on: https://go-review.googlesource.com/3162Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>

Currently all PTRLIT element initializers escape. There is no reason for that.
This change links STRUCTLIT to PTRLIT; STRUCTLIT element initializers are
already linked to the STRUCTLIT. As the result, PTRLIT element initializers
escape when PTRLIT itself escapes.

Change-Id: I89ecd8677cbf81addcfd469cd2fd461c0e9bf7dd
Reviewed-on: https://go-review.googlesource.com/3031Reviewed-by: Russ Cox <rsc@golang.org>

Change-Id: I832a433f0f2fc10b0a2fea0bfb003a988fc2c81b
Reviewed-on: https://go-review.googlesource.com/2039Reviewed-by: Russ Cox <rsc@golang.org>

cmd/go part of tracing functionality:
https://docs.google.com/document/u/1/d/1FP5apqzBgr7ahCCgFO-yoVhk4YZrNIDNf9RybngBc14/pub
Full change:
https://codereview.appspot.com/146920043

Change-Id: If346e11b8029c475b01fbf7172ce1c88171fb1b2
Reviewed-on: https://go-review.googlesource.com/1460Reviewed-by: Russ Cox <rsc@golang.org>

testing part of tracing functionality:
https://docs.google.com/document/u/1/d/1FP5apqzBgr7ahCCgFO-yoVhk4YZrNIDNf9RybngBc14/pub
Full change:
https://codereview.appspot.com/146920043

Change-Id: Ia3c2c4417106937d5775b0e7064db92c1fc36679
Reviewed-on: https://go-review.googlesource.com/1461Reviewed-by: Russ Cox <rsc@golang.org>

runtime/pprof part of tracing functionality:
https://docs.google.com/document/u/1/d/1FP5apqzBgr7ahCCgFO-yoVhk4YZrNIDNf9RybngBc14/pub
Full change:
https://codereview.appspot.com/146920043

Change-Id: I3143a569cbd33576f19ca47308d1ff5200d8c955
Reviewed-on: https://go-review.googlesource.com/1452Reviewed-by: Russ Cox <rsc@golang.org>

Add actual tracing of interesting runtime events.
Part of a larger tracing functionality:
https://docs.google.com/document/u/1/d/1FP5apqzBgr7ahCCgFO-yoVhk4YZrNIDNf9RybngBc14/pub
Full change:
https://codereview.appspot.com/146920043

Change-Id: Icccf54aea54e09350bb698ba6bf11532f9fbe6d3
Reviewed-on: https://go-review.googlesource.com/1451Reviewed-by: Russ Cox <rsc@golang.org>

This is first patch of series of patches that implement tracing functionality.
Design doc:
https://docs.google.com/document/u/1/d/1FP5apqzBgr7ahCCgFO-yoVhk4YZrNIDNf9RybngBc14/pub
Full change:
https://codereview.appspot.com/146920043

Change-Id: I84588348bb05a6f6a102c230f3bca6380a3419fe
Reviewed-on: https://go-review.googlesource.com/1450Reviewed-by: Russ Cox <rsc@golang.org>

For some reason the current conditions require the type to be "uintptr-shaped".
This cuts off structs and arrays with a pointer.
isdirectiface and width==widthptr is sufficient condition to enable the fast paths.

Change-Id: I11842531e7941365413606cfd6c34c202aa14786
Reviewed-on: https://go-review.googlesource.com/3414Reviewed-by: Russ Cox <rsc@golang.org>

Fixes #9691.

Change-Id: I22bfc82e05497e91a7b18a668913aed6c723365d
Reviewed-on: https://go-review.googlesource.com/3282Reviewed-by: Russ Cox <rsc@golang.org>

Race builders report goroutine leaks after addition of this benchmark:
http://build.golang.org/log/18e47f4cbc18ee8db125e1f1157573dd1e333c41
Close idle connection in default transport.

Change-Id: I86ff7b2e0972ed47c5ebcb9fce19e7f39d3ff530
Reviewed-on: https://go-review.googlesource.com/3412Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Call frame allocations can account for significant portion
of all allocations in a program, if call is executed
in an inner loop (e.g. to process every line in a log).
On the other hand, the allocation is easy to remove
using sync.Pool since the allocation is strictly scoped.

benchmark           old ns/op     new ns/op     delta
BenchmarkCall       634           338           -46.69%
BenchmarkCall-4     496           167           -66.33%

benchmark           old allocs     new allocs     delta
BenchmarkCall       1              0              -100.00%
BenchmarkCall-4     1              0              -100.00%

Update #7818

Change-Id: Icf60cce0a9be82e6171f0c0bd80dee2393db54a7
Reviewed-on: https://go-review.googlesource.com/1954Reviewed-by: Keith Randall <khr@golang.org>

This change extends existing test case to Windows for helping to fix
golang.org/issue/5395.

Change-Id: Iff077fa98ede511981df513f48d84c19375b3e04
Reviewed-on: https://go-review.googlesource.com/3304Reviewed-by: Alex Brainman <alex.brainman@gmail.com>

Pointers change from run to run, making it hard to use
the debug output to identify the reason for a changed
object file.

Change-Id: I0c954da0943092c48686afc99ecf75eba516de6a
Reviewed-on: https://go-review.googlesource.com/3352Reviewed-by: Aram Hăvărneanu <aram@mgk.ro>
Reviewed-by: Rob Pike <r@golang.org>

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/3340Reviewed-by: Adam Langley <agl@golang.org>

- fixed Float.Add, Float.Sub
- fixed Float.PString to be platform independent
- fixed Float.Uint64
- fixed various test outputs

TBR: adonovan

Change-Id: I9d273b344d4786f1fed18862198b23285c358a39
Reviewed-on: https://go-review.googlesource.com/3321Reviewed-by: Robert Griesemer <gri@golang.org>

The %61 hack was added when runtime was is in C.
Now the Go compiler does the optimization.

Change-Id: I79c3302ec4b931eaaaaffe75e7101c92bf287fc7
Reviewed-on: https://go-review.googlesource.com/3289Reviewed-by: Keith Randall <khr@golang.org>

BenchmarkClient is intended for profiling
the client without the HTTP server code.
The server code runs in a subprocess.

Change-Id: I9aa128604d0d4e94dc5c0372dc86f962282ed6e8
Reviewed-on: https://go-review.googlesource.com/3164Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

Change-Id: I73a416291a2374dbb8ce8586f24059f8dce56529
Reviewed-on: https://go-review.googlesource.com/3360Reviewed-by: Alan Donovan <adonovan@google.com>

Consider the following code:

s := "(" + string(byteSlice) + ")"

Currently we allocate a new string during []byte->string conversion,
and pass it to concatstrings. String allocation is unnecessary in
this case, because concatstrings does memorize the strings for later use.
This change uses slicebytetostringtmp to construct temp string directly
from []byte buffer and passes it to concatstrings.

I've found few such cases in std lib:

	s += string(msg[off:off+c]) + "."
	buf.WriteString("Sec-WebSocket-Accept: " + string(c.accept) + "\r\n")
	bw.WriteString("Sec-WebSocket-Key: " + string(nonce) + "\r\n")
	err = xml.Unmarshal([]byte("<Top>"+string(data)+"</Top>"), &logStruct)
	d.err = d.syntaxError("invalid XML name: " + string(b))
	return m, ProtocolError("malformed MIME header line: " + string(kv))

But there are much more in our internal code base.

Change-Id: I42f401f317131237ddd0cb9786b0940213af16fb
Reviewed-on: https://go-review.googlesource.com/3163Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>

This is another case where we can say that the address refers to stack.
We create such temps for OSTRUCTLIT initialization.

This eliminates a handful of write barriers today.
But this come up a prerequisite for another change (capturing vars by value),
otherwise we emit writebarriers in writebarrier itself when
capture writebarrier arguments by value.

Change-Id: Ibba93acd0f5431c5a4c3d90ef1e622cb9a7ff50e
Reviewed-on: https://go-review.googlesource.com/3285Reviewed-by: Russ Cox <rsc@golang.org>

Typecheck for range variables before typechecking for range body.
Body can refer to new vars declared in for range,
so it is preferable to typecheck them before the body.
Makes typecheck order consistent between ORANGE and OFOR.

This come up during another change that computes some predicates
on variables during typechecking.

Change-Id: Ic975db61b1fd5b7f9ee78896d4cc7d93c593c532
Reviewed-on: https://go-review.googlesource.com/3284Reviewed-by: Russ Cox <rsc@golang.org>

Half of tests currently crash with GODEBUG=wbshadow.
_PageSize is set to 8192. So data can be extended outside
of actually mapped region during rounding. Which leads to crash
during initial copying to shadow.
Use _PhysPageSize instead.

Change-Id: Iaa89992bd57f86dafa16b092b53fdc0606213acb
Reviewed-on: https://go-review.googlesource.com/3286Reviewed-by: Russ Cox <rsc@golang.org>

Currently we scan maps even if k/v does not contain pointers.
This is required because overflow buckets are hanging off the main table.
This change introduces a separate array that contains pointers to all
overflow buckets and keeps them alive. Buckets themselves are marked
as containing no pointers and are not scanned by GC (if k/v does not
contain pointers).

This brings maps in line with slices and chans -- GC does not scan
their contents if elements do not contain pointers.

Currently scanning of a map[int]int with 2e8 entries (~8GB heap)
takes ~8 seconds. With this change scanning takes negligible time.

Update #9477.

Change-Id: Id8a04066a53d2f743474cad406afb9f30f00eaae
Reviewed-on: https://go-review.googlesource.com/3288Reviewed-by: Keith Randall <khr@golang.org>

runtime/debug test crashes with GOMAXPROCS>1:

fatal error: unexpected signal during runtime execution
[signal 0xb code=0x1 addr=0x0 pc=0x80521b8]
runtime stack:
runtime.throw(0x8195028, 0x2a)
	src/runtime/panic.go:508 +0x71 fp=0x18427f24 sp=0x18427f18
runtime.sigpanic()
	src/runtime/sigpanic_unix.go:12 +0x53 fp=0x18427f4c sp=0x18427f24
runtime.finq_callback(0x0, 0x0, 0x0, 0x8129140, 0x0)
	src/runtime/heapdump.go:410 +0x58 fp=0x18427f58 sp=0x18427f4c
runtime.iterate_finq(0x81a6860)
	src/runtime/mfinal.go:89 +0x73 fp=0x18427f78 sp=0x18427f58
runtime.dumproots()
	src/runtime/heapdump.go:448 +0x17a fp=0x18427fa4 sp=0x18427f78
runtime.mdump()
	src/runtime/heapdump.go:652 +0xbc fp=0x18427fb4 sp=0x18427fa4
runtime.writeheapdump_m(0x3)

This happens because runfinq goroutine nils some elements in allfin after
execution of finalizers:

	// drop finalizer queue references to finalized object
	f.fn = nil
	f.arg = nil
	f.ot = nil

Then heapdump crashes trying to dereference fn.fn here:

func finq_callback(fn *funcval, obj unsafe.Pointer, nret uintptr, fint *_type, ot *ptrtype) {
	dumpint(tagQueuedFinalizer)
	dumpint(uint64(uintptr(obj)))
	dumpint(uint64(uintptr(unsafe.Pointer(fn))))
	dumpint(uint64(uintptr(unsafe.Pointer(fn.fn))))
	dumpint(uint64(uintptr(unsafe.Pointer(fint))))
	dumpint(uint64(uintptr(unsafe.Pointer(ot))))
}

Change-Id: I372433c964180d782967be63d4355e568666980d
Reviewed-on: https://go-review.googlesource.com/3287Reviewed-by: Keith Randall <khr@golang.org>

This reverts commit 8d7bf229.

Change-Id: Iad2c74a504d64bcf7ca707b00bda29bc796a2ae9
Reviewed-on: https://go-review.googlesource.com/3320Reviewed-by: Adam Langley <agl@golang.org>

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/2422Reviewed-by: Adam Langley <agl@golang.org>