While implementing an ECDSA request signature algorithm I was writing unit tests for it. The tests should work in a reproducible way: we generate the same private key each time, sign constant data with the same random (which is needed for ECDSA) - we get the same signature. It seems quite straightforward.

Using reproducible random stream⌗

Looking at the documentation, we see that we should pass elliptic curve parameters and the random stream we want to use.

https://godoc.org/crypto/ecdsa#GenerateKey

// GenerateKey generates a public and private key pair.
func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error)

So it looks like if we pass exactly the same random data here, we will get the same key. Okay, good. Let’s take a PRNG and use is for key generation.

Note that usually as the random source here goes some kind of KDF or XOF (like BLAKE2/SHA3). In this demo though, I take one from math/rand for the sake of simplicity. You should never do that in real applications.

    privRandom := rand.New(rand.NewSource(1))
    priv, _ := ecdsa.GenerateKey(elliptic.P256(), privRandom)
    pk, _ := x509.MarshalPKIXPublicKey(priv.Public())
    fmt.Printf("%x", pk)

Outputs:

3059301306072a8648ce3d020106082a8648ce3d03010703420004bd9d64a498f0b14a1c67a78dc5f8faceb5b195eec35f91b43f931ce2f44828d1925d897c649affc2d3940575d096ed8d19b0908b1c6a2042c627589057519395

This yields the same result on each run. Which is not a surprise, as we always run the same data through the same algorithm.

Let’s sign a message now.

    signRandom := rand.New(rand.NewSource(2))
    msgHash := sha256.New().Sum([]byte("msg"))
    r, s, _ := ecdsa.Sign(signRandom, priv, msgHash)
    fmt.Printf("r: %v\ns: %v\n", r, s)

Yields:

r: 100208058185876378552887569670579625957693662286329420505909837704135172775474
s: 14564155116193857911583572423625250943838296850548688432220745142979318743780

but then sometimes this:

r: 83046307405099488930792620711173203184836792003014229095908217487419596636969
s: 83881183107550802640600691868060814644284868586946726392372569224638997936927

Why is this happening?⌗

I thought that it could be due to the fact that there are two valid ECDSA signatures - another one comes as -s mod n instead of s. Then there should be a behavior to pick the sign, which is a bit weird to have in the first place.

Okay, but the r is also changing - it means that we get something entirely different in these cases. What’s the deal?

We go to the code of ecdsa.Sign() and the first line there immediately gives us the answer - some mangling of our random stream is going on there:

randutil.MaybeReadByte(rand)

What does it do?⌗

The documentation for it says the following:

MaybeReadByte reads a single byte from r with ~50% probability. This is used
to ensure that callers do not depend on non-guaranteed behavior, e.g.
assuming that rsa.GenerateKey is deterministic w.r.t. a given random stream.

This does not affect tests that pass a stream of fixed bytes as the random
source (e.g. a zeroReader).

Curious! So it does advance the random stream we have as the input to prevent us from getting reproducible results. This is exactly what we are hitting. Still, you can generate reproducible results if you have a random source that consists of the same bytes, so reading a byte from it will leave it in an identical state. It looks like a gorgeous hack to me.

How does it work?⌗

It does another curious hack - reading from a closed channel with a select statement.

select statement has the property to pseudorandomly pick the case if there are multiple cases ready. The hack is that one may use multiple reads from an always-ready channel. What channel is that? Right, a closed channel, as all the reads from it do return immediately. So the following code reads a byte only with a probability of 0.5.

func MaybeReadByte(r io.Reader) {
	//...
	select {
	case <-closedChan:
		return
	case <-closedChan:
		var buf [1]byte
		r.Read(buf[:])
	}
}

Further reading⌗

The original commit and its message is also interesting to read. For instance, the hack isn’t used for ECDSA and DSA key generation as they have straightforward implementations without many variations and are unlikely to change. It’s hardly the case of RSA key generation - the process of finding primes is subject to change during optimizations or flaw fixes. The key point is that one may use any kind of algorithm to get the primes.

I hope you enjoyed the hack too. Now you know that one may use this fun way to generate random numbers in Go without importing any package or use the standard library even! It is entertaining to tap into the runtime’s fastrand that is used for flip-a-coin situations like select statement internally.

Have a nice day! ✨