tka: implement AUM and Key types

This is the first in a series of PRs implementing the internals for the
Tailnet Key Authority. This PR implements the AUM and Key types, which
are used by pretty much everything else. Future PRs:

 - The State type & related machinery
 - The Tailchonk (storage) type & implementation
 - The Authority type and sync implementation

Signed-off-by: Tom DNetto <tom@tailscale.com>

7 files changed, 656 insertions, 0 deletions

diff --git a/go.mod b/go.mod
index a014de039..a5018e79f 100644
--- a/go.mod
+++ b/go.mod
@@ -69,6 +69,7 @@ require (
 
 require (
 	4d63.com/gochecknoglobals v0.1.0 // indirect
+	filippo.io/edwards25519 v1.0.0-rc.1 // indirect
 	github.com/Antonboom/errname v0.1.5 // indirect
 	github.com/Antonboom/nilnil v0.1.0 // indirect
 	github.com/BurntSushi/toml v1.1.0 // indirect
@@ -121,6 +122,7 @@ require (
 	github.com/fatih/color v1.13.0 // indirect
 	github.com/fatih/structtag v1.2.0 // indirect
 	github.com/fsnotify/fsnotify v1.5.1 // indirect
+	github.com/fxamacker/cbor/v2 v2.4.0 // indirect
 	github.com/fzipp/gocyclo v0.3.1 // indirect
 	github.com/gliderlabs/ssh v0.3.3 // indirect
 	github.com/go-critic/go-critic v0.6.1 // indirect
@@ -162,6 +164,7 @@ require (
 	github.com/hashicorp/errwrap v1.1.0 // indirect
 	github.com/hashicorp/go-multierror v1.1.1 // indirect
 	github.com/hashicorp/hcl v1.0.0 // indirect
+	github.com/hdevalence/ed25519consensus v0.0.0-20220222234857-c00d1f31bab3 // indirect
 	github.com/huandu/xstrings v1.3.2 // indirect
 	github.com/imdario/mergo v0.3.12 // indirect
 	github.com/inconshreveable/mousetrap v1.0.0 // indirect
@@ -255,6 +258,7 @@ require (
 	github.com/uudashr/gocognit v1.0.5 // indirect
 	github.com/vbatts/tar-split v0.11.2 // indirect
 	github.com/vishvananda/netns v0.0.0-20211101163701-50045581ed74 // indirect
+	github.com/x448/float16 v0.8.4 // indirect
 	github.com/xanzy/ssh-agent v0.3.1 // indirect
 	github.com/yeya24/promlinter v0.1.0 // indirect
 	go4.org/intern v0.0.0-20211027215823-ae77deb06f29 // indirect
diff --git a/go.sum b/go.sum
index 6ae8f1a0d..b372855c9 100644
--- a/go.sum
+++ b/go.sum
@@ -52,6 +52,8 @@ cloud.google.com/go/storage v1.8.0/go.mod h1:Wv1Oy7z6Yz3DshWRJFhqM/UCfaWIRTdp0RX
 cloud.google.com/go/storage v1.10.0/go.mod h1:FLPqc6j+Ki4BU591ie1oL6qBQGu2Bl/tZ9ullr3+Kg0=
 contrib.go.opencensus.io/exporter/stackdriver v0.13.4/go.mod h1:aXENhDJ1Y4lIg4EUaVTwzvYETVNZk10Pu26tevFKLUc=
 dmitri.shuralyov.com/gpu/mtl v0.0.0-20190408044501-666a987793e9/go.mod h1:H6x//7gZCb22OMCxBHrMx7a5I7Hp++hsVxbQ4BYO7hU=
+filippo.io/edwards25519 v1.0.0-rc.1 h1:m0VOOB23frXZvAOK44usCgLWvtsxIoMCTBGJZlpmGfU=
+filippo.io/edwards25519 v1.0.0-rc.1/go.mod h1:N1IkdkCkiLB6tki+MYJoSx2JTY9NUlxZE7eHn5EwJns=
 filippo.io/mkcert v1.4.3 h1:axpnmtrZMM8u5Hf4N3UXxboGemMOV+Tn+e+pkHM6E3o=
 filippo.io/mkcert v1.4.3/go.mod h1:64ke566uBwAQcdK3vRDABgsgVHqrfORPTw6YytZCTxk=
 github.com/Antonboom/errname v0.1.5 h1:IM+A/gz0pDhKmlt5KSNTVAvfLMb+65RxavBXpRtCUEg=
@@ -294,6 +296,8 @@ github.com/fsnotify/fsnotify v1.4.9/go.mod h1:znqG4EE+3YCdAaPaxE2ZRY/06pZUdp0tY4
 github.com/fsnotify/fsnotify v1.5.1 h1:mZcQUHVQUQWoPXXtuf9yuEXKudkV2sx1E06UadKWpgI=
 github.com/fsnotify/fsnotify v1.5.1/go.mod h1:T3375wBYaZdLLcVNkcVbzGHY7f1l/uK5T5Ai1i3InKU=
 github.com/fullstorydev/grpcurl v1.6.0/go.mod h1:ZQ+ayqbKMJNhzLmbpCiurTVlaK2M/3nqZCxaQ2Ze/sM=
+github.com/fxamacker/cbor/v2 v2.4.0 h1:ri0ArlOR+5XunOP8CRUowT0pSJOwhW098ZCUyskZD88=
+github.com/fxamacker/cbor/v2 v2.4.0/go.mod h1:TA1xS00nchWmaBnEIxPSE5oHLuJBAVvqrtAnWBwBCVo=
 github.com/fzipp/gocyclo v0.3.1 h1:A9UeX3HJSXTBzvHzhqoYVuE0eAhe+aM8XBCCwsPMZOc=
 github.com/fzipp/gocyclo v0.3.1/go.mod h1:DJHO6AUmbdqj2ET4Z9iArSuwWgYDRryYt2wASxc7x3E=
 github.com/ghodss/yaml v1.0.0/go.mod h1:4dBDuWmgqj2HViK6kFavaiC9ZROes6MMH2rRYeMEF04=
@@ -603,6 +607,8 @@ github.com/hashicorp/memberlist v0.1.3/go.mod h1:ajVTdAv/9Im8oMAAj5G31PhhMCZJV2p
 github.com/hashicorp/memberlist v0.2.2/go.mod h1:MS2lj3INKhZjWNqd3N0m3J+Jxf3DAOnAH9VT3Sh9MUE=
 github.com/hashicorp/serf v0.8.2/go.mod h1:6hOLApaqBFA1NXqRQAsxw9QxuDEvNxSQRwA/JwenrHc=
 github.com/hashicorp/serf v0.9.5/go.mod h1:UWDWwZeL5cuWDJdl0C6wrvrUwEqtQ4ZKBKKENpqIUyk=
+github.com/hdevalence/ed25519consensus v0.0.0-20220222234857-c00d1f31bab3 h1:aSVUgRRRtOrZOC1fYmY9gV0e9z/Iu+xNVSASWjsuyGU=
+github.com/hdevalence/ed25519consensus v0.0.0-20220222234857-c00d1f31bab3/go.mod h1:5PC6ZNPde8bBqU/ewGZig35+UIZtw9Ytxez8/q5ZyFE=
 github.com/hpcloud/tail v1.0.0/go.mod h1:ab1qPbhIpdTxEkNHXyeSf5vhxWSCs/tWer42PpOxQnU=
 github.com/huandu/xstrings v1.0.0/go.mod h1:4qWG/gcEcfX4z/mBDHJ++3ReCw9ibxbsNJbcucJdbSo=
 github.com/huandu/xstrings v1.2.0/go.mod h1:DvyZB1rfVYsBIigL8HwpZgxHwXozlTgGqn63UyNX5k4=
@@ -1172,6 +1178,8 @@ github.com/vishvananda/netlink v1.1.1-0.20211118161826-650dca95af54/go.mod h1:tw
 github.com/vishvananda/netns v0.0.0-20200728191858-db3c7e526aae/go.mod h1:DD4vA1DwXk04H54A1oHXtwZmA0grkVMdPxx/VGLCah0=
 github.com/vishvananda/netns v0.0.0-20211101163701-50045581ed74 h1:gga7acRE695APm9hlsSMoOoE65U4/TcqNj90mc69Rlg=
 github.com/vishvananda/netns v0.0.0-20211101163701-50045581ed74/go.mod h1:DD4vA1DwXk04H54A1oHXtwZmA0grkVMdPxx/VGLCah0=
+github.com/x448/float16 v0.8.4 h1:qLwI1I70+NjRFUR3zs1JPUCgaCXSh3SW62uAKT1mSBM=
+github.com/x448/float16 v0.8.4/go.mod h1:14CWIYCyZA/cWjXOioeEpHeN/83MdbZDRQHoFcYsOfg=
 github.com/xanzy/ssh-agent v0.2.1/go.mod h1:mLlQY/MoOhWBj+gOGMQkOeiEvkx+8pJSI+0Bx9h2kr4=
 github.com/xanzy/ssh-agent v0.3.0/go.mod h1:3s9xbODqPuuhK9JV1R321M/FlMZSBvE5aY6eAcqrDh0=
 github.com/xanzy/ssh-agent v0.3.1 h1:AmzO1SSWxw73zxFZPRwaMN1MohDw8UyHnmuxyceTEGo=
diff --git a/tka/aum.go b/tka/aum.go
new file mode 100644
index 000000000..88166a4c5
--- /dev/null
+++ b/tka/aum.go
@@ -0,0 +1,256 @@
+// Copyright (c) 2022 Tailscale Inc & AUTHORS All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package tka
+
+import (
+	"bytes"
+	"crypto/ed25519"
+	"errors"
+	"fmt"
+
+	"github.com/fxamacker/cbor/v2"
+	"golang.org/x/crypto/blake2s"
+)
+
+// AUMHash represents the BLAKE2s digest of an Authority Update Message (AUM).
+type AUMHash [blake2s.Size]byte
+
+// AUMSigHash represents the BLAKE2s digest of an Authority Update
+// Message (AUM), sans any signatures.
+type AUMSigHash [blake2s.Size]byte
+
+// AUMKind describes valid AUM types.
+type AUMKind uint8
+
+// Valid AUM types. Do NOT reorder.
+const (
+	AUMInvalid AUMKind = iota
+	// An AddKey AUM describes a new key trusted by the TKA.
+	//
+	// Only the Key optional field may be set.
+	AUMAddKey
+	// A RemoveKey AUM describes hte removal of a key trusted by TKA.
+	//
+	// Only the KeyID optional field may be set.
+	AUMRemoveKey
+	// A DisableNL AUM describes the disablement of TKA.
+	//
+	// Only the DisablementSecret optional field may be set.
+	AUMDisableNL
+	// A NoOp AUM carries no information and is used in tests.
+	AUMNoOp
+	// A UpdateKey AUM updates the metadata or votes of an existing key.
+	//
+	// Only KeyID, along with either/or Meta or Votes optional fields
+	// may be set.
+	AUMUpdateKey
+	// A Checkpoint AUM specifies the full state of the TKA.
+	//
+	// Only the State optional field may be set.
+	AUMCheckpoint
+)
+
+func (k AUMKind) String() string {
+	switch k {
+	case AUMInvalid:
+		return "invalid"
+	case AUMAddKey:
+		return "add-key"
+	case AUMRemoveKey:
+		return "remove-key"
+	case AUMDisableNL:
+		return "disable-nl"
+	case AUMNoOp:
+		return "no-op"
+	case AUMCheckpoint:
+		return "checkpoint"
+	case AUMUpdateKey:
+		return "update-key"
+	default:
+		return fmt.Sprintf("AUM?<%d>", int(k))
+	}
+}
+
+// AUM describes an Authority Update Message.
+//
+// The rules for adding new types of AUMs (MessageKind):
+// - CBOR key IDs must never be changed.
+// - New AUM types must not change semantics that are manipulated by other
+//   AUM types.
+// - The serialization of existing data cannot change (in other words, if
+//   an existing serialization test in aum_test.go fails, you need to try a
+//   different approach).
+//
+// The rules for adding new fields are as follows:
+// - Must all be optional.
+// - An unset value must not result in serialization overhead. This is
+//   necessary so the serialization of older AUMs stays the same.
+// - New processing semantics of the new fields must be compatible with the
+//   behavior of old clients (which will ignore the field).
+// - No floats!
+type AUM struct {
+	MessageKind AUMKind `cbor:"1,keyasint"`
+	PrevAUMHash []byte  `cbor:"2,keyasint"`
+
+	// Key encodes a public key to be added to the key authority.
+	// This field is used for AddKey AUMs.
+	Key *Key `cbor:"3,keyasint,omitempty"`
+
+	// KeyID references a public key which is part of the key authority.
+	// This field is used for RemoveKey and UpdateKey AUMs.
+	KeyID KeyID `cbor:"4,keyasint,omitempty"`
+
+	// State describes the full state of the key authority.
+	// This field is used for Checkpoint AUMs.
+	// TODO(tom): Use type *State once a future PR brings in that type.
+	State interface{} `cbor:"5,keyasint,omitempty"`
+
+	// DisablementSecret is used to transmit a secret for disabling
+	// the TKA.
+	// This field is used for DisableNL AUMs.
+	DisablementSecret []byte `cbor:"6,keyasint,omitempty"`
+
+	// Votes and Meta describe properties of a key in the key authority.
+	// These fields are used for UpdateKey AUMs.
+	Votes *uint             `cbor:"7,keyasint,omitempty"`
+	Meta  map[string]string `cbor:"8,keyasint,omitempty"`
+
+	// Signatures lists the signatures over this AUM.
+	// CBOR key 23 is the last key which can be encoded as a single byte.
+	Signatures []Signature `cbor:"23,keyasint,omitempty"`
+}
+
+// StaticValidate returns a nil error if the AUM is well-formed.
+func (a *AUM) StaticValidate() error {
+	if a.Key != nil {
+		if err := a.Key.StaticValidate(); err != nil {
+			return err
+		}
+	}
+	if a.PrevAUMHash != nil && len(a.PrevAUMHash) == 0 {
+		return errors.New("absent parent must be represented by a nil slice")
+	}
+	for i, sig := range a.Signatures {
+		if len(sig.KeyID) == 0 || len(sig.Signature) != ed25519.SignatureSize {
+			return fmt.Errorf("signature %d has missing keyID or malformed signature", i)
+		}
+	}
+
+	// TODO(tom): Validate State once a future PR brings in that type.
+
+	switch a.MessageKind {
+	case AUMAddKey:
+		if a.Key == nil {
+			return errors.New("AddKey AUMs must contain a key")
+		}
+		if a.KeyID != nil || a.DisablementSecret != nil || a.State != nil || a.Votes != nil || a.Meta != nil {
+			return errors.New("AddKey AUMs may only specify a Key")
+		}
+	case AUMRemoveKey:
+		if len(a.KeyID) == 0 {
+			return errors.New("RemoveKey AUMs must specify a key ID")
+		}
+		if a.Key != nil || a.DisablementSecret != nil || a.State != nil || a.Votes != nil || a.Meta != nil {
+			return errors.New("RemoveKey AUMs may only specify a KeyID")
+		}
+	case AUMUpdateKey:
+		if len(a.KeyID) == 0 {
+			return errors.New("UpdateKey AUMs must specify a key ID")
+		}
+		if a.Meta == nil && a.Votes == nil {
+			return errors.New("UpdateKey AUMs must contain an update to votes or key metadata")
+		}
+		if a.Key != nil || a.DisablementSecret != nil || a.State != nil {
+			return errors.New("UpdateKey AUMs may only specify KeyID, Votes, and Meta")
+		}
+	case AUMCheckpoint:
+		if a.State == nil {
+			return errors.New("Checkpoint AUMs must specify the state")
+		}
+		if a.KeyID != nil || a.DisablementSecret != nil || a.Key != nil || a.Votes != nil || a.Meta != nil {
+			return errors.New("Checkpoint AUMs may only specify State")
+		}
+	case AUMDisableNL:
+		if len(a.DisablementSecret) == 0 {
+			return errors.New("DisableNL AUMs must specify a disablement secret")
+		}
+		if a.KeyID != nil || a.State != nil || a.Key != nil || a.Votes != nil || a.Meta != nil {
+			return errors.New("DisableNL AUMs may only a disablement secret")
+		}
+	}
+
+	return nil
+}
+
+// Serialize returns the given AUM in a serialized format.
+func (a *AUM) Serialize() []byte {
+	// Why CBOR and not something like JSON?
+	//
+	// The main function of an AUM is to carry signed data. Signatures are
+	// over digests, so the serialized representation must be deterministic.
+	// Further, experience with other attempts (JWS/JWT,SAML,X509 etc) has
+	// taught us that even subtle behaviors such as how you handle invalid
+	// or unrecognized fields + any invariants in subsequent re-serialization
+	// can easily lead to security-relevant logic bugs. Its certainly possible
+	// to invent a workable scheme by massaging a JSON parsing library, though
+	// profoundly unwise.
+	//
+	// CBOR is one of the few encoding schemes that are appropriate for use
+	// with signatures and has security-conscious parsing + serialization
+	// rules baked into the spec. We use the CTAP2 mode, which is well
+	// understood + widely-implemented, and already proven for use in signing
+	// assertions through its use by FIDO2 devices.
+	out := bytes.NewBuffer(make([]byte, 0, 128))
+	encoder, err := cbor.CTAP2EncOptions().EncMode()
+	if err != nil {
+		// Deterministic validation of encoding options, should
+		// never fail.
+		panic(err)
+	}
+	if err := encoder.NewEncoder(out).Encode(a); err != nil {
+		// Writing to a bytes.Buffer should never fail.
+		panic(err)
+	}
+	return out.Bytes()
+}
+
+// Hash returns a cryptographic digest of all AUM contents.
+func (a *AUM) Hash() AUMHash {
+	return blake2s.Sum256(a.Serialize())
+}
+
+// SigHash returns the cryptographic digest which a signature
+// is over.
+//
+// This is identical to Hash() except the Signatures are not
+// serialized. Without this, the hash used for signatures
+// would be circularly dependent on the signatures.
+func (a AUM) SigHash() AUMSigHash {
+	dupe := a
+	dupe.Signatures = nil
+	return blake2s.Sum256(dupe.Serialize())
+}
+
+// Parent returns the parent's AUM hash and true, or a
+// zero value and false if there was no parent.
+func (a *AUM) Parent() (h AUMHash, ok bool) {
+	if len(a.PrevAUMHash) > 0 {
+		copy(h[:], a.PrevAUMHash)
+		return h, true
+	}
+	return h, false
+}
+
+func (a *AUM) sign25519(priv ed25519.PrivateKey) {
+	key := Key{Kind: Key25519, Public: priv.Public().(ed25519.PublicKey)}
+	sigHash := a.SigHash()
+
+	a.Signatures = append(a.Signatures, Signature{
+		KeyID:     key.ID(),
+		Signature: ed25519.Sign(priv, sigHash[:]),
+	})
+}
+
+// TODO(tom): Implement Weight() once a future PR brings in the State type.
diff --git a/tka/aum_test.go b/tka/aum_test.go
new file mode 100644
index 000000000..ad8e5b971
--- /dev/null
+++ b/tka/aum_test.go
@@ -0,0 +1,197 @@
+// Copyright (c) 2022 Tailscale Inc & AUTHORS All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package tka
+
+import (
+	"bytes"
+	"testing"
+
+	"github.com/fxamacker/cbor/v2"
+	"github.com/google/go-cmp/cmp"
+)
+
+func TestSerialization(t *testing.T) {
+	uint2 := uint(2)
+
+	tcs := []struct {
+		Name   string
+		AUM    AUM
+		Expect []byte
+	}{
+		{
+			"AddKey",
+			AUM{MessageKind: AUMAddKey, Key: &Key{}},
+			[]byte{
+				0xa3, // major type 5 (map), 3 items
+				0x01, // |- major type 0 (int), value 1 (first key, MessageKind)
+				0x01, // |- major type 0 (int), value 1 (first value, AUMAddKey)
+				0x02, // |- major type 0 (int), value 2 (second key, PrevAUMHash)
+				0xf6, // |- major type 7 (val), value null (second value, nil)
+				0x03, // |- major type 0 (int), value 3 (third key, Key)
+				0xa3, // |- major type 5 (map), 3 items (type Key)
+				0x01, //    |- major type 0 (int), value 1 (first key, Kind)
+				0x00, //    |- major type 0 (int), value 0 (first value)
+				0x02, //    |- major type 0 (int), value 2 (second key, Votes)
+				0x00, //    |- major type 0 (int), value 0 (first value)
+				0x03, //    |- major type 0 (int), value 3 (third key, Public)
+				0xf6, //    |- major type 7 (val), value null (third value, nil)
+			},
+		},
+		{
+			"RemoveKey",
+			AUM{MessageKind: AUMRemoveKey, KeyID: []byte{1, 2}},
+			[]byte{
+				0xa3, // major type 5 (map), 3 items
+				0x01, // |- major type 0 (int), value 1 (first key, MessageKind)
+				0x02, // |- major type 0 (int), value 2 (first value, AUMRemoveKey)
+				0x02, // |- major type 0 (int), value 2 (second key, PrevAUMHash)
+				0xf6, // |- major type 7 (val), value null (second value, nil)
+				0x04, // |- major type 0 (int), value 4 (third key, KeyID)
+				0x42, // |- major type 2 (byte string), 2 items
+				0x01, //    |- major type 0 (int), value 1 (byte 1)
+				0x02, //    |- major type 0 (int), value 2 (byte 2)
+			},
+		},
+		{
+			"UpdateKey",
+			AUM{MessageKind: AUMUpdateKey, Votes: &uint2, KeyID: []byte{1, 2}, Meta: map[string]string{"a": "b"}},
+			[]byte{
+				0xa5, // major type 5 (map), 5 items
+				0x01, // |- major type 0 (int), value 1 (first key, MessageKind)
+				0x05, // |- major type 0 (int), value 2 (first value, AUMUpdateKey)
+				0x02, // |- major type 0 (int), value 2 (second key, PrevAUMHash)
+				0xf6, // |- major type 7 (val), value null (second value, nil)
+				0x04, // |- major type 0 (int), value 4 (third key, KeyID)
+				0x42, // |- major type 2 (byte string), 2 items
+				0x01, //    |- major type 0 (int), value 1 (byte 1)
+				0x02, //    |- major type 0 (int), value 2 (byte 2)
+				0x07, // |- major type 0 (int), value 7 (fourth key, Votes)
+				0x02, // |- major type 0 (int), value 2 (forth value, 2)
+				0x08, // |- major type 0 (int), value 8 (fifth key, Meta)
+				0xa1, // |- major type 5 (map), 1 item (map[string]string type)
+				0x61, //    |- major type 3 (text string), value 1 (first key, one byte long)
+				0x61, //       |- byte 'a'
+				0x61, //    |- major type 3 (text string), value 1 (first value, one byte long)
+				0x62, //       |- byte 'b'
+			},
+		},
+		{
+			"DisableNL",
+			AUM{MessageKind: AUMDisableNL, PrevAUMHash: []byte{1, 2}, DisablementSecret: []byte{3, 4}},
+			[]byte{
+				0xa3, // major type 5 (map), 3 items
+				0x01, // |- major type 0 (int), value 1 (first key, MessageKind)
+				0x03, // |- major type 0 (int), value 3 (first value, AUMDisableNL)
+				0x02, // |- major type 0 (int), value 2 (second key, PrevAUMHash)
+				0x42, // |- major type 2 (byte string), 2 items (second value)
+				0x01, //    |- major type 0 (int), value 1 (byte 1)
+				0x02, //    |- major type 0 (int), value 2 (byte 2)
+				0x06, // |- major type 0 (int), value 6 (third key, DisablementSecret)
+				0x42, // |- major type 2 (byte string), 2 items (third value)
+				0x03, //    |- major type 0 (int), value 3 (byte 3)
+				0x04, //    |- major type 0 (int), value 4 (byte 4)
+			},
+		},
+		// TODO(tom): Uncomment once a future PR brings in the State type.
+		// {
+		// 	"Checkpoint",
+		// 	AUM{MessageKind: AUMCheckpoint, PrevAUMHash: []byte{1, 2}, State: &State{
+		// 		LastAUMHash: []byte{3, 4},
+		// 		Keys: []Key{
+		// 			{Kind: Key25519, Public: []byte{5, 6}},
+		// 		},
+		// 	}},
+		// 	[]byte{
+		// 		0xa3, // major type 5 (map), 3 items
+		// 		0x01, // |- major type 0 (int), value 1 (first key, MessageKind)
+		// 		0x06, // |- major type 0 (int), value 6 (first value, AUMCheckpoint)
+		// 		0x02, // |- major type 0 (int), value 2 (second key, PrevAUMHash)
+		// 		0x42, // |- major type 2 (byte string), 2 items (second value)
+		// 		0x01, //    |- major type 0 (int), value 1 (byte 1)
+		// 		0x02, //    |- major type 0 (int), value 2 (byte 2)
+		// 		0x05, // |- major type 0 (int), value 5 (third key, State)
+		// 		0xa3, // |- major type 5 (map), 3 items (third value, State type)
+		// 		0x01, //    |- major type 0 (int), value 1 (first key, LastAUMHash)
+		// 		0x42, //    |- major type 2 (byte string), 2 items (first value)
+		// 		0x03, //       |- major type 0 (int), value 3 (byte 3)
+		// 		0x04, //    |- major type 0 (int), value 4 (byte 4)
+		// 		0x02, //    |- major type 0 (int), value 2 (second key, DisablementSecrets)
+		// 		0xf6, //    |- major type 7 (val), value null (second value, nil)
+		// 		0x03, //    |- major type 0 (int), value 3 (third key, Keys)
+		// 		0x81, //    |- major type 4 (array), value 1 (one item in array)
+		// 		0xa3, //       |- major type 5 (map), 3 items (Key type)
+		// 		0x01, //          |- major type 0 (int), value 1 (first key, Kind)
+		// 		0x01, //          |- major type 0 (int), value 1 (first value, Key25519)
+		// 		0x02, //          |- major type 0 (int), value 2 (second key, Votes)
+		// 		0x00, //          |- major type 0 (int), value 0 (second value, 0)
+		// 		0x03, //          |- major type 0 (int), value 3 (third key, Public)
+		// 		0x42, //          |- major type 2 (byte string), 2 items (third value)
+		// 		0x05, //             |- major type 0 (int), value 5 (byte 5)
+		// 		0x06, //             |- major type 0 (int), value 6 (byte 6)
+		// 	},
+		// },
+		{
+			"Signature",
+			AUM{MessageKind: AUMAddKey, Signatures: []Signature{{KeyID: []byte{1}}}},
+			[]byte{
+				0xa3, // major type 5 (map), 3 items
+				0x01, // |- major type 0 (int), value 1 (first key, MessageKind)
+				0x01, // |- major type 0 (int), value 1 (first value, AUMAddKey)
+				0x02, // |- major type 0 (int), value 2 (second key, PrevAUMHash)
+				0xf6, // |- major type 7 (val), value null (second value, nil)
+				0x17, // |- major type 0 (int), value 22 (third key, Signatures)
+				0x81, // |- major type 4 (array), value 1 (one item in array)
+				0xa2, //   |- major type 5 (map), 2 items (Signature type)
+				0x01, //     |- major type 0 (int), value 1 (first key, KeyID)
+				0x41, //     |- major type 2 (byte string), 1 item
+				0x01, //       |- major type 0 (int), value 1 (byte 1)
+				0x02, //     |- major type 0 (int), value 2 (second key, Signature)
+				0xf6, //     |- major type 7 (val), value null (second value, nil)
+			},
+		},
+	}
+
+	for _, tc := range tcs {
+		t.Run(tc.Name, func(t *testing.T) {
+			data := tc.AUM.Serialize()
+			if diff := cmp.Diff(tc.Expect, data); diff != "" {
+				t.Errorf("serialization differs (-want, +got):\n%s", diff)
+			}
+
+			var decodedAUM AUM
+			if err := cbor.Unmarshal(data, &decodedAUM); err != nil {
+				t.Fatalf("Unmarshal failed: %v", err)
+			}
+			if diff := cmp.Diff(tc.AUM, decodedAUM); diff != "" {
+				t.Errorf("unmarshalled version differs (-want, +got):\n%s", diff)
+			}
+		})
+	}
+}
+
+func TestAUMHashes(t *testing.T) {
+	// .Hash(): a hash over everything.
+	// .SigHash(): a hash over everything except the signatures.
+	//             The signatures are over a hash of the AUM, so
+	//             using SigHash() breaks this circularity.
+
+	aum := AUM{MessageKind: AUMAddKey, Key: &Key{Kind: Key25519}}
+	sigHash1 := aum.SigHash()
+	aumHash1 := aum.Hash()
+
+	aum.Signatures = []Signature{{KeyID: []byte{1, 2, 3, 4}}}
+	sigHash2 := aum.SigHash()
+	aumHash2 := aum.Hash()
+	if len(aum.Signatures) != 1 {
+		t.Error("signature was removed by one of the hash functions")
+	}
+
+	if !bytes.Equal(sigHash1[:], sigHash1[:]) {
+		t.Errorf("signature hash dependent on signatures!\n\t1 = %x\n\t2 = %x", sigHash1, sigHash2)
+	}
+	if bytes.Equal(aumHash1[:], aumHash2[:]) {
+		t.Error("aum hash didnt change")
+	}
+}
diff --git a/tka/key.go b/tka/key.go
new file mode 100644
index 000000000..eabdccdfb
--- /dev/null
+++ b/tka/key.go
@@ -0,0 +1,121 @@
+// Copyright (c) 2022 Tailscale Inc & AUTHORS All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package tka
+
+import (
+	"crypto/ed25519"
+	"errors"
+	"fmt"
+
+	"github.com/hdevalence/ed25519consensus"
+)
+
+// KeyKind describes the different varieties of a Key.
+type KeyKind uint8
+
+// Valid KeyKind values.
+const (
+	KeyInvalid KeyKind = iota
+	Key25519
+)
+
+func (k KeyKind) String() string {
+	switch k {
+	case KeyInvalid:
+		return "invalid"
+	case Key25519:
+		return "25519"
+	default:
+		return fmt.Sprintf("Key?<%d>", int(k))
+	}
+}
+
+// Key describes the public components of a key known to network-lock.
+type Key struct {
+	Kind KeyKind `cbor:"1,keyasint"`
+
+	// Votes describes the weight applied to signatures using this key.
+	// Weighting is used to deterministically resolve branches in the AUM
+	// chain (i.e. forks, where two AUMs exist with the same parent).
+	Votes uint `cbor:"2,keyasint"`
+
+	// Public encodes the public key of the key. For 25519 keys,
+	// this is simply the point on the curve representing the public
+	// key.
+	Public []byte `cbor:"3,keyasint"`
+
+	// Meta describes arbitrary metadata about the key. This could be
+	// used to store the name of the key, for instance.
+	Meta map[string]string `cbor:"12,keyasint,omitempty"`
+}
+
+func (k Key) ID() KeyID {
+	switch k.Kind {
+	// Because 25519 public keys are so short, we just use the 32-byte
+	// public as their 'key ID'.
+	case Key25519:
+		return KeyID(k.Public)
+	default:
+		panic("unsupported key kind")
+	}
+}
+
+const maxMetaBytes = 512
+
+func (k Key) StaticValidate() error {
+	if k.Votes > 4096 {
+		return fmt.Errorf("excessive key weight: %d > 4096", k.Votes)
+	}
+
+	// We have an arbitrary upper limit on the amount
+	// of metadata that can be associated with a key, so
+	// people don't start using it as a key-value store and
+	// causing pathological cases due to the number + size of
+	// AUMs.
+	var metaBytes uint
+	for k, v := range k.Meta {
+		metaBytes += uint(len(k) + len(v))
+	}
+	if metaBytes > maxMetaBytes {
+		return fmt.Errorf("key metadata too big (%d > %d)", metaBytes, maxMetaBytes)
+	}
+
+	switch k.Kind {
+	case Key25519:
+	default:
+		return fmt.Errorf("unrecognized key kind: %v", k.Kind)
+	}
+	return nil
+}
+
+// KeyID references a verification key stored in the key authority.
+//
+// For 25519 keys: The 32-byte public key.
+type KeyID []byte
+
+// Signature describes a signature over an AUM, which can be verified
+// using the key referenced by KeyID.
+type Signature struct {
+	KeyID     KeyID  `cbor:"1,keyasint"`
+	Signature []byte `cbor:"2,keyasint"`
+}
+
+// Verify returns a nil error if the signature is valid over the
+// provided AUM BLAKE2s digest, using the given key.
+func (s *Signature) Verify(aumDigest AUMSigHash, key Key) error {
+	// NOTE(tom): Even if we can compute the public from the KeyID,
+	//            its possible for the KeyID to be attacker-controlled
+	//            so we should use the public contained in the state machine.
+	switch key.Kind {
+	case Key25519:
+		if ed25519consensus.Verify(ed25519.PublicKey(key.Public), aumDigest[:], s.Signature) {
+			return nil
+		}
+		return errors.New("invalid signature")
+
+	default:
+		return fmt.Errorf("unhandled key type: %v", key.Kind)
+	}
+}
diff --git a/tka/key_test.go b/tka/key_test.go
new file mode 100644
index 000000000..0b8b0ee4b
--- /dev/null
+++ b/tka/key_test.go
@@ -0,0 +1,64 @@
+// Copyright (c) 2022 Tailscale Inc & AUTHORS All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package tka
+
+import (
+	"bytes"
+	"crypto/ed25519"
+	"encoding/binary"
+	"math/rand"
+	"testing"
+)
+
+// returns a random source based on the test name + extraSeed.
+func testingRand(t *testing.T, extraSeed int64) *rand.Rand {
+	var seed int64
+	if err := binary.Read(bytes.NewBuffer([]byte(t.Name())), binary.LittleEndian, &seed); err != nil {
+		panic(err)
+	}
+	return rand.New(rand.NewSource(seed + extraSeed))
+}
+
+// generates a 25519 private key based on the seed + test name.
+func testingKey25519(t *testing.T, seed int64) (ed25519.PublicKey, ed25519.PrivateKey) {
+	pub, priv, err := ed25519.GenerateKey(testingRand(t, seed))
+	if err != nil {
+		panic(err)
+	}
+	return pub, priv
+}
+
+func TestVerify25519(t *testing.T) {
+	pub, priv := testingKey25519(t, 1)
+	key := Key{
+		Kind:   Key25519,
+		Public: pub,
+	}
+
+	aum := AUM{
+		MessageKind: AUMRemoveKey,
+		KeyID:       []byte{1, 2, 3, 4},
+		// Signatures is set to crap so we are sure its ignored in the sigHash computation.
+		Signatures: []Signature{{KeyID: []byte{45, 42}}},
+	}
+	sigHash := aum.SigHash()
+	aum.Signatures = []Signature{
+		{
+			KeyID:     key.ID(),
+			Signature: ed25519.Sign(priv, sigHash[:]),
+		},
+	}
+
+	if err := aum.Signatures[0].Verify(aum.SigHash(), key); err != nil {
+		t.Errorf("signature verification failed: %v", err)
+	}
+
+	// Make sure it fails with a different public key.
+	pub2, _ := testingKey25519(t, 2)
+	key2 := Key{Kind: Key25519, Public: pub2}
+	if err := aum.Signatures[0].Verify(aum.SigHash(), key2); err == nil {
+		t.Error("signature verification with different key did not fail")
+	}
+}
diff --git a/tka/tka.go b/tka/tka.go
new file mode 100644
index 000000000..cec790d99
--- /dev/null
+++ b/tka/tka.go
@@ -0,0 +1,6 @@
+// Copyright (c) 2022 Tailscale Inc & AUTHORS All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package tka (WIP) implements the Tailnet Key Authority.
+package tka