/
sig_chain.go
1323 lines (1139 loc) · 39.5 KB
/
sig_chain.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// Copyright 2015 Keybase, Inc. All rights reserved. Use of
// this source code is governed by the included BSD license.
package libkb
import (
"errors"
"fmt"
"io"
"io/ioutil"
"time"
"github.com/buger/jsonparser"
keybase1 "github.com/keybase/client/go/protocol/keybase1"
)
type ChainLinks []*ChainLink
//
// As of Sigchain V2, there are 3 types of sigchain links you might
// encounter.
//
// V1 AKA Inner: The original sigchain link is a JSON blob describing
// the signer's eldest key, signing key, payload, and prev pointers,
// among other fields. As we migrate to sigchain V2, this is known as the
// "inner" link. It persists in some cases and is elided for bandwidth
// savings in others.
//
// V2 AKA Outer/Inner Split: In V2, the signer computes a signature over
// a much smaller outer link (see OuterLinkV2 in chain_link_v2.go). The
// "curr" field in the outer link points to a V1 inner link by content hash.
// Essential fields from the V1 inner link are hoisted up into the V2 outer
// link and therefore must agree. Thus, the "prev" pointer in the V2 outer
// link is the same as the "prev" pointer in the V2 inner link; it equals
// the "curr" pointer of the previous outer link.
//
// V2 Stubbed: To save bandwidth, the server is allowed to send over just
// the V2 Outer link, minus any signatures, minus an inner link, if the
// consuming client can safely ignore those details.
//
type SigChain struct {
Contextified
uid keybase1.UID
username NormalizedUsername
chainLinks ChainLinks // all the links we know about, starting with seqno 1
idVerified bool
loadedFromLinkOne bool
wasFullyCached bool
// If we've locally delegated a key, it won't be reflected in our
// loaded chain, so we need to make a note of it here.
localCki *ComputedKeyInfos
// If we've made local modifications to our chain, mark it here;
// there's a slight lag on the server and we might not get the
// new chain tail if we query the server right after an update.
localChainTail *MerkleTriple
// When the local chain was updated.
localChainUpdateTime time.Time
// The sequence number of the first chain link in the current subchain. For
// a user who has never done a reset, this is 1. Note that if the user has
// done a reset (or just created a fresh account) but not yet made any
// signatures, this seqno refers to a link that doesn't yet exist.
currentSubchainStart keybase1.Seqno
// In some cases, it is useful to load all existing subchains for this user.
// If so, they will be slotted into this slice.
prevSubchains []ChainLinks
}
func (sc SigChain) Len() int {
return len(sc.chainLinks)
}
func (c ChainLinks) EldestSeqno() keybase1.Seqno {
if len(c) == 0 {
return keybase1.Seqno(0)
}
return c[0].GetSeqno()
}
func (sc *SigChain) LocalDelegate(kf *KeyFamily, key GenericKey, sigID keybase1.SigID, signingKid keybase1.KID, isSibkey bool, mhm keybase1.HashMeta, fau keybase1.Seqno) (err error) {
sc.G().Log.Debug("SigChain#LocalDelegate(key: %s, sigID: %s, signingKid: %s, isSibkey: %v)", key.GetKID(), sigID, signingKid, isSibkey)
cki := sc.localCki
l := sc.GetLastLink()
if cki == nil && l != nil && l.cki != nil {
// TODO: Figure out whether this needs to be a deep copy. See
// https://github.com/keybase/client/issues/414 .
cki = l.cki.ShallowCopy()
}
if cki == nil {
sc.G().Log.Debug("LocalDelegate: creating new cki (signingKid: %s)", signingKid)
cki = NewComputedKeyInfos(sc.G())
cki.InsertLocalEldestKey(signingKid)
}
// Update the current state
sc.localCki = cki
if len(sigID) > 0 {
var zeroTime time.Time
err = cki.Delegate(key.GetKID(), NowAsKeybaseTime(0), sigID, signingKid, signingKid, "" /* pgpHash */, isSibkey, time.Unix(0, 0), zeroTime, mhm, fau, keybase1.SigChainLocation{})
}
return
}
func (sc *SigChain) LocalDelegatePerUserKey(perUserKey keybase1.PerUserKey) error {
cki := sc.localCki
l := sc.GetLastLink()
if cki == nil && l != nil && l.cki != nil {
// TODO: Figure out whether this needs to be a deep copy. See
// https://github.com/keybase/client/issues/414 .
cki = l.cki.ShallowCopy()
}
if cki == nil {
return errors.New("LocalDelegatePerUserKey: no computed key info")
}
// Update the current state
sc.localCki = cki
err := cki.DelegatePerUserKey(perUserKey)
return err
}
func (sc *SigChain) EldestSeqno() keybase1.Seqno {
return sc.currentSubchainStart
}
func (c ChainLinks) GetComputedKeyInfos() (cki *ComputedKeyInfos) {
ll := last(c)
if ll == nil {
return nil
}
return ll.cki
}
func (sc SigChain) GetComputedKeyInfos() (cki *ComputedKeyInfos) {
cki = sc.localCki
if cki == nil {
if l := sc.GetLastLink(); l != nil {
if l.cki == nil {
sc.G().Log.Debug("GetComputedKeyInfos: l.cki is nil")
}
cki = l.cki
}
}
return
}
func (sc SigChain) GetComputedKeyInfosWithVersionBust() (cki *ComputedKeyInfos) {
ret := sc.GetComputedKeyInfos()
if ret == nil {
return ret
}
if ret.IsStaleVersion() {
sc.G().Log.Debug("Threw out CKI due to stale version (%d)", ret.Version)
ret = nil
}
return ret
}
func (sc SigChain) GetFutureChainTail() (ret *MerkleTriple) {
now := sc.G().Clock().Now()
if sc.localChainTail != nil && now.Sub(sc.localChainUpdateTime) < ServerUpdateLag {
ret = sc.localChainTail
}
return
}
func reverse(links ChainLinks) {
for i, j := 0, len(links)-1; i < j; i, j = i+1, j-1 {
links[i], links[j] = links[j], links[i]
}
}
func first(links ChainLinks) (ret *ChainLink) {
if len(links) == 0 {
return nil
}
return links[0]
}
func last(links ChainLinks) (ret *ChainLink) {
if len(links) == 0 {
return nil
}
return links[len(links)-1]
}
func (sc *SigChain) VerifiedChainLinks(fp PGPFingerprint) (ret ChainLinks) {
last := sc.GetLastLink()
if last == nil || !last.sigVerified {
return nil
}
start := -1
for i := len(sc.chainLinks) - 1; i >= 0 && sc.chainLinks[i].MatchFingerprint(fp); i-- {
start = i
}
if start >= 0 {
ret = ChainLinks(sc.chainLinks[start:])
}
return ret
}
func (sc *SigChain) Bump(mt MerkleTriple) {
mt.Seqno = sc.GetLastKnownSeqno() + 1
sc.G().Log.Debug("| Bumping SigChain LastKnownSeqno to %d", mt.Seqno)
sc.localChainTail = &mt
sc.localChainUpdateTime = sc.G().Clock().Now()
}
func (sc *SigChain) LoadFromServer(m MetaContext, t *MerkleTriple, selfUID keybase1.UID) (dirtyTail *MerkleTriple, err error) {
m, tbs := m.WithTimeBuckets()
low := sc.GetLastLoadedSeqno()
sc.loadedFromLinkOne = (low == keybase1.Seqno(0) || low == keybase1.Seqno(-1))
m.CDebugf("+ Load SigChain from server (uid=%s, low=%d)", sc.uid, low)
defer func() { m.CDebugf("- Loaded SigChain -> %s", ErrToOk(err)) }()
resp, finisher, err := sc.G().API.GetResp(APIArg{
Endpoint: "sig/get",
SessionType: APISessionTypeOPTIONAL,
Args: HTTPArgs{
"uid": UIDArg(sc.uid),
"low": I{int(low)},
"v2_compressed": B{true},
},
MetaContext: m,
})
if err != nil {
return
}
if finisher != nil {
defer finisher()
}
recordFin := tbs.Record("SigChain.LoadFromServer.ReadAll")
body, err := ioutil.ReadAll(resp.Body)
if err != nil {
recordFin()
return nil, err
}
recordFin()
return sc.LoadServerBody(m, body, low, t, selfUID)
}
func (sc *SigChain) LoadServerBody(m MetaContext, body []byte, low keybase1.Seqno, t *MerkleTriple, selfUID keybase1.UID) (dirtyTail *MerkleTriple, err error) {
// NOTE: This status only gets set from the server if the requesting user
// has not interacted with the deleted user. The idea being if you have
// interacted (chatted, etc) with this user you should still verify their
// sigchain. Otherwise you can ignore it.
if val, err := jsonparser.GetInt(body, "status", "code"); err == nil {
if keybase1.StatusCode(val) == keybase1.StatusCode_SCDeleted {
// Do not bother trying to read the sigchain - user is
// deleted.
return nil, UserDeletedError{}
}
}
foundTail := false
var links ChainLinks
var tail *ChainLink
numEntries := 0
jsonparser.ArrayEach(body, func(value []byte, dataType jsonparser.ValueType, offset int, inErr error) {
var link *ChainLink
if link, err = ImportLinkFromServer(m, sc, value, selfUID); err != nil {
m.CDebugf("ImportLinkFromServer error: %s", err)
return
}
if link.GetSeqno() <= low {
return
}
// After we know it's not a dupe, let's put the link to cache.
putLinkToCache(m, link)
if selfUID.Equal(link.GetUID()) {
m.CDebugf("| Setting isOwnNewLinkFromServer=true for seqno %d", link.GetSeqno())
link.isOwnNewLinkFromServer = true
}
links = append(links, link)
if !foundTail && t != nil {
if foundTail, err = link.checkAgainstMerkleTree(t); err != nil {
return
}
}
tail = link
numEntries++
}, "sigs")
if err != nil {
return nil, err
}
m.CDebugf("| Got back %d new entries", numEntries)
if t != nil && !foundTail {
err = NewServerChainError("Failed to reach (%s, %d) in server response",
t.LinkID, int(t.Seqno))
return nil, err
}
if tail != nil {
dirtyTail = tail.ToMerkleTriple()
// If we've stored a `last` and it's less than the one
// we just loaded, then nuke it.
if sc.localChainTail != nil && sc.localChainTail.Less(*dirtyTail) {
m.CDebugf("| Clear cached last (%d < %d)", sc.localChainTail.Seqno, dirtyTail.Seqno)
sc.localChainTail = nil
sc.localCki = nil
}
}
sc.chainLinks = append(sc.chainLinks, links...)
return dirtyTail, nil
}
func (sc *SigChain) SetUIDUsername(uid keybase1.UID, username string) {
sc.uid = uid
sc.username = NewNormalizedUsername(username)
}
func (sc *SigChain) getFirstSeqno() (ret keybase1.Seqno) {
if len(sc.chainLinks) > 0 {
ret = sc.chainLinks[0].GetSeqno()
}
return ret
}
func (sc *SigChain) VerifyChain(m MetaContext) (err error) {
defer m.CTrace("SigChain#VerifyChain", func() error { return err })()
for i := len(sc.chainLinks) - 1; i >= 0; i-- {
curr := sc.chainLinks[i]
m.VLogf(VLog1, "| verify link %d (%s)", i, curr.id)
if curr.chainVerified {
m.CDebugf("| short-circuit at link %d", i)
break
}
if err = curr.VerifyLink(); err != nil {
return err
}
if i > 0 {
prev := sc.chainLinks[i-1]
// NB: In a sigchain v2 link, `id` refers to the hash of the
// *outer* link, not the hash of the v1-style inner payload.
if !prev.id.Eq(curr.GetPrev()) {
return ChainLinkPrevHashMismatchError{fmt.Sprintf("Chain mismatch at seqno=%d", curr.GetSeqno())}
}
if prev.GetSeqno()+1 != curr.GetSeqno() {
return ChainLinkWrongSeqnoError{fmt.Sprintf("Chain seqno mismatch at seqno=%d (previous=%d)", curr.GetSeqno(), prev.GetSeqno())}
}
}
if err = curr.CheckNameAndID(sc.username, sc.uid); err != nil {
return err
}
curr.markChainVerified()
}
return err
}
func (sc SigChain) GetCurrentTailTriple() (ret *MerkleTriple) {
if l := sc.GetLastLink(); l != nil {
ret = l.ToMerkleTriple()
}
return
}
func (sc SigChain) GetLastLoadedID() (ret LinkID) {
if l := last(sc.chainLinks); l != nil {
ret = l.id
}
return
}
func (sc SigChain) GetLastKnownID() (ret LinkID) {
if sc.localChainTail != nil {
ret = sc.localChainTail.LinkID
} else {
ret = sc.GetLastLoadedID()
}
return
}
func (sc SigChain) GetFirstLink() *ChainLink {
return first(sc.chainLinks)
}
func (sc SigChain) GetLastLink() *ChainLink {
return last(sc.chainLinks)
}
func (sc SigChain) GetLastKnownSeqno() (ret keybase1.Seqno) {
sc.G().Log.Debug("+ GetLastKnownSeqno()")
defer func() {
sc.G().Log.Debug("- GetLastKnownSeqno() -> %d", ret)
}()
if sc.localChainTail != nil {
sc.G().Log.Debug("| Cached in last summary object...")
ret = sc.localChainTail.Seqno
} else {
ret = sc.GetLastLoadedSeqno()
}
return
}
func (sc SigChain) GetLastLoadedSeqno() (ret keybase1.Seqno) {
sc.G().Log.Debug("+ GetLastLoadedSeqno()")
defer func() {
sc.G().Log.Debug("- GetLastLoadedSeqno() -> %d", ret)
}()
if l := last(sc.chainLinks); l != nil {
sc.G().Log.Debug("| Fetched from main chain")
ret = l.GetSeqno()
}
return
}
func (sc *SigChain) Store(m MetaContext) (err error) {
for i := len(sc.chainLinks) - 1; i >= 0; i-- {
link := sc.chainLinks[i]
var didStore bool
if didStore, err = link.Store(m); err != nil || !didStore {
return err
}
select {
case <-m.Ctx().Done():
return m.Ctx().Err()
default:
}
}
return nil
}
// Some users (6) managed to reuse eldest keys after a sigchain reset, without
// using the "eldest" link type, before the server prohibited this. To clients,
// that means their chains don't appear to reset. We hardcode these cases.
const resetReason = "hardcoded reset"
var hardcodedResets = map[keybase1.LinkID]SpecialChainLink{
"f6dae096194690cfee8974b0e10a99ecac2cc8e4f9383516a1f626f614e566e0": SpecialChainLink{UID: keybase1.UID("2d5c41137d7d9108dbdaa2160ba7e200"), Seqno: keybase1.Seqno(11), Reason: resetReason},
"8d7c1a0c99186f972afc5d3624aca2f88ddc3a5dbf84e826ef0b520c31a78aa3": SpecialChainLink{UID: keybase1.UID("f1c263462dd526695c458af924977719"), Seqno: keybase1.Seqno(18), Reason: resetReason},
"b489635b4243ef80836a0c4515ed7e30e146f0041704931df280c72e28e9d0fe": SpecialChainLink{UID: keybase1.UID("8dbf0f1617e285befa93d3da54b68419"), Seqno: keybase1.Seqno(8), Reason: resetReason},
"bc898feeb7a2717e23dc1f457dc18902fb9157bf86374b2a0b1aaba4f2831bee": SpecialChainLink{UID: keybase1.UID("372c1cbd72e4f851a74d232478a72319"), Seqno: keybase1.Seqno(2), Reason: resetReason},
"91cb1b2c3c76d2ad54be47b034a3f544da9ea8405f6eb68a929ef5fb98914436": SpecialChainLink{UID: keybase1.UID("12e124d5d1ff6179f3aab88100b93d19"), Seqno: keybase1.Seqno(5), Reason: resetReason},
"af381fd3a43e22edc2ac1f271e3270b92038e4a820de335d179d34eb780f8796": SpecialChainLink{UID: keybase1.UID("a07089770463db10994c8727177eef19"), Seqno: keybase1.Seqno(12), Reason: resetReason},
}
// GetCurrentSubchain takes the given sigchain and walks backward until it
// finds the start of the current subchain, returning all the links in the
// subchain. See isSubchainStart for the details of the logic here.
func (sc *SigChain) GetCurrentSubchain(m MetaContext, eldest keybase1.KID) (ChainLinks, error) {
return cropToRightmostSubchain(m, sc.chainLinks, eldest, sc.uid)
}
// cropToRightmostSubchain takes the given set of chain links, and then limits the tail
// of the chain to just those that correspond to the eldest key given by `eldest`.
func cropToRightmostSubchain(m MetaContext, links []*ChainLink, eldest keybase1.KID, uid keybase1.UID) (ChainLinks, error) {
// Check for a totally empty chain (that is, a totally new account).
if len(links) == 0 {
return nil, nil
}
// Confirm that the last link is not stubbed. This would prevent us from
// reading the eldest_kid, so the server should never do it.
lastLink := links[len(links)-1]
if lastLink.IsStubbed() {
return nil, errors.New("the last chain link is unexpectedly stubbed in GetCurrentSunchain")
}
// Check whether the eldest KID doesn't match the latest link. That means
// the account has just been reset, and so as with a new account, there is
// no current subchain.
if !lastLink.ToEldestKID().Equal(eldest) {
return nil, nil
}
// The usual case: The eldest kid we're looking for matches the latest
// link, and we need to loop backwards through every pair of links we have.
// If we find a subchain start, return that subslice of links.
for i := len(links) - 1; i > 0; i-- {
curr := links[i]
prev := links[i-1]
isStart, err := isSubchainStart(m, curr, prev, uid)
if err != nil {
return nil, err
}
if isStart {
return links[i:], nil
}
}
// If we didn't find a start anywhere in the middle of the chain, then this
// user has no resets, and we'll return the whole chain. Sanity check that
// we actually loaded everything back to seqno 1. (Anything else would be
// some kind of bug in chain loading.)
if links[0].GetSeqno() != 1 {
return nil, errors.New("chain ended unexpectedly before seqno 1 in GetCurrentSubchain")
}
// In this last case, we're returning the whole chain.
return links, nil
}
// When we're *in the middle of a subchain* (see the note below), there are
// four ways we can tell that a link is the start of a new subchain:
// 1) The link is seqno 1, the very first link the user ever makes.
// 2) The link has the type "eldest". Modern seqno 1 links and sigchain resets
// take this form, but old ones don't.
// 3) The link has a new eldest kid relative to the one that came before. In
// the olden days, all sigchain resets were of this form. Note that oldest
// links didn't have the eldest_kid field at all, so the signing kid was
// assumed to be the eldest.
// 4) One of a set of six hardcoded links that made it in back when case 3 was
// the norm, but we forgot to prohibit reusing the same eldest key. We figured
// out this set from server data, once we noticed the mistake.
//
// Note: This excludes cases where a subchain has length zero, either because
// the account is totally new, or because it just did a reset but has no new
// links (as reflected in the eldest kid we get from the merkle tree).
// Different callers handle those cases differently. (Loading the sigchain from
// local cache happens before we get the merkle leaf, for example, and so it
// punts reset-after-latest-link detection to the server loading step).
func isSubchainStart(m MetaContext, currentLink *ChainLink, prevLink *ChainLink, uid keybase1.UID) (bool, error) {
// case 1 -- unlikely to be hit in practice, because prevLink would be nil
if currentLink.GetSeqno() == 1 {
return true, nil
}
// case 2
if currentLink.IsEldest() {
return true, nil
}
// case 2.5: The signatures in cases 3 and 4 are very old, from long before
// v2 sigs were introduced. If either the current or previous sig is v2,
// short circuit here. This is important because stubbed links (introduced
// with v2) break the eldest_kid check for case 3.
if currentLink.unpacked.sigVersion > 1 || prevLink.unpacked.sigVersion > 1 {
return false, nil
}
// case 3
if !currentLink.ToEldestKID().Equal(prevLink.ToEldestKID()) {
return true, nil
}
// case 4
found, _, err := currentLink.checkSpecialLinksTable(hardcodedResets, uid, "harcoded resets")
if err != nil {
m.CWarningf("Error in isSubchainStart: %s", err.Error())
return false, err
}
if found {
m.CDebugf("Sigchain playback hit hardcoded reset at %s for %s", currentLink.LinkID(), uid)
}
return found, nil
}
// Dump prints the sigchain to the writer arg.
func (sc *SigChain) Dump(w io.Writer) {
fmt.Fprintf(w, "sigchain dump\n")
for i, l := range sc.chainLinks {
fmt.Fprintf(w, "link %d: %+v\n", i, l)
}
fmt.Fprintf(w, "last known seqno: %d\n", sc.GetLastKnownSeqno())
fmt.Fprintf(w, "last known id: %s\n", sc.GetLastKnownID())
}
// verifySubchain verifies the given subchain and outputs a yes/no answer
// on whether or not it's well-formed, and also yields ComputedKeyInfos for
// all keys found in the process, including those that are now retired.
func (sc *SigChain) verifySubchain(m MetaContext, kf KeyFamily, links ChainLinks) (cached bool, cki *ComputedKeyInfos, err error) {
un := sc.username
m.CDebugf("+ verifySubchain")
defer func() {
m.CDebugf("- verifySubchain -> %v, %s", cached, ErrToOk(err))
}()
if len(links) == 0 {
err = InternalError{"verifySubchain should never get an empty chain."}
return cached, cki, err
}
last := links[len(links)-1]
if cki = last.GetSigCheckCache(); cki != nil {
if cki.IsStaleVersion() {
m.CDebugf("Ignoring cached CKI, since the version is old (%d < %d)", cki.Version, ComputedKeyInfosVersionCurrent)
} else {
cached = true
m.CDebugf("Skipped verification (cached): %s", last.id)
return cached, cki, err
}
}
cki = NewComputedKeyInfos(sc.G())
ckf := ComputedKeyFamily{kf: &kf, cki: cki, Contextified: sc.Contextified}
first := true
seenInflatedWalletStellarLink := false
for linkIndex, link := range links {
isBad, reason, err := link.IsBad()
if err != nil {
return cached, cki, err
}
if isBad {
m.CDebugf("Ignoring bad chain link with link ID %s: %s", link.LinkID(), reason)
continue
}
if link.IsStubbed() {
if first {
return cached, cki, SigchainV2StubbedFirstLinkError{}
}
if !link.AllowStubbing() {
return cached, cki, SigchainV2StubbedSignatureNeededError{}
}
linkTypeV2, err := link.GetSigchainV2TypeFromV2Shell()
if err != nil {
return cached, cki, err
}
if linkTypeV2 == SigchainV2TypeWalletStellar && seenInflatedWalletStellarLink {
// There may not be stubbed wallet links following an unstubbed wallet links (for a given network).
// So that the server can't roll back someone's active wallet address.
return cached, cki, SigchainV2StubbedDisallowed{}
}
sc.G().VDL.Log(VLog1, "| Skipping over stubbed-out link: %s", link.id)
continue
}
tcl, w := NewTypedChainLink(link)
if w != nil {
w.Warn(sc.G())
}
sc.G().VDL.Log(VLog1, "| Verify link: %s %v %v", link.id, link.chainVerified, link.hashVerified)
if first {
if err = ckf.InsertEldestLink(tcl, un); err != nil {
return cached, cki, err
}
first = false
}
// Optimization: only check sigs on some links, like the final
// link, or those that delegate and revoke keys.
// Note that we do this *before* processing revocations in the key
// family. That's important because a chain link might revoke the same
// key that signed it.
isDelegating := (tcl.GetRole() != DLGNone)
isModifyingKeys := isDelegating || tcl.Type() == string(DelegationTypePGPUpdate)
isFinalLink := (linkIndex == len(links)-1)
hasRevocations := link.HasRevocations()
sc.G().VDL.Log(VLog1, "| isDelegating: %v, isModifyingKeys: %v, isFinalLink: %v, hasRevocations: %v",
isDelegating, isModifyingKeys, isFinalLink, hasRevocations)
if pgpcl, ok := tcl.(*PGPUpdateChainLink); ok {
if hash := pgpcl.GetPGPFullHash(); hash != "" {
m.CDebugf("| Setting active PGP hash for %s: %s", pgpcl.kid, hash)
ckf.SetActivePGPHash(pgpcl.kid, hash)
}
}
if isModifyingKeys || isFinalLink || hasRevocations {
err = link.VerifySigWithKeyFamily(ckf)
if err != nil {
m.CDebugf("| Failure in VerifySigWithKeyFamily: %s", err)
return cached, cki, err
}
}
if isDelegating {
err = ckf.Delegate(tcl)
if err != nil {
m.CDebugf("| Failure in Delegate: %s", err)
return cached, cki, err
}
}
if pukl, ok := tcl.(*PerUserKeyChainLink); ok {
err := ckf.cki.DelegatePerUserKey(pukl.ToPerUserKey())
if err != nil {
return cached, cki, err
}
}
if _, ok := tcl.(*WalletStellarChainLink); ok {
// Assert that wallet chain links are be >= v2.
// They must be v2 in order to be stubbable later for privacy.
if link.unpacked.sigVersion < 2 {
return cached, cki, SigchainV2Required{}
}
seenInflatedWalletStellarLink = true
}
if err = tcl.VerifyReverseSig(ckf); err != nil {
m.CDebugf("| Failure in VerifyReverseSig: %s", err)
return cached, cki, err
}
if err = ckf.Revoke(tcl); err != nil {
return cached, cki, err
}
if err = ckf.UpdateDevices(tcl); err != nil {
return cached, cki, err
}
if err != nil {
m.CDebugf("| bailing out on error: %s", err)
return cached, cki, err
}
}
last.PutSigCheckCache(cki)
return cached, cki, err
}
func (sc *SigChain) verifySigsAndComputeKeysCurrent(m MetaContext, eldest keybase1.KID, ckf *ComputedKeyFamily) (cached bool, linksConsumed int, err error) {
cached = false
m.CDebugf("+ verifySigsAndComputeKeysCurrent for user %s (eldest = %s)", sc.uid, eldest)
defer func() {
m.CDebugf("- verifySigsAndComputeKeysCurrent for user %s -> %s", sc.uid, ErrToOk(err))
}()
if err = sc.VerifyChain(m); err != nil {
return cached, 0, err
}
// AllKeys mode is now the default.
if first := sc.getFirstSeqno(); first > keybase1.Seqno(1) {
err = ChainLinkWrongSeqnoError{fmt.Sprintf("Wanted a chain from seqno=1, but got seqno=%d", first)}
return cached, 0, err
}
// There are 3 cases that we have to think about here for recording the
// start of the current subchain (and a fourth where we don't make it here
// at all, when the chain is fully cached and fresh):
//
// 1. The chain is totally empty, because the user is new.
// 2. The chain has links, but the user just did a reset, and so the
// current subchain is empty.
// 3. The common case: a user with some links in the current subchain.
//
// In cases 1 and 2 we say the subchain start is zero, an invalid seqno.
// Write that out now, to overwrite anything we computed during local
// sigchain loading.
sc.currentSubchainStart = 0
if ckf.kf == nil || eldest.IsNil() {
m.CDebugf("| VerifyWithKey short-circuit, since no Key available")
sc.localCki = NewComputedKeyInfos(sc.G())
ckf.cki = sc.localCki
return cached, 0, err
}
links, err := cropToRightmostSubchain(m, sc.chainLinks, eldest, sc.uid)
if err != nil {
return cached, 0, err
}
// Update the subchain start if we're in case 3 from above.
if len(links) > 0 {
sc.currentSubchainStart = links[0].GetSeqno()
}
if len(links) == 0 {
m.CDebugf("| Empty chain after we limited to eldest %s", eldest)
eldestKey, _ := ckf.FindKeyWithKIDUnsafe(eldest)
sc.localCki = NewComputedKeyInfos(sc.G())
err = sc.localCki.InsertServerEldestKey(eldestKey, sc.username)
ckf.cki = sc.localCki
return cached, 0, err
}
if cached, ckf.cki, err = sc.verifySubchain(m, *ckf.kf, links); err != nil {
return cached, len(links), err
}
// We used to check for a self-signature of one's keybase username
// here, but that doesn't make sense because we haven't accounted
// for revocations. We'll go it later, after reconstructing
// the id_table. See LoadUser in user.go and
// https://github.com/keybase/go/issues/43
return cached, len(links), nil
}
func reverseListOfChainLinks(arr []ChainLinks) {
for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
arr[i], arr[j] = arr[j], arr[i]
}
}
func (c ChainLinks) omittingNRightmostLinks(n int) ChainLinks {
return c[0 : len(c)-n]
}
// VerifySigsAndComputeKeys iterates over all potentially all incarnations of the user, trying to compute
// multiple subchains. It returns (bool, error), where bool is true if the load hit the cache, and false otherwise.
func (sc *SigChain) VerifySigsAndComputeKeys(m MetaContext, eldest keybase1.KID, ckf *ComputedKeyFamily) (bool, error) {
// First consume the currently active sigchain.
cached, numLinksConsumed, err := sc.verifySigsAndComputeKeysCurrent(m, eldest, ckf)
if err != nil || ckf.kf == nil {
return cached, err
}
allCached := cached
// Now let's examine any historical subchains, if there are any.
historicalLinks := sc.chainLinks.omittingNRightmostLinks(numLinksConsumed)
if len(historicalLinks) > 0 {
m.CDebugf("After consuming %d links, there are %d historical links left",
numLinksConsumed, len(historicalLinks))
// ignore error here, since it shouldn't kill the overall load if historical subchains don't run
// correctly.
cached, _ = sc.verifySigsAndComputeKeysHistorical(m, historicalLinks, *ckf.kf)
if !cached {
allCached = false
}
}
return allCached, nil
}
func (sc *SigChain) verifySigsAndComputeKeysHistorical(m MetaContext, allLinks ChainLinks, kf KeyFamily) (allCached bool, err error) {
defer m.CTrace("verifySigsAndComputeKeysHistorical", func() error { return err })()
var cached bool
var prevSubchains []ChainLinks
for {
if len(allLinks) == 0 {
m.CDebugf("Ending iteration through previous subchains; no further links")
break
}
i := len(allLinks) - 1
link := allLinks[i]
eldest := link.ToEldestKID()
seqno := link.GetSeqno()
if eldest.IsNil() {
m.CDebugf("Ending iteration through previous subchains; saw a nil eldest (@%d)", seqno)
break
}
m.CDebugf("Examining subchain that ends at %d with eldest %s", seqno, eldest)
var links ChainLinks
links, err = cropToRightmostSubchain(m, allLinks, eldest, sc.uid)
if err != nil {
m.CInfof("Error backtracking all links from %d: %s", seqno, err)
break
}
cached, _, err = sc.verifySubchain(m, kf, links)
if err != nil {
m.CInfof("Error verifying subchain from %d: %s", seqno, err)
break
}
if !cached {
allCached = false
}
prevSubchains = append(prevSubchains, links)
allLinks = allLinks.omittingNRightmostLinks(len(links))
}
reverseListOfChainLinks(prevSubchains)
m.CDebugf("Loaded %d additional historical subchains", len(prevSubchains))
sc.prevSubchains = prevSubchains
return allCached, nil
}
func (sc *SigChain) GetLinkFromSeqno(seqno keybase1.Seqno) *ChainLink {
for _, link := range sc.chainLinks {
if link.GetSeqno() == keybase1.Seqno(seqno) {
return link
}
}
return nil
}
func (sc *SigChain) GetLinkFromSigID(id keybase1.SigID) *ChainLink {
for _, link := range sc.chainLinks {
if link.GetSigID().Equal(id) {
return link
}
}
return nil
}
// GetLinkFromSigIDQuery will return true if it finds a ChainLink
// with a SigID that starts with query.
func (sc *SigChain) GetLinkFromSigIDQuery(query string) *ChainLink {
for _, link := range sc.chainLinks {
if link.GetSigID().Match(query, false) {
return link
}
}
return nil
}
//========================================================================
type ChainType struct {
DbType ObjType
Private bool
Encrypted bool
GetMerkleTriple func(u *MerkleUserLeaf) *MerkleTriple
}
var PublicChain = &ChainType{
DbType: DBSigChainTailPublic,
Private: false,
Encrypted: false,
GetMerkleTriple: func(u *MerkleUserLeaf) *MerkleTriple { return u.public },
}
//========================================================================
type SigChainLoader struct {
MetaContextified
user *User
self bool
leaf *MerkleUserLeaf
chain *SigChain
chainType *ChainType
links ChainLinks
ckf ComputedKeyFamily
dirtyTail *MerkleTriple
currentSubchainStart keybase1.Seqno
// The preloaded sigchain; maybe we're loading a user that already was
// loaded, and here's the existing sigchain.
preload *SigChain
}
//========================================================================
func (l *SigChainLoader) LoadLastLinkIDFromStorage() (mt *MerkleTriple, err error) {
var tmp MerkleTriple
var found bool
found, err = l.G().LocalDb.GetInto(&tmp, l.dbKey())
if err != nil {
l.G().Log.Debug("| Error loading last link: %s", err)
} else if !found {
l.G().Log.Debug("| LastLinkId was null")
} else {
mt = &tmp
}
return
}
func (l *SigChainLoader) AccessPreload() bool {
if l.preload == nil {
l.G().Log.Debug("| Preload not provided")
return false
}
l.G().Log.Debug("| Preload successful")
src := l.preload.chainLinks
l.links = make(ChainLinks, len(src))
copy(l.links, src)
return true
}
func (l *SigChainLoader) LoadLinksFromStorage() (err error) {
uid := l.user.GetUID()
defer l.M().CTraceTimed(fmt.Sprintf("SigChainLoader.LoadFromStorage(%s)", uid),
func() error { return err })()
var mt *MerkleTriple
if mt, err = l.LoadLastLinkIDFromStorage(); err != nil || mt == nil || mt.LinkID == nil {
l.M().CDebugf("| short-circuting LoadLinksFromStorage: LoadLastLinkIDFromStorage returned err=%v", err)
if mt == nil {
l.M().CDebugf("| mt (MerkleTriple) nil result from load last link ID from storage")
}
if mt != nil && mt.LinkID == nil {
l.M().CDebugf("| mt (MerkleTriple) from storage has a nil link ID")
}
return err
}
currentLink, err := ImportLinkFromStorage(l.M(), mt.LinkID, l.selfUID())
if err != nil {
return err
}
if currentLink == nil {
l.M().CDebugf("tried to load previous link ID %s, but link not found", mt.LinkID.String())