go/protocol/protocol.go

// Copyright 2016 The Roughtime Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License. */

// Package protocol implements the core of the Roughtime protocol.
package protocol

import (
	"bytes"
	"crypto/sha512"
	"encoding/binary"
	"errors"
	"io"
	"math"
	"sort"

	"golang.org/x/crypto/ed25519"
)

const (
	// NonceSize is the number of bytes in a nonce.
	NonceSize = sha512.Size
	// MinRequestSize is the minimum number of bytes in a request.
	MinRequestSize = 1024

	certificateContext    = "RoughTime v1 delegation signature--\x00"
	signedResponseContext = "RoughTime v1 response signature\x00"
)

// makeTag converts a four character string into a Roughtime tag value.
func makeTag(tag string) uint32 {
	if len(tag) != 4 {
		panic("makeTag: len(tag) != 4: " + tag)
	}

	return uint32(tag[0]) | uint32(tag[1])<<8 | uint32(tag[2])<<16 | uint32(tag[3])<<24
}

var (
	// Various tags used in the Roughtime protocol.
	tagCERT = makeTag("CERT")
	tagDELE = makeTag("DELE")
	tagINDX = makeTag("INDX")
	tagMAXT = makeTag("MAXT")
	tagMIDP = makeTag("MIDP")
	tagMINT = makeTag("MINT")
	tagNONC = makeTag("NONC")
	tagPAD  = makeTag("PAD\xff")
	tagPATH = makeTag("PATH")
	tagPUBK = makeTag("PUBK")
	tagRADI = makeTag("RADI")
	tagROOT = makeTag("ROOT")
	tagSIG  = makeTag("SIG\x00")
	tagSREP = makeTag("SREP")

	// TagNonce names the bytestring containing the client's nonce.
	TagNonce = tagNONC
)

// tagsSlice is the type of an array of tags. It provides utility functions so
// that they can be sorted.
type tagsSlice []uint32

func (t tagsSlice) Len() int           { return len(t) }
func (t tagsSlice) Less(i, j int) bool { return t[i] < t[j] }
func (t tagsSlice) Swap(i, j int)      { t[i], t[j] = t[j], t[i] }

// Encode converts a map of tags to bytestrings into an encoded message. The
// number of elements in msg and the sum of the lengths of all the bytestrings
// must be ≤ 2**32.
func Encode(msg map[uint32][]byte) ([]byte, error) {
	if len(msg) == 0 {
		return make([]byte, 4), nil
	}

	if len(msg) >= math.MaxInt32 {
		return nil, errors.New("encode: too many tags")
	}

	var payloadSum uint64
	for _, payload := range msg {
		if len(payload)%4 != 0 {
			return nil, errors.New("encode: length of value is not a multiple of four")
		}
		payloadSum += uint64(len(payload))
	}
	if payloadSum >= 1<<32 {
		return nil, errors.New("encode: payloads too large")
	}

	tags := tagsSlice(make([]uint32, 0, len(msg)))
	for tag := range msg {
		tags = append(tags, tag)
	}
	sort.Sort(tags)

	numTags := uint64(len(tags))

	encoded := make([]byte, 4*(1+numTags-1+numTags)+payloadSum)
	binary.LittleEndian.PutUint32(encoded, uint32(len(tags)))
	offsets := encoded[4:]
	tagBytes := encoded[4*(1+(numTags-1)):]
	payloads := encoded[4*(1+(numTags-1)+numTags):]

	currentOffset := uint32(0)

	for i, tag := range tags {
		payload := msg[tag]
		if i > 0 {
			binary.LittleEndian.PutUint32(offsets, currentOffset)
			offsets = offsets[4:]
		}

		binary.LittleEndian.PutUint32(tagBytes, tag)
		tagBytes = tagBytes[4:]

		if len(payload) > 0 {
			copy(payloads, payload)
			payloads = payloads[len(payload):]
			currentOffset += uint32(len(payload))
		}
	}

	return encoded, nil
}

