idnits 2.17.1 draft-schiff-ntp-chronos-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (September 2, 2019) is 1697 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'RFC2629' is defined on line 310, but no explicit reference was found in the text == Unused Reference: 'RFC3552' is defined on line 314, but no explicit reference was found in the text == Unused Reference: 'RFC5226' is defined on line 319, but no explicit reference was found in the text -- Obsolete informational reference (is this intentional?): RFC 2629 (Obsoleted by RFC 7749) -- Obsolete informational reference (is this intentional?): RFC 5226 (Obsoleted by RFC 8126) Summary: 0 errors (**), 0 flaws (~~), 5 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group N. R.Schiff 3 Internet-Draft D. Dolev 4 Intended status: Informational Hebrew University of Jerusalem 5 Expires: March 5, 2020 T. Mizrahi 6 Huawei Network.IO Innovation Lab 7 M. Schapira 8 Hebrew University of Jerusalem 9 September 2, 2019 11 A Secure Selection and Filtering Mechanism for the Network Time Protocol 12 Version 4 13 draft-schiff-ntp-chronos-03 15 Abstract 17 The Network Time Protocol version 4 (NTPv4) defines the peer process, 18 the clock filter algorithm, the system process and the clock 19 description algorithm. The clock filter algorithm and the system 20 process, as defined in RFC 5905, are the mechanism according to which 21 an NTP client chooses the NTP servers it synchronized with. This 22 document specifies an alternative set of client mechanisms, named 23 Chronos, that is backward compatible with NTPv4, and offers an 24 improved level of security against time shifting attacks. 26 Status of This Memo 28 This Internet-Draft is submitted in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF). Note that other groups may also distribute 33 working documents as Internet-Drafts. The list of current Internet- 34 Drafts is at https://datatracker.ietf.org/drafts/current/. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 This Internet-Draft will expire on March 5, 2020. 43 Copyright Notice 45 Copyright (c) 2019 IETF Trust and the persons identified as the 46 document authors. All rights reserved. 48 This document is subject to BCP 78 and the IETF Trust's Legal 49 Provisions Relating to IETF Documents 50 (https://trustee.ietf.org/license-info) in effect on the date of 51 publication of this document. Please review these documents 52 carefully, as they describe your rights and restrictions with respect 53 to this document. Code Components extracted from this document must 54 include Simplified BSD License text as described in Section 4.e of 55 the Trust Legal Provisions and are provided without warranty as 56 described in the Simplified BSD License. 58 Table of Contents 60 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 61 2. Conventions Used in This Document . . . . . . . . . . . . . . 3 62 2.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 63 2.2. Terms and Abbreviations . . . . . . . . . . . . . . . . . 3 64 2.3. Notations . . . . . . . . . . . . . . . . . . . . . . . . 3 65 3. Extension for NTP Selection Process . . . . . . . . . . . . . 4 66 3.1. Peer calibration Process . . . . . . . . . . . . . . . . 4 67 3.2. Chronos Selection Process . . . . . . . . . . . . . . . . 4 68 4. Chronos Pseudocode . . . . . . . . . . . . . . . . . . . . . 5 69 5. Precision Vs. Security . . . . . . . . . . . . . . . . . . . 5 70 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 6 71 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 6 72 8. Security Considerations . . . . . . . . . . . . . . . . . . . 6 73 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 7 74 9.1. Normative References . . . . . . . . . . . . . . . . . . 7 75 9.2. Informative References . . . . . . . . . . . . . . . . . 7 76 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 8 78 1. Introduction 80 According to RFC 5905 [RFC5905], the NTP servers used for updating 81 the client's time are chosen by the clock filter algorithm and the 82 system process. However, this method may be vulnerable to time 83 shifting attacks, in which the attacker's goal is to shift the local 84 time of an NTP client. Time shifting attacks on NTP are possible 85 even if all NTP communications are encrypted and authenticated. This 86 document introduces an improved system process with a secure 87 algorithm called Chronos. Chronos is backwards compatible with 88 NTPv4, as an NTP client that runs Chronos is interoperable with 89 [RFC5905]-compatible NTPv4 servers. 91 Chronos achieves accurate synchronization even in the presence of 92 powerful attackers who are in direct control of a large number of NTP 93 servers. Chronos leverages ideas from distributed computing 94 literature on clock synchronization in the presence of adversarial 95 (Byzantine) behaviour. 97 A Chronos client iteratively "crowdsources" time queries across 98 multiple NTP servers and applies a provably secure algorithm for 99 eliminating "suspicious" responses and averaging over the remaining 100 responses. Chronos is carefully engineered to minimize communication 101 overhead so as to avoid overloading NTP servers. Chronos' security 102 was evaluated both theoretically and experimentally with a prototype 103 implementation. The experimental results indicate that in order to 104 implement a successful time-shifting attack on a Chronos client by 105 over 100ms from the UTC, even a powerful man-in-the-middle attacker 106 requires over 20 years of effort in expectation. The full paper is 107 in [Chronos_paper]. 109 Chronos differs from the current NTPv4 in two aspects. First, the 110 Chronos client relies on a large number of NTP servers, from which 111 only few are chosen at random in order to avoid overloading the 112 servers. Second, the selection algorithm uses an approximate 113 agreement technique to remove outliers, thus limiting the attacker's 114 ability to contaminate the chosen time samples. These Chronos client 115 mechanisms have provable security guarantees against man-in-the- 116 middle attackers and attackers who are capable of compromising a 117 large number of NTP servers. 119 2. Conventions Used in This Document 121 2.1. Terminology 123 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 124 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 125 document are to be interpreted as described in RFC 2119 [RFC2119]. 127 2.2. Terms and Abbreviations 129 NTPv4 Network Time Protocol version 4 [RFC5905]. 131 Selection process Clock filter algorithm and system process 132 [RFC5905]. 134 2.3. Notations 135 Describing Chronos algorithm, the following notation are used. 137 +---------+---------------------------------------------------------+ 138 | Notaion | Meaning | 139 +---------+---------------------------------------------------------+ 140 | w | An upper bound on the distance from the local time at | 141 | | any NTP server with an accurate clock ("truechimer" as | 142 | | in [RFC5905]) | 143 | Cest | the client's estimate for the time that passed since | 144 | | its last synchronization to the server pool (sec) | 145 | ERR | (2W*Cest)/1000 | 146 | K | panic trigger | 147 | tc | the current time, as indicated by the client's local | 148 | | clock [sec] | 149 +---------+---------------------------------------------------------+ 151 Table 1: Chronos Notations 153 3. Extension for NTP Selection Process 155 A client that runs Chronos does not implement the functionality 156 described in Sections 10 and 11 in [RFC5905]. Instead, the client 157 implements the behavior described in this section and the next one. 159 3.1. Peer calibration Process 161 The peer calibration process gathers a server pool of hundreds of 162 servers. Each NTP client conducts the peer process as in Section 9 163 in [RFC5905], on an hourly basis for 24 consecutive hours and 164 generates the union of all received IP addresses. Importantly, this 165 is executed in the background once in a long time (e.g., every few 166 weeks/months). 168 3.2. Chronos Selection Process 170 The Chronos selection process samples the server pool and removes 171 outliers (replaces the clock filter algorithm and the system process 172 as in [RFC5905]). First, a subset on the order of tens of the 173 servers in the server pool is selected at random. Then, out of the 174 tens of collected samples, the third lowest-value samples and third 175 highest value samples are discarded. 177 Given the remaining samples, Chronos checks two conditions: 179 o The maximal distance between every two time samples does not 180 exceed 2w. 182 o The average value of the remaining samples is at a distance of at 183 most ERR+2w from the client's local clock. 185 (where w,ERR are described in Table 1). 187 In the event that both of these conditions are satisfied, the average 188 of the remaining samples is the "final offset". Otherwise, a few 189 tens of the servers from the pool are sampled again, in the exact 190 same manner. This re-sampling process continues until the two 191 conditions are finally satisfied or the number of times the servers 192 are re-sampled exceeds a "Panic Trigger" (K in Table 1), in which 193 case, Chronos enters a "Panic Mode". 195 In panic mode a Chronos client queries all the servers in the server 196 pool, orders the collected time samples from lowest to highest and 197 eliminates the bottom third and the top third of the samples. The 198 client then averages over the remaining samples, which become the new 199 "final offset". 201 As in [RFC5905], the final offset is passed to the clock discipline 202 algorithm to steer the system clock to the correct time. 204 4. Chronos Pseudocode 206 The Chronos pseudocode Time Sampling Scheme is the following: 208 counter := 0 209 While counter < K do 210 S := sample(m) //gather sample from tens randomly chosen servers 211 T := bi-side-trim(S,1/3) //trim third lowest and highest values 212 if (max(T) -min(T) <= 2w) and (|avg(T)-tc| < ERR + 2w) Then 213 return avg(t) 214 end 215 counter ++; 216 end 217 // panic mode; 218 S := sample(n); 219 T := bi-sided-trim(S,n/3) //trim bottom and top thrids; 220 return avg(T) 222 5. Precision Vs. Security 224 Chronos client changes the list of the sampled servers more 225 frequently than NTPv4 [Chronos_paper], without using NTPv4 filters. 226 This enables Chronos to be provably more secure than NTPv4 [RFC5905] 227 but might adversely affect its precision and accuracy. Therefore we 228 add the following smoothing mechanism: Chronos returns the offset 229 with minimal absolute value unless its distance from the average 230 offset is larger than a predefined value. Another approach we 231 considered was to use the same set of servers as in the previous 232 sample, unless the difference between the current offset and the new 233 offset is larger than a predefined value. 235 In our experiments we observed that with the smoothing mechanism, 236 Chornos and NTP are similar in terms of precision and accuracy when 237 there is no attack. 239 6. Acknowledgements 241 The authors would like to thank Miroslav Lichvar, Yaakov.J.Stein and 242 Karen O'Donoghue for contributions to this document and helpful 243 discussions and comments. 245 7. IANA Considerations 247 This memo includes no request to IANA. 249 8. Security Considerations 251 As explained above, a Chronos client repeatedly gathers time samples 252 from small subsets of a large pool of NTP servers. The following 253 form of a man-in-the-middle (MitM) Byzantine attacker is considered: 254 a MitM attacker is assumed to control a subset of the servers in the 255 pool of available servers and is capable of determining precisely the 256 values of the time samples gathered by the Chronos client from these 257 NTP servers. The threat model thus encompasses a broad spectrum of 258 MitM attackers ranging from fairly weak (yet dangerous) MitM 259 attackers only capable of delaying and dropping packets to extremely 260 powerful MitM attackers who are in control of authenticated NTP 261 servers. MitM attackers captured by this framework might be, for 262 example, (1) in direct control of a fraction of the NTP servers 263 (e.g., by exploiting a software vulnerability), (2) an ISP (or other 264 Autonomous-System-level attacker) on the default BGP paths from the 265 NTP client to a fraction of the available servers, (3) a nation state 266 with authority over the owners of NTP servers in its jurisdiction, or 267 (4) an attacker capable of hijacking (e.g., through DNS cache 268 poisoning or BGP prefix hijacking) traffic to some of the available 269 NTP servers. The details of the specific attack scenario are 270 abstracted by reasoning about MitM attackers in terms of the fraction 271 of servers with respect to which the attacker has MitM capabilities. 273 Analytical results (in [Chronos_paper]) indicate that in order to 274 succeed in shifting time at a Chronos client by even a small time 275 shift (e.g., 100ms), even a powerful man-in-the-middle attacker 276 requires many years of effort (e.g., over 20 years in expectation). 278 It should be noted that Chronos provides resilience to MitM attacks 279 that cannot be achieved by cryptographic authentication protocols. 280 However, adding an authentication and crypto-based security layer to 281 the Chronos layer is important for achieving high security guarantees 282 and detection of various spoofing and modification attacks. 284 Further details about the Chronos security considerations and 285 guarantees are discussed in [Chronos_paper]. 287 9. References 289 9.1. Normative References 291 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 292 Requirement Levels", BCP 14, RFC 2119, 293 DOI 10.17487/RFC2119, March 1997, 294 . 296 [RFC5905] Mills, D., Martin, J., Ed., Burbank, J., and W. Kasch, 297 "Network Time Protocol Version 4: Protocol and Algorithms 298 Specification", RFC 5905, DOI 10.17487/RFC5905, June 2010, 299 . 301 9.2. Informative References 303 [Chronos_paper] 304 Deutsch, O., Schiff, N., Dolev, D., and M. Schapira, 305 "Preventing (Network) Time Travel with Chronos", 2018, 306 . 310 [RFC2629] Rose, M., "Writing I-Ds and RFCs using XML", RFC 2629, 311 DOI 10.17487/RFC2629, June 1999, 312 . 314 [RFC3552] Rescorla, E. and B. Korver, "Guidelines for Writing RFC 315 Text on Security Considerations", BCP 72, RFC 3552, 316 DOI 10.17487/RFC3552, July 2003, 317 . 319 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 320 IANA Considerations Section in RFCs", RFC 5226, 321 DOI 10.17487/RFC5226, May 2008, 322 . 324 [roughtime] 325 Patton, C., "Roughtime: Securing Time with Digital 326 Signatures", 2018, 327 . 329 Authors' Addresses 331 Neta Rozen Schiff 332 Hebrew University of Jerusalem 333 Jerusalem 334 Israel 336 Phone: +972 2 549 4599 337 Email: neta.r.schiff@gmail.com 339 Danny Dolev 340 Hebrew University of Jerusalem 341 Jerusalem 342 Israel 344 Phone: +972 2 549 4588 345 Email: danny.dolev@mail.huji.ac.il 347 Tal Mizrahi 348 Huawei Network.IO Innovation Lab 349 Israel 351 Email: tal.mizrahi.phd@gmail.com 353 Michael Schapira 354 Hebrew University of Jerusalem 355 Jerusalem 356 Israel 358 Phone: +972 2 549 4570 359 Email: schapiram@huji.ac.il