idnits 2.17.1 draft-ietf-stime-ntpauth-03.txt: ** The Abstract section seems to be numbered Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 36 longer pages, the longest (page 2) being 66 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 37 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 712 instances of too long lines in the document, the longest one being 5 characters in excess of 72. ** The abstract seems to contain references ([11]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. == There are 6 instances of lines with non-RFC2606-compliant FQDNs in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (February 2002) is 8106 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '1' on line 33 looks like a reference -- Missing reference section? '11' on line 145 looks like a reference -- Missing reference section? '7' on line 117 looks like a reference -- Missing reference section? '2' on line 133 looks like a reference -- Missing reference section? '5' on line 143 looks like a reference -- Missing reference section? '12' on line 133 looks like a reference -- Missing reference section? '6' on line 143 looks like a reference -- Missing reference section? '8' on line 143 looks like a reference -- Missing reference section? '4' on line 195 looks like a reference -- Missing reference section? '3' on line 195 looks like a reference -- Missing reference section? '9' on line 231 looks like a reference Summary: 8 errors (**), 0 flaws (~~), 5 warnings (==), 13 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force David L. Mills 3 Internet Draft University of Delaware 4 Standards Track February 2002 6 Public key Cryptography for the Network Time Protocol 7 Version 2 8 < draft-ietf-stime-ntpauth-03.txt > 10 Status of this Memorandum 12 This document is an Internet-Draft and is in full conformance with all 13 provisions of Section 10 of RFC2026. 15 Internet-Drafts are working documents of the Internet Engineering Task 16 Force (IETF), its areas, and its working groups. Note that other groups 17 may also distribute working documents as Internet-Drafts. 19 Internet-Drafts are draft documents valid for a maximum of six months 20 and may be updated, replaced, or obsoleted by other documents at any 21 time. It is inappropriate to use Internet- Drafts as reference material 22 or to cite them other than as "work in progress." 24 The list of current Internet-Drafts can be accessed at 25 http://www.ietf.org/ietf/1id-abstracts.txt 26 The list of Internet-Draft Shadow Directories can be accessed at 27 http://www.ietf.org/shadow.html. This document is an Internet- 28 Draft. 30 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 31 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 32 document are to be interpreted as described in RFC-2119 [1]. 34 1. Abstract 36 This memorandum describes a scheme for authenticating servers to clients 37 using the Network Time Protocol. It extends prior schemes based on 38 symmetric key cryptography to a new scheme based on public key 39 cryptography. The new scheme, called Autokey, is based on the premiss 40 that the IPSEC schemes proposed by the IETF cannot be adopted intact, 41 since that would preclude stateless servers and severely compromise 42 timekeeping accuracy. In addition, the IPSEC model presumes 43 authenticated timestamps are always available; however, 44 cryptographically verified timestamps require interaction between the 45 timekeeping function and authentication function in ways not yet 46 considered in the IPSEC model. 48 The main body of this memorandum contains a description of the security 49 model, approach rationale, protocol design and vulnerability analysis. 51 It obsoletes a previous report [11] primarily in the schemes for 52 distributing public keys and related values. A detailed description of 53 the protocol states, events and transition functions is included. 54 Detailed packet formats and field descriptions are given in the 55 appendix. A prototype of the Autokey design based on this memorandum has 56 been implemented, tested and documented in the NTP Version 4 software 57 distribution for Unix, Windows and VMS at www.ntp.org. 59 While not strictly a security function, the Autokey protocol also 60 provides means to securely retrieve a table of historic leap seconds 61 necessary to convert ordinary civil time (UTC) to atomic time (TAI) 62 where needed. The tables can be retrieved either directly from national 63 time servers operated by NIST or indirectly through NTP and intervening 64 servers. 66 Changes Since the Preceding Draft 68 This is a major rewrite of the previous draft. There are numerous 69 changes scattered through this memorandum to clarify the presentation 70 and add a few new features. Among the most important: 72 1. The reference implementation now uses the OpenSSL cryptographic 73 software library. Besides being somewhat faster than the older RSAref2.0 74 library, it supports several different message digest and signature 75 encryption schemes. 77 2. The Autokey protocol and reference implementation support the Public 78 Key Infrastructure (PKI), including X.500 certificates. 80 3. The Autokey protocol has been redesigned to be simpler, more uniform 81 and more robust. There is only one generic message format and all 82 requests can carry signed parameters. 84 4. Strong assertions are now possible about the authentication of 85 timestamps and filestamps. This makes correctness modeling more robust 86 and simplifies vulnerability assessment. 88 5. Certain security potholes have been filled in, in particular the 89 cookie in client/server and symmetric modes is now encrypted. 91 6. The description of the protocol, its state variables, transition 92 function, inputs and outputs are simpler, less wordy and more amenable 93 to correctness modelling. 95 7. Provisions have been made to handle cases when the endpoint addresses 96 are changed, as in mobile IP. 98 Introduction 100 A distributed network service requires reliable, ubiquitous and 101 survivable provisions to prevent accidental or malicious attacks on the 102 servers and clients in the network or the values they exchange. 103 Reliability requires that clients can determine that received packets 104 are authentic; that is, were actually sent by the intended server and 105 not manufactured or modified by an intruder. Ubiquity requires that any 106 client can verify the authenticity of any server using only public 107 information. Survivability requires protection from faulty 108 implementations, improper operation and possibly malicious clogging and 109 replay attacks with or without data modification. These requirements are 110 especially stringent with widely distributed network services, since 111 damage due to failures can propagate quickly throughout the network, 112 devastating archives, routing databases and monitoring systems and even 113 bring down major portions of the network. 115 The Network Time Protocol (NTP) contains provisions to cryptographically 116 authenticate individual servers as described in the most recent protocol 117 specification RFC-1305 [7]; however, that specification does not provide 118 a scheme for the distribution of cryptographic keys, nor does it provide 119 for the retrieval of cryptographic media that reliably bind the server 120 identification credentials with the associated private keys and related 121 public values. However, conventional key agreement and digital 122 signatures with large client populations can cause significant 123 performance degradations, especially in time critical applications such 124 as NTP. In addition, there are problems unique to NTP in the interaction 125 between the authentication and synchronization functions, since each 126 requires the other. 128 This memorandum describes a cryptographically sound and efficient 129 methodology for use in NTP and similar distributed protocols. As 130 demonstrated in the reports and briefings cited in the references at the 131 end of this memorandum, there is a place for PKI and related schemes, 132 but none of these schemes alone satisfies the requirements of the NTP 133 security model. The various key agreement schemes [2, 5, 12] proposed by 134 the IETF require per-association state variables, which contradicts the 135 principles of the remote procedure call (RPC) paradigm in which servers 136 keep no state for a possibly large client population. An evaluation of 137 the PKI model and algorithms as implemented in the RSAref2.0 package 138 formerly distributed by RSA Laboratories leads to the conclusion that 139 any scheme requiring every NTP packet to carry a PKI digital signature 140 would result in unacceptably poor timekeeping performance. 142 A revised security model and authentication scheme called Autokey was 143 proposed in earlier reports [5, 6, 8]. It has been evolved and refined 144 since then and implemented in NTP Version 4 for Unix, Windows and VMS 145 [11]. It is based on a combination of PKI and a pseudo-random sequence 146 generated by repeated hashes of a cryptographic value involving both 147 public and private components. This scheme has been tested and evaluated 148 in a local environment and in the CAIRN experiment network funded by 149 DARPA. A detailed description of the security model, design principles 150 and implementation experience is presented in this memorandum. 151 Additional information about NTP, including executive summaries, 152 software documentation, briefings and bibliography can be found at 153 www.eecis.udel.edu/~mills/ntp.htm. Additional information about the 154 reference implementation can be found at 155 www.eecis.udel.edu/~ntp/ntp_spool/html/authopt.htm. 157 Security Model 159 NTP security requirements are even more stringent than most other 160 distributed services. First, the operation of the authentication 161 mechanism and the time synchronization mechanism are inextricably 162 intertwined. Reliable time synchronization requires cryptographic keys 163 which are valid only over designated time intervals; but, time intervals 164 can be enforced only when participating servers and clients are reliably 165 synchronized to UTC. Second, the NTP subnet is hierarchical by nature, 166 so time and trust flow from the primary servers at the root through 167 secondary servers to the clients at the leaves. 169 A client can claim authentic to dependent applications only if all 170 servers on the path to the primary servers are bone-fide authentic. In 171 order to emphasize this requirement, in this memorandum the notion of 172 "authentic" is replaced by "proventic", a noun new to English and 173 derived from provenance, as in the provenance of a painting. Having 174 abused the language this far, the suffixes fixable to the various noun 175 and verb derivatives of authentic will be adopted for proventic as well. 176 In NTP each server authenticates the next lower stratum servers and 177 proventicates the lowest stratum (primary) servers. Serious computer 178 linguists would correctly interpret the proventic relation as the 179 transitive closure of the authentic relation. 181 It is important to note that the notion of proventic does not 182 necessarily imply the time is correct. A client considers a server 183 proventic if it can validate its certificate and its apparent time is 184 within the valid interval specified on the certificate. The statement 185 "the client is synchronized to proventic sources" means that the system 186 clock has been set using the time values of one or more proventic client 187 associations and according to the NTP mitigation algorithms. While a 188 certificate authority must satisfy this requirement when signing a 189 certificate request, the certificate itself can be stored in public 190 directories and retrieved over unsecured networks. 192 Over the last several years the IETF has defined and evolved the IPSEC 193 infrastructure for privacy protection and source authentication in the 194 Internet, The infrastructure includes the Encapsulating Security Payload 195 (ESP) [4] and Authentication Header (AH) [3] for IPv4 and IPv6. 196 Cryptographic algorithms that use these headers for various purposes 197 include those developed for the PKI, including MD5 message digests, RSA 198 digital signatures and several variations of Diffie-Hellman key 199 agreements. The fundamental assumption in the security model is that 200 packets transmitted over the Internet can be intercepted by other than 201 the intended receiver, remanufactured in various ways and replayed in 202 whole or part. These packets can cause the client to believe or produce 203 incorrect information, cause protocol operations to fail, interrupt 204 network service or consume precious processor resources. 206 In the case of NTP, the assumed goal of the intruder is to inject false 207 time values, disrupt the protocol or clog the network or servers or 208 clients with spurious packets that exhaust resources and deny service to 209 legitimate applications. The mission of the algorithms and protocols 210 described in this memorandum is to detect and discard spurious packets 211 sent by other than the intended sender or sent by the intended sender, 212 but modified or replayed by an intruder. The cryptographic means of the 213 reference implementation are based on the OpenSSL cryptographic software 214 library available at www.openssl.org, but other libraries with 215 equivalent functionality could be used as well. It is important for 216 distribution and export purposes that the way in which these algorithms 217 are used precludes encryption of any data other than incidental to the 218 construction of digital signatures. 220 There are a number of defense mechanisms already built in the NTP 221 architecture, protocol and algorithms. The fundamental timestamp 222 exchange scheme is inherently resistant to replay attacks. The 223 engineered clock filter, selection and clustering algorithms are 224 designed to defend against evil cliques of Byzantine traitors. While not 225 necessarily designed to defeat determined intruders, these algorithms 226 and accompanying sanity checks have functioned well over the years to 227 deflect improperly operating but presumably friendly scenarios. However, 228 these mechanisms do not securely identify and authenticate servers to 229 clients. Without specific further protection, an intruder can inject any 230 or all of the following mischiefs. Further discussion on the assumed 231 intruder model is given in [9], but beyond the scope of this memorandum. 233 1. An intruder can intercept and archive packets forever, as well as all 234 the public values ever generated and transmitted over the net. 236 2. An intruder can generate packets faster than the server or client can 237 process them, especially if they require expensive cryptographic 238 computations. 240 3. An intruder can originate, intercept, modify and replay a packet. 241 However, it cannot permanently prevent packet transmission over the net; 242 that is, it cannot break the wire, only tell lies and congest it. In 243 this memorandum a distinction is made between a middleman attack, where 244 the intruder can modify and replace an intercepted packet, and a wiretap 245 attack, where the intruder can modify and replay the packet only after 246 the original packet has been received. 248 The following assumptions are fundamental to the Autokey design. They 249 are discussed at some length in the briefing slides and links at 250 www.eecis.udel.edu/~mills/ntp.htm and will not be further elaborated in 251 this memorandum. 253 1. The running times for public key algorithms are relatively long and 254 highly variable. In general, the performance of the synchronization 255 function is badly degraded if these algorithms must be used for every 256 NTP packet. 258 2. In some modes of operation it is not feasible for a server to retain 259 state variables for every client. It is however feasible to regenerated 260 them for a client upon arrival of a packet from that client. 262 3. The lifetime of cryptographic values must be enforced, which requires 263 a reliable system clock. However, the sources that synchronize the 264 system clock must be cryptographically proventicated. This circular 265 interdependence of the timekeeping and proventication functions requires 266 special handling. 268 4. All proventication functions must involve only public values 269 transmitted over the net. Private values must never be disclosed beyond 270 the machine on which they were created. 272 5. Public encryption keys and certificates must be retrievable directly 273 from servers without requiring secured channels; however, the 274 fundamental security of identification credentials and public values 275 bound to those credentials must be a function of external certificate 276 authorities and/or webs of trust. 278 Unlike the ssh security model, where the client must be securely 279 identified to the server, in NTP the server must be securely identified 280 to the client. In ssh each different interface address can be bound to a 281 different name, as returned by a reverse-DNS query. In this design 282 separate public/private key pairs may be required for each interface 283 address with a distinct name. A perceived advantage of this design is 284 that the security compartment can be different for each interface. This 285 allows a firewall, for instance, to require some interfaces to 286 proventicate the client and others not. 288 However, the NTP security model specifically assumes all time values and 289 cryptographic values are public, so there is no need to associate each 290 interface with different cryptographic values. In other words, there is 291 one set of private secrets for the host, not one for each interface. In 292 the NTP design the host name, as returned by the gethostname() Unix 293 library function, represents all interface addresses. Since at least in 294 some host configurations the host name may not be identifiable in a DNS 295 query, the name must be either configured in advance or obtained 296 directly from the server using the Autokey protocol. 298 Approach 300 The Autokey protocol described in this memorandum is designed to meet 301 the following objectives. Again, in-depth discussions on these 302 objectives is in the web briefings and will not be elaborated in this 303 memorandum. Note that here and elsewhere in this memorandum mention of 304 broadcast mode means multicast mode as well, with exceptions noted in 305 the web page at www.eecis.udel.edu/~ntp/ntp_spool/html/assoc.htm. 307 1. It must interoperate with the existing NTP architecture model and 308 protocol design. In particular, it must support the symmetric key scheme 309 described in RFC-1305. As a practical matter, the reference 310 implementation must use the same internal key management system, 311 including the use of 32-bit key IDs and existing mechanisms to store, 312 activate and revoke keys. 314 2. It must provide for the independent collection of cryptographic 315 values and time values. A client is synchronized to a proventic source 316 only when the required cryptographic values have been obtained and 317 verified and the NTP timestamps have passed all sanity checks. 319 3. It must not significantly degrade the potential accuracy of the NTP 320 synchronization algorithms. In particular, it must not make unreasonable 321 demands on the network or host processor and memory resources. 323 4. It must be resistant to cryptographic attacks, specifically those 324 identified in the security model above. In particular, it must be 325 tolerant of operational or implementation variances, such as packet loss 326 or misorder, or suboptimal configurations. 328 5. It must build on a widely available suite of cryptographic 329 algorithms, yet be independent of the particular choice. In particular, 330 it must not require data encryption other than incidental to signature 331 encryption and cookie encryption operations. 333 6. It must function in all the modes supported by NTP, including 334 client/server, broadcast and symmetric modes. 336 7. It must not require intricate per-client or per-server configuration 337 other than the availability of the required cryptographic keys and 338 certificates. 340 8. The reference implementation must contain provisions to generate 341 cryptographic key files specific to each client and server. Eventually, 342 it must contain provisions to validate public values using certificate 343 authorities and/or webs of trust. 345 Autokey Proventication Scheme 347 Autokey public key cryptography is based on the PKI algorithms commonly 348 used in the Secure Shell and Secure Sockets Layer applications. As in 349 these applications Autokey uses keyed message digests to detect packet 350 modification, digital signatures to verify the source and public key 351 algorithms to encrypt session keys or cookies. What makes Autokey 352 cryptography unique is the way in which these algorithms are used to 353 deflect intruder attacks while maintaining the integrity and accuracy of 354 the time synchronization function. 356 The NTP Version 3 symmetric key cryptography uses keyed-MD5 message 357 digests with a 128-bit private key and 32-bit key ID. In order to retain 358 backward compatibility, the key ID space is partitioned in two subspaces 359 at a pivot point of 65536. Symmetric key IDs have values less than the 360 pivot and indefinite lifetime. Autokey key IDs have pseudo-random values 361 equal to or greater than the pivot and are expunged immediately after 362 use. 364 There are three Autokey protocol variants corresponding to each of the 365 three NTP modes: client/server, broadcast and symmetric. All three 366 variants make use of specially contrived session keys, called autokeys, 367 and a precomputed pseudo-random sequence of autokeys with the key IDs 368 saved in a key list. As in the original NTP Version 3 authentication 369 scheme, the Autokey protocol operates separately for each association, 370 so there may be several autokey sequences operating independently at the 371 same time. 373 An autokey is computed from four fields in network byte order as shown 374 below: 376 +-----------+-----------+-----------+-----------+ 377 | Source IP | Dest IP | Key ID | Cookie | 378 +-----------+-----------+-----------+-----------+ 380 The four values are hashed by the MD5 message digest algorithm to 381 produce the 128-bit key value, which in the reference implementation is 382 stored along with the key ID in a cache used for symmetric keys as well 383 as autokeys. Keys are retrieved from the cache by key ID using hash 384 tables and a fast lookup algorithm. 386 The NTP packet format has been augmented to include one or more 387 extension fields piggybacked between the original NTP header and the 388 message authenticator code (MAC) at the end of the packet. For packets 389 without extension fields, the cookie is a shared private value conveyed 390 in encrypted form. For packets with extension fields, the cookie has a 391 default public value of zero, since these packets can be validated 392 independently using digital signatures. 394 For use with IPv4, the Source IP and Dest IP fields contain 32 bits; for 395 use with IPv6, these fields contain 128 bits. In either case the Key ID 396 and Cookie fields contain 32 bits. Thus, an IPv4 autokey has four 32-bit 397 words, while an IPv6 autokey has ten 32-bit words. The source and 398 destination IP addresses and key ID are public values visible in the 399 packet, while the cookie can be a public value or shared private value, 400 depending on the mode. 402 There are some scenarios where the use of endpoint IP addresses may be 403 difficult or impossible. These include configurations where network 404 address translation (NAT) devices are in use or when addresses are 405 changed during an association lifetime due to mobility constraints. For 406 Autokey, the only restriction is that the addresses visible in the 407 transmitted packet must be the same as those used to construct the 408 autokey sequence and key list and that these addresses be the same as 409 those visible in the received packet. Provisions are included in the 410 reference implementation to handle cases when these addresses change, as 411 possible in mobile IP. For scenarios where the endpoint IP addresses are 412 not available, an optional public identification value could be used 413 instead of the addresses. Examples include the Interplanetary Internet, 414 where bundles are identified by name rather than address. Specific 415 provisions are for further study. 417 The key list consists of a sequence of key IDs starting with a 32-bit 418 random private value called the autokey seed. The associated autokey is 419 computed as above using the specified cookie and the first 32 bits in 420 network byte order of this value become the next key ID. Operations 421 continue in this way to generate the entire list, which may have up to 422 100 entries. It may happen that a newly generated key ID is less than 423 the pivot or collides with another one already generated (birthday 424 event). When this happens, which should occur only rarely, the key list 425 is terminated at that point. The lifetime of each key is set to expire 426 one poll interval after its scheduled use. In the reference 427 implementation, the list is terminated when the maximum key lifetime is 428 about one hour. 430 The index of the last key ID in the list is saved along with the next 431 key ID for that entry, collectively called the autokey values. The list 432 is used in reverse order, so that the first autokey used is the last one 433 generated. The Autokey protocol includes a message to retrieve the 434 autokey values and signature, so that subsequent packets can be 435 validated using one or more hashes that eventually match the first key 436 ID (valid) or exceed the index (invalid). This is called the autokey 437 test in the following and is done for every packet, including those with 438 and without extension fields. In the reference implementation the most 439 recent key ID received is saved for comparison with the first 32 bits in 440 network byte order of the next following key value. This minimizes the 441 number of hash operations in case a packet is lost. 443 Autokey Operations 445 Autokey works differently in the various NTP modes. The scheme used in 446 client/server mode was suggested by Steve Kent over lunch some time ago, 447 but considerably modified since that meal. The server keeps no state for 448 each client, but uses a fast algorithm and a private random value called 449 the server seed to regenerate the cookie upon arrival of a client 450 packet. The cookie is calculated in a manner similar to the autokey, but 451 the key ID field is zero and the cookie field is the server seed. The 452 first 32 bits of the hash is the cookie used for the actual autokey 453 calculation by both the client and server. It is thus specific to each 454 client separately and of no use to other clients or an intruder. 456 In previous versions of the Autokey protocol the cookie was transmitted 457 in clear on the assumption it was not useful to a wiretapper other than 458 to launch an ineffective replay attack. However, an middleman could 459 intercept the cookie and manufacture bogus messages acceptable to the 460 client. In order to reduce the vulnerability to such an attack, the 461 Autokey Version 2 server encrypts the cookie using a public key supplied 462 by the client. While requiring additional processor resources for the 463 encryption, this makes it effectively impossible to spoof a cookie. 465 [Note in passing. In an attempt to avoid the use of overt encryption 466 operations, an experimental scheme used a Diffie-Hellman agreed key as a 467 stream cipher to encrypt the cookie. However, not only was the protocol 468 extremely awkward, but the processing time to execute the agreement, 469 encrypt the key and sign the result was horrifically expensive - 15 470 seconds(!) in a vintage Sun IPC. This scheme was quickly dropped in 471 favor of generic public key encryption.] 472 In client/server mode the client uses the cookie and each key ID on the 473 key list in turn to retrieve the autokey and generate the MAC in the NTP 474 packet. The server uses the same values to generate the message digest 475 and verifies it matches the MAC in the packet. It then generates the MAC 476 for the response using the same values, but with the IP source and 477 destination addresses exchanged. The client generates the message digest 478 and verifies it matches the MAC in the packet. In order to deflect old 479 replays, the client verifies the key ID matches the last one sent. In 480 this mode the sequential structure of the key list is not exploited, but 481 doing it this way simplifies and regularizes the implementation while 482 making it nearly impossible for an intruder to guess the next key ID. 484 In broadcast mode clients normally do not send packets to the server, 485 except when first starting up to calibrate the propagation delay in 486 client/server mode. At the same time the client runs the Autokey 487 protocol as in that mode. After obtaining and verifying the cookie, the 488 client continues to obtain and verify the autokey values. To obtain 489 these values, the client must provide the ID of the particular server 490 association, since there can be more than one operating in the same 491 server. For this purpose, the NTP broadcast packet includes the 492 association ID in every packet sent, except when sending the first 493 packet after generating a new key list, when it sends the autokey values 494 instead. 496 In symmetric mode each peer keeps state variables related to the other. 497 A shared private cookie is conveyed using the same scheme as in 498 client/server mode, except that the cookie is a random value. The key 499 list for each direction is generated separately by each peer and used 500 independently, but each is generated with the same cookie. There exists 501 a possible race condition where each peer sends a cookie request message 502 before receiving the cookie response from the other peer. In this case, 503 each peer winds up with two values, one it generated and one the other 504 peer generated. The ambiguity is resolved simply by computing the 505 working cookie as the exclusive-OR of the two values. 507 Once the client receives and validates the certificate, subsequent 508 packets containing valid signed extension fields are presumed to contain 509 valid time values, unless these values fall outside the valid interval 510 specified on the certificate. However, unless the system clock has 511 already been set by some other proventic means, it is not known whether 512 these values actually represent a truechime or falsetick source. As the 513 protocol evolves, the NTP associations continue to accumulated time 514 values until a majority clique is available to synchronize the system 515 clock. At this point the NTP intersection algorithm culls the 516 falsetickers from the population and the remaining truechimers are 517 allowed to discipline the clock. 519 The time values for even falsetick sources form a proventic total 520 ordering relative to the applicable signature timestamps. This raises 521 the interesting issue of how to mitigate between the timestamps of 522 different associations. It might happen, for instance, that the 523 timestamp of some Autokey message is ahead of the system clock by some 524 presumably small amount. For this reason, timestamp comparisons between 525 different associations and between associations and the system clock are 526 avoided, except in the NTP intersection and clustering algorithms. 528 Once the Autokey values have been instantiated, the protocol is normally 529 dormant. In all modes except broadcast, packets are normally sent 530 without extension fields, unless the packet is the first one sent after 531 generating a new key list or unless the client has requested the cookie 532 or autokey values. If for some reason the client clock is stepped, 533 rather than slewed, all cryptographic and time values for all 534 associations are purged and the Autokey protocol restarted from scratch 535 in all associations. This insures that stale values never propagate 536 beyond a clock step. 538 Public Key Signatures and Timestamps 540 While public key signatures provide strong protection against 541 misrepresentation of source, computing them is expensive. This invites 542 the opportunity for an intruder to clog the client or server by 543 replaying old messages or to originate bogus messages. A client 544 receiving such messages might be forced to verify what turns out to be 545 an invalid signature and consume significant processor resources. 547 In order to foil such attacks, every signed extension field carries a 548 timestamp in the form of the NTP seconds at the signature epoch. The 549 signature span includes the timestamp itself together with optional 550 additional data. If the Autokey protocol has verified a proventic source 551 and the NTP algorithms have validated the time values, the system clock 552 can be synchronized and signatures will then carry a nonzero (valid) 553 timestamp. Otherwise the system clock is unsynchronized and signatures 554 carry a zero (invalid) timestamp. Extension fields with invalid 555 timestamps are discarded before any values are used or signatures 556 verified. 558 There are three signature types currently defined: 560 1. Cookie signature/timestamp: Each association has a cookie for use 561 when generating a key list. The cookie value is determined along with 562 the cookie signature and timestamp upon arrival of a cookie request 563 message. The values are returned in a a cookie response message. 565 2. Autokey signature/timestamp: Each association has a key list for 566 generating the autokey sequence. The autokey values are determined along 567 with the autokey signature and timestamp when a new key list is 568 generated, which occurs about once per hour in the reference 569 implementation. The values are returned in a autokey response message. 571 3. Public values signature/timestamp: The public key, certificate and 572 leapsecond table values are signed at the time of generation, which 573 occurs when the system clock is first synchronized to a proventic 574 source, when the values have changed and about once per day after that, 575 even if these values have not changed. During protocol operations, each 576 of these values and associated signatures and timestamps are returned in 577 the associated request or response message. While there are in fact 578 three public value signatures, the values are all signed at the same 579 time, so there is only one public value timestamp. 581 The most recent timestamp of each type is saved for comparison. Once a 582 valid signature with valid timestamp has been received, messages with 583 invalid timestamps or earlier valid timestamps of the same type are 584 discarded before the signature is verified. For signed messages this 585 deflects replays that otherwise might consume significant processor 586 resources; for other messages the Autokey protocol deflects message 587 modification or replay by a wiretapper, but not necessarily by a 588 middleman. In addition, the NTP protocol itself is inherently resistant 589 to replays and consumes only minimal processor resources. 591 All cryptographic values used by the protocol are time sensitive and are 592 regularly refreshed. In particular, files containing cryptographic basis 593 values used by signature and encryption algorithms are regenerated from 594 time to time. It is the intent that file regenerations occur without 595 specific advance warning and without requiring prior distribution of the 596 file contents. While cryptographic data files are not specifically 597 signed, every file name includes an extension called the filestamp, 598 which is a string of decimal digits representing the NTP seconds at the 599 generation epoch. 601 Filestamps and timestamps can be compared in any combination and use the 602 same conventions. It is necessary to compare them from time to time to 603 determine which are earlier or later. Since these quantities have a 604 granularity only to the second, such comparisons are ambiguous if the 605 values are the same. Thus, the ambiguity must be resolved for each 606 comparison operation as described below. 608 It is important that filestamps be proventic data; thus, they cannot be 609 produced unless the producer has been synchronized to a proventic 610 source. As such, the filestamps represent a total ordering of creation 611 epoches and serve as means to expunge old data and insure new data are 612 consistent. As the data are forwarded from server to client, the 613 filestamps are preserved, including those for certificate and 614 leapseconds files. Packets with older filestamps are discarded before 615 spending cycles to verify the signature. 617 Autokey Dances 619 This section presents an overview of the three Autokey protocols, called 620 dances, corresponding to the NTP client/server, broadcast and symmetric 621 active/passive modes. Each dance is designed to be nonintrusive and to 622 require no additional packets other than for regular NTP operations. The 623 NTP protocol and Autokey dance operate independently and simultaneously 624 and use the same packets. When the Autokey dance is over, subsequent 625 packets are authenticated by the autokey sequence and thus considered 626 proventic as well. Autokey assumes clients poll servers at a relatively 627 low rate, such as once per minute. In particular, it is assumed that a 628 request sent at one poll opportunity will normally result in a response 629 before the next poll opportunity. 631 The Autokey protocol data unit is the extension field, one or more of 632 which can be piggybacked in the NTP packet. An extension field contains 633 either a request with optional data or a response with data. To avoid 634 deadlocks, any number of responses can be included in a packet, but only 635 one request. A response is generated for every request, even if the 636 requestor is not synchronized or proventicated. Some requests and most 637 responses carry timestamped signatures. The signature covers the data, 638 timestamp and filestamp, where applicable. Only if the packet passes all 639 extension field tests is the signature verified. 641 Dance Steps 643 The protocol state machine is very simple. The state is determined by 644 nine bits, four provided by the server, five determined by the client 645 association operations. The nine bits are stored along with the 646 digest/signature scheme identifier in the host status word of the server 647 and in the association status word of the client. In all dances the 648 client first sends an Association request message and receives the 649 Association response specifying which cryptographic values the server is 650 prepared to offer and the digest/signature scheme it will use. 652 If compatible, the client installs the server status word as the 653 association status word and sends a Certificate request message to the 654 server. The server returns a Certificate response including the 655 certificate and signature. The reference implementation requires the 656 certificate to be self-signed, which serves as an additional consistency 657 check. This check may be removed in future and replaced with a 658 certificate trail mechanism. If the certificate contents and signature 659 are valid, NTP timestamps in this and subsequent messages with valid 660 signatures are considered proventic. 662 In client/server mode the client sends a Cookie request message 663 including the public key of the host key. The server constructs the 664 cookie as described above and encrypts it using this key. It sends a 665 Cookie response including the encrypted cookie to the client and 666 expunges all values resulting from the calculations in order to remain 667 stateless. The client verifies the signature and decrypts the cookie. A 668 similar dance is used in symmetric modes, but the cookie is generated as 669 a random value. 671 The cookie is used to construct the key list and autokey values in all 672 modes. In client/server mode there is no need to provide these values to 673 the server, so once the cookie has been obtained the client can generate 674 the key list and validate succeeding packets directly. In other modes 675 the client retrieves the autokey values from the server using an Autokey 676 message exchange. Once these values have been received, the client 677 validates succeeding packets using the autokey sequence as described 678 previously. 680 A final exchange occurs when the server has the leapseconds table, as 681 indicated in the host status word. If so, the client obtains the table 682 and compares the filestamp with its own leapseconds table filestamp, if 683 available. If the server table is newer than the client table, the 684 client replaces its table with the server table. The client, acting as 685 server, can now provide the most recent table to any of its own 686 dependent clients. In symmetric modes, this results in both peers having 687 the newest table. 689 Status Words 691 Each sever and client operating as a server implements a host status 692 word and an association status word with the format and content shown 693 below. The low order four host status bits are lit during host 694 initialization, depending on whether cryptographic data files are 695 present or not; the next four association bits are dark. There are two 696 additional bits implemented separately. The high order 16 bits specify 697 the message digest/signature encryption scheme. 699 The host status word is provided to clients in the Association response 700 message. The client initializes the association status word and then 701 lights and dims the association bits as the dance proceeds. 703 1 2 3 704 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 705 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 706 | | |L|K|C|A|L|S|E|E| 707 | Digest/Signature NID | Reserved |P|E|K|U|P|I|N|N| 708 | | |T|Y|Y|T|F|G|C|B| 709 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 711 The host status bits are defined as follows: 713 ENB - Lit if the server implements the Autokey protocol and is prepared 714 to dance. 716 ENC - Lit if the server has loaded a valid encryption key file. This bit 717 is normally lit, but can dim if an error occurs. 719 SIG - Lit if the server has loaded a valid signature key file. This bit 720 is included primarily for error supervision and can be either lit or 721 dim. 723 LPF - Lit if the server has loaded a valid leapseconds file. This bit 724 can be either lit or dim. 726 The client association status bits are defined as follows: 728 AUT - Lit when the certificate is present and validated. When lit, 729 signed values in subsequent messages are presumed proventic. 731 CKY - Lit when the cookie is first received and validated. 733 KEY - Lit when the autokey values are first received and validated. When 734 lit, clients can validate packets without extension fields according to 735 the autokey sequence. 737 LPT - Lit when the leapseconds table is received and validated. 739 An additional bit LST not part of the association status word lights 740 when the key list is regenerated and signed and dims when the autokey 741 values are transmitted. This is necessary to avoid livelock under some 742 conditions. 744 An additional bit LBK not part of the association status word lights 745 when the association transmit timestamp matches the packet originate 746 timestamp and dims otherwise. If lit, this confirms the packet was 747 received in response to one previously sent by this association. 749 Host State Variables 751 Host Name 752 The name of the host returned by the Unix gethostname() library 753 function. It must agree with the subject and issuer name in the 754 certificate. 756 Host Key 757 The RSA key from the host key file and used to encrypt/decrypt cookies. 758 It carries the public value timestamp and the filestamp at the host key 759 file creation epoch. This is also the signature key, unless a signature 760 key is specified. 762 Public Key 763 The public encryption key for the Cookie request message and derived 764 from the host key. It carries the public value timestamp and the 765 filestamp at the host key file creation epoch. 767 Sign Key 768 The RSA or DSA key from the sign key file and used to encrypt 769 signatures. It carries the public value timestamp and the filestamp at 770 the sign key file creation epoch. 772 Certificate 773 The X.509 certificate from the certificate file. It carries the public 774 value timestamp and the filestamp at the certificate file creation 775 epoch. 777 Leapseconds Table, Leapseconds Table Filestamp 778 The NIST leapseconds table from the NIST leapseconds file. It carries 779 the public value timestamp and the filestamp at the leapseconds file 780 creation epoch. 782 Digest/signature NID 783 The identifier of the message digest/signature encryption scheme derived 784 from the sign key. It must agree with the NID on the certificate. 786 Client Association State Variables 788 Peer Association ID 789 The association ID of the peer as received in a response message. 791 Host Name 792 The name of the host returned by the Association response. It must agree 793 with the subject name in the certificate. 795 Digest/Signature NID 796 The identifier of the message digest/signature encryption scheme 797 returned in the Association response message. It must agree with the 798 value encoded in the certificate. 800 Public Values Timestamp 801 The timestamp returned by the latest Certificate response, Cookie 802 request or Leapseconds message. 804 Certificate 805 The X.509 certificate returned in the certificate response message, 806 together with its timestamp and filestamp. 808 Cookie 809 The cookie returned in a Cookie response message, together with its 810 timestamp and filestamp. 812 Receive Autokey values 813 The autokey values returned in an Autokey response message, together 814 with its timestamp and filestamp. 816 Server Association State Variables (broadcast and symmetric modes) 818 Association ID 819 The association ID of the server for use in client request messages. 821 Send Autokey Values 822 The autokey values, signature and timestamp. 824 Key List 825 A sequence of key IDs starting with a random autokey seed and each 826 pointing to the next. It is computed timestamped and signed at the next 827 poll opportunity when the key list is empty. 829 Autokey Seed 830 The private value used to initialize the key list. It is randomized for 831 each new key list. 833 Current Key Number 834 The index of the entry on the Key List to be used at the next poll 835 opportunity. 837 Send Encrypt Values (symmetric modes only) 838 The encrypted cookie, signature and timestamp computed upon arrival of 839 the Cookie request message. These data are held until the next poll 840 opportunity. 842 Server seed 843 The private value hashed with the IP addresses to construct the cookie 844 used in client/server mode. It is randomized when the public value 845 signatures are refreshed. 847 Autokey Messages 849 There are currently five Autokey request types and five corresponding 850 responses. An abbreviated description of these messages is given below; 851 the detailed formats are described in Appendix A. 853 Association Message (1) 854 The client sends the request to retrieve the host status word and host 855 name. The server responds with these values. 857 Certificate Message (2) 858 The client sends the request to retrieve the server certificate. The 859 server responds with the certificate. 861 Cookie Message (3) 862 The client sends the request, including the public member of the host 863 key, to retrieve the cookie. The server responds with the cookie 864 encrypted with the public key. 866 Autokey Message (4) 867 The client sends the request to retrieve the autokey values, if 868 available. The server responds with these values. 870 Leapseconds Message (5) 871 The client sends the request including its leapseconds table, if 872 available. The server responds with its own leapseconds table. Both the 873 client and server agree to use the version with the latest filestamp. 875 State Transitions 877 The state transitions of the three dances are shown below. The 878 capitalized truth values represent the association status word bits, 879 except for the SYNC value, which is true when the host is synchronized 880 to a proventic source and false otherwise. All truth values are 881 initialized false and become true upon the arrival of a specific 882 response messages, as detailed in the above status bits description. 884 Client/Server Dance 886 The client/server dance begins when the client sends an Association 887 request message to the server. It ends upon arrival of the Cookie 888 response, which lights the CKY and KEY bits. Subsequent packets received 889 without extension fields are validated by the autokey sequence. An 890 optional final exchange is possible to retrieve the leapseconds table. 892 while (1) { 893 wait_for_next_packet; 894 make_NTP_header; 895 if (response_ready) 896 send_response; 897 if (!ENB) 898 send_Association_request; 899 else if (!CRF) 900 send_Certificate_request; 901 else if (!CKY) 902 send_Cookie_request; 903 else if (LPF & !LPT) 904 send_Leapseconds_request; 905 } 907 Broadcast Client Dance 909 The broadcast client dance begins when the client receives the first 910 broadcast packet, which includes an Association response with the 911 association ID. The broadcast client uses the association ID to initiate 912 a client/server dance in order to calibrate the propagation delay. The 913 dance ends upon arrival of the Autokey response, which lights the KEY 914 bit. Subsequent packets received without extension fields are validated 915 by the autokey sequence. An optional final exchange is possible to 916 retrieve the leapseconds table. When the server generates a new key 917 list, the server replaces the Association response with an Autokey 918 response in the first packet sent. 920 while (1) { 921 wait_for_next_packet; 922 make_NTP_header; 923 if (response_ready) 924 send_response; 925 if (!ENB) 926 send_Association_request; 927 else if (!CRF) 928 send_Certificate_request; 929 else if (!CKY) 930 send_Cookie_request; 931 else if (!KEY) 932 send_Autokey_request; 933 else if (LPF & !LPT) 934 send_Leapseconds_request; 935 } 937 Symmetric Dance 939 The symmetric active dance begins when the active peer sends an 940 Association request to the passive peer. The passive peer mobilizes an 941 association and steps the same dance from the beginning. Until the 942 active peer is synchronized to a proventic source (which could be the 943 passive peer) and can sign messages, the passive peer will loop waiting 944 to light the CRF bit and the active peer will skip the cookie exchange. 946 Meanwhile, the active peer retrieves the certificate and autokey values 947 from the passive peer and lights the KEY bit. When for some reason 948 either peer generates a new key list, at the first opportunity the peer 949 sends the autokey values; that is, it pushes the values rather than 950 pulls them. This is to prevent a possible deadlock where each peer is 951 waiting for values from the other one. 953 while (1) { 954 wait_for_next_packet; 955 make_NTP_header; 956 if (response_ready) 957 send_response; 958 if (!ENB) 959 send_Association_request; 960 else if (!CRF) 961 send_Certificate_request; 962 else if (!CKY & SYNC) 963 send_Cookie_request; 964 else if (LST) 965 send_Autokey_response; 966 else if (!KEY) 967 send_Autokey_request; 968 else if (LPF & !LPT & SYNC) 969 send_Leapseconds_request; 970 } 972 Once the active peer has synchronized to a proventic source, it includes 973 timestamped signatures with its messages. The passive peer, which has 974 been stalled waiting for the CRF bit to light and the active peer, which 975 now finds the SYNC bit lit, continues their respective dances. The next 976 message sent by either peer is a Cookie request. The recipient rolls a 977 random cookie, lights its CKY bit and returns the encrypted cookie in 978 the Cookie response. The recipient decrypts the cookie and lights its 979 CKY bit. 981 It is not a protocol error if both peers happen to send a cookie request 982 at the same time. In this case both peers will have two values, one 983 generated by one peer and the other received from the other peer. In 984 such cases the working cookie is constructed as the exclusive-OR of the 985 two values. 987 At the next packet transmission opportunity, either peer generates a new 988 key list and lights the LST bit; however, there may already be an 989 Autokey request queued for transmission and the rules say no more than 990 one request in a packet. When available, either peer sends an Autokey 991 response and clears the LST bit. The recipient initializes the autokey 992 values, clears the LST bit and lights the KEY bit. Subsequent packets 993 received without extension fields are validated by the autokey sequence. 995 The above description assumes the active peer synchronizes to the 996 passive peer, which itself is synchronized to some other source, such as 997 a radio clock or another NTP server. In this case, the active peer is 998 operating at a stratum level one greater than the passive peer and so 999 the passive peer will not synchronize to it unless it loses its own 1000 sources and the active peer itself has another source. 1002 Key Refreshment 1004 About once per day the server seed is randomized and the signatures 1005 recomputed. The operations are: 1007 while (1) { 1008 wait_for_next_refresh; 1009 crank_random_generator; 1010 generate_autokey_private_value; 1011 if (!SYNC) 1012 continue; 1013 update_public_value_timestamp; 1014 compute_signatures; 1015 } 1017 Error Recovery 1019 The protocol state machine which drives the various Autokey operations 1020 includes provisions for various kinds of error conditions that can arise 1021 due to missing files, corrupted data, protocol violations and packet 1022 loss or misorder, not to mention hostile intrusion. There are two 1023 mechanisms which maintain the liveness state of the protocol, the 1024 reachability register defined in RFC-1305 and the watchdog timer, which 1025 is new in NTP Version 4. 1027 The reachability register is an 8-bit register that shifts left with 0 1028 replacing the rightmost bit. A shift occurs for every poll interval, 1029 whether or not a poll is actually sent. If an arriving packet passes all 1030 authentication and sanity checks, the rightmost bit is set to 1. If any 1031 bit in this register is a 1, the server is reachable, otherwise it is 1032 unreachable. If the server was once reachable and then becomes 1033 unreachable, a general reset is performed. A general reset reinitializes 1034 all association variables to the state when first mobilized and returns 1035 all acquired resources to the system. In addition, if the association is 1036 not configured, it is demobilized until the next packet is received. 1038 The watchdog timer increments for every poll interval, whether or not a 1039 poll is actually sent and regardless of the reachability state. The 1040 counter is set to zero upon arrival of a packet from a proventicated 1041 source, as determined by the Autokey protocol. In the reference 1042 implementation, if the counter reaches 16 a general reset is performed. 1043 In addition, if the association is configured, the poll interval is 1044 doubled. This reduces the network load for packets that are unlikely to 1045 elicit a response. 1047 At each state in the protocol the client expects a particular response 1048 from the server. A request is included in the NTP message sent at each 1049 poll interval until a valid response is received or a general reset 1050 occurs, in which case the protocol restarts from the beginning. In some 1051 cases noted below, certain kinds of errors cause appropriate action 1052 which avoids the somewhat lengthy timeout/restart cycle. While this 1053 behavior might be considered rather conservative, the advantage is that 1054 old cryptographic and time values can never persist from one 1055 mobilization to the next. 1057 There are a number of situations where some event happens that causes 1058 the remaining autokeys on the key list to become invalid. When one of 1059 these situations happens, the key list and associated autokeys in the 1060 key cache are purged. A new key list, signature and timestamp are 1061 generated when the next NTP message is sent, assuming there is one. 1062 Following is a list of these situations. 1064 1. When the cookie value changes for any reason. 1066 2. When a client switches from client/server mode to broadcast mode. 1067 There is no further need for the key list, since the client will not 1068 transmit again. 1070 3. When the poll interval is changed. In this case the calculated 1071 expiration times for the keys become invalid. 1073 4. When a general reset is performed. 1075 5. If a problem is detected when an entry is fetched from the key list. 1076 This could happen if the key was marked non-trusted or timed out, either 1077 of which implies a software bug. 1079 6. When the signatures are refreshed, the key lists for all associations 1080 are purged. 1082 7. When the client is first synchronized or the system clock is stepped, 1083 the key lists for all associations are purged. 1085 There are special cases designed to quickly respond to broken 1086 associations, such as when a server restarts or refreshes keys. Since 1087 the client cookie is invalidated, the server rejects the next client 1088 request and returns a crypto-NAK packet. Since the crypto-NAK has no 1089 MAC, the problem for the client is to determine whether it is legitimate 1090 or the result of intruder mischief. In order to reduce the vulnerability 1091 to such mischief, the crypto-NAK is believed only if the result of a 1092 previous packet sent by the client, as confirmed by the LBK status bit. 1093 This bit is lit in the NTP protocol if the packet originate timestamp 1094 matches the association transmit timestamp. While this defense can be 1095 easily circumvented by a middleman, it does deflect other kinds of 1096 intruder warfare. The LBK bit is also used to validate most responses 1097 and some requests as well. 1099 Security Analysis 1101 This section discusses the most obvious security vulnerabilities in the 1102 various Autokey dances. Throughout the discussion the cryptographic 1103 algorithms themselves are assumed secure; that is, a brute force 1104 cryptanalytic attack will not reveal the host private key or sign 1105 private key or cookie value or server seed or autokey seed or be able to 1106 predict the random generator values. 1108 There are three tiers of defense against intruder attacks. The first is 1109 a keyed message digest including a secret cookie conveyed in encrypted 1110 form. A packet is discarded if the message digest does not match the 1111 MAC. The second tier is the autokey sequence, which is generated by 1112 repeated hashes starting from a secret server seed and used in reverse 1113 order. While any receiver can authenticate a packet relative to the last 1114 one received and by induction to a signed extension field, as a 1115 practical matter a wiretapper cannot predict the next autokey and thus 1116 cannot spoof a valid packet. The third tier is timestamped signatures 1117 which reliably bind the autokey values to the private key of a trusted 1118 server. 1120 In addition to the three-tier defense strategy, all packets are 1121 protected by the NTP sanity checks. Since NTP packets carry time values, 1122 replays of old or bogus packets can be deflected once the client has 1123 synchronized to proventic sources. Additional sanity checks involving 1124 timestamps and filestamps are summarized in Appendix C. 1126 During the Autokey dances when extension fields are in use, the cookie 1127 is a public value (0) rather than a shared private value. Therefore, an 1128 intruder can easily construct a packet with a valid MAC; however, once 1129 the certificate is stored, extension fields carry timestamped signatures 1130 and bogus packets are readily avoided. While most request messages are 1131 unsigned, only the Association response message is unsigned. This 1132 message is used in the first packet sent by a server or peer and in most 1133 NTP broadcast packets. 1135 A bogus Association response message can cause a client livelock or 1136 deadlock condition. However, these packets do not affect NTP time values 1137 and do not consume significant resources. To reduce the vulnerability to 1138 bogus packets, the NTP transmit timestamp in the Association and 1139 Certificate request messages is used as a nonce. The NTP server copies 1140 this value to the originate timestamp in the NTP header, so that the 1141 client can verify that the message is a response to the original 1142 request. To minimize the possibility that an intruder can guess the 1143 nonce, the client should fill in the low order unused bits in the 1144 transmit timestamp with random values. In addition, replays of all 1145 except Autokey response messages are discarded before the signatures are 1146 verified. 1148 In client/server and symmetric modes extension fields are no longer 1149 needed after the Autokey dance has concluded. The client validates the 1150 packet using the message digest and autokey sequence. A successful 1151 middleman attack is unlikely, since without the server seed the intruder 1152 cannot produce the cookie and without the cookie cannot produce a valid 1153 MAC. In broadcast mode a wiretapper cannot synthesize a valid packet 1154 without the autokey seed, so cannot manufacture an bogus packet 1155 acceptable to the receiver. The most the intruder can do is replay an 1156 old packet causing the client to repeat hash operations until exceeding 1157 the maximum key number. On the other hand, a middleman could do real 1158 harm by intercepting a packet, using the key ID to generate a correct 1159 autokey and then synthesizing a bogus packet. There does not seem to be 1160 a suitable solution for this as long as the server has no per-client 1161 state. 1163 A client instantiates cryptographic variables only if the server is 1164 synchronized to a proventic source. A host does not sign values or 1165 generate cryptographic data files unless synchronized to a proventic 1166 source. This raises an interesting issue; how does a client generate 1167 proventic cryptographic files before it has ever been synchronized to a 1168 proventic source? Who shaves the barber if the barber shaves everybody 1169 in town who does not shave himself? In principle, this paradox is 1170 resolved by assuming the primary (stratum 1) servers are proventicated 1171 by external phenomological means. 1173 Cryptanalysis 1175 Some observations on the particular engineering constraints of the 1176 Autokey protocol are in order. First, the number of bits in some 1177 cryptographic values are considerably smaller than would ordinarily be 1178 expected for strong cryptography. One of the reasons for this is the 1179 need for compatibility with previous NTP versions; another is the need 1180 for small and constant latencies and minimal processing requirements. 1181 Therefore, what the scheme gives up on the strength of these values must 1182 be regained by agility in the rate of change of the cryptographic basis 1183 values. Thus, autokeys are used only once and basis values are 1184 regenerated frequently. However, in most cases even a successful 1185 cryptanalysis of these values compromises only a particular 1186 client/server association and does not represent a danger to the general 1187 population. 1189 While the protocol has not been subjected to a formal analysis, a few 1190 preliminary assertions can be made. The protocol cannot loop forever in 1191 any state, since the association timeout and general reset insure that 1192 the association variables will eventually be purged and the protocol 1193 restarted from the beginning. However, if something is seriously wrong, 1194 the timeout/restart cycle could continue indefinitely until whatever is 1195 wrong is fixed. 1197 Clogging Attacks 1199 There are two clogging vulnerabilities exposed in the protocol design: a 1200 sign attack where the intruder hopes to clog the victim server with 1201 needless signature computations, and a verify attack where the intruder 1202 attempts to clog the victim client with needless verification 1203 computations. Autokey uses public key encryption algorithms for both 1204 signature and cookie encryption and these algorithms require significant 1205 processor resources. 1207 In order to reduce the exposure to a sign attack, signatures are 1208 computed only when the data have changed. For instance, the autokey 1209 values are signed only when the key list is regenerated, which happens 1210 about once an hour, while the public values are signed only when the 1211 values are refreshed, which happens about once per day. However, in 1212 client/server mode the protocol precludes server state variables on 1213 behalf of an individual client, so the cookie must be computed, 1214 encrypted and signed for every cookie response. Ordinarily, cookie 1215 requests are seldom used, except when the server seed or public value 1216 signatures are refreshed. However, a determined intruder could replay 1217 cookie requests at high rate, which may very well clog the server. There 1218 appears no easy countermeasure for this particular attack. 1220 A verify attack attempts to clog the receiver by provoking spurious 1221 signature verifications. The signature timestamp is designed to deflect 1222 replays of packets with old or duplicate extension fields before 1223 invoking expensive signature operations. A bogus signature with a 1224 timestamp in the future could do this, but the autokey sequence would 1225 detect this, since success would require cryptanalysis of both the 1226 server seed and autokey seed. 1228 Since the Certificate response is signed, a middleman attack will not 1229 compromise the certificate data; however, a determined middleman could 1230 hammer the client with intentionally defective Certificate responses 1231 before a valid one could be received and force spurious signature 1232 verifications, which of course would fail. An intruder could flood the 1233 server with Certificate request messages, but the Certificate response 1234 message is signed only once, so the result would be no worse than 1235 flooding the network with spurious packets. 1237 An interesting vulnerability in client/server mode is for an intruder to 1238 replay a recent client packet with an intentional bit error. This could 1239 cause the server to return a crypto-NAK packet, which would then cause 1240 the client to request the cookie and result in a sign attack on the 1241 server. This results in the server and client burning spurious machine 1242 cycles and resulting in denial of service. As in other cases mentioned 1243 previously, the NTP timestamp check greatly reduces the likelihood of a 1244 successful attack. 1246 In broadcast and symmetric modes the client must include the association 1247 ID in the Autokey request. Since association ID values for different 1248 invocations of the NTP daemon are randomized over the 16-bit space, it 1249 is unlikely that a very old packet would contain a valid association ID 1250 value. An intruder could save old server packets and replay them to the 1251 client population with the hope that the values will be accepted and 1252 cause general chaos. The conservative client will discard them on the 1253 basis of invalid timestamp. 1255 As mentioned previously, an intruder could pounce on the initial volley 1256 between peers in symmetric mode before both peers have determined each 1257 other reachable. In this volley the peers are vulnerable to an intruder 1258 using fake timestamps. The result can be that the peers never 1259 synchronize the timestamps and never completely mobilize their 1260 associations. A clever intruder might notice the interval between public 1261 value signatures and concentrate attack on the vulnerable intervals. An 1262 obvious countermeasure is to randomize these intervals. A more 1263 comprehensive countermeasure remains to be devised. 1265 Appendix A. Packet Formats 1266 The NTP Version 4 packet consists of a number of fields made up of 32- 1267 bit (4 octet) words in network byte order. The packet consists of three 1268 components, the header, one or more optional extension fields and an 1269 optional message authenticator code (MAC), consisting of the Key ID and 1270 Message Digest fields. The format is shown below, where the size of some 1271 multiple word fields is shown in words. 1273 1 2 3 1274 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1275 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1276 |LI | VN |Mode | Stratum | Poll | Precision | 1277 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1278 | Root Delay | 1279 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1280 | Root Dispersion | 1281 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1282 | Reference ID | 1283 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1284 | | 1285 | Reference Timestamp (2) | 1286 | | 1287 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1288 | | 1289 | Originate Timestamp (2) | 1290 | | 1291 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1292 | | 1293 | Receive Timestamp (2) | 1294 | | 1295 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1296 | | 1297 | Transmit Timestamp (2) | 1298 | | 1299 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1300 | | 1301 | | 1302 = Extension Field(s) = 1303 | | 1304 | | 1305 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1306 | Key ID | 1307 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1308 | | 1309 | | 1310 | Message Digest (4) | 1311 | | 1312 | | 1313 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1315 The NTP header extends from the beginning of the packet to the end of 1316 the Transmit Timestamp field. The format and interpretation of the 1317 header fields are backwards compatible with the NTP Version 3 header 1318 fields as described in RFC-1305, except for a slightly modified 1319 computation for the Root Dispersion field. In NTP Version 3, this field 1320 includes an estimated jitter quantity based on weighted absolute 1321 differences, while in NTP Version 4 this quantity is based on weighted 1322 root-mean-square (RMS) differences. 1324 An unauthenticated NTP packet includes only the NTP header, while an 1325 authenticated one contains in addition a MAC. The format and 1326 interpretation of the NTP Version 4 MAC is described in RFC-1305 when 1327 using the Digital Encryption Standard (DES) algorithm operating in 1328 Cipher-Block Chaining (CBC) node. This algorithm and mode of operation 1329 is no longer supported in NTP Version 4. The preferred replacement in 1330 both NTP Version 3 and 4 is the Message Digest 5 (MD5) algorithm, which 1331 is included in the distribution. For MD5 the Message Digest field is 4 1332 words (8 octets), but the Key ID field remains 1 word (4 octets). 1334 Extension Field Format 1336 In NTP Version 4 one or more extension fields can be inserted after the 1337 NTP header and before the MAC, which is always present when an extension 1338 field is present. The extension fields can occur in any order; however, 1339 in some cases there is a preferred order which improves the protocol 1340 efficiency. While previous versions of the Autokey protocol used several 1341 different extension field formats, in version 2 of the protocol only a 1342 single extension field format is used. 1344 Each extension field contains a request or response message in the 1345 following format: 1347 1 2 3 1348 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1349 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1350 |R|E| Version | Code | Length | 1351 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1352 | Association ID | 1353 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1354 | Timestamp | 1355 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1356 | Filestamp | 1357 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1358 | Value Length | 1359 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1360 | | 1361 | | 1362 = Value = 1363 | | 1364 | | 1365 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1366 | Signature Length | 1367 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1368 | | 1369 | | 1370 = Signature = 1371 | | 1372 | | 1373 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1375 Each extension field except the last is padded to a word (4 octets) 1376 boundary, while the last is padded to a doubleword (8 octets) boundary. 1377 The Length field covers the entire field length, including the Length 1378 field itself and padding. While the minimum field length is 8 octets, a 1379 maximum field length remains to be established. The reference 1380 implementation discards any packet with an extension field length over 1381 1024 octets. 1383 The presence of the MAC and extension fields in the packet is determined 1384 from the length of the remaining area after the header to the end of the 1385 packet. The parser initializes a pointer just after the header. If the 1386 length is not a multiple of 4, a format error has occurred and the 1387 packet is discarded. If the length is zero the packet is not 1388 authenticated. If the length is 4 (1 word), the packet is an error 1389 report or crypto-NAK resulting from a previous packet that failed the 1390 message digest check. The 4 octets are presently unused and should be 1391 set to 0. If the length is 8 (2 words), 12 (3 words) or 16 (4 words), 1392 the packet is discarded with a format error. If the length is greater 1393 than 20 (5 words), one or more extension fields are present. 1395 If an extension field is present, the parser examines the length field. 1396 If the length is less than 4 or not a multiple of 4, a format error has 1397 occurred and the packet is discarded; otherwise, the parser increments 1398 the pointer by this value. The parser now uses the same rules as above 1399 to determine whether a MAC is present and/or another extension field. An 1400 additional implementation-dependent test is necessary to ensure the 1401 pointer does not stray outside the buffer space occupied by the packet. 1403 In the Autokey Version 2 format, the Code field specifies the request or 1404 response operation, while the Version field is 2 identifying the current 1405 protocol version. There are two flag bits defined. Bit 0 is the response 1406 flag (R) and bit 1 is the error flag (E); the other six bits are 1407 presently unused and should be set to 0. The remaining fields will be 1408 described later. 1410 In the most common protocol operations, a client sends a request to a 1411 server with an operation code specified in the Code field and the R bit 1412 set to 0. Ordinarily, the client sets the E bit to 0 as well, but may in 1413 future set it to 1 for some purpose. The Association ID field is set to 1414 the value previously received from the server or 0 otherwise. The server 1415 returns a response with the same operation code in the Code field and 1416 the R bit set to 1. The server can also set the E bit to 1 in case of 1417 error. The Association ID field is set to the association ID sending the 1418 response as a handle for subsequent exchanges. If for some reason the 1419 association ID value in a request does not match the association ID of 1420 any mobilized association, the server returns the request with both the 1421 R and E bits set to 1. Note that, it is not a protocol error to send an 1422 unsolicited response with no matching request. 1424 In some cases not all fields may be present. For instance, when a client 1425 has not synchronized to a proventic source, signatures are not valid. In 1426 such cases the Timestamp and Signature Length fields are 0 and the 1427 Signature field is empty. Some request and error response messages carry 1428 no value or signature fields, so in these messages only the first two 1429 words are present. The extension field parser verifies that the 1430 extension field length is at least 8 if no value field is expected and 1431 at least 24 if it is. The parser also verifies that the sum of the value 1432 and signature lengths is equal to or less than the extension field 1433 length. 1435 The Timestamp and Filestamp words carry the seconds field of the NTP 1436 timestamp. The Timestamp field establishes the signature epoch of the 1437 data field in the message, while the filestamp establishes the 1438 generation epoch of the file that ultimately produced the data that was 1439 signed. Since a signature and timestamp are valid only when the signing 1440 host is synchronized to a proventic source and a cryptographic data file 1441 can only be generated if a signature is possible, the filestamp is 1442 always nonzero, except in the Association Response message, where it 1443 contains the server status word. 1445 Autokey Version 2 Messages 1447 Association Message 1449 The Association message is used to obtain the host name and related 1450 values. The request message has the following format: 1452 1 2 3 1453 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1454 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1455 |0|0| 1 | 1 | 8 | 1456 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1457 | 0 | 1458 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1460 The response message has the following format: 1462 1 2 3 1463 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1464 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1465 |1|E| 1 | 1 | Length | 1466 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1467 | 0 | 1468 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1469 | Public Value Timestamp | 1470 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1471 | Status Word | 1472 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1473 | Host Name Length | 1474 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1475 | | 1476 | | 1477 = Host Name = 1478 | | 1479 | | 1480 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1481 | 0 | 1482 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1484 This is the only response that is accepted if the association status 1485 word is zero; otherwise, it is ignored. As this is the first request 1486 sent and the response is not from an association, the Association ID 1487 fields are 0. The Host Name field contains the unterminated string 1488 returned by the Unix gethostname() library function. The Status Word is 1489 defined in previously in this memorandum. While minimum and maximum host 1490 name lengths remain to be established, the reference implementation uses 1491 the values 4 and 256, respectively. 1493 Certificate Message 1495 The Certificate message is used to obtain the certificate and related 1496 values. The request message has the following format: 1498 1 2 3 1499 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1500 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1501 |0|0| 2 | 2 | 8 | 1502 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1503 | Association ID | 1504 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1506 The response message has the following format: 1508 1 2 3 1509 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1510 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1511 |1|E| 2 | 2 | Length | 1512 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1513 | Association ID | 1514 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1515 | Public Values Timestamp | 1516 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1517 | Certificate Filestamp | 1518 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1519 | Certificate Length | 1520 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1521 | | 1522 | | 1523 = Certificate = 1524 | | 1525 | | 1526 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1527 | Certificate Signature Length | 1528 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1529 | | 1530 | | 1531 = Certificate Signature = 1532 | | 1533 | | 1534 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1536 The response is accepted only if the association status word is nonzero, 1537 AUT = 0 and LBK = 1. The certificate is encoded in X.509 format using 1538 ASN.1 syntax. If the certificate has expired or for some reason is no 1539 longer available, the response includes only the first two words with 1540 the E bit set. The remaining fields are defined previously in this 1541 memorandum. 1543 Cookie Message 1545 The Cookie is used in client/server and symmetric modes to obtain the 1546 server cookie. The request message has the following format: 1548 1 2 3 1549 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1550 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1551 |0|0| 3 | 3 | Length | 1552 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1553 | Association ID | 1554 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1555 | Public Values Timestamp | 1556 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1557 | Certificate Filestamp | 1558 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1559 | Public Key Length | 1560 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1561 | | 1562 | | 1563 = Public Key = 1564 | | 1565 | | 1566 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1567 | Public Key Signature Length | 1568 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1569 | | 1570 | | 1571 = Public Key Signature = 1572 | | 1573 | | 1574 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1576 The request is accepted only if AUT = 1, CKY = 0 and LBK = 1. The Public 1577 Key field contains the server public key values to be used for cookie 1578 encryption. The values are encoded in ASN.1 format. The remaining fields 1579 are defined previously in this memorandum. 1581 The response message has the following format: 1583 1 2 3 1584 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1585 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1586 |1|E| 3 | 3 | Length | 1587 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1588 | Association ID | 1589 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1590 | Cookie Timestamp | 1591 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1592 | Certificate Filestamp | 1593 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1594 | Encrypted Cookie Length | 1595 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1596 | | 1597 | | 1598 = Encrypted Cookie = 1599 | | 1600 | | 1601 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1602 | Cookie Signature Length | 1603 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1604 | | 1605 | | 1606 = Cookie Signature = 1607 | | 1608 | | 1609 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1611 The response is accepted only if AUT = 1 and LBK = 1. The Cookie 1612 Timestamp, Encrypted Cookie and Cookie Signature fields are determined 1613 upon arrival of the request message. The Encrypted Cookie field contains 1614 the encrypted cookie value according to the public key provided in the 1615 request. If CKY = 0, the decrypted cookie is used directly. If CKY = 1, 1616 the decrypted cookie is exclusive-ORed with the existing cookie. If an 1617 error occurs when decoding the public key or encrypting the cookie, the 1618 response includes only the first two words with the E bit set. The 1619 remaining fields are defined previously in this memorandum. 1621 Autokey Message 1623 The Autokey message is used to obtain the autokey values. The request 1624 message has the following format: 1626 1 2 3 1627 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1628 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1629 |0|0| 2 | 4 | 8 | 1630 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1631 | Association ID | 1632 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1634 The response message has the following format: 1636 1 2 3 1637 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1638 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1639 |1|E| 4 | 4 | Length | 1640 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1641 | Association ID | 1642 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1643 | Autokey Timestamp | 1644 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1645 | Certificate Filestamp | 1646 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1647 | 8 | 1648 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1649 | Key ID | 1650 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1651 | Key Number | 1652 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1653 | Autokey Signature Length | 1654 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1655 | | 1656 | | 1657 = Autokey Signature = 1658 | | 1659 | | 1660 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1662 The response is accepted only if AUT = 1 and KEY = 0 in the association 1663 status word; otherwise, it is ignored. The Autokey Timestamp, Key ID, 1664 Key Number and Autokey Signature fields are determined when the most 1665 recent key list was generated. If a key list has not been generated or 1666 the association ID matches no mobilized association, the response 1667 includes only the first two words with the E bit set. The remaining 1668 fields are defined previously in this memorandum. 1670 Leapseconds Table Message 1672 The Leapseconds Table message is used to exchange leapseconds tables. 1673 The request and response messages have the following format, except that 1674 the R bit is set in the response: 1676 1 2 3 1677 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1678 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1679 |0|0| 2 | 5 | Length | 1680 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1681 | Association ID | 1682 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1683 | Public Values Timestamp | 1684 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1685 | Leapseconds Filestamp | 1686 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1687 | Leapseconds Table Length | 1688 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1689 | | 1690 | | 1691 = Leapseconds Table = 1692 | | 1693 | | 1694 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1695 | Leapseconds Signature Length | 1696 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1697 | | 1698 | | 1699 = Leapseconds Signature = 1700 | | 1701 | | 1702 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1704 The response is accepted only if AUT = 1 and LPT = 0 in the association 1705 status word; otherwise, it is ignored. The Leapseconds Table field 1706 contains the leapseconds table as parsed from the leapseconds file 1707 available from NIST. In client/server mode the client requests the table 1708 from the server when the LPF bit is set in the host status word. If the 1709 client already has a copy, it uses the one with the latest filestamp. In 1710 symmetric modes the peers exchange tables and both use the one with the 1711 latest filestamp. If the leapseconds table is requested but unavailable, 1712 the response includes only the first two words with the E bit set. The 1713 remaining fields are defined previously in this memorandum. 1715 Appendix B. Key Generation and Management 1717 The ntp-genkeys utility program in the NTP software distribution 1718 generates public/private key, certificate request and certificate files. 1719 A set of files is generated for every message digest and signature 1720 encryption scheme supported by the OpenSSL software library. All files 1721 are based on a pseudo-random number generator seeded in such a way that 1722 random values are exceedingly unlikely to repeat. The files are PEM 1723 encoded in printable ASCII format suitable for mailing as MIME objects. 1724 The file names include the name of the generating host together with the 1725 filestamp, as described previously in this memorandum. 1727 The generated files are typically stored in a shared directory in NFS 1728 mounted file systems, with files containing private keys obscured to all 1729 but root. Links from default file names assumed by the NTP daemon are 1730 installed to the selected files for the host key, sign key and host 1731 certificate. Since the files of successive generations and different 1732 hosts have unique names, there is no possibility of name collisions. An 1733 extensive set of consistency checks avoids linking from a particular 1734 host to the files of another host, for example. 1736 The ntp-genkeys program generates public/private key files for both the 1737 RSA and DSA encryption algorithms with a default modulus of 512 bits. 1738 The host key used for cookie encryption must be RSA. By default, the 1739 same key is used for signature encryption. However, a different RSA key 1740 or a DSA key can be specified for signature encryption. 1742 The ntp-genkeys program also generates certificate request and self- 1743 signed certificate files. The X.509 certificate request used by Autokey 1744 includes at the minimum these values and possibly related information 1745 needed by an external certificate authority. Autokey expects the subject 1746 name and issuer name to be the same as the generating host name. 1748 The program avoids the need for a serial number file by using the 1749 filestamp as the certificate serial number. By default, certificates are 1750 valid for one year following the time of generation, although these 1751 conventions may change. Also, the program assumes X.509 version 1 1752 formats, although this may change to version 3 in future. Other 1753 implementations might have different conventions. 1755 Appendix C. Packet Processing Rules 1757 Exhaustive examination of possible vulnerabilities at the various 1758 processing steps of the NTP protocol as specified in RFC-1305 have 1759 resulted in a revised list of packet sanity tests. There are 12 tests, 1760 called TEST1 through TEST12 in the reference implementation, which are 1761 performed in a specific order designed to gain maximum diagnostic 1762 information while protecting against an accidental or malicious clogging 1763 attack. These tests are described in detail in the Flash Codes section 1764 of the ntpq documentation page at 1765 www.eecis.udel.edu/~ntp/ntp_spool/html/ntpq.htm. 1767 The sanity tests are divided into three tiers as previously described. 1768 The first tier deflects access control and packet message digest 1769 violations. The second deflects packets from broken or unsynchronized 1770 servers and replays. The third deflects packets with invalid header 1771 fields or time values with excessive errors. However, the tests in this 1772 last group do not directly affect cryptographic the protocol 1773 vulnerability, so are beyond the scope of discussion here. 1775 When a host initializes, it reads its own host key, sign key and 1776 certificate files, which are required for continued operation. 1777 Optionally, it reads the leapseconds file, when available. When reading 1778 these files the host checks the filestamps for validity; for instance, 1779 all filestamps must be later than the time the UTC timescale was 1780 established in 1972 and the certificate filestamp must not be earlier 1781 than the sign key filestamp (or host key filestamp, if that is the 1782 default sign key). In general, at the time the files are read, the host 1783 is not synchronized, so it cannot determine whether the filestamps are 1784 bogus other than these simple checks. 1786 Once a client has synchronized to a proventic source, additional checks 1787 are implemented as each message arrives. In the following the relation A 1788 -> B is Lamport's "happens before" relation which is true if event A 1789 happens before event B. Here the relation is assume to hold if event A 1790 is simultaneous with event B, unless noted to the contrary. The 1791 following assertions are required: 1793 1. For timestamp T and filestamp F, F->T; that is, the timestamp must 1794 not be earlier than the filestamp. 1796 2. In client and symmetric modes, for host key filestamp H, public key 1797 timestamp P, cookie timestamp C and autokey timestamp A, H->P->C->A; 1798 that is, once the cookie is generated an earlier cookie will not be 1799 accepted, and once the key list and autokey values are generated, 1800 earlier autokey values will not be accepted. 1802 3. For sign file S and certificate filestamp C specifying begin time B 1803 and end time E, S->C->B->E; that is, the valid period must be nonempty 1804 and not retroactive. 1806 4. For timestamp T, begin time B and end time E, B->T->E; that is, the 1807 timestamp T is valid from the beginning if second B through the end of 1808 second E. This raises the interesting possibilities where a truechimer 1809 server with expired certificate or a falseticker with valid certificate 1810 are not detected until the client has synchronized to a clique of 1811 proventic truechimers. 1813 5. For each of signatures, the client saves the most recent valid 1814 timestamp T0 and filestamp F0. For every received message carrying 1815 timestamp T1 and filestamp F1, the message is discarded unless T0->T1 1816 and F0->F1; however, if the KEY bit of the association status word is 1817 dim, the message is not discarded if T1 = T0; that is, old messages are 1818 discarded and, in addition, if the server is proventic, the message is 1819 discarded if an old duplicate. 1821 An interesting question is what happens if during regular operation a 1822 certificate becomes invalid. The behavior assumed is identical to the 1823 case where an incorrect sign key were used. Thus, the next time a client 1824 attempts to verify an autokey signature, for example, the operation 1825 would fail and eventually cause a general client reset and restart. 1827 Security Considerations 1829 Security issues are the main topic of this memorandum. 1831 References 1833 Note: Internet Engineering Task Force documents can be obtained at 1834 www.ietf.org. Other papers and reports can be obtained at 1835 www.eecis.udel.edu/~mills. Additional briefings in PowerPoint, 1836 PostScript and PDF are at that site in ./autokey.htm. 1838 1. Bradner, S. Key words for use in RFCs to indicate requirement levels. 1839 Request for Comments RFC-2119, BCP 14, Internet Engineering Task Force, 1840 March 1997. 1842 2. Karn, P., and W. Simpson. Photuris: session-key management protocol. 1843 Request for Comments RFC-2522, Internet Engineering Task Force, March 1844 1999. 1846 3. Kent, S., R. Atkinson. IP Authentication Header. Request for Comments 1847 RFC-2402, Internet Engineering Task Force, November 1998. 1849 4. Kent, S., and R. Atkinson. IP Encapsulating security payload (ESP). 1850 Request for Comments RFC-2406, Internet Engineering Task Force, November 1851 1998. 1853 5. Maughan, D., M. Schertler, M. Schneider, and J. Turner. Internet 1854 security association and key management protocol (ISAKMP). Request for 1855 Comments RFC-2408, Internet Engineering Task Force, November 1998. 1857 6. Mills, D.L. Authentication scheme for distributed, ubiquitous, real- 1858 time protocols. Proc. Advanced Telecommunications/Information 1859 Distribution Research Program (ATIRP) Conference (College Park MD, 1860 January 1997), 293-298. 1862 7. Mills, D.L. Cryptographic authentication for real-time network 1863 protocols. In: AMS DIMACS Series in Discrete Mathematics and Theoretical 1864 Computer Science, Vol. 45 (1999), 135-144. 1866 8. Mills, D.L. Network Time Protocol (Version 3) specification, 1867 implementation and analysis. Network Working Group Report RFC-1305, 1868 University of Delaware, March 1992, 113 pp. 1870 9. Mills, D.L. Proposed authentication enhancements for the Network Time 1871 Protocol version 4. Electrical Engineering Report 96-10-3, University of 1872 Delaware, October 1996, 36 pp. 1874 10. Mills, D.L, and A. Thyagarajan. Network time protocol version 4 1875 proposed changes. Electrical Engineering Department Report 94-10-2, 1876 University of Delaware, October 1994, 32 pp. 1878 11. Mills, D.L. Public key cryptography for the Network Time Protocol. 1879 Electrical Engineering Report 00-5-1, University of Delaware, May 2000. 1880 23 pp. 1882 12. Orman, H. The OAKLEY key determination protocol. Request for 1883 Comments RFC-2412, Internet Engineering Task Force, November 1998. 1885 Author's Address 1887 David L. Mills 1888 Electrical and Computer Engineering Department 1889 University of Delaware 1890 Newark, DE 19716 1891 mail mills@udel.edu, phone 302 831 8247, fax 302 831 4316 1892 web www.eecis.udel.edu/~mills 1894 Full Copyright Statement 1896 "Copyright (C) The Internet Society, 2001. All Rights Reserved. This 1897 document and translations of it may be copied and furnished to others, 1898 and derivative works that comment on or otherwise explain it or assist 1899 in its implmentation may be prepared, copied, published and distributed, 1900 in whole or in part, without restriction of any kind, provided that the 1901 above copyright notice and this paragraph are included on all such 1902 copies and derivative works. However, this document itself may not be 1903 modified in any way, such as by removing the copyright notice or 1904 references to the Internet Society or other Internet organizations, 1905 except as needed for the purpose of developing Internet standards in 1906 which case the procedures for copyrights defined in the Internet 1907 Standards process must be followed, or as required to translate it into.