// Decode parses the output of encode back into a map of tags to bytestrings.
func Decode(bytes []byte) (map[uint32][]byte, error) {
	if len(bytes) < 4 {
		return nil, errors.New("decode: message too short to be valid")
	}
	if len(bytes)%4 != 0 {
		return nil, errors.New("decode: message is not a multiple of four bytes")
	}

	numTags := uint64(binary.LittleEndian.Uint32(bytes))

	if numTags == 0 {
		return make(map[uint32][]byte), nil
	}

	minLen := 4 * (1 + (numTags - 1) + numTags)

	if uint64(len(bytes)) < minLen {
		return nil, errors.New("decode: message too short to be valid")
	}

	offsets := bytes[4:]
	tags := bytes[4*(1+numTags-1):]
	payloads := bytes[minLen:]

	if len(payloads) > math.MaxInt32 {
		return nil, errors.New("decode: message too large")
	}
	payloadLength := uint32(len(payloads))

	currentOffset := uint32(0)
	var lastTag uint32
	ret := make(map[uint32][]byte)

	for i := uint64(0); i < numTags; i++ {
		tag := binary.LittleEndian.Uint32(tags)
		tags = tags[4:]

		if i > 0 && lastTag >= tag {
			return nil, errors.New("decode: tags out of order")
		}

		var nextOffset uint32
		if i < numTags-1 {
			nextOffset = binary.LittleEndian.Uint32(offsets)
			offsets = offsets[4:]
		} else {
			nextOffset = payloadLength
		}

		if nextOffset%4 != 0 {
			return nil, errors.New("decode: payload length is not a multiple of four bytes")
		}

		if nextOffset < currentOffset {
			return nil, errors.New("decode: offsets out of order")
		}

		length := nextOffset - currentOffset
		if uint32(len(payloads)) < length {
			return nil, errors.New("decode: message truncated")
		}

		payload := payloads[:length]
		payloads = payloads[length:]
		ret[tag] = payload
		currentOffset = nextOffset
		lastTag = tag
	}

	return ret, nil
}

// messageOverhead returns the number of bytes needed for Encode to encode the
// given number of tags.
func messageOverhead(numTags int) int {
	return 4 * 2 * numTags
}

// CalculateChainNonce calculates the nonce to be used in the next request in a
// chain given a reply and a blinding factor.
func CalculateChainNonce(prevReply, blind []byte) (nonce [NonceSize]byte) {
	h := sha512.New()
	h.Write(prevReply)
	prevReplyHash := h.Sum(nil)

	h.Reset()
	h.Write(prevReplyHash)
	h.Write(blind)
	h.Sum(nonce[:0])

	return nonce
}

// CreateRequest creates a Roughtime request given an entropy source and the
// contents of a previous reply for chaining. If this request is the first of a
// chain, prevReply can be empty. It returns the nonce (needed to verify the
// reply), the blind (needed to prove correct chaining to an external party)
// and the request itself.
func CreateRequest(rand io.Reader, prevReply []byte) (nonce, blind [NonceSize]byte, request []byte, err error) {
	if _, err := io.ReadFull(rand, blind[:]); err != nil {
		return nonce, blind, nil, err
	}

	nonce = CalculateChainNonce(prevReply, blind[:])

	padding := make([]byte, MinRequestSize-messageOverhead(2)-len(nonce))
	msg, err := Encode(map[uint32][]byte{
		tagNONC: nonce[:],
		tagPAD:  padding,
	})
	if err != nil {
		return nonce, blind, nil, err
	}

	return nonce, blind, msg, nil
}

// tree represents a Merkle tree of nonces. Each element of values is a layer
// in the tree, with the widest layer first.
type tree struct {
	values [][][NonceSize]byte
}

var (
	hashLeafTweak = []byte{0}
	hashNodeTweak = []byte{1}
)

// hashLeaf hashes an nonce to form the leaf of the Merkle tree.
func hashLeaf(out *[sha512.Size]byte, in []byte) {
	h := sha512.New()
	h.Write(hashLeafTweak)
	h.Write(in)
	h.Sum(out[:0])
}

// hashNode hashes two child elements of the Merkle tree to produce an interior
// node.
func hashNode(out *[sha512.Size]byte, left, right []byte) {
	h := sha512.New()
	h.Write(hashNodeTweak)
	h.Write(left)
	h.Write(right)
	h.Sum(out[:0])
}

// newTree creates a Merkle tree given one or more nonces.
func newTree(nonces [][]byte) *tree {
	if len(nonces) == 0 {
		panic("newTree: passed empty slice")
	}

	levels := 1
	width := len(nonces)
	for width > 1 {
		width = (width + 1) / 2
		levels++
	}

	ret := &tree{
		values: make([][][NonceSize]byte, 0, levels),
	}

	leaves := make([][NonceSize]byte, ((len(nonces)+1)/2)*2)
	for i, nonce := range nonces {
		var leaf [NonceSize]byte
		hashLeaf(&leaf, nonce)
		leaves[i] = leaf
	}
	// Fill any extra leaves with an existing leaf, to simplify analysis
	// that we are not inadvertently signing other messages.
	for i := len(nonces); i < len(leaves); i++ {
		leaves[i] = leaves[0]
	}
	ret.values = append(ret.values, leaves)

	for i := 1; i < levels; i++ {
		lastLevel := ret.values[i-1]
		width := len(lastLevel) / 2
		if width%2 == 1 {
			width++
		}
		level := make([][NonceSize]byte, width)
		for j := 0; j < len(lastLevel)/2; j++ {
			hashNode(&level[j], lastLevel[j*2][:], lastLevel[j*2+1][:])
		}
		// Fill the extra node with an existing node, to simplify
		// analysis that we are not inadvertently signing other
		// messages.
		if len(lastLevel)/2 < len(level) {
			level[len(lastLevel)/2] = level[0]
		}
		ret.values = append(ret.values, level)
	}

	return ret
}

// Root returns the root value of t.
func (t *tree) Root() *[NonceSize]byte {
	return &t.values[len(t.values)-1][0]
}

// Levels returns the number of levels in t.
func (t *tree) Levels() int {
	return len(t.values)
}

// Path returns elements from t needed to prove, given the root, that the leaf
// at the given index is in the tree.
func (t *tree) Path(index int) (path [][]byte) {
	path = make([][]byte, 0, len(t.values))

	for level := 0; level < len(t.values)-1; level++ {
		if index%2 == 1 {
			path = append(path, t.values[level][index-1][:])
		} else {
			path = append(path, t.values[level][index+1][:])
		}

		index /= 2
	}

	return path
}

// CreateReplies signs, using privateKey, a batch of nonces along with the
// given time and radius in microseconds. It returns one reply for each nonce
// using that signature and includes cert in each.
func CreateReplies(nonces [][]byte, midpoint uint64, radius uint32, cert []byte, privateKey []byte) ([][]byte, error) {
	if len(nonces) == 0 {
		return nil, nil
	}

	tree := newTree(nonces)

	var midpointBytes [8]byte
	binary.LittleEndian.PutUint64(midpointBytes[:], midpoint)
	var radiusBytes [4]byte
	binary.LittleEndian.PutUint32(radiusBytes[:], radius)

	signedReply := map[uint32][]byte{
		tagMIDP: midpointBytes[:],
		tagRADI: radiusBytes[:],
		tagROOT: tree.Root()[:],
	}
	signedReplyBytes, err := Encode(signedReply)
	if err != nil {
		return nil, err
	}

	toBeSigned := signedResponseContext + string(signedReplyBytes)
	sig := ed25519.Sign(privateKey, []byte(toBeSigned))

	reply := map[uint32][]byte{
		tagSREP: signedReplyBytes,
		tagSIG:  sig,
		tagCERT: cert,
	}

	replies := make([][]byte, 0, len(nonces))

	for i := range nonces {
		var indexBytes [4]byte
		binary.LittleEndian.PutUint32(indexBytes[:], uint32(i))
		reply[tagINDX] = indexBytes[:]

		path := tree.Path(i)
		pathBytes := make([]byte, 0, NonceSize*len(path))
		for _, pathStep := range path {
			pathBytes = append(pathBytes, pathStep...)
		}
		reply[tagPATH] = pathBytes

		replyBytes, err := Encode(reply)
		if err != nil {
			return nil, err
		}

		replies = append(replies, replyBytes)
	}

	return replies, nil
}

// CreateCertificate returns a signed certificate, using rootPrivateKey,
// delegating authority for the given timestamp to publicKey.
func CreateCertificate(minTime, maxTime uint64, publicKey, rootPrivateKey []byte) (certBytes []byte, err error) {
	if maxTime < minTime {
		return nil, errors.New("protocol: maxTime < minTime")
	}

	var minTimeBytes, maxTimeBytes [8]byte
	binary.LittleEndian.PutUint64(minTimeBytes[:], minTime)
	binary.LittleEndian.PutUint64(maxTimeBytes[:], maxTime)

	signed := map[uint32][]byte{
		tagPUBK: publicKey,
		tagMINT: minTimeBytes[:],
		tagMAXT: maxTimeBytes[:],
	}

	signedBytes, err := Encode(signed)
	if err != nil {
		return nil, err
	}

	toBeSigned := certificateContext + string(signedBytes)
	sig := ed25519.Sign(rootPrivateKey, []byte(toBeSigned))

	cert := map[uint32][]byte{
		tagSIG:  sig,
		tagDELE: signedBytes,
	}

	return Encode(cert)
}

func getValue(msg map[uint32][]byte, tag uint32, name string) (value []byte, err error) {
	value, ok := msg[tag]
	if !ok {
		return nil, errors.New("protocol: missing " + name)
	}
	return value, nil
}

func getFixedLength(msg map[uint32][]byte, tag uint32, name string, length int) (value []byte, err error) {
	value, err = getValue(msg, tag, name)
	if err != nil {
		return nil, err
	}
	if len(value) != length {
		return nil, errors.New("protocol: incorrect length for " + name)
	}
	return value, nil
}

func getUint32(msg map[uint32][]byte, tag uint32, name string) (result uint32, err error) {
	valueBytes, err := getFixedLength(msg, tag, name, 4)
	if err != nil {
		return 0, err
	}
	return binary.LittleEndian.Uint32(valueBytes), nil
}

func getUint64(msg map[uint32][]byte, tag uint32, name string) (result uint64, err error) {
	valueBytes, err := getFixedLength(msg, tag, name, 8)
	if err != nil {
		return 0, err
	}
	return binary.LittleEndian.Uint64(valueBytes), nil
}

func getSubmessage(msg map[uint32][]byte, tag uint32, name string) (result map[uint32][]byte, err error) {
	valueBytes, err := getValue(msg, tag, name)
	if err != nil {
		return nil, err
	}

	result, err = Decode(valueBytes)
	if err != nil {
		return nil, errors.New("protocol: failed to parse " + name + ": " + err.Error())
	}

	return result, nil
}

// VerifyReply parses the Roughtime reply in replyBytes, authenticates it using
// publicKey and verifies that nonce is included in it. It returns the included
// timestamp and radius.
func VerifyReply(replyBytes, publicKey []byte, nonce [NonceSize]byte) (time uint64, radius uint32, err error) {
	reply, err := Decode(replyBytes)
	if err != nil {
		return 0, 0, errors.New("protocol: failed to parse top-level reply: " + err.Error())
	}

	cert, err := getSubmessage(reply, tagCERT, "certificate")
	if err != nil {
		return 0, 0, err
	}

	signatureBytes, err := getFixedLength(cert, tagSIG, "signature", ed25519.SignatureSize)
	if err != nil {
		return 0, 0, err
	}

	delegationBytes, err := getValue(cert, tagDELE, "delegation")
	if err != nil {
		return 0, 0, err
	}

	if !ed25519.Verify(publicKey, []byte(certificateContext+string(delegationBytes)), signatureBytes) {
		return 0, 0, errors.New("protocol: invalid delegation signature")
	}

	delegation, err := Decode(delegationBytes)
	if err != nil {
		return 0, 0, errors.New("protocol: failed to parse delegation: " + err.Error())
	}

	minTime, err := getUint64(delegation, tagMINT, "minimum time")
	if err != nil {
		return 0, 0, err
	}

	maxTime, err := getUint64(delegation, tagMAXT, "maximum time")
	if err != nil {
		return 0, 0, err
	}

	delegatedPublicKey, err := getFixedLength(delegation, tagPUBK, "public key", ed25519.PublicKeySize)
	if err != nil {
		return 0, 0, err
	}

	responseSigBytes, err := getFixedLength(reply, tagSIG, "signature", ed25519.SignatureSize)
	if err != nil {
		return 0, 0, err
	}

	signedResponseBytes, ok := reply[tagSREP]
	if !ok {
		return 0, 0, errors.New("protocol: response is missing signed portion")
	}

	if !ed25519.Verify(delegatedPublicKey, []byte(signedResponseContext+string(signedResponseBytes)), responseSigBytes) {
		return 0, 0, errors.New("protocol: invalid response signature")
	}

	signedResponse, err := Decode(signedResponseBytes)
	if err != nil {
		return 0, 0, errors.New("protocol: failed to parse signed response: " + err.Error())
	}

	root, err := getFixedLength(signedResponse, tagROOT, "root", sha512.Size)
	if err != nil {
		return 0, 0, err
	}

	midpoint, err := getUint64(signedResponse, tagMIDP, "midpoint")
	if err != nil {
		return 0, 0, err
	}

	radius, err = getUint32(signedResponse, tagRADI, "radius")
	if err != nil {
		return 0, 0, err
	}

	if maxTime < minTime {
		return 0, 0, errors.New("protocol: invalid delegation range")
	}

	if midpoint < minTime || maxTime < midpoint {
		return 0, 0, errors.New("protocol: timestamp out of range for delegation")
	}

	index, err := getUint32(reply, tagINDX, "index")
	if err != nil {
		return 0, 0, err
	}

	path, err := getValue(reply, tagPATH, "path")
	if err != nil {
		return 0, 0, err
	}
	if len(path)%sha512.Size != 0 {
		return 0, 0, errors.New("protocol: path is not a multiple of the hash size")
	}

	var hash [sha512.Size]byte
	hashLeaf(&hash, nonce[:])

	for len(path) > 0 {
		pathElementIsRight := index&1 == 0
		if pathElementIsRight {
			hashNode(&hash, hash[:], path[:sha512.Size])
		} else {
			hashNode(&hash, path[:sha512.Size], hash[:])
		}

		index >>= 1
		path = path[sha512.Size:]
	}

	if !bytes.Equal(hash[:], root) {
		return 0, 0, errors.New("protocol: calculated tree root doesn't match signed root")
	}

	return midpoint, radius, nil
}