Go 1.0.3: The Minor Release

Go 1.0.3 shipped on 21 September 2012, the third point release and by far the largest: 223 commits against 1.0.2. The release note describes all of it in one line: "includes minor code and documentation fixes."¹ Most of it is exactly that, typo corrections and CLA additions and doc tweaks.

Three of those commits are the subject here, and none is minor. One let a few malformed bytes crash any program that decompressed untrusted data. One made a Go TLS server fail against OpenSSL about one handshake in a few hundred. One made the compiler give the wrong answer for an ordinary number. They sit in three different corners of the language: the decompressor, the crypto library, and the compiler.

The decompressor#

The first bug you could trigger from outside the program.

The crash#

You have some compressed bytes from a source you do not control, and you inflate them. Here is that, with a stream built to be malformed. On current Go, hit Run.

package main

import (
	"compress/flate"
	"fmt"
	"io"
	"io/ioutil"
	"strings"
)

func main() {
	// A crafted DEFLATE stream with a malformed block header.
	bad := "\xfc\xfe\x36\xe7\x5e\x1c\xef\xb3\x55\x58\x77\xb6\x56\xb5\x43\xf4" +
		"\x6f\xf2\xd2\xe6\x3d\x99\xa0\x85\x8c\x48\xeb\xf8\xda\x83\x04\x2a" +
		"\x75\xc4\xf8\x0f\x12\x11\xb9\xb4\x4b\x09\xa0\xbe\x8b\x91\x4c"
	r := flate.NewReader(strings.NewReader(bad))
	n, err := io.Copy(ioutil.Discard, r)
	fmt.Printf("copied=%d err=%v\n", n, err)
}

copied=0 err=flate: corrupt input before offset 3

Current Go reads three bytes, decides the stream is corrupt, and returns an error for the caller to handle. Now the same program on Go 1.0, built from source and run unchanged:²

$ go version
go version go1
$ go run decompress.go
panic: runtime error: index out of range

goroutine 1 [running]:
compress/flate.(*decompressor).readHuffman(0xf840059000, 0x0, 0x0, 0x1)
	/goroot/src/pkg/compress/flate/inflate.go:343 +0x3cf
compress/flate.(*decompressor).nextBlock(0xf840059000, 0x405fc6)
	/goroot/src/pkg/compress/flate/inflate.go:262 +0x1ab

There is no error value this time. The panic comes up from inside compress/flate, three stack frames into the standard library, on input the program was handed from outside.

The overrun#

DEFLATE, the algorithm behind gzip and zlib, encodes a block by first describing the Huffman codes it will use, then the data. A dynamic-Huffman block opens with three counts: how many literal and length codes follow, how many distance codes, and how many code-length codes. The decoder reads those counts and then reads exactly that many entries.

Two of those counts drive the bug. Decode them out of the stream's first two bytes:

package main

import "fmt"

func main() {
	// The block header lives in the first two bytes, read low bit first:
	// BFINAL(1) BTYPE(2) HLIT(5) HDIST(5) HCLEN(4).
	b0, b1 := byte(0xfc), byte(0xfe)
	bits := uint16(b0) | uint16(b1)<<8

	btype := (bits >> 1) & 3
	hlit := (bits >> 3) & 0x1f
	hdist := (bits >> 8) & 0x1f

	fmt.Printf("BTYPE = %d (2 is a dynamic-Huffman block)\n", btype)
	fmt.Printf("HLIT  = %d, so nlit  = %d\n", hlit, int(hlit)+257)
	fmt.Printf("HDIST = %d, so ndist = %d\n", hdist, int(hdist)+1)
	fmt.Printf("nlit + ndist = %d, and the table holds 286 + 32 = 318\n",
		int(hlit)+257+int(hdist)+1)
}

BTYPE = 2 (2 is a dynamic-Huffman block)
HLIT  = 31, so nlit  = 288
HDIST = 30, so ndist = 31
nlit + ndist = 319, and the table holds 286 + 32 = 318

HLIT is a five-bit field, so it holds 0 through 31, and the decoder reads it as nlit = HLIT + 257, a number from 257 to 288. This stream sets it to its maximum: 288 code lengths to follow.

The decoder writes those code lengths into a fixed array. In the Go 1.0 source that array is declared for the largest valid header:

const (
	maxLit  = 286
	maxDist = 32
)

// inside the decompressor:
bits [maxLit + maxDist]int // 318 entries

func (f *decompressor) readHuffman() error {
	// ...
	nlit := int(f.b&0x1F) + 257 // 257..288, taken straight from the stream
	// ...
	for i, n := 0, nlit+ndist; i < n; {
		// ...
		f.bits[i] = x // writes indices 0 .. nlit+ndist-1
		i++
	}
}

The array holds 318 entries, and 318 is maxLit + maxDist, exactly 286 + 32. Those 318 slots match the largest header the format permits: RFC 1951 caps HLIT at 29, so a well-formed nlit never exceeds 286.³

But nlit came straight from the stream, and the stream said 288, two more than the 286 the array budgeted for literal codes. The decoder fills nlit + ndist entries, and for this header that is 319, one more than the array holds. The write to f.bits[318] lands one index past the end, where the last valid slot is 317, so Go's bounds check fires and turns the out-of-bounds write into a panic instead of the silent memory corruption it would be in C.

The fix is a single guard, added right after the count is read. Nigel Tao's change checks nlit against the size the array was built for, and returns a corrupt-input error when it does not fit:⁴

 	nlit := int(f.b&0x1F) + 257
+	if nlit > maxLit {
+		return CorruptInputError(f.roffset)
+	}

That guard is why this was worth a point release. A panic is not a returned error: it unwinds the stack on its own, and if nothing recovers it, it ends the program. Code that decompresses untrusted input often does not expect to fail that way, so a malformed header becomes a denial of service, needing no valid data and no credentials, only a few bytes with the wrong count in the first one. Anything that inflated bytes off the wire was exposed, and in 2012 that surface was widening, anywhere a server accepted compressed input it had not created.

The crypto library#

The decompressor bug crashed the program. This one produced no crash and no error, only an intermittent failure against one client, and it was harder to trace.

A short signature#

In July 2012 Evan Shaw reported that his Go HTTPS server worked against browsers and Go clients but failed against a Ruby client built on OpenSSL, which rejected about one connection in a few hundred with a bad signature error and nothing in the failed handshakes to set them apart from the rest.⁵

During a TLS handshake the server signs part of the exchange with its RSA private key and the client verifies it. The signature Go produced was mathematically valid and verified fine as a number. OpenSSL rejected it for its length. Here is one message signed with one RSA key, on Go 1.0 and on a current toolchain. The key was generated by the Go 1.0 toolchain so both accept it, and PKCS#1 v1.5 signing is deterministic, so the value is fixed:⁶

# Go 1.0, the toolchain that shipped the bug:
$ go run sign.go
modulus is 128 bytes; signature is 127 bytes
first 6 bytes: c8fe05bee5e3

# a current toolchain, same key and message:
$ go run sign.go
modulus is 128 bytes; signature is 128 bytes
first 6 bytes: 00c8fe05bee5

The modulus is 128 bytes, so a signature under this key is 128 bytes. On Go 1.0 this one is 127. The two outputs are the same value: the current signature is the Go 1.0 signature with a leading 00 byte that Go 1.0 dropped.

The missing zero#

A PKCS#1 v1.5 signature is a large integer, and putting it on the wire means encoding it as bytes. The standard fixes the width: the octet string is exactly as many bytes as the modulus, big-endian, left-padded with zeros when the number is small, so a 128-byte modulus always takes a 128-byte signature.⁷

Go 1.0 computed the integer correctly, then encoded it with big.Int.Bytes, which returns the shortest big-endian form and drops leading zeros:

package main

import (
	"fmt"
	"math/big"
)

// left-padding is what the fix applies to the signature: pad back out to k.
func leftPad(b []byte, k int) []byte {
	out := make([]byte, k)
	copy(out[k-len(b):], b)
	return out
}

func main() {
	// An RSA signature value whose big-endian form starts with a zero byte.
	s := new(big.Int).SetBytes([]byte{0x00, 0xc8, 0xfe, 0x05, 0xbe})
	k := 5 // the modulus is 5 bytes wide

	buggy := s.Bytes()
	fixed := leftPad(s.Bytes(), k)
	fmt.Printf("Go 1.0   c.Bytes():   % x  (%d bytes)\n", buggy, len(buggy))
	fmt.Printf("Go 1.0.3 left-padded: % x  (%d bytes)\n", fixed, len(fixed))
}

Go 1.0   c.Bytes():   c8 fe 05 be  (4 bytes)
Go 1.0.3 left-padded: 00 c8 fe 05 be  (5 bytes)

The left-padding is the repair; the bare Bytes call is what Go 1.0 shipped. Whenever the signature integer was small enough to begin with a zero byte, Bytes returned one byte fewer than the modulus. For a value that looks random, a leading zero byte turns up about once in 256, which is the rate at which the handshakes failed.

Go's own verifier accepted the short encoding, so a Go client and a Go server never noticed the missing byte, while OpenSSL enforced the length and rejected it. Adam Langley put the requirement in the change description itself: "OpenSSL requires that RSA signatures be exactly the same byte-length as the modulus." His fix left-pads the output to that length, and it covered both functions that had the bug, PKCS#1 v1.5 signing and encryption.⁸

The compiler#

The decompressor and the signature were both in the standard library. This bug was in the compiler, and it made a basic operation give the wrong answer.

The wrong answer#

A conversion from a floating-point number to an integer truncates toward zero, so a float64 holding 2.9 converts to 2. On the amd64 compiler in Go 1.0 it converted to 3. Run this on current Go:

package main

import "fmt"

func main() {
	// The Go spec says a float-to-integer conversion truncates toward zero.
	for _, f := range []float64{2.9, 39.7, 258.6} {
		fmt.Printf("uint64(%v) = %d\n", f, uint64(f))
	}
}

uint64(2.9) = 2
uint64(39.7) = 39
uint64(258.6) = 258

Truncation, as specified. The same program on Go 1.0:⁹

$ go run conv.go
uint64(2.9) = 3
uint64(39.7) = 40
uint64(258.6) = 259

Every value is rounded to the nearest integer instead of truncated.

One instruction#

The amd64 processor has no instruction that converts a float straight to an unsigned 64-bit integer, so the compiler builds the conversion from the signed one plus a correction. The signed convert is where the bug lived. The instruction the compiler emitted, CVTSD2SI, rounds according to the processor's current rounding mode, which is round-to-nearest by default. The one the language needs, CVTTSD2SI, truncates. They differ by the extra T, and the neighbouring code that converted to a signed int64 already used the truncating form.¹⁰

Shenghou Ma's fix is that letter, in both the float64 and float32 paths:

-			a = ACVTSD2SQ;
+			a = ACVTTSD2SQ;

The ACVTTSD2SQ is Go's assembler name for CVTTSD2SI into a 64-bit register. With it the conversion truncates, and a float64 of 2.9 converts to 2 on amd64 as it always did on the other architectures.

Three commits#

Go 1.0.3 was 223 commits. Three of them are the bugs above; the rest is documentation, contributor additions, and a long tail of small library fixes.