diff options
Diffstat (limited to 'libgo/go/golang.org/x/mod/sumdb/note/note.go')
-rw-r--r-- | libgo/go/golang.org/x/mod/sumdb/note/note.go | 681 |
1 files changed, 681 insertions, 0 deletions
diff --git a/libgo/go/golang.org/x/mod/sumdb/note/note.go b/libgo/go/golang.org/x/mod/sumdb/note/note.go new file mode 100644 index 00000000000..3c8e67bc3d5 --- /dev/null +++ b/libgo/go/golang.org/x/mod/sumdb/note/note.go @@ -0,0 +1,681 @@ +// Copyright 2019 The Go 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 note defines the notes signed by the Go module database server. +// +// This package is part of a DRAFT of what the Go module database server will look like. +// Do not assume the details here are final! +// +// A note is text signed by one or more server keys. +// The text should be ignored unless the note is signed by +// a trusted server key and the signature has been verified +// using the server's public key. +// +// A server's public key is identified by a name, typically the "host[/path]" +// giving the base URL of the server's transparency log. +// The syntactic restrictions on a name are that it be non-empty, +// well-formed UTF-8 containing neither Unicode spaces nor plus (U+002B). +// +// A Go module database server signs texts using public key cryptography. +// A given server may have multiple public keys, each +// identified by the first 32 bits of the SHA-256 hash of +// the concatenation of the server name, a newline, and +// the encoded public key. +// +// Verifying Notes +// +// A Verifier allows verification of signatures by one server public key. +// It can report the name of the server and the uint32 hash of the key, +// and it can verify a purported signature by that key. +// +// The standard implementation of a Verifier is constructed +// by NewVerifier starting from a verifier key, which is a +// plain text string of the form "<name>+<hash>+<keydata>". +// +// A Verifiers allows looking up a Verifier by the combination +// of server name and key hash. +// +// The standard implementation of a Verifiers is constructed +// by VerifierList from a list of known verifiers. +// +// A Note represents a text with one or more signatures. +// An implementation can reject a note with too many signatures +// (for example, more than 100 signatures). +// +// A Signature represents a signature on a note, verified or not. +// +// The Open function takes as input a signed message +// and a set of known verifiers. It decodes and verifies +// the message signatures and returns a Note structure +// containing the message text and (verified or unverified) signatures. +// +// Signing Notes +// +// A Signer allows signing a text with a given key. +// It can report the name of the server and the hash of the key +// and can sign a raw text using that key. +// +// The standard implementation of a Signer is constructed +// by NewSigner starting from an encoded signer key, which is a +// plain text string of the form "PRIVATE+KEY+<name>+<hash>+<keydata>". +// Anyone with an encoded signer key can sign messages using that key, +// so it must be kept secret. The encoding begins with the literal text +// "PRIVATE+KEY" to avoid confusion with the public server key. +// +// The Sign function takes as input a Note and a list of Signers +// and returns an encoded, signed message. +// +// Signed Note Format +// +// A signed note consists of a text ending in newline (U+000A), +// followed by a blank line (only a newline), +// followed by one or more signature lines of this form: +// em dash (U+2014), space (U+0020), +// server name, space, base64-encoded signature, newline. +// +// Signed notes must be valid UTF-8 and must not contain any +// ASCII control characters (those below U+0020) other than newline. +// +// A signature is a base64 encoding of 4+n bytes. +// +// The first four bytes in the signature are the uint32 key hash +// stored in big-endian order, which is to say they are the first +// four bytes of the truncated SHA-256 used to derive the key hash +// in the first place. +// +// The remaining n bytes are the result of using the specified key +// to sign the note text (including the final newline but not the +// separating blank line). +// +// Generating Keys +// +// There is only one key type, Ed25519 with algorithm identifier 1. +// New key types may be introduced in the future as needed, +// although doing so will require deploying the new algorithms to all clients +// before starting to depend on them for signatures. +// +// The GenerateKey function generates and returns a new signer +// and corresponding verifier. +// +// Example +// +// Here is a well-formed signed note: +// +// If you think cryptography is the answer to your problem, +// then you don't know what your problem is. +// +// — PeterNeumann x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM= +// +// It can be constructed and displayed using: +// +// skey := "PRIVATE+KEY+PeterNeumann+c74f20a3+AYEKFALVFGyNhPJEMzD1QIDr+Y7hfZx09iUvxdXHKDFz" +// text := "If you think cryptography is the answer to your problem,\n" + +// "then you don't know what your problem is.\n" +// +// signer, err := note.NewSigner(skey) +// if err != nil { +// log.Fatal(err) +// } +// +// msg, err := note.Sign(¬e.Note{Text: text}, signer) +// if err != nil { +// log.Fatal(err) +// } +// os.Stdout.Write(msg) +// +// The note's text is two lines, including the final newline, +// and the text is purportedly signed by a server named +// "PeterNeumann". (Although server names are canonically +// base URLs, the only syntactic requirement is that they +// not contain spaces or newlines). +// +// If Open is given access to a Verifiers including the +// Verifier for this key, then it will succeed at verifiying +// the encoded message and returning the parsed Note: +// +// vkey := "PeterNeumann+c74f20a3+ARpc2QcUPDhMQegwxbzhKqiBfsVkmqq/LDE4izWy10TW" +// msg := []byte("If you think cryptography is the answer to your problem,\n" + +// "then you don't know what your problem is.\n" + +// "\n" + +// "— PeterNeumann x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM=\n") +// +// verifier, err := note.NewVerifier(vkey) +// if err != nil { +// log.Fatal(err) +// } +// verifiers := note.VerifierList(verifier) +// +// n, err := note.Open([]byte(msg), verifiers) +// if err != nil { +// log.Fatal(err) +// } +// fmt.Printf("%s (%08x):\n%s", n.Sigs[0].Name, n.Sigs[0].Hash, n.Text) +// +// You can add your own signature to this message by re-signing the note: +// +// skey, vkey, err := note.GenerateKey(rand.Reader, "EnochRoot") +// if err != nil { +// log.Fatal(err) +// } +// _ = vkey // give to verifiers +// +// me, err := note.NewSigner(skey) +// if err != nil { +// log.Fatal(err) +// } +// +// msg, err := note.Sign(n, me) +// if err != nil { +// log.Fatal(err) +// } +// os.Stdout.Write(msg) +// +// This will print a doubly-signed message, like: +// +// If you think cryptography is the answer to your problem, +// then you don't know what your problem is. +// +// — PeterNeumann x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM= +// — EnochRoot rwz+eBzmZa0SO3NbfRGzPCpDckykFXSdeX+MNtCOXm2/5n2tiOHp+vAF1aGrQ5ovTG01oOTGwnWLox33WWd1RvMc+QQ= +// +package note + +import ( + "bytes" + "crypto/sha256" + "encoding/base64" + "encoding/binary" + "errors" + "fmt" + "io" + "strconv" + "strings" + "unicode" + "unicode/utf8" + + "golang.org/x/crypto/ed25519" +) + +// A Verifier verifies messages signed with a specific key. +type Verifier interface { + // Name returns the server name associated with the key. + Name() string + + // KeyHash returns the key hash. + KeyHash() uint32 + + // Verify reports whether sig is a valid signature of msg. + Verify(msg, sig []byte) bool +} + +// A Signer signs messages using a specific key. +type Signer interface { + // Name returns the server name associated with the key. + Name() string + + // KeyHash returns the key hash. + KeyHash() uint32 + + // Sign returns a signature for the given message. + Sign(msg []byte) ([]byte, error) +} + +// keyHash computes the key hash for the given server name and encoded public key. +func keyHash(name string, key []byte) uint32 { + h := sha256.New() + h.Write([]byte(name)) + h.Write([]byte("\n")) + h.Write(key) + sum := h.Sum(nil) + return binary.BigEndian.Uint32(sum) +} + +var ( + errVerifierID = errors.New("malformed verifier id") + errVerifierAlg = errors.New("unknown verifier algorithm") + errVerifierHash = errors.New("invalid verifier hash") +) + +const ( + algEd25519 = 1 +) + +// isValidName reports whether name is valid. +// It must be non-empty and not have any Unicode spaces or pluses. +func isValidName(name string) bool { + return name != "" && utf8.ValidString(name) && strings.IndexFunc(name, unicode.IsSpace) < 0 && !strings.Contains(name, "+") +} + +// NewVerifier construct a new Verifier from an encoded verifier key. +func NewVerifier(vkey string) (Verifier, error) { + name, vkey := chop(vkey, "+") + hash16, key64 := chop(vkey, "+") + hash, err1 := strconv.ParseUint(hash16, 16, 32) + key, err2 := base64.StdEncoding.DecodeString(key64) + if len(hash16) != 8 || err1 != nil || err2 != nil || !isValidName(name) || len(key) == 0 { + return nil, errVerifierID + } + if uint32(hash) != keyHash(name, key) { + return nil, errVerifierHash + } + + v := &verifier{ + name: name, + hash: uint32(hash), + } + + alg, key := key[0], key[1:] + switch alg { + default: + return nil, errVerifierAlg + + case algEd25519: + if len(key) != 32 { + return nil, errVerifierID + } + v.verify = func(msg, sig []byte) bool { + return ed25519.Verify(key, msg, sig) + } + } + + return v, nil +} + +// chop chops s at the first instance of sep, if any, +// and returns the text before and after sep. +// If sep is not present, chop returns before is s and after is empty. +func chop(s, sep string) (before, after string) { + i := strings.Index(s, sep) + if i < 0 { + return s, "" + } + return s[:i], s[i+len(sep):] +} + +// verifier is a trivial Verifier implementation. +type verifier struct { + name string + hash uint32 + verify func([]byte, []byte) bool +} + +func (v *verifier) Name() string { return v.name } +func (v *verifier) KeyHash() uint32 { return v.hash } +func (v *verifier) Verify(msg, sig []byte) bool { return v.verify(msg, sig) } + +// NewSigner constructs a new Signer from an encoded signer key. +func NewSigner(skey string) (Signer, error) { + priv1, skey := chop(skey, "+") + priv2, skey := chop(skey, "+") + name, skey := chop(skey, "+") + hash16, key64 := chop(skey, "+") + hash, err1 := strconv.ParseUint(hash16, 16, 32) + key, err2 := base64.StdEncoding.DecodeString(key64) + if priv1 != "PRIVATE" || priv2 != "KEY" || len(hash16) != 8 || err1 != nil || err2 != nil || !isValidName(name) || len(key) == 0 { + return nil, errSignerID + } + + // Note: hash is the hash of the public key and we have the private key. + // Must verify hash after deriving public key. + + s := &signer{ + name: name, + hash: uint32(hash), + } + + var pubkey []byte + + alg, key := key[0], key[1:] + switch alg { + default: + return nil, errSignerAlg + + case algEd25519: + if len(key) != 32 { + return nil, errSignerID + } + key = ed25519.NewKeyFromSeed(key) + pubkey = append([]byte{algEd25519}, key[32:]...) + s.sign = func(msg []byte) ([]byte, error) { + return ed25519.Sign(key, msg), nil + } + } + + if uint32(hash) != keyHash(name, pubkey) { + return nil, errSignerHash + } + + return s, nil +} + +var ( + errSignerID = errors.New("malformed verifier id") + errSignerAlg = errors.New("unknown verifier algorithm") + errSignerHash = errors.New("invalid verifier hash") +) + +// signer is a trivial Signer implementation. +type signer struct { + name string + hash uint32 + sign func([]byte) ([]byte, error) +} + +func (s *signer) Name() string { return s.name } +func (s *signer) KeyHash() uint32 { return s.hash } +func (s *signer) Sign(msg []byte) ([]byte, error) { return s.sign(msg) } + +// GenerateKey generates a signer and verifier key pair for a named server. +// The signer key skey is private and must be kept secret. +func GenerateKey(rand io.Reader, name string) (skey, vkey string, err error) { + pub, priv, err := ed25519.GenerateKey(rand) + if err != nil { + return "", "", err + } + pubkey := append([]byte{algEd25519}, pub...) + privkey := append([]byte{algEd25519}, priv.Seed()...) + h := keyHash(name, pubkey) + + skey = fmt.Sprintf("PRIVATE+KEY+%s+%08x+%s", name, h, base64.StdEncoding.EncodeToString(privkey)) + vkey = fmt.Sprintf("%s+%08x+%s", name, h, base64.StdEncoding.EncodeToString(pubkey)) + return skey, vkey, nil +} + +// NewEd25519VerifierKey returns an encoded verifier key using the given name +// and Ed25519 public key. +func NewEd25519VerifierKey(name string, key ed25519.PublicKey) (string, error) { + if len(key) != ed25519.PublicKeySize { + return "", fmt.Errorf("invalid public key size %d, expected %d", len(key), ed25519.PublicKeySize) + } + + pubkey := append([]byte{algEd25519}, key...) + hash := keyHash(name, pubkey) + + b64Key := base64.StdEncoding.EncodeToString(pubkey) + return fmt.Sprintf("%s+%08x+%s", name, hash, b64Key), nil +} + +// A Verifiers is a collection of known verifier keys. +type Verifiers interface { + // Verifier returns the Verifier associated with the key + // identified by the name and hash. + // If the name, hash pair is unknown, Verifier should return + // an UnknownVerifierError. + Verifier(name string, hash uint32) (Verifier, error) +} + +// An UnknownVerifierError indicates that the given key is not known. +// The Open function records signatures without associated verifiers as +// unverified signatures. +type UnknownVerifierError struct { + Name string + KeyHash uint32 +} + +func (e *UnknownVerifierError) Error() string { + return fmt.Sprintf("unknown key %s+%08x", e.Name, e.KeyHash) +} + +// An ambiguousVerifierError indicates that the given name and hash +// match multiple keys passed to VerifierList. +// (If this happens, some malicious actor has taken control of the +// verifier list, at which point we may as well give up entirely, +// but we diagnose the problem instead.) +type ambiguousVerifierError struct { + name string + hash uint32 +} + +func (e *ambiguousVerifierError) Error() string { + return fmt.Sprintf("ambiguous key %s+%08x", e.name, e.hash) +} + +// VerifierList returns a Verifiers implementation that uses the given list of verifiers. +func VerifierList(list ...Verifier) Verifiers { + m := make(verifierMap) + for _, v := range list { + k := nameHash{v.Name(), v.KeyHash()} + m[k] = append(m[k], v) + } + return m +} + +type nameHash struct { + name string + hash uint32 +} + +type verifierMap map[nameHash][]Verifier + +func (m verifierMap) Verifier(name string, hash uint32) (Verifier, error) { + v, ok := m[nameHash{name, hash}] + if !ok { + return nil, &UnknownVerifierError{name, hash} + } + if len(v) > 1 { + return nil, &ambiguousVerifierError{name, hash} + } + return v[0], nil +} + +// A Note is a text and signatures. +type Note struct { + Text string // text of note + Sigs []Signature // verified signatures + UnverifiedSigs []Signature // unverified signatures +} + +// A Signature is a single signature found in a note. +type Signature struct { + // Name and Hash give the name and key hash + // for the key that generated the signature. + Name string + Hash uint32 + + // Base64 records the base64-encoded signature bytes. + Base64 string +} + +// An UnverifiedNoteError indicates that the note +// successfully parsed but had no verifiable signatures. +type UnverifiedNoteError struct { + Note *Note +} + +func (e *UnverifiedNoteError) Error() string { + return "note has no verifiable signatures" +} + +// An InvalidSignatureError indicates that the given key was known +// and the associated Verifier rejected the signature. +type InvalidSignatureError struct { + Name string + Hash uint32 +} + +func (e *InvalidSignatureError) Error() string { + return fmt.Sprintf("invalid signature for key %s+%08x", e.Name, e.Hash) +} + +var ( + errMalformedNote = errors.New("malformed note") + errInvalidSigner = errors.New("invalid signer") + + sigSplit = []byte("\n\n") + sigPrefix = []byte("— ") +) + +// Open opens and parses the message msg, checking signatures from the known verifiers. +// +// For each signature in the message, Open calls known.Verifier to find a verifier. +// If known.Verifier returns a verifier and the verifier accepts the signature, +// Open records the signature in the returned note's Sigs field. +// If known.Verifier returns a verifier but the verifier rejects the signature, +// Open returns an InvalidSignatureError. +// If known.Verifier returns an UnknownVerifierError, +// Open records the signature in the returned note's UnverifiedSigs field. +// If known.Verifier returns any other error, Open returns that error. +// +// If no known verifier has signed an otherwise valid note, +// Open returns an UnverifiedNoteError. +// In this case, the unverified note can be fetched from inside the error. +func Open(msg []byte, known Verifiers) (*Note, error) { + if known == nil { + // Treat nil Verifiers as empty list, to produce useful error instead of crash. + known = VerifierList() + } + + // Must have valid UTF-8 with no non-newline ASCII control characters. + for i := 0; i < len(msg); { + r, size := utf8.DecodeRune(msg[i:]) + if r < 0x20 && r != '\n' || r == utf8.RuneError && size == 1 { + return nil, errMalformedNote + } + i += size + } + + // Must end with signature block preceded by blank line. + split := bytes.LastIndex(msg, sigSplit) + if split < 0 { + return nil, errMalformedNote + } + text, sigs := msg[:split+1], msg[split+2:] + if len(sigs) == 0 || sigs[len(sigs)-1] != '\n' { + return nil, errMalformedNote + } + + n := &Note{ + Text: string(text), + } + + // Parse and verify signatures. + // Ignore duplicate signatures. + seen := make(map[nameHash]bool) + seenUnverified := make(map[string]bool) + numSig := 0 + for len(sigs) > 0 { + // Pull out next signature line. + // We know sigs[len(sigs)-1] == '\n', so IndexByte always finds one. + i := bytes.IndexByte(sigs, '\n') + line := sigs[:i] + sigs = sigs[i+1:] + + if !bytes.HasPrefix(line, sigPrefix) { + return nil, errMalformedNote + } + line = line[len(sigPrefix):] + name, b64 := chop(string(line), " ") + sig, err := base64.StdEncoding.DecodeString(b64) + if err != nil || !isValidName(name) || b64 == "" || len(sig) < 5 { + return nil, errMalformedNote + } + hash := binary.BigEndian.Uint32(sig[0:4]) + sig = sig[4:] + + if numSig++; numSig > 100 { + // Avoid spending forever parsing a note with many signatures. + return nil, errMalformedNote + } + + v, err := known.Verifier(name, hash) + if _, ok := err.(*UnknownVerifierError); ok { + // Drop repeated identical unverified signatures. + if seenUnverified[string(line)] { + continue + } + seenUnverified[string(line)] = true + n.UnverifiedSigs = append(n.UnverifiedSigs, Signature{Name: name, Hash: hash, Base64: b64}) + continue + } + if err != nil { + return nil, err + } + + // Drop repeated signatures by a single verifier. + if seen[nameHash{name, hash}] { + continue + } + seen[nameHash{name, hash}] = true + + ok := v.Verify(text, sig) + if !ok { + return nil, &InvalidSignatureError{name, hash} + } + + n.Sigs = append(n.Sigs, Signature{Name: name, Hash: hash, Base64: b64}) + } + + // Parsed and verified all the signatures. + if len(n.Sigs) == 0 { + return nil, &UnverifiedNoteError{n} + } + return n, nil +} + +// Sign signs the note with the given signers and returns the encoded message. +// The new signatures from signers are listed in the encoded message after +// the existing signatures already present in n.Sigs. +// If any signer uses the same key as an existing signature, +// the existing signature is elided from the output. +func Sign(n *Note, signers ...Signer) ([]byte, error) { + var buf bytes.Buffer + if !strings.HasSuffix(n.Text, "\n") { + return nil, errMalformedNote + } + buf.WriteString(n.Text) + + // Prepare signatures. + var sigs bytes.Buffer + have := make(map[nameHash]bool) + for _, s := range signers { + name := s.Name() + hash := s.KeyHash() + have[nameHash{name, hash}] = true + if !isValidName(name) { + return nil, errInvalidSigner + } + + sig, err := s.Sign(buf.Bytes()) // buf holds n.Text + if err != nil { + return nil, err + } + + var hbuf [4]byte + binary.BigEndian.PutUint32(hbuf[:], hash) + b64 := base64.StdEncoding.EncodeToString(append(hbuf[:], sig...)) + sigs.WriteString("— ") + sigs.WriteString(name) + sigs.WriteString(" ") + sigs.WriteString(b64) + sigs.WriteString("\n") + } + + buf.WriteString("\n") + + // Emit existing signatures not replaced by new ones. + for _, list := range [][]Signature{n.Sigs, n.UnverifiedSigs} { + for _, sig := range list { + name, hash := sig.Name, sig.Hash + if !isValidName(name) { + return nil, errMalformedNote + } + if have[nameHash{name, hash}] { + continue + } + // Double-check hash against base64. + raw, err := base64.StdEncoding.DecodeString(sig.Base64) + if err != nil || len(raw) < 4 || binary.BigEndian.Uint32(raw) != hash { + return nil, errMalformedNote + } + buf.WriteString("— ") + buf.WriteString(sig.Name) + buf.WriteString(" ") + buf.WriteString(sig.Base64) + buf.WriteString("\n") + } + } + buf.Write(sigs.Bytes()) + + return buf.Bytes(), nil +} |