idnits 2.17.1 draft-ietf-ntp-autokey-07.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Sep 2009 rather than the newer Notice from 28 Dec 2009. (See https://trustee.ietf.org/license-info/) 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 9 instances of too long lines in the document, the longest one being 4 characters in excess of 72. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 2346: '... EXPLICIT Extensions OPTIONAL...' Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document seems to contain a disclaimer for pre-RFC5378 work, and may have content which was first submitted before 10 November 2008. The disclaimer is necessary when there are original authors that you have been unable to contact, or if some do not wish to grant the BCP78 rights to the IETF Trust. If you are able to get all authors (current and original) to grant those rights, you can and should remove the disclaimer; otherwise, the disclaimer is needed and you can ignore this comment. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (November 11, 2009) is 5277 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 ---------------------------------------------------------------------------- -- Obsolete informational reference (is this intentional?): RFC 1305 (Obsoleted by RFC 5905) -- Obsolete informational reference (is this intentional?): RFC 2402 (Obsoleted by RFC 4302, RFC 4305) -- Obsolete informational reference (is this intentional?): RFC 2406 (Obsoleted by RFC 4303, RFC 4305) -- Obsolete informational reference (is this intentional?): RFC 2408 (Obsoleted by RFC 4306) -- Obsolete informational reference (is this intentional?): RFC 2510 (Obsoleted by RFC 4210) -- Obsolete informational reference (is this intentional?): RFC 2875 (Obsoleted by RFC 6955) Summary: 3 errors (**), 0 flaws (~~), 1 warning (==), 9 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 Intended status: Informational D. Mills 5 Expires: May 15, 2010 U. Delaware 6 November 11, 2009 8 Network Time Protocol Version 4 Autokey Specification 9 draft-ietf-ntp-autokey-07 11 Abstract 13 This memo describes the Autokey security model for authenticating 14 servers to clients using the Network Time Protocol (NTP) and public 15 key cryptography. Its design is based on the premise that IPsec 16 schemes cannot be adopted intact, since that would preclude stateless 17 servers and severely compromise timekeeping accuracy. In addition, 18 PKI schemes presume authenticated time values are always available to 19 enforce certificate lifetimes; however, cryptographically verified 20 timestamps require interaction between the timekeeping and 21 authentication functions. 23 This memo includes the Autokey requirements analysis, design 24 principles and protocol specification. A detailed description of the 25 protocol states, events and transition functions is included. A 26 prototype of the Autokey design based on this memo has been 27 implemented, tested and documented in the NTP Version 4 (NTPv4) 28 software distribution for Unix, Windows and VMS at 29 http://www.ntp.org. 31 Status of this Memo 33 This Internet-Draft is submitted to IETF in full conformance with the 34 provisions of BCP 78 and BCP 79. 36 Internet-Drafts are working documents of the Internet Engineering 37 Task Force (IETF), its areas, and its working groups. Note that 38 other groups may also distribute working documents as Internet- 39 Drafts. 41 Internet-Drafts are draft documents valid for a maximum of six months 42 and may be updated, replaced, or obsoleted by other documents at any 43 time. It is inappropriate to use Internet-Drafts as reference 44 material or to cite them other than as "work in progress." 46 The list of current Internet-Drafts can be accessed at 47 http://www.ietf.org/ietf/1id-abstracts.txt. 49 The list of Internet-Draft Shadow Directories can be accessed at 50 http://www.ietf.org/shadow.html. 52 This Internet-Draft will expire on May 15, 2010. 54 Copyright Notice 56 Copyright (c) 2009 IETF Trust and the persons identified as the 57 document authors. All rights reserved. 59 This document is subject to BCP 78 and the IETF Trust's Legal 60 Provisions Relating to IETF Documents 61 (http://trustee.ietf.org/license-info) in effect on the date of 62 publication of this document. Please review these documents 63 carefully, as they describe your rights and restrictions with respect 64 to this document. Code Components extracted from this document must 65 include Simplified BSD License text as described in Section 4.e of 66 the Trust Legal Provisions and are provided without warranty as 67 described in the BSD License. 69 This document may contain material from IETF Documents or IETF 70 Contributions published or made publicly available before November 71 10, 2008. The person(s) controlling the copyright in some of this 72 material may not have granted the IETF Trust the right to allow 73 modifications of such material outside the IETF Standards Process. 74 Without obtaining an adequate license from the person(s) controlling 75 the copyright in such materials, this document may not be modified 76 outside the IETF Standards Process, and derivative works of it may 77 not be created outside the IETF Standards Process, except to format 78 it for publication as an RFC or to translate it into languages other 79 than English. 81 Table of Contents 83 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 84 2. NTP Security Model . . . . . . . . . . . . . . . . . . . . . . 4 85 3. Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 86 4. Autokey Cryptography . . . . . . . . . . . . . . . . . . . . . 8 87 5. Autokey Protocol Overview . . . . . . . . . . . . . . . . . . 12 88 6. NTP Secure Groups . . . . . . . . . . . . . . . . . . . . . . 14 89 7. Identity Schemes . . . . . . . . . . . . . . . . . . . . . . . 18 90 8. Timestamps and Filestamps . . . . . . . . . . . . . . . . . . 20 91 9. Autokey Operations . . . . . . . . . . . . . . . . . . . . . . 21 92 10. Autokey Protocol Messages . . . . . . . . . . . . . . . . . . 23 93 10.1. No-Operation . . . . . . . . . . . . . . . . . . . . . . 26 94 10.2. Association Message (ASSOC) . . . . . . . . . . . . . . . 26 95 10.3. Certificate Message (CERT) . . . . . . . . . . . . . . . 26 96 10.4. Cookie Message (COOKIE) . . . . . . . . . . . . . . . . . 26 97 10.5. Autokey Message (AUTO) . . . . . . . . . . . . . . . . . 26 98 10.6. Leapseconds Values Message (LEAP) . . . . . . . . . . . . 27 99 10.7. Sign Message (SIGN) . . . . . . . . . . . . . . . . . . . 27 100 10.8. Identity Messages (IFF, GQ, MV) . . . . . . . . . . . . . 27 101 11. Autokey State Machine . . . . . . . . . . . . . . . . . . . . 27 102 11.1. Status Word . . . . . . . . . . . . . . . . . . . . . . . 27 103 11.2. Host State Variables . . . . . . . . . . . . . . . . . . 30 104 11.3. Client State Variables (all modes) . . . . . . . . . . . 32 105 11.4. Protocol State Transitions . . . . . . . . . . . . . . . 32 106 11.4.1. Server Dance . . . . . . . . . . . . . . . . . . . . 33 107 11.4.2. Broadcast Dance . . . . . . . . . . . . . . . . . . . 33 108 11.4.3. Symmetric Dance . . . . . . . . . . . . . . . . . . . 35 109 11.5. Error Recovery . . . . . . . . . . . . . . . . . . . . . 36 110 12. Security Considerations . . . . . . . . . . . . . . . . . . . 37 111 12.1. Protocol Vulnerability . . . . . . . . . . . . . . . . . 37 112 12.2. Clogging Vulnerability . . . . . . . . . . . . . . . . . 38 113 13. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 39 114 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 39 115 14.1. Normative References . . . . . . . . . . . . . . . . . . 39 116 14.2. Informative References . . . . . . . . . . . . . . . . . 39 117 Appendix A. Timestamps, Filestamps and Partial Ordering . . . . . 41 118 Appendix B. Identity Schemes . . . . . . . . . . . . . . . . . . 42 119 Appendix C. Private Certificate (PC) Scheme . . . . . . . . . . . 42 120 Appendix D. Trusted Certificate (TC) Scheme . . . . . . . . . . . 43 121 Appendix E. Schnorr (IFF) Identity Scheme . . . . . . . . . . . . 44 122 Appendix F. Guillard-Quisquater (GQ) Identity Scheme . . . . . . 45 123 Appendix G. Mu-Varadharajan (MV) Identity Scheme . . . . . . . . 47 124 Appendix H. ASN.1 Encoding Rules . . . . . . . . . . . . . . . . 50 125 Appendix I. COOKIE request, IFF response, GQ response, MV 126 response . . . . . . . . . . . . . . . . . . . . . . 50 127 Appendix J. Certificates . . . . . . . . . . . . . . . . . . . . 51 128 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 53 130 1. Introduction 132 A distributed network service requires reliable, ubiquitous and 133 survivable provisions to prevent accidental or malicious attacks on 134 the servers and clients in the network or the values they exchange. 135 Reliability requires that clients can determine that received packets 136 are authentic; that is, were actually sent by the intended server and 137 not manufactured or modified by an intruder. Ubiquity requires that 138 a client can verify the authenticity of a server using only public 139 information. Survivability requires protection from faulty 140 implementations, improper operation and possibly malicious clogging 141 and replay attacks. 143 This memo describes a cryptographically sound and efficient 144 methodology for use in the Network Time Protocol (NTP) 145 [I-D.ietf-ntp-ntpv4-proto]. The various key agreement schemes 146 [RFC2408][RFC2412][RFC2522] proposed require per-association state 147 variables, which contradicts the principles of the remote procedure 148 call (RPC) paradigm in which servers keep no state for a possibly 149 large client population. An evaluation of the PKI model and 150 algorithms, e.g., as implemented in the OpenSSL library, leads to the 151 conclusion that any scheme requiring every NTP packet to carry a PKI 152 digital signature would result in unacceptably poor timekeeping 153 performance. 155 The Autokey protocol is based on a combination of PKI and a pseudo- 156 random sequence generated by repeated hashes of a cryptographic value 157 involving both public and private components. This scheme has been 158 implemented, tested and deployed in the Internet of today. A 159 detailed description of the security model, design principles and 160 implementation is presented in this memo. 162 This informational document describes the NTP extensions for Autokey 163 as implemented in an NTPv4 software distribution available from 164 http://www.ntp.org. This description is provided to offer a basis 165 for future work and a reference for the software release. This 166 document also describes the motivation for the extensions within the 167 protocol. 169 2. NTP Security Model 171 NTP security requirements are even more stringent than most other 172 distributed services. First, the operation of the authentication 173 mechanism and the time synchronization mechanism are inextricably 174 intertwined. Reliable time synchronization requires cryptographic 175 keys which are valid only over a designated time intervals; but, time 176 intervals can be enforced only when participating servers and clients 177 are reliably synchronized to UTC. In addition, the NTP subnet is 178 hierarchical by nature, so time and trust flow from the primary 179 servers at the root through secondary servers to the clients at the 180 leaves. 182 A client can claim authentic to dependent applications only if all 183 servers on the path to the primary servers are bone-fide authentic. 184 In order to emphasize this requirement, in this memo the notion of 185 "authentic" is replaced by "proventic", a noun new to English and 186 derived from provenance, as in the provenance of a painting. Having 187 abused the language this far, the suffixes fixable to the various 188 derivatives of authentic will be adopted for proventic as well. In 189 NTP each server authenticates the next lower stratum servers and 190 proventicates (authenticates by induction) the lowest stratum 191 (primary) servers. Serious computer linguists would correctly 192 interpret the proventic relation as the transitive closure of the 193 authentic relation. 195 It is important to note that the notion of proventic does not 196 necessarily imply the time is correct. A NTP client mobilizes a 197 number of concurrent associations with different servers and uses a 198 crafted agreement algorithm to pluck truechimers from the population 199 possibly including falsetickers. A particular association is 200 proventic if the server certificate and identity have been verified 201 by the means described in this memo. However, the statement "the 202 client is synchronized to proventic sources" means that the system 203 clock has been set using the time values of one or more proventic 204 associations and according to the NTP mitigation algorithms. 206 Over the last several years the IETF has defined and evolved the 207 IPsec infrastructure for privacy protection and source authentication 208 in the Internet. The infrastructure includes the Encapsulating 209 Security Payload (ESP) [RFC2406] and Authentication Header (AH) 210 [RFC2402] for IPv4 and IPv6. Cryptographic algorithms that use these 211 headers for various purposes include those developed for the PKI, 212 including various message digest, digital signature and key agreement 213 algorithms. This memo takes no position on which message digest or 214 which digital signature algorithm is used. This is established by a 215 profile for each community of users. 217 It will facilitate the discussion in this memo to refer to the 218 reference implementation available at http://www.ntp.org. It 219 includes Autokey as described in this memo and is available to the 220 general public; however, it is not part of the specification itself. 221 The cryptographic means used by the reference implementation and its 222 user community are based on the OpenSSL cryptographic software 223 library available at http://www.openssl.org, but other libraries with 224 equivalent functionality could be used as well. It is important for 225 distribution and export purposes that the way in which these 226 algorithms are used precludes encryption of any data other than 227 incidental to the construction of digital signatures. 229 The fundamental assumption in NTP the security model is that packets 230 transmitted over the Internet can be intercepted by other than the 231 intended recipient, remanufactured in various ways and replayed in 232 whole or part. These packets can cause the client to believe or 233 produce incorrect information, cause protocol operations to fail, 234 interrupt network service or consume precious network and processor 235 resources. 237 In the case of NTP, the assumed goal of the intruder is to inject 238 false time values, disrupt the protocol or clog the network, servers 239 or clients with spurious packets that exhaust resources and deny 240 service to legitimate applications. The mission of the algorithms 241 and protocols described in this memo is to detect and discard 242 spurious packets sent by other than the intended sender or sent by 243 the intended sender, but modified or replayed by an intruder. 245 There are a number of defense mechanisms already built in the NTP 246 architecture, protocol and algorithms. The on-wire timestamp 247 exchange scheme is inherently resistant to spoofing, packet loss and 248 replay attacks. The engineered clock filter, selection and 249 clustering algorithms are designed to defend against evil cliques of 250 Byzantine traitors. While not necessarily designed to defeat 251 determined intruders, these algorithms and accompanying sanity checks 252 have functioned well over the years to deflect improperly operating 253 but presumably friendly scenarios. However, these mechanisms do not 254 securely identify and authenticate servers to clients. Without 255 specific further protection, an intruder can inject any or all of the 256 following attacks. 258 1. An intruder can intercept and archive packets forever, as well as 259 all the public values ever generated and transmitted over the 260 net. 262 2. An intruder can generate packets faster than the server, network 263 or client can process them, especially if they require expensive 264 cryptographic computations. 266 3. In a wiretap attack the intruder can intercept, modify and replay 267 a packet. However, it cannot permanently prevent onward 268 transmission of the original packet; that is, it cannot break the 269 wire, only tell lies and congest it. Except in unlikely cases 270 considered in Section 12, the modified packet cannot arrive at 271 the victim before the original packet, nor does it have the 272 server private keys or identity parameters. 274 4. In a man-in-the-middle or masquerade attack the intruder is 275 positioned between the server and client, so it can intercept, 276 modify and replay a packet and prevent onward transmission of the 277 original packet. Except in unlikely cases considered in 278 Section 12, the middleman does not have the server private keys. 280 The NTP security model assumes the following possible limitations. 282 1. The running times for public key algorithms are relatively long 283 and highly variable. In general, the performance of the time 284 synchronization function is badly degraded if these algorithms 285 must be used for every NTP packet. 287 2. In some modes of operation it is not feasible for a server to 288 retain state variables for every client. It is however feasible 289 to regenerated them for a client upon arrival of a packet from 290 that client. 292 3. The lifetime of cryptographic values must be enforced, which 293 requires a reliable system clock. However, the sources that 294 synchronize the system clock must be cryptographically 295 proventicated. This circular interdependence of the timekeeping 296 and proventication functions requires special handling. 298 4. Client security functions must involve only public values 299 transmitted over the net. Private values must never be disclosed 300 beyond the machine on which they were created, except in the case 301 of a special trusted agent (TA) assigned for this purpose. 303 Unlike the Secure Shell security model, where the client must be 304 securely authenticated to the server, in NTP the server must be 305 securely authenticated to the client. In ssh each different 306 interface address can be bound to a different name, as returned by a 307 reverse-DNS query. In this design separate public/private key pairs 308 may be required for each interface address with a distinct name. A 309 perceived advantage of this design is that the security compartment 310 can be different for each interface. This allows a firewall, for 311 instance, to require some interfaces to authenticate the client and 312 others not. 314 3. Approach 316 The Autokey protocol described in this memo is designed to meet the 317 following objectives. In-depth discussions on these objectives is in 318 the web briefings and will not be elaborated in this memo. Note that 319 here and elsewhere in this memo mention of broadcast mode means 320 multicast mode as well, with exceptions as noted in the NTP software 321 documentation. 323 1. It must interoperate with the existing NTP architecture model and 324 protocol design. In particular, it must support the symmetric 325 key scheme described in [RFC1305]. As a practical matter, the 326 reference implementation must use the same internal key 327 management system, including the use of 32-bit key IDs and 328 existing mechanisms to store, activate and revoke keys. 330 2. It must provide for the independent collection of cryptographic 331 values and time values. A NTP packet is accepted for processing 332 only when the required cryptographic values have been obtained 333 and verified and the packet has passed all header sanity checks. 335 3. 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 4. 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 disorder, or suboptimal configurations. 345 5. 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 6. It must function in all the modes supported by NTP, including 351 server, symmetric and broadcast modes. 353 4. Autokey Cryptography 355 Autokey cryptography is based on the PKI algorithms commonly used in 356 the Secure Shell and Secure Sockets Layer applications. As in these 357 applications Autokey uses message digests to detect packet 358 modification, digital signatures to verify credentials and public 359 certificates to provide traceable authority. What makes Autokey 360 cryptography unique is the way in which these algorithms are used to 361 deflect intruder attacks while maintaining the integrity and accuracy 362 of the time synchronization function. 364 Autokey, like many other remote procedure call (RPC) protocols, 365 depends on message digests for basic authentication; however, it is 366 important to understand that message digests are also used by NTP 367 when Autokey is not available or not configured. Selection of the 368 digest algorithm is a function of NTP configuration and is 369 transparent to Autokey. 371 The protocol design and reference implementation support both 128-bit 372 and 160-bit message digest algorithms, each with a 32-bit key ID. In 373 order to retain backward compatibility with NTPv3, the NTPv4 key ID 374 space is partitioned in two subspaces at a pivot point of 65536. 375 Symmetric key IDs have values less than the pivot and indefinite 376 lifetime. Autokey key IDs have pseudo-random values equal to or 377 greater than the pivot and are expunged immediately after use. 379 Both symmetric key and public key cryptography authenticate as shown 380 in Figure 1. The server looks up the key associated with the key ID 381 and calculates the message digest from the NTP header and extension 382 fields together with the key value. The key ID and digest form the 383 message authentication code (MAC) included with the message. The 384 client does the same computation using its local copy of the key and 385 compares the result with the digest in the MAC. If the values agree, 386 the message is assumed authentic. 388 +------------------+ 389 | NTP Header and | 390 | Extension Fields | 391 +------------------+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 392 | | | Message Authenticator Code | 393 \|/ \|/ + (MAC) + 394 ******************** | +-------------------------+ | 395 * Compute Hash *<----| Key ID | Message Digest | + 396 ******************** | +-------------------------+ | 397 | +-+-+-+-+-+-+-|-+-+-+-+-+-+-+-+-+ 398 \|/ \|/ 399 +------------------+ +-------------+ 400 | Message Digest |------>| Compare | 401 +------------------+ +-------------+ 403 Figure 1: Message Authentication 405 Autokey uses specially contrived session keys, called autokeys, and a 406 precomputed pseudo-random sequence of autokeys which are saved in the 407 autokey list. The Autokey protocol operates separately for each 408 association, so there may be several autokey sequences operating 409 independently at the same time. 411 +-------------+-------------+--------+--------+ 412 | Src Address | Dst Address | Key ID | Cookie | 413 +-------------+-------------+--------+--------+ 415 Figure 2: NTPv4 Autokey 417 An autokey is computed from four fields in network byte order as 418 shown in Figure 2. The four values are hashed using the MD5 419 algorithm to produce the 128-bit autokey value, which in the 420 reference implementation is stored along with the key ID in a cache 421 used for symmetric keys as well as autokeys. Keys are retrieved from 422 the cache by key ID using hash tables and a fast lookup algorithm. 424 For use with IPv4 the Src Address and Dst Address fields contain 32 425 bits; for use with IPv6 these fields contain 128 bits. In either 426 case the Key ID and Cookie fields contain 32 bits. Thus, an IPv4 427 autokey has four 32-bit words, while an IPv6 autokey has ten 32-bit 428 words. The source and destination addresses and key ID are public 429 values visible in the packet, while the cookie can be a public value 430 or shared private value, depending on the NTP mode. 432 The NTP packet format has been augmented to include one or more 433 extension fields piggybacked between the original NTP header and the 434 MAC. For packets without extension fields, the cookie is a shared 435 private value. For packets with extension fields, the cookie has a 436 default public value of zero, since these packets are validated 437 independently using 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 list and that these fields be the same 446 as those visible in the received packet. [The use of alternative 447 means, such as Autokey host names (discussed later) or hashes of 448 these names may be a topic for future study.] 450 +-----------+-----------+------+------+ +---------+ +-----+------+ 451 |Src Address|Dst Address|Key ID|Cookie|-->| | |Final|Final | 452 +-----------+-----------+------+------+ | Session | |Index|Key ID| 453 | | | | | Key ID | +-----+------+ 454 \|/ \|/ \|/ \|/ | List | | | 455 ************************************* +---------+ \|/ \|/ 456 * COMPUTE HASH * ******************* 457 ************************************* *COMPUTE SIGNATURE* 458 | Index n ******************* 459 \|/ | 460 +--------+ | 461 | Next | \|/ 462 | Key ID | +-----------+ 463 +--------+ | Signature | 464 Index n+1 +-----------+ 466 Figure 3: Constructing the Key List 468 Figure 3 shows how the autokey list and autokey values are computed. 469 The key IDs used in the autokey list consists of a sequence starting 470 with a random 32-bit nonce (autokey seed) equal to or greater than 471 the pivot as the first key ID. The first autokey is computed as 472 above using the given cookie and autokey seed and assigned index 0. 473 The first 32 bits of the result in network byte order become the next 474 key ID. The MD5 hash of the autokey is the key value saved in the 475 key cache along with the key ID. The first 32 bits of the key become 476 the key ID for the next autokey assigned index 1. 478 Operations continue to generate the entire list. It may happen that 479 a newly generated key ID is less than the pivot or collides with 480 another one already generated (birthday event). When this happens, 481 which occurs only rarely, the key list is terminated at that point. 482 The lifetime of each key is set to expire one poll interval after its 483 scheduled use. In the reference implementation, the list is 484 terminated when the maximum key lifetime is about one hour, so for 485 poll intervals above one hour a new key list containing only a single 486 entry is regenerated for every poll. 488 +------------------+ 489 | NTP Header and | 490 | Extension Fields | 491 +------------------+ 492 | | 493 \|/ \|/ +---------+ 494 **************** +--------+ | Session | 495 * COMPUTE HASH *<---| Key ID |<---| Key ID | 496 **************** +--------+ | List | 497 | | +---------+ 498 \|/ \|/ 499 +----------------------------------+ 500 | Message Authenticator Code (MAC) | 501 +----------------------------------+ 503 Figure 4: Transmitting Messages 505 The index of the last autokey in the list is saved along with the key 506 ID for that entry, collectively called the autokey values. The 507 autokey values are then signed for use later. The list is used in 508 reverse order as shown in Figure 4, so that the first autokey used is 509 the last one generated. 511 The Autokey protocol includes a message to retrieve the autokey 512 values and verify the signature, so that subsequent packets can be 513 validated using one or more hashes that eventually match the last key 514 ID (valid) or exceed the index (invalid). This is called the autokey 515 test in the following and is done for every packet, including those 516 with and without extension fields. In the reference implementation 517 the most recent key ID received is saved for comparison with the 518 first 32 bits in network byte order of the next following key value. 519 This minimizes the number of hash operations in case a single packet 520 is lost. 522 5. Autokey Protocol Overview 524 The Autokey protocol includes a number of request/response exchanges 525 that must be completed in order. In each exchange a client sends a 526 request message with data and expects a server response message with 527 data. Requests and responses are contained in extension fields, one 528 request or response in each field, as described later. An NTP packet 529 can contain one request message and one or more response messages. 530 Following is a list of these messages. 532 o Parameter exchange. The request includes the client host name and 533 status word; the response includes the server host name and status 534 word. The status word specifies the digest/signature scheme to 535 use and the identity schemes supported. 537 o Certificate exchange. The request includes the subject name of a 538 certificate; the response consists of a signed certificate with 539 that subject name. If the issuer name is not the same as the 540 subject name, it has been signed by a host one step closer to a 541 trusted host, so certificate retrieval continues for the issuer 542 name. If it is trusted and self-signed, the trail concludes at 543 the trusted host. If nontrusted and self-signed, the host 544 certificate has not yet been signed, so the trail temporarily 545 loops. Completion of this exchange lights the VAL bit as 546 described below. 548 o Identity exchange. The certificate trail is generally not 549 considered sufficient protection against man-in-the-middle attacks 550 unless additional protection such as the proof-of-possession 551 scheme described in [RFC2875] is available, but this is expensive 552 and requires servers to retain state. Autokey can use one of the 553 challenge/response identity schemes described in Appendix B. 554 Completion of this exchange lights the IFF bit as described below. 556 o Cookie exchange. The request includes the public key of the 557 server. The response includes the server cookie encrypted with 558 this key. The client uses this value when constructing the key 559 list. Completion of this exchange lights the COOK bit as 560 described below. 562 o Autokey exchange. The request includes either no data or the 563 autokey values in symmetric modes. The response includes the 564 autokey values of the server. These values are used to verify the 565 autokey sequence. Completion of this exchange lights the AUT bit 566 as described below. 568 o Sign exchange. This exchange is executed only when the client has 569 synchronized to a proventic source. The request includes the 570 self-signed client certificate. The server acting as CA 571 interprets the certificate as a X.509v3 certificate request. It 572 extracts the subject, issuer, and extension fields, builds a new 573 certificate with these data along with its own serial number and 574 expiration time, then signs it using its own private key and 575 includes it in the response. The client uses the signed 576 certificate in its own role as server for dependent clients. 577 Completion of this exchange lights the SIGN bit as described 578 below. 580 o Leapseconds exchange. This exchange is executed only when the 581 client has synchronized to a proventic source. This exchange 582 occurs when the server has the leapseconds values, as indicated in 583 the host status word. If so, the client requests the values and 584 compares them with its own values, if available. If the server 585 values are newer than the client values, the client replaces its 586 own with the server values. The client, acting as server, can now 587 provide the most recent values to its dependent clients. In 588 symmetric mode, this results in both peers having the newest 589 values. Completion of this exchange lights the LPT bit as 590 described below. 592 Once the certificates and identity have been validated, subsequent 593 packets are validated by digital signatures and the autokey sequence. 594 The association is now proventic with respect to the downstratum 595 trusted host, but is not yet selectable to discipline the system 596 clock. The associations accumulate time values and the mitigation 597 algorithms continue in the usual way. When these algorithms have 598 culled the falsetickers and cluster outlyers and at least three 599 survivors remain, the system clock has been synchronized to a 600 proventic source. 602 The time values for truechimer sources form a proventic partial 603 ordering relative to the applicable signature timestamps. This 604 raises the interesting issue of how to mitigate between the 605 timestamps of different associations. It might happen, for instance, 606 that the timestamp of some Autokey message is ahead of the system 607 clock by some presumably small amount. For this reason, timestamp 608 comparisons between different associations and between associations 609 and the system clock are avoided, except in the NTP intersection and 610 clustering algorithms and when determining whether a certificate has 611 expired. 613 6. NTP Secure Groups 615 NTP secure groups are used to define cryptographic compartments and 616 security hierarchies. A secure group consists of a number of hosts 617 dynamically assembled as a forest with roots the trusted hosts (THs) 618 at the lowest stratum of the group. The THs do not have to be, but 619 often are, primary (stratum 1) servers. A trusted authority (TA), 620 not necessarily a group host, generates private identity keys for 621 servers and public identity keys for clients at the leaves of the 622 forest. The TA deploys the server keys to the THs and other 623 designated servers using secure means and posts the client keys on a 624 public web site. 626 For Autokey purposes all hosts belonging to a secure group have the 627 same group name but different host names, not necessarily related to 628 the DNS names. The group name is used in the subject and issuer 629 fields of the TH certificates; the host name is used in these fields 630 for other hosts. Thus, all host certificates are self-signed. 631 During the Autokey protocol a client requests the server to sign its 632 certificate and caches the result. A certificate trail is 633 constructed by each host, possibly via intermediate hosts and ending 634 at a TH. Thus, each host along the trail retrieves the entire trail 635 from its server(s) and provides this plus its own signed certificates 636 to its clients. 638 Secure groups can be configured as hierarchies where a TH of one 639 group can be a client of one or more other groups operating at a 640 lower stratum. In one scenario, THs for groups RED and GREEN can be 641 cryptographically distinct, but both be clients of group BLUE 642 operating at a lower stratum. In another scenario, THs for group 643 CYAN can be clients of multiple groups YELLOW and MAGENTA, both 644 operating at a lower stratum. There are many other scenarios, but 645 all must be configured to include only acyclic certificate trails. 647 In Figure 5, the Alice group consists of THs Alice, which is also the 648 TA, and Carol. Dependent servers Brenda and Denise have configured 649 Alice and Carol, respectively, as their time sources. Stratum 3 650 server Eileen has configured both Brenda and Denise as her time 651 sources. Public certificates are identified by the subject and 652 signed by the issuer. Note that the server group keys have been 653 previously installed on Brenda and Denise and the client group keys 654 installed on all machines. 656 +-------------+ +-------------+ +-------------+ 657 | Alice Group | | Brenda | | Denise | 658 | Alice | | | | | 659 | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 660 Certificate | | Alice | | | | Brenda| | | | Denise| | 661 +-+-+-+-+-+ | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 662 | Subject | | | Alice*| 1 | | | Alice | 4 | | | Carol | 4 | 663 +-+-+-+-+-+ | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 664 | Issuer | S | | | | | | 665 +-+-+-+-+-+ | +=======+ | | +-+-+-+-+ | | +-+-+-+-+ | 666 | ||Alice|| 3 | | | Alice | | | | Carol | | 667 Group Key | +=======+ | | +-+-+-+-+ | | +-+-+-+-+ | 668 +=========+ +-------------+ | | Alice*| 2 | | | Carol*| 2 | 669 || Group || S | Alice Group | | +-+-+-+-+ | | +-+-+-+-+ | 670 +=========+ | Carol | | | | | 671 | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 672 S = step | | Carol | | | | Brenda| | | | Denise| | 673 * = trusted | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 674 | | Carol*| 1 | | | Brenda| 1 | | | Denise| 1 | 675 | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | 676 | | | | | | 677 | +=======+ | | +=======+ | | +=======+ | 678 | ||Alice|| 3 | | ||Alice|| 3 | | ||Alice|| 3 | 679 | +=======+ | | +=======+ | | +=======+ | 680 +-------------+ +-------------+ +-------------+ 681 Stratum 1 Stratum 2 683 +---------------------------------------------+ 684 | Eileen | 685 | | 686 | +-+-+-+-+ +-+-+-+-+ | 687 | | Eileen| | Eileen| | 688 | +-+-+-+-+ +-+-+-+-+ | 689 | | Brenda| 4 | Carol | 4 | 690 | +-+-+-+-+ +-+-+-+-+ | 691 | | 692 | +-+-+-+-+ +-+-+-+-+ | 693 | | Alice | | Carol | | 694 | +-+-+-+-+ +-+-+-+-+ | 695 | | Alice*| 2 | Carol*| 2 | 696 | +-+-+-+-+ +-+-+-+-+ | 697 | | 698 | +-+-+-+-+ +-+-+-+-+ | 699 | | Brenda| | Denise| | 700 | +-+-+-+-+ +-+-+-+-+ | 701 | | Alice | 2 | Carol | 2 | 702 | +-+-+-+-+ +-+-+-+-+ | 703 | | 704 | +-+-+-+-+ | 705 | | Eileen| | 706 | +-+-+-+-+ | 707 | | Eileen| 1 | 708 | +-+-+-+-+ | 709 | | 710 | +=======+ | 711 | ||Alice|| 3 | 712 | +=======+ | 713 +---------------------------------------------+ 714 Stratum 3 716 Figure 5: NTP Secure Groups 718 The steps in hiking the certificate trails and verifying identity are 719 as follows. Note the step number in the description matches the step 720 number in the figure. 722 1. The girls start by loading the host key, sign key, self-signed 723 certificate and group key. Each client and server acting as a 724 client starts the Autokey protocol by retrieving the server host 725 name and digest/signature. This is done using the ASSOC exchange 726 described later. 728 2. They continue to load certificates recursively until a self- 729 signed trusted certificate is found. Brenda and Denise 730 immediately find trusted certificates for Alice and Carol, 731 respectively, but Eileen will loop because neither Brenda nor 732 Denise have their own certificates signed by either Alice or 733 Carol. This is done using the CERT exchange described later. 735 3. Brenda and Denise continue with the selected identity schemes to 736 verify that Alice and Carol have the correct group key previously 737 generated by Alice. This is done using one of the identity 738 schemes IFF, GQ or MV described later. If this succeeds, each 739 continues in step 4. 741 4. Brenda and Denise present their certificates for signature using 742 the SIGN exchange described later. If this succeeds, either or 743 both Brenda and Denise can now provide these signed certificates 744 to Eileen, which may be looping in step 2. Eileen can now verify 745 the trail via either Brenda or Denise to the trusted certificates 746 for Alice and Carol. Once this is done, Eileen can complete the 747 protocol just as Brenda and Denise. 749 For various reasons it may be convenient for a server to have client 750 keys for more than one group. For example, Figure 6 shows three 751 secure groups Alice, Helen and Carol arranged in a hierarchy. Hosts 752 A, B, C and D belong to Alice with A and B her THs. Hosts R and S 753 belong to Helen with R her TH. Hosts X and Y belong to Carol withi X 754 her TH. Note that the TH for a group is always the lowest stratum 755 and that the hosts of the combined groups form an acyclic graph. 756 Note also that the certificate trail for each group terminates on a 757 TH for that group. 759 ***** ***** @@@@@ 760 Stratum 1 * A * * B * @ R @ 761 ***** ***** @@@@@ 762 \ / / 763 \ / / 764 ***** @@@@@ ********* 765 2 * C * @ S @ * Alice * 766 ***** @@@@@ ********* 767 / \ / 768 / \ / @@@@@@@@@ 769 ***** ##### @ Helen @ 770 3 * D * # X # @@@@@@@@@ 771 ***** ##### 772 / \ ######### 773 / \ # Carol # 774 ##### ##### ######### 775 4 # Y # # Z # 776 ##### ##### 778 Figure 6: Hierarchical Overlapping Groups 780 The intent of the scenario is to provide security separation, so that 781 servers cannot masquerade as in other groups and clients cannot 782 masquerade as servers. Assume for example that Alice and Helen 783 belong to national standards laboratories and their server keys are 784 used to confirm identity between members of each group. Carol is a 785 prominent corporation receiving standards products and requiring 786 cryptographic authentication. Perhaps under contract, host X 787 belonging to Carol has client keys for both Alice and Helen and 788 server keys for Carol. The Autokey protocol operates for each group 789 separately while preserving security separation. Host X can prove 790 identity in Carol to clients Y and Z, but cannot prove to anybody 791 that it belongs to either Alice or Helen. 793 7. Identity Schemes 795 A digital signature scheme provides secure server authentication, but 796 it does not provide protection against masquerade, unless the server 797 identity is verified by other means. The PKI model requires a server 798 to prove identity to the client by a certificate trail, but 799 independent means such as a driver's license are required for a CA to 800 sign the server certificate. While Autokey supports this model by 801 default, in a hierarchical ad-hoc network, especially with server 802 discovery schemes like NTP Manycast, proving identity at each rest 803 stop on the trail must be an intrinsic capability of Autokey itself. 805 While the identity scheme described in [RFC2875] is based on a 806 ubiquitous Diffie-Hellman infrastructure, it is expensive to generate 807 and use when compared to others described in Appendix B. In 808 principle, an ordinary public key scheme could be devised for this 809 purpose, but the most stringent Autokey design requires that every 810 challenge, even if duplicated, results in a different acceptable 811 response. 813 1. The scheme must have a relatively long lifetime, certainly longer 814 than a typical certificate, and have no specific lifetime or 815 expiration date. At the time the scheme is used the host has not 816 yet synchronized to a proventic source, so the scheme cannot 817 depend time.. 819 2. As the scheme can be used many times where the data might be 820 exposed to potential intruders, the data must be either nonces or 821 encrypted nonces. 823 3. The scheme should allow designated servers to prove identity to 824 designated clients, but not allow clients acting as servers to 825 prove identity to dependent clients. 827 4. To the geatest extent possible, the scheme should represent a 828 zero-knowledge proof; that is, the client should be able to 829 verify the server has the correct group key, but without knowing 830 the key itself. 832 There are five schemes now implemented in the NTPv4 reference 833 implementation to prove identity: (1) private certificate (PC), (2) 834 trusted certificate (TC), (3) a modified Schnorr algorithm (IFF aka 835 Identify Friendly or Foe), (4) a modified Guillou-Quisquater 836 algorithm (GQ), and (5) a modified Mu-Varadharajan algorithm (MV). 837 Not all of these provide the same level of protection and one, TC, 838 provides no protection but is included for comparison. Following is 839 a brief summary description of each; details are given in Appendix B. 841 The PC scheme involves a private certificate as group key. The 842 certificate is distributed to all other group members by secure means 843 and is never revealed outside the group. In effect, the private 844 certificate is used as a symmetric key. This scheme is used 845 primarily for testing and development and is not recommended for 846 regular use and is not considered further in this memo. 848 All other schemes involve a conventional certificate trail as 849 described in [RFC5280]. This is the default scheme when an identity 850 scheme is not required. While the remaining identity schemes 851 incorporate TC, it is not by itself considered further in this memo. 853 The three remaining schemes IFF, GQ and MV involve a 854 cryptographically strong challenge-response exchange where an 855 intruder cannot deduce the server key, even after repeated 856 observations of multiple exchanges. In addition, the MV scheme is 857 properly described as a zero-knowledge proof, because the client can 858 verify the server has the correct group key without either the server 859 or client knowing its value. These schemes start when the client 860 sends a nonce to the server, which then rolls its own nonce, performs 861 a mathematical operation and sends the results to the client. The 862 client performs another mathematical operation and verifies the 863 results are correct. 865 8. Timestamps and Filestamps 867 While public key signatures provide strong protection against 868 misrepresentation of source, computing them is expensive. This 869 invites the opportunity for an intruder to clog the client or server 870 by replaying old messages or originating bogus messages. A client 871 receiving such messages might be forced to verify what turns out to 872 be an invalid signature and consume significant processor resources. 873 In order to foil such attacks, every Autokey message carries a 874 timestamp in the form of the NTP seconds when it was created. If the 875 system clock is synchronized to a proventic source, a signature is 876 produced with valid (nonzero) timestamp. Otherwise, there is no 877 signature and the timestamp is invalid (zero). The protocol detects 878 and discards extension fields with old or duplicate timestamps, 879 before any values are used or signatures are verified. 881 Signatures are computed only when cryptographic values are created or 882 modified, which is by design not very often. Extension fields 883 carrying these signatures are copied to messages as needed, but the 884 signatures are not recomputed. There are three signature types: 886 1. Cookie signature/timestamp. The cookie is signed when created by 887 the server and sent to the client. 889 2. Autokey signature/timestamp. The autokey values are signed when 890 the key list is created. 892 3. Public values signature/timestamp. The public key, certificate 893 and leapsecond values are signed at the time of generation, which 894 occurs when the system clock is first synchronized to a proventic 895 source, when the values have changed and about once per day after 896 that, even if these values have not changed. 898 The most recent timestamp received of each type is saved for 899 comparison. Once a signature with valid timestamp has been received, 900 messages with invalid timestamps or earlier valid timestamps of the 901 same type are discarded before the signature is verified. This is 902 most important in broadcast mode, which could be vulnerable to a 903 clogging attack without this test. 905 All cryptographic values used by the protocol are time sensitive and 906 are regularly refreshed. In particular, files containing 907 cryptographic values used by signature and encryption algorithms are 908 regenerated from time to time. It is the intent that file 909 regenerations occur without specific advance warning and without 910 requiring prior distribution of the file contents. While 911 cryptographic data files are not specifically signed, every file is 912 associated with a filestamp showing the NTP seconds at the creation 913 epoch. 915 Filestamps and timestamps can be compared in any combination and use 916 the same conventions. It is necessary to compare them from time to 917 time to determine which are earlier or later. Since these quantities 918 have a granularity only to the second, such comparisons are ambiguous 919 if the values are in the same second. 921 It is important that filestamps be proventic data; thus, they cannot 922 be produced unless the producer has been synchronized to a proventic 923 source. As such, the filestamps throughout the NTP subnet represent 924 a partial ordering of all creation epochs and serve as means to 925 expunge old data and insure new data are consistent. As the data are 926 forwarded from server to client, the filestamps are preserved, 927 including those for certificate and leapseconds values. Packets with 928 older filestamps are discarded before spending cycles to verify the 929 signature. 931 9. Autokey Operations 933 The NTP protocol has three principal modes of operation: client/ 934 server, symmetric and broadcast and each has its own Autokey program, 935 or dance. Autokey choreography is designed to be nonintrusive and to 936 require no additional packets other than for regular NTP operations. 937 The NTP and Autokey protocols operate simultaneously and 938 independently. When the dance is complete, subsequent packets are 939 validated by the autokey sequence and thus considered proventic as 940 well. Autokey assumes NTP clients poll servers at a relatively low 941 rate, such as once per minute or slower. In particular, it assumes 942 that a request sent at one poll opportunity will normally result in a 943 response before the next poll opportunity; however the protocol is 944 robust against a missed or duplicate response. 946 The server dance was suggested by Steve Kent over lunch some time 947 ago, but considerably modified since that meal. The server keeps no 948 state for each client, but uses a fast algorithm and a 32-bit random 949 private value (server seed) to regenerate the cookie upon arrival of 950 a client packet. The cookie is calculated as the first 32 bits of 951 the autokey computed from the client and server addresses, key ID 952 zero and the server seed as cookie. The cookie is used for the 953 actual autokey calculation by both the client and server and is thus 954 specific to each client separately. 956 In the server dance the client uses the cookie and each key ID on the 957 key list in turn to retrieve the autokey and generate the MAC. The 958 server uses the same values to generate the message digest and 959 verifies it matches the MAC. It then generates the MAC for the 960 response using the same values, but with the client and server 961 addresses interchanged. The client generates the message digest and 962 verifies it matches the MAC. In order to deflect old replays, the 963 client verifies the key ID matches the last one sent. In this dance 964 the sequential structure of the key list is not exploited, but doing 965 it this way simplifies and regularizes the implementation while 966 making it nearly impossible for an intruder to guess the next key ID. 968 In the broadcast dance clients normally do not send packets to the 969 server, except when first starting up. At that time the client runs 970 the server dance to verify the server credentials and calibrate the 971 propagation delay. The dance requires the association ID of the 972 particular server association, since there can be more than one 973 operating in the same server. For this purpose, the server packet 974 includes the association ID in every response message sent and, when 975 sending the first packet after generating a new key list, it sends 976 the autokey values as well. After obtaining and verifying the 977 autokey values, no extension fields are necessary and the client 978 verifies further server packets using the autokey sequence. 980 The symmetric dance is similar to the server dance and requires only 981 a small amount of state between the arrival of a request and 982 departure of the response. The key list for each direction is 983 generated separately by each peer and used independently, but each is 984 generated with the same cookie. The cookie is conveyed in a way 985 similar to the server dance, except that the cookie is a simple 986 nonce. There exists a possible race condition where each peer sends 987 a cookie request before receiving the cookie response from the other 988 peer. In this case each peer winds up with two values, one it 989 generated and one the other peer generated. The ambiguity is 990 resolved simply by computing the working cookie as the EXOR of the 991 two values. 993 Once the autokey dance has completed, it is normally dormant. In all 994 except the broadcast dance, packets are normally sent without 995 extension fields, unless the packet is the first one sent after 996 generating a new key list or unless the client has requested the 997 cookie or autokey values. If for some reason the client clock is 998 stepped, rather than slewed, all cryptographic and time values for 999 all associations are purged and the dances in all associations 1000 restarted from scratch. This insures that stale values never 1001 propagate beyond a clock step. 1003 10. Autokey Protocol Messages 1005 The Autokey protocol data unit is the extension field, one or more of 1006 which can be piggybacked in the NTP packet. An extension field 1007 contains either a request with optional data or a response with 1008 optional data. To avoid deadlocks, any number of responses can be 1009 included in a packet, but only one request. A response is generated 1010 for every request, even if the requestor is not synchronized to a 1011 proventic source, but most contain meaningful data only if the 1012 responder is synchronized to a proventic source. Some requests and 1013 most responses carry timestamped signatures. The signature covers 1014 the entire extension field, including the timestamp and filestamp, 1015 where applicable. Only if the packet has correct format, length and 1016 message digest are cycles spent to verify the signature. 1018 There are currently eight Autokey requests and eight corresponding 1019 responses. The NTP packet format is described in 1020 [I-D.ietf-ntp-ntpv4-proto] and the extension field format used for 1021 these messages is illustrated in Figure 7. 1023 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 1024 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1025 |R|E| Code | Field Type | Length | 1026 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1027 | Association ID | 1028 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1029 | Timestamp | 1030 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1031 | Filestamp | 1032 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1033 | Value Length | 1034 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1035 \ / 1037 / Value \ 1038 \ / 1039 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1040 | Signature Length | 1041 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1042 \ / 1043 / Signature \ 1044 \ / 1045 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1046 \ / 1047 / Padding (if needed) \ 1048 \ / 1049 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1051 Figure 7: NTPv4 Extension Field Format 1053 While each extension field is zero-padded to a 4-octet (word) 1054 boundary, the entire extension is not word-aligned. The Length field 1055 covers the entire extension field, including the Length and Padding 1056 fields. While the minimum field length is 8 octets, a maximum field 1057 length remains to be established. The reference implementation 1058 discards any packet with a field length more than 1024 octets. 1060 One or more extension fields follow the NTP packet header and the 1061 last followed by the MAC. The extension field parser initializes a 1062 pointer to the first octet beyond the NTP packet header and 1063 calculates the number of octets remaining to the end of the packet. 1064 If the remaining length is 20 (128-bit digest plus 4-octet key ID) or 1065 22 (160-bit digest plus 4-octet key ID), the remaining data are the 1066 MAC and parsing is complete. If the remaining length is greater than 1067 22 an extension field is present. If the remaining length is less 1068 than 8 or not a multiple of 4, a format error has occurred and the 1069 packet is discarded; otherwise, the parser increments the pointer by 1070 the extension field length and then uses the same rules as above to 1071 determine whether a MAC is present or another extension field. 1073 In Autokey the 8-bit Field Type field is interpreted as the version 1074 number, currently 2. For future versions values 1-7 have been 1075 reserved for Autokey; other values may be assigned for other 1076 applications. The 6-bit Code field specifies the request or response 1077 operation. There are two flag bits: bit 0 is the Response Flag (R) 1078 and bit 1 is the Error Flag (E); the Reserved field is unused and 1079 should be set to 0. The remaining fields will be described later. 1081 In the most common protocol operations, a client sends a request to a 1082 server with an operation code specified in the Code field and both 1083 the R bit and E bit dim. The server returns a response with the same 1084 operation code in the Code field and lights the R bit. The server 1085 can also light the E bit in case of error. Note that it is not 1086 necessarily a protocol error to send an unsolicited response with no 1087 matching request. If the R bit is dim, the client sets the 1088 Association ID field to the client association ID which the servert 1089 returns for verification. If the two values do not match, the 1090 response is discarded as if never sent. If the R bit is lit, the 1091 Association ID field is set the the server association ID obtained in 1092 the initial protocol exchange. If the Association ID field does not 1093 match any mobilized association ID, the request is discarded as if 1094 never sent. 1096 In some cases not all fields may be present. For requests, until a 1097 client has synchronized to a proventic source, signatures are not 1098 valid. In such cases the Timestamp field and Signature Length field 1099 (which specifies the length of the Signature) are zero and the 1100 Signature field is absent. Some request and error response messages 1101 carry no value or signature fields, so in these messages only the 1102 first two words (8 octests) are present. 1104 The Timestamp and Filestamp words carry the seconds field of an NTP 1105 timestamp. The timestamp establishes the signature epoch of the data 1106 field in the message, while the filestamp establishes the generation 1107 epoch of the file that ultimately produced the data that is signed. 1108 A signature and timestamp are valid only when the signing host is 1109 synchronized to a proventic source; otherwise, the timestamp is zero. 1110 A cryptographic data file can only be generated if a signature is 1111 possible; otherwise, the filestamp is zero, except in the ASSOC 1112 response message, where it contains the server status word. 1114 As in all other TCP/IP protocol designs, all data are sent in network 1115 byte order. Unless specified otherwise in the descriptions to 1116 follow, the data referred to are stored in the Value field. The 1117 Value Length field specifies the length of the data in the Value 1118 field. 1120 10.1. No-Operation 1122 A No-operation request (Code 0) does nothing except return an empty 1123 response which can be used as a crypto-ping. 1125 10.2. Association Message (ASSOC) 1127 An Association Message (Code 1) is used in the parameter exchange to 1128 obtain the host name and status word. The request contains the 1129 client status word in the Filestamp field and the Autokey host name 1130 in the Value field. The response contains the server status word in 1131 the Filestamp field and the Autokey host name in the Value field. 1132 The Autokey host name is not necessarily the DNS host name. A valid 1133 response lights the ENAB bit and possibly others in the association 1134 status word. 1136 When multiple identity schemes are supported, the host status word 1137 determine which ones are available. In server and symmetric modes 1138 the response status word contains bits corresponding to the supported 1139 schemes. In all modes the scheme is selected based on the client 1140 identity parameters which are loaded at startup. 1142 10.3. Certificate Message (CERT) 1144 A Certificate Message (Code 2) is used in the certificate exchange to 1145 obtain a certificate by subject name. The request contains the 1146 subject name; the response contains the certificate encoded in X.509 1147 format with ASN.1 syntax as described in Appendix H. 1149 If the subject name in the response does not match the issuer name, 1150 the exchange continues with the issuer name replacing the subject 1151 name in the request. The exchange continues until a trusted, self- 1152 signed certificate is found and lights the CERT bit in the 1153 association status word. 1155 10.4. Cookie Message (COOKIE) 1157 The Cookie Message (Code 3) is used in server and symmetric modes to 1158 obtain the server cookie. The request contains the host public key 1159 encoded with ASN.1 syntax as described in Appendix H. The response 1160 contains the cookie encrypted by the public key in the request. A 1161 valid response lights the COOKIE bit in the association status word. 1163 10.5. Autokey Message (AUTO) 1165 The Autokey Message (Code 4) is used to obtain the autokey values. 1166 The request contains no value for a client or the autokey values for 1167 a symmetric peer. The response contains two 32-bit words, the first 1168 is the final key ID, while the second is the index of the final key 1169 ID. A valid response lights the AUTO bit in the association status 1170 word. 1172 10.6. Leapseconds Values Message (LEAP) 1174 The Leapseconds Values Message (Cpde 5) is used to obtain the 1175 leapseconds values as parsed from the leapseconds table from NIST. 1176 The request contains no values. The response contains three 32-bit 1177 integers: first the NTP seconds of the latest leap event followed by 1178 the NTP seconds when the latest NIST table expires and then the TAI 1179 offset following the leap event. A valid response lights the LEAP 1180 bit in the association status word. 1182 10.7. Sign Message (SIGN) 1184 The Sign Message (Code 6) requests the server to sign and return a 1185 certificate presented in the request. The request contains the 1186 client certificate encoded in X.509 format with ASN.1 syntax as 1187 described in Appendix H. The response contains the client 1188 certificate signed by the server private key. A valid response 1189 lights the SIGN bit in the association status word. 1191 10.8. Identity Messages (IFF, GQ, MV) 1193 The Identity Messages (Code 7 (IFF), 8 (GQ), or 9 (MV)) contains the 1194 client challenge, usually a 160- or 512-bit nonce. The response 1195 contains the result of the mathematical operation defined in 1196 Appendix B. The Response is encoded in ASN.1 syntax as described in 1197 Appendix H. A valid response lights the VRFY bit in the association 1198 status word. 1200 11. Autokey State Machine 1202 This section describes the formal model of the Autokey state machine, 1203 its state variables and the state transition functions. 1205 11.1. Status Word 1207 The server implements a host status word, while each client 1208 implements an association status word. These words have the format 1209 and content shown in Figure 8. The low order 16 bits of the status 1210 word define the state of the Autokey dance, while the high order 16 1211 bits specify the Numerical Identifier (NID) as generated by the 1212 OpenSSL library of the OID for one of the message digest/signature 1213 encryption schemes defined in [RFC3279]. The NID values for the 1214 digest/signature algorithms defined in RFC 3279 are as follows: 1216 +------------------------+----------------------+-----+ 1217 | Algorithm | OID | NID | 1218 +------------------------+----------------------+-----+ 1219 | pkcs-1 | 1.2.840.113549.1.1 | 2 | 1220 | md2 | 1.2.840.113549.2.2 | 3 | 1221 | md5 | 1.2.840.113549.2.5 | 4 | 1222 | rsaEncryption | 1.2.840.113549.1.1.1 | 6 | 1223 | md2WithRSAEncryption | 1.2.840.113549.1.1.2 | 7 | 1224 | md5WithRSAEncryption | 1.2.840.113549.1.1.4 | 8 | 1225 | id-sha1 | 1.3.14.3.2.26 | 64 | 1226 | sha-1WithRSAEncryption | 1.2.840.113549.1.1.5 | 65 | 1227 | id-dsa-wth-sha1 | 1.2.840.10040.4.3 | 113 | 1228 | id-dsa | 1.2.840.10040.4.1 | 116 | 1229 +------------------------+----------------------+-----+ 1231 Bits 24-31 are reserved for server use, while bits 16-23 are reserved 1232 for client use. In the host portion bits 24-27 specify the available 1233 identity schemes, while bits 28-31 specify the server capabilities. 1234 There are two additional bits implemented separately. 1236 1 2 3 1237 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 1238 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1239 | Digest / Signature NID | Client | Ident | Host | 1240 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1242 Figure 8: Status Word 1244 The host status word is included in the ASSOC request and response 1245 messages. The client copies this word to the association status word 1246 and then lights additional bits as the dance proceeds. Once enabled, 1247 these bits ordinarily never come dark unless a general reset occurs 1248 and the protocol is restarted from the beginning. 1250 The host status bits are defined as follows: 1252 o ENAB (31) Lit if the server implements the Autokey protocol. 1254 o LVAL (30) Lit if the server has installed leapseconds values, 1255 either from the NIST leapseconds file or from another server. 1257 o Bits (28-29) are reserved - always dark. 1259 o Bits 24-27 select which server identity schemes are available. 1260 While specific coding for various schemes is yet to be determined, 1261 the schemes available in the reference implementation and 1262 described in Appendix B include the following: 1264 * none - Trusted Certificate (TC) Scheme (default). 1266 * PC (27) Private Certificate Scheme. 1268 * IFF (26) Schnorr aka Identify-Friendly-or-Foe Scheme. 1270 * GQ (25) Guillard-Quisquater Scheme. 1272 * MV (24) Mu-Varadharajan Scheme. 1274 o The PC scheme is exclusive of any other scheme. Otherwise, the 1275 IFF, GQ and MV bits can be enabled in any combination. 1277 The association status bits are defined as follows: 1279 o CERT (23) Lit when the trusted host certificate and public key are 1280 validated. 1282 o VRFY (22) Lit when the trusted host identity credentials are 1283 confirmed. 1285 o PROV (21) Lit when the server signature is verified using its 1286 public key and identity credentials. Also called the proventic 1287 bit elsewhere in this memo. When enabled, signed values in 1288 subsequent messages are presumed proventic. 1290 o COOK (20) Lit when the cookie is received and validated. When 1291 lit, key lists with nonzero cookies are generated; when dim, the 1292 cookie is zero. 1294 o AUTO (19) Lit when the autokey values are received and validated. 1295 When lit, clients can validate packets without extension fields 1296 according to the autokey sequence. 1298 o SIGN (18) Lit when the host certificate is signed by the server. 1300 o LEAP (17) Lit when the leapseconds values are received and 1301 validated. 1303 o Bit 16 is reserved - always dark. 1305 There are three additional bits: LIST, SYNC and PEER not included in 1306 the association status word. LIST is lit when the key list is 1307 regenerated and dim when the autokey values have been transmitted. 1308 This is necessary to avoid livelock under some conditions. SYNC is 1309 lit when the client has synchronized to a proventic source and never 1310 dim after that. PEER is lit when the server has synchronized, as 1311 indicated in the NTP header, and never dim after that. 1313 11.2. Host State Variables 1315 Following is a list of host state variables. 1317 Host Name - The name of the host, by default the string returned by 1318 the Unix gethostname() library function. In the reference 1319 implementation this is a configurable value. 1321 Host Status Word - This word is initialized when the host first 1322 starts up. The format is described above. 1324 Host Key - The RSA public/private key pair used to encrypt/decrypt 1325 cookies. This is also the default sign key. 1327 Sign Key - The RSA or DSA public/private key pair used to encrypt/ 1328 decrypt signatures when the host key is not used for this purpose. 1330 Sign Digest - The message digest algorithm used to compute the 1331 message digest before encryption. 1333 IFF Parameters - The parameters used in the optional IFF identity 1334 scheme described in Appendix B. 1336 GQ Parameters - The parameters used in the optional GQ identity 1337 scheme described in Appendix B. 1339 MV Parameters - The parameters used in the optional MV identity 1340 scheme described in Appendix B. 1342 Server Seed - The private value hashed with the IP addresses and key 1343 identifier to construct the cookie. 1345 Certificate Information Structure (CIS) - This structure includes 1346 certain information fields from an X.509v3 certificate, together with 1347 the certificate itself. The fields extracted include the subject and 1348 issuer names, subject public key and message digest algorithm 1349 (pointers), and the beginning and end of the valid period in NTP 1350 seconds. 1352 The certificate itself is stored as an extension field in network 1353 byte order so it can be copied intact to the message. The structure 1354 is signed using the sign key and carries the public values timestamp 1355 at signature time and the filestamp of the original certificate file. 1356 The structure is used by the CERT response message and SIGN request 1357 and response messages. 1359 A flags field in the CIS determines the status of the certificate. 1360 The field is encoded as follows: 1362 o TRUST (0x01) - The certificate has been signed by a trusted 1363 issuer. If the certificate is self-signed and contains 1364 "trustRoot" in the Extended Key Usage field, this bit is lit when 1365 the CIS is constructed. 1367 o SIGN (0x02) - The certificate signature has been verified. If the 1368 certificate is self-signed and verified using the contained public 1369 key, this bit is lit when the CIS is constructed. 1371 o VALID (0x04) - The certificate is valid and can be used to verify 1372 signatures. This bit is lit when a trusted certificate has been 1373 found on a valid certificate trail. 1375 o PRIV (0x08) - The certificate is private and not to be revealed. 1376 If the certificate is self-signed and contains "Private" in the 1377 Extended Key Usage field, this bit is lit when the CIS is 1378 constructed. 1380 o ERROR (0x80) - The certificate is defective and not to be used in 1381 any way. 1383 Certificate List - CIS structures are stored on the certificate list 1384 in order of arrival, with the most recently received CIS placed first 1385 on the list. The list is initialized with the CIS for the host 1386 certificate, which is read from the host certificate file. 1387 Additional CIS entries are added to the list as certificates are 1388 obtained from the servers during the certificate exchange. CIS 1389 entries are discarded if overtaken by newer ones. 1391 The following values are stored as an extension field structure in 1392 network byte order so they can be copied intact to the message. They 1393 are used to send some Autokey requests and responses. All but the 1394 Host Name Values structure are signed using the sign key and all 1395 carry the public values timestamp at signature time. 1397 Host Name Values. This is used to send ASSOC request and response 1398 messages. It contains the host status word and host name. 1400 Public Key Values - This is used to send the COOKIE request message. 1401 It contains the public encryption key used for the COOKIE response 1402 message. 1404 Leapseconds Values. This is used to send the LEAP response message. 1405 In contains the leapseconds values in the LEAP message description. 1407 11.3. Client State Variables (all modes) 1409 Following is a list of state variables used by the various dances in 1410 all modes. 1412 Association ID - The association ID used in responses. It is 1413 assigned when the association is mobilized. 1415 Association Status Word - The status word copied from the ASSOC 1416 response; subsequently modified by the state machine. 1418 Subject Name - The server host name copied from the ASSOC response. 1420 Issuer Name - The host name signing the certificate. It is extracted 1421 from the current server certificate upon arrival and used to request 1422 the next host on the certificate trail. 1424 Server Public Key - The public key used to decrypt signatures. It is 1425 extracted from the server host certificate. 1427 Server Message Digest - The digest/signature scheme determined in the 1428 parameter exchange. 1430 Group Key - A set of values used by the identity exchange. It 1431 identifies the cryptographic compartment shared by the server and 1432 client. 1434 Receive Cookie Values - The cookie returned in a COOKIE response, 1435 together with its timestamp and filestamp 1437 Receive Autokey Values - The autokey values returned in an AUTO 1438 response, together with its timestamp and filestamp. 1440 Send Autokey Values - The autokey values with signature and 1441 timestamps. 1443 Key List - A sequence of key IDs starting with the autokey seed and 1444 each pointing to the next. It is computed, timestamped and signed at 1445 the next poll opportunity when the key list becomes empty. 1447 Current Key Number - The index of the entry on the Key List to be 1448 used at the next poll opportunity. 1450 11.4. Protocol State Transitions 1452 The protocol state machine is very simple but robust. The state is 1453 determined by the client status word bits defined above. The state 1454 transitions of the three dances are shown below. The capitalized 1455 truth values represent the client status bits. All bits are 1456 initialized dark and are lit upon the arrival of a specific response 1457 message as detailed above. 1459 11.4.1. Server Dance 1461 The server dance begins when the client sends an ASSOC request to the 1462 server. The clock is updated when PREV is lit and the dance ends 1463 when LEAP is lit. In this dance the autokey values are not used, so 1464 an autokey exchange is not necessary. Note that the SIGN and LEAP 1465 requests are not issued until the client has synchronized to a 1466 proventic source. Subsequent packets without extension fields are 1467 validated by the autokey sequence. This example and others assumes 1468 the IFF identity scheme has been selected in the parameter exchange.. 1470 1 while (1) { 1471 2 wait_for_next_poll; 1472 3 make_NTP_header; 1473 4 if (response_ready) 1474 5 send_response; 1475 6 if (!ENB) /* parameter exchange */ 1476 7 ASSOC_request; 1477 8 else if (!CERT) /* certificate exchange */ 1478 9 CERT_request(Host_Name); 1479 10 else if (!IFF) /* identity exchange */ 1480 11 IFF_challenge; 1481 12 else if (!COOK) /* cookie exchange */ 1482 13 COOKIE_request; 1483 14 else if (!SYNC) /* wait for synchronization */ 1484 15 continue; 1485 16 else if (!SIGN) /* sign exchange */ 1486 17 SIGN_request(Host_Certificate); 1487 18 else if (!LEAP) /* leapsecond values exchange */ 1488 19 LEAP_request; 1489 20 send packet; 1490 21 } 1492 Figure 9: Server Dance 1494 If the server refreshes the private seed, the cookie becomes invalid. 1495 The server responds to an invalid cookie with a crypto_NAK message, 1496 which causes the client to restart the protocol from the beginning. 1498 11.4.2. Broadcast Dance 1500 The broadcast dance is similar to the server dance with the cookie 1501 exchange replaced by the autokey values exchange. The broadcast 1502 dance begins when the client receives a broadcast packet including an 1503 ASSOC response with the server association ID. This mobilizes a 1504 client association in order to proventicate the source and calibrate 1505 the propagation delay. The dance ends when the LEAP bit is lit, 1506 after which the client sends no further packets. Normally, the 1507 broadcast server includes an ASSOC response in each transmitted 1508 packet. However, when the server generates a new key list, it 1509 includes an AUTO response instead. 1511 In the broadcast dance extension fields are used with every packet, 1512 so the cookie is always zero and no cookie exchange is necessary. As 1513 in the server dance, the clock is updated when PREV is lit and the 1514 dance ends when LEAP is lit. Note that the SIGN and LEAP requests 1515 are not issued until the client has synchronized to a proventic 1516 source. Subsequent packets without extension fields are validated by 1517 the autokey sequence. 1519 1 while (1) { 1520 2 wait_for_next_poll; 1521 3 make_NTP_header; 1522 4 if (response_ready) 1523 5 send_response; 1524 6 if (!ENB) /* parameters exchange */ 1525 7 ASSOC_request; 1526 8 else if (!CERT) /* certificate exchange */ 1527 9 CERT_request(Host_Name); 1528 10 else if (!IFF) /* identity exchange */ 1529 11 IFF_challenge; 1530 12 else if (!AUT) /* autokey values exchange */ 1531 13 AUTO_request; 1532 14 else if (!SYNC) /* wait for synchronization */ 1533 15 continue; 1534 16 else if (!SIGN) /* sign exchange */ 1535 17 SIGN_request(Host_Certificate); 1536 18 else if (!LEAP) /* leapsecond values exchange */ 1537 19 LEAP_request; 1538 20 send NTP_packet; 1539 21 } 1541 Figure 10: Broadcast Dance 1543 If a packet is lost and the autokey sequence is broken, the client 1544 hashes the current autokey until either it matches the previous 1545 autokey or the number of hashes exceeds the count given in the 1546 autokey values. If the latter, the client sends an AUTO request to 1547 retrieve the autokey values. If the client receives a crypto-NAK 1548 during the dance, or if the association ID changes, the client 1549 restarts the protocol from the beginning. 1551 11.4.3. Symmetric Dance 1553 The symmetric dance is intricately choreographed. It begins when the 1554 active peer sends an ASSOC request to the passive peer. The passive 1555 peer mobilizes an association and both peers step a three-way dance 1556 where each peer completes a parameter exchange with the other. Until 1557 one of the peers has synchronized to a proventic source (which could 1558 be the other peer) and can sign messages, the other peer loops 1559 waiting for a valid timestamp in the ensuing CERT response. 1561 1 while (1) { 1562 2 wait_for_next_poll; 1563 3 make_NTP_header; 1564 4 if (!ENB) /* parameters exchange */ 1565 5 ASSOC_request; 1566 6 else if (!CERT) /* certificate exchange */ 1567 7 CERT_request(Host_Name); 1568 8 else if (!IFF) /* identity exchange */ 1569 9 IFF_challenge; 1570 10 else if (!COOK && PEER) /* cookie exchange */ 1571 11 COOKIE_request); 1572 12 else if (!AUTO) /* autokey values exchange */ 1573 13 AUTO_request; 1574 14 else if (LIST) /* autokey values response */ 1575 15 AUTO_response; 1576 16 else if (!SYNC) /* wait for synchronization */ 1577 17 continue; 1578 18 else if (!SIGN) /* sign exchange */ 1579 19 SIGN_request; 1580 20 else if (!LEAP) /* leapsecond values exchange */ 1581 21 LEAP_request; 1582 22 send NTP_packet; 1583 23 } 1585 Figure 11: Symmetric Dance 1587 Once a peer has synchronized to a proventic source, it includes 1588 timestamped signatures in its messages. The other peer, which has 1589 been stalled waiting for valid timestamps, now mates the dance. It 1590 retrives the now nonzero cookie using a cookie exchange and then the 1591 updated autokey values using an autokey exchange. 1593 As in the broadcast dance, if a packet is lost and the autokey 1594 sequence broken, the peer hashes the current autokey until either it 1595 matches the previous autokey or the number of hashes exceeds the 1596 count given in the autokey values. If the latter, the client sends 1597 an AUTO request to retrive the autokey values. If the peer receives 1598 a crypto-NAK during the dance, or if the association ID changes, the 1599 peer restarts the protocol from the beginning. 1601 11.5. Error Recovery 1603 The Autokey protocol state machine includes provisions for various 1604 kinds of error conditions that can arise due to missing files, 1605 corrupted data, protocol violations and packet loss or misorder, not 1606 to mention hostile intrusion. This section describes how the 1607 protocol responds to reachability and timeout events which can occur 1608 due to such errors. 1610 A persistent NTP association is mobilized by an entry in the 1611 configuration file, while an ephemeral association is mobilized upon 1612 the arrival of a broadcast or symmetric active packet with no 1613 matching association. Subsequently, a general reset reinitializes 1614 all association variables to the initial state when first mobilized. 1615 In addition, if the association is ephemeral, the association is 1616 demobilized and all resources acquired are returned to the system. 1618 Every NTP association has two variables which maintain the liveness 1619 state of the protocol, the 8-bit reach register and the unreach 1620 counter defined in [I-D.ietf-ntp-ntpv4-proto]. At every poll 1621 interval the reach register is shifted left, the low order bit is 1622 dimmed and the high order bit is lost. At the same time the unreach 1623 counter is incremented by one. If an arriving packet passes all 1624 authentication and sanity checks, the rightmost bit of the reach 1625 register is lit and the unreach counter is set to zero. If any bit 1626 in the reach register is lit, the server is reachable, otherwise it 1627 is unreachable. 1629 When the first poll is sent from an association, the reach register 1630 and unreach counter are set to zero. If the unreach counter reaches 1631 16, the poll interval is doubled. In addition, if association is 1632 persistent, it is demobilized. This reduces the network load for 1633 packets that are unlikely to elicit a response. 1635 At each state in the protocol the client expects a particular 1636 response from the server. A request is included in the NTP packet 1637 sent at each poll interval until a valid response is received or a 1638 general reset occurs, in which case the protocol restarts from the 1639 beginning. A general reset also occurs for an association when an 1640 unrecoverable protocol error occurs. A general reset occurs for all 1641 associations when the system clock is first synchronized or the clock 1642 is stepped or when the server seed is refreshed. 1644 There are special cases designed to quickly respond to broken 1645 associations, such as when a server restarts or refreshes keys. 1646 Since the client cookie is invalidated, the server rejects the next 1647 client request and returns a crypto-NAK packet. Since the crypto-NAK 1648 has no MAC, the problem for the client is to determine whether it is 1649 legitimate or the result of intruder mischief. In order to reduce 1650 the vulnerability in such cases, the crypto-NAK, as well as all 1651 responses, is believed only if the result of a previous packet sent 1652 by the client and not a replay, as confirmed by the NTP on-wire 1653 protocol. While this defense can be easily circumvented by a man-in- 1654 the-middle, it does deflect other kinds of intruder warfare. 1656 There are a number of situations where some event happens that causes 1657 the remaining autokeys on the key list to become invalid. When one 1658 of these situations happens, the key list and associated autokeys in 1659 the key cache are purged. A new key list, signature and timestamp 1660 are generated when the next NTP message is sent, assuming there is 1661 one. Following is a list of these situations: 1663 1. When the cookie value changes for any reason. 1665 2. When the poll interval is changed. In this case the calculated 1666 expiration times for the keys become invalid. 1668 3. If a problem is detected when an entry is fetched from the key 1669 list. This could happen if the key was marked non-trusted or 1670 timed out, either of which implies a software bug. 1672 12. Security Considerations 1674 This section discusses the most obvious security vulnerabilities in 1675 the various Autokey dances. In the following discussion the 1676 cryptographic algorithms and private values themselves are assumed 1677 secure; that is, a brute force cryptanalytic attack will not reveal 1678 the host private key, sign private key, cookie value, identity 1679 parameters, server seed or autokey seed. In addition, an intruder 1680 will not be able to predict random generator values. 1682 12.1. Protocol Vulnerability 1684 While the protocol has not been subjected to a formal analysis, a few 1685 preliminary assertions can be made. In the client/server and 1686 symmetric dances the underlying NTP on-wire protocol is resistant to 1687 lost, duplicate and bogus packets, even if the clock is not 1688 synchronized, so the protocol is not vulnerable to a wiretapper 1689 attack. The on-wire protocol is resistant to replays of both the 1690 client request packet and the server reply packet. A man-in-the- 1691 middle attack, even if it could simulate a valid cookie, could not 1692 prove identity. 1694 In the broadcast dance the client begins with a volley in client/ 1695 server mode to obtain the autokey values and signature, so has the 1696 same protection as in that mode. When continuing in receive-only 1697 mode, a wiretapper cannot produce a key list with valid signed 1698 autokey values. If it replays an old packet, the client will reject 1699 it by the timestamp check. The most it can do is manufacture a 1700 future packet causing clients to repeat the autokey hash operations 1701 until exceeding the maximum key number. If this happens the 1702 broadcast client temporarily reverts to client mode to refresh the 1703 autokey values. 1705 By assumption, a man-in-the-middle attacker that intercepts a packet 1706 cannot break the wire or delay an intercepted packet. If this 1707 assumption is removed, the middleman could intercept a broadcast 1708 packet and replace the data and message digest without detection by 1709 the clients. 1711 As mentioned previously in this memo, the TC identity scheme is 1712 vulnerable to a man-in-the-middle attack where an intruder could 1713 create a bogus certificate trail. To foil this kind of attack, 1714 either the PC, IFF, GQ or MV identity schemes must be used. 1716 A client instantiates cryptographic variables only if the server is 1717 synchronized to a proventic source. A server does not sign values or 1718 generate cryptographic data files unless synchronized to a proventic 1719 source. This raises an interesting issue: how does a client generate 1720 proventic cryptographic files before it has ever been synchronized to 1721 a proventic source? [Who shaves the barber if the barber shaves 1722 everybody in town who does not shave himself?] In principle, this 1723 paradox is resolved by assuming the primary (stratum 1) servers are 1724 proventicated by external phenomenological means. 1726 12.2. Clogging Vulnerability 1728 A self-induced clogging incident cannot happen, since signatures are 1729 computed only when the data have changed and the data do not change 1730 very often. For instance, the autokey values are signed only when 1731 the key list is regenerated, which happens about once an hour, while 1732 the public values are signed only when one of them is updated during 1733 a dance or the server seed is refreshed, which happens about once per 1734 day. 1736 There are two clogging vulnerabilities exposed in the protocol 1737 design: an encryption attack where the intruder hopes to clog the 1738 victim server with needless cryptographic calculations, and a 1739 decryption attack where the intruder attempts to clog the victim 1740 client with needless cryptographic calculations. Autokey uses public 1741 key cryptography and the algorithms that perform these functions 1742 consume significant resources. 1744 In client/server and peer dances an encryption hazard exists when a 1745 wiretapper replays prior cookie request messages at speed. There is 1746 no obvious way to deflect such attacks, as the server retains no 1747 state between requests. Replays of cookie request or response 1748 messages are detected and discarded by the client on-wire protocol. 1750 In broadcast mode a client a decryption hazard exists when a 1751 wiretapper replays autokey response messages at speed. Once 1752 synchronized to a proventic source, a legitimate extension field with 1753 timestamp the same as or earlier than the most recently received of 1754 that type is immediately discarded. This foils a man-in-the-middle 1755 cut-and-paste attack using an earlier response, for example. A 1756 legitimate extension field with timestamp in the future is unlikely, 1757 as that would require predicting the autokey sequence. However, this 1758 causes the client to refresh and verify the autokey values and 1759 signature. 1761 A determined attacker can destabilize the on-wire protocol or an 1762 Autokey dance in various ways by replaying old messages before the 1763 client or peer has synchronized for the first time. For instance, 1764 replaying an old symmetric mode message before the peers have 1765 synchronize will prevent the peers from ever synchronizing. 1766 Replaying out of order Autokey messages in any mode during a dance 1767 could prevent the dance from ever completing. There is nothing new 1768 in these kinds of attack; a similar vulnerabily even exists in TCP. 1770 13. IANA Considerations 1772 This document has no IANA Actions. 1774 14. References 1776 14.1. Normative References 1778 [I-D.ietf-ntp-ntpv4-proto] 1779 Kasch, W., Mills, D., and J. Burbank, "Network Time 1780 Protocol Version 4 Protocol And Algorithms Specification", 1781 draft-ietf-ntp-ntpv4-proto-13 (work in progress), 1782 October 2009. 1784 14.2. Informative References 1786 [DASBUCH] Mills, D., "Computer Network Time Synchronization - the 1787 Network Time Protocol", 2006. 1789 [GUILLOU] Guillou, L. and J. Quisquatar, "A "paradoxical" identity- 1790 based signature scheme resulting from zero-knowledge", 1791 1990. 1793 [MV] Mu, Y. and V. Varadharajan, "Robust and secure 1794 broadcasting", 2001. 1796 [RFC1305] Mills, D., "Network Time Protocol (Version 3) 1797 Specification, Implementation", RFC 1305, March 1992. 1799 [RFC2402] Kent, S. and R. Atkinson, "IP Authentication Header", 1800 RFC 2402, November 1998. 1802 [RFC2406] Kent, S. and R. Atkinson, "IP Encapsulating Security 1803 Payload (ESP)", RFC 2406, November 1998. 1805 [RFC2408] Maughan, D., Schneider, M., and M. Schertler, "Internet 1806 Security Association and Key Management Protocol 1807 (ISAKMP)", RFC 2408, November 1998. 1809 [RFC2412] Orman, H., "The OAKLEY Key Determination Protocol", 1810 RFC 2412, November 1998. 1812 [RFC2510] Adams, C. and S. Farrell, "Internet X.509 Public Key 1813 Infrastructure Certificate Management Protocols", 1814 RFC 2510, March 1999. 1816 [RFC2522] Karn, P. and W. Simpson, "Photuris: Session-Key Management 1817 Protocol", RFC 2522, March 1999. 1819 [RFC2875] Prafullchandra, H. and J. Schaad, "Diffie-Hellman Proof- 1820 of-Possession Algorithms", RFC 2875, July 2000. 1822 [RFC3279] Bassham, L., Polk, W., and R. Housley, "Algorithms and 1823 Identifiers for the Internet X.509 Public Key 1824 Infrastructure Certificate and Certificate Revocation List 1825 (CRL) Profile", RFC 3279, April 2002. 1827 [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., 1828 Housley, R., and W. Polk, "Internet X.509 Public Key 1829 Infrastructure Certificate and Certificate Revocation List 1830 (CRL) Profile", RFC 5280, May 2008. 1832 [SCHNORR] Schnorr, C., "Efficient signature generation for smart 1833 cards", 1991. 1835 [STINSON] Stinson, D., "Cryptography - Theory and Practice", 1995. 1837 Appendix A. Timestamps, Filestamps and Partial Ordering 1839 When the host starts, it reads the host key and host certificate 1840 files, which are required for continued operation. It also reads the 1841 sign key and leapseconds values, when available. When reading these 1842 files the host checks the file formats and filestamps for validity; 1843 for instance, all filestamps must be later than the time the UTC 1844 timescale was established in 1972 and the certificate filestamp must 1845 not be earlier than its associated sign key filestamp. At the time 1846 the files are read the host is not synchronized, so it cannot 1847 determine whether the filestamps are bogus other than these simple 1848 checks. It must not produce filestamps or timestamps until 1849 synchronized to a proventic source. 1851 In the following the relation A --> B is Lamport's "happens before" 1852 relation, which is true if event A happens before event B. When 1853 timestamps are compared to timestamps, the relation is false if A 1854 <--> B; that is, false if the events are simultaneous. For 1855 timestamps compared to filestamps and filestamps compared to 1856 filestamps, the relation is true if A <--> B. Note that the current 1857 time plays no part in these assertions except in (6) below; however, 1858 the NTP protocol itself insures a correct partial ordering for all 1859 current time values. 1861 The following assertions apply to all relevant responses: 1863 1. The client saves the most recent timestamp T0 and filestamp F0 1864 for the respective signature type. For every received message 1865 carrying timestamp T1 and filestamp F1, the message is discarded 1866 unless T0 --> T1 and F0 --> F1. The requirement that T0 --> T1 1867 is the primary defense against replays of old messages. 1869 2. For timestamp T and filestamp F, F --> T; that is, the filestamp 1870 must happen before the timestamp. If not, this could be due to a 1871 file generation error or a significant error in the system clock 1872 time. 1874 3. For sign key filestamp S, certificate filestamp C, cookie 1875 timestamp D and autokey timestamp A, S --> C --> D --> A; that 1876 is, the autokey must be generated after the cookie, the cookie 1877 after the certificate and the certificate after the sign key. 1879 4. For sign key filestamp S and certificate filestamp C specifying 1880 begin time B and end time E, S --> C--> B --> E; that is, the 1881 valid period must not be retroactive. 1883 5. A certificate for subject S signed by issuer I and with filestamp 1884 C1 obsoletes, but does not necessarily invalidate, another 1885 certificate with the same subject and issuer but with filestamp 1886 C0, where C0 --> C1. 1888 6. A certificate with begin time B and end time E is invalid and can 1889 not be used to verify signatures if t --> B or E --> t, where t 1890 is the current proventic time. Note that the public key 1891 previously extracted from the certificate continues to be valid 1892 for an indefinite time. This raises the interesting possibility 1893 where a truechimer server with expired certificate or a 1894 falseticker with valid certificate are not detected until the 1895 client has synchronized to a proventic source. 1897 Appendix B. Identity Schemes 1899 There are five identity schemes in the NTPv4 reference 1900 implementation: (1) private certificate (PC), (2) trusted certificate 1901 (TC), (3) a modified Schnorr algorithm (IFF - Identify Friend or 1902 Foe), (4) a modified Guillou-Quisquater algorithm (GQ), and (5) a 1903 modified Mu-Varadharajan algorithm (MV). 1905 The PC scheme is intended for testing and development and not 1906 recommended for general use. The TC scheme uses a certificate trail, 1907 but not an identity scheme. The IFF, GQ and MV identity schemes use 1908 a cryptographically strong challenge-response exchange where an 1909 intruder cannot learn the group key, even after repeated observations 1910 of multiple exchanges. These schemes begin when the client sends a 1911 nonce to the server, which then rolls its own nonce, performs a 1912 mathematical operation and sends the results to the client. The 1913 client performs a second mathematical operation to prove the server 1914 has the same group key as the client. 1916 Appendix C. Private Certificate (PC) Scheme 1918 The PC scheme shown in Figure 12 uses a private certificate as the 1919 group key. 1921 Trusted 1922 Authority 1923 Secure +-------------+ Secure 1924 +--------------| Certificate |-------------+ 1925 | +-------------+ | 1926 | | 1927 \|/ \|/ 1928 +-------------+ +-------------+ 1929 | Certificate | | Certificate | 1930 +-------------+ +-------------+ 1931 Server Client 1933 Figure 12: Private Certificate (PC) Identity Scheme 1935 A certificate is designated private when the X509v3 Extended Key 1936 Usage extension field is present and contains "Private". The private 1937 certificate is distributed to all other group members by secret 1938 means, so in fact becomes a symmetric key. Private certificates are 1939 also trusted, so there is no need for a certificate trail or identity 1940 scheme. 1942 Appendix D. Trusted Certificate (TC) Scheme 1944 All other schemes involve a conventional certificate trail as shown 1945 in Figure 13. 1947 Trusted 1948 Host Host Host 1949 +-----------+ +-----------+ +-----------+ 1950 +--->| Subject | +--->| Subject | +--->| Subject | 1951 | +-----------+ | +-----------+ | +-----------+ 1952 ...---+ | Issuer |---+ | Issuer |---+ | Issuer | 1953 +-----------+ +-----------+ +-----------+ 1954 | Signature | | Signature | | Signature | 1955 +-----------+ +-----------+ +-----------+ 1957 Figure 13: Trusted Certificate (TC) Identity Scheme 1959 As described in RFC-2510 [RFC2510], each certificate is signed by an 1960 issuer one step closer to the trusted host, which has a self-signed 1961 trusted certificate. A certificate is designated trusted when an 1962 X509v3 Extended Key Usage extension field is present and contains 1963 "trustRoot". If no identity scheme is specified in the parameter 1964 exchange, this is the default scheme. 1966 Appendix E. Schnorr (IFF) Identity Scheme 1968 The IFF scheme is useful when the group key is concealed, so that 1969 client keys need not be protected. The primary disadvantage is that 1970 when the server key is refreshed all hosts must update the client 1971 key. The scheme shown in Figure 14 involves a set of public 1972 parameters and a group key including both private and public 1973 components. The public component is the client key. 1975 Trusted 1976 Authority 1977 +------------+ 1978 | Parameters | 1979 Secure +------------+ Insecure 1980 +-------------| Group Key |-----------+ 1981 | +------------+ | 1982 \|/ \|/ 1983 +------------+ Challenge +------------+ 1984 | Parameters |<------------------------| Parameters | 1985 +------------+ +------------+ 1986 | Group Key |------------------------>| Client Key | 1987 +------------+ Response +------------+ 1988 Server Client 1990 Figure 14: Schnorr (IFF) Identity Scheme 1992 By happy coincidence, the mathematical principles on which IFF is 1993 based are similar to DSA. The scheme is a modification an algorithm 1994 described in [SCHNORR] and [STINSON] p. 285. The parameters are 1995 generated by routines in the OpenSSL library, but only the moduli p, 1996 q and generator g are used. The p is a 512-bit prime, g a generator 1997 of the multiplicative group Z_p* and q a 160-bit prime that divides 1998 (p-1) and is a qth root of 1 mod p; that is, g^q = 1 mod p. The TA 1999 rolls a private random group key b (0 < b < q), then computes public 2000 client key v = g^(q-b) mod p. The TA distributes (p, q, g, b) to all 2001 servers using secure means and (p, q, g, v) to all clients not 2002 necessarily using secure means. 2004 The TA hides IFF parameters and keys in an OpenSSL DSA cuckoo 2005 structure. The IFF parameters are identical to the DSA parameters, 2006 so the OpenSSL library can be used directly. The structure shown in 2007 FigureFigure 15 is written to a file as a DSA private key encoded in 2008 PEM. Unused structure members are set to one. 2010 +----------------------------------+-------------+ 2011 | IFF | DSA | Item | Include | 2012 +=========+==========+=============+=============+ 2013 | p | p | modulus | all | 2014 +---------+----------+-------------+-------------+ 2015 | q | q | modulus | all | 2016 +---------+----------+-------------+-------------+ 2017 | g | g | generator | all | 2018 +---------+----------+-------------+-------------+ 2019 | b | priv_key | group key | server | 2020 +---------+----------+-------------+-------------+ 2021 | v | pub_key | client key | client | 2022 +---------+----------+-------------+-------------+ 2024 Figure 15: IFF Identity Scheme Structure 2026 Alice challenges Bob to confirm identity using the following protocol 2027 exchange. 2029 1. Alice rolls random r (0 < r < q) and sends to Bob. 2031 2. Bob rolls random k (0 < k < q), computes y = k + br mod q and x = 2032 g^k mod p, then sends (y, hash(x)) to Alice. 2034 3. Alice computes z = g^y * v^r mod p and verifies hash(z) equals 2035 hash(x). 2037 If the hashes match, Alice knows that Bob has the group key b. 2038 Besides making the response shorter, the hash makes it effectively 2039 impossible for an intruder to solve for b by observing a number of 2040 these messages. The signed response binds this knowledge to Bob's 2041 private key and the public key previously received in his 2042 certificate. 2044 Appendix F. Guillard-Quisquater (GQ) Identity Scheme 2046 The GQ scheme is useful when the server key must be refreshed from 2047 time to time without changing the group key. The NTP utility 2048 programs include the GQ client key in the X509v3 Subject Key 2049 Identifier extension field. The primary disadvantage of the scheme 2050 is that the group key must be protected in both the server and 2051 client. A secondary disadvantage is that when a server key is 2052 refreshed, old extension fields no longer work. The scheme is shown 2053 in Figure 16a involves a set of public parameters and group key used 2054 to generate private server keys and client keys. 2056 Trusted 2057 Authority 2058 +------------+ 2059 | Parameters | 2060 Secure +------------+ Secure 2061 +-------------| Group Key |-----------+ 2062 | +------------+ | 2063 \|/ \|/ 2064 +------------+ Challenge +------------+ 2065 | Parameters |<------------------------| Parameters | 2066 +------------+ +------------+ 2067 | Group Key | | Group Key | 2068 +------------+ Response +------------+ 2069 | Server Key |------------------------>| Client Key | 2070 +------------+ +------------+ 2071 Server Client 2073 Figure 16: Schnorr (IFF) Identity Scheme 2075 By happy coincidence, the mathematical principles on which GQ is 2076 based are similar to RSA. The scheme is a modification of an 2077 algorithm described in [GUILLOU] and [STINSON] p. 300 (with errors). 2078 The parameters are generated by routines in the OpenSSL library, but 2079 only the moduli p and q are used. The 512-bit public modulus is 2080 n=pq, where p and q are secret large primes. The TA rolls random 2081 large prime b (0 < b < n) and distributes (n, b) to all group servers 2082 and clients using secure means, since an intruder in possession of 2083 these values could impersonate a legitimate server. The private 2084 server key and public client key are constructed later. 2086 The TA hides GQ parameters and keys in an OpenSSL RSA cuckoo 2087 structure. The GQ parameters are identical to the RSA parameters, so 2088 the OpenSSL library can be used directly. When generating a 2089 certificate, the server rolls random server key u (0 < u < n) and 2090 client key its inverse obscured by the group key v = (u^-1)^b mod n. 2091 These values replace the private and public keys normally generated 2092 by the RSA scheme. The client key is conveyed in a X.509 certificate 2093 extension. The updated GQ structure shown in Figure 17 is written as 2094 an RSA private key encoded in PEM. Unused structure members are set 2095 to one. 2097 +---------------------------------+-------------+ 2098 | GQ | RSA | Item | Include | 2099 +=========+==========+============+=============+ 2100 | n | n | modulus | all | 2101 +---------+----------+------------+-------------+ 2102 | b | e | group key | all | 2103 +---------+----------+------------+-------------+ 2104 | u | p | server key | server | 2105 +---------+----------+------------+-------------+ 2106 | v | q | client key | client | 2107 +---------+----------+------------+-------------+ 2109 Figure 17: GQ Identity Scheme Structure 2111 Alice challenges Bob to confirm identity using the following 2112 exchange. 2114 1. Alice rolls random r (0 < r < n) and sends to Bob. 2116 2. Bob rolls random k (0 < k < n) and computes y = ku^r mod n and x 2117 = k^b mod n, then sends (y, hash(x)) to Alice. 2119 3. Alice computes z = (v^r)*(y^b) mod n and verifies hash(z) equals 2120 hash(x). 2122 If the hashes match, Alice knows that Bob has the corresponding 2123 server key u. Besides making the response shorter, the hash makes it 2124 effectively impossible for an intruder to solve for u by observing a 2125 number of these messages. The signed response binds this knowledge 2126 to Bob's private key and the client key previously received in his 2127 certificate. 2129 Appendix G. Mu-Varadharajan (MV) Identity Scheme 2131 The MV scheme is perhaps the most interesting and flexible of the 2132 three challenge/response schemes, but is devilishly complicated. It 2133 is most useful when a small number of servers provide synchronization 2134 to a large client population where there might be considerable risk 2135 of compromise between and among the servers and clients. The client 2136 population can be partitioned into a modest number of subgroups, each 2137 associated with an individual client key. 2139 The TA generates an intricate cryptosystem involving encryption and 2140 decryption keys, together with a number of activation keys and 2141 associated client keys. The TA can activate and revoke individual 2142 client keys without changing the client keys themselves. The TA 2143 provides to the servers an encryption key E and partial decryption 2144 keys g-bar and g-hat which depend on the activated keys. The servers 2145 have no additional information and, in particular, cannot masquerade 2146 as a TA. In addition, the TA provides to each client j individual 2147 partial decryption keys x-bar_j and x-hat_j, which do not need to be 2148 changed if the TA activates or deactivates any client key. The 2149 clients have no further information and, in particular, cannot 2150 masquerade as a server or TA. 2152 The scheme uses an encryption algorithm similar to El Gamal 2153 cryptography and a polynomial formed from the expansion of product 2154 terms (x-x_1)(x-x_2)(x-x_3)...(x-x_n), as described in [MV]. The 2155 paper has significant errors and serious omissions. The cryptosystem 2156 is constructed so that, for every encryption key E its inverse is 2157 (g-bar^x-hat_j)(g-hat^x-bar_j) mod p for every j. This remains true 2158 if both quantities are raised to the power k mod p. The difficulty 2159 in finding E is equivalent to the discrete log problem. 2161 The scheme is shown in Figure 18. The TA generates the parameters, 2162 group key, server keys and client keys, one for each client, all of 2163 which must be protected to prevent theft of service. Note that only 2164 the TA has the group key, which is not known to either the servers or 2165 clients. In this sense the MV scheme is a zero-knowledge proof. 2167 Trusted 2168 Authority 2169 +------------+ 2170 | Parameters | 2171 +------------+ 2172 | Group Key | 2173 +------------+ 2174 | Server Key | 2175 Secure +------------+ Secure 2176 +-------------| Client Key |-----------+ 2177 | +------------+ | 2178 \|/ \|/ 2179 +------------+ Challenge +------------+ 2180 | Parameters |<------------------------| Parameters | 2181 +------------+ +------------+ 2182 | Server Key |------------------------>| Client Key | 2183 +------------+ Response +------------+ 2184 Server Client 2186 Figure 18: Mu-Varadharajan (MV) Identity Scheme 2188 The TA hides MV parameters and keys in OpenSSL DSA cuckoo structures. 2190 The MV parameters are identical to the DSA parameters, so the OpenSSL 2191 library can be used directly. The structure shown in the figures 2192 below are written to files as a the fkey encoded in PEM. Unused 2193 structure members are set to one. The Figure 19 shows the data 2194 structure used by the servers, while Figure Figure 20 shows the 2195 client data structure associated with each activation key. 2197 +---------------------------------+-------------+ 2198 | MV | DSA | Item | Include | 2199 +=========+==========+============+=============+ 2200 | p | p | modulus | all | 2201 +---------+----------+------------+-------------+ 2202 | q | q | modulus | server | 2203 +---------+----------+------------+-------------+ 2204 | E | g | private | server | 2205 | | | encrypt | | 2206 +---------+----------+------------+-------------+ 2207 | g-bar | priv_key | public | server | 2208 | | | decrypt | | 2209 +---------+----------+------------+-------------+ 2210 | g-hat | pub_key | public | server | 2211 | | | decrypt | | 2212 +---------+----------+------------+-------------+ 2214 Figure 19: MV Scheme Server Structure 2216 +---------------------------------+-------------+ 2217 | MV | DSA | Item | Include | 2218 +=========+==========+============+=============+ 2219 | p | p | modulus | all | 2220 +---------+----------+------------+-------------+ 2221 | x-bar_j | priv_key | public | client | 2222 | | | decrypt | | 2223 +---------+----------+------------+-------------+ 2224 | x-hat_j | pub_key | public | client | 2225 | | | decrypt | | 2226 +---------+----------+------------+-------------+ 2228 Figure 20: MV Scheme Client Structure 2230 The devil is in the details, which are beyond the scope of this memo. 2231 The steps in generating the cryptosystem activating the keys and 2232 generating the partial decryption keys are in [DASBUCH] page 170 ff. 2234 Alice challenges Bob to confirm identity using the following 2235 exchange. 2237 1. Alice rolls random r (0 < r < q) and sends to Bob. 2239 2. Bob rolls random k (0 < k < q) and computes the session 2240 encryption key E-prime = E^k mod p and partial decryption keys 2241 g-bar-prime = g-bar^k mod p and g-hat-prime = g-hat^k mod p. He 2242 encrypts x = E-prime * r mod p and sends (x, g-bar-prime, g-hat- 2243 prime) to Alice. 2245 3. Alice computes the session decryption key E^-1 = (g-bar-prime)^x- 2246 hat_j (g-hat-prime)^x-bar_j mod p and verifies that r = E^-1 x. 2248 Appendix H. ASN.1 Encoding Rules 2250 Certain value fields in request and response messages contain data 2251 encoded in ASN.1 distinguished encoding rules (DER). The BNF grammar 2252 for each encoding rule is given below along with the OpenSSL routine 2253 used for the encoding in the reference implementation. The object 2254 identifiers for the encryption algorithms and message digest/ 2255 signature encryption schemes are specified in [RFC3279]. The 2256 particular algorithms required for conformance are not specified in 2257 this memo. 2259 Appendix I. COOKIE request, IFF response, GQ response, MV response 2261 The value field of the COOKIE request message contains a sequence of 2262 two integers (n, e) encoded by the i2d_RSAPublicKey() routine in the 2263 OpenSSL distribution. In the request, n is the RSA modulus in bits 2264 and e is the public exponent. 2266 RSAPublicKey ::= SEQUENCE { 2267 n ::= INTEGER, 2268 e ::= INTEGER 2269 } 2271 The IFF and GQ responses contain a sequence of two integers (r, s) 2272 encoded by the i2d_DSA_SIG() routine in the OpenSSL distribution. In 2273 the responses, r is the challenge response and s is the hash of the 2274 private value. 2276 DSAPublicKey ::= SEQUENCE { 2277 r ::= INTEGER, 2278 s ::= INTEGER 2279 } 2280 The MV response contains a sequence of three integers (p, q, g) 2281 encoded by the i2d_DSAparams() routine in the OpenSSL library. In 2282 the response, p is the hash of the encrypted challenge value and (q, 2283 g) is the client portion of the decryption key. 2285 DSAparameters ::= SEQUENCE { 2286 p ::= INTEGER, 2287 q ::= INTEGER, 2288 g ::= INTEGER 2289 } 2291 Appendix J. Certificates 2293 Certificate extension fields are used to convey information used by 2294 the identity schemes. While the semantics of these fields generally 2295 conforms with conventional usage, there are subtle variations. The 2296 fields used by Autokey Version 2 include: 2298 o Basic Constraints. This field defines the basic functions of the 2299 certificate. It contains the string "critical,CA:TRUE", which 2300 means the field must be interpreted and the associated private key 2301 can be used to sign other certificates. While included for 2302 compatibility, Autokey makes no use of this field. 2304 o Key Usage. This field defines the intended use of the public key 2305 contained in the certificate. It contains the string 2306 "digitalSignature,keyCertSign", which means the contained public 2307 key can be used to verify signatures on data and other 2308 certificates. While included for compatibility, Autokey makes no 2309 use of this field. 2311 o Extended Key Usage. This field further refines the intended use 2312 of the public key contained in the certificate and is present only 2313 in self-signed certificates. It contains the string "Private" if 2314 the certificate is designated private or the string "trustRoot" if 2315 it is designated trusted. A private certificate is always 2316 trusted. 2318 o Subject Key Identifier. This field contains the client identity 2319 key used in the GQ identity scheme. It is present only if the GQ 2320 scheme is in use. 2322 The value field contains a X509v3 certificate encoded by the 2323 i2d_X509() routine in the OpenSSL distribution. The encoding follows 2324 the rules stated in [RFC5280], including the use of X509v3 extension 2325 fields. 2327 Certificate ::= SEQUENCE { 2328 tbsCertificate TBSCertificate, 2329 signatureAlgorithm AlgorithmIdentifier, 2330 signatureValue BIT STRING 2331 } 2333 The signatureAlgorithm is the object identifier of the message 2334 digest/signature encryption scheme used to sign the certificate. The 2335 signatureValue is computed by the certificate issuer using this 2336 algorithm and the issuer private key. 2338 TBSCertificate ::= SEQUENCE { 2339 version EXPLICIT v3(2), 2340 serialNumber CertificateSerialNumber, 2341 signature AlgorithmIdentifier, 2342 issuer Name, 2343 validity Validity, 2344 subject Name, 2345 subjectPublicKeyInfo SubjectPublicKeyInfo, 2346 extensions EXPLICIT Extensions OPTIONAL 2347 } 2349 The serialNumber is an integer guaranteed to be unique for the 2350 generating host. The reference implementation uses the NTP seconds 2351 when the certificate was generated. The signature is the object 2352 identifier of the message digest/signature encryption scheme used to 2353 sign the certificate. It must be identical to the 2354 signatureAlgorithm. 2356 CertificateSerialNumber 2357 SET { ::= INTEGER 2358 Validity ::= SEQUENCE { 2359 notBefore UTCTime, 2360 notAfter UTCTime 2361 } 2362 } 2364 The notBefore and notAfter define the period of validity as defined 2365 in Appendix B. 2367 SubjectPublicKeyInfo ::= SEQUENCE { 2368 algorithm AlgorithmIdentifier, 2369 subjectPublicKey BIT STRING 2370 } 2372 The AlgorithmIdentifier specifies the encryption algorithm for the 2373 subject public key. The subjectPublicKey is the public key of the 2374 subject. 2376 Extensions ::= SEQUENCE SIZE (1..MAX) OF Extension 2377 Extension ::= SEQUENCE { 2378 extnID OBJECT IDENTIFIER, 2379 critical BOOLEAN DEFAULT FALSE, 2380 extnValue OCTET STRING 2381 } 2383 SET { 2384 Name ::= SEQUENCE { 2385 OBJECT IDENTIFIER commonName 2386 PrintableString HostName 2387 } 2388 } 2390 For trusted host certificates the subject and issuer HostName is the 2391 NTP name of the group, while for all other host certificates the 2392 subject and issuer HostName is the NTP name of the host. In the 2393 reference implementation if these names are not explicitly specified, 2394 they default to the string returned by the Unix gethostname() routine 2395 (trailing NUL removed). For other than self-signed certificates, the 2396 issuer HostName is the unique DNS name of the host signing the 2397 certificate. 2399 Authors' Addresses 2401 Brian Haberman (editor) 2402 The Johns Hopkins University Applied Physics Laboratory 2403 11100 Johns Hopkins Road 2404 Laurel, MD 20723-6099 2405 US 2407 Phone: +1 443 778 1319 2408 Email: brian@innovationslab.net 2410 Dr. David L. Mills 2411 University of Delaware 2412 Newark, DE 19716 2413 US 2415 Phone: +1 302 831 8247 2416 Email: mills@udel.edu