1// Copyright 2019 The Go Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5// Package note defines the notes signed by the Go module database server. 6// 7// A note is text signed by one or more server keys. 8// The text should be ignored unless the note is signed by 9// a trusted server key and the signature has been verified 10// using the server's public key. 11// 12// A server's public key is identified by a name, typically the "host[/path]" 13// giving the base URL of the server's transparency log. 14// The syntactic restrictions on a name are that it be non-empty, 15// well-formed UTF-8 containing neither Unicode spaces nor plus (U+002B). 16// 17// A Go module database server signs texts using public key cryptography. 18// A given server may have multiple public keys, each 19// identified by the first 32 bits of the SHA-256 hash of 20// the concatenation of the server name, a newline, and 21// the encoded public key. 22// 23// Verifying Notes 24// 25// A Verifier allows verification of signatures by one server public key. 26// It can report the name of the server and the uint32 hash of the key, 27// and it can verify a purported signature by that key. 28// 29// The standard implementation of a Verifier is constructed 30// by NewVerifier starting from a verifier key, which is a 31// plain text string of the form "<name>+<hash>+<keydata>". 32// 33// A Verifiers allows looking up a Verifier by the combination 34// of server name and key hash. 35// 36// The standard implementation of a Verifiers is constructed 37// by VerifierList from a list of known verifiers. 38// 39// A Note represents a text with one or more signatures. 40// An implementation can reject a note with too many signatures 41// (for example, more than 100 signatures). 42// 43// A Signature represents a signature on a note, verified or not. 44// 45// The Open function takes as input a signed message 46// and a set of known verifiers. It decodes and verifies 47// the message signatures and returns a Note structure 48// containing the message text and (verified or unverified) signatures. 49// 50// Signing Notes 51// 52// A Signer allows signing a text with a given key. 53// It can report the name of the server and the hash of the key 54// and can sign a raw text using that key. 55// 56// The standard implementation of a Signer is constructed 57// by NewSigner starting from an encoded signer key, which is a 58// plain text string of the form "PRIVATE+KEY+<name>+<hash>+<keydata>". 59// Anyone with an encoded signer key can sign messages using that key, 60// so it must be kept secret. The encoding begins with the literal text 61// "PRIVATE+KEY" to avoid confusion with the public server key. 62// 63// The Sign function takes as input a Note and a list of Signers 64// and returns an encoded, signed message. 65// 66// Signed Note Format 67// 68// A signed note consists of a text ending in newline (U+000A), 69// followed by a blank line (only a newline), 70// followed by one or more signature lines of this form: 71// em dash (U+2014), space (U+0020), 72// server name, space, base64-encoded signature, newline. 73// 74// Signed notes must be valid UTF-8 and must not contain any 75// ASCII control characters (those below U+0020) other than newline. 76// 77// A signature is a base64 encoding of 4+n bytes. 78// 79// The first four bytes in the signature are the uint32 key hash 80// stored in big-endian order, which is to say they are the first 81// four bytes of the truncated SHA-256 used to derive the key hash 82// in the first place. 83// 84// The remaining n bytes are the result of using the specified key 85// to sign the note text (including the final newline but not the 86// separating blank line). 87// 88// Generating Keys 89// 90// There is only one key type, Ed25519 with algorithm identifier 1. 91// New key types may be introduced in the future as needed, 92// although doing so will require deploying the new algorithms to all clients 93// before starting to depend on them for signatures. 94// 95// The GenerateKey function generates and returns a new signer 96// and corresponding verifier. 97// 98// Example 99// 100// Here is a well-formed signed note: 101// 102// If you think cryptography is the answer to your problem, 103// then you don't know what your problem is. 104// 105// — PeterNeumann x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM= 106// 107// It can be constructed and displayed using: 108// 109// skey := "PRIVATE+KEY+PeterNeumann+c74f20a3+AYEKFALVFGyNhPJEMzD1QIDr+Y7hfZx09iUvxdXHKDFz" 110// text := "If you think cryptography is the answer to your problem,\n" + 111// "then you don't know what your problem is.\n" 112// 113// signer, err := note.NewSigner(skey) 114// if err != nil { 115// log.Fatal(err) 116// } 117// 118// msg, err := note.Sign(¬e.Note{Text: text}, signer) 119// if err != nil { 120// log.Fatal(err) 121// } 122// os.Stdout.Write(msg) 123// 124// The note's text is two lines, including the final newline, 125// and the text is purportedly signed by a server named 126// "PeterNeumann". (Although server names are canonically 127// base URLs, the only syntactic requirement is that they 128// not contain spaces or newlines). 129// 130// If Open is given access to a Verifiers including the 131// Verifier for this key, then it will succeed at verifiying 132// the encoded message and returning the parsed Note: 133// 134// vkey := "PeterNeumann+c74f20a3+ARpc2QcUPDhMQegwxbzhKqiBfsVkmqq/LDE4izWy10TW" 135// msg := []byte("If you think cryptography is the answer to your problem,\n" + 136// "then you don't know what your problem is.\n" + 137// "\n" + 138// "— PeterNeumann x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM=\n") 139// 140// verifier, err := note.NewVerifier(vkey) 141// if err != nil { 142// log.Fatal(err) 143// } 144// verifiers := note.VerifierList(verifier) 145// 146// n, err := note.Open([]byte(msg), verifiers) 147// if err != nil { 148// log.Fatal(err) 149// } 150// fmt.Printf("%s (%08x):\n%s", n.Sigs[0].Name, n.Sigs[0].Hash, n.Text) 151// 152// You can add your own signature to this message by re-signing the note: 153// 154// skey, vkey, err := note.GenerateKey(rand.Reader, "EnochRoot") 155// if err != nil { 156// log.Fatal(err) 157// } 158// _ = vkey // give to verifiers 159// 160// me, err := note.NewSigner(skey) 161// if err != nil { 162// log.Fatal(err) 163// } 164// 165// msg, err := note.Sign(n, me) 166// if err != nil { 167// log.Fatal(err) 168// } 169// os.Stdout.Write(msg) 170// 171// This will print a doubly-signed message, like: 172// 173// If you think cryptography is the answer to your problem, 174// then you don't know what your problem is. 175// 176// — PeterNeumann x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM= 177// — EnochRoot rwz+eBzmZa0SO3NbfRGzPCpDckykFXSdeX+MNtCOXm2/5n2tiOHp+vAF1aGrQ5ovTG01oOTGwnWLox33WWd1RvMc+QQ= 178// 179package note 180 181import ( 182 "bytes" 183 "crypto/sha256" 184 "encoding/base64" 185 "encoding/binary" 186 "errors" 187 "fmt" 188 "io" 189 "strconv" 190 "strings" 191 "unicode" 192 "unicode/utf8" 193 194 "golang.org/x/crypto/ed25519" 195) 196 197// A Verifier verifies messages signed with a specific key. 198type Verifier interface { 199 // Name returns the server name associated with the key. 200 Name() string 201 202 // KeyHash returns the key hash. 203 KeyHash() uint32 204 205 // Verify reports whether sig is a valid signature of msg. 206 Verify(msg, sig []byte) bool 207} 208 209// A Signer signs messages using a specific key. 210type Signer interface { 211 // Name returns the server name associated with the key. 212 Name() string 213 214 // KeyHash returns the key hash. 215 KeyHash() uint32 216 217 // Sign returns a signature for the given message. 218 Sign(msg []byte) ([]byte, error) 219} 220 221// keyHash computes the key hash for the given server name and encoded public key. 222func keyHash(name string, key []byte) uint32 { 223 h := sha256.New() 224 h.Write([]byte(name)) 225 h.Write([]byte("\n")) 226 h.Write(key) 227 sum := h.Sum(nil) 228 return binary.BigEndian.Uint32(sum) 229} 230 231var ( 232 errVerifierID = errors.New("malformed verifier id") 233 errVerifierAlg = errors.New("unknown verifier algorithm") 234 errVerifierHash = errors.New("invalid verifier hash") 235) 236 237const ( 238 algEd25519 = 1 239) 240 241// isValidName reports whether name is valid. 242// It must be non-empty and not have any Unicode spaces or pluses. 243func isValidName(name string) bool { 244 return name != "" && utf8.ValidString(name) && strings.IndexFunc(name, unicode.IsSpace) < 0 && !strings.Contains(name, "+") 245} 246 247// NewVerifier construct a new Verifier from an encoded verifier key. 248func NewVerifier(vkey string) (Verifier, error) { 249 name, vkey := chop(vkey, "+") 250 hash16, key64 := chop(vkey, "+") 251 hash, err1 := strconv.ParseUint(hash16, 16, 32) 252 key, err2 := base64.StdEncoding.DecodeString(key64) 253 if len(hash16) != 8 || err1 != nil || err2 != nil || !isValidName(name) || len(key) == 0 { 254 return nil, errVerifierID 255 } 256 if uint32(hash) != keyHash(name, key) { 257 return nil, errVerifierHash 258 } 259 260 v := &verifier{ 261 name: name, 262 hash: uint32(hash), 263 } 264 265 alg, key := key[0], key[1:] 266 switch alg { 267 default: 268 return nil, errVerifierAlg 269 270 case algEd25519: 271 if len(key) != 32 { 272 return nil, errVerifierID 273 } 274 v.verify = func(msg, sig []byte) bool { 275 return ed25519.Verify(key, msg, sig) 276 } 277 } 278 279 return v, nil 280} 281 282// chop chops s at the first instance of sep, if any, 283// and returns the text before and after sep. 284// If sep is not present, chop returns before is s and after is empty. 285func chop(s, sep string) (before, after string) { 286 i := strings.Index(s, sep) 287 if i < 0 { 288 return s, "" 289 } 290 return s[:i], s[i+len(sep):] 291} 292 293// verifier is a trivial Verifier implementation. 294type verifier struct { 295 name string 296 hash uint32 297 verify func([]byte, []byte) bool 298} 299 300func (v *verifier) Name() string { return v.name } 301func (v *verifier) KeyHash() uint32 { return v.hash } 302func (v *verifier) Verify(msg, sig []byte) bool { return v.verify(msg, sig) } 303 304// NewSigner constructs a new Signer from an encoded signer key. 305func NewSigner(skey string) (Signer, error) { 306 priv1, skey := chop(skey, "+") 307 priv2, skey := chop(skey, "+") 308 name, skey := chop(skey, "+") 309 hash16, key64 := chop(skey, "+") 310 hash, err1 := strconv.ParseUint(hash16, 16, 32) 311 key, err2 := base64.StdEncoding.DecodeString(key64) 312 if priv1 != "PRIVATE" || priv2 != "KEY" || len(hash16) != 8 || err1 != nil || err2 != nil || !isValidName(name) || len(key) == 0 { 313 return nil, errSignerID 314 } 315 316 // Note: hash is the hash of the public key and we have the private key. 317 // Must verify hash after deriving public key. 318 319 s := &signer{ 320 name: name, 321 hash: uint32(hash), 322 } 323 324 var pubkey []byte 325 326 alg, key := key[0], key[1:] 327 switch alg { 328 default: 329 return nil, errSignerAlg 330 331 case algEd25519: 332 if len(key) != 32 { 333 return nil, errSignerID 334 } 335 key = ed25519.NewKeyFromSeed(key) 336 pubkey = append([]byte{algEd25519}, key[32:]...) 337 s.sign = func(msg []byte) ([]byte, error) { 338 return ed25519.Sign(key, msg), nil 339 } 340 } 341 342 if uint32(hash) != keyHash(name, pubkey) { 343 return nil, errSignerHash 344 } 345 346 return s, nil 347} 348 349var ( 350 errSignerID = errors.New("malformed verifier id") 351 errSignerAlg = errors.New("unknown verifier algorithm") 352 errSignerHash = errors.New("invalid verifier hash") 353) 354 355// signer is a trivial Signer implementation. 356type signer struct { 357 name string 358 hash uint32 359 sign func([]byte) ([]byte, error) 360} 361 362func (s *signer) Name() string { return s.name } 363func (s *signer) KeyHash() uint32 { return s.hash } 364func (s *signer) Sign(msg []byte) ([]byte, error) { return s.sign(msg) } 365 366// GenerateKey generates a signer and verifier key pair for a named server. 367// The signer key skey is private and must be kept secret. 368func GenerateKey(rand io.Reader, name string) (skey, vkey string, err error) { 369 pub, priv, err := ed25519.GenerateKey(rand) 370 if err != nil { 371 return "", "", err 372 } 373 pubkey := append([]byte{algEd25519}, pub...) 374 privkey := append([]byte{algEd25519}, priv.Seed()...) 375 h := keyHash(name, pubkey) 376 377 skey = fmt.Sprintf("PRIVATE+KEY+%s+%08x+%s", name, h, base64.StdEncoding.EncodeToString(privkey)) 378 vkey = fmt.Sprintf("%s+%08x+%s", name, h, base64.StdEncoding.EncodeToString(pubkey)) 379 return skey, vkey, nil 380} 381 382// NewEd25519VerifierKey returns an encoded verifier key using the given name 383// and Ed25519 public key. 384func NewEd25519VerifierKey(name string, key ed25519.PublicKey) (string, error) { 385 if len(key) != ed25519.PublicKeySize { 386 return "", fmt.Errorf("invalid public key size %d, expected %d", len(key), ed25519.PublicKeySize) 387 } 388 389 pubkey := append([]byte{algEd25519}, key...) 390 hash := keyHash(name, pubkey) 391 392 b64Key := base64.StdEncoding.EncodeToString(pubkey) 393 return fmt.Sprintf("%s+%08x+%s", name, hash, b64Key), nil 394} 395 396// A Verifiers is a collection of known verifier keys. 397type Verifiers interface { 398 // Verifier returns the Verifier associated with the key 399 // identified by the name and hash. 400 // If the name, hash pair is unknown, Verifier should return 401 // an UnknownVerifierError. 402 Verifier(name string, hash uint32) (Verifier, error) 403} 404 405// An UnknownVerifierError indicates that the given key is not known. 406// The Open function records signatures without associated verifiers as 407// unverified signatures. 408type UnknownVerifierError struct { 409 Name string 410 KeyHash uint32 411} 412 413func (e *UnknownVerifierError) Error() string { 414 return fmt.Sprintf("unknown key %s+%08x", e.Name, e.KeyHash) 415} 416 417// An ambiguousVerifierError indicates that the given name and hash 418// match multiple keys passed to VerifierList. 419// (If this happens, some malicious actor has taken control of the 420// verifier list, at which point we may as well give up entirely, 421// but we diagnose the problem instead.) 422type ambiguousVerifierError struct { 423 name string 424 hash uint32 425} 426 427func (e *ambiguousVerifierError) Error() string { 428 return fmt.Sprintf("ambiguous key %s+%08x", e.name, e.hash) 429} 430 431// VerifierList returns a Verifiers implementation that uses the given list of verifiers. 432func VerifierList(list ...Verifier) Verifiers { 433 m := make(verifierMap) 434 for _, v := range list { 435 k := nameHash{v.Name(), v.KeyHash()} 436 m[k] = append(m[k], v) 437 } 438 return m 439} 440 441type nameHash struct { 442 name string 443 hash uint32 444} 445 446type verifierMap map[nameHash][]Verifier 447 448func (m verifierMap) Verifier(name string, hash uint32) (Verifier, error) { 449 v, ok := m[nameHash{name, hash}] 450 if !ok { 451 return nil, &UnknownVerifierError{name, hash} 452 } 453 if len(v) > 1 { 454 return nil, &ambiguousVerifierError{name, hash} 455 } 456 return v[0], nil 457} 458 459// A Note is a text and signatures. 460type Note struct { 461 Text string // text of note 462 Sigs []Signature // verified signatures 463 UnverifiedSigs []Signature // unverified signatures 464} 465 466// A Signature is a single signature found in a note. 467type Signature struct { 468 // Name and Hash give the name and key hash 469 // for the key that generated the signature. 470 Name string 471 Hash uint32 472 473 // Base64 records the base64-encoded signature bytes. 474 Base64 string 475} 476 477// An UnverifiedNoteError indicates that the note 478// successfully parsed but had no verifiable signatures. 479type UnverifiedNoteError struct { 480 Note *Note 481} 482 483func (e *UnverifiedNoteError) Error() string { 484 return "note has no verifiable signatures" 485} 486 487// An InvalidSignatureError indicates that the given key was known 488// and the associated Verifier rejected the signature. 489type InvalidSignatureError struct { 490 Name string 491 Hash uint32 492} 493 494func (e *InvalidSignatureError) Error() string { 495 return fmt.Sprintf("invalid signature for key %s+%08x", e.Name, e.Hash) 496} 497 498var ( 499 errMalformedNote = errors.New("malformed note") 500 errInvalidSigner = errors.New("invalid signer") 501 502 sigSplit = []byte("\n\n") 503 sigPrefix = []byte("— ") 504) 505 506// Open opens and parses the message msg, checking signatures from the known verifiers. 507// 508// For each signature in the message, Open calls known.Verifier to find a verifier. 509// If known.Verifier returns a verifier and the verifier accepts the signature, 510// Open records the signature in the returned note's Sigs field. 511// If known.Verifier returns a verifier but the verifier rejects the signature, 512// Open returns an InvalidSignatureError. 513// If known.Verifier returns an UnknownVerifierError, 514// Open records the signature in the returned note's UnverifiedSigs field. 515// If known.Verifier returns any other error, Open returns that error. 516// 517// If no known verifier has signed an otherwise valid note, 518// Open returns an UnverifiedNoteError. 519// In this case, the unverified note can be fetched from inside the error. 520func Open(msg []byte, known Verifiers) (*Note, error) { 521 if known == nil { 522 // Treat nil Verifiers as empty list, to produce useful error instead of crash. 523 known = VerifierList() 524 } 525 526 // Must have valid UTF-8 with no non-newline ASCII control characters. 527 for i := 0; i < len(msg); { 528 r, size := utf8.DecodeRune(msg[i:]) 529 if r < 0x20 && r != '\n' || r == utf8.RuneError && size == 1 { 530 return nil, errMalformedNote 531 } 532 i += size 533 } 534 535 // Must end with signature block preceded by blank line. 536 split := bytes.LastIndex(msg, sigSplit) 537 if split < 0 { 538 return nil, errMalformedNote 539 } 540 text, sigs := msg[:split+1], msg[split+2:] 541 if len(sigs) == 0 || sigs[len(sigs)-1] != '\n' { 542 return nil, errMalformedNote 543 } 544 545 n := &Note{ 546 Text: string(text), 547 } 548 549 // Parse and verify signatures. 550 // Ignore duplicate signatures. 551 seen := make(map[nameHash]bool) 552 seenUnverified := make(map[string]bool) 553 numSig := 0 554 for len(sigs) > 0 { 555 // Pull out next signature line. 556 // We know sigs[len(sigs)-1] == '\n', so IndexByte always finds one. 557 i := bytes.IndexByte(sigs, '\n') 558 line := sigs[:i] 559 sigs = sigs[i+1:] 560 561 if !bytes.HasPrefix(line, sigPrefix) { 562 return nil, errMalformedNote 563 } 564 line = line[len(sigPrefix):] 565 name, b64 := chop(string(line), " ") 566 sig, err := base64.StdEncoding.DecodeString(b64) 567 if err != nil || !isValidName(name) || b64 == "" || len(sig) < 5 { 568 return nil, errMalformedNote 569 } 570 hash := binary.BigEndian.Uint32(sig[0:4]) 571 sig = sig[4:] 572 573 if numSig++; numSig > 100 { 574 // Avoid spending forever parsing a note with many signatures. 575 return nil, errMalformedNote 576 } 577 578 v, err := known.Verifier(name, hash) 579 if _, ok := err.(*UnknownVerifierError); ok { 580 // Drop repeated identical unverified signatures. 581 if seenUnverified[string(line)] { 582 continue 583 } 584 seenUnverified[string(line)] = true 585 n.UnverifiedSigs = append(n.UnverifiedSigs, Signature{Name: name, Hash: hash, Base64: b64}) 586 continue 587 } 588 if err != nil { 589 return nil, err 590 } 591 592 // Drop repeated signatures by a single verifier. 593 if seen[nameHash{name, hash}] { 594 continue 595 } 596 seen[nameHash{name, hash}] = true 597 598 ok := v.Verify(text, sig) 599 if !ok { 600 return nil, &InvalidSignatureError{name, hash} 601 } 602 603 n.Sigs = append(n.Sigs, Signature{Name: name, Hash: hash, Base64: b64}) 604 } 605 606 // Parsed and verified all the signatures. 607 if len(n.Sigs) == 0 { 608 return nil, &UnverifiedNoteError{n} 609 } 610 return n, nil 611} 612 613// Sign signs the note with the given signers and returns the encoded message. 614// The new signatures from signers are listed in the encoded message after 615// the existing signatures already present in n.Sigs. 616// If any signer uses the same key as an existing signature, 617// the existing signature is elided from the output. 618func Sign(n *Note, signers ...Signer) ([]byte, error) { 619 var buf bytes.Buffer 620 if !strings.HasSuffix(n.Text, "\n") { 621 return nil, errMalformedNote 622 } 623 buf.WriteString(n.Text) 624 625 // Prepare signatures. 626 var sigs bytes.Buffer 627 have := make(map[nameHash]bool) 628 for _, s := range signers { 629 name := s.Name() 630 hash := s.KeyHash() 631 have[nameHash{name, hash}] = true 632 if !isValidName(name) { 633 return nil, errInvalidSigner 634 } 635 636 sig, err := s.Sign(buf.Bytes()) // buf holds n.Text 637 if err != nil { 638 return nil, err 639 } 640 641 var hbuf [4]byte 642 binary.BigEndian.PutUint32(hbuf[:], hash) 643 b64 := base64.StdEncoding.EncodeToString(append(hbuf[:], sig...)) 644 sigs.WriteString("— ") 645 sigs.WriteString(name) 646 sigs.WriteString(" ") 647 sigs.WriteString(b64) 648 sigs.WriteString("\n") 649 } 650 651 buf.WriteString("\n") 652 653 // Emit existing signatures not replaced by new ones. 654 for _, list := range [][]Signature{n.Sigs, n.UnverifiedSigs} { 655 for _, sig := range list { 656 name, hash := sig.Name, sig.Hash 657 if !isValidName(name) { 658 return nil, errMalformedNote 659 } 660 if have[nameHash{name, hash}] { 661 continue 662 } 663 // Double-check hash against base64. 664 raw, err := base64.StdEncoding.DecodeString(sig.Base64) 665 if err != nil || len(raw) < 4 || binary.BigEndian.Uint32(raw) != hash { 666 return nil, errMalformedNote 667 } 668 buf.WriteString("— ") 669 buf.WriteString(sig.Name) 670 buf.WriteString(" ") 671 buf.WriteString(sig.Base64) 672 buf.WriteString("\n") 673 } 674 } 675 buf.Write(sigs.Bytes()) 676 677 return buf.Bytes(), nil 678} 679