Wrap TFM; start splitting sk.i up into more .i's.
[sovereign-keys.git] / issues / timing-corner-cases.txt
1 If the timeline servers are willing to pause additions to their timelines for
2 some time (or run their clocks slow), and collaborate with a Certificate
3 Authority or a party in the DNSSEC hierarchy, they may be able to pretend to
4 have registered new sovereign keys before the actual registrants.
5
6 This attack requires very significant resources, and it must be performed
7 early (when the SK is registered, rather than at any point later).
8
9 Various protocol modifications could be made to place bounds upon how much
10 "pausing" timelines could get away with, or to give SK registrants ways to
11 cryptographically prove that this happened to them, or to perform distributed
12 locking so that the attackers cannot watch legimitate writes and then pretend
13 to have registered that name first.  It is unclear whether such
14 modifications are worth the added complexity, given the corner case nature of
15 the attack and the resources that are risked in performing it.
16
17 (Notes from Jered mapping to this problem below...)
18
19 Thoughts on UTC.
20
21 The sovereign key system uses coordinated universal time (UTC) to define
22 precedence for domain to key mappings and to audit timeline integrity. This is
23 an appealing idea, since UTC is a well-known, independent external reference,
24 and in theory many synchronization problems should reduce to accurate
25 timekeeping.  In practice however, there are many issues around using UTC
26 correctly.
27
28 Monotonicity at one timeline server.
29
30 Expecting timestamps to be monotonic at a single timeline server is dangerous.
31 While rate slew time adjustment facilities like adjtimex(2) and adjtime(3) are
32 common, gettimeofday(2) leap second handling varies between Linux and BSD at
33 least, and the system clock may be set back manually or in a system failure.
34 For example, after reboot a timeline server may be running with an RTC-set or
35 even NTP-adjusted time earlier than one it has previously reported.
36
37 A robust implementation should be resilient to timestamp sequence breaks.
38
39 Sequence breaks may cause a timeline server to send inconsistent freshness, e.g.
40 - At time t, the timeline has N records, followed by
41 - At time t', the timeline has N+1 records, t' < t.
42 Taken together these messages invalidate a timeline.
43
44 Sequence breaks may also cause a timeline server to register entries with
45 incorrect precedence, i.e. to insert into rather than append onto the timeline.
46
47 A naive solution is to wait. Do not respond to any requests unless the current
48 system time is newer than the newest reported or stored timestamp. This
49 requires atomically storing and updating a newest timestamp before doing
50 anything. There are serious DoS implications if a time far in the future is
51 ever reported or stored.
52  
53    : pde I like the "wait" solution.  If we are a timeline there are three
54    cases: (1) our clock is slighlty wrong for legitimate reasons; (2) our
55    clock is very wrong; (3) our clock is fine but some other timeline has a very
56    wrong clock, which may mean it's been compromised or something.  In case 1
57    waiting is correct; in case 2 the best action may be to raise errors or
58    something but waiting is at least safe; in 3 it would be best to proceed
59    with caution.
60
61 A better solution is to maintain a locally consistent, monotonic time
62 reference at each timeline server such as seconds since Nth process start
63 using a monotonic counter of process starts, and a monotonic relative time
64 reference such as clock_gettime(3) with CLOCK_MONOTONIC. These local
65 timestamps can be used to check integrity and precedence for that timeline. An
66 observer may also verify that they are always increasing. Best estimate UTC
67 timestamps could still be stored and sent along with these timestamps to
68 provide some assurance of recency, without permanently invalidating a
69 timeline.
70
71 Global consistency.
72
73 The system needs to order events between distributed timeline servers. UTC seems
74 attractive for collation because each timeline server can be updated
75 independently, and Internet hosts can track a UTC reference to +/-0.2s, which
76 intuitively seems close enough.
77
78 One problem is the timeline server with the slowest clock gets precedence when a
79 registration is contested, which incentivizes bad timekeeping. A larger problem
80 is that only a single time measurement at a single timeline server tracks
81 precedence, and registrants have no way to verify or contest this measurement.
82 A still larger problem is that, prior to collation, there is no way to know if
83 a new domain to key mapping has precedence on some other timeline server.
84
85 An interesting notion is to maintain a logical clock to establish a
86 happened-before relation using message passing between timeline servers. Doing
87 this synchronously probably assumes some knowledge of the topology of timeline
88 servers which it would be better not to assume. But it might be possible to
89 sample the correlation between timeline times to bound inconsistency.
90
91 If timeline A sees freshness updates from B, it can deduce that timestamp tb0
92 happened before its current timestamp ta0 and include a statement of this in
93 its own freshness. Any registrations before tb0 precede those after ta0. From
94 pairwise combinations of such facts, a mirror should be able to deduce
95 precedence to within the resolution of its freshness samples. When there is
96 ambiguity, we might prefer a tiebreaker such as longest timeline length rather
97 than lowest timestamp.
98
99 If we also have the property that a timeline consistent with another timeline at
100 some time implies that it incorporates all those records, and are assured that
101 updates to a timeline are self-consistent, we could provide bounds on the window
102 in which an inconsistency with a previously seen timeline may be present...
103
104 TODO... flesh this out some more.
105
106 Miscellaneous.
107
108 Atomicity and freshness at one timeline server.
109
110 A timeline server must report freshness, timeline length N as of a recent time
111 T.  Writes queued for the store with timestamps t < T may land after T or
112 never. So when computing freshness at T, a careless implementation may
113 under-report (fail to count queued writes that will succeed), or over-report
114 (count queued writes that will fail) timeline length, and thus invalidate the
115 timeline.
116
117 To be safe, an implementation should compute freshness updates atomically under
118 hard locks. For example:
119 1. Flush the store queue. Block new requests and commit all pending writes.
120 2. Query the maximum committed serial number N.
121 3. Read current timestamp T.
122 4. Update freshness with (T, N).
123
124 Also:
125 Previously a timeline has reported it has N entries as of time T, but a merged
126 timeline may have 2N entries as of time T according to the timeline itself. This
127 requires that freshness be computed always with reference to the current
128 monotonic timestamp, not the newest stored timestamp.