1// Copyright 2015 Keybase, Inc. All rights reserved. Use of 2// this source code is governed by the included BSD license. 3 4package libkb 5 6import ( 7 "crypto/sha256" 8 "crypto/sha512" 9 "crypto/subtle" 10 "encoding/hex" 11 "encoding/json" 12 "errors" 13 "fmt" 14 "math" 15 "strings" 16 "sync" 17 "time" 18 19 chat1 "github.com/keybase/client/go/protocol/chat1" 20 keybase1 "github.com/keybase/client/go/protocol/keybase1" 21 "github.com/keybase/client/go/sig3" 22 jsonw "github.com/keybase/go-jsonw" 23) 24 25const ( 26 NodeHashLenLong = sha512.Size // = 64 27 NodeHashLenShort = sha256.Size // = 32 28) 29 30type NodeHash interface { 31 Check(s string) bool // Check if the node hashes to this string 32 String() string 33 bytes() []byte 34 IsNil() bool 35 Eq(h NodeHash) bool 36} 37 38type NodeHashShort [NodeHashLenShort]byte 39type NodeHashLong [NodeHashLenLong]byte 40 41// NodeHashAny incorporates either a short (256-bit) or a long (512-bit) hash. 42// It's unfortunate we need it, but I didn't see any other way to use the 43// Go json marshal/unmarshal system where the hashes might be either short 44// or long. Our hacky solution is to have a union-type struct that supports 45// both, and just to unmarshal into the relevant field. Note this 46// type also fits ths NodeHash interface. 47type NodeHashAny struct { 48 s *NodeHashShort 49 l *NodeHashLong 50} 51 52var _ NodeHash = NodeHashShort{} 53var _ NodeHash = NodeHashLong{} 54var _ NodeHash = NodeHashAny{} 55 56func (h1 NodeHashShort) Check(s string) bool { 57 h2 := sha256.Sum256([]byte(s)) 58 return subtle.ConstantTimeCompare(h1[:], h2[:]) == 1 59} 60 61func (h1 NodeHashShort) String() string { 62 return hex.EncodeToString(h1[:]) 63} 64 65func (h1 NodeHashShort) bytes() []byte { 66 return h1[:] 67} 68 69func (h1 NodeHashShort) IsNil() bool { 70 return false 71} 72 73func (h1 NodeHashShort) Eq(h2 NodeHash) bool { 74 return subtle.ConstantTimeCompare(h1.bytes(), h2.bytes()) == 1 75} 76 77func (h1 NodeHashShort) ExportToHashMeta() keybase1.HashMeta { 78 return keybase1.HashMeta(h1.bytes()) 79} 80 81func (h1 NodeHashLong) Check(s string) bool { 82 h2 := sha512.Sum512([]byte(s)) 83 return subtle.ConstantTimeCompare(h1[:], h2[:]) == 1 84} 85 86func (h1 NodeHashLong) String() string { 87 return hex.EncodeToString(h1[:]) 88} 89 90func (h1 NodeHashLong) bytes() []byte { 91 return h1[:] 92} 93 94func (h1 NodeHashLong) IsNil() bool { 95 return false 96} 97 98func (h1 NodeHashLong) Eq(h2 NodeHash) bool { 99 return subtle.ConstantTimeCompare(h1.bytes(), h2.bytes()) == 1 100} 101 102func hashEq(h1 NodeHash, h2 NodeHash) bool { 103 b1 := h1.bytes() 104 b2 := h2.bytes() 105 return subtle.ConstantTimeCompare(b1, b2) == 1 106} 107 108func (h NodeHashAny) Check(s string) bool { 109 switch { 110 case h.s != nil: 111 return h.s.Check(s) 112 case h.l != nil: 113 return h.l.Check(s) 114 default: 115 return false 116 } 117} 118 119func (h NodeHashAny) String() string { 120 switch { 121 case h.s != nil: 122 return h.s.String() 123 case h.l != nil: 124 return h.l.String() 125 default: 126 return "" 127 } 128} 129 130func (h NodeHashAny) bytes() []byte { 131 switch { 132 case h.s != nil: 133 return h.s.bytes() 134 case h.l != nil: 135 return h.l.bytes() 136 default: 137 return nil 138 } 139} 140 141func (h NodeHashAny) Eq(h2 NodeHash) bool { 142 return subtle.ConstantTimeCompare(h.bytes(), h2.bytes()) == 1 143} 144 145func (h *NodeHashAny) UnmarshalJSON(b []byte) error { 146 s := keybase1.Unquote(b) 147 148 // empty strings are OK, to mean no hash available 149 if len(s) == 0 { 150 return nil 151 } 152 153 g, err := NodeHashFromHex(s) 154 if err != nil { 155 return err 156 } 157 switch g := g.(type) { 158 case NodeHashShort: 159 h.s = &g 160 case NodeHashLong: 161 h.l = &g 162 default: 163 return errors.New("unknown hash type") 164 } 165 return nil 166} 167 168func (h NodeHashAny) IsNil() bool { 169 return h.s == nil && h.l == nil 170} 171 172func (h1 *NodeHashShort) UnmarshalJSON(b []byte) error { 173 s := keybase1.Unquote(b) 174 // empty strings are OK, to mean no hash available 175 if len(s) == 0 { 176 return nil 177 } 178 g, err := NodeHashFromHex(s) 179 if err != nil { 180 return err 181 } 182 if ret, ok := g.(NodeHashShort); ok { 183 *h1 = ret 184 return nil 185 } 186 return errors.New("bad SHA256 hash") 187} 188 189func (h1 *NodeHashLong) UnmarshalJSON(b []byte) error { 190 s := keybase1.Unquote(b) 191 // empty strings are OK, to mean no hash available 192 if len(s) == 0 { 193 return nil 194 } 195 g, err := NodeHashFromHex(s) 196 if err != nil { 197 return err 198 } 199 if ret, ok := g.(NodeHashLong); ok { 200 *h1 = ret 201 return nil 202 } 203 return errors.New("bad SHA512hash") 204} 205 206func (h *NodeHashAny) MarshalJSON() ([]byte, error) { 207 s := h.String() 208 if len(s) == 0 { 209 return nil, nil 210 } 211 return keybase1.Quote(s), nil 212} 213 214type MerkleClientInterface interface { 215 CanExamineHistoricalRoot(m MetaContext, q keybase1.Seqno) bool 216 FetchRootFromServerByMinSeqno(m MetaContext, lowerBound keybase1.Seqno) (mr *MerkleRoot, err error) 217 FetchRootFromServer(m MetaContext, freshness time.Duration) (mr *MerkleRoot, err error) 218 FirstExaminableHistoricalRoot(m MetaContext) *keybase1.Seqno 219 FirstMainRootWithHiddenRootHash(m MetaContext) (s keybase1.Seqno, err error) 220 LastRoot(m MetaContext) *MerkleRoot 221 LastRootToSigJSON(m MetaContext) (ret *jsonw.Wrapper, err error) 222 LookupLeafAtHashMeta(m MetaContext, leafID keybase1.UserOrTeamID, hm keybase1.HashMeta) (leaf *MerkleGenericLeaf, err error) 223 LookupLeafAtSeqno(m MetaContext, leafID keybase1.UserOrTeamID, s keybase1.Seqno) (leaf *MerkleGenericLeaf, root *MerkleRoot, err error) 224 LookupLeafAtSeqnoForAudit(m MetaContext, leafID keybase1.UserOrTeamID, s keybase1.Seqno, processHiddenRespFunc ProcessHiddenRespFunc) (leaf *MerkleGenericLeaf, root *MerkleRoot, hiddenResp *MerkleHiddenResponse, err error) 225 LookupRootAtSeqno(m MetaContext, s keybase1.Seqno) (root *MerkleRoot, err error) 226 LookupTeam(m MetaContext, teamID keybase1.TeamID) (leaf *MerkleTeamLeaf, err error) 227 LookupTeamWithHidden(m MetaContext, teamID keybase1.TeamID, processHiddenRespFunc ProcessHiddenRespFunc) (leaf *MerkleTeamLeaf, hiddenResp *MerkleHiddenResponse, lastMerkleRoot *MerkleRoot, err error) 228 LookupUser(m MetaContext, q HTTPArgs, sigHints *SigHints, opts MerkleOpts) (u *MerkleUserLeaf, err error) 229} 230 231type MerkleClient struct { 232 Contextified 233 234 // protects whole object 235 // 236 // Warning: Never grab the latestRootLock while holding this lock, as the 237 // opposite happens and so you might introduce deadlocks. 238 sync.RWMutex 239 240 keyring *SpecialKeyRing 241 242 // The most recently-available root 243 lastRoot *MerkleRoot 244 245 // The first node we saw that has skip pointers; not used in production 246 firstSkip *keybase1.Seqno 247 248 // The first merkle root that contains the root of the hidden merkle tree 249 firstRootWithHidden keybase1.Seqno 250 251 // latestRootLock ensures that only one API call to fetch the latest merkle 252 // root is in flight at a time. These calls are expensive and would almost 253 // always get the same answer when concurrent. 254 // 255 // Warning: it is ok, to grab the object Lock while holding this one, but do 256 // not ever go the other way around, or you are risking deadlocks. 257 latestRootLock sync.Mutex 258} 259 260var _ MerkleClientInterface = (*MerkleClient)(nil) 261 262type MerkleRoot struct { 263 sigs *jsonw.Wrapper 264 payload MerkleRootPayload 265 fetched time.Time 266} 267 268func (mr MerkleRoot) HashMeta() keybase1.HashMeta { 269 return mr.ShortHash().ExportToHashMeta() 270} 271 272func (mr MerkleRoot) IsNil() bool { 273 return mr == MerkleRoot{} 274} 275 276type SkipSequence []MerkleRootPayload 277 278type MerkleTriple struct { 279 Seqno keybase1.Seqno `json:"seqno"` 280 LinkID LinkID `json:"id"` 281 SigID keybase1.SigIDBase `json:"sigid,omitempty"` 282} 283 284type MerkleUserLeaf struct { 285 public *MerkleTriple 286 private *MerkleTriple 287 idVersion int64 288 username string 289 uid keybase1.UID 290 eldest keybase1.KID // may be empty 291 resets *MerkleResets 292} 293 294type MerkleTeamLeaf struct { 295 TeamID keybase1.TeamID 296 Public *MerkleTriple 297 Private *MerkleTriple 298} 299 300type MerkleGenericLeaf struct { 301 LeafID keybase1.UserOrTeamID 302 Public *MerkleTriple 303 Private *MerkleTriple 304 305 // if the leaf is a User leaf, we'll have extra information here, like 306 // reset chain and eldest key. On a team leaf, this will be nil. 307 userExtras *MerkleUserLeaf 308} 309 310func (l MerkleTeamLeaf) MerkleGenericLeaf() *MerkleGenericLeaf { 311 return &MerkleGenericLeaf{ 312 LeafID: l.TeamID.AsUserOrTeam(), 313 Public: l.Public, 314 Private: l.Private, 315 } 316} 317 318func (mul MerkleUserLeaf) MerkleGenericLeaf() *MerkleGenericLeaf { 319 return &MerkleGenericLeaf{ 320 LeafID: mul.uid.AsUserOrTeam(), 321 Public: mul.public, 322 Private: mul.private, 323 userExtras: &mul, 324 } 325} 326 327func (l MerkleGenericLeaf) PartialClone() MerkleGenericLeaf { 328 ret := MerkleGenericLeaf{LeafID: l.LeafID} 329 if l.Public != nil { 330 tmp := *l.Public 331 ret.Public = &tmp 332 } 333 if l.Private != nil { 334 tmp := *l.Private 335 ret.Private = &tmp 336 } 337 return ret 338} 339 340type PathSteps []*PathStep 341 342type merkleUserInfoT struct { 343 uid keybase1.UID 344 uidPath PathSteps 345 idVersion int64 346 username string 347 usernameCased string 348 unverifiedResetChain unverifiedResetChain 349} 350 351type VerificationPath struct { 352 Contextified 353 root *MerkleRoot 354 path PathSteps 355} 356 357type MerkleRootPayload struct { 358 packed string 359 unpacked *MerkleRootPayloadUnpacked 360} 361 362func (mrp MerkleRootPayload) shortHash() NodeHashShort { 363 return sha256.Sum256([]byte(mrp.packed)) 364} 365 366func (mrp MerkleRootPayload) hasSkips() bool { 367 tab := mrp.unpacked.Body.Skips 368 return tab != nil && len(tab) > 0 369} 370 371type MerkleRootPayloadUnpacked struct { 372 Body struct { 373 Kbfs struct { 374 Private struct { 375 Root keybase1.KBFSRootHash `json:"root"` 376 Version *keybase1.Seqno `json:"version"` 377 } `json:"private"` 378 Public struct { 379 Root keybase1.KBFSRootHash `json:"root"` 380 Version *keybase1.Seqno `json:"version"` 381 } `json:"public"` 382 PrivateTeam struct { 383 Root keybase1.KBFSRootHash `json:"root"` 384 Version *keybase1.Seqno `json:"version"` 385 } `json:"privateteam"` 386 } `json:"kbfs"` 387 LegacyUIDRoot NodeHashShort `json:"legacy_uid_root"` 388 Prev NodeHashLong `json:"prev"` 389 Root NodeHashLong `json:"root"` 390 Seqno keybase1.Seqno `json:"seqno"` 391 Skips SkipTable `json:"skips"` 392 Txid string `json:"txid"` 393 Type string `json:"type"` 394 Version int `json:"version"` 395 PvlHash string `json:"pvl_hash"` 396 ProofServicesHash string `json:"proof_services_hash"` 397 ExternalURLHash string `json:"external_urls_hash"` 398 BlindMerkleRootHash string `json:"blind_merkle_root_hash"` 399 } `json:"body"` 400 Ctime int64 `json:"ctime"` 401 Tag string `json:"tag"` 402} 403 404type SkipTable map[keybase1.Seqno]NodeHashAny 405 406type PathStep struct { 407 prefix string 408 node string // The JSON-stringified version of the node (to be unpacked lazily) 409} 410 411func (mt MerkleTriple) Eq(mt2 MerkleTriple) bool { 412 return mt.Seqno == mt2.Seqno && mt.LinkID.Eq(mt2.LinkID) && mt.SigID.Eq(mt2.SigID) 413} 414 415func (mul MerkleUserLeaf) Public() *MerkleTriple { 416 return mul.public 417} 418 419func NodeHashFromHex(s string) (NodeHash, error) { 420 switch hex.DecodedLen(len(s)) { 421 case NodeHashLenLong: 422 var buf NodeHashLong 423 err := DecodeHexFixed(buf[:], []byte(s)) 424 if err != nil { 425 return nil, err 426 } 427 return buf, err 428 case NodeHashLenShort: 429 var buf NodeHashShort 430 err := DecodeHexFixed(buf[:], []byte(s)) 431 if err != nil { 432 return nil, err 433 } 434 return buf, err 435 default: 436 return nil, fmt.Errorf("Bad NodeHash; wrong length: %d", len(s)) 437 } 438} 439 440func GetNodeHash(w *jsonw.Wrapper) (NodeHash, error) { 441 s, err := w.GetString() 442 if err != nil { 443 return nil, err 444 } 445 ret, err := NodeHashFromHex(s) 446 return ret, err 447} 448 449func GetNodeHashVoid(w *jsonw.Wrapper, nhp *NodeHash, errp *error) { 450 nh, err := GetNodeHash(w) 451 if err != nil { 452 *errp = err 453 } else { 454 *nhp = nh 455 } 456} 457 458func computeSetBitsBigEndian(x uint) []uint { 459 if x == 0 { 460 return nil 461 } else if x == 1 { 462 return []uint{1} 463 } 464 // Allocate maximum array size necessary 465 high := int(math.Ceil(math.Log2(float64(x)))) 466 ret := make([]uint, 0, high) 467 for i, bit := 0, uint(1); i <= high; i, bit = i+1, bit*2 { 468 if x&bit != 0 { 469 ret = append(ret, bit) 470 } 471 } 472 return ret 473} 474 475func computeLogPatternMerkleSkips(startSeqno keybase1.Seqno, endSeqno keybase1.Seqno) (ret []uint, err error) { 476 if endSeqno < startSeqno { 477 return ret, fmt.Errorf("got startSeqno > endSeqno (%d > %d) in merkle skip sequence", startSeqno, endSeqno) 478 } 479 if endSeqno == startSeqno { 480 return ret, nil 481 } 482 end := uint(endSeqno) 483 start := uint(startSeqno) 484 diff := end - start 485 skips := computeSetBitsBigEndian(diff) 486 curr := end 487 // Ignore first set bit 488 for i := len(skips) - 1; i > 0; i-- { 489 curr -= skips[i] 490 ret = append(ret, curr) 491 } 492 return ret, nil 493} 494 495func NewMerkleClient(g *GlobalContext) *MerkleClient { 496 return &MerkleClient{ 497 keyring: NewSpecialKeyRing(g.Env.GetMerkleKIDs(), g), 498 lastRoot: nil, 499 Contextified: NewContextified(g), 500 } 501} 502 503func (mc *MerkleClient) init(m MetaContext) error { 504 err := mc.loadRoot(m) 505 return err 506} 507 508func merkleHeadKey() DbKey { 509 // DBMerkleRoot was once used to store specific roots with Key: fmt.Sprintf("%d", int) 510 return DbKey{ 511 Typ: DBMerkleRoot, 512 Key: "HEAD", 513 } 514} 515 516func (mc *MerkleClient) dbGet(m MetaContext, k DbKey) (ret *MerkleRoot, err error) { 517 defer m.VTrace(VLog1, fmt.Sprintf("MerkleClient#dbGet(%+v)", k), &err)() 518 curr, err := m.G().LocalDb.Get(k) 519 if err != nil { 520 return nil, err 521 } 522 if curr == nil { 523 m.VLogf(VLog1, "| MerkleClient#dbGet(%+v) found not results", k) 524 return nil, nil 525 } 526 527 mr, err := NewMerkleRootFromJSON(curr, MerkleOpts{}) 528 if err != nil { 529 return nil, err 530 } 531 return mr, err 532} 533 534func (mc *MerkleClient) loadRoot(m MetaContext) (err error) { 535 defer m.VTrace(VLog1, "MerkleClient#loadRoot()", &err)() 536 var mr *MerkleRoot 537 mr, err = mc.dbGet(m, merkleHeadKey()) 538 if mr == nil || err != nil { 539 return err 540 } 541 mc.Lock() 542 mc.lastRoot = mr 543 mc.Unlock() 544 return nil 545} 546 547func (mr *MerkleRoot) HasSkips() bool { 548 return mr.payload.hasSkips() 549} 550 551func (mr *MerkleRoot) ToJSON() (jw *jsonw.Wrapper) { 552 ret := jsonw.NewDictionary() 553 _ = ret.SetKey("sigs", mr.sigs) 554 _ = ret.SetKey("payload_json", jsonw.NewString(mr.payload.packed)) 555 _ = ret.SetKey("fetched_ns", jsonw.NewInt64(mr.fetched.UnixNano())) 556 return ret 557} 558 559func (mr MerkleRoot) ShortHash() NodeHashShort { 560 return mr.payload.shortHash() 561} 562 563func NewMerkleRootPayloadFromJSONString(s string) (ret MerkleRootPayload, err error) { 564 ret = MerkleRootPayload{packed: s} 565 err = json.Unmarshal([]byte(s), &ret.unpacked) 566 if err != nil { 567 return ret, err 568 } 569 return ret, nil 570} 571 572func NewMerkleRootFromJSON(jw *jsonw.Wrapper, opts MerkleOpts) (ret *MerkleRoot, err error) { 573 var sigs *jsonw.Wrapper 574 var payloadJSONString string 575 var mrp MerkleRootPayload 576 577 if !opts.noSigCheck { 578 if sigs, err = jw.AtKey("sigs").ToDictionary(); err != nil { 579 return nil, err 580 } 581 } 582 583 if payloadJSONString, err = jw.AtKey("payload_json").GetString(); err != nil { 584 return nil, err 585 } 586 587 if mrp, err = NewMerkleRootPayloadFromJSONString(payloadJSONString); err != nil { 588 return nil, err 589 } 590 591 ret = &MerkleRoot{ 592 sigs: sigs, 593 payload: mrp, 594 fetched: time.Time{}, 595 } 596 597 fetchedNs, err := jw.AtKey("fetched_ns").GetInt64() 598 if err == nil { 599 ret.fetched = time.Unix(0, fetchedNs) 600 } 601 602 return ret, nil 603} 604 605func importPathFromJSON(jw *jsonw.Wrapper) (out []*PathStep, err error) { 606 if jw.IsNil() { 607 return 608 } 609 610 var path *jsonw.Wrapper 611 if path, err = jw.ToArray(); err != nil { 612 return 613 } 614 615 var l int 616 if l, err = path.Len(); err != nil { 617 return 618 } 619 620 for i := 0; i < l; i++ { 621 var step *PathStep 622 if step, err = pathStepFromJSON(path.AtIndex(i)); err != nil { 623 return 624 } 625 out = append(out, step) 626 } 627 return 628} 629 630// FetchRootFromServerByMinSeqno returns the latest root this client knows 631// about. If the seqno of the latest root is smaller than the lowerBound 632// argument, a new api call is made to the server. However, if the server 633// returns a root at a seqno smaller than lowerBound, no errors are raised. 634func (mc *MerkleClient) FetchRootFromServerByMinSeqno(m MetaContext, lowerBound keybase1.Seqno) (mr *MerkleRoot, err error) { 635 defer m.VTrace(VLog0, "MerkleClient#FetchRootFromServerByMinSeqno", &err)() 636 637 checkFreshness := func() (ok bool, root *MerkleRoot) { 638 root = mc.LastRoot(m) 639 if root != nil && *root.Seqno() >= lowerBound { 640 m.VLogf(VLog0, "seqno=%d, and was current enough, so returning non-nil previously fetched root", *root.Seqno()) 641 return true, root 642 } 643 return false, root 644 } 645 646 if ok, root := checkFreshness(); ok { 647 return root, nil 648 } 649 650 mc.latestRootLock.Lock() 651 defer mc.latestRootLock.Unlock() 652 // by the time we got the lock, the root might have been updated to a recent enough one, so check again 653 ok, root := checkFreshness() 654 if ok { 655 return root, nil 656 } 657 658 return mc.fetchAndStoreRootFromServerLocked(m, root) 659} 660 661// FetchRootFromServer fetches a root from the server. If the last-fetched root was fetched within 662// freshness ago, then OK to return the last-fetched root. Otherwise refetch. Similarly, if the freshness 663// passed is 0, then always refresh. 664func (mc *MerkleClient) FetchRootFromServer(m MetaContext, freshness time.Duration) (mr *MerkleRoot, err error) { 665 defer m.VTrace(VLog0, "MerkleClient#FetchRootFromServer", &err)() 666 667 now := m.G().Clock().Now() 668 669 checkFreshness := func() (ok bool, root *MerkleRoot) { 670 root = mc.LastRoot(m) 671 if root != nil && freshness > 0 && now.Sub(root.fetched) < freshness { 672 m.VLogf(VLog0, "freshness=%s, and was current enough, so returning non-nil previously fetched root", freshness) 673 return true, root 674 } 675 return false, root 676 } 677 678 if ok, root := checkFreshness(); ok { 679 return root, nil 680 } 681 682 mc.latestRootLock.Lock() 683 defer mc.latestRootLock.Unlock() 684 // by the time we got the lock, the root might have been updated to a recent enough one, so check again 685 ok, root := checkFreshness() 686 if ok { 687 return root, nil 688 } 689 690 return mc.fetchAndStoreRootFromServerLocked(m, root) 691} 692 693func (mc *MerkleClient) fetchAndStoreRootFromServerLocked(m MetaContext, lastRoot *MerkleRoot) (mr *MerkleRoot, err error) { 694 defer m.VTrace(VLog0, "MerkleClient#fetchRootFromServerLocked", &err)() 695 var ss SkipSequence 696 var apiRes *APIRes 697 var opts MerkleOpts 698 699 mr, ss, apiRes, err = mc.lookupRootAndSkipSequence(m, lastRoot, opts) 700 if err != nil { 701 return nil, err 702 } 703 704 if mr == nil { 705 // The server indicated that last root is the most recent one: updating 706 // the fetch time and skipping verification 707 lastRoot.fetched = m.G().Clock().Now() 708 mc.Lock() 709 defer mc.Unlock() 710 mc.storeRoot(m, lastRoot) 711 return lastRoot, nil 712 } 713 714 if err = mc.verifySkipSequenceAndRoot(m, ss, mr, lastRoot, apiRes, opts); err != nil { 715 return nil, err 716 } 717 718 mc.Lock() 719 defer mc.Unlock() 720 mc.storeRoot(m, mr) 721 722 return mr, nil 723} 724 725// if both mr and err are nil, this indicates the server did not send a new root 726// as lastRoot was the most recent one. 727func (mc *MerkleClient) lookupRootAndSkipSequence(m MetaContext, lastRoot *MerkleRoot, opts MerkleOpts) (mr *MerkleRoot, ss SkipSequence, apiRes *APIRes, err error) { 728 729 // c=1 invokes server-side compression 730 q := HTTPArgs{ 731 "c": B{true}, 732 } 733 734 // Get back a series of skips from the last merkle root we had to the new 735 // one we're getting back, and hold the server to it. 736 lastSeqno := lastRoot.Seqno() 737 if lastSeqno != nil { 738 q.Add("last", I{int(*lastSeqno)}) 739 // If the last root known to the server has seqno last, we do not need 740 // to receive it again. 741 q.Add("skip_last", B{true}) 742 } 743 744 apiRes, err = m.G().API.Get(m, APIArg{ 745 Endpoint: "merkle/root", 746 SessionType: APISessionTypeNONE, 747 Args: q, 748 AppStatusCodes: []int{SCOk}, 749 }) 750 751 if err != nil { 752 return nil, nil, nil, err 753 } 754 755 seqno, err := apiRes.Body.AtKey("seqno").GetInt64() 756 if err != nil { 757 return nil, nil, nil, fmt.Errorf("merkle/root response does not contain seqno: %v", err) 758 } 759 if lastSeqno != nil && *lastSeqno == keybase1.Seqno(seqno) { 760 // here we can ignore the rest of the server response (the server 761 // should not send it anyways), as lastRoot is still the most recent 762 // root 763 m.Debug("The server indicated that the root at seqno %v (which we have) is the most recent, shortcircuiting the root parsing and validation.", seqno) 764 return nil, nil, nil, nil 765 } 766 767 mr, err = readRootFromAPIRes(m, apiRes.Body, opts) 768 if err != nil { 769 return nil, nil, nil, err 770 } 771 ss, err = mc.readSkipSequenceFromAPIRes(m, apiRes, mr, lastRoot) 772 if err != nil { 773 return nil, nil, nil, err 774 } 775 return mr, ss, apiRes, err 776} 777 778func (mc *MerkleClient) lookupLeafAndPathUser(m MetaContext, q HTTPArgs, sigHints *SigHints, root *MerkleRoot, opts MerkleOpts) (vp *VerificationPath, userInfo *merkleUserInfoT, apiRes *APIRes, err error) { 779 opts.isUser = true 780 vp, apiRes, err = mc.lookupLeafAndPath(m, q, root, sigHints, opts) 781 if err != nil { 782 return nil, nil, nil, err 783 } 784 785 if sigHints != nil { 786 if err = sigHints.RefreshWith(m, apiRes.Body.AtKey("sigs")); err != nil { 787 return nil, nil, nil, err 788 } 789 } 790 791 userInfo, err = mc.readUserFromAPIRes(m, apiRes) 792 if err != nil { 793 return nil, nil, nil, err 794 } 795 796 return vp, userInfo, apiRes, nil 797} 798 799func (mc *MerkleClient) lookupLeafAndPath(m MetaContext, q HTTPArgs, root *MerkleRoot, sigHints *SigHints, opts MerkleOpts) (vp *VerificationPath, res *APIRes, err error) { 800 apiRes, root, err := mc.lookupLeafAndPathHelper(m, q, sigHints, root, opts) 801 if err != nil { 802 return nil, nil, err 803 } 804 805 vp, err = mc.readPathFromAPIRes(m, apiRes, opts) 806 if err != nil { 807 return nil, nil, err 808 } 809 vp.root = root 810 811 return vp, apiRes, nil 812} 813 814// `MerkleOpts.isUser` is true for loading a user and false for loading a team. 815func (mc *MerkleClient) lookupLeafAndPathHelper(m MetaContext, q HTTPArgs, sigHints *SigHints, root *MerkleRoot, opts MerkleOpts) (apiRes *APIRes, newRoot *MerkleRoot, err error) { 816 defer m.VTrace(VLog1, "MerkleClient#lookupLeafAndPathHelper", &err)() 817 818 for i := 0; i < 5; i++ { 819 apiRes, rootRefreshNeeded, err := mc.lookupLeafAndPathHelperOnce(m, q, sigHints, root, opts) 820 if err != nil { 821 return nil, nil, err 822 } 823 if !rootRefreshNeeded { 824 return apiRes, root, err 825 } 826 827 m.Debug("Server suggested a root refresh is necessary") 828 root, err = mc.FetchRootFromServer(m, 0) 829 if err != nil { 830 return nil, nil, err 831 } 832 } 833 834 return nil, nil, fmt.Errorf("Too many server requests to refresh the merkle root") 835} 836 837// `isUser` is true for loading a user and false for loading a team. 838func (mc *MerkleClient) lookupLeafAndPathHelperOnce(m MetaContext, q HTTPArgs, sigHints *SigHints, root *MerkleRoot, opts MerkleOpts) (apiRes *APIRes, rootRefreshNeeded bool, err error) { 839 defer m.VTrace(VLog1, "MerkleClient#lookupLeafAndPathHelperOnce", &err)() 840 841 if !opts.NoServerPolling { 842 // Poll for 10s and ask for a race-free state. 843 w := 10 * int(CITimeMultiplier(mc.G())) 844 q.Add("poll", I{w}) 845 } 846 847 q.Add("c", B{true}) 848 if opts.isUser { 849 q.Add("load_deleted", B{true}) 850 q.Add("load_reset_chain", B{true}) 851 } 852 853 // Add the local db sigHints version 854 if sigHints != nil { 855 q.Add("sig_hints_low", I{sigHints.version}) 856 } 857 858 // Get back a path from the leaf to the current merkle root. The root itself 859 // is not included. 860 tail := root.Seqno() 861 if tail != nil { 862 q.Add("tail", I{int(*tail)}) 863 } 864 865 apiRes, err = m.G().API.Get(m, APIArg{ 866 Endpoint: "merkle/path", 867 SessionType: APISessionTypeOPTIONAL, 868 Args: q, 869 AppStatusCodes: []int{SCOk, SCNotFound, SCDeleted, SCMerkleUpdateRoot}, 870 }) 871 872 if err != nil { 873 return nil, false, err 874 } 875 876 switch apiRes.AppStatus.Code { 877 case SCMerkleUpdateRoot: 878 // Server indicated that a refetch of the root is needed 879 return nil, true, nil 880 case SCOk: 881 err = assertRespSeqnoPrecedesCurrentRoot(apiRes, root) 882 if err != nil { 883 return nil, false, err 884 } 885 // TRIAGE-2068 886 case SCNotFound: 887 return nil, false, NotFoundError{} 888 case SCDeleted: 889 return nil, false, UserDeletedError{} 890 } 891 return apiRes, false, nil 892} 893 894func assertRespSeqnoPrecedesCurrentRoot(apiRes *APIRes, root *MerkleRoot) error { 895 resSeqno, err := apiRes.Body.AtKey("root").AtKey("seqno").GetInt64() 896 if err != nil { 897 return err 898 } 899 if keybase1.Seqno(resSeqno) > *root.Seqno() { 900 // The server should have returned SCMerkleUpdateRoot instead 901 return MerkleClientError{m: fmt.Sprintf("The server unexpectedly returned root (%v) ahead of the last one we know about (%v) instead of asking to update", keybase1.Seqno(resSeqno), *root.Seqno())} 902 } 903 return nil 904} 905 906func readSkipSequenceFromStringList(v []string) (ret SkipSequence, err error) { 907 for _, s := range v { 908 var p MerkleRootPayload 909 if p, err = NewMerkleRootPayloadFromJSONString(s); err != nil { 910 return nil, err 911 } 912 ret = append(ret, p) 913 } 914 return ret, nil 915} 916 917func (mc *MerkleClient) readAndCheckRootFromAPIRes(m MetaContext, apiRes *APIRes, currentRoot *MerkleRoot, opts MerkleOpts) (newRoot *MerkleRoot, err error) { 918 newRoot, err = readRootFromAPIRes(m, apiRes.Body.AtKey("root"), opts) 919 if err != nil { 920 return nil, err 921 } 922 ss, err := mc.readSkipSequenceFromAPIRes(m, apiRes, newRoot, currentRoot) 923 if err != nil { 924 return nil, err 925 } 926 err = mc.verifySkipSequenceAndRoot(m, ss, newRoot, currentRoot, apiRes, opts) 927 if err != nil { 928 return nil, err 929 } 930 return newRoot, nil 931} 932 933func readRootFromAPIRes(m MetaContext, jw *jsonw.Wrapper, opts MerkleOpts) (*MerkleRoot, error) { 934 ret, err := NewMerkleRootFromJSON(jw, opts) 935 if err != nil { 936 return nil, err 937 } 938 if chk := GetMerkleCheckpoint(m); chk != nil && *ret.Seqno() < *chk.Seqno() { 939 msg := fmt.Sprintf("got unexpected early root %d < %d", *ret.Seqno(), *chk.Seqno()) 940 m.Error("checkpoint failure: %s", msg) 941 return nil, NewClientMerkleFailedCheckpointError(msg) 942 } 943 ret.fetched = m.G().Clock().Now() 944 return ret, nil 945} 946 947// readSkipSequenceFromAPIRes returns a SkipSequence. We construct the sequence by starting with the 948// most recent merkle root, adding the "skip" pointers returned by the server, and finally bookending 949// with the merkle root we last fetched from the DB. In verifySkipSequence, we walk over this Sequence 950// to make sure that it obeys proper construction. 951func (mc *MerkleClient) readSkipSequenceFromAPIRes(m MetaContext, res *APIRes, thisRoot *MerkleRoot, lastRoot *MerkleRoot) (ret SkipSequence, err error) { 952 defer m.VTrace(VLog1, "MerkleClient#readSkipSequenceFromAPIRes", &err)() 953 if lastRoot == nil { 954 m.VLogf(VLog0, "| lastRoot==nil") 955 return nil, nil 956 } 957 if !thisRoot.HasSkips() { 958 m.VLogf(VLog0, "| thisRoot has no skips") 959 return nil, nil 960 } 961 skips := res.Body.AtKey("skips") 962 963 if skips.IsNil() { 964 m.VLogf(VLog1, "| skip list from API server is nil") 965 return nil, nil 966 } 967 968 var v []string 969 if err = skips.UnmarshalAgain(&v); err != nil { 970 m.VLogf(VLog0, "| failed to unmarshal skip list as a list of strings") 971 return nil, err 972 } 973 974 ret, err = readSkipSequenceFromStringList(v) 975 if err != nil { 976 return nil, err 977 } 978 979 // Create the skip sequence by bookending the list the server replies with 980 // with: (1) the most recent root, sent back in this reply; and (2) our last 981 // root, which we read out of cache (in memory or on disk). HOWEVER, in the 982 // case of lookup up historical roots, the ordering might be reversed. So 983 // we swap in that case. 984 985 left, right := thisRoot.payload, lastRoot.payload 986 if left.seqno() < right.seqno() { 987 left, right = right, left 988 } 989 990 ret = append(SkipSequence{left}, ret...) 991 ret = append(ret, right) 992 993 return ret, nil 994} 995 996func (mc *MerkleClient) readUserFromAPIRes(m MetaContext, res *APIRes) (userInfo *merkleUserInfoT, err error) { 997 userInfo = &merkleUserInfoT{} 998 999 userInfo.uid, err = GetUID(res.Body.AtKey("uid")) 1000 if err != nil { 1001 return nil, err 1002 } 1003 1004 // We don't trust this version, but it's useful to tell us if there 1005 // are new versions unsigned data, like basics, and maybe uploaded 1006 // keys 1007 userInfo.idVersion, err = res.Body.AtKey("id_version").GetInt64() 1008 if err != nil { 1009 return nil, err 1010 } 1011 1012 userInfo.uidPath, err = importPathFromJSON(res.Body.AtKey("uid_proof_path")) 1013 if err != nil { 1014 return nil, err 1015 } 1016 1017 userInfo.username, err = res.Body.AtKey("username").GetString() 1018 if err != nil { 1019 return nil, err 1020 } 1021 userInfo.usernameCased, _ = res.Body.AtKey("username_cased").GetString() 1022 1023 userInfo.unverifiedResetChain, err = importResetChainFromServer(m, res.Body.AtKey("reset_chain")) 1024 if err != nil { 1025 return nil, err 1026 } 1027 1028 return userInfo, nil 1029} 1030 1031func (mc *MerkleClient) readPathFromAPIRes(m MetaContext, res *APIRes, opts MerkleOpts) (vp *VerificationPath, err error) { 1032 defer m.VTrace(VLog1, "MerkleClient#readPathFromAPIRes", &err)() 1033 1034 vp = &VerificationPath{ 1035 Contextified: NewContextified(mc.G()), 1036 } 1037 1038 vp.path, err = importPathFromJSON(res.Body.AtKey("path")) 1039 if err != nil { 1040 return nil, err 1041 } 1042 1043 return vp, nil 1044} 1045 1046func pathStepFromJSON(jw *jsonw.Wrapper) (ps *PathStep, err error) { 1047 1048 var prefix string 1049 pw := jw.AtKey("prefix") 1050 if !pw.IsNil() { 1051 var s string 1052 if s, err = pw.GetString(); err != nil { 1053 return 1054 } 1055 prefix = s 1056 } 1057 node, err := jw.AtKey("node").AtKey("val").GetString() 1058 if err != nil { 1059 return 1060 } 1061 ps = &PathStep{prefix, node} 1062 return 1063} 1064 1065func (mc *MerkleClient) LastRoot(m MetaContext) *MerkleRoot { 1066 mc.RLock() 1067 defer mc.RUnlock() 1068 if mc.lastRoot == nil { 1069 return nil 1070 } 1071 ret := mc.lastRoot 1072 chk := GetMerkleCheckpoint(m) 1073 if chk != nil && *ret.Seqno() < *chk.Seqno() { 1074 ret = chk 1075 } 1076 return ret.ShallowCopy() 1077} 1078 1079func (mr MerkleRoot) ExportToAVDL(g *GlobalContext) keybase1.MerkleRootAndTime { 1080 hashMeta := mr.ShortHash() 1081 return keybase1.MerkleRootAndTime{ 1082 Root: keybase1.MerkleRootV2{ 1083 Seqno: mr.payload.unpacked.Body.Seqno, 1084 HashMeta: hashMeta[:], 1085 }, 1086 UpdateTime: keybase1.TimeFromSeconds(mr.payload.unpacked.Ctime), 1087 FetchTime: keybase1.ToTime(mr.fetched), 1088 } 1089} 1090 1091// storeRoot stores the root in the db and mem. 1092// Must be called from under a lock. 1093func (mc *MerkleClient) storeRoot(m MetaContext, root *MerkleRoot) { 1094 m.VLogf(VLog0, "storing merkle root: %d", *root.Seqno()) 1095 err := mc.G().LocalDb.Put(merkleHeadKey(), nil, root.ToJSON()) 1096 if err != nil { 1097 m.Error("Cannot commit Merkle root to local DB: %s", err) 1098 } else { 1099 mc.lastRoot = root 1100 } 1101} 1102 1103func (mc *MerkleClient) firstExaminableHistoricalRootProd(m MetaContext) *keybase1.Seqno { 1104 chk := GetMerkleCheckpoint(m) 1105 var ret *keybase1.Seqno 1106 if chk != nil { 1107 ret = chk.Seqno() 1108 } 1109 if ret == nil || FirstProdMerkleSeqnoWithSkips > *ret { 1110 ret = &FirstProdMerkleSeqnoWithSkips 1111 } 1112 return ret 1113} 1114 1115func (mc *MerkleClient) FirstExaminableHistoricalRoot(m MetaContext) *keybase1.Seqno { 1116 1117 if mc.G().Env.GetRunMode() == ProductionRunMode { 1118 return mc.firstExaminableHistoricalRootProd(m) 1119 } 1120 1121 ret := mc.getFirstSkip() 1122 if ret != nil { 1123 return ret 1124 } 1125 1126 ret = mc.getFirstSkipFromServer(m) 1127 return ret 1128} 1129 1130func (mc *MerkleClient) getFirstSkip() *keybase1.Seqno { 1131 mc.RLock() 1132 defer mc.RUnlock() 1133 return mc.firstSkip 1134} 1135 1136type firstSkipRaw struct { 1137 Status AppStatus `json:"status"` 1138 Seqno keybase1.Seqno `json:"seqno"` 1139} 1140 1141func (r *firstSkipRaw) GetAppStatus() *AppStatus { 1142 return &r.Status 1143} 1144 1145func (mc *MerkleClient) getFirstSkipFromServer(m MetaContext) *keybase1.Seqno { 1146 1147 var raw firstSkipRaw 1148 err := m.G().API.GetDecode(m, APIArg{ 1149 Endpoint: "merkle/first_root_with_skips", 1150 SessionType: APISessionTypeNONE, 1151 AppStatusCodes: []int{SCOk}, 1152 }, &raw) 1153 1154 if err != nil { 1155 m.Debug("failed to fetch first skip from server: %v", err) 1156 return nil 1157 } 1158 1159 m.Debug("Got back seqno=%v as first merkle root with skips", raw.Seqno) 1160 1161 mc.Lock() 1162 mc.firstSkip = &raw.Seqno 1163 mc.Unlock() 1164 1165 return &raw.Seqno 1166} 1167 1168func (mc *MerkleClient) firstMainRootWithHiddenRootHashProd(m MetaContext) (s keybase1.Seqno) { 1169 return FirstProdMerkleSeqnoWithHiddenRootHash 1170} 1171 1172func (mc *MerkleClient) FirstMainRootWithHiddenRootHash(m MetaContext) (s keybase1.Seqno, err error) { 1173 if mc.G().Env.GetRunMode() == ProductionRunMode { 1174 return mc.firstMainRootWithHiddenRootHashProd(m), nil 1175 } 1176 1177 s = mc.getFirstMainRootWithHiddenRootHash() 1178 if s != 0 { 1179 return s, nil 1180 } 1181 1182 return mc.getFirstMainRootWithHiddenRootHashFromServer(m) 1183} 1184 1185func (mc *MerkleClient) getFirstMainRootWithHiddenRootHash() keybase1.Seqno { 1186 mc.RLock() 1187 defer mc.RUnlock() 1188 return mc.firstRootWithHidden 1189} 1190 1191type firstHiddenSeqnoRaw struct { 1192 Status AppStatus `json:"status"` 1193 Seqno keybase1.Seqno `json:"seqno"` 1194} 1195 1196func (r *firstHiddenSeqnoRaw) GetAppStatus() *AppStatus { 1197 return &r.Status 1198} 1199 1200func (mc *MerkleClient) getFirstMainRootWithHiddenRootHashFromServer(m MetaContext) (s keybase1.Seqno, err error) { 1201 1202 var raw firstHiddenSeqnoRaw 1203 err = m.G().API.GetDecode(m, APIArg{ 1204 Endpoint: "merkle/first_root_with_hidden", 1205 SessionType: APISessionTypeNONE, 1206 AppStatusCodes: []int{SCOk}, 1207 }, &raw) 1208 1209 if err != nil { 1210 m.Debug("failed to fetch first main root with hidden from server: %v", err) 1211 return 0, fmt.Errorf("failed to fetch first main root with hidden from server: %v", err) 1212 } 1213 1214 m.Debug("Got back seqno=%v as first merkle root with hidden root hash", raw.Seqno) 1215 1216 mc.Lock() 1217 mc.firstRootWithHidden = raw.Seqno 1218 mc.Unlock() 1219 1220 return raw.Seqno, nil 1221} 1222 1223func (mc *MerkleClient) findValidKIDAndSig(root *MerkleRoot) (keybase1.KID, string, error) { 1224 if v, err := root.sigs.Keys(); err == nil { 1225 for _, s := range v { 1226 kid := keybase1.KIDFromString(s) 1227 if !mc.keyring.IsValidKID(kid) { 1228 continue 1229 } else if sig, err := root.sigs.AtKey(s).AtKey("sig").GetString(); err == nil { 1230 return kid, sig, nil 1231 } 1232 } 1233 } 1234 var nilKID keybase1.KID 1235 return nilKID, "", MerkleClientError{"no known verifying key", merkleErrorNoKnownKey} 1236} 1237 1238func (mc *MerkleClient) verifySkipSequence(m MetaContext, ss SkipSequence, thisRoot *MerkleRoot, lastRoot *MerkleRoot, opts MerkleOpts) (err error) { 1239 defer m.VTrace(VLog1, "MerkleClient#verifySkipSequence", &err)() 1240 1241 var left, right keybase1.Seqno 1242 if thisRoot.Seqno() != nil { 1243 left = *thisRoot.Seqno() 1244 } 1245 if lastRoot.Seqno() != nil { 1246 right = *lastRoot.Seqno() 1247 } 1248 1249 // In historical queries (for which we fetch old roots), we check the skip 1250 // sequence in the opposite direction. 1251 if opts.historical { 1252 left, right = right, left 1253 } 1254 1255 // In this case, the server did not return a skip sequence. It's OK if 1256 // the last known root is too old. It's not OK if the last known root is 1257 // from after the server starting providing skip pointers. 1258 if ss == nil { 1259 m.VLogf(VLog1, "| nil SkipSequence") 1260 fss := mc.FirstExaminableHistoricalRoot(m) 1261 if lastRoot == nil { 1262 m.VLogf(VLog1, "| lastRoot==nil, so OK") 1263 return nil 1264 } 1265 if fss == nil { 1266 m.VLogf(VLog1, "| no known root with skips, so OK") 1267 return nil 1268 } 1269 if *fss > right { 1270 m.VLogf(VLog1, "| right marker (%d) is from before first known root with skips (%d), so OK", int(right), int(*fss)) 1271 return nil 1272 } 1273 if *fss > left { 1274 m.VLogf(VLog1, "| left marker (%d) is from before first known root with skips (%d), so OK", int(left), int(*fss)) 1275 return nil 1276 } 1277 if thisRoot != nil && *lastRoot.Seqno() == *thisRoot.Seqno() { 1278 m.VLogf(VLog1, "| thisRoot is the same as lastRoot (%d), so OK", int(*lastRoot.Seqno())) 1279 return nil 1280 } 1281 return MerkleClientError{fmt.Sprintf("Expected a skip sequence with last=%d", int(*lastRoot.Seqno())), merkleErrorNoSkipSequence} 1282 } 1283 1284 if left == right { 1285 m.VLogf(VLog1, "| No change since last check (seqno %d)", *thisRoot.Seqno()) 1286 return nil 1287 } 1288 return ss.verify(m, left, right) 1289} 1290 1291// verify verifies the raw "Skip Sequence" ss. ss contains a list of MerkleRootPayloads beginning 1292// with the most recently returned root, and ending with the last root that we fetched. So for instance, 1293// it might contain: [ 100, 84, 82, 81 ] in that case that we last fetched Seqno=81 and the server is 1294// currently at Seqno=100. 1295func (ss SkipSequence) verify(m MetaContext, thisRoot keybase1.Seqno, lastRoot keybase1.Seqno) (err error) { 1296 defer m.VTrace(VLog1, "SkipSequence#verify", &err)() 1297 1298 expectedSkips, err := computeLogPatternMerkleSkips(lastRoot, thisRoot) 1299 if err != nil { 1300 return MerkleClientError{fmt.Sprintf("Failed to compute expected skip pattern: %s", err), merkleErrorWrongSkipSequence} 1301 } 1302 // Don't check bookends that were added by client 1303 if len(expectedSkips)+2 != len(ss) { 1304 return MerkleClientError{fmt.Sprintf("Wrong number of skips: expected %d, got %d.", len(expectedSkips)+2, len(ss)), merkleErrorWrongSkipSequence} 1305 } 1306 1307 for index := 1; index < len(ss)-1; index++ { 1308 root := ss[index].seqno() 1309 if keybase1.Seqno(expectedSkips[index-1]) != root { 1310 return MerkleClientError{fmt.Sprintf("Unexpected skip index: expected %d, got %d.", expectedSkips[index-1], root), merkleErrorWrongSkipSequence} 1311 } 1312 } 1313 1314 const maxClockDriftSeconds int64 = 5 * 60 1315 var totalDrift int64 1316 1317 for index := 0; index < len(ss)-1; index++ { 1318 nextIndex := index + 1 1319 thisRoot, prevRoot := ss[index].seqno(), ss[nextIndex].seqno() 1320 m.VLogf(VLog1, "| Checking skip %d->%d", thisRoot, prevRoot) 1321 1322 // Next compare the skip pointer in this merkle root against the hash of the previous 1323 // root in the merkle root sequence. They must be equal. 1324 hash := ss[index].skipToSeqno(prevRoot) 1325 if hash == nil || hash.IsNil() { 1326 return MerkleClientError{fmt.Sprintf("Skip missing at %d->%d", thisRoot, prevRoot), merkleErrorSkipMissing} 1327 } 1328 if !hashEq(hash, ss[nextIndex].shortHash()) { 1329 m.VLogf(VLog0, "| Failure in hashes: %s != %s", hash.String(), ss[nextIndex].shortHash().String()) 1330 return MerkleClientError{fmt.Sprintf("Skip pointer mismatch at %d->%d", thisRoot, prevRoot), merkleErrorSkipHashMismatch} 1331 } 1332 1333 // Check that ctimes in the sequence are nearly strictly ordered; we have to make sure we can handle slight 1334 // clock jitters since the server might need to rewind time due to leap seconds or NTP issues. 1335 // We'll allow at most 5 minutes of "time-travel" between 2 updates, and no more than 5minutes of time travel 1336 // across the whole sequence 1337 thisCTime, prevCTime := ss[index].ctime(), ss[nextIndex].ctime() 1338 if prevCTime > thisCTime { 1339 drift := prevCTime - thisCTime 1340 if drift > maxClockDriftSeconds { 1341 return MerkleClientError{ 1342 fmt.Sprintf("Out of order ctimes: %d at %d should not have come before %d at %d (even with %ds tolerance)", thisRoot, thisCTime, prevRoot, prevCTime, maxClockDriftSeconds), 1343 merkleErrorOutOfOrderCtime, 1344 } 1345 } 1346 totalDrift += drift 1347 } 1348 } 1349 1350 if totalDrift > maxClockDriftSeconds { 1351 return MerkleClientError{ 1352 fmt.Sprintf("Too much clock drift detected (%ds) in skip sequence", totalDrift), 1353 merkleErrorTooMuchClockDrift, 1354 } 1355 1356 } 1357 1358 return nil 1359} 1360 1361func (mc *MerkleClient) verifyRootHelper(m MetaContext, newRoot *MerkleRoot, currentRoot *MerkleRoot, opts MerkleOpts) (err error) { 1362 defer m.VTrace(VLog1, fmt.Sprintf("merkleClient#verifyRootHelper(root=%d, cached=%v, opts=%+v)", int(*newRoot.Seqno()), currentRoot.Seqno() == nil, opts), &err)() 1363 1364 // First make sure it's not a rollback. If we're doing an historical lookup, it's 1365 // actual OK. 1366 if !opts.historical && currentRoot != nil && *currentRoot.Seqno() > *newRoot.Seqno() { 1367 return fmt.Errorf("Server rolled back Merkle tree: %d > %d", *currentRoot.Seqno(), *newRoot.Seqno()) 1368 } 1369 1370 if currentRoot != nil && currentRoot.ShortHash() == newRoot.ShortHash() { 1371 // the new root is the same as the old one, no need to check it again 1372 return nil 1373 } 1374 1375 kid, sig, err := mc.findValidKIDAndSig(newRoot) 1376 if err != nil { 1377 return err 1378 } 1379 m.VLogf(VLog1, "+ Merkle: using KID=%s for verifying server sig", kid) 1380 1381 key, err := mc.keyring.Load(m, kid) 1382 if err != nil { 1383 return err 1384 } 1385 1386 if key == nil { 1387 return MerkleClientError{"no known verifying key", merkleErrorNoKnownKey} 1388 } 1389 1390 // Actually run the PGP verification over the signature 1391 _, err = key.VerifyString(mc.G().Log, sig, []byte(newRoot.payload.packed)) 1392 if err != nil { 1393 return err 1394 } 1395 1396 skips := newRoot.payload.unpacked.Body.Skips 1397 if err := verifyRootSkips(*newRoot.Seqno(), skips); err != nil { 1398 return err 1399 } 1400 1401 m.VLogf(VLog1, "- Merkle: server sig verified") 1402 1403 return nil 1404} 1405 1406func verifyRootSkips(rootSeqno keybase1.Seqno, skips SkipTable) error { 1407 expectedSkips := computeExpectedRootSkips(uint(rootSeqno)) 1408 if len(expectedSkips) != len(skips) { 1409 return MerkleClientError{fmt.Sprintf("Root check: wrong number of skips: expected %d, got %d.", len(expectedSkips), len(skips)), merkleErrorWrongRootSkips} 1410 } 1411 for _, expectedSkip := range expectedSkips { 1412 seqno := keybase1.Seqno(expectedSkip) 1413 _, ok := skips[seqno] 1414 if !ok { 1415 return MerkleClientError{fmt.Sprintf("Root check: unexpected skip index: wanted %d, but did not exist.", seqno), merkleErrorWrongRootSkips} 1416 } 1417 } 1418 return nil 1419} 1420 1421func computeExpectedRootSkips(start uint) []uint { 1422 if start <= 1 { 1423 return nil 1424 } 1425 high := int(math.Ceil(math.Log2(float64(start)))) 1426 ret := make([]uint, high) 1427 for i, skip := 0, uint(1); i < high; i, skip = i+1, skip*2 { 1428 ret[i] = start - skip 1429 } 1430 return ret 1431} 1432 1433func parseTriple(jw *jsonw.Wrapper) (*MerkleTriple, error) { 1434 if jw.IsNil() { 1435 return nil, nil 1436 } 1437 1438 l, err := jw.Len() 1439 if err != nil { 1440 return nil, err 1441 } 1442 if l == 0 { 1443 return nil, nil 1444 } 1445 if l == 1 { 1446 return nil, fmt.Errorf("Bad merkle 'triple', with < 2 values") 1447 } 1448 if l > 3 { 1449 return nil, fmt.Errorf("Bad merkle triple, with > 3 values") 1450 } 1451 seqno, err := jw.AtIndex(0).GetInt64() 1452 if err != nil { 1453 return nil, err 1454 } 1455 li, err := GetLinkID(jw.AtIndex(1)) 1456 if err != nil { 1457 return nil, err 1458 } 1459 1460 var si keybase1.SigIDBase 1461 if l == 3 { 1462 si, err = GetSigIDBase(jw.AtIndex(2)) 1463 if err != nil { 1464 return nil, err 1465 } 1466 } 1467 1468 return &MerkleTriple{keybase1.Seqno(seqno), li, si}, nil 1469 1470} 1471 1472func parseV1(jw *jsonw.Wrapper) (user *MerkleUserLeaf, err error) { 1473 var t *MerkleTriple 1474 if t, err = parseTriple(jw); err == nil { 1475 user = &MerkleUserLeaf{ 1476 public: t, 1477 private: nil, 1478 } 1479 } 1480 return 1481} 1482func parseV2(jw *jsonw.Wrapper) (*MerkleUserLeaf, error) { 1483 user := MerkleUserLeaf{} 1484 1485 l, err := jw.Len() 1486 if err != nil { 1487 return nil, err 1488 } 1489 if l < 2 { 1490 return nil, fmt.Errorf("No public chain.") 1491 } 1492 1493 user.public, err = parseTriple(jw.AtIndex(1)) 1494 if err != nil { 1495 return nil, err 1496 } 1497 1498 if l >= 3 { 1499 user.private, err = parseTriple(jw.AtIndex(2)) 1500 if err != nil { 1501 return nil, err 1502 } 1503 } 1504 1505 if l >= 4 && !jw.AtIndex(3).IsNil() { 1506 eldest, err := GetKID(jw.AtIndex(3)) 1507 if err != nil { 1508 return nil, err 1509 } 1510 user.eldest = eldest 1511 } 1512 1513 if l >= 5 { 1514 user.resets, err = parseV2LeafResetChainTail(jw.AtIndex(4)) 1515 if err != nil { 1516 return nil, err 1517 } 1518 } 1519 1520 return &user, nil 1521} 1522 1523func parseMerkleUserLeaf(m MetaContext, jw *jsonw.Wrapper, g *GlobalContext) (user *MerkleUserLeaf, err error) { 1524 m.VLogf(VLog1, "+ ParsingMerkleUserLeaf") 1525 1526 if jw == nil { 1527 m.VLogf(VLog0, "| empty leaf found; user wasn't in tree") 1528 user = &MerkleUserLeaf{} 1529 return 1530 } 1531 1532 l, err := jw.Len() 1533 if err != nil { 1534 return 1535 } 1536 if l < 2 { 1537 err = fmt.Errorf("Expected an array of length 2 or more") 1538 return 1539 } 1540 1541 v, err := jw.AtIndex(0).GetInt() 1542 1543 if err != nil { 1544 return 1545 } 1546 1547 // We messed up and didn't version the initial leafs of the tree 1548 if _, e2 := jw.AtIndex(1).GetString(); e2 == nil { 1549 v = 1 1550 } 1551 1552 switch v { 1553 case 1: 1554 user, err = parseV1(jw) 1555 case 2: 1556 user, err = parseV2(jw) 1557 default: 1558 err = fmt.Errorf("Unexpected version: %d", v) 1559 } 1560 1561 m.VLogf(VLog1, "- ParsingMerkleUserLeaf -> %v", ErrToOk(err)) 1562 return 1563} 1564 1565func parseMerkleTeamLeaf(m MetaContext, jw *jsonw.Wrapper, g *GlobalContext) (leaf *MerkleTeamLeaf, err error) { 1566 m.VLogf(VLog1, "+ ParsingMerkleTeamLeaf") 1567 1568 if jw == nil { 1569 m.VLogf(VLog0, "| empty leaf found; team wasn't in tree") 1570 leaf = &MerkleTeamLeaf{} 1571 return 1572 } 1573 1574 l, err := jw.Len() 1575 if err != nil { 1576 return 1577 } 1578 // length should be 4, but only use the first 3, and allow larger for forward compatibility. 1579 if l < 3 { 1580 err = fmt.Errorf("Expected an array of length >=3 but got %v", l) 1581 return 1582 } 1583 1584 v, err := jw.AtIndex(0).GetInt() 1585 if err != nil { 1586 return 1587 } 1588 if v != 2 { 1589 err = fmt.Errorf("Expected version 2 but got %v", v) 1590 return 1591 } 1592 1593 public, err := parseTriple(jw.AtIndex(1)) 1594 if err != nil { 1595 return 1596 } 1597 1598 private, err := parseTriple(jw.AtIndex(2)) 1599 if err != nil { 1600 return 1601 } 1602 1603 m.VLogf(VLog1, "- ParsingMerkleTeamLeaf -> %v", ErrToOk(err)) 1604 return &MerkleTeamLeaf{ 1605 // TeamID is filled in by the caller 1606 Public: public, 1607 Private: private, 1608 }, err 1609} 1610 1611func (vp *VerificationPath) verifyUsername(m MetaContext, userInfo merkleUserInfoT) (username string, err error) { 1612 if CheckUIDAgainstUsername(userInfo.uid, userInfo.username) == nil { 1613 m.VLogf(VLog1, "| Username %s mapped to %s via direct hash", userInfo.username, userInfo.uid) 1614 username = userInfo.username 1615 return 1616 } 1617 1618 m.VLogf(VLog1, "| Failed to map Username %s -> UID %s via direct hash", userInfo.username, userInfo.uid) 1619 1620 if userInfo.usernameCased != userInfo.username && strings.ToLower(userInfo.usernameCased) == userInfo.username { 1621 m.VLogf(VLog1, "| Checking cased username difference: %s v %s", userInfo.username, userInfo.usernameCased) 1622 if checkUIDAgainstCasedUsername(userInfo.uid, userInfo.usernameCased) == nil { 1623 m.VLogf(VLog1, "| Username %s mapped to %s via direct hash (w/ username casing)", userInfo.usernameCased, userInfo.uid) 1624 username = userInfo.username 1625 return 1626 } 1627 } 1628 1629 hsh := sha256.Sum256([]byte(strings.ToLower(userInfo.username))) 1630 hshS := hex.EncodeToString(hsh[:]) 1631 var leaf *jsonw.Wrapper 1632 1633 if vp.root.LegacyUIDRootHash() == nil { 1634 err = MerkleClientError{"no legacy UID root hash found in root", merkleErrorNoLegacyUIDRoot} 1635 return 1636 } 1637 1638 if leaf, err = userInfo.uidPath.VerifyPath(vp.root.LegacyUIDRootHash(), hshS); err != nil { 1639 return 1640 } 1641 1642 var uid2 keybase1.UID 1643 if uid2, err = GetUID(leaf); err != nil { 1644 return 1645 } 1646 if userInfo.uid.NotEqual(uid2) { 1647 err = UIDMismatchError{fmt.Sprintf("UID %s != %s via merkle tree", uid2, userInfo.uid)} 1648 return 1649 } 1650 1651 m.VLogf(VLog1, "| Username %s mapped to %s via Merkle lookup", userInfo.username, userInfo.uid) 1652 username = userInfo.username 1653 1654 return 1655} 1656 1657func (vp *VerificationPath) verifyUser(m MetaContext, uid keybase1.UID) (user *MerkleUserLeaf, err error) { 1658 curr := vp.root.RootHash() 1659 1660 var leaf *jsonw.Wrapper 1661 leaf, err = vp.path.VerifyPath(curr, uid.String()) 1662 1663 if leaf != nil && err == nil { 1664 if leaf, err = leaf.ToArray(); err != nil { 1665 msg := fmt.Sprintf("Didn't find a leaf for user in tree: %s", err) 1666 err = MerklePathNotFoundError{uid.String(), msg} 1667 } 1668 } 1669 1670 if err == nil { 1671 // noop 1672 } else if _, ok := err.(MerklePathNotFoundError); ok { 1673 m.VLogf(VLog0, fmt.Sprintf("In checking Merkle tree: %s", err)) 1674 } else { 1675 return 1676 } 1677 1678 user, err = parseMerkleUserLeaf(m, leaf, vp.G()) 1679 if user != nil { 1680 user.uid = uid 1681 } 1682 return 1683} 1684 1685func (vp *VerificationPath) verifyTeam(m MetaContext, teamID keybase1.TeamID) (teamLeaf *MerkleTeamLeaf, err error) { 1686 curr := vp.root.RootHash() 1687 1688 var leaf *jsonw.Wrapper 1689 leaf, err = vp.path.VerifyPath(curr, teamID.String()) 1690 1691 if leaf != nil && err == nil { 1692 if leaf, err = leaf.ToArray(); err != nil { 1693 msg := fmt.Sprintf("Didn't find a leaf for team in tree: %s", err) 1694 err = MerklePathNotFoundError{teamID.String(), msg} 1695 } 1696 } 1697 1698 if err == nil { 1699 // noop 1700 } else if _, ok := err.(MerklePathNotFoundError); ok { 1701 m.VLogf(VLog0, fmt.Sprintf("In checking Merkle tree: %s", err)) 1702 } else { 1703 return 1704 } 1705 1706 teamLeaf, err = parseMerkleTeamLeaf(m, leaf, vp.G()) 1707 if teamLeaf != nil { 1708 teamLeaf.TeamID = teamID 1709 } 1710 return 1711} 1712 1713func (path PathSteps) VerifyPath(curr NodeHash, uidS string) (juser *jsonw.Wrapper, err error) { 1714 1715 bpath := uidS 1716 lastTyp := 0 1717 1718 for i, step := range path { 1719 payload := step.node 1720 if !curr.Check(payload) { 1721 err = fmt.Errorf("Hash mismatch at level=%d", i) 1722 break 1723 } 1724 1725 var jw *jsonw.Wrapper 1726 jw, err = jsonw.Unmarshal([]byte(payload)) 1727 if err != nil { 1728 err = fmt.Errorf("Can't parse JSON at level=%d: %s", i, err) 1729 break 1730 } 1731 1732 plen := len(step.prefix) 1733 if plen > len(bpath) { 1734 err = fmt.Errorf("Path prefix longer than identifier: %v > %v", plen, len(bpath)) 1735 return nil, err 1736 } 1737 if plen > 0 && bpath[:plen] != step.prefix { 1738 err = fmt.Errorf("Path mismatch at level %d: %s != %s", i, bpath[:plen], step.prefix) 1739 break 1740 } 1741 1742 lastTyp, err = jw.AtKey("type").GetInt() 1743 if err != nil { 1744 err = fmt.Errorf("At level %d, failed to get a valid 'type'", i) 1745 break 1746 } 1747 1748 if lastTyp == MerkleTreeNode { 1749 if plen == 0 { 1750 err = fmt.Errorf("Empty prefix len at level=%d", i) 1751 return 1752 } 1753 curr, err = GetNodeHash(jw.AtKey("tab").AtKey(step.prefix)) 1754 if err != nil { 1755 err = MerklePathNotFoundError{uidS, err.Error()} 1756 break 1757 } 1758 juser = nil 1759 } else { 1760 juser = jw.AtKey("tab").AtKey(uidS) 1761 } 1762 } 1763 1764 if err == nil && juser == nil { 1765 err = MerklePathNotFoundError{uidS, "tree path didn't end in a leaf"} 1766 } 1767 return 1768} 1769 1770func (mc *MerkleClient) verifySkipSequenceAndRoot(m MetaContext, ss SkipSequence, curr *MerkleRoot, prev *MerkleRoot, apiRes *APIRes, opts MerkleOpts) (err error) { 1771 1772 defer func() { 1773 if err != nil { 1774 m.VLogf(VLog0, "| Full APIRes was: %s", apiRes.Body.MarshalToDebug()) 1775 } 1776 }() 1777 1778 // It's important to check the merkle skip sequence before verifying the root. 1779 if err = mc.verifySkipSequence(m, ss, curr, prev, opts); err != nil { 1780 return err 1781 } 1782 if opts.noSigCheck { 1783 m.VLogf(VLog0, "| noSigCheck wanted, so skipping out") 1784 return nil 1785 } 1786 return mc.verifyRootHelper(m, curr, prev, opts) 1787} 1788 1789func (mc *MerkleClient) LookupUser(m MetaContext, q HTTPArgs, sigHints *SigHints, opts MerkleOpts) (u *MerkleUserLeaf, err error) { 1790 1791 m.VLogf(VLog0, "+ MerkleClient.LookupUser(%v)", q) 1792 1793 if err = mc.init(m); err != nil { 1794 return nil, err 1795 } 1796 1797 root, err := mc.FetchRootFromServer(m, DefaultMerkleRootFreshness) 1798 if err != nil { 1799 return nil, err 1800 } 1801 1802 path, userInfo, _, err := mc.lookupLeafAndPathUser(m, q, sigHints, root, opts) 1803 if err != nil { 1804 return nil, err 1805 } 1806 // spot check that the user-specific path attributes were filled 1807 if userInfo.uid.IsNil() { 1808 return nil, fmt.Errorf("verification path has nil UID") 1809 } 1810 1811 if u, err = path.verifyUser(m, userInfo.uid); err != nil { 1812 return nil, err 1813 } 1814 1815 if u.username, err = path.verifyUsername(m, *userInfo); err != nil { 1816 return nil, err 1817 } 1818 1819 if err = u.resets.verifyAndLoad(m, userInfo.unverifiedResetChain); err != nil { 1820 return nil, err 1821 } 1822 1823 u.idVersion = userInfo.idVersion 1824 1825 m.VLogf(VLog0, "- MerkleClient.LookupUser(%v) -> OK", q) 1826 return u, nil 1827} 1828 1829func (vp *VerificationPath) verifyUserOrTeam(m MetaContext, id keybase1.UserOrTeamID) (leaf *MerkleGenericLeaf, err error) { 1830 1831 if id.IsUser() { 1832 user, err := vp.verifyUser(m, id.AsUserOrBust()) 1833 if err != nil { 1834 return nil, err 1835 } 1836 return user.MerkleGenericLeaf(), nil 1837 } 1838 1839 if id.IsTeamOrSubteam() { 1840 team, err := vp.verifyTeam(m, id.AsTeamOrBust()) 1841 if err != nil { 1842 return nil, err 1843 } 1844 return team.MerkleGenericLeaf(), nil 1845 } 1846 1847 return nil, errors.New("id was neither a user or a team") 1848} 1849 1850func (mc *MerkleClient) LookupLeafAtHashMeta(m MetaContext, leafID keybase1.UserOrTeamID, hm keybase1.HashMeta) (leaf *MerkleGenericLeaf, err error) { 1851 m.VLogf(VLog0, "+ MerkleClient.LookupLeafAtHashMeta(%v)", leafID) 1852 paramer := func(a *HTTPArgs) { 1853 a.Add("start_hash_meta", S{Val: hm.String()}) 1854 } 1855 checker := func(path *VerificationPath) error { 1856 if !path.root.HashMeta().Eq(hm) { 1857 return MerkleClientError{"hash meta failed to match", merkleErrorHashMeta} 1858 } 1859 return nil 1860 } 1861 leaf, _, _, err = mc.lookupLeafHistorical(m, leafID, paramer, checker, MerkleOpts{}, nil) 1862 return leaf, err 1863} 1864 1865func (mc *MerkleClient) checkHistoricalSeqno(s keybase1.Seqno) error { 1866 if mc.G().Env.GetRunMode() == ProductionRunMode && s < FirstProdMerkleSeqnoWithSigs { 1867 return MerkleClientError{fmt.Sprintf("cannot load seqno=%d; must load at %d or higher", s, FirstProdMerkleSeqnoWithSigs), merkleErrorAncientSeqno} 1868 } 1869 return nil 1870} 1871 1872type MerkleOpts struct { 1873 // All used internally 1874 noSigCheck bool 1875 historical bool 1876 isUser bool 1877 1878 // Used externally 1879 NoServerPolling bool 1880} 1881 1882func (mc *MerkleClient) LookupLeafAtSeqno(m MetaContext, leafID keybase1.UserOrTeamID, s keybase1.Seqno) (leaf *MerkleGenericLeaf, root *MerkleRoot, err error) { 1883 leaf, root, _, err = mc.lookupLeafAtSeqno(m, leafID, s, MerkleOpts{}, nil /* processHiddenResponseFunc */) 1884 return leaf, root, err 1885} 1886 1887func (mc *MerkleClient) LookupLeafAtSeqnoForAudit(m MetaContext, leafID keybase1.UserOrTeamID, s keybase1.Seqno, processHiddenResponseFunc ProcessHiddenRespFunc) (leaf *MerkleGenericLeaf, root *MerkleRoot, hiddenResp *MerkleHiddenResponse, err error) { 1888 return mc.lookupLeafAtSeqno(m, leafID, s, MerkleOpts{noSigCheck: true}, processHiddenResponseFunc) 1889} 1890 1891func (mc *MerkleClient) lookupLeafAtSeqno(m MetaContext, leafID keybase1.UserOrTeamID, s keybase1.Seqno, opts MerkleOpts, processHiddenResponseFunc ProcessHiddenRespFunc) (leaf *MerkleGenericLeaf, root *MerkleRoot, hiddenResp *MerkleHiddenResponse, err error) { 1892 m.VLogf(VLog0, "+ MerkleClient.lookupLeafAtSeqno(%v,%v,%v)", leafID, s, opts) 1893 if err = mc.checkHistoricalSeqno(s); err != nil { 1894 return nil, nil, nil, err 1895 } 1896 paramer := func(a *HTTPArgs) { 1897 a.Add("start_seqno", I{Val: int(s)}) 1898 if opts.noSigCheck { 1899 a.Add("no_root_sigs", B{Val: true}) 1900 } 1901 } 1902 // Since we are looking up a leaf at a specific seqno, ensure we have root 1903 // at least as recent as that seqno. 1904 _, err = mc.FetchRootFromServerByMinSeqno(m, s) 1905 if err != nil { 1906 return nil, nil, nil, err 1907 } 1908 1909 checker := func(path *VerificationPath) error { 1910 if path.root.Seqno() == nil { 1911 return MerkleClientError{"no such seqno was found", merkleErrorNotFound} 1912 } 1913 if *path.root.Seqno() != s { 1914 return MerkleClientError{"seqno mismatch", merkleErrorBadSeqno} 1915 } 1916 return nil 1917 } 1918 return mc.lookupLeafHistorical(m, leafID, paramer, checker, opts, processHiddenResponseFunc) 1919} 1920 1921func (mc *MerkleClient) LookupRootAtSeqno(m MetaContext, s keybase1.Seqno) (root *MerkleRoot, err error) { 1922 defer m.VTrace(VLog0, fmt.Sprintf("LookupRootAtSeqno(%d)", s), &err)() 1923 _, root, err = mc.LookupLeafAtSeqno(m, keybase1.UserOrTeamID(""), s) 1924 return root, err 1925} 1926 1927func (mc *MerkleClient) lookupLeafHistorical(m MetaContext, leafID keybase1.UserOrTeamID, paramer func(*HTTPArgs), checker func(*VerificationPath) error, opts MerkleOpts, processHiddenResponseFunc ProcessHiddenRespFunc) (leaf *MerkleGenericLeaf, root *MerkleRoot, hiddenResp *MerkleHiddenResponse, err error) { 1928 opts.historical = true 1929 1930 var path *VerificationPath 1931 var apiRes *APIRes 1932 1933 if err = mc.init(m); err != nil { 1934 return nil, nil, nil, err 1935 } 1936 1937 // The most current root we got. This might be slightly out of date, but all 1938 // we really care is that it points back to another historical root, which 1939 // should be before currentRoot. If it's not, we'll refresh currentRoot in 1940 // the process. 1941 currentRoot := mc.LastRoot(m) 1942 1943 q := NewHTTPArgs() 1944 if leafID.IsNil() { 1945 q.Add("no_leaf", B{Val: true}) 1946 } else { 1947 q.Add("leaf_id", S{Val: leafID.String()}) 1948 } 1949 paramer(&q) 1950 1951 if apiRes, currentRoot, err = mc.lookupLeafAndPathHelper(m, q, nil, currentRoot, opts); err != nil { 1952 return nil, nil, nil, err 1953 } 1954 1955 path, err = mc.readPathFromAPIRes(m, apiRes, opts) 1956 if err != nil { 1957 return nil, nil, nil, err 1958 } 1959 resSeqno, err := apiRes.Body.AtKey("root").AtKey("seqno").GetInt64() 1960 if err != nil { 1961 return nil, nil, nil, err 1962 } 1963 if keybase1.Seqno(resSeqno) == *currentRoot.Seqno() { 1964 path.root = currentRoot 1965 } else { 1966 path.root, err = mc.readAndCheckRootFromAPIRes(m, apiRes, currentRoot, opts) 1967 if err != nil { 1968 return nil, nil, nil, err 1969 } 1970 } 1971 1972 if err = checker(path); err != nil { 1973 return nil, nil, nil, err 1974 } 1975 1976 if !leafID.IsNil() { 1977 leaf, err = path.verifyUserOrTeam(m, leafID) 1978 if err != nil { 1979 return nil, nil, nil, err 1980 } 1981 1982 if processHiddenResponseFunc != nil { 1983 hiddenResp, err = processHiddenResponseFunc(m, leafID.AsTeamOrBust(), apiRes, path.root.BlindMerkleRootHash()) 1984 if err != nil { 1985 return nil, nil, nil, err 1986 } 1987 } 1988 } 1989 1990 return leaf, path.root, hiddenResp, nil 1991} 1992 1993func (mc *MerkleClient) LookupTeamWithHidden(m MetaContext, teamID keybase1.TeamID, processHiddenRespFunc ProcessHiddenRespFunc) (leaf *MerkleTeamLeaf, hiddenResp *MerkleHiddenResponse, lastMerkleRoot *MerkleRoot, err error) { 1994 // Copied from LookupUser. These methods should be kept relatively in sync. 1995 return mc.lookupTeam(m, teamID, processHiddenRespFunc) 1996} 1997 1998func (mc *MerkleClient) LookupTeam(m MetaContext, teamID keybase1.TeamID) (leaf *MerkleTeamLeaf, err error) { 1999 // Copied from LookupUser. These methods should be kept relatively in sync. 2000 leaf, _, _, err = mc.lookupTeam(m, teamID, nil) 2001 return leaf, err 2002} 2003 2004type MerkleHiddenResponseType uint8 2005 2006const ( 2007 // the server did not include any hidden chain data 2008 MerkleHiddenResponseTypeNONE MerkleHiddenResponseType = 1 2009 // the server provided a proof of absence (or inclusion with an empty leaf) for 2010 // the requested key 2011 MerkleHiddenResponseTypeABSENCEPROOF MerkleHiddenResponseType = 2 2012 // the server provided a valid inclusion proof for the returned leaf in the tree 2013 MerkleHiddenResponseTypeOK MerkleHiddenResponseType = 3 2014 2015 // All hidden checks should be skipped as the feature flag is off 2016 MerkleHiddenResponseTypeFLAGOFF MerkleHiddenResponseType = 127 2017) 2018 2019type MerkleHiddenResponse struct { 2020 RespType MerkleHiddenResponseType `json:"resp_type"` 2021 CommittedHiddenTail *sig3.Tail `json:"committed_hidden_tail"` 2022 UncommittedSeqno keybase1.Seqno `json:"uncommitted_seqno"` 2023} 2024 2025func (m *MerkleHiddenResponse) GetUncommittedSeqno() keybase1.Seqno { 2026 if m == nil { 2027 return 0 2028 } 2029 return m.UncommittedSeqno 2030} 2031 2032func (m *MerkleHiddenResponse) GetCommittedSeqno() keybase1.Seqno { 2033 if m == nil || m.RespType != MerkleHiddenResponseTypeOK { 2034 return 0 2035 } 2036 return m.CommittedHiddenTail.Seqno 2037} 2038 2039type ProcessHiddenRespFunc func(m MetaContext, teamID keybase1.TeamID, apiRes *APIRes, blindRootHash string) (*MerkleHiddenResponse, error) 2040 2041func (mc *MerkleClient) lookupTeam(m MetaContext, teamID keybase1.TeamID, processHiddenResponseFunc ProcessHiddenRespFunc) (leaf *MerkleTeamLeaf, hiddenResp *MerkleHiddenResponse, lastMerkleRoot *MerkleRoot, err error) { 2042 2043 m.VLogf(VLog0, "+ MerkleClient.LookupTeam(%v)", teamID) 2044 2045 var path *VerificationPath 2046 var apiRes *APIRes 2047 var opts MerkleOpts 2048 2049 if err = mc.init(m); err != nil { 2050 return nil, nil, nil, err 2051 } 2052 2053 root, err := mc.FetchRootFromServer(m, DefaultMerkleRootFreshness) 2054 if err != nil { 2055 return nil, nil, nil, err 2056 } 2057 q := NewHTTPArgs() 2058 q.Add("leaf_id", S{Val: teamID.String()}) 2059 2060 if path, apiRes, err = mc.lookupLeafAndPath(m, q, root, nil, opts); err != nil { 2061 return nil, nil, nil, err 2062 } 2063 2064 if leaf, err = path.verifyTeam(m, teamID); err != nil { 2065 return nil, nil, nil, err 2066 } 2067 2068 if processHiddenResponseFunc != nil { 2069 hiddenResp, err = processHiddenResponseFunc(m, teamID, apiRes, path.root.BlindMerkleRootHash()) 2070 if err != nil { 2071 return nil, nil, nil, err 2072 } 2073 } 2074 2075 m.VLogf(VLog0, "- MerkleClient.LookupTeam(%v) -> OK", teamID) 2076 return leaf, hiddenResp, path.root, err 2077} 2078 2079func (mr *MerkleRoot) ToSigJSON() (ret *jsonw.Wrapper) { 2080 2081 ret = jsonw.NewDictionary() 2082 _ = ret.SetKey("seqno", jsonw.NewInt(int(*mr.Seqno()))) 2083 _ = ret.SetKey("ctime", jsonw.NewInt64(mr.Ctime())) 2084 _ = ret.SetKey("hash", jsonw.NewString(mr.RootHash().String())) 2085 _ = ret.SetKey("hash_meta", jsonw.NewString(mr.ShortHash().String())) 2086 2087 return 2088} 2089 2090func (mr *MerkleRoot) ToInfo() chat1.MerkleRoot { 2091 return chat1.MerkleRoot{ 2092 Seqno: int64(*mr.Seqno()), 2093 Hash: mr.RootHash().bytes(), 2094 } 2095} 2096 2097func (mr *MerkleRoot) ToMerkleRootV2() keybase1.MerkleRootV2 { 2098 return keybase1.MerkleRootV2{ 2099 Seqno: *mr.Seqno(), 2100 HashMeta: mr.HashMeta(), 2101 } 2102} 2103 2104func (mc *MerkleClient) LastRootToSigJSON(m MetaContext) (ret *jsonw.Wrapper, err error) { 2105 // Lazy-init, only when needed. 2106 if err = mc.init(m); err == nil { 2107 mc.RLock() 2108 if mc.lastRoot != nil { 2109 ret = mc.lastRoot.ToSigJSON() 2110 } 2111 mc.RUnlock() 2112 } 2113 return 2114} 2115 2116func (mul *MerkleUserLeaf) MatchUser(u *User, uid keybase1.UID, nun NormalizedUsername) (err error) { 2117 if mul.username != u.GetName() { 2118 err = MerkleClashError{fmt.Sprintf("vs loaded object: username %s != %s", mul.username, u.GetName())} 2119 } else if mul.uid.NotEqual(u.GetUID()) { 2120 err = MerkleClientError{fmt.Sprintf("vs loaded object: UID %s != %s", mul.uid, u.GetUID()), merkleErrorUIDMismatch} 2121 } else if !nun.IsNil() && !NewNormalizedUsername(mul.username).Eq(nun) { 2122 err = MerkleClashError{fmt.Sprintf("vs given arg: username %s != %s", mul.username, nun)} 2123 } else if uid.NotEqual(mul.uid) { 2124 err = MerkleClashError{fmt.Sprintf("vs given arg: UID %s != %s", uid, mul.uid)} 2125 } 2126 return 2127} 2128 2129func (mt MerkleTriple) Less(mt2 MerkleTriple) bool { 2130 return mt.Seqno < mt2.Seqno 2131} 2132 2133func GetMerkleTriple(jw *jsonw.Wrapper) (ret *MerkleTriple, err error) { 2134 var tmp MerkleTriple 2135 if err = jw.UnmarshalAgain(&tmp); err != nil { 2136 ret = &tmp 2137 } 2138 return ret, err 2139} 2140 2141func (mr MerkleRoot) ShallowCopy() *MerkleRoot { 2142 return &mr 2143} 2144 2145func (mr *MerkleRoot) Seqno() *keybase1.Seqno { 2146 if mr == nil { 2147 return nil 2148 } 2149 tmp := mr.payload.seqno() 2150 return &tmp 2151} 2152 2153func (mr *MerkleRoot) RootHash() NodeHash { 2154 if mr == nil { 2155 return nil 2156 } 2157 return mr.payload.rootHash() 2158} 2159 2160func (mr *MerkleRoot) LegacyUIDRootHash() NodeHash { 2161 if mr == nil { 2162 return nil 2163 } 2164 return mr.payload.legacyUIDRootHash() 2165} 2166 2167func (mr *MerkleRoot) PvlHash() string { 2168 if mr == nil { 2169 return "" 2170 } 2171 return mr.payload.pvlHash() 2172} 2173 2174func (mr *MerkleRoot) ProofServicesHash() string { 2175 if mr == nil { 2176 return "" 2177 } 2178 return mr.payload.proofServicesHash() 2179} 2180 2181func (mr *MerkleRoot) ExternalURLHash() string { 2182 if mr == nil { 2183 return "" 2184 } 2185 return mr.payload.externalURLHash() 2186} 2187 2188func (mr *MerkleRoot) BlindMerkleRootHash() string { 2189 if mr == nil { 2190 return "" 2191 } 2192 return mr.payload.blindMerkleRootHash() 2193} 2194 2195func (mr *MerkleRoot) SkipToSeqno(s keybase1.Seqno) NodeHash { 2196 if mr == nil { 2197 return nil 2198 } 2199 return mr.payload.skipToSeqno(s) 2200} 2201 2202func (mr *MerkleRoot) Ctime() int64 { 2203 if mr == nil { 2204 return 0 2205 } 2206 return mr.payload.ctime() 2207} 2208 2209func (mr *MerkleRoot) Fetched() time.Time { 2210 if mr == nil { 2211 return time.Time{} 2212 } 2213 return mr.fetched 2214} 2215 2216func (mr *MerkleRoot) KBFSPrivate() (keybase1.KBFSRootHash, *keybase1.Seqno) { 2217 if mr == nil { 2218 return nil, nil 2219 } 2220 return mr.payload.kbfsPrivate() 2221} 2222 2223func (mr *MerkleRoot) KBFSPublic() (keybase1.KBFSRootHash, *keybase1.Seqno) { 2224 if mr == nil { 2225 return nil, nil 2226 } 2227 return mr.payload.kbfsPublic() 2228} 2229 2230func (mr *MerkleRoot) KBFSPrivateTeam() (keybase1.KBFSRootHash, *keybase1.Seqno) { 2231 if mr == nil { 2232 return nil, nil 2233 } 2234 return mr.payload.kbfsPrivateTeam() 2235} 2236 2237func (mrp MerkleRootPayload) skipToSeqno(s keybase1.Seqno) NodeHash { 2238 if mrp.unpacked.Body.Skips == nil { 2239 return nil 2240 } 2241 return mrp.unpacked.Body.Skips[s] 2242} 2243 2244func (mrp MerkleRootPayload) seqno() keybase1.Seqno { return mrp.unpacked.Body.Seqno } 2245func (mrp MerkleRootPayload) rootHash() NodeHash { return mrp.unpacked.Body.Root } 2246func (mrp MerkleRootPayload) legacyUIDRootHash() NodeHash { return mrp.unpacked.Body.LegacyUIDRoot } 2247func (mrp MerkleRootPayload) pvlHash() string { return mrp.unpacked.Body.PvlHash } 2248func (mrp MerkleRootPayload) proofServicesHash() string { return mrp.unpacked.Body.ProofServicesHash } 2249func (mrp MerkleRootPayload) externalURLHash() string { return mrp.unpacked.Body.ExternalURLHash } 2250func (mrp MerkleRootPayload) blindMerkleRootHash() string { 2251 return mrp.unpacked.Body.BlindMerkleRootHash 2252} 2253func (mrp MerkleRootPayload) ctime() int64 { return mrp.unpacked.Ctime } 2254func (mrp MerkleRootPayload) kbfsPrivate() (keybase1.KBFSRootHash, *keybase1.Seqno) { 2255 return mrp.unpacked.Body.Kbfs.Private.Root, mrp.unpacked.Body.Kbfs.Private.Version 2256} 2257func (mrp MerkleRootPayload) kbfsPublic() (keybase1.KBFSRootHash, *keybase1.Seqno) { 2258 return mrp.unpacked.Body.Kbfs.Public.Root, mrp.unpacked.Body.Kbfs.Public.Version 2259} 2260func (mrp MerkleRootPayload) kbfsPrivateTeam() (keybase1.KBFSRootHash, *keybase1.Seqno) { 2261 return mrp.unpacked.Body.Kbfs.PrivateTeam.Root, mrp.unpacked.Body.Kbfs.PrivateTeam.Version 2262} 2263 2264func (mc *MerkleClient) CanExamineHistoricalRoot(m MetaContext, q keybase1.Seqno) bool { 2265 chk := mc.FirstExaminableHistoricalRoot(m) 2266 if chk == nil { 2267 return true 2268 } 2269 return q >= *chk 2270} 2271