idnits 2.17.1 draft-schiff-ntp-chronos-00.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 (June 28, 2018) is 2119 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'RFC2629' is defined on line 289, but no explicit reference was found in the text == Unused Reference: 'RFC3552' is defined on line 293, but no explicit reference was found in the text == Unused Reference: 'RFC5226' is defined on line 298, 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: December 30, 2018 T. Mizrahi 6 Marvell 7 M. Schapira 8 Hebrew University of Jerusalem 9 June 28, 2018 11 A Secure Selection and Filtering Mechanism for the Network Time Protocol 12 Version 4 13 draft-schiff-ntp-chronos-00 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 December 30, 2018. 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. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 5 70 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 6 71 7. Security Considerations . . . . . . . . . . . . . . . . . . . 6 72 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 6 73 8.1. Normative References . . . . . . . . . . . . . . . . . . 7 74 8.2. Informative References . . . . . . . . . . . . . . . . . 7 75 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 7 77 1. Introduction 79 According to RFC 5905 [RFC5905], the NTP servers used for updating 80 the client's time are chosen by the clock filter algorithm and the 81 system process. However, this method may be vulnerable to time 82 shifting attacks, in which the attacker's goal is to shift the local 83 time of an NTP client. Time shifting attacks on NTP are possible 84 even if all NTP communications are encrypted and authenticated. This 85 document introduces an improved system process with a secure 86 algorithm called Chronos. Chronos is backwards compatible with 87 NTPv4, as an NTP client that runs Chronos is interoperable with 88 [RFC5905]-compatible NTPv4 servers. 90 Chronos achieves accurate synchronization even in the presence of 91 powerful attackers who are in direct control of a large number of NTP 92 servers. Chronos leverages ideas from distributed computing 93 literature on clock synchronization in the presence of adversarial 94 (Byzantine) behaviour. 96 A Chronos client iteratively "crowdsources" time queries across 97 multiple NTP servers and applies a provably secure algorithm for 98 eliminating "suspicious" responses and averaging over the remaining 99 responses. Chronos is carefully engineered to minimize communication 100 overhead so as to avoid overloading NTP servers. Chronos' security 101 was evaluated both theoretically and experimentally with a prototype 102 implementation. The experimental results indicate that in order to 103 implement a successful time-shifting attack on a Chronos client by 104 over 100ms from the UTC, even a powerful man-in-the-middle attacker 105 requires over 20 years of effort in expectation. The full paper is 106 in [Chronos_paper]. 108 Chronos differs from the current NTPv4 in two aspects. First, the 109 Chronos client relies on a large number of NTP servers, from which 110 only few are chosen at random in order to avoid overloading the 111 servers. Second, the selection algorithm uses an approximate 112 agreement technique to remove outliers, thus limiting the attacker's 113 ability to contaminate the chosen time samples. These Chronos client 114 mechanisms have provable security guarantees against man-in-the- 115 middle attackers and attackers who are capable of compromising a 116 large number of NTP servers. 118 2. Conventions Used in This Document 120 2.1. Terminology 122 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 123 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 124 document are to be interpreted as described in RFC 2119 [RFC2119]. 126 2.2. Terms and Abbreviations 128 NTPv4 Network Time Protocol version 4 [RFC5905]. 130 Selection process Clock filter algorithm and system process 131 [RFC5905]. 133 2.3. Notations 134 Describing Chronos algorithm, the following notation are used. 136 +---------+---------------------------------------------------------+ 137 | Notaion | Meaning | 138 +---------+---------------------------------------------------------+ 139 | w | An upper bound on the distance from the local time at | 140 | | any NTP server with an accurate clock ("truechimer" as | 141 | | in [RFC5905]) | 142 | Cest | the client's estimate for the time that passed since | 143 | | its last synchronization to the server pool (sec) | 144 | ERR | (2W*Cest)/1000 | 145 | K | panic trigger | 146 | tc | the current time, as indicated by the client's local | 147 | | clock [sec] | 148 +---------+---------------------------------------------------------+ 150 Table 1: Chronos Notations 152 3. Extension for NTP Selection Process 154 A client that runs Chronos does not implement the functionality 155 described in Sections 10 and 11 in [RFC5905]. Instead, the client 156 implements the behavior described in this section and the next one. 158 3.1. Peer calibration Process 160 The peer calibration process gathers a server pool of hundreds of 161 servers. Each NTP client conducts the peer process as in Section 9 162 in [RFC5905], on an hourly basis for 24 consecutive hours and 163 generates the union of all received IP addresses. Importantly, this 164 is executed in the background once in a long time (e.g., every few 165 weeks/months). 167 3.2. Chronos Selection Process 169 The Chronos selection process samples the server pool and removes 170 outliers (replaces the clock filter algorithm and the system process 171 as in [RFC5905]). First, a subset on the order of tens of the 172 servers in the server pool is selected at random. Then, out of the 173 tens of collected samples, the third lowest-value samples and third 174 highest value samples are discarded. 176 Given the remaining samples, Chronos checks two conditions: 178 o The maximal distance between every two time samples does not 179 exceed 2w. 181 o The average value of the remaining samples is at a distance of at 182 most ERR+2w from the client's local clock. 184 (where w,ERR are described in Table 1). 186 In the event that both of these conditions are satisfied, the average 187 of the remaining samples is the "final offset". Otherwise, a few 188 tens of the servers from the pool are sampled again, in the exact 189 same manner. This re-sampling process continues until the two 190 conditions are finally satisfied or the number of times the servers 191 are re-sampled exceeds a "Panic Trigger" (K in Table 1), in which 192 case, Chronos enters a "Panic Mode". 194 In panic mode a Chronos client queries all the servers in the server 195 pool, orders the collected time samples from lowest to highest and 196 eliminates the bottom third and the top third of the samples. The 197 client then averages over the remaining samples, which become the new 198 "final offset". 200 As in [RFC5905], the final offset is passed to the clock discipline 201 algorithm to steer the system clock to the correct time. 203 4. Chronos Pseudocode 205 The Chronos pseudocode Time Sampling Scheme is the following: 207 counter := 0 208 While counter < K do 209 S := sample(m) //gather sample from tens randomly chosen servers 210 T := bi-side-trim(S,1/3) //trim third lowest and highest values 211 if (max(T) -min(T) <= 2w) and (|avg(T)-tc| < ERR + 2w) Then 212 return avg(t) 213 end 214 counter ++; 215 end 216 // panic mode; 217 S := sample(n); 218 T := bi-sided-trim(S,n/3) //trim bottom and top thrids; 219 return avg(T) 221 5. Acknowledgements 223 ... 225 6. IANA Considerations 227 This memo includes no request to IANA. 229 7. Security Considerations 231 As explained above, a Chronos client repeatedly gathers time samples 232 from small subsets of a large pool of NTP servers. The following 233 form of a man-in-the-middle (MitM) Byzantine attacker is considered: 234 a MitM attacker is assumed to control a subset of the servers in the 235 pool of available servers and is capable of determining precisely the 236 values of the time samples gathered by the Chronos client from these 237 NTP servers. The threat model thus encompasses a broad spectrum of 238 MitM attackers ranging from fairly weak (yet dangerous) MitM 239 attackers only capable of delaying and dropping packets to extremely 240 powerful MitM attackers who are in control of authenticated NTP 241 servers. MitM attackers captured by this framework might be, for 242 example, (1) in direct control of a fraction of the NTP servers 243 (e.g., by exploiting a software vulnerability), (2) an ISP (or other 244 Autonomous-System-level attacker) on the default BGP paths from the 245 NTP client to a fraction of the available servers, (3) a nation state 246 with authority over the owners of NTP servers in its jurisdiction, or 247 (4) an attacker capable of hijacking (e.g., through DNS cache 248 poisoning or BGP prefix hijacking) traffic to some of the available 249 NTP servers. The details of the specific attack scenario are 250 abstracted by reasoning about MitM attackers in terms of the fraction 251 of servers with respect to which the attacker has MitM capabilities. 253 Analytical results (in [Chronos_paper]) indicate that in order to 254 succeed in shifting time at a Chronos client by even a small time 255 shift (e.g., 100ms), even a powerful man-in-the-middle attacker 256 requires many years of effort (e.g., over 20 years in expectation). 258 It should be noted that Chronos provides resilience to MitM attacks 259 that cannot be achieved by cryptographic authentication protocols. 260 However, adding an authentication and crypto-based security layer to 261 the Chronos layer is important for achieving high security guarantees 262 and detection of various spoofing and modification attacks. 264 Further details about the Chronos security considerations and 265 guarantees are discussed in [Chronos_paper]. 267 8. References 268 8.1. Normative References 270 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 271 Requirement Levels", BCP 14, RFC 2119, 272 DOI 10.17487/RFC2119, March 1997, 273 . 275 [RFC5905] Mills, D., Martin, J., Ed., Burbank, J., and W. Kasch, 276 "Network Time Protocol Version 4: Protocol and Algorithms 277 Specification", RFC 5905, DOI 10.17487/RFC5905, June 2010, 278 . 280 8.2. Informative References 282 [Chronos_paper] 283 Deutsch, O., Schiff, N., Dolev, D., and M. Schapira, 284 "Preventing (Network) Time Travel with Chronos", 2018, 285 . 289 [RFC2629] Rose, M., "Writing I-Ds and RFCs using XML", RFC 2629, 290 DOI 10.17487/RFC2629, June 1999, 291 . 293 [RFC3552] Rescorla, E. and B. Korver, "Guidelines for Writing RFC 294 Text on Security Considerations", BCP 72, RFC 3552, 295 DOI 10.17487/RFC3552, July 2003, 296 . 298 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 299 IANA Considerations Section in RFCs", RFC 5226, 300 DOI 10.17487/RFC5226, May 2008, 301 . 303 Authors' Addresses 305 Neta Rozen Schiff 306 Hebrew University of Jerusalem 307 Jerusalem 308 Israel 310 Phone: +972 2 549 4599 311 Email: neta.r.schiff@gmail.com 312 Danny Dolev 313 Hebrew University of Jerusalem 314 Jerusalem 315 Israel 317 Phone: +972 2 549 4588 318 Email: danny.dolev@mail.huji.ac.il 320 Tal Mizrahi 321 Marvell 322 6 Hamada St. 323 Yokneam 2066721 324 Israel 326 Email: talmi@marvell.com 328 Michael Schapira 329 Hebrew University of Jerusalem 330 Jerusalem 331 Israel 333 Phone: +972 2 549 4570 334 Email: schapiram@huji.ac.il