idnits 2.17.1 draft-ietf-ntp-autokey-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 17. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 3127. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 3138. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 3145. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 3151. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- == There are 1 instance of lines with non-RFC2606-compliant FQDNs in the document. == The 'Obsoletes: ' line in the draft header should list only the _numbers_ of the RFCs which will be obsoleted by this document (if approved); it should not include the word 'RFC' in the list. -- The draft header indicates that this document obsoletes RFC1305, but the abstract doesn't seem to mention this, which it should. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year -- 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 (September 25, 2007) is 6057 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-13) exists of draft-ietf-ntp-ntpv4-proto-07 -- Obsolete informational reference (is this intentional?): RFC 4306 (ref. '2') (Obsoleted by RFC 5996) -- Obsolete informational reference (is this intentional?): RFC 1305 (ref. '8') (Obsoleted by RFC 5905) -- Obsolete informational reference (is this intentional?): RFC 2875 (ref. '9') (Obsoleted by RFC 6955) -- Obsolete informational reference (is this intentional?): RFC 3280 (ref. '11') (Obsoleted by RFC 5280) Summary: 1 error (**), 0 flaws (~~), 4 warnings (==), 13 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group B. Haberman, Ed. 3 Internet-Draft JHU/APL 4 Obsoletes: RFC 1305 D. Mills 5 (if approved) U. Delaware 6 Intended status: Informational September 25, 2007 7 Expires: March 28, 2008 9 Network Time Protocol Version 4 Autokey Specification 10 draft-ietf-ntp-autokey-00 12 Status of this Memo 14 By submitting this Internet-Draft, each author represents that any 15 applicable patent or other IPR claims of which he or she is aware 16 have been or will be disclosed, and any of which he or she becomes 17 aware will be disclosed, in accordance with Section 6 of BCP 79. 19 Internet-Drafts are working documents of the Internet Engineering 20 Task Force (IETF), its areas, and its working groups. Note that 21 other groups may also distribute working documents as Internet- 22 Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six months 25 and may be updated, replaced, or obsoleted by other documents at any 26 time. It is inappropriate to use Internet-Drafts as reference 27 material or to cite them other than as "work in progress." 29 The list of current Internet-Drafts can be accessed at 30 http://www.ietf.org/ietf/1id-abstracts.txt. 32 The list of Internet-Draft Shadow Directories can be accessed at 33 http://www.ietf.org/shadow.html. 35 This Internet-Draft will expire on March 28, 2008. 37 Copyright Notice 39 Copyright (C) The IETF Trust (2007). 41 Abstract 43 This memo describes the Autokey security model for authenticating 44 servers to clients using the Network Time Protocol (NTP) and public 45 key cryptography. Its design is based on the premise that IPSEC 46 schemes cannot be adopted intact, since that would preclude stateless 47 servers and severely compromise timekeeping accuracy. In addition, 48 PKI schemes presume authenticated time values are always available to 49 enforce certificate lifetimes; however, cryptographically verified 50 timestamps require interaction between the timekeeping and 51 authentication functions. 53 This memo includes the Autokey requirements analysis, design 54 principles and protocol specification. A detailed description of the 55 protocol states, events and transition functions is included. A 56 prototype of the Autokey design based on this report has been 57 implemented, tested and documented in the NTP Version 4 (NTPv4) 58 software distribution for Unix, Windows and VMS at 59 http://www.ntp.org. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 64 1.1. Requirements Notation . . . . . . . . . . . . . . . . . . 4 65 2. NTP Security Model . . . . . . . . . . . . . . . . . . . . . . 4 66 3. Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 67 4. Autokey Cryptography . . . . . . . . . . . . . . . . . . . . . 9 68 5. Secure Groups . . . . . . . . . . . . . . . . . . . . . . . . 12 69 6. Identity Schemes . . . . . . . . . . . . . . . . . . . . . . . 18 70 7. Autokey Operations . . . . . . . . . . . . . . . . . . . . . . 20 71 8. Public Key Signatures and Timestamps . . . . . . . . . . . . . 22 72 9. Autokey Protocol Overview . . . . . . . . . . . . . . . . . . 24 73 10. Autokey State Machine . . . . . . . . . . . . . . . . . . . . 26 74 10.1. Status Word . . . . . . . . . . . . . . . . . . . . . . . 26 75 10.2. Host State Variables . . . . . . . . . . . . . . . . . . . 28 76 10.3. Client State Variables (all modes) . . . . . . . . . . . . 30 77 10.4. Server State Variables (broadcast and symmetric modes) . . 31 78 10.5. Autokey Protocol Messages . . . . . . . . . . . . . . . . 31 79 10.5.1. No-Operation . . . . . . . . . . . . . . . . . . . . 33 80 10.5.2. Association Message (ASSOC) . . . . . . . . . . . . . 33 81 10.5.3. Certificate Message (CERT) . . . . . . . . . . . . . 34 82 10.5.4. Cookie Message (COOKIE) . . . . . . . . . . . . . . . 34 83 10.5.5. Autokey Message (AUTO) . . . . . . . . . . . . . . . 34 84 10.5.6. Leapseconds Table Message (LEAP) . . . . . . . . . . 35 85 10.5.7. Sign Message (SIGN) . . . . . . . . . . . . . . . . . 35 86 10.5.8. Identity Messages (IFF, GQ, MV) . . . . . . . . . . . 35 87 10.6. Protocol State Transitions . . . . . . . . . . . . . . . . 35 88 10.6.1. Server Dance . . . . . . . . . . . . . . . . . . . . 36 89 10.6.2. Broadcast Dance . . . . . . . . . . . . . . . . . . . 37 90 10.6.3. Symmetric Dance . . . . . . . . . . . . . . . . . . . 38 91 11. Error Recovery . . . . . . . . . . . . . . . . . . . . . . . . 40 92 12. Security Considerations . . . . . . . . . . . . . . . . . . . 42 93 12.1. Protocol Vulnerability . . . . . . . . . . . . . . . . . . 42 94 12.2. Clogging Vulnerability . . . . . . . . . . . . . . . . . . 44 95 13. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 45 96 14. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 45 97 15. References . . . . . . . . . . . . . . . . . . . . . . . . . . 46 98 15.1. Normative References . . . . . . . . . . . . . . . . . . . 46 99 15.2. Informative References . . . . . . . . . . . . . . . . . . 46 100 Appendix A. Cryptographic Key and Certificate Management . . . . 47 101 Appendix B. Autokey Error Checking . . . . . . . . . . . . . . . 48 102 B.1. Packet Processing Rules . . . . . . . . . . . . . . . . . 49 103 B.2. Timestamps, Filestamps and Partial Ordering . . . . . . . 51 104 Appendix C. Certificates . . . . . . . . . . . . . . . . . . . . 52 105 Appendix D. Identity Schemes . . . . . . . . . . . . . . . . . . 53 106 D.1. Private Certificate (PC) Scheme . . . . . . . . . . . . . 53 107 D.2. Trusted Certificate (TC) Scheme . . . . . . . . . . . . . 54 108 D.3. Schnorr (IFF) Scheme . . . . . . . . . . . . . . . . . . . 56 109 D.4. Guillard-Quisquater (GQ) . . . . . . . . . . . . . . . . . 58 110 D.5. Mu-Varadharajan (MV) Identity Scheme . . . . . . . . . . . 60 111 D.6. Interoperability Issues . . . . . . . . . . . . . . . . . 64 112 Appendix E. ASN.1 Encoding Rules . . . . . . . . . . . . . . . . 66 113 E.1. COOKIE request, IFF response, GQ response, MV response . . 66 114 E.2. CERT response, SIGN request and response . . . . . . . . . 67 115 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 68 116 Intellectual Property and Copyright Statements . . . . . . . . . . 70 118 1. Introduction 120 A distributed network service requires reliable, ubiquitous and 121 survivable provisions to prevent accidental or malicious attacks on 122 the servers and clients in the network or the values they exchange. 123 Reliability requires that clients can determine that received packets 124 are authentic; that is, were actually sent by the intended server and 125 not manufactured or modified by an intruder. Ubiquity requires that 126 any client can verify the authenticity of any server using only 127 public information. Survivability requires protection from faulty 128 implementations, improper operation and possibly malicious clogging 129 and replay attacks with or without data modification. These 130 requirements are especially stringent with widely distributed network 131 services, since damage due to failures can propagate quickly 132 throughout the network, devastating archives, routing databases and 133 monitoring systems and even bring down major portions of the network. 135 This memo describes a cryptographically sound and efficient 136 methodology for use in the Network Time Protocol (NTP) [1]. The 137 various key agreement schemes [2][3][4] proposed require per- 138 association state variables, which contradicts the principles of the 139 remote procedure call (RPC) paradigm in which servers keep no state 140 for a possibly large client population. An evaluation of the PKI 141 model and algorithms as implemented in the OpenSSL library leads to 142 the conclusion that any scheme requiring every NTP packet to carry a 143 PKI digital signature would result in unacceptably poor timekeeping 144 performance. The Autokey protocol is based on a combination of PKI 145 and a pseudo-random sequence generated by repeated hashes of a 146 cryptographic value involving both public and private components. 147 This scheme has been implemented, tested and widely deployed in the 148 Internet of today. A detailed description of the security model, 149 design principles and implementation experience is presented in this 150 report. 152 1.1. Requirements Notation 154 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 155 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 156 document are to be interpreted as described in [5]. 158 2. NTP Security Model 160 NTP security requirements are even more stringent than most other 161 distributed services. First, the operation of the authentication 162 mechanism and the time synchronization mechanism are inextricably 163 intertwined. Reliable time synchronization requires cryptographic 164 media which are valid only over designated time intervals; but, time 165 intervals can be enforced only when participating servers and clients 166 are reliably synchronized to UTC. In addition, the NTP subnet is 167 hierarchical by nature, so time and trust flow from the primary 168 servers at the root through secondary servers to the clients at the 169 leaves. 171 A client can claim authentic to dependent applications only if all 172 servers on the path to the primary servers are bone-fide authentic. 173 In order to emphasize this requirement, in this report the notion of 174 "authentic" is replaced by "proventic", a noun new to English and 175 derived from provenance, as in the provenance of a painting. Having 176 abused the language this far, the suffixes fixable to the various 177 noun and verb derivatives of authentic will be adopted for proventic 178 as well. In NTP each server authenticates the next lower stratum 179 servers and proventicates (authenticates by induction) the lowest 180 stratum (primary) servers. Serious computer linguists would 181 correctly interpret the proventic relation as the transitive closure 182 of the authentic relation. 184 It is important to note that the notion of proventic does not 185 necessarily imply the time is correct. A NTP client mobilizes a 186 number of concurrent associations with different servers and uses 187 crafted mitigation algorithm to pluck truechimers from the population 188 possibly including falsetickers. A particular association is 189 proventic if the server certificate and identity have been verified 190 by the means described in this report. However, the statement "the 191 client is synchronized to proventic sources" means that the system 192 clock has been set using the time values of one or more proventic 193 associations and according to the NTP mitigation algorithms. While a 194 certificate authority (CA) must satisfy this requirement when signing 195 a certificate request, the certificate itself can be stored in public 196 directories and retrieved over unsecured network paths. 198 Over the last several years the IETF has defined and evolved the 199 IPSEC infrastructure for privacy protection and source authentication 200 in the Internet. The infrastructure includes the Encapsulating 201 Security Payload (ESP) [6] and Authentication Header (AH) [7] for 202 IPv4 and IPv6. Cryptographic algorithms that use these headers for 203 various purposes include those developed for the PKI, including MD5 204 message digests, RSA digital signatures and several variations of 205 Diffie-Hellman key agreements. The fundamental assumption in the 206 security model is that packets transmitted over the Internet can be 207 intercepted by other than the intended recipient, remanufactured in 208 various ways and replayed in whole or part. These packets can cause 209 the client to believe or produce incorrect information, cause 210 protocol operations to fail, interrupt network service or consume 211 precious network and processor resources. 213 In the case of NTP, the assumed goal of the intruder is to inject 214 false time values, disrupt the protocol or clog the network, servers 215 or clients with spurious packets that exhaust resources and deny 216 service to legitimate applications. The mission of the algorithms 217 and protocols described in this report is to detect and discard 218 spurious packets sent by other than the intended sender or sent by 219 the intended sender, but modified or replayed by an intruder. The 220 cryptographic means of the reference implementation are based on the 221 OpenSSL cryptographic software library available at www.openssl.org, 222 but other libraries with equivalent functionality could be used as 223 well. It is important for distribution and export purposes that the 224 way in which these algorithms are used precludes encryption of any 225 data other than incidental to the construction of digital signatures. 227 There are a number of defense mechanisms already built in the NTP 228 architecture, protocol and algorithms. The fundamental timestamp 229 exchange scheme is inherently resistant to spoofing and replay 230 attacks. The engineered clock filter, selection and clustering 231 algorithms are designed to defend against evil cliques of Byzantine 232 traitors. While not necessarily designed to defeat determined 233 intruders, these algorithms and accompanying sanity checks have 234 functioned well over the years to deflect improperly operating but 235 presumably friendly scenarios. However, these mechanisms do not 236 securely identify and authenticate servers to clients. Without 237 specific further protection, an intruder can inject any or all of the 238 following attacks. 240 1. An intruder can intercept and archive packets forever, as well as 241 all the public values ever generated and transmitted over the 242 net. 244 2. An intruder can generate packets faster than the server, network 245 or client can process them, especially if they require expensive 246 cryptographic computations. 248 3. In a wiretap attack the intruder can intercept, modify and replay 249 a packet. However, it cannot permanently prevent onward 250 transmission of the original packet; that is, it cannot break the 251 wire, only tell lies and congest it. Except in unlikely cases 252 considered in Section 12, the modified packet cannot arrive at 253 the victim before the original packet, nor does it have the 254 server private keys or identity parameters. 256 4. In a middleman or masquerade attack the intruder is positioned 257 between the server and client, so it can intercept, modify and 258 replay a packet and prevent onward transmission of the original 259 packet. Except in unlikely cases considered in Section 12, the 260 middleman does not have the server private keys or identity 261 parameters. 263 The NTP security model assumes the following possible limitations. 265 1. The running times for public key algorithms are relatively long 266 and highly variable. In general, the performance of the time 267 synchronization function is badly degraded if these algorithms 268 must be used for every NTP packet. 270 2. In some modes of operation it is not feasible for a server to 271 retain state variables for every client. It is however feasible 272 to efficiently regenerated them for a client upon arrival of a 273 packet from that client. 275 3. The lifetime of cryptographic values must be enforced, which 276 requires a reliable system clock. However, the sources that 277 synchronize the system clock must be cryptographically 278 proventicated. This circular interdependence of the timekeeping 279 and proventication functions requires special handling. 281 4. All proventication functions must involve only public values 282 transmitted over the net with the single exception of encrypted 283 signatures and cookies intended only to authenticate the source. 284 Private values must never be disclosed beyond the machine on 285 which they were created except in the case of a special trusted 286 agent (TA) assigned for this purpose. 288 5. Public encryption keys and certificates must be retrievable 289 directly from servers without requiring secured channels; 290 however, the fundamental security of identification credentials 291 and public values bound to those credentials must be a function 292 of certificate authorities and/or webs of trust. 294 6. Error checking must be at the enhanced paranoid level, as network 295 terrorists may be able to craft errored packets that consume 296 excessive cycles with needless result. While this report 297 includes an informal vulnerability analysis and error protection 298 paradigm, a formal model based on communicating finite-state 299 machine analysis remains to be developed. 301 Unlike the Secure Shell security model, where the client must be 302 securely authenticated to the server, in NTP the server must be 303 securely authenticated to the client. In ssh each different 304 interface address can be bound to a different name, as returned by a 305 reverse-DNS query. In this design separate public/private key pairs 306 may be required for each interface address with a distinct name. A 307 perceived advantage of this design is that the security compartment 308 can be different for each interface. This allows a firewall, for 309 instance, to require some interfaces to authenticate the client and 310 others not. 312 However, the NTP security model specifically assumes that access 313 control is performed by means external to the protocol and that all 314 time values and cryptographic values are public, so there is no need 315 to associate each interface with different cryptographic values. To 316 do so would create the possibility of a two-faced clock, which is 317 ordinarily considered a Byzantine hazard. In other words, there is 318 one set of private secrets for the host, not one for each interface. 319 In the NTP design the host name, by default the string returned by 320 the Unix gethostname() library function, represents all interface 321 addresses. Since at least in some host configurations the host name 322 may not be identifiable in a DNS query, the name must be either 323 configured in advance or obtained directly from the server using the 324 Autokey protocol. 326 3. Approach 328 The Autokey protocol described in this report is designed to meet the 329 following objectives. 331 1. It must interoperate with the existing NTP architecture model and 332 protocol design. In particular, it must support the symmetric 333 key scheme described in [8]. 335 2. It must not significantly degrade the potential accuracy of the 336 NTP synchronization algorithms. In particular, it must not make 337 unreasonable demands on the network or host processor and memory 338 resources. 340 3. It must be resistant to cryptographic attacks, specifically those 341 identified in the security model above. In particular, it must 342 be tolerant of operational or implementation variances, such as 343 packet loss or misorder, or suboptimal configurations. 345 4. It must build on a widely available suite of cryptographic 346 algorithms, yet be independent of the particular choice. In 347 particular, it must not require data encryption other than 348 incidental to signature and cookie encryption operations. 350 5. It must function in all the modes supported by NTP, including 351 server, symmetric and broadcast modes. 353 6. It must not require intricate per-client or per-server 354 configuration other than the availability of the required 355 cryptographic keys and certificates. 357 4. Autokey Cryptography 359 Autokey public key cryptography is based on the PKI algorithms 360 commonly used in the Secure Shell and Secure Sockets Layer 361 applications. As in these applications Autokey uses keyed message 362 digests to detect packet modification, digital signatures to verify 363 the source and public key algorithms to encrypt cookies. What makes 364 Autokey cryptography unique is the way in which these algorithms are 365 used to deflect intruder attacks while maintaining the integrity and 366 accuracy of the time synchronization function. 368 NTPv3 and NTPv4 symmetric key cryptography uses keyed-MD5 message 369 digests with a 128-bit private key and 32-bit key ID. In order to 370 retain backward compatibility with NTPv3, the NTPv4 key ID space is 371 partitioned in two subspaces at a pivot point of 65536. Symmetric 372 key IDs have values less than the pivot and indefinite lifetime. 373 Autokey key IDs have pseudo-random values equal to or greater than 374 the pivot and are expunged immediately after use. Both symmetric key 375 and public key cryptography authenticate as shown in Figure 1. The 376 server looks up the key associated with the key ID and calculates the 377 message digest from the NTP header and extension fields together with 378 the key value. The key ID and digest form the message authentication 379 code (MAC) included with the message. The client does the same 380 computation using its local copy of the key and compares the result 381 with the digest in the MAC. If the values agree, the message is 382 assumed authentic. 384 +------------------+ 385 | NTP Header and | 386 | Extension Fields | 387 +------------------+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 388 | | | Message Authenticator Code | 389 \|/ \|/ + (MAC) + 390 ******************** | +-------------------------+ | 391 * Compute Hash *<----| Key ID | Message Digest | + 392 ******************** | +-------------------------+ | 393 | +-+-+-+-+-+-+-|-+-+-+-+-+-+-+-+-+ 394 \|/ \|/ 395 +------------------+ +-------------+ 396 | Message Digest |------>| Compare | 397 +------------------+ +-------------+ 399 Figure 1: Message Authentication 401 There are three Autokey protocol variants corresponding to each of 402 the three NTP modes: server, symmetric and broadcast. All three 403 variants make use of specially contrived session keys, called 404 autokeys, and a precomputed pseudo-random sequence of autokeys which 405 are saved along with the key IDs in a key list. As in the original 406 NTPv3 authentication scheme, the Autokey protocol operates separately 407 for each association, so there may be several autokey sequences 408 operating independently at the same time. 410 +-------------+-------------+--------+--------+ 411 | Src Address | Dst Address | Key ID | Cookie | 412 +-------------+-------------+--------+--------+ 414 Figure 2: NTPv4 Autokey 416 An autokey is computed from four fields in network byte order as 417 shown in Figure 2. The four values are hashed by the MD5 message 418 digest algorithm to produce the 128-bit autokey value, which in the 419 reference implementation is stored along with the key ID in a cache 420 used for symmetric keys as well as autokeys. Keys are retrieved from 421 the cache by key ID using hash tables and a fast lookup algorithm. 423 For use with IPv4, the Source Address and Dest Address fields contain 424 32 bits; for use with IPv6, these fields contain 128 bits. In either 425 case the Key ID and Cookie fields contain 32 bits. Thus, an IPv4 426 autokey has four 32-bit words, while an IPv6 autokey has ten 32-bit 427 words. The source and destination addresses and key ID are public 428 values visible in the packet, while the cookie can be a public value 429 or private value, depending on the mode. 431 The NTP packet format has been augmented to include one or more 432 extension fields piggybacked between the original NTP header and the 433 MAC at the end of the packet. For packets without extension fields, 434 the cookie is a shared private value conveyed in encrypted form. For 435 packets with extension fields, the cookie has a default public value 436 of zero, since these packets can be validated independently using 437 digital signatures. 439 There are some scenarios where the use of endpoint IP addresses may 440 be difficult or impossible. These include configurations where 441 network address translation (NAT) devices are in use or when 442 addresses are changed during an association lifetime due to mobility 443 constraints. For Autokey, the only restriction is that the address 444 fields visible in the transmitted packet must be the same as those 445 used to construct the autokey sequence and key list and that these 446 fields be the same as those visible in the received packet. 448 For scenarios where the endpoint IP addresses are not available, an 449 optional public identification value could be used instead of the 450 addresses. Examples include the Interplanetary Internet, where 451 bundles are identified by name rather than address. Specific 452 provisions are for further study. 454 +-----------+-----------+------+------+ +---------+ +-----+------+ 455 |Src Address|Dst Address|Key ID|Cookie|-->| | |Final|Final | 456 +-----------+-----------+------+------+ | Session | |Index|Key ID| 457 | | | | | Key ID | +-----+------+ 458 \|/ \|/ \|/ \|/ | List | | | 459 ************************************* +---------+ \|/ \|/ 460 * COMPUTE HASH * ******************* 461 ************************************* *COMPUTE SIGNATURE* 462 | Index n ******************* 463 \|/ | 464 +--------+ | 465 | Next | \|/ 466 | Key ID | +-----------+ 467 +--------+ | Signature | 468 Index n+1 +-----------+ 470 Figure 3: Constructing the Key List 472 Figure 3 shows how the autokey list and autokey values are computed. 473 The key list consists of a sequence of key IDs starting with a random 474 32-bit nonce (autokey seed) equal to or greater than the pivot as the 475 first key ID. The first autokey is computed as above using the given 476 cookie and the first 32 bits of the result in network byte order 477 become the next key ID. Operations continue to generate the entire 478 list. It may happen that a newly generated key ID is less than the 479 pivot or collides with another one already generated (birthday 480 event). When this happens, which occurs only rarely, the key list is 481 terminated at that point. The lifetime of each key is set to expire 482 one poll interval after its scheduled use. In the reference 483 implementation the list is terminated when the maximum key lifetime 484 is about one hour, so for poll intervals above one hour a new key 485 list containing only a single entry is regenerated for every poll. 487 +------------------+ 488 | NTP Header and | 489 | Extension Fields | 490 +------------------+ 491 | | 492 \|/ \|/ +---------+ 493 **************** +--------+ | Session | 494 * COMPUTE HASH *<---| Key ID |<---| Key ID | 495 **************** +--------+ | List | 496 | | +---------+ 497 \|/ \|/ 498 +----------------------------------+ 499 | Message Authenticator Code (MAC) | 500 +----------------------------------+ 501 Figure 4: Transmitting Messages 503 The index of the last key ID in the list is saved along with the next 504 key ID for that entry, collectively called the autokey values. The 505 autokey values are then signed. The list is used in reverse order as 506 shown in Figure 4, so that the first autokey used is the last one 507 generated. The Autokey protocol includes a message to retrieve the 508 autokey values and signature, so that subsequent packets can be 509 validated using one or more hashes that eventually match the last key 510 ID (valid) or exceed the index (invalid). This is called the autokey 511 test in the following and is done for every packet, including those 512 with and without extension fields. In the reference implementation 513 the most recent key ID received is saved for comparison with the 514 first 32 bits in network byte order of the next following key value. 515 This minimizes the number of hash operations in case a single packet 516 is lost. 518 5. Secure Groups 520 A digital signature scheme provides an authentic certificate trail, 521 but does not provide protection against masquerade, unless the server 522 identity is verified by other means. The PKI security model assumes 523 each host is able to verify the certificate trail to a trusted 524 certificate authority (CA), where each ascendant host must prove 525 identity to the immediately descendant host by independent means, 526 such as a credit card number or PIN. While Autokey supports this 527 model by default, in a hierarchical ad-hoc network, especially with 528 server discovery schemes like NTP Manycast, proving identity at each 529 rest stop on the trail must be an intrinsic capability of Autokey 530 itself. 532 In the NTP security model every member of a closed group, such as 533 might be operated by a timestamping service, be in possession of a 534 secret group key. This could take the form of a private certificate 535 or one or another identification schemes described in the literature 536 and Appendix D. Certificate trails and identification schemes are at 537 the heart of the NTP security model preventing masquerade and 538 middleman attacks. The Autokey protocol operates to hike the trails 539 and then run the identity schemes. 541 A NTP secure group consists of a number of hosts dynamically 542 assembled as a forest with roots the trusted hosts at the lowest 543 stratum of the group. The trusted hosts do not have to be, but often 544 are, primary (stratum 1) servers. A trusted authority (TA), usually 545 one of the trusted hosts, generates private and public identity media 546 and deploys selected values to the group members. The identity 547 values are of two kinds, encrypted private keys used by servers with 548 dependent clients and nonencrypted public parameters used by all 549 hosts, including those that are not group members, but depend on 550 group members for authentication purposes.Figure 5 552 +-------------+ +-------------+ +-------------+ 553 | Alice | | Brenda | | Denise | 554 | | | | | | 555 | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 556 Certificate | | Alice | | | | Brenda| | | | Denise| | 557 +-+-+-+-+-+ | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 558 | Subject | | | Alice*| 1 | | | Alice | 4 | | | Carol | 4 | 559 +-+-+-+-+-+ | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 560 | Issuer | S | | | | | | 561 +-+-+-+-+-+ | +=======+ | | +-+-+-+-+ | | +-+-+-+-+ | 562 | ||Alice|| 3 | | | Alice | | | | Carol | | 563 Group Key | +=======+ | | +-+-+-+-+ | | +-+-+-+-+ | 564 +=========+ +-------------+ | | Alice*| 2 | | | Carol*| 2 | 565 || Group || S | Carol | | +-+-+-+-+ | | +-+-+-+-+ | 566 +=========+ | | | | | | 567 | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 568 S = step | | Carol | | | | Brenda| | | | Denise| | 569 * = trusted | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 570 | | Carol*| 1 | | | Brenda| 1 | | | Denise| 1 | 571 | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 572 | | | | | | 573 | +=======+ | | +=======+ | | +=======+ | 574 | ||Alice|| 3 | | ||Alice|| 3 | | ||Alice|| 3 | 575 | +=======+ | | +=======+ | | +=======+ | 576 +-------------+ +-------------+ +-------------+ 577 Stratum 1 Stratum 2 579 +---------------------------------------------+ 580 | Eileen | 581 | | 582 | +-+-+-+-+ +-+-+-+-+ | 583 | | Eileen| | Eileen| | 584 | +-+-+-+-+ +-+-+-+-+ | 585 | | Brenda| | Carol | 4 | 586 | +-+-+-+-+ +-+-+-+-+ | 587 | | 588 | +-+-+-+-+ +-+-+-+-+ | 589 | | Alice | | Carol | | 590 | +-+-+-+-+ +-+-+-+-+ | 591 | | Alice*| | Carol*| 2 | 592 | +-+-+-+-+ +-+-+-+-+ | 593 | | 594 | +-+-+-+-+ +-+-+-+-+ | 595 | | Brenda| | Denise| | 596 | +-+-+-+-+ +-+-+-+-+ | 597 | | Alice | | Carol | 2 | 598 | +-+-+-+-+ +-+-+-+-+ | 599 | | 600 | +-+-+-+-+ | 601 | | Eileen| | 602 | +-+-+-+-+ | 603 | | Eileen| 1 | 604 | +-+-+-+-+ | 605 | | 606 | +=======+ | 607 | ||Alice|| 3 | 608 | +=======+ | 609 +---------------------------------------------+ 610 Stratum 3 612 Figure 5: NTP Secure Groups 614 The steps in hiking the certificate trails and verifying identity are 615 as follows. Note the step number in the description matches the step 616 number in the figure. 618 1. At startup each host loads its self-signed certificate from a 619 local file. By convention the lowest stratum certificates are 620 marked trusted in a X.509 extension field. As Alice and Carol 621 have trusted certificates, they need do nothing further to 622 validate the time. It could be that the trusted hosts depend on 623 servers in other groups; this scenario is discussed later. 625 2. The girls begin the Autokey protocol which establishes the server 626 name, signature scheme, certificate and identity scheme for each 627 group host. They continue to load certificates recursively until 628 a self-signed trusted certificate is found. Brenda and Denise 629 immediately find self-signed trusted certificates for Alice and 630 Carol, respectively, but Eileen will loop because neither Brenda 631 nor Denise have their own certificates signed by either Alice or 632 Carol. 634 3. Brenda and Denise continue with one of the identity schemes 635 described below to verify each has the group keys previously 636 deployed by Alice. If this succeeds, each continues in step 4. 638 4. Brenda and Denise present their certificates to Alice and Carol 639 for signature. If this succeeds, either or both Brenda and 640 Denise can now provide these signed certificates to Eileen, which 641 may be looping in step 2. When Eileen receives them, she can now 642 follow the trail via either Brenda or Denise to the trusted 643 certificates for Alice and Carol. Once this is done, Eileen can 644 complete the protocol just as Brenda and Denise. 646 The NTP security model is based on multiple, hierarchical, 647 overlapping security compartments or groups. The example above 648 illustrates how groups can be used to construct closed compartments, 649 depending on how the identity credentials are deployed. The rules 650 can be summarized: 652 1. Every host holds the public parameters generated by a TA. Those 653 hosts with clients hold in addition the secret group key. 655 2. A host is trusted if it operates at the lowest stratum in the 656 group and has a trusted, self-signed certificate. 658 3. A host uses the identity scheme to prove to another host it has 659 the same group key, even as in some (zero knowledge) schemes 660 neither knows the exact key value. 662 4. A client verifies group membership if the server can prove it has 663 the same key as the client and has an unbroken certificate trail 664 to a trusted host. 666 For various reasons it may be convenient for the trusted hosts to 667 hold parameters for one or more groups operating at a lower stratum. 668 For example, Figure 6 shows three secure groups Alice, Helen and 669 Carol arranged in a hierarchy. Hosts A, B, C and D belong to the 670 Alice group, hosts R and S to the Helen group and hosts X, Y and Z to 671 the Carol group. While not strictly necessary, hosts A, B and R are 672 stratum 1 and presumed trusted; the TA generating the group keys and 673 parameters could be one of them or another not shown. 675 ***** ***** @@@@@ 676 Stratum 1 * A * * B * @ R @ 677 ***** ***** @@@@@ 678 \ / / 679 \ / / 680 ***** @@@@@ ********* 681 2 * C * @ S @ * Alice * 682 ***** @@@@@ ********* 683 / \ / 684 / \ / @@@@@@@@@ 685 ***** ##### @ Helen @ 686 3 * D * # X # @@@@@@@@@ 687 ***** ##### 688 / \ ######### 689 / \ # Carol # 690 ##### ##### ######### 691 4 # Y # # Z # 692 ##### ##### 694 Figure 6: Hierarchical Overlapping Groups 696 The intent of the design is to provide security separation, so that 697 servers cannot masquerade as TAs and clients cannot masquerade as 698 servers. Assume for example that Alice and Helen belong to national 699 standards laboratories and their group keys are used to confirm 700 identity between members of each group. Carol is a prominent 701 corporation receiving standards products via broadcast satellite and 702 requiring cryptographic authentication. 704 Perhaps under contract, host X belonging to the Carol group has 705 rented group parameters for both Alice and Helen and has group keys 706 for Carol. The Autokey protocol operates for each group separately 707 while preserving security separation. Host X can prove identity in 708 Carol to clients Y and Z, but cannot prove to anybody that it belongs 709 to either Alice or Helen. 711 In some scenarios it would be desirable that servers cannot 712 masquerade as the TA and clients cannot masquerade as servers. This 713 can be assured using the MV identity scheme described later. It 714 allows the same broadcast transmission to be authenticated by more 715 than one key, one used internally by the laboratories (Alice and/or 716 Helen) and the other handed out to clients like Carol. In the MV 717 scheme these keys can be separately activated upon subscription and 718 deactivated if the subscriber fails to pay the bill. In the MV 719 scheme a key can be deactivated without requiring the other keys to 720 be recomputed. 722 Figure 7 shows operational details where more than one group is 723 involved, in this case Carol and Alice. As in the previous example, 724 Brenda has configured Alice as her time source and Denise has 725 configured Carol as her time source. Alice and Brenda have group 726 keys and parameters for the Alice group; Carol and Denise have group 727 keys and parameters for the Carol group. Eileen has parameters for 728 both groups. The protocol operates as previously described to verify 729 Alice to Brenda and Carol to Denise. 731 +-------------+ +-------------+ +-------------+ 732 | Alice | | Brenda | | Denise | 733 | | | | | | 734 | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 735 Certificate | | Alice | | | | Brenda| | | | Denise| | 736 +-+-+-+-+-+ | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 737 | Subject | | | Alice*| 1 | | | Alice | 4 | | | Carol | 4 | 738 +-+-+-+-+-+ | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 739 | Issuer | S | | | | | | 740 +-+-+-+-+-+ | +=======+ | | +-+-+-+-+ | | +-+-+-+-+ | 741 | ||Alice|| 3 | | | Alice | | | | Carol | | 742 Group Key | +=======+ | | +-+-+-+-+ | | +-+-+-+-+ | 743 +=========+ +-------------+ | | Alice*| 2 | | | Carol*| 2 | 744 || Group || S | Carol | | +-+-+-+-+ | | +-+-+-+-+ | 745 +=========+ | | | | | | 746 | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 747 S = step | | Carol | | | | Brenda| | | | Denise| | 748 * = trusted | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 749 | | Carol*| 1 | | | Brenda| 1 | | | Denise| 1 | 750 | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 751 | | | | | | 752 | +=======+ | | +=======+ | | +=======+ | 753 | ||Carol|| 3 | | ||Alice|| 3 | | ||Carol|| 3 | 754 | +=======+ | | +=======+ | | +=======+ | 755 +-------------+ +-------------+ +-------------+ 756 Stratum 1 Stratum 2 758 +---------------------------------------------+ 759 | Eileen | 760 | | 761 | +-+-+-+-+ +-+-+-+-+ | 762 | | Eileen| | Eileen| | 763 | +-+-+-+-+ +-+-+-+-+ | 764 | | Brenda| | Carol | 4 | 765 | +-+-+-+-+ +-+-+-+-+ | 766 | | 767 | +-+-+-+-+ +-+-+-+-+ | 768 | | Alice | | Carol | | 769 | +-+-+-+-+ +-+-+-+-+ | 770 | | Alice*| | Carol*| 2 | 771 | +-+-+-+-+ +-+-+-+-+ | 772 | | 773 | +-+-+-+-+ +-+-+-+-+ | 774 | | Brenda| | Denise| | 775 | +-+-+-+-+ +-+-+-+-+ | 776 | | Alice | | Carol | 2 | 777 | +-+-+-+-+ +-+-+-+-+ | 778 | | 779 | +-+-+-+-+ | 780 | | Eileen| | 781 | +-+-+-+-+ | 782 | | Eileen| 1 | 783 | +-+-+-+-+ | 784 | | 785 | +=======+ +=======+ | 786 | ||Alice|| ||Carol|| 3 | 787 | +=======+ +=======+ | 788 +---------------------------------------------+ 789 Stratum 3 791 Figure 7: Multiple Overlapping Groups 793 The interesting case is Eileen, who may verify identity either via 794 Brenda or Denise or both. To do that she uses the public pameters of 795 either Alice and Carol or both. But, Eileen doesn't know which of 796 the two parameters to use until hiking the certificate trail to find 797 the trusted certificate of either Alice or Carol and then loading the 798 associated parameters. This scenario can of course become even more 799 complex as the number of servers and depth of the tree increase. The 800 bottom line is that every host must have the parameters for all the 801 lowest-stratum trusted hosts it is ever likely to find. 803 6. Identity Schemes 805 While the identity scheme described in [9] is based on a ubiquitous 806 Diffie-Hellman infrastructure, it is expensive to generate and use 807 when compared to others described in Appendix D. There are five 808 schemes now implemented in the NTPv4 reference implementation to 809 prove identity: (1) private certificate (PC), (2) trusted certificate 810 (TC), (3) a modified Schnorr algorithm (IFF aka Identify Friendly or 811 Foe), (4) a modified Guillou-Quisquater algorithm (GQ), and (5) a 812 modified Mu-Varadharajan algorithm (MV). Following is a summary 813 description of each; details are given in Appendix D. 815 The PC scheme involves a private certificate as group key. A 816 certificate is designated private by a X509 Version 3 extension field 817 when generated by utility routines in the NTP software distribution. 819 The certificate is distributed to all other group members by secure 820 means and is never revealed outside the group. A client is marked 821 trusted when the first signature is verified. In effect, the private 822 certificate is used as a symmetric key. This scheme is 823 cryptographically strong as long as the private certificate is 824 protected; however, it can be very awkward to refresh the keys or 825 certificate, since new values must be securely distributed to a 826 possibly large population and activated simultaneously. It is 827 included here primarily as a yardstick and protocol exercise. 829 All other schemes involve a conventional certificate trail as 830 described in RFC 4210 [10], where each certificate is signed by an 831 issuer one step closer to the trusted hosts, which have self-signed 832 trusted certificates. A certificate is designated trusted by a X509 833 Version 3 extension field when generated by utility routines in the 834 NTP software distribution. A host obtains the certificates of all 835 other hosts along the trail ending at a trusted host, then requests 836 the immediately ascendant host to sign its own certificate. 837 Subsequently, these certificates are provided to descendent hosts by 838 the Autokey protocol. In this scheme keys, parameters and 839 certificates can be refreshed at any time, but a masquerade 840 vulnerability remains unless a request to sign a client certificate 841 is validated by some means such as reverse-DNS. If no specific 842 identity scheme is specified, this is the default TC identity scheme. 844 The three remaining schemes IFF, GQ and MV involve a 845 cryptographically strong challenge-response exchange where an 846 intruder cannot learn the group key, even after repeated observations 847 of multiple exchanges. In addition, the IFF and MV schemes are 848 properly described as zero-knowledge proofs, because the client can 849 verify the server has the group key without the client knowing its 850 value. 852 These schemes start when the client sends a nonce to the server, 853 which then rolls its own nonce, performs a mathematical operation and 854 sends the results along with a message digest to the client. The 855 client performs another mathematical operation and verifies the 856 results match the message digest. The IFF scheme is used when the 857 certificate is generated by a third party, such as a commercial 858 service and in general has the same refreshment and distribution 859 problems as PC. However, this scheme has the advantage that the 860 group key is not known to the clients. 862 On the other hand, when certificates are generated by routines in the 863 NTPv4 distribution, the GQ scheme may be a better choice. In this 864 scheme the server further obscures the secret group key using a 865 public/private key pair which can be refreshed at any time. The 866 public member is conveyed in the certificate by a X509 Version 3 867 extension field which changes for each regeneration of key pair and 868 certificate. 870 The MV scheme is perhaps the most interesting and flexible of the 871 three challenge/response schemes. It can be used when a small number 872 of servers provide synchronization to a large client population where 873 there might be considerable risk of compromise between and among the 874 servers and clients. The TA generates a deliciously intricate 875 cryptosystem involving public and private encryption keys, together 876 with a number of activation keys and associated private client 877 decryption keys. The activation keys are used by the TA to activate 878 and revoke individual client decryption keys without changing the 879 decryption keys themselves. 881 The TA provides the server with a private encryption key and public 882 decryption key. The server adjusts the keys by a nonce for each 883 plaintext encryption, so they appear different on each use. The 884 encrypted ciphertext and adjusted public decryption key are provided 885 in the client message. The client computes the decryption key from 886 its private decryption key and the public decryption key in the 887 message. 889 7. Autokey Operations 891 The Autokey protocol has three variations or dances corresponding to 892 the NTP server, symmetric and broadcast modes. The server dance was 893 suggested by Steve Kent over lunch some time ago, but considerably 894 modified since that meal. The server keeps no state for each client, 895 but uses a fast algorithm and a 32-bit random private value (server 896 seed) to regenerate the cookie upon arrival of a client packet. The 897 cookie is calculated as the first 32 bits of the autokey computed 898 from the client and server addresses, a key ID of zero and the server 899 seed as cookie. The cookie is used for the actual autokey 900 calculation by both the client and server and is thus specific to 901 each client separately. 903 In previous Autokey versions the cookie was transmitted in clear on 904 the assumption it was not useful to a wiretapper other than to launch 905 an ineffective replay attack. However, a middleman could intercept 906 the cookie and manufacture bogus messages acceptable to the client. 907 In order to reduce the risk of such an attack, the Autokey Version 2 908 server encrypts the cookie using a public key supplied by the client. 909 While requiring additional processor resources for the encryption, 910 this makes it effectively impossible to spoof a cookie or masquerade 911 as the server. 913 In the server dance the client uses the cookie and each key ID on the 914 key list in turn to retrieve the autokey and generate the MAC in the 915 NTP packet. The server uses the same values to generate the message 916 digest and verifies it matches the MAC in the packet. It then 917 generates the MAC for the response using the same values, but with 918 the client and server addresses exchanged. The client generates the 919 message digest and verifies it matches the MAC in the packet. In 920 order to deflect old replays, the client verifies the key ID matches 921 the last one sent. In this mode the sequential structure of the key 922 list is not exploited, but doing it this way simplifies and 923 regularizes the implementation while making it nearly impossible for 924 an intruder to guess the next key ID. 926 In the broadcast dance clients normally do not send packets to the 927 server, except when first starting up to verify credentials and 928 calibrate the propagation delay. At the same time the client runs 929 the broadcast dance to obtain the autokey values. The dance requires 930 the association ID of the particular server association, since there 931 can be more than one operating in the same server. For this purpose, 932 the server packet includes the association ID in every response 933 message sent and, when sending the first packet after generating a 934 new key list, it sends the autokey values as well. After obtaining 935 and verifying the autokey values, the client verifies further server 936 packets using the autokey sequence. 938 The symmetric dance is similar to the server dance and keeps only a 939 small amount of state between the arrival of a packet and departure 940 of the reply. The key list for each direction is generated 941 separately by each peer and used independently, but each is generated 942 with the same cookie. The cookie is conveyed in a way similar to the 943 server dance, except that the cookie is a random value. There exists 944 a possible race condition where each peer sends a cookie request 945 message before receiving the cookie response from the other peer. In 946 this case, each peer winds up with two values, one it generated and 947 one the other peer generated. The ambiguity is resolved simply by 948 computing the working cookie as the EXOR of the two values. 950 Autokey choreography includes one or more exchanges, each with a 951 specific purpose, that must be completed in order. The client 952 obtains the server host name, digest/signature scheme and identity 953 scheme in the parameter exchange. It recursively obtains and 954 verifies certificates on the trail leading to a trusted certificate 955 in the certificate exchange and verifies the server identity in the 956 identity exchange. In the values exchange the client obtains the 957 cookie and autokey values, depending on the particular dance. 958 Finally, the client presents its self-signed certificate to the 959 server for signature in the sign exchange. 961 Once the certificates and identity have been validated, subsequent 962 packets are validated by digital signatures and autokey sequences. 963 These packets are presumed to contain valid time values; however, 964 unless the system clock has already been set by some other proventic 965 means, it is not known whether these values actually represent a 966 truechime or falsetick source. As the protocol evolves, the NTP 967 associations continue to accumulate time values until a majority 968 clique is available in a population of at least three servers. At 969 this point the NTP mitigation algorithms cull the falsetickers and 970 cluster outlyers from the population and the survivors are allowed to 971 discipline the system clock. 973 The time values for truechimer sources form a proventic partial 974 ordering relative to the applicable signature timestamps. This 975 raises the interesting issue of how to mitigate between the 976 timestamps of different associations. It might happen, for instance, 977 that the timestamp of some Autokey message is ahead of the system 978 clock by some presumably small amount. For this reason, timestamp 979 comparisons between different associations and between associations 980 and the system clock are avoided, except in the NTP intersection and 981 clustering algorithms and when determining whether a certificate has 982 expired. 984 Once the Autokey values have been instantiated, the dances are 985 normally dormant. In all except the broadcast dance, packets are 986 normally sent without extension fields, unless the packet is the 987 first one sent after generating a new key list or unless the client 988 has requested the cookie or autokey values. If for some reason the 989 client clock is stepped, rather than slewed, all cryptographic and 990 time values for all associations are purged and the dances in all 991 associations restarted from scratch. This insures that stale values 992 never propagate beyond a clock step. At intervals of about one day 993 the reference implementation purges all associations, refreshes all 994 signatures, garbage collects expired certificates and refreshes the 995 server seed. 997 8. Public Key Signatures and Timestamps 999 While public key signatures provide strong protection against 1000 misrepresentation of source, computing them is expensive. This 1001 invites the opportunity for an intruder to clog the client or server 1002 by replaying old messages or to originate bogus messages. A client 1003 receiving such messages might be forced to verify what turns out to 1004 be an invalid signature and consume significant processor resources. 1006 In order to foil such attacks, every signed extension field carries a 1007 timestamp in the form of the NTP seconds at the signature epoch. The 1008 signature spans the entire extension field including the timestamp. 1010 If the Autokey protocol has verified a proventic source and the NTP 1011 algorithms have validated the time values, the system clock can be 1012 synchronized and signatures will then carry a nonzero (valid) 1013 timestamp. Otherwise the system clock is unsynchronized and 1014 signatures carry a zero (invalid) timestamp. The protocol detects 1015 and discards replayed extension fields with old or duplicate 1016 timestamps, as well as fabricated extension fields with bogus 1017 timestamps, before any values are used or signatures verified. 1019 There are three signature types currently defined: 1021 1. Cookie signature/timestamp. Each association has a cookie for 1022 use when generating a key list. The cookie value is determined 1023 along with the cookie signature and timestamp upon arrival of a 1024 cookie request message. The values are returned in a a cookie 1025 response message. 1027 2. Autokey signature/timestamp. Each association has a key list for 1028 generating the autokey sequence. The autokey values are 1029 determined along with the autokey signature and timestamp when a 1030 new key list is generated, which occurs about once per hour in 1031 the reference implementation. The values are returned in a 1032 autokey response message. 1034 3. Public values signature/timestamp. All public key and 1035 certificate values are signed at the time of generation, which 1036 occurs when the system clock is first synchronized to a proventic 1037 source, when the values have changed and about once per day after 1038 that, even if these values have not changed. During protocol 1039 operations, each of these values and associated signatures and 1040 timestamps are returned in the associated request or response 1041 message. While there are in fact several public value 1042 signatures, depending on the number of entries on the certificate 1043 list, the values are all signed at the same time, so there is 1044 only one public value timestamp. 1046 The most recent timestamp received of each type is saved for 1047 comparison. Once a valid signature with valid timestamp has been 1048 received, messages with invalid timestamps or earlier valid 1049 timestamps of the same type are discarded before the signature is 1050 verified. For signed messages this deflects replays that otherwise 1051 might consume significant processor resources. For other messages 1052 the Autokey protocol deflects message modification or replay by a 1053 wiretapper, but not necessarily by a middleman. In addition, the NTP 1054 protocol itself is inherently resistant to replays and consumes only 1055 minimal processor resources. 1057 All cryptographic values used by the protocol are time sensitive and 1058 are regularly refreshed. In particular, files containing 1059 cryptographic basis values used by signature and encryption 1060 algorithms are regenerated from time to time. It is the intent that 1061 file regenerations occur without specific advance warning and without 1062 requiring prior distribution of the file contents. While 1063 cryptographic data files are not specifically signed, every file is 1064 associated with a filestamp in the form of the NTP seconds at the 1065 creation epoch. It is not the intent in this report to specify file 1066 formats or names or encoding rules; however, whatever conventions are 1067 used must support a NTP filestamp in one form or another. Additional 1068 details specific to the reference implementation are in Appendix A. 1070 Filestamps and timestamps can be compared in any combination and use 1071 the same conventions. It is necessary to compare them from time to 1072 time to determine which are earlier or later. Since these quantities 1073 have a granularity only to the second, such comparisons are ambiguous 1074 if the values are in the same second. Thus, the ambiguity must be 1075 resolved for each comparison operation as described in Appendix B. 1077 It is important that filestamps be proventic data; thus, they cannot 1078 be produced unless the producer has been synchronized to a proventic 1079 source. As such, the filestamps throughout the NTP subnet represent 1080 a partial ordering of all creation epochs and serve as means to 1081 expunge old data and insure new data are consistent. As the data are 1082 forwarded from server to client, the filestamps are preserved, 1083 including those for certificate files. Packets with older filestamps 1084 are discarded before spending cycles to verify the signature. 1086 9. Autokey Protocol Overview 1088 This section presents an overview of the three dances: server, 1089 broadcast and symmetric. Each dance is designed to be nonintrusive 1090 and to require no additional packets other than for regular NTP 1091 operations. The NTP and Autokey protocols operate independently and 1092 simultaneously and use the same packets. When the preliminary dance 1093 exchanges are complete, subsequent packets are validated by the 1094 autokey sequence and thus considered proventic as well. Autokey 1095 assumes hosts poll servers at a relatively low rate, such as once per 1096 minute or slower. In particular, it is assumed that a request sent 1097 at one poll opportunity will normally result in a response before the 1098 next poll opportunity; however the protocol is robust against a 1099 missed or duplicate response. 1101 The Autokey protocol data unit is the extension field, one or more of 1102 which can be piggybacked in the NTP packet. An extension field 1103 contains either a request with optional data or a response with or 1104 without data. To avoid deadlocks, any number of responses can be 1105 included in a packet, but only one request. A response is generated 1106 for every request, even if the requestor is not synchronized to a 1107 proventic source, but contain meaningful data only if the responder 1108 is synchronized to a proventic source. Some requests and most 1109 responses carry timestamped signatures. The signature covers the 1110 entire extension field, including the timestamp and filestamp, where 1111 applicable. Only if the packet passes all extension field tests are 1112 cycles spent to verify the signature. 1114 All dances begin with the parameter exchange where the host obtains 1115 the server host name and status word specifying the digest/signature 1116 scheme it will use and the identity schemes it supports. The dance 1117 continues with the certificate exchange where the host obtains and 1118 verifies the certificates along the trail to a trusted, self-signed 1119 certificate usually, but not necessarily, provided by a primary 1120 (stratum 1) server. Primary servers are by design proventic with 1121 trusted, self-signed certificates. 1123 However, the certificate trail is not sufficient protection against 1124 middleman attacks unless an identity scheme such as described in 1125 Appendix D or proof-of-possession scheme in [9] is available. While 1126 the protocol for a generic challenge/response scheme is defined in 1127 this report, the choice of one or another required or optional 1128 identification schemes is yet to be determined. If all certificate 1129 signatures along the trail are verified and the server identity is 1130 confirmed, the host continues with the cookie and autokey exchanges 1131 as necessary to complete the protocol. Upon completion the host 1132 verifies packets using digital signatures and/or the autokey 1133 sequence. 1135 Once synchronized to a proventic source, the host continues with the 1136 sign exchange where the server acting as CA signs the host 1137 certificate. The CA interprets the certificate as a X.509v3 1138 certificate request, but verifies the signature if it is self-signed. 1139 The CA extracts the subject, issuer, extension fields and public key, 1140 then builds a new certificate with these data along with its own 1141 serial number and begin and end times, then signs it using its own 1142 public key. The host uses the signed certificate in its own role as 1143 CA for dependent clients. 1145 A final exchange occurs when the server has the NIST leapseconds 1146 table, as indicated in the host status word. If so, the host 1147 requests the table and compares the filestamp with its own 1148 leapseconds table filestamp, if available. If the server table is 1149 newer than the host table, the host replaces its table with the 1150 server table. The host, acting as server, can now provide the most 1151 recent table to its dependent clients. In symmetric mode, this 1152 results in both peers having the newest table. 1154 10. Autokey State Machine 1156 This section describes the formal model of the Autokey state machine, 1157 its state variables and the state transition functions. 1159 10.1. Status Word 1161 Each server and client operating also as a server implements a host 1162 status word, while each client implements an association status word 1163 for each server. Both words have the format and content shown in 1164 Figure 8. The low order 16 bits of the status word define the state 1165 of the Autokey protocol, while the high order 16 bits specify the 1166 message digest/signature encryption scheme. as encoded in the OpenSSL 1167 library. Bits 24-31 of the status word are reserved for server use, 1168 while bits 16-23 are reserved for client association use. In the 1169 host portion bits 24-27 specify the available identity schemes, while 1170 bits 28-31 specify the server capabilities. There are four 1171 additional bits implemented separately. 1173 1 2 3 1174 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 1175 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1176 | Digest / Signature NID | Client | Ident | Host | 1177 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1179 Figure 8: Status Word 1181 The host status word is included in the ASSOC request and response 1182 messages. The client copies this word to the association status word 1183 and then lights additional status bits as the dance proceeds. Once 1184 enabled, these bits never come dim unless a general reset occurs and 1185 the protocol is restarted from the beginning. The status bits are 1186 defined as follows: 1188 o ENB (31) - Lit if the server implements the Autokey protocol 1190 o LPF (30) - Lit if the server has loaded a valid leapseconds file 1192 o IDN (24-27) - These four bits select which identity scheme is in 1193 use. While specific coding for various schemes is yet to be 1194 determined, the schemes available in the reference implementation 1195 and described in Appendix D include the following: 1197 * 0x0 Trusted Certificate (TC) Scheme (default) 1199 * 0x1 Private Certificate (PC) Scheme 1200 * 0x2 Schnorr aka Identify-Friendly-or-Foe (IFF) Scheme 1202 * 0x4 Guillard-Quisquater (GC) Scheme 1204 * 0x8 Mu-Varadharajan (MV) Scheme 1206 The PC scheme is exclusive of any other scheme. Otherwise, the IFF, 1207 GQ and MV bits can be lit in any combination. 1209 The association status bits are defined as follows: 1211 o VAL (0x0100) - Lit when the server certificate and public key are 1212 validated. 1214 o IFF (0x0200) - Lit when the server identity credentials are 1215 confirmed. 1217 o PRV (0x0400) - Lit when the server signature is verified using the 1218 public key and identity credentials. Also called the proventic 1219 bit elsewhere in this report. When enabled, signed values in 1220 subsequent messages are presumed proventic. 1222 o CKY (0x0800) - Lit when the cookie is received and validated. 1223 When enabled, key lists can be generated. 1225 o AUT (0x1000) - Lit when the autokey values are received and 1226 validated. When enabled, clients can validate packets without 1227 extension fields according to the autokey sequence. 1229 o SGN (0x2000) - Lit when the host certificate is signed by the 1230 server. 1232 o LPT (0x4000) - Lit when the leapseconds table is received and 1233 validated. 1235 There are four additional status bits LST, LBK, DUP, and SYN not 1236 included in the status word. All except SYN are association 1237 properties, while SYN is a host property. These bits may be enabled 1238 (set to 1) or disabled (set to 0) as the protocol proceeds; all 1239 except LST are active whether or not the protocol is running. LST is 1240 enabled when the key list is regenerated and signed and comes dim 1241 after the autokey values have been transmitted. This is necessary to 1242 avoid livelock under some conditions. SYN is enabled when the client 1243 has synchronized to a proventic source and never dim after that. 1244 There are two error bits maintained by the NTP on-wire protocol: 1246 o LBK - indicates the received packet does not match the last one 1247 sent 1249 o DUP - indicates a duplicate packet 1251 These bits, which are described in Appendix B, are lit if the 1252 corresponding error has occurred for the current packet and dim 1253 otherwise. 1255 10.2. Host State Variables 1257 Following is a list of state variables used by the server protocol. 1259 o Host Name - The name of the server; by default, the string 1260 returned by the Unix gethostname() library function. The name 1261 must agree with the subject name in the server certificate 1263 o Host Status Word - This word is initialized when the host first 1264 starts up. The format is described above 1266 o Host Key - The RSA public/private key pair used to encrypt/decrypt 1267 cookies. This is also the default sign key 1269 o Sign Key - The RSA or DSA public/private key pair used to encrypt/ 1270 decrypt signatures when the host key is not used for this purpose 1272 o Sign Digest - The message digest algorithm used to compute the 1273 signature before encryption 1275 o IFF identity - The keys and parameters used in the optional IFF 1276 identity scheme described in Appendix D 1278 o GQ identity - The keys and parameters used in the optional GQ 1279 identity scheme described in Appendix D 1281 o MV identity - The keys and parameters used in the optional MV 1282 identity scheme described in Appendix D 1284 o Server Seed - The private value hashed with the IP addresses to 1285 construct the cookie 1287 o Certificate Information Structure (CIS) - Certificates are used to 1288 construct certificate information structures (CIS) which are 1289 stored on the certificate list. The structure includes certain 1290 information fields from an X.509v3 certificate, together with the 1291 certificate itself encoded in ASN.1 syntax. Each structure 1292 carries the public value timestamp and the filestamp of the 1293 certificate file when it was generated. Elsewhere in this report 1294 the CIS will not be distinguished from the certificate unless 1295 noted otherwise. A flags field in the CIS determines the status 1296 of the certificate. The field is encoded as follows: 1298 * TRST (0x01) - The certificate has been signed by a trusted 1299 issuer. If the certificate is self-signed and contains 1300 "trustRoot" in the Extended Key Usage field, this bit will be 1301 lit when the CIS is constructed 1303 * SIGN (0x02) - The certificate signature has been verified. If 1304 the certificate is self-signed and verified using the contained 1305 public key, this bit will lit when the CIS is constructed 1307 * VALD (0x04) - The certificate is valid and can be used to 1308 verify signatures. This bit is lit when a trusted certificate 1309 has been found on a valid certificate trail 1311 * PRIV (0x08) - The certificate is private and not to be 1312 revealed. If the certificate is self-signed and contains 1313 "Private" in the Extended Key Usage field, this bit will be lit 1314 when the CIS is constructed 1316 * ERRR (0x80) - The certificate is defective and not to be used 1317 in any way 1319 o Certificate List - CIS structures are stored on the certificate 1320 list in order of arrival, with the most recently received CIS 1321 placed first on the list. The list is initialized with the CIS 1322 for the host certificate, which is read from the certificate file. 1323 Additional CIS entries are pushed on the list as certificates are 1324 obtained from the servers during the certificate exchange. CIS 1325 entries are discarded if overtaken by newer ones or expire due to 1326 old age 1328 o Host Certificate - The self-signed X.509v3 certificate for the 1329 host. The subject and issuer fields consist of the host name, 1330 while the message digest/signature encryption scheme consists of 1331 the sign key and message digest defined above. Optional 1332 information used in the identity schemes is carried in X.509v3 1333 extension fields compatible with [11] 1335 o Public Key Values - The public encryption key for the COOKIE 1336 request, which consists of the public value of the host key. It 1337 carries the public values timestamp and the filestamp of the host 1338 key file 1340 o Leapseconds Table Values. The NIST leapseconds table from the 1341 NIST leapseconds file. It carries the public values timestamp and 1342 the filestamp of the leapseconds file 1344 10.3. Client State Variables (all modes) 1346 Following is a list of state variables used by the client association 1347 protocol in all modes. 1349 o Association ID - The association ID used in responses. It is 1350 assigned when the association is mobilized 1352 o Server Association ID - The server association ID used in 1353 requests. It is copied from the first nonzero association ID 1354 field in a response 1356 o Server Host Name - The server host name determined in the 1357 parameter exchange 1359 o Server Issuer Name - The host name signing the certificate. It is 1360 extracted from the current server certificate upon arrival and 1361 used to request the next item on the certificate trail 1363 o Association Status Word - The host status word of the server 1364 determined in the parameter exchange 1366 o Server Public Key - The public key used to decrypt signatures. It 1367 is extracted from the first certificate received, which by design 1368 is the server host certificate 1370 o Server Message Digest - The digest/signature scheme determined in 1371 the parameter exchange 1373 o Identification Challenge - A 512-bit nonce used in the 1374 identification exchange 1376 o Group Key - A set of values used by the identification exchange. 1377 It identifies the cryptographic compartment shared by the server 1378 and client 1380 o Receive Cookie Values - The cookie returned in a COOKIE response, 1381 together with its timestamp and filestamp 1383 o Receive Autokey Values - The autokey values returned in an AUTO 1384 response, together with its timestamp and filestamp 1386 o Receive Leapsecond Values - The leapsecond table returned by a 1387 LEAP response, together with its timestamp and filestamp 1389 10.4. Server State Variables (broadcast and symmetric modes) 1391 Following is a list of server state variables used in broadcast and 1392 symmetric modes. 1394 o Send Cookie Values - The cookie encryption values, signature and 1395 timestamps 1397 o Send Autokey Values - The autokey values, signature and timestamps 1399 o Key List - A sequence of key IDs starting with the autokey seed 1400 and each pointing to the next. It is computed, timestamped and 1401 signed at the next poll opportunity when the key list becomes 1402 empty 1404 o Current Key Number - The index of the entry on the Key List to be 1405 used at the next poll opportunity 1407 10.5. Autokey Protocol Messages 1409 There are currently eight Autokey requests and eight corresponding 1410 responses. The NTPv4 packet format is described in [1] and the 1411 extension field format used for these messages is illustrated in 1412 Figure 9. 1414 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 1415 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1416 | Field Type | Length | 1417 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1418 | Association ID | 1419 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1420 | Timestamp | 1421 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1422 | Filestamp | 1423 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1424 | Value Length | 1425 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1426 \ / 1427 / Value \ 1428 \ / 1429 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1430 | Signature Length | 1431 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1432 \ / 1433 / Signature \ 1434 \ / 1435 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1436 \ / 1437 / Padding (if needed) \ 1438 \ / 1439 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1441 Figure 9: NTPv4 Extension Field Format 1443 Each extension field is zero-padded to a 4-octet boundary. The 1444 Length field covers the entire extension field, including the Length 1445 and Padding fields. While the minimum field length is 8 octets, a 1446 maximum field length remains to be established. The reference 1447 implementation discards any packet with a total field length more 1448 than 1024 octets. 1450 If an extension field is present, the parser examines the Length 1451 field. If the length is less than 4 or not a multiple of 4, a format 1452 error has occurred and the packet MUST be discarded; otherwise, the 1453 parser increments the pointer by the length value. The parser now 1454 uses the same rules as above to determine whether a MAC is present 1455 and/or another extension field. 1457 The 8-bit Code field specifies the request or response operation, 1458 while the 4-bit Version Number (VN) field is 2 for the current 1459 protocol version. There are four flag bits: bit 0 is the Response 1460 Flag (R) and bit 1 is the Error Flag (E); the other two bits are 1461 presently unused and should be set to 0. The remaining fields will 1462 be described later. 1464 In the most common protocol operations, a client sends a request to a 1465 server with an operation code specified in the Code field and both 1466 the R bit and E bit dim. The Association ID field is set to the 1467 value previously received from the server or 0 otherwise. The server 1468 returns a response with the same operation code in the Code field and 1469 lights the R bit. The server can also light the E bit in case of 1470 error. The Association ID field is set to the association ID of the 1471 server as a handle for subsequent exchanges. If for some reason the 1472 association ID value in a request does not match the association ID 1473 of any mobilized association, the server returns the request with 1474 both the R and E bits lit. Note that it is not necessarily a 1475 protocol error to send an unsolicited response with no matching 1476 request. 1478 In some cases not all fields may be present. For requests, until a 1479 client has synchronized to a proventic source, signatures are not 1480 valid. In such cases the Timestamp and Signature Length fields are 0 1481 and the Signature field is empty. Responses are generated only when 1482 the responder has synchronized to a proventic source; otherwise, an 1483 empty response message is sent. Some request and error response 1484 messages carry no value or signature fields, so in these messages 1485 only the first two words are present. 1487 The Timestamp and Filestamp words carry the seconds field of an NTP 1488 timestamp. The Timestamp field establishes the signature epoch of 1489 the data field in the message, while the filestamp establishes the 1490 generation epoch of the file that ultimately produced the data that 1491 is signed. A signature and timestamp are valid only when the signing 1492 host is synchronized to a proventic source; otherwise, the timestamp 1493 is zero. A cryptographic data file can only be generated if a 1494 signature is possible; otherwise, the filestamp is zero, except in 1495 the ASSOC response message, where it contains the server status word. 1497 10.5.1. No-Operation 1499 A No-operation request (Field Type = 0) does nothing except return an 1500 empty reply which can be used as a crypto-ping. 1502 10.5.2. Association Message (ASSOC) 1504 An Association Message (Field Type = 1) is used in the parameter 1505 exchange to obtain the host name and related values. The request 1506 contains the host status word in the filestamp field. The response 1507 contains the server status word in the filestamp field and in 1508 addition the host name, which by default is the string returned by 1509 the Unix gethostname() library function. While minimum and maximum 1510 host name lengths remain to be established, the reference 1511 implementation uses the values 4 and 256, respectively. The 1512 remaining fields are defined previously in this report. 1514 If the server response is acceptable and both server and client share 1515 the same identity scheme, ENB is lit. When the PC identity scheme is 1516 in use, the ASSOC response lights VAL, IFF, and SIG, since the PC 1517 exchange is complete at this point. 1519 10.5.3. Certificate Message (CERT) 1521 A Certificate Message (Field Type = 2) is used in the certificate 1522 exchange to obtain a certificates and related values by subject name. 1523 The request contains the subject name. For the purposes of 1524 interoperability with older Autokey versions, if only the first two 1525 words are sent, the request is for the server host certificate. The 1526 response contains the certificate encoded in X.509 format with ASN.1 1527 syntax as described in Appendix E. 1529 If the subject name in the response does not match the issuer name, 1530 the exchange continues with the issuer name replacing the subject 1531 name in the request. The exchange continues until either the subject 1532 name matches the issuer name, indicating a self-signed certificate, 1533 or the trst bit is set in the CIS, indicating a trusted certificate. 1534 If a trusted certificate is found, the client stops the exchange and 1535 lights VAL. If a self-signed certificate is found but not trusted, 1536 the protocol loops at polite intervals until one is found or timeout. 1538 10.5.4. Cookie Message (COOKIE) 1540 The Cookie Message (Field Type = 3) is used in server and symmetric 1541 modes to obtain the server cookie. The request contains the host 1542 public key encoded with ASN.1 syntax as described in Appendix E. The 1543 response contains the cookie encrypted by the public key in the 1544 request. The signature and timestamps are determined when the cookie 1545 is encrypted. If the response is valid, the client lights CKY. 1547 10.5.5. Autokey Message (AUTO) 1549 The Autokey Message (Field Type = 4) is used to obtain the autokey 1550 values. The request contains no value. The response contains two 1551 32-bit words in network order. The first word is the final key ID, 1552 while the second is the index of the final key ID. The signature and 1553 timestamps are determined when the key list is generated. If the 1554 response is valid, the client lights AUT. 1556 10.5.6. Leapseconds Table Message (LEAP) 1558 The Leapseconds Table Message (Field Type = 5) is used to exchange 1559 leapseconds tables. The request and response messages have the same 1560 format, except that the R bit is dim in the request and lit in the 1561 response. Both the request and response contains the leapseconds 1562 table as parsed from the NIST leapseconds file. If the client 1563 already has a copy of the leapseconds data, it uses the one with the 1564 latest filestamp and discards the other. If the response is valid, 1565 the client lights LPT. 1567 10.5.7. Sign Message (SIGN) 1569 The Sign Message (Field Type = 6) requests the server to sign and 1570 return the certificate presented in the request. The request 1571 contains the client certificate encoded in X.509 format with ASN.1 1572 syntax as described in Appendix E. The response contains the client 1573 certificate signed by the server private key. If the certificate is 1574 valid when received by the host, it is linked in the certificate list 1575 and SGN is lit. 1577 10.5.8. Identity Messages (IFF, GQ, MV) 1579 The Identity Messages (Field Type = 7 (IFF), 8 (GQ), or 9 (MV)) 1580 contains the host challenge, usually a 160- or 512-bit nonce. The 1581 response contains the result of the mathematical operation defined in 1582 Appendix D. The Response is encoded in ASN.1 syntax as described in 1583 Appendix E. The response signature and timestamp are determined when 1584 the response is sent. If the response is valid, IFF is lit. 1586 10.6. Protocol State Transitions 1588 The protocol state machine is very simple but robust. The state is 1589 determined by the server status bits defined above. The state 1590 transitions of the three dances are shown below. The capitalized 1591 truth values represent the server status bits. All server bits are 1592 initialized dim and lit upon the arrival of a specific response 1593 message, as detailed above. 1595 When the system clock is first set and about once per day after that, 1596 or when the system clock is stepped, the server seed is refreshed, 1597 signatures and timestamps updated and the protocol restarted in all 1598 associations. When the server seed is refreshed or a new certificate 1599 or leapseconds table is received, the public values timestamp is 1600 reset to the current time and all signatures are recomputed. 1602 10.6.1. Server Dance 1604 The server dance begins when the host sends an ASSOC request to the 1605 server. It ends when the first signature is verified and PRV is lit. 1606 Subsequent packets received without extension fields are validated by 1607 the autokey sequence. An optional LEAP exchange updates the 1608 leapseconds table. Note the order of the identity exchanges and that 1609 only the first one will be used if multiple schemes are available. 1610 Note also that the SIGN and LEAP requests are not issued until the 1611 client has synchronized to a proventic source. 1613 while (1) { 1614 wait_for_next_poll; 1615 make_NTP_header; 1616 if (response_ready) 1617 send_response; 1618 if (!ENB) 1619 / * parameters exchange */ 1620 ASSOC_request; 1621 else if (!VAL) 1622 /* certificate exchange */ 1623 CERT_request(Host_Name); 1624 else if (IDN & GQ && !IFF) 1625 /* GQ identity exchange */ 1626 GQ_challenge; 1627 else if (IDN & IFF && !IFF) 1628 /* IFF identity exchange */ 1629 IFF_challenge; 1630 else if (!IFF) 1631 /* TC identity exchange */ 1632 CERT_request(Issuer_Name); 1633 else if (!CKY) 1634 /* cookie exchange */ 1635 COOKIE_request; 1636 else if (SYN && !SIG) 1637 /* signe exchange */ 1638 SIGN_request(Host_Certificate); 1639 else if (SYN && LPF & !LPT) 1640 /* leapseconds exchange */ 1641 LEAP_request; 1643 } 1645 When the PC identity scheme is in use, the ASSOC response lights VAL, 1646 IFF, and SIG; the COOKIE response lights CKY and AUT; and the first 1647 valid signature lights PRV. 1649 10.6.2. Broadcast Dance 1651 The only difference between the broadcast and server dances is the 1652 inclusion of an autokey values exchange following the cookie 1653 exchange. The broadcast dance begins when the host receives the 1654 first broadcast packet, which includes an ASSOC response with 1655 association ID. The host uses the association ID to initiate a 1656 server dance in order to calibrate the propagation delay. 1658 The dance ends when the first signature is verified and PRV is lit. 1659 Subsequent packets received without extension fields are validated by 1660 the autokey sequence. An optional LEAP exchange updates the 1661 leapseconds table. When the server generates a new key list, the 1662 server replaces the ASSOC response with an AUTO response in the first 1663 packet sent. 1665 while (1) { 1666 wait_for_next_poll; 1667 make_NTP_header; 1668 if (response_ready) 1669 send_response; 1670 if (!ENB) 1671 /* parameters exchange */ 1672 ASSOC_request; 1673 else if (!VAL) 1674 /* certificate exchange */ 1675 CERT_request(Host_Name); 1676 else if (IDN & GQ && !IFF) 1677 /* GQ identity exchange */ 1678 GQ_challenge; 1679 else if (IDN & IFF && !IFF) 1680 /* IFF identity exchange */ 1681 IFF_challenge; 1682 else if (!IFF) 1683 /* TC identity exchange */ 1684 CERT_request(Issuer_Name); 1685 else if (!CKY) 1686 /* cookie exchange */ 1687 COOKIE_request; 1688 else if (!AUT) 1689 /* autokey values exchange */ 1690 AUTO_request; 1691 else if (SYN &&! SIG) 1692 /* sign exchange */ 1693 SIGN_request(Host_Certificate); 1694 else if (SYN && LPF & !LPT) 1695 /* leapseconds exchange */ 1696 LEAP_request; 1698 } 1700 When the PC identity scheme is in use, the ASSOC response sets VAL, 1701 IFF, and SIG to 1; the COOKIE response sets CKY and AUT to 1; and the 1702 first valid signature set PRV to 1. 1704 10.6.3. Symmetric Dance 1706 The symmetric dance is intricately choreographed. It begins when the 1707 active peer sends an ASSOC request to the passive peer. The passive 1708 peer mobilizes an association and both peers step the same dance from 1709 the beginning. Until the active peer is synchronized to a proventic 1710 source (which could be the passive peer) and can sign messages, the 1711 passive peer loops waiting for the timestamp in the ASSOC response to 1712 be lit. Until then, the active peer dances the server steps, but 1713 skips the sign, cookie and leapseconds exchanges. 1715 while (1) { 1716 wait_for_next_poll; 1717 make_NTP_header; 1718 if (!ENB) 1719 /* parameters exchange */ 1720 ASSOC_request; 1721 else if (!VAL) 1722 /* certificate exchange */ 1723 CERT_request(Host_Name); 1724 else if (IDN & GQ && !IFF) 1725 /* GQ identity exchange */ 1726 GQ_challenge; 1727 else if (IDN & IFF && !IFF) 1728 /* IFF identity exchange */ 1729 IFF_challenge; 1730 else if (!IFF) 1731 /* TC identity exchange */ 1732 CERT_request(Issuer_Name); 1733 else if (SYN && !SIG) 1734 /* sign exchange */ 1735 SIGN_request(Host_Certificate); 1736 else if (SYN && !CKY) 1737 /* cookie exchange */ 1738 COOKIE_request; 1739 else if (!LST) 1740 /* autokey values response */ 1741 AUTO_response; 1742 else if (!AUT) 1743 /* autokey values exchange */ 1744 AUTO_request; 1745 else if (SYN && LPF & !LPT) 1746 /* leapseconds exchange */ 1747 LEAP_request; 1748 } 1750 When the PC identity scheme is in use, the ASSOC response lights VAL, 1751 IFF, and SIG; the COOKIE response lights CKY and AUT; and the first 1752 valid signature lights PRV. 1754 Once the active peer has synchronized to a proventic source, it 1755 includes timestamped signatures with its messages. The first thing 1756 it does after lighting timestamps is dance the sign exchange so that 1757 the passive peer can survive the default identity exchange, if 1758 necessary. This is pretty weird, since the passive peer will find 1759 the active certificate signed by its own public key. 1761 The passive peer, which has been stalled waiting for the active 1762 timestamps to be lit, now mates the dance. The initial value of the 1763 cookie is zero. If a COOKIE response has not been received by either 1764 peer, the next message sent is a COOKIE request. The recipient rolls 1765 a random cookie, lights CKY and returns the encrypted cookie. The 1766 recipient decrypts the cookie and lights CKY. It is not a protocol 1767 error if both peers happen to send a COOKIE request at the same time. 1768 In this case both peers will have two values, one generated by itself 1769 and the other received from the other peer. In such cases the 1770 working cookie is constructed as the EXOR of the two values. 1772 At the next packet transmission opportunity, either peer generates a 1773 new key list and lights LST; however, there may already be an AUTO 1774 request queued for transmission and the rules say no more than one 1775 request in a packet. When available, either peer sends an AUTO 1776 response and dims LST. The recipient initializes the autokey values 1777 and lights LST and AUT. Subsequent packets received without 1778 extension fields are validated by the autokey sequence. 1780 The above description assumes the active peer synchronizes to the 1781 passive peer, which itself is synchronized to some other source, such 1782 as a radio clock or another NTP server. In this case, the active 1783 peer is operating at a stratum level one greater than the passive 1784 peer and so the passive peer will not synchronize to it unless it 1785 loses its own sources and the active peer itself has another source. 1786 Various other intricate scenarios are possible. 1788 11. Error Recovery 1790 The Autokey protocol state machine includes provisions for various 1791 kinds of error conditions that can arise due to missing files, 1792 corrupted data, protocol violations and packet loss or misorder, not 1793 to mention hostile intrusion. This section describes how the 1794 protocol responds to reachability and timeout events which can occur 1795 due to such errors. Appendix B contains an extended discussion on 1796 error checking and timestamp validation. 1798 A persistent NTP association is mobilized by an entry in the 1799 configuration file, while an ephemeral association is mobilized upon 1800 the arrival of a broadcast, manycast or symmetric active packet with 1801 no matching association. If necessary, a general reset reinitializes 1802 all association variables to the initial state when first mobilized. 1803 In addition, if the association is ephemeral, the association is 1804 demobilized and all resources acquired are returned to the system. 1806 Every NTP association has two variables which maintain the liveness 1807 state of the protocol, the 8-bit reachability register defined in [8] 1808 and the watchdog timer, which is new in NTPv4. At every poll 1809 interval the reachability register is shifted left, the low order bit 1810 is dimmed and the high order bit is lost. At the same time the 1811 watchdog counter is incremented by one. If an arriving packet passes 1812 all authentication and sanity checks, the rightmost bit of the 1813 reachability register is lit and the watchdog counter is set to zero. 1814 If any bit in the reachability register is lit, the server is 1815 reachable, otherwise it is unreachable. 1817 When the first poll is sent from an association, the reachability 1818 register and watchdog counter are zero. If the watchdog counter 1819 reaches a preset threshold before the server becomes reachable, a 1820 general reset occurs. This resets the protocol and clears any 1821 acquired resources before trying again. If the association is 1822 ephemerable, it is demobilized; otherwise, the poll interval is 1823 doubled. This reduces the network load for packets that are unlikely 1824 to elicit a response. 1826 At each state in the protocol the client expects a particular 1827 response from the server. A request is included in the NTP packet 1828 sent at each poll interval until a valid response is received or a 1829 general reset occurs, in which case the protocol restarts from the 1830 beginning. A general reset also occurs for an association when an 1831 unrecoverable protocol error occurs. A general reset occurs for all 1832 associations when the system clock is first synchronized or the clock 1833 is stepped or when the server seed is refreshed. 1835 There are special cases designed to quickly respond to broken 1836 associations, such as when a server restarts or refreshes keys. 1837 Since the client cookie is invalidated, the server rejects the next 1838 client request and returns a crypto-NAK packet. A cryoti-NAK packet 1839 has a runt MAC with a key ID of zero and no message digest. The 1840 problem for the host is to determine whether it is legitimate or the 1841 result of intruder mischief. This is done using the NTPv4 on-wire 1842 protocol, which requites the crypto-NAK, as well as all responses, to 1843 be believed only if the result of a previous packet sent by the host 1844 and not a replay, as confirmed by the LBK and DUP status bits 1845 described above. While this defense can be easily circumvented by a 1846 middleman, it does deflect other kinds of intruder warfare. 1848 There are a number of situations where some event happens that causes 1849 the remaining autokeys on the key list to become invalid. When one 1850 of these situations happens, the key list and associated autokeys in 1851 the key cache are purged. A new key list, signature and timestamp 1852 are generated when the next NTP message is sent, assuming there is 1853 one. Following is a list of these situations: 1855 1. When the cookie value changes for any reason. 1857 2. When a client switches from client mode to broadcast client mode. 1858 There is no further need for the key list, since the client will 1859 not transmit again. 1861 3. When the poll interval is changed. In this case the calculated 1862 expiration times for the keys become invalid. 1864 4. If a problem is detected when an entry is fetched from the key 1865 list. This could happen if the key was marked non-trusted or 1866 timed out, either of which implies a software bug. 1868 12. Security Considerations 1870 This section discusses the most obvious security vulnerabilities in 1871 the various Autokey dances. First, some observations on the 1872 particular engineering parameters of the Autokey protocol are in 1873 order. The number of bits in some cryptographic values are 1874 considerably smaller than would ordinarily be expected for strong 1875 cryptography. One of the reasons for this is the need for 1876 compatibility with previous NTP versions; another is the need for 1877 small and constant latencies and minimal processing requirements. 1878 Therefore, what the scheme gives up on the strength of these values 1879 must be regained by agility in the rate of change of the 1880 cryptographic basis values. Thus, autokeys are used only once and 1881 seed values are regenerated frequently. However, in most cases even 1882 a successful cryptanalysis of these values compromises only a 1883 particular association and does not represent a danger to the general 1884 population. 1886 Throughout the following discussion the cryptographic algorithms and 1887 private values themselves are assumed secure; that is, a brute force 1888 cryptanalytic attack will not reveal the host private key, sign 1889 private key, cookie value, identity parameters, server seed or 1890 autokey seed. In addition, an intruder will not be able to predict 1891 random generator values or predict the next autokey. On the other 1892 hand, the intruder can remember the totality of all past values for 1893 all packets ever sent. Ordinarily, the timestamp/filestamp 1894 provisions will make such possesions unusable. 1896 12.1. Protocol Vulnerability 1898 While the protocol has not been subjected to a formal analysis, a few 1899 preliminary assertions can be made. The protocol cannot loop forever 1900 in any state, since the watchdog counter and general reset insure 1901 that the association variables will eventually be purged and the 1902 protocol restarted from the beginning. However, if something is 1903 seriously wrong, the timeout/restart cycle could continue 1904 indefinitely until whatever is wrong is fixed. This is not a 1905 clogging hazard, as the timeout period is very long compared to 1906 expected network delays. 1908 The LBK and DUP bits described in the main body and Appendix B are 1909 effective whether or not cryptographic means are in use. The DUP bit 1910 deflects duplicate packets in any mode, while the LBK bit deflects 1911 bogus packets in all except broadcast mode. All packets must have 1912 the correct MAC, as verified with correct key ID and cookie. In all 1913 modes the next key ID cannot be predicted by a wiretapper, so are of 1914 no use for cryptanalysis. 1916 As long as the client has validated the server certificate trail, a 1917 wiretapper cannot produce a convincing signature and cannot produce 1918 cryptographic values acceptable to the client. As long as the 1919 identity values are not compromised, a middleman cannot masquerade as 1920 a legitimate group member and produce convincing certificates or 1921 signatures. In server and symmetric modes after the preliminary 1922 exchanges have concluded, extension fields are no longer used, a 1923 client validates the packet using the autokey sequence. A wiretapper 1924 cannot predict the next Key IDs, so cannot produce a valid MAC. A 1925 middleman cannot successfully modify and replay a message, since he 1926 does not know the cookie and without the cookie cannot produce a 1927 valid MAC. 1929 In broadcast mode a wiretapper cannot produce a key list with signed 1930 autokey values that a client will accept. The most it can do is 1931 replay an old packet causing clients to repeat the autokey hash 1932 operations until exceeding the maximum key number. However, a 1933 middleman could intercept an otherwise valid broadcast packet and 1934 produce a bogus packet with acceptable MAC, since in this case it 1935 knows the key ID before the clients do. Of course, the middleman key 1936 list would eventually be used up and clients would discover the ruse 1937 when verifying the signature of the autokey values. There does not 1938 seem to be a suitable defense against this attack. 1940 During the exchanges where extension fields are in use, the cookie is 1941 a public value rather than a shared secret and an intruder can easily 1942 construct a packet with a valid MAC, but not a valid signature. In 1943 the certificate and identity exchanges an intruder can generate fake 1944 request messages which may evade server detection; however, the LBK 1945 and DUP bits minimize the client exposure to the resulting rogue 1946 responses. A wiretapper might be able to intercept a request, 1947 manufacture a fake response and loft it swiftly to the client before 1948 the real server response. A middleman could do this without even 1949 being swift. However, once the identity exchange has completed and 1950 the PRV bit lit, these attacks are readily deflected. 1952 A client instantiates cryptographic variables only if the server is 1953 synchronized to a proventic source. A server does not sign values or 1954 generate cryptographic data files unless synchronized to a proventic 1955 source. This raises an interesting issue: how does a client generate 1956 proventic cryptographic files before it has ever been synchronized to 1957 a proventic source? [Who shaves the barber if the barber shaves 1958 everybody in town who does not shave himself?] In principle, this 1959 paradox is resolved by assuming the primary (stratum 1) servers are 1960 proventicated by external phenomenological means. 1962 There is a significant vulnerability in the underlying NTP on-wire 1963 protocol. Until confirming the first exchange when a host first 1964 comes up, an intruder can replay an old message, which cause the LBK 1965 and DUP bits to be reset. If the intruder does this repeatedly, the 1966 host may never synchronize. This vulnerability is the same as with 1967 TCP. 1969 12.2. Clogging Vulnerability 1971 There are two clogging vulnerabilities exposed in the protocol 1972 design: an encryption attack where the intruder hopes to clog the 1973 victim server with needless cookie or signature encryptions or 1974 identity calculations, and a decryption attack where the intruder 1975 attempts to clog the victim client with needless cookie or 1976 verification decryptions. Autokey uses public key cryptography and 1977 the algorithms that perform these functions consume significant 1978 processor resources. 1980 In order to reduce exposure to decryption attacks the LBK and DUP 1981 bits deflect bogus and replayed packets before invoking any 1982 cryptographic operations. In order to reduce exposure to encryption 1983 attacks, signatures are computed only when the data have changed. 1984 For instance, the autokey values are signed only when the key list is 1985 regenerated, which happens about once an hour, while the public 1986 values are signed only when one of them changes or the server seed is 1987 refreshed, which happens about once per day. 1989 In some Autokey dances the protocol precludes server state variables 1990 on behalf of an individual client, so a request message must be 1991 processed and the response message sent without delay. The identity, 1992 cookie and sign exchanges are particularly vulnerable to a clogging 1993 attack, since these exchanges can involve expensive cryptographic 1994 algorithms as well as digital signatures. A determined intruder 1995 could replay identity, cookie or sign requests at high rate, which 1996 may very well be a useful munition for an encryption attack. 1997 Ordinarily, these requests are seldom used, except when the protocol 1998 is restarted or the server seed or public values are refreshed. 2000 Once synchronized to a proventic source, a legitimate extension field 2001 with timestamp the same as or earlier than the most recent received 2002 of that type is immediately discarded. This foils a middleman cut- 2003 and-paste attack using an earlier AUTO response, for example. A 2004 legitimate extension field with timestamp in the future is unlikely, 2005 as that would require predicting the autokey sequence. In either 2006 case the extension field is discarded before expensive signature 2007 computations. This defense is most useful in symmetric mode, but a 2008 useful redundancy in other modes. 2010 The client is vulnerable to a certificate clogging attack until 2011 declared proventic, after which CERT responses are discarded. Before 2012 that, a determined intruder could flood the client with bogus 2013 certificate responses and force spurious signature verifications, 2014 which of course would fail. The intruder could flood the server with 2015 bogus certificate requests and cause similar mischief. Once declared 2016 proventic, further certificate responses are discard, so these 2017 attacks would fail. The intruder could flood the server with 2018 replayed sign requests and cause the server to verify the request and 2019 sign the response, although the client would drop the response due 2020 invalid timestamp. 2022 An interesting adventure is when an intruder replays a recent packet 2023 with an intentional bit error. A stateless server will return a 2024 crypto-NAK message which the client will notice and discard, since 2025 the LBK bit is lit. However, a legitimate crypto-NAK is sent if the 2026 server has just refreshed the server seed. In this case the LBK bit 2027 is dim and the client performs a general reset and restarts the 2028 protocol as expected. Another adventure is to replay broadcast mode 2029 packets at high rate. These will be rejected by the clients by the 2030 timestamp check and before consuming signature cycles. 2032 In broadcast and symmetric modes the client must include the 2033 association ID in the AUTO request. Since association ID values for 2034 different invocations of the NTP daemon are randomized over the 16- 2035 bit space, it is unlikely that a bogus request would match a valid 2036 association with different IP addresses, for example, and cause 2037 confusion. 2039 13. IANA Considerations 2041 Any IANA registries needed? 2043 14. Acknowledgements 2045 ... 2047 15. References 2049 15.1. Normative References 2051 [1] Burbank, J., "Network Time Protocol Version 4 Protocol And 2052 Algorithms Specification", draft-ietf-ntp-ntpv4-proto-07 (work 2053 in progress), July 2007. 2055 15.2. Informative References 2057 [2] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol", 2058 RFC 4306, December 2005. 2060 [3] Orman, H., "The OAKLEY Key Determination Protocol", RFC 2412, 2061 November 1998. 2063 [4] Karn, P. and W. Simpson, "Photuris: Session-Key Management 2064 Protocol", RFC 2522, March 1999. 2066 [5] Bradner, S., "Key words for use in RFCs to Indicate Requirement 2067 Levels", BCP 14, RFC 2119, March 1997. 2069 [6] Kent, S., "IP Encapsulating Security Payload (ESP)", RFC 4303, 2070 December 2005. 2072 [7] Kent, S., "IP Authentication Header", RFC 4302, December 2005. 2074 [8] Mills, D., "Network Time Protocol (Version 3) Specification, 2075 Implementation", RFC 1305, March 1992. 2077 [9] Prafullchandra, H. and J. Schaad, "Diffie-Hellman Proof-of- 2078 Possession Algorithms", RFC 2875, July 2000. 2080 [10] Adams, C., Farrell, S., Kause, T., and T. Mononen, "Internet 2081 X.509 Public Key Infrastructure Certificate Management Protocol 2082 (CMP)", RFC 4210, September 2005. 2084 [11] Housley, R., Polk, W., Ford, W., and D. Solo, "Internet X.509 2085 Public Key Infrastructure Certificate and Certificate 2086 Revocation List (CRL) Profile", RFC 3280, April 2002. 2088 [12] Schnorr, C., "Efficient signature generation for smart cards", 2089 1991. 2091 [13] Stinson, D., "Cryptography - Theory and Practice", 1995. 2093 [14] Guillou, L. and J. Quisquatar, "A "paradoxical" identity-based 2094 signature scheme resulting from zero-knowledge", 1990. 2096 [15] Mu, Y. and V. Varadharajan, "Robust and secure broadcasting", 2097 2001. 2099 [16] Bassham, L., Polk, W., and R. Housley, "Algorithms and 2100 Identifiers for the Internet X.509 Public Key Infrastructure 2101 Certificate and Certificate Revocation List (CRL) Profile", 2102 RFC 3279, April 2002. 2104 Appendix A. Cryptographic Key and Certificate Management 2106 This appendix describes how cryptographic keys and certificates are 2107 generated and managed in the NTPv4 reference implementation. These 2108 means are not intended to become part of any standard that may be 2109 evolved from this report, but to serve as an example of how these 2110 functions can be implemented and managed in a typical operational 2111 environment. 2113 The ntp-keygen utility program in the NTPv4 software library 2114 generates public/private key files, certificate files and identity 2115 key/parameter files. By default the modulus of all encryption and 2116 identity keys is 512 bits. All random cryptographic data are based 2117 on a pseudo-random number generator seeded in such a way that random 2118 values are exceedingly unlikely to repeat. The files are in ASN.1 2119 format, encrypted is necessary, then PEM encoded in printable ASCII 2120 format suitable for mailing as MIME objects. 2122 Every file has a filestamp, which is a string of decimal digits 2123 representing the NTP seconds when the file was created. The file 2124 name is formed from the concatenation of the host name, filestamp and 2125 constant strings, so files can be copied from one environment to 2126 another while preserving the original filestamp. The file header 2127 includes the file name and date and generation time in printable 2128 ASCII. The utility assumes the host is synchronized to a proventic 2129 source at the time of generation, so that filestamps are proventic 2130 data. This raises an interesting circularity issue that will not be 2131 further explored here. 2133 The generated files are typically stored in NFS mounted file systems, 2134 with files containing private keys obscured to all but root. 2135 Symbolic links are installed from default file names assumed by the 2136 NTP daemon to the selected files. Since the files of successive 2137 generations and different hosts have unique names, there is no 2138 possibility of name collisions. 2140 Public/private host and sign keys and certificates must be generated 2141 by the host to which they belong. The host key must be RSA, since it 2142 is used to encrypt the cookie, as well as encrypt signatures by 2143 default. The optional sign key can be RSA or DSA, since it is used 2144 only to encrypt signatures. In principle, certificates could be 2145 generated directly by OpenSSL utility programs, as long as the 2146 symbolic links are consistent. 2148 Identity keys and parameters must be generated by the ntp-keygen 2149 utility, since they have proprietary formats. Since these are 2150 private to the group, they are generated by one host acting as a 2151 trusted authority and then distributed to all other members of the 2152 group by secure means. 2154 Certificates are usually, but not necessarily, generated by the host 2155 to which they belong. The ntp-keygen utility generates self-signed 2156 X.509v3 host certificate files with optional extension fields. 2157 Certificate requests are not used, since the certificate itself is 2158 used as a request to be signed. OpenSSL X.509v3 certificates are 2159 generated as an OpenSSL structure, which is then PEM encoded in ASN.1 2160 syntax and written to the host certificate file. The string returned 2161 by the Unix gethostname() routine is used by default for both the 2162 subject and issuer fields. The serial number and begin time fields 2163 are derived from the filestamp; the end time is one year hence. The 2164 host certificate is signed by the sign key or host key if a sign key 2165 is not present. 2167 An important design goal is to make cryptographic data refreshment as 2168 simple and intuitive as possible, so it can be driven by scripts on a 2169 periodic basis. When the ntp-keygen utility is run for the first 2170 time, it creates by default a RSA host key file and RSA-MD5 host 2171 certificate file and necessary symbolic links. After that, it 2172 creates a new certificate file and symbolic link using the existing 2173 host key. The program run with given options creates identity key/ 2174 parameter files for one or more IFF, GQ or MV identity schemes. The 2175 key files must then be securely copied to all other group members and 2176 symbolic links installed from the default names to the installed 2177 files. In the GQ scheme the next and each subsequent time the ntp- 2178 keygen utility runs, it automatically creates or updates the private/ 2179 public identity key files and certificate file using the existing 2180 identity parameters. 2182 Appendix B. Autokey Error Checking 2184 Exhaustive examination of possible vulnerabilities at the various 2185 processing steps of the NTPv3 protocol as specified in [8] have 2186 resulted in a revised list of packet sanity tests. There are 12 2187 tests in the NTPv4 reference implementation, called TEST1 through 2188 TEST12, which are performed in a specific order designed to gain 2189 maximum diagnostic information while protecting against an accidental 2190 or malicious clogging attacks. These tests are described in detail 2191 in the NTP software documentation. Those relevant to the Autokey 2192 protocol are described in this appendix. 2194 The sanity tests are classified in four tiers. The first tier 2195 deflects access control and message digest violations. The second, 2196 represented by the autokey sequence, deflects spoofed or replayed 2197 packets. The third, represented by timestamped digital signatures, 2198 binds cryptographic values to verifiable credentials. The fourth 2199 deflects packets with invalid NTP header fields or out of bounds time 2200 values. However, the tests in this last group do not directly affect 2201 cryptographic protocol vulnerability, so are beyond the scope of 2202 discussion here. 2204 B.1. Packet Processing Rules 2206 Every arriving NTP packet is checked enthusiastically for format, 2207 content and protocol errors. Some packet header fields are checked 2208 by the main NTP code path both before and after the Autokey protocol 2209 engine cranks. These include the NTP version number, overall packet 2210 length and extension field lengths. The total length of all 2211 extension fields may be no longer than 1024 octets in the reference 2212 implementation. Packets failing any of these checks are discarded 2213 immediately. Packets denied by the access control mechanism will be 2214 discarded later, but processing continues temporarily in order to 2215 gather further information useful for error recovery and reporting. 2217 Next, the cookie and session key are determined and the MAC computed 2218 as described above. If the MAC fails to match the value included in 2219 the packet, the action depends on the mode and the type of packet. 2220 Packets failing the MAC check will be discarded later, but processing 2221 continues temporarily in order to gather further information useful 2222 for error recovery and reporting. 2224 The NTP transmit and receive timestamps are in effect nonces, since 2225 an intruder cannot effectively guess either value in advance. To 2226 minimize the possibility that an intruder can guess the nonces, the 2227 low order unused bits in all timestamps are obscured with random 2228 values. If the transmit timestamp matches the transmit timestamp in 2229 the last packet received, the packet is a duplicate, so the DUP bit 2230 is lit. If the packet mode is not broadcast and the last transmit 2231 timestamp does not match the originate timestamp in the packet, 2232 either it was delivered out of order or an intruder has injected a 2233 rogue packet, so the LBK bit is lit. Packets with either the DUP or 2234 LBK bit will be discarded later, but processing continues temporarily 2235 in order to gather further information useful for error recovery and 2236 reporting. 2238 Further indicators of the server and client state are apparent from 2239 the transmit and receive timestamps of both the packet and the 2240 association. The quite intricate rules take into account these and 2241 the above error indicators They are designed to discriminate between 2242 legitimate cases where the server or client are in inconsistent 2243 states and recoverable, and when an intruder is trying to destabilize 2244 the protocol or force consumption of needless resources. The exact 2245 behavior is beyond the scope of discussion, but is clearly described 2246 in the source code documentation. 2248 Next, the Autokey protocol engine is cranked and the dances evolve as 2249 described above. Some requests and all responses have value fields 2250 which carry timestamps and filestamps. When the server or client is 2251 synchronized to a proventic source, most requests and responses with 2252 value fields carry signatures with valid timestamps. When not 2253 synchronized to a proventic source, value fields carry an invalid 2254 (zero) timestamp and the signature field and signature length word 2255 are omitted. 2257 The extension field parser checks that the Autokey version number, 2258 operation code and field length are valid. If the error bit is lit 2259 in a request, the request is discarded without response; if an error 2260 is discovered in processing the request, or if the responder is not 2261 synchronized to a proventic source, the response contains only the 2262 first two words of the request with the response and error bits lit. 2263 For messages with signatures, the parser requires that timestamps and 2264 filestamps are valid and not a replay, that the signature length 2265 matches the certificate public key length and only then verifies the 2266 signature. Errors are reported via the security logging facility. 2268 All certificates must have correct ASN.1 encoding, supported digest/ 2269 signature scheme and valid subject, issuer, public key and, for self- 2270 signed certificates, valid signature. While the begin and end times 2271 can be checked relative to the filestamp and each other, whether the 2272 certificate is valid relative to the actual time cannot be determined 2273 until the client is synchronized to a proventic source and the 2274 certificate is signed and verified by the server. 2276 When the protocol starts the only response accepted is ASSOC with 2277 valid timestamp, after which the server status word must be nonzero. 2278 ASSOC responses are discarded if this word is nonzero. The only 2279 responses accepted after that and until the PRV bit is lit are CERT, 2280 IFF and GQ. Once identity is confirmed and IFF is lit, these 2281 responses are no longer accepted, but all other responses are 2282 accepted only if in response to a previously sent request and only in 2283 the order prescribed in the protocol dances. Additional checks are 2284 implemented for each request type and dance step. 2286 B.2. Timestamps, Filestamps and Partial Ordering 2288 When the host starts, it reads the host key and certificate files, 2289 which are required for continued operation. It also reads the sign 2290 key and leapseconds file, when available. When reading these files 2291 the host checks the file formats and filestamps for validity; for 2292 instance, all filestamps must be later than the time the UTC 2293 timescale was established in 1972 and the certificate filestamp must 2294 not be earlier than its associated sign key filestamp. In general, 2295 at the time the files are read, the host is not synchronized, so it 2296 cannot determine whether the filestamps are bogus other than these 2297 simple checks. 2299 In the following the relation A --> B is Lamport's "happens before" 2300 relation, which is true if event A happens before event B. When 2301 timestamps are compared to timestamps, the relation is false if A 2302 <--> B; that is, false if the events are simultaneous. For 2303 timestamps compared to filestamps and filestamps compared to 2304 filestamps, the relation is true if A <--> B. Note that the current 2305 time plays no part in these assertions except in (6) below; however, 2306 the NTP protocol itself insures a correct partial ordering for all 2307 current time values. 2309 The following assertions apply to all relevant responses: 2311 1. The client saves the most recent timestamp T0 and filestamp F0 2312 for the respective signature type. For every received message 2313 carrying timestamp T1 and filestamp F1, the message is discarded 2314 unless T0 --> T1 and F0 --> F1. The requirement that T0 --> T1 2315 is the primary defense against replays of old messages. 2317 2. For timestamp T and filestamp F, F --> T; that is, the filestamp 2318 must happen before the timestamp. If not, this could be due to a 2319 file generation error or a significant error in the system clock 2320 time. 2322 3. For sign key filestamp S, certificate filestamp C, cookie 2323 timestamp D and autokey timestamp A, S --> C --> D --> A; that 2324 is, the autokey must be generated after the cookie, the cookie 2325 after the certificate and the certificate after the sign key. 2327 4. For sign key filestamp S and certificate filestamp C specifying 2328 begin time B and end time E, S --> C--> B --> E; that is, the 2329 valid period must not be retroactive. 2331 5. A certificate for subject S signed by issuer I and with filestamp 2332 C1 obsoletes, but does not necessarily invalidate, another 2333 certificate with the same subject and issuer but with filestamp 2334 C0, where C0 --> C1. 2336 6. A certificate with begin time B and end time E is invalid and can 2337 not be used to verify signatures if t --> B or E --> t, where t 2338 is the current proventic time. Note that the public key 2339 previously extracted from the certificate continues to be valid 2340 for an indefinite time. This raises the interesting possibility 2341 where a truechimer server with expired certificate or a 2342 falseticker with valid certificate are not detected until the 2343 client has synchronized to a clique of proventic truechimers. 2345 Appendix C. Certificates 2347 Certificate extension fields are used to convey information used by 2348 the identity schemes, such as whether the certificate is private, 2349 trusted or contains a public identity key. While the semantics of 2350 these fields generally conforms with conventional usage, there are 2351 subtle variations. The fields used by Autokey Version 2 include: 2353 o Basic Constraints. This field defines the basic functions of the 2354 certificate. It contains the string "critical,CA:TRUE", which 2355 means the field must be interpreted and the associated private key 2356 can be used to sign other certificates. While included for 2357 compatibility, Autokey makes no use of this field. 2359 o Key Usage. This field defines the intended use of the public key 2360 contained in the certificate. It contains the string 2361 "digitalSignature,keyCertSign", which means the contained public 2362 key can be used to verify signatures on data and other 2363 certificates. While included for compatibility, Autokey makes no 2364 use of this field. 2366 o Extended Key Usage. This field further refines the intended use 2367 of the public key contained in the certificate and is present only 2368 in self-signed certificates. It contains the string "Private" if 2369 the certificate is designated private or the string "trustRoot" if 2370 it is designated trusted. A private certificate is always 2371 trusted. 2373 o Subject Key Identifier. This field contains the public identity 2374 key used in the GQ identity scheme. It is present only if the GQ 2375 scheme is configured. 2377 Appendix D. Identity Schemes 2379 The Internet infrastructure model described in [10] is based on 2380 certificate trails where a subject proves identity to a certificate 2381 authority (CA) who then signs the subject certificate using the CA 2382 issuer key. The CA in turn proves identity to the next CA and 2383 obtains its own signed certificate. The trail continues to a CA with 2384 a self-signed trusted root certificate independently validated by 2385 other means. If it is possible to prove identity at each step, each 2386 certificate along the trail can be considered trusted relative to the 2387 identity scheme and trusted root certificate. 2389 The important issue with respect to NTP is the cryptographic strength 2390 of the identity scheme, since if a middleman could compromise it, the 2391 trail would have a security breach. In electric mail and commerce 2392 the identity scheme can be based on handwritten signatures, 2393 photographs, fingerprints and other things very hard to counterfeit. 2394 As applied to NTP subnets and identity proofs, the scheme must allow 2395 a client to securely verify that a server knows the same secret that 2396 it does, presuming the secret was previously instantiated by secure 2397 means, but without revealing the secret to members outside the group. 2399 While the identity scheme described in RFC-2875 [9] is based on a 2400 ubiquitous Diffie-Hellman infrastructure, it is expensive to generate 2401 and use when compared to others described in this appendix. There 2402 are five schemes now implemented in the NTPv4 reference 2403 implementation to prove identity: (1) private certificate (PC), (2) 2404 trusted certificate (TC), (3) a modified Schnorr algorithm (IFF aka 2405 Identify Friendly or Foe), (4) a modified Guillou-Quisquater 2406 algorithm (GQ), and (5) a modified Mu-Varadharajan algorithm (MV). 2407 The available schemes are selected during the key generation phase, 2408 with the particular scheme selected during the parameter exchange. 2410 The IFF, GQ and MV schemes involve a cryptographically strong 2411 challenge-response exchange where an intruder cannot learn the group 2412 key, even after repeated observations of multiple exchanges. These 2413 schemes begin when the client sends a nonce to the server, which then 2414 rolls its own nonce, performs a mathematical operation and sends the 2415 results along with a message digest to the client. The client 2416 performs a second mathematical operation to produce a digest that 2417 must match the one included in the message. To the extent that a 2418 server can prove identity to a client without either knowing the 2419 group key, a scheme is properly described as a zero-knowledge proof. 2421 D.1. Private Certificate (PC) Scheme 2423 The PC scheme shown in Figure Figure 13 involves the use of a private 2424 certificate as group key. A certificate is designated private by a 2425 X509 Version 3 extension field when generated by utility routines in 2426 the NTP software distribution. The certificate is distributed to all 2427 other group members by secure means and is never revealed outside the 2428 group. A client is marked trusted in the Parameter Exchange and 2429 authentic when the first signature is verified. This scheme is 2430 cryptographically strong as long as the private certificate is 2431 protected; however, it can be very awkward to refresh the keys or 2432 certificate, since new values must be securely distributed to a 2433 possibly large population and activated simultaneously. 2435 Trusted 2436 Authority 2437 Secure +-------------+ Secure 2438 +--------------| Certificate |-------------+ 2439 | +-------------+ | 2440 | | 2441 \|/ \|/ 2442 +-------------+ +-------------+ 2443 | Certificate | | Certificate | 2444 +-------------+ +-------------+ 2445 Server Client 2447 Figure 13: Private Certificate (PC) Identity Scheme 2449 The PC scheme uses a private certificate as group key. A certificate 2450 is designated private for the purpose of the this scheme if the CIS 2451 Private bit is lit. The certificate is distributed to all other 2452 group members by secret means and never revealed outside the group. 2453 There is no identity exchange, since the certificate itself is the 2454 group key. Therefore, when the parameter exchange completes the VAL, 2455 IFF and SGN bits are lit in the server status word. When the 2456 following cookie exchange is complete, the PRV bit is lit and 2457 operation continues as described in the main body of this report. 2459 D.2. Trusted Certificate (TC) Scheme 2461 All other schemes involve a conventional certificate trail as shown 2462 in Figure Figure 14. As described in RFC-4210 [10], each certificate 2463 is signed by an issuer one step closer to the trusted host, which has 2464 a self-signed trusted certificate, A certificate is designated 2465 trusted by a X509 Version 3 extension field when generated by utility 2466 routines in the NTP software distribution. A host obtains the 2467 certificates of all other hosts along the trail leading to a trusted 2468 host by the Autokey protocol, then requests the immediately ascendant 2469 host to sign its certificate. Subsequently, these certificates are 2470 provided to descendent hosts by the Autokey protocol. In this scheme 2471 keys and certificates can be refreshed at any time, but a masquerade 2472 vulnerability remains unless a request to sign a client certificate 2473 is validated by some means such as reverse-DNS. If no specific 2474 identity scheme is specified in the Identification Exchange, this is 2475 the default TC scheme. 2477 Trusted 2478 Host Host Host 2479 +-----------+ +-----------+ +-----------+ 2480 +--->| Subject | +--->| Subject | +--->| Subject | 2481 | +-----------+ | +-----------+ | +-----------+ 2482 ...---+ | Issuer |---+ | Issuer |---+ | Issuer | 2483 +-----------+ +-----------+ +-----------+ 2484 | Signature | | Signature | | Signature | 2485 +-----------+ +-----------+ +-----------+ 2487 Figure 14: Private Certificate (PC) Identity Scheme 2489 The TC identification exchange follows the parameter exchange in 2490 which the VAL bit is lit. It involves a conventional certificate 2491 trail and a sequence of certificates, each signed by an issuer one 2492 stratum level lower than the client, and terminating at a trusted 2493 certificate, as described in [10]. A certificate is designated 2494 trusted for the purpose of the TC scheme if the CIS Trust bit is lit 2495 and the certificate is self-signed. Such would normally be the case 2496 when the trail ends at a primary (stratum 1) server, but the trail 2497 can end at a secondary server if the security model permits this. 2499 When a certificate is obtained from a server, or when a certificate 2500 is signed by a server, A CIS for the new certificate is pushed on the 2501 certificate list, but only if the certificate filestamp is greater 2502 than any with the same subject name and issuer name already on the 2503 list. The list is then scanned looking for signature opportunities. 2504 If a CIS issuer name matches the subject name of another CIS and the 2505 issuer certificate is verified using the public key of the subject 2506 certificate, the CIS Sign bit is lit in the issuer CIS. Furthermore, 2507 if the Trust bit is lit in the subject CIS, the Trust bit is lit in 2508 the issuer CIS. 2510 The client continues to follow the certificate trail to a self-signed 2511 certificate, lighting the Sign and Trust bits as it proceeds. If it 2512 finds a self-signed certificate with Trust bit lit, the client lights 2513 the IFF and PRV bits and the exchange completes. It can, however, 2514 happen that the client finds a self-signed certificate with Trust bit 2515 dark. This can happen when a server is just coming up, has 2516 synchronized to a proventic source, but has not yet completed the 2517 Sign exchange. This is considered a temporary condition, so the 2518 client simply retries at poll opportunities until the server 2519 certificate is signed. 2521 D.3. Schnorr (IFF) Scheme 2523 The Schnorr (IFF) identity scheme is useful when certificates are 2524 generated by means other than the NTP software library, such as a 2525 trusted public authority. In this case a X.509v3 extension field 2526 might not be available to convey the identity public key. The scheme 2527 involves a set of parameters which persist for the life of the 2528 scheme. New generations of these parameters must be securely 2529 transmitted to all members of the group before use. The scheme is 2530 self contained and independent of new generations of host keys, sign 2531 keys and certificates. 2533 Certificates can be generated by the OpenSSL library or an external 2534 public certificate authority, but conveying an arbitrary public value 2535 in a certificate extension field might not be possible. The TA 2536 generates IFF parameters and keys and distributes them by secure 2537 means to all servers, then removes the group key and redistributes 2538 these data to dependent clients. Without the group key a client 2539 cannot masquerade as a legitimate server. 2541 The IFF parameters are generated by OpenSSL routines normally used to 2542 generate DSA keys. By happy coincidence, the mathematical principles 2543 on which IFF is based are similar to DSA, but only the moduli p, q 2544 and generator g are used in identity calculations. The parameters 2545 hide in a DSA cuckoo structure and use the same members. The values 2546 are used by an identity scheme based on DSA cryptography and 2547 described in [12] and [13] p. 285. The p is a 512-bit prime, g a 2548 generator of the multiplicative group Zp* and q a 160-bit prime that 2549 divides (p-1) and is a qth root of 1 mod p; that is, g^q mod p. The 2550 TA rolls a private random group key b (0 < b < q), then computes 2551 public client key v = g^(q-b) mod p. The TA distributes (p, q, g, b) 2552 to all servers using secure means and (p, q, g, v) to all clients not 2553 necessarily using secure means. 2555 Trusted 2556 Authority 2557 +------------+ 2558 | Parameters | 2559 Secure +------------+ Insecure 2560 +-------------| Group Key |-----------+ 2561 | +------------+ | 2562 | | Client Key | | 2563 | +------------+ | 2564 \|/ \|/ 2565 +------------+ Challenge +------------+ 2566 | Parameters |<------------------------| Parameters | 2567 +------------+ +------------+ 2568 | Group Key |------------------------>| Client Key | 2569 +------------+ Response +------------+ 2570 Server Client 2572 Figure 15: Schnorr (IFF) Identity Scheme 2574 The IFF identity scheme is shown in Figure Figure 15. The TA 2575 generates a DSA parameter structure for use as IFF parameters. The 2576 IFF parameters are identical to the DSA parameters, so the OpenSSL 2577 library DSA parameter generation routine can be used directly. The 2578 DSA parameter structure shown in Table Figure 16 is written to a file 2579 as a DSA private key encoded in PEM. Unused structure members are 2580 set to one. 2582 +----------------------------------+-------------+ 2583 | IFF | DSA | Item | Include | 2584 +=========+==========+=============+=============+ 2585 | p | p | modulus | all | 2586 +---------+----------+-------------+-------------+ 2587 | q | q | modulus | all | 2588 +---------+----------+-------------+-------------+ 2589 | g | g | generator | all | 2590 +---------+----------+-------------+-------------+ 2591 | b | priv_key | group key | server | 2592 +---------+----------+-------------+-------------+ 2593 | v | pub_key | client keys | client | 2594 +---------+----------+-------------+-------------+ 2596 Figure 16: IFF Identity Scheme Parameters 2598 Alice challenges Bob to confirm identity using the following protocol 2599 exchange. 2601 1. Alice rolls random r (0 < r < q) and sends to Bob. 2603 2. Bob rolls random k (0 < k < q), computes y = k + br mod q and x = 2604 g^k mod p, then sends (y, hash(x)) to Alice. 2606 3. Alice computes z = g^y * v^r mod p and verifies hash(z) = 2607 hash(x). 2609 If the hashes match, Alice knows that Bob has the group key b. 2610 Besides making the response shorter, the hash makes it effectively 2611 impossible for an intruder to solve for b by observing a number of 2612 these messages. The signed response binds this knowledge to Bob's 2613 private key and the public key previously received in his 2614 certificate. On success the IFF and PRV bits are lit in the server 2615 status word. 2617 D.4. Guillard-Quisquater (GQ) 2619 The Guillou-Quisquater (GQ) identity scheme is useful when 2620 certificates are generated using the NTP software library. These 2621 routines convey the GQ public key in a X.509v3 extension field. The 2622 scheme involves a set of parameters which persist for the life of the 2623 scheme and a private/public identity key, which is refreshed each 2624 time a new certificate is generated. The utility inserts the client 2625 key in an X.509 extension field when the certificate is generated. 2626 The client key is used when computing the response to a challenge. 2627 The TA generates the GQ parameters and keys and distributes them by 2628 secure means to all group members. The scheme is self contained and 2629 independent of new generations of host keys and sign keys and 2630 certificates. 2632 The GQ parameters are generated by OpenSSL routines normally used to 2633 generate RSA keys. By happy coincidence, the mathematical principles 2634 on which GQ is based are similar to RSA, but only the modulus n is 2635 used in identity calculations. The parameters hide in a RSA cuckoo 2636 structure and use the same members. The values are used in an 2637 identity scheme based on RSA cryptography and described in [14] and 2638 [13] p. 300 (with errors). The 512-bit public modulus n=pq, where p 2639 and q are secret large primes. The TA rolls random group key b (0 < 2640 b < n) and distributes (n, b) to all group members using secure 2641 means. The private server key and public client key are constructed 2642 later. 2644 Trusted 2645 Authority 2646 +------------+ 2647 | Parameters | 2648 Secure +------------+ Secure 2649 +-------------| Group Key |-----------+ 2650 | +------------+ | 2651 \|/ \|/ 2652 +------------+ Challenge +------------+ 2653 | Parameters |<------------------------| Parameters | 2654 +------------+ +------------+ 2655 | Group Key | | Group Key | 2656 +------------+ Response +------------+ 2657 | Server Key |------------------------>| Client Key | 2658 +------------+ +------------+ 2659 Server Client 2661 Figure 17: Schnorr (IFF) Identity Scheme 2663 The GQ identity scheme is shown in Figure Figure 17. When generating 2664 new certificates, the server rolls new random private server key u (0 2665 < u < n) and public client key its inverse obscured by the group key 2666 v = (u^-1)^b mod n. These values replace the private and public keys 2667 normally generated by the RSA scheme. In addition, the public client 2668 key is conveyed in a X.509 certificate extension. The updated GQ 2669 structure shown in Figure Figure 18 is written as an RSA private key 2670 encoded in PEM. Unused structure members are set to one. 2672 +---------------------------------+-------------+ 2673 | GQ | RSA | Item | Include | 2674 +=========+==========+============+=============+ 2675 | n | n | modulus | all | 2676 +---------+----------+------------+-------------+ 2677 | b | e | group key | server | 2678 +---------+----------+------------+-------------+ 2679 | u | p | server key | server | 2680 +---------+----------+------------+-------------+ 2681 | v | q | client key | client | 2682 +---------+----------+------------+-------------+ 2684 Figure 18: IFF Identity Scheme Parameters 2686 Alice challenges Bob to confirm identity using the following 2687 exchange. 2689 1. Alice rolls random r (0 < r < n) and sends to Bob. 2691 2. Bob rolls random k (0 < k < n) and computes y = ku^r mod n and x 2692 = k^b mod n, then sends (y, hash(x)) to Alice. 2694 3. Alice computes z = (v^r)*(y^b) mod n and verifies hash(z) = 2695 hash(x). 2697 If the hashes match, Alice knows that Bob has the group key b. 2698 Besides making the response shorter, the hash makes it effectively 2699 impossible for an intruder to solve for b by observing a number of 2700 these messages. The signed response binds this knowledge to Bob's 2701 private key and the public key previously received in his 2702 certificate. Further evidence is the certificate containing the 2703 public identity key, since this is also signed with Bob's private 2704 key. On success the IFF and PRV bits are lit in the server status 2705 word. 2707 D.5. Mu-Varadharajan (MV) Identity Scheme 2709 The Mu-Varadharajan (MV) scheme was originally intended to encrypt 2710 broadcast transmissions to receivers which do not transmit. There is 2711 one encryption key for the broadcaster and a separate decryption key 2712 for each receiver. It operates something like a pay-per-view 2713 satellite broadcasting system where the session key is encrypted by 2714 the broadcaster and the decryption keys are held in a tamper proof 2715 set-top box. We don't use it this way, but read on. 2717 The MV scheme is perhaps the most interesting and flexible of the 2718 three challenge/response schemes. It can be used when a small number 2719 of servers provide synchronization to a large client population where 2720 there might be considerable risk of compromise between and among the 2721 servers and clients. The TA generates an intricate cryptosystem 2722 involving public and private encryption keys, together with a number 2723 of activation keys and associated private client decryption keys. 2724 The activation keys are used by the TA to activate and revoke 2725 individual client decryption keys without changing the decryption 2726 keys themselves. 2728 The TA provides the server with a private encryption key and public 2729 decryption key. The server adjusts the keys by a nonce for each 2730 plaintext encryption, so they appear different on each use. The 2731 encrypted ciphertext and adjusted public decryption key are provided 2732 in the client message. The client computes the decryption key from 2733 its private decryption key and the public decryption key in the 2734 message. 2736 In the MV scheme the activation keys are known only to the TA. The 2737 TA decides which keys to activate and provides to the servers a 2738 private encryption key E and public decryption keys g-bar and g-hat 2739 which depend on the activated keys. The servers have no additional 2740 information and, in particular, cannot masquerade as a TA. In 2741 addition, the TA provides to each client j individual private 2742 decryption keys x-bar_j and x-hat_j , which do not need to be changed 2743 if the TA activates or deactivates this key. The clients have no 2744 further information and, in particular, cannot masquerade as a server 2745 or TA. 2747 The MV values hide in a DSA cuckoo structure which uses the same 2748 parameters, but generated in a different way. The values are used in 2749 an encryption scheme similar to El Gamal cryptography and a 2750 polynomial formed from the expansion of product terms (x-x_1)*(x- 2751 x_2)*(x-x_3)*...*(x-x_n), as described in [15]. The paper has 2752 significant errors and serious omissions. 2754 Trusted 2755 Authority 2756 +------------+ 2757 | Parameters | 2758 +------------+ 2759 | Group Key | 2760 +------------+ 2761 | Server Key | 2762 Secure +------------+ Secure 2763 +-------------| Client Key |-----------+ 2764 | +------------+ | 2765 \|/ \|/ 2766 +------------+ Challenge +------------+ 2767 | Parameters |<------------------------| Parameters | 2768 +------------+ +------------+ 2769 | Server Key |------------------------>| Client Key | 2770 +------------+ Response +------------+ 2771 Server Client 2773 Figure 19: Mu-Varadharajan (MV) Identity Scheme 2775 The MV identity scheme is shown in Figure Figure 19. The TA writes 2776 the server parameters, private encryption key and public decryption 2777 keys for all servers as a DSA private key encoded in PEM, as shown in 2778 the Figure Figure 20. 2780 +---------------------------------+-------------+ 2781 | MV | DSA | Item | Include | 2782 +=========+==========+============+=============+ 2783 | p | p | modulus | all | 2784 +---------+----------+------------+-------------+ 2785 | q | q | modulus | server | 2786 +---------+----------+------------+-------------+ 2787 | E | g | private | server | 2788 | | | encrypt | | 2789 +---------+----------+------------+-------------+ 2790 | g-bar | priv_key | public | server | 2791 | | | decrypt | | 2792 +---------+----------+------------+-------------+ 2793 | g-hat | pub_key | public | server | 2794 | | | decrypt | | 2795 +---------+----------+------------+-------------+ 2797 Figure 20: MV Scheme Server Parameters 2799 The TA writes the client parameters and private decryption keys for 2800 each client as a DSA private key encoded in PEM. It is used only by 2801 the designated recipient(s) who pay a suitably outrageous fee for its 2802 use. Unused structure members are set to one, as shown in Table 2803 Figure 21, 2805 +---------------------------------+-------------+ 2806 | MV | DSA | Item | Include | 2807 +=========+==========+============+=============+ 2808 | p | p | modulus | all | 2809 +---------+----------+------------+-------------+ 2810 | x-bar_j | priv_key | public | client | 2811 | | | decrypt | | 2812 +---------+----------+------------+-------------+ 2813 | x-hat_j | pub_key | public | client | 2814 | | | decrypt | | 2815 +---------+----------+------------+-------------+ 2817 Figure 21: MV Scheme Client Parameters 2819 The devil is in the details. Let q be the product of n distinct 2820 primes s'_j (j = 1...n), where each s'_j, also called an activation 2821 key, has m significant bits. Let prime p = 2q + 1, so that q and 2822 each s'_j divide p-1 and p has M=nm+1 significant bits. Let g be the 2823 generator of the multiplicative group Zp*; that is, gcd(g, p-1) = 1 2824 and g^q = 1 mod p. We do modular arithmetic over Zq and then project 2825 into Zp* as powers of g. Sometimes we have to compute an inverse 2826 b^-1 of random b in Zq, but for that purpose we require gcd(b, q) = 2827 1. We expect M to be in the 500-bit range and n relatively small, 2828 like 30. The TA uses a nasty probabilistic algorithm to generate the 2829 cryptosystem. 2831 1. Generate the m-bit primes s'_j (0 < j < n), which may have to be 2832 replaced later. As a practical matter, it is tough to find more 2833 than 30 distinct primes for M=512 or 60 primes for M=1024. The 2834 latter can take several hundred iterations and several minutes on 2835 a Sun Blade 1000. 2837 2. Compute modulus q = s'_1 * s'_2 * ... * s'_n, then modulus p = 2q 2838 + 1. If p is composite, the TA replaces one of the primes with a 2839 new distinct prime and tries again. Note that q will hardly be a 2840 secret since p is revealed to servers and clients. However, 2841 factoring q to find the primes should be adequately hard, as this 2842 is the same problem considered hard in RSA. Question: is it as 2843 hard to find n small prime factors totalling M bits as it is to 2844 find two large prime factors totalling M bits? Remember, the bad 2845 guy doesn't know n. 2847 3. Associate with each s'_j an element s_j such that s_j*s'_j = s'_j 2848 mod q. One way to find an s_j is the quotient s_j = (q + s'_j) / 2849 s'_j. 2851 4. Compute the generator g of Z_p using a random roll such that 2852 gcd(g, p-1) = 1 and g^q = 1 mod p. If not, roll again. 2854 Once the cryptosystem parameters have been determined, the TA sets up 2855 a specific instance of the scheme as follows. 2857 1. Roll n random roots x_j (0 < x_j < q) for a polynomial of order 2858 n. While it may not be strictly necessary, Make sure each root 2859 has no factors in common with q. 2861 2. Expand the n product terms (x-x_0)*(x-x_1)*...*(x-x_n) to form n 2862 + 1 coefficients a_i mod q (0 <= i < n) in powers of x using a 2863 fast method contributed by C. Boncelet. 2865 3. Generate g_i = g^(a_i) mod p for all i and the generator g. 2866 Verify the product g_i^(a_i*(x_j)^i) = 1 mod p for all i, j (0 <= 2867 i < n, 0 <= j < n). Note the a_i*(x_j)^i exponent is computed 2868 mod q, but the g_i is computed mod p. Also note the expression 2869 given in the paper cited is incorrect. 2871 4. Make master encryption key A = product of (g_i)^x_j mod p (0 <= i 2872 < n, 0 <= j < n). Keep it around for awhile, since it is 2873 expensive to compute. 2875 5. Roll private random group key b (0 < b < q), where gcd(b, q) = 1 2876 to guarantee the inverse exists, then compute b^-1 mod q. If b 2877 is changed, all keys must be recomputed. 2879 6. Make private client keys x-bar_j = b^-1 * ((x_1)^n + (x_2)^n + 2880 ... + (x_n)^n) mod q (omitting (x_j)^n from the summation) and 2881 x-hat_j = s_j * (x_j)^n mod q for all j. Note that the keys for 2882 the jth client involve only s_j, but not s'_j or s. The TA sends 2883 (p, x-bar_j, x-hat_j) to the jth client(s) using secure means. 2885 7. The activation key is initially q by construction. The TA 2886 revokes client j by dividing q by s'_j. The quotient becomes the 2887 activation key s. Note we always have to revoke one key; 2888 otherwise, the plaintext and cryptotext would be identical. The 2889 TA computes E = A^s, g-bar = x-bar^s mod p, g-hat = x-hat^sb mod 2890 p and sends (p, E, g-bar, g-hat to the servers using secure 2891 means. 2893 Alice challenges Bob to confirm identity using the following 2894 exchange. 2896 1. Alice rolls random r (0 < r < q) and sends to Bob. 2898 2. Bob rolls random k (0 < k < q) and computes the session 2899 encryption key E' = E^k mod p and public decryption key g-bar' = 2900 g-bar^k mod p and g-hat' = g-hat^k mod p. He encrypts x = E' * r 2901 mod p and sends (hash(x), g-bar', g-hat') to Alice. 2903 3. Alice computes the session decryption key E^-1 = (g-bar')^x-hat_j 2904 * (g-hat')^x-bar_j mod p, recovers the encryption key E' = 2905 (E^-1)^-1 mod p, encrypts z = E' * r mod p, then verifies that 2906 hash(z) = hash(x). 2908 D.6. Interoperability Issues 2910 A specific combination of authentication scheme (none, symmetric key, 2911 Autokey), digest/signature scheme and identity scheme (PC, TC, IFF, 2912 GQ, MV) is called a cryptotype, although not all combinations are 2913 possible. There may be management configurations where the servers 2914 and clients may not all support the same cryptotypes. A secure NTPv4 2915 subnet can be configured in several ways while keeping in mind the 2916 principles explained in this section. Note however that some 2917 cryptotype combinations may successfully interoperate with each 2918 other, but may not represent good security practice. 2920 The cryptotype of an association is determined at the time of 2921 mobilization, either at configuration time or some time later when a 2922 packet of appropriate cryptotype arrives. When a client, broadcast 2923 or symmetric active association is mobilized at configuration time, 2924 it can be designated non-authentic, authenticated with symmetric key 2925 or authenticated with some Autokey scheme, and subsequently it will 2926 send packets with that cryptotype. When a responding server, 2927 broadcast client or symmetric passive association is mobilized, it is 2928 designated with the same cryptotype as the received packet. 2930 When multiple identity schemes are supported, the parameter exchange 2931 determines which one is used. The request message contains bits 2932 corresponding to the schemes it supports, while the response message 2933 contains bits corresponding to the schemes it supports. The client 2934 matches the server bits with its own and selects a compatible 2935 identity scheme. The server is driven entirely by the client 2936 selection and remains stateless. When multiple selections are 2937 possible, the order from most secure to least is GC, IFF, TC. Note 2938 that PC does not interoperate with any of the others, since they 2939 require the host certificate which a PC server will not reveal. 2941 Following the principle that time is a public value, a server 2942 responds to any client packet that matches its cryptotype 2943 capabilities. Thus, a server receiving a non-authenticated packet 2944 will respond with a non-authenticated packet, while the same server 2945 receiving a packet of a cryptotype it supports will respond with 2946 packets of that cryptotype. However, new broadcast or manycast 2947 client associations or symmetric passive associations will not be 2948 mobilized unless the server supports a cryptotype compatible with the 2949 first packet received. By default, non-authenticated associations 2950 will not be mobilized unless overridden in a decidedly dangerous way. 2952 Some examples may help to reduce confusion. Client Alice has no 2953 specific cryptotype selected. Server Bob supports both symmetric key 2954 and Autokey cryptography. Alice's non-authenticated packets arrive 2955 at Bob, who replies with non-authenticated packets. Cathy has a copy 2956 of Bob's symmetric key file and has selected key ID 4 in packets to 2957 Bob. If Bob verifies the packet with key ID 4, he sends Cathy a reply 2958 with that key. If authentication fails, Bob sends Cathy a thing 2959 called a crypto-NAK, which tells her something broke. She can see 2960 the evidence using the utility programs of the NTP software library. 2962 Symmetric peers Bob and Denise have rolled their own host keys, 2963 certificates and identity parameters and lit the host status bits for 2964 the identity schemes they can support. Upon completion of the 2965 parameter exchange, both parties know the digest/signature scheme and 2966 available identity schemes of the other party. They do not have to 2967 use the same schemes, but each party must use the digest/signature 2968 scheme and one of the identity schemes supported by the other party. 2970 It should be clear from the above that Bob can support all the girls 2971 at the same time, as long as he has compatible authentication and 2972 identification credentials. Now, Bob can act just like the girls in 2973 his own choice of servers; he can run multiple configured 2974 associations with multiple different servers (or the same server, 2975 although that might not be useful). But, wise security policy might 2976 preclude some cryptotype combinations; for instance, running an 2977 identity scheme with one server and no authentication with another 2978 might not be wise. 2980 Appendix E. ASN.1 Encoding Rules 2982 Certain value fields in request and response messages contain data 2983 encoded in ASN.1 distinguished encoding rules (DER). The BNF grammar 2984 for each encoding rule is given below along with the OpenSSL routine 2985 used for the encoding in the reference implementation. The object 2986 identifiers for the encryption algorithms and message digest/ 2987 signature encryption schemes are specified in [16]. The particular 2988 algorithms required for conformance are not specified in this report. 2990 E.1. COOKIE request, IFF response, GQ response, MV response 2992 The value field of the COOKIE request message contains a sequence of 2993 two integers (n, e) encoded by the i2d_RSAPublicKey() routine in the 2994 OpenSSL distribution. In the request, n is the RSA modulus in bits 2995 and e is the public exponent. 2997 RSAPublicKey ::= SEQUENCE { 2998 n ::= INTEGER, 2999 e ::= INTEGER 3000 } 3002 The IFF and GQ responses contain a sequence of two integers (r, s) 3003 encoded by the i2d_DSA_SIG() routine in the OpenSSL distribution. In 3004 the responses, r is the challenge response and s is the hash of the 3005 private value. 3007 DSAPublicKey ::= SEQUENCE { 3008 r ::= INTEGER, 3009 s ::= INTEGER 3010 } 3012 The MV response contains a sequence of three integers (p, q, g) 3013 encoded by the i2d_DSAparams() routine in the OpenSSL library. In 3014 the response, p is the hash of the encrypted challenge value and (q, 3015 g) is the client portion of the decryption key. 3017 DSAparameters ::= SEQUENCE { 3018 p ::= INTEGER, 3019 q ::= INTEGER, 3020 g ::= INTEGER 3021 } 3023 E.2. CERT response, SIGN request and response 3025 The value field contains a X509v3 certificate encoded by the 3026 i2d_X509() routine in the OpenSSL distribution. The encoding follows 3027 the rules stated in [11], including the use of X509v3 extension 3028 fields. 3030 Certificate ::= SEQUENCE { 3031 tbsCertificate TBSCertificate, 3032 signatureAlgorithm AlgorithmIdentifier, 3033 signatureValue BIT STRING 3034 } 3036 The signatureAlgorithm is the object identifier of the message 3037 digest/signature encryption scheme used to sign the certificate. The 3038 signatureValue is computed by the certificate issuer using this 3039 algorithm and the issuer private key. 3041 TBSCertificate ::= SEQUENCE { 3042 version EXPLICIT v3(2), 3043 serialNumber CertificateSerialNumber, 3044 signature AlgorithmIdentifier, 3045 issuer Name, 3046 validity Validity, 3047 subject Name, 3048 subjectPublicKeyInfo SubjectPublicKeyInfo, 3049 extensions EXPLICIT Extensions OPTIONAL 3050 } 3052 The serialNumber is an integer guaranteed to be unique for the 3053 generating host. The reference implementation uses the NTP seconds 3054 when the certificate was generated. The signature is the object 3055 identifier of the message digest/signature encryption scheme used to 3056 sign the certificate. It must be identical to the 3057 signatureAlgorithm. 3059 CertificateSerialNumber ::= INTEGER 3060 Validity ::= SEQUENCE { 3061 notBefore UTCTime, 3062 notAfter UTCTime 3063 } 3064 The notBefore and notAfter define the period of validity as defined 3065 in Appendix D. 3067 SubjectPublicKeyInfo ::= SEQUENCE { 3068 algorithm AlgorithmIdentifier, 3069 subjectPublicKey BIT STRING 3070 } 3072 The AlgorithmIdentifier specifies the encryption algorithm for the 3073 subject public key. The subjectPublicKey is the public key of the 3074 subject. 3076 Extensions ::= SEQUENCE SIZE (1..MAX) OF Extension 3077 Extension ::= SEQUENCE { 3078 extnID OBJECT IDENTIFIER, 3079 critical BOOLEAN DEFAULT FALSE, 3080 extnValue OCTET STRING 3081 } 3083 Name ::= SEQUENCE { 3084 OBJECT IDENTIFIER commonName 3085 PrintableString HostName 3086 } 3088 For all certificates, the subject HostName is the unique DNS name of 3089 the host to which the public key belongs. The reference 3090 implementation uses the string returned by the Unix gethostname() 3091 routine (trailing NUL removed). For other than self-signed 3092 certificates, the issuer HostName is the unique DNS name of the host 3093 signing the certificate. 3095 Authors' Addresses 3097 Brian Haberman (editor) 3098 The Johns Hopkins University Applied Physics Laboratory 3099 11100 Johns Hopkins Road 3100 Laurel, MD 20723-6099 3101 US 3103 Phone: +1 443 778 1319 3104 Email: brian@innovationslab.net 3105 Dr. David L. Mills 3106 University of Delaware 3107 Newark, DE 19716 3108 US 3110 Phone: +1 302 831 8247 3111 Email: mills@udel.edu 3113 Full Copyright Statement 3115 Copyright (C) The IETF Trust (2007). 3117 This document is subject to the rights, licenses and restrictions 3118 contained in BCP 78, and except as set forth therein, the authors 3119 retain all their rights. 3121 This document and the information contained herein are provided on an 3122 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 3123 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 3124 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 3125 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 3126 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 3127 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 3129 Intellectual Property 3131 The IETF takes no position regarding the validity or scope of any 3132 Intellectual Property Rights or other rights that might be claimed to 3133 pertain to the implementation or use of the technology described in 3134 this document or the extent to which any license under such rights 3135 might or might not be available; nor does it represent that it has 3136 made any independent effort to identify any such rights. Information 3137 on the procedures with respect to rights in RFC documents can be 3138 found in BCP 78 and BCP 79. 3140 Copies of IPR disclosures made to the IETF Secretariat and any 3141 assurances of licenses to be made available, or the result of an 3142 attempt made to obtain a general license or permission for the use of 3143 such proprietary rights by implementers or users of this 3144 specification can be obtained from the IETF on-line IPR repository at 3145 http://www.ietf.org/ipr. 3147 The IETF invites any interested party to bring to its attention any 3148 copyrights, patents or patent applications, or other proprietary 3149 rights that may cover technology that may be required to implement 3150 this standard. Please address the information to the IETF at 3151 ietf-ipr@ietf.org. 3153 Acknowledgment 3155 Funding for the RFC Editor function is provided by the IETF 3156 Administrative Support Activity (IASA).