idnits 2.17.1 draft-schiff-ntp-chronos-01.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 (October 21, 2018) is 2014 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'RFC2629' is defined on line 307, but no explicit reference was found in the text == Unused Reference: 'RFC3552' is defined on line 311, but no explicit reference was found in the text == Unused Reference: 'RFC5226' is defined on line 316, 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: April 24, 2019 T. Mizrahi 6 Huawei Network.IO Innovation Lab 7 M. Schapira 8 Hebrew University of Jerusalem 9 October 21, 2018 11 A Secure Selection and Filtering Mechanism for the Network Time Protocol 12 Version 4 13 draft-schiff-ntp-chronos-01 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 April 24, 2019. 43 Copyright Notice 45 Copyright (c) 2018 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. Such an 228 effect is bounded by Chronos' w parameter that is set by default to 229 25ms, which is appropriate for many applications [roughtime]. 231 In scenarios where precision and accuracy are critical, a hybrid 232 approach can be applied: by default NTPv4 updates the local clock but 233 when a threat or evidence of attack is detected (e.g., a system peer 234 is too far from the local clock) Chronos time is considered. 236 6. Acknowledgements 238 The authors would like to thank Miroslav Lichvar, Yaakov.J.Stein and 239 Karen O'Donoghue for contributions to this document and helpful 240 discussions and comments. 242 7. IANA Considerations 244 This memo includes no request to IANA. 246 8. Security Considerations 248 As explained above, a Chronos client repeatedly gathers time samples 249 from small subsets of a large pool of NTP servers. The following 250 form of a man-in-the-middle (MitM) Byzantine attacker is considered: 251 a MitM attacker is assumed to control a subset of the servers in the 252 pool of available servers and is capable of determining precisely the 253 values of the time samples gathered by the Chronos client from these 254 NTP servers. The threat model thus encompasses a broad spectrum of 255 MitM attackers ranging from fairly weak (yet dangerous) MitM 256 attackers only capable of delaying and dropping packets to extremely 257 powerful MitM attackers who are in control of authenticated NTP 258 servers. MitM attackers captured by this framework might be, for 259 example, (1) in direct control of a fraction of the NTP servers 260 (e.g., by exploiting a software vulnerability), (2) an ISP (or other 261 Autonomous-System-level attacker) on the default BGP paths from the 262 NTP client to a fraction of the available servers, (3) a nation state 263 with authority over the owners of NTP servers in its jurisdiction, or 264 (4) an attacker capable of hijacking (e.g., through DNS cache 265 poisoning or BGP prefix hijacking) traffic to some of the available 266 NTP servers. The details of the specific attack scenario are 267 abstracted by reasoning about MitM attackers in terms of the fraction 268 of servers with respect to which the attacker has MitM capabilities. 270 Analytical results (in [Chronos_paper]) indicate that in order to 271 succeed in shifting time at a Chronos client by even a small time 272 shift (e.g., 100ms), even a powerful man-in-the-middle attacker 273 requires many years of effort (e.g., over 20 years in expectation). 275 It should be noted that Chronos provides resilience to MitM attacks 276 that cannot be achieved by cryptographic authentication protocols. 277 However, adding an authentication and crypto-based security layer to 278 the Chronos layer is important for achieving high security guarantees 279 and detection of various spoofing and modification attacks. 281 Further details about the Chronos security considerations and 282 guarantees are discussed in [Chronos_paper]. 284 9. References 286 9.1. Normative References 288 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 289 Requirement Levels", BCP 14, RFC 2119, 290 DOI 10.17487/RFC2119, March 1997, 291 . 293 [RFC5905] Mills, D., Martin, J., Ed., Burbank, J., and W. Kasch, 294 "Network Time Protocol Version 4: Protocol and Algorithms 295 Specification", RFC 5905, DOI 10.17487/RFC5905, June 2010, 296 . 298 9.2. Informative References 300 [Chronos_paper] 301 Deutsch, O., Schiff, N., Dolev, D., and M. Schapira, 302 "Preventing (Network) Time Travel with Chronos", 2018, 303 . 307 [RFC2629] Rose, M., "Writing I-Ds and RFCs using XML", RFC 2629, 308 DOI 10.17487/RFC2629, June 1999, 309 . 311 [RFC3552] Rescorla, E. and B. Korver, "Guidelines for Writing RFC 312 Text on Security Considerations", BCP 72, RFC 3552, 313 DOI 10.17487/RFC3552, July 2003, 314 . 316 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 317 IANA Considerations Section in RFCs", RFC 5226, 318 DOI 10.17487/RFC5226, May 2008, 319 . 321 [roughtime] 322 Patton, C., "Roughtime: Securing Time with Digital 323 Signatures", 2018, 324 . 326 Authors' Addresses 328 Neta Rozen Schiff 329 Hebrew University of Jerusalem 330 Jerusalem 331 Israel 333 Phone: +972 2 549 4599 334 Email: neta.r.schiff@gmail.com 336 Danny Dolev 337 Hebrew University of Jerusalem 338 Jerusalem 339 Israel 341 Phone: +972 2 549 4588 342 Email: danny.dolev@mail.huji.ac.il 344 Tal Mizrahi 345 Huawei Network.IO Innovation Lab 346 Israel 348 Email: tal.mizrahi.phd@gmail.com 350 Michael Schapira 351 Hebrew University of Jerusalem 352 Jerusalem 353 Israel 355 Phone: +972 2 549 4570 356 Email: schapiram@huji.ac.il