Figure 2. NTPv4 Autokey Figure 3. Constructing the Key List Figure 4. Transmitting Messages Figure 1. Message Authentication Figure 9. Status Word Figure 5. NTP Secure Groups Figure 8. Identity Exchange Figure 6. Hierarchical Overlapping Groups Figure 7. Multiple Overlapping Groups 1. Introduction A distributed network service requires reliable, ubiquitous and survivable provisions to prevent accidental or malicious attacks on the servers and clients in the network or the values they exchange. Reliability requires that clients can determine that received packets are authentic; that is, were actually sent by the intended server and not manufactured or modified by an intruder. Ubiquity requires that any client can verify the authenticity of any server using only public information. Survivability requires protection from faulty implementations, improper operation and possibly malicious clogging and replay attacks with or without data modification. These requirements are especially stringent with widely distributed network services, since damage due to failures can propagate quickly throughout the network, devastating archives, routing databases and monitoring systems and even bring down major portions of the network. The Network Time Protocol (NTP) contains provisions to cryptographically authenticate individual servers as described in the most recent protocol NTP Version 3 (NTPv3) specification [11]; however, that specification does not provide a scheme for the distribution of cryptographic keys, nor does it provide for the retrieval of cryptographic media that reliably bind the server identification credentials to the associated private keys and related public values. However, conventional key agreement and digital signatures with large client populations can cause significant performance degradations, especially in time critical applications such as NTP. In addition, there are problems unique to NTP in the interaction between the authentication and synchronization functions, since each requires the other. This report describes a cryptographically sound and efficient methodology for use in NTP and similar distributed protocols. As demonstrated in the reports and briefings cited in the references at the end of this report, there is a place for the public key infrastructure (PKI) and related schemes, but none of these schemes alone satisfies the requirements of the NTP security model. The various key agreement schemes [8], [13], [5] proposed by the IETF require per-association state variables, which contradicts the principles of the remote procedure call (RPC) paradigm in which servers keep no state for a possibly large client population. An evaluation of the PKI model and algorithms as implemented in the OpenSSL library leads to the conclusion that any scheme requiring every NTP packet to carry a PKI digital signature would result in unacceptably poor timekeeping performance. A revised security model and authentication scheme called Autokey was proposed in earlier reports [10], [9]. It is based on a combination of PKI and a pseudo-random sequence generated by repeated hashes of a cryptographic value involving both public and private components. This scheme has been implemented, tested and widely deployed in the Internet of today. A detailed description of the security model, design principles and implementation experience is presented in this report. Additional information about NTP, including executive summaries, briefings and a bibliography can be found on the NTP project page linked from www.ntp.org. The NTPv4 reference implementation for Unix and Windows, including sources and documentation in HTML, is available from the NTP repository at the same site. All of the features described in this report, including support for both IPv4 and IPv6 address families, are included in the current NTPv4 version at that repository. The reference implementation is not intended to become part of any standard that may be evolved from this report, but to serve as an example of how the procedures described in this report can be implemented in a practical way. 2. NTP Security Model NTP security requirements are even more stringent than most other distributed services. First, the operation of the authentication mechanism and the time synchronization mechanism are inextricably intertwined. Reliable time synchronization requires cryptographic keys which are valid only over designated time intervals; but, time intervals can be enforced only when participating servers and clients are reliably synchronized to UTC. In addition, the NTP subnet is hierarchical by nature, so time and trust flow from the primary servers at the root through secondary servers to the clients at the leaves. A client can claim authentic to dependent applications only if all servers on the path to the primary servers are bone-fide authentic. In order to emphasize this requirement, in this report the notion of “authentic” is replaced by “proventic”, a noun new to English and derived from provenance, as in the provenance of a painting. Having abused the language this far, the suffixes fixable to the various noun and verb derivatives of authentic will be adopted for proventic as well. In NTP each server authenticates the next lower stratum servers and proventicates (authenticates by induction) the lowest stratum (primary) servers. Serious computer linguists would correctly interpret the proventic relation as the transitive closure of the authentic relation. It is important to note that the notion of proventic does not necessarily imply the time is correct. A NTP client mobilizes a number of concurrent associations with different servers and uses a crafted agreement algorithm to pluck truechimers from the population possibly including falsetickers. A particular association is proventic if the server certificate and identity have been verified by the means described in this report. However, the statement “the client is synchronized to proventic sources” means that the system clock has been set using the time values of one or more proventic associations and according to the NTP mitigation algorithms. While a certificate authority (CA) must satisfy this requirement when signing a certificate request, the certificate itself can be stored in public directories and retrieved over unsecured network paths. Over the last several years the IETF has defined and evolved the IPSEC infrastructure for privacy protection and source authentication in the Internet, The infrastructure includes the Encapsulating Security Payload (ESP) [7] and Authentication Header (AH) [6] for IPv4 and IPv6. Cryptographic algorithms that use these headers for various purposes include those developed for the PKI, including MD5 message digests, RSA digital signatures and several variations of Diffie-Hellman key agreements. The fundamental assumption in the security model is that packets transmitted over the Internet can be intercepted by other than the intended recipient, remanufactured in various ways and replayed in whole or part. These packets can cause the client to believe or produce incorrect information, cause protocol operations to fail, interrupt network service or consume precious network and processor resources. In the case of NTP, the assumed goal of the intruder is to inject false time values, disrupt the protocol or clog the network, servers or clients with spurious packets that exhaust resources and deny service to legitimate applications. The mission of the algorithms and protocols described in this report is to detect and discard spurious packets sent by other than the intended sender or sent by the intended sender, but modified or replayed by an intruder. The cryptographic means of the reference implementation are based on the OpenSSL cryptographic software library available at www.openssl.org, but other libraries with equivalent functionality could be used as well. It is important for distribution and export purposes that the way in which these algorithms are used precludes encryption of any data other than incidental to the construction of digital signatures. There are a number of defense mechanisms already built in the NTP architecture, protocol and algorithms. The fundamental timestamp exchange scheme is inherently resistant to spoofing and replay attacks. The engineered clock filter, selection and clustering algorithms are designed to defend against evil cliques of Byzantine traitors. While not necessarily designed to defeat determined intruders, these algorithms and accompanying sanity checks have functioned well over the years to deflect improperly operating but presumably friendly scenarios. However, these mechanisms do not securely identify and authenticate servers to clients. Without specific further protection, an intruder can inject any or all of the following mischiefs. Further discussion is in [9] and in the briefings at the NTP project page, but beyond the scope of this report. 1. An intruder can intercept and archive packets forever, as well as all the public values ever generated and transmitted over the net. 2. An intruder can generate packets faster than the server, network or client can process them, especially if they require expensive cryptographic computations. 3. In a wiretap attack the intruder can intercept, modify and replay a packet. However, it cannot permanently prevent onward transmission of the original packet; that is, it cannot break the wire, only tell lies and congest it. Except in unlikely cases considered in Appendix D, the modified packet cannot arrive at the victim before the original packet, nor does it have the server private keys or identity parameters. 4. In a middleman or masquerade attack the intruder is positioned between the server and client, so it can intercept, modify and replay a packet and prevent onward transmission of the original packet. Except in unlikely cases considered in Appendix D, the middleman does not have the server private keys or identity parameters. The NTP security model assumes the following possible limitations. Further discussion is in [9] and in the briefings at the NTP project page, but beyond the scope of this report. 1. The running times for public key algorithms are relatively long and highly variable. In general, the performance of the time synchronization function is badly degraded if these algorithms must be used for every NTP packet. 2. In some modes of operation it is not feasible for a server to retain state variables for every client. It is however feasible to regenerated them for a client upon arrival of a packet from that client. 3. The lifetime of cryptographic values must be enforced, which requires a reliable system clock. However, the sources that synchronize the system clock must be cryptographically proventicated. This circular interdependence of the timekeeping and proventication functions requires special handling. 4. All proventication functions must involve only public values transmitted over the net with the single exception of encrypted signatures and cookies intended only to authenticate the source. Private values must never be disclosed beyond the machine on which they were created except in the case of a special trusted agent (TA) assigned for this purpose. 5. Public encryption keys and certificates must be retrievable directly from servers without requiring secured channels; however, the fundamental security of identification credentials and public values bound to those credentials must be a function of certificate authorities and/or webs of trust. 6. Error checking must be at the enhanced paranoid level, as network terrorists may be able to craft errored packets that consume excessive cycles with needless result. While this report includes an informal vulnerability analysis and error protection paradigm, a formal model based on communicating finite-state machine analysis remains to be developed. Unlike the Secure Shell security model, where the client must be securely authenticated to the server, in NTP the server must be securely authenticated to the client. In ssh each different interface address can be bound to a different name, as returned by a reverse-DNS query. In this design separate public/private key pairs may be required for each interface address with a distinct name. A perceived advantage of this design is that the security compartment can be different for each interface. This allows a firewall, for instance, to require some interfaces to authenticate the client and others not. However, the NTP security model specifically assumes that access control is performed by means external to the protocol and that all time values and cryptographic values are public, so there is no need to associate each interface with different cryptographic values. To do so would create the possibility of a two-faced clock, which is ordinarily considered a Byzantine hazard. In other words, there is one set of private secrets for the host, not one for each interface. In the NTP design the host name, as for instance returned by the Unix gethostname() library function, represents all interface addresses. Since at least in some host configurations the host name may not be identifiable in a DNS query, the name must be either configured in advance or obtained directly from the server using the Autokey protocol. 3. Approach The Autokey protocol described in this report is designed to meet the following objectives. Again, in-depth discussions on these objectives is in the web briefings and will not be elaborated in this report. Note that here and elsewhere in this report mention of broadcast mode means multicast mode as well, with exceptions as noted in the NTP software documentation. 1. It must interoperate with the existing NTP architecture model and protocol design. In particular, it must support the symmetric key scheme described in [11]. As a practical matter, the reference implementation must use the same internal key management system, including the use of 32-bit key IDs and existing mechanisms to store, activate and revoke keys. 2. It must provide for the independent collection of cryptographic values and time values. A NTP packet is accepted for processing only when the required cryptographic values have been obtained and verified and the NTP header has passed all sanity checks. 3. It must not significantly degrade the potential accuracy of the NTP synchronization algorithms. In particular, it must not make unreasonable demands on the network or host processor and memory resources. 4. It must be resistant to cryptographic attacks, specifically those identified in the security model above. In particular, it must be tolerant of operational or implementation variances, such as packet loss or misorder, or suboptimal configurations. 5. It must build on a widely available suite of cryptographic algorithms, yet be independent of the particular choice. In particular, it must not require data encryption other than incidental to signature and cookie encryption operations. 6. It must function in all the modes supported by NTP, including server, symmetric and broadcast modes. 7. It must not require intricate per-client or per-server configuration other than the availability of the required cryptographic keys and certificates. 8. The reference implementation must contain provisions to generate cryptographic key files specific to each client and server. 4. Autokey Cryptography Autokey public key cryptography is based on the PKI algorithms commonly used in the Secure Shell and Secure Sockets Layer applications. As in these applications Autokey uses keyed message digests to detect packet modification, digital signatures to verify the source and public key algorithms to encrypt cookies. What makes Autokey cryptography unique is the way in which these algorithms are used to deflect intruder attacks while maintaining the integrity and accuracy of the time synchronization function. NTPv3 and NTPv4 symmetric key cryptography uses keyed-MD5 message digests with a 128- bit private key and 32-bit key ID. In order to retain backward compatibility with NTPv3, the NTPv4 key ID space is partitioned in two subspaces at a pivot point of 65536. Symmetric key IDs have values less than the pivot and indefinite lifetime. Autokey key IDs have pseudo-random values equal to or greater than the pivot and are expunged immediately after use. Both symmetric key and public key cryptography authenticate as shown in Figure 1. The server looks up the key associated with the key ID and calculates the message digest from the NTP header and extension fields together with the key value. The key ID and digest form the message authentication code (MAC) included with the message. The client does the same computation using its local copy of the key and compares the result with the digest in the MAC. If the values agree, the message is assumed authentic. There are three Autokey protocol variants corresponding to each of the three NTP modes: server, symmetric and broadcast. All three variants make use of specially contrived session keys, called autokeys, and a precomputed pseudo-random sequence of autokeys which are saved along with the key IDs in a key list. As in the original NTPv3 authentication scheme, the Autokey protocol operates separately for each association, so there may be several autokey sequences operating independently at the same time. An autokey is computed from four fields in network byte order as shown in Figure 2. The four values are hashed by the MD5 message digest algorithm to produce the 128-bit autokey value, which in the reference implementation is stored along with the key ID in a cache used for symmetric keys as well as autokeys. Keys are retrieved from the cache by key ID using hash tables and a fast lookup algorithm. For use with IPv4, the Source Address and Dest Address fields contain 32 bits; for use with IPv6, these fields contain 128 bits. In either case the Key ID and Cookie fields contain 32 bits. Thus, an IPv4 autokey has four 32-bit words, while an IPv6 autokey has ten 32-bit words. The source and destination addresses and key ID are public values visible in the packet, while the cookie can be a public value or shared private value, depending on the mode. The NTP packet format has been augmented to include one or more extension fields piggybacked between the original NTP header and the MAC at the end of the packet. For packets without extension fields, the cookie is a shared private value conveyed in encrypted form. For packets with extension fields, the cookie has a default public value of zero, since these packets can be validated independently using digital signatures. There are some scenarios where the use of endpoint IP addresses may be difficult or impossible. These include configurations where network address translation (NAT) devices are in use or when addresses are changed during an association lifetime due to mobility constraints. For Autokey, the only restriction is that the address fields visible in the transmitted packet must be the same as those used to construct the autokey sequence and key list and that these fields be the same as those visible in the received packet. Provisions are included in the reference implementation to handle cases when these addresses change, as possible in mobile IP. For scenarios where the endpoint IP addresses are not available, an optional public identification value could be used instead of the addresses. Examples include the Interplanetary Internet, where bundles are identified by name rather than address. Specific provisions are for further study. Figure 3 shows how the autokey list and autokey values are computed. The key list consists of a sequence of key IDs starting with a random 32-bit nonce (autokey seed) equal to or greater than the pivot as the first key ID. The first autokey is computed as above using the given cookie and the first 32 bits of the result in network byte order become the next key ID. Operations continue to generate the entire list. It may happen that a newly generated key ID is less than the pivot or collides with another one already generated (birthday event). When this happens, which occurs only rarely, the key list is terminated at that point. The lifetime of each key is set to expire one poll interval after its scheduled use. In the reference implementation, the list is terminated when the maximum key lifetime is about one hour, so for poll intervals above one hour a new key list containing only a single entry is regenerated for every poll. The index of the last key ID in the list is saved along with the next key ID for that entry, collectively called the autokey values. The autokey values are then signed. The list is used in reverse order as shown in Figure 4, so that the first autokey used is the last one generated. The Autokey protocol includes a message to retrieve the autokey values and signature, so that subsequent packets can be validated using one or more hashes that eventually match the last key ID (valid) or exceed the index (invalid). This is called the autokey test in the following and is done for every packet, including those with and without extension fields. In the reference implementation the most recent key ID received is saved for comparison with the first 32 bits in network byte order of the next following key value. This minimizes the number of hash operations in case a single packet is lost. 5. Secure Groups A digital signature scheme provides secure server authentication, but it does not provide protection against masquerade, unless the server identity is verified by other means. The PKI security model assumes each client is able to verify the certificate trail to a trusted certificate authority (CA), where each ascendant server must prove identity to the immediately descendant client by independent means, such as a credit card number or PIN. While Autokey supports this model by default, in a hierarchical ad-hoc network, especially with server discovery schemes like NTP Manycast, proving identity at each rest stop on the trail must be an intrinsic capability of Autokey itself. In the NTP security model every member of a closed group, such as might be operated by a timestamping service, be in possession of a secret group key. This could take the form of a private certificate or one or another identification schemes described in the literature and Appendix E. Certificate trails and identification schemes are at the heart of the NTP security model preventing masquerade and middleman attacks. The Autokey protocol operates to hike the trails and run the identity schemes. A NTP secure group consists of a number of hosts dynamically assembled as a forest with roots the trusted hosts at the lowest stratum of the group. The trusted hosts do not have to be, but often are, primary (stratum 1) servers. A trusted authority (TA), not necessarily a group host, generates private and public identity values and deploys selected values to the group members using secure means. In Figure 5 the Alice group consists of trusted hosts Alice, which is also the TA, and Carol. Dependent servers Brenda and Denise have configured Alice and Carol, respectively, as their time sources. Stratum 3 server Eileen has configured both Brenda and Denise as her time sources. The certificates are identified by the subject and signed by the issuer. Note that the group key has previously been generated by Alice and deployed by secure means to all group members. The steps in hiking the certificate trails and verifying identity are as follows. Note the step number in the description matches the step number in the figure. 1. At startup each server loads its self-signed certificate from a local file. By convention the lowest stratum certificates are marked trusted in a X.509 extension field. As Alice and Carol have trusted certificates, they need do nothing further to validate the time. It could be that the trusted hosts depend on servers in other groups; this scenario is discussed later. 2. The girls begin the Autokey protocol which establishes the server name, signature scheme, certificate and identity scheme for each configured server. They continue to load certificates recursively until a self-signed trusted certificate is found. Brenda and Denise immediately find self-signed trusted certificates for Alice and Carol, respectively, but Eileen will loop because neither Brenda nor Denise have their own certificates signed by either Alice or Carol. 3. Brenda and Denise continue with one of the identity schemes described below to verify each has the group key previously deployed by Alice. If this succeeds, each continues in step 4. 4. Brenda and Denise present their certificates to Alice for signature. If this succeeds, either or both Brenda and Denise can now provide these signed certificates to Eileen, which may be looping in step 2. When Eileen receives them, she can now follow the trail via either Brenda or Denise to the trusted certificates for Alice and Carol. Once this is done, Eileen can complete the protocol just as Brenda and Denise. The NTP security model is based on multiple, hierarchical, overlapping security compartments or groups. The example above illustrates how groups can be used to construct closed compartments, depending on how the identity credentials are deployed. The rules can be summarized: 1. Each host holds a private group key generated by a TA. 2. A host is trusted if it operates at the lowest stratum in the group and has a trusted, self- signed certificate. 3. A host uses the identity scheme to prove to another host it has the same group key, even as in some (zero knowledge) schemes neither knows the exact key value. 4. A client verifies group membership if the server has the same key and has an unbroken certificate trail to a trusted host. Each compartment is assigned a group key by the TA, which is then deployed to all group members by secure means. For various reasons it may be convenient for a server to hold keys for more than one group. For example, Figure 6 shows three secure groups Alice, Helen and Carol arranged in a hierarchy. Hosts A, B, C and D belong to the Alice group, hosts R, S to the Helen group and hosts X, Y and Z to the Carol group. While not strictly necessary, hosts A, B and R are stratum 1 and presumed trusted, but the TA generating the group keys could be one of them or another not shown. In most identity schemes there are two kinds of group keys, server and client. The intent of the design is to provide security separation, so that servers cannot masquerade as TAs and clients cannot masquerade as servers. Assume for example that Alice and Helen belong to national standards laboratories and their group keys are used to confirm identity between members of each group. Carol is a prominent corporation receiving standards products via broadcast satellite and requiring cryptographic authentication. Perhaps under contract, host X belonging to the Carol group has rented client keys for both Alice and Helen and has server keys for Carol. The Autokey protocol operates for each group separately while preserving security separation. Host X can prove identity in Carol to clients Y and Z, but cannot prove to anybody that he belongs to either Alice or Helen. Ordinarily, it would not be desirable to reveal the group key in server keys and forbidden to reveal it in client keys. This can be avoided using the MV identity scheme described later. It allows the same broadcast transmission to be authenticated by more than one key, one used internally by the laboratories (Alice and/or Helen) and the other handed out to clients like Carol. In the MV scheme these keys can be separately activated upon subscription and deactivated if the subscriber fails to pay the bill. Figure 7 shows operational details where more than one group is involved, in this case Carol and Alice. As in the previous example, Brenda has configured Alice as her time source and Denise has configured Carol as her time source. Alice and Carol have server keys; Brenda and Denise have server and client keys only for their respective groups. Eileen has client keys for both Alice and Carol. The protocol operates as previously described to verify Alice to Brenda and Carol to Denise. The interesting case is Eileen, who may verify identity either via Brenda or Denise or both. To do that she uses the client keys of either Alice and Carol or both. But, Eileen doesn’t know which of the two keys to use until hiking the certificate trail to find the trusted certificate of either Alice or Carol and then loading the associated local key. This scenario can of course become even more complex as the number of servers and depth of the tree increase. The bottom line is that every host must have the client keys for all the lowest-stratum trusted hosts it is ever likely to find. 6. Identity Schemes While the identity scheme described in RFC-2875 [14] is based on a ubiquitous Diffie-Hellman infrastructure, it is expensive to generate and use when compared to others described in Appendix E. There are five schemes now implemented in the NTPv4 reference implementation to prove identity: (1) private certificate (PC), (2) trusted certificate (TC), (3) a modified Schnorr algorithm (IFF aka Identify Friendly or Foe), (4) a modified Guillou-Quisquater algorithm (GQ), and (5) a modified Mu-Varadharajan algorithm (MV). Following is a summary description of each; details are given in Appendix E. The PC scheme involves a private certificate as group key. A certificate is designated private by a X509 Version 3 extension field when generated by utility routines in the NTP software distribution. The certificate is distributed to all other group members by secure means and is never revealed outside the group. A client is marked trusted when the first signature is verified. In effect, the private certificate is used as a symmetric key. This scheme is cryptographically strong as long as the private certificate is protected; however, it can be very awkward to refresh the keys or certificate, since new values must be securely distributed to a possibly large population and activated simultaneously. All other schemes involve a conventional certificate trail as described in RFC-2510 [1], where each certificate is signed by an issuer one step closer to the trusted host, which has a self-signed trusted certificate. A certificate is designated trusted by a X509 Version 3 extension field when generated by utility routines in the NTP software distribution. A host obtains the certificates of all other hosts along the trail leading to a trusted host by the Autokey protocol, then requests the immediately ascendant host to sign its own certificate. Subsequently, these certificates are provided to descendent hosts by the Autokey protocol. In this scheme keys and certificates can be refreshed at any time, but a masquerade vulnerability remains unless a request to sign a client certificate is validated by some means such as reverse-DNS. If no specific identity scheme is specified, this is the default TC identity scheme. The three remaining schemes IFF, GQ and MV involve a cryptographically strong challenge- response exchange where an intruder cannot learn the group key, even after repeated observations of multiple exchanges. In addition, the IFF and MV schemes are properly described as zero-knowledge proofs, because the client can verify the server has the group key without the client knowing its value. As shown in Figure 8, these schemes start when the client sends a nonce to the server, which then rolls its own nonce, performs a mathematical operation and sends the results along with a message digest to the client. The client performs another mathematical operation and verifies the results match the message digest. The IFF scheme is used when the certificate is generated by a third party, such as a commercial service and in general has the same refreshment and distribution problems as PC. However, this scheme has the advantage that the group key is not known to the clients. On the other hand, when certificates are generated by routines in the NTP distribution, the GQ scheme may be a better choice. In this scheme the server further obscures the secret group key using a public/private key pair which can be refreshed at any time. The public member is conveyed in the certificate by a X509 Version 3 extension field which changes for each regeneration of key pair and certificate. The MV scheme is perhaps the most interesting and flexible of the three challenge/response schemes. It can be used when a small number of servers provide synchronization to a large client population where there might be considerable risk of compromise between and among the servers and clients. The TA generates a deliciously intricate cryptosystem involving public and private encryption keys, together with a number of activation keys and associated private client decryption keys. The activation keys are used by the TA to activate and revoke individual client decryption keys without changing the decryption keys themselves. The TA provides the server with a private encryption key and public decryption key. The server adjusts the keys by a nonce for each plaintext encryption, so they appear different on each use. The encrypted ciphertext and adjusted public decryption key are provided in the client message. The client computes the decryption key from its private decryption key and the public decryption key in the message. 7. Autokey Operations The Autokey protocol has three variations or dances corresponding to the NTP server, symmetric and broadcast modes. The server dance was suggested by Steve Kent over lunch some time ago, but considerably modified since that meal. The server keeps no state for each client, but uses a fast algorithm and a 32-bit random private value (server seed) to regenerate the cookie upon arrival of a client packet. The cookie is calculated as the first 32 bits of the autokey computed from the client and server addresses, a key ID of zero and the server seed as cookie. The cookie is used for the actual autokey calculation by both the client and server and is thus specific to each client separately. In previous Autokey versions the cookie was transmitted in clear on the assumption it was not useful to a wiretapper other than to launch an ineffective replay attack. However, a middleman could intercept the cookie and manufacture bogus messages acceptable to the client. In order to reduce the risk of such an attack, the Autokey Version 2 server encrypts the cookie using a public key supplied by the client. While requiring additional processor resources for the encryption, this makes it effectively impossible to spoof a cookie or masquerade as the server. In the server dance the client uses the cookie and each key ID on the key list in turn to retrieve the autokey and generate the MAC in the NTP packet. The server uses the same values to generate the message digest and verifies it matches the MAC in the packet. It then generates the MAC for the response using the same values, but with the client and server addresses exchanged. The client generates the message digest and verifies it matches the MAC in the packet. In order to deflect old replays, the client verifies the key ID matches the last one sent. In this mode the sequential structure of the key list is not exploited, but doing it this way simplifies and regularizes the implementation while making it nearly impossible for an intruder to guess the next key ID. In the broadcast dance clients normally do not send packets to the server, except when first starting up to verify credentials and calibrate the propagation delay. At the same time the client runs the broadcast dance to obtain the autokey values. The dance requires the association ID of the particular server association, since there can be more than one operating in the same server. For this purpose, the server packet includes the association ID in every response message sent and, when sending the first packet after generating a new key list, it sends the autokey values as well. After obtaining and verifying the autokey values, the client verifies further server packets using the autokey sequence. The symmetric dance is similar to the server dance and keeps only a small amount of state between the arrival of a packet and departure of the reply. The key list for each direction is generated separately by each peer and used independently, but each is generated with the same cookie. The cookie is conveyed in a way similar to the server dance, except that the cookie is a random value. There exists a possible race condition where each peer sends a cookie request message before receiving the cookie response from the other peer. In this case, each peer winds up with two values, one it generated and one the other peer generated. The ambiguity is resolved simply by computing the working cookie as the EXOR of the two values. Autokey choreography includes one or more exchanges, each with a specific purpose, that must be completed in order. The client obtains the server host name, digest/signature scheme and identity scheme in the parameter exchange. It recursively obtains and verifies certificates on the trail leading to a trusted certificate in the certificate exchange and verifies the server identity in the identity exchange. In the values exchange the client obtains the cookie and autokey values, depending on the particular dance. Finally, the client presents its self-signed certificate to the server for signature in the sign exchange. Once the certificates and identity have been validated, subsequent packets are validated by digital signatures and autokey sequences. These packets are presumed to contain valid time values; however, unless the system clock has already been set by some other proventic means, it is not known whether these values actually represent a truechime or falsetick source. As the protocol evolves, the NTP associations continue to accumulate time values until a majority clique is available in a population of at least three servers. At this point the NTP mitigation algorithms cull the falsetickers and cluster outlyers from the population and the survivors are allowed to discipline the system clock. The time values for truechimer sources form a proventic partial ordering relative to the applicable signature timestamps. This raises the interesting issue of how to mitigate between the timestamps of different associations. It might happen, for instance, that the timestamp of some Autokey message is ahead of the system clock by some presumably small amount. For this reason, timestamp comparisons between different associations and between associations and the system clock are avoided, except in the NTP intersection and clustering algorithms and when determining whether a certificate has expired. Once the Autokey values have been instantiated, the dances are normally dormant. In all except the broadcast dance, packets are normally sent without extension fields, unless the packet is the first one sent after generating a new key list or unless the client has requested the cookie or autokey values. If for some reason the client clock is stepped, rather than slewed, all cryptographic and time values for all associations are purged and the dances in all associations restarted from scratch. This insures that stale values never propagate beyond a clock step. At intervals of about one day the reference implementation purges all associations, refreshes all signatures, garbage collects expired certificates and refreshes the server seed. 8. Public Key Signatures and Timestamps While public key signatures provide strong protection against misrepresentation of source, computing them is expensive. This invites the opportunity for an intruder to clog the client or server by replaying old messages or to originate bogus messages. A client receiving such messages might be forced to verify what turns out to be an invalid signature and consume significant processor resources. In order to foil such attacks, every signed extension field carries a timestamp in the form of the NTP seconds at the signature epoch. The signature spans the entire extension field including the timestamp. If the Autokey protocol has verified a proventic source and the NTP algorithms have validated the time values, the system clock can be synchronized and signatures will then carry a nonzero (valid) timestamp. Otherwise the system clock is unsynchronized and signatures carry a zero (invalid) timestamp. The protocol detects and discards replayed extension fields with old or duplicate timestamps, as well as fabricated extension fields with bogus timestamps, before any values are used or signatures verified. There are three signature types currently defined: Cookie signature/timestamp. Each association has a cookie for use when generating a key list. The cookie value is determined along with the cookie signature and timestamp upon arrival of a cookie request message. The values are returned in a a cookie response message. Autokey signature/timestamp. Each association has a key list for generating the autokey sequence. The autokey values are determined along with the autokey signature and timestamp when a new key list is generated, which occurs about once per hour in the reference implementation. The values are returned in a autokey response message. Public values signature/timestamp. All public key, certificate and leapsecond table values are signed at the time of generation, which occurs when the system clock is first synchronized to a proventic source, when the values have changed and about once per day after that, even if these values have not changed. During protocol operations, each of these values and associated signatures and timestamps are returned in the associated request or response message. While there are in fact several public value signatures, depending on the number of entries on the certificate list, the values are all signed at the same time, so there is only one public value timestamp. The most recent timestamp received of each type is saved for comparison. Once a valid signature with valid timestamp has been received, messages with invalid timestamps or earlier valid timestamps of the same type are discarded before the signature is verified. For signed messages this deflects replays that otherwise might consume significant processor resources. For other messages the Autokey protocol deflects message modification or replay by a wiretapper, but not necessarily by a middleman. In addition, the NTP protocol itself is inherently resistant to replays and consumes only minimal processor resources. All cryptographic values used by the protocol are time sensitive and are regularly refreshed. In particular, files containing cryptographic basis values used by signature and encryption algorithms are regenerated from time to time. It is the intent that file regenerations occur without specific advance warning and without requiring prior distribution of the file contents. While cryptographic data files are not specifically signed, every file is associated with a filestamp in the form of the NTP seconds at the creation epoch. It is not the intent in this report to specify file formats or names or encoding rules; however, whatever conventions are used must support a NTP filestamp in one form or another. Additional details specific to the reference implementation are in Appendix B. Filestamps and timestamps can be compared in any combination and use the same conventions. It is necessary to compare them from time to time to determine which are earlier or later. Since these quantities have a granularity only to the second, such comparisons are ambiguous if the values are in the same second. Thus, the ambiguity must be resolved for each comparison operation as described in Appendix C. It is important that filestamps be proventic data; thus, they cannot be produced unless the producer has been synchronized to a proventic source. As such, the filestamps throughout the NTP subnet represent a partial ordering of all creation epochs and serve as means to expunge old data and insure new data are consistent. As the data are forwarded from server to client, the filestamps are preserved, including those for certificate and leapseconds files. Packets with older filestamps are discarded before spending cycles to verify the signature. 9. Autokey Protocol Overview This section presents an overview of the three dances: server, broadcast and symmetric. Each dance is designed to be nonintrusive and to require no additional packets other than for regular NTP operations. The NTP and Autokey protocols operate independently and simultaneously and use the same packets. When the preliminary dance exchanges are complete, subsequent packets are validated by the autokey sequence and thus considered proventic as well. Autokey assumes clients poll servers at a relatively low rate, such as once per minute or slower. In particular, it is assumed that a request sent at one poll opportunity will normally result in a response before the next poll opportunity; however the protocol is robust against a missed or duplicate response. The Autokey protocol data unit is the extension field, one or more of which can be piggybacked in the NTP packet. An extension field contains either a request with optional data or a response with data. To avoid deadlocks, any number of responses can be included in a packet, but only one request. A response is generated for every request, even if the requestor is not synchronized to a proventic source, but contain meaningful data only if the responder is synchronized to a proventic source. Some requests and most responses carry timestamped signatures. The signature covers the entire extension field, including the timestamp and filestamp, where applicable. Only if the packet passes all extension field tests are cycles spent to verify the signature. All dances begin with the parameter exchange where the client obtains the server host name and status word specifying the digest/signature scheme it will use and the identity schemes it supports. The dance continues with the certificate exchange where the client obtains and verifies the certificates along the trail to a trusted, self-signed certificate usually, but not necessarily, provided by a primary (stratum 1) server. Primary servers are by design proventic with trusted, self-signed certificates. However, the certificate trail is not sufficient protection against middleman attacks unless an identity scheme such as described in Appendix E or proof-of-possession scheme in [14] is available. While the protocol for a generic challenge/response scheme is defined in this report, the choice of one or another required or optional identification schemes is yet to be determined. If all certificate signatures along the trail are verified and the server identity is confirmed, the client continues with the cookie and autokey exchanges as necessary to complete the protocol. Upon completion the client verifies packets using digital signatures and/or the autokey sequence. Once synchronized to a proventic source, the client continues with the sign exchange where the server acting as CA signs the client certificate. The CA interprets the certificate as a X.509v3 certificate request, but verifies the signature if it is self-signed. The CA extracts the subject, issuer, extension fields and public key, then builds a new certificate with these data along with its own serial number and begin and end times, then signs it using its own public key. The client uses the signed certificate in its own role as CA for dependent clients. A final exchange occurs when the server has the leapseconds table, as indicated in the host status word. If so, the client requests the table and compares the filestamp with its own leapseconds table filestamp, if available. If the server table is newer than the client table, the client replaces its table with the server table. The client, acting as server, can now provide the most recent table to any of its dependent clients. In symmetric mode, this results in both peers having the newest table. 10. Autokey State Machine This section describes the formal model of the Autokey state machine, its state variables and the state transition functions. Each server and client operating also as a server implements a single host status word, while each client implements an association status word for each server. Both words have the format and content shown in Figure 9. The low order 16 bits of the status word define the state of the Autokey protocol, while the high order 16 bits specify the message digest/ signature encryption scheme. as encoded in the OpenSSL library. Bits 24-31 of the status word are reserved for server use, while bits 16-23 are reserved for client association use. In the host portion bits 24-27 specify the available identity schemes, while bits 28-31 specify the server capabilities. There are four additional bits implemented separately. The host status word is included in the ASSOC request and response messages. The client copies this word to the association status word and then lights additional status bits as the dance proceeds. Once lit, these bits never come dark unless a general reset occurs and the protocol is restarted from the beginning. The status bits are defined as follows: ENB (31). Lit if the server implements the Autokey protocol and is prepared to dance. Dim would be very strange. LPF (30). Lit if the server has loaded a valid leapseconds file. This bit can be either lit or dim. IDN (24-27). These four bits select which identity scheme is in use. While specific coding for various schemes is yet to be determined, the schemes available in the reference implementation and described in Appendix E include the following. 0x0 Trusted Certificate (TC) Scheme (default) 0x1 Private Certificate (PC) Scheme 0x2 Schnorr aka Identify-Friendly-or-Foe (IFF) Scheme 0x4 Guillard-Quisquater (GC) Scheme 0x8 Mu-Varadharajan (MV) Scheme The PC scheme is exclusive of any other scheme. Otherwise, the IFF, GQ and MV bits can be lit in any combination. The association status bits are defined as follows: VAL 0x0100. Lit when the server certificate and public key are validated. IFF 0x0200. Lit when the server identity credentials are confirmed. PRV 0x0400. Lit when the server signature is verified using the public key and identity credentials. Also called the proventic bit elsewhere in this report. When lit, signed values in subsequent messages are presumed proventic. CKY 0x0800. Lit when the cookie is received and validated. When lit, key lists can be generated. AUT 0x1000. Lit when the autokey values are received and validated. When lit, clients can validate packets without extension fields according to the autokey sequence. SGN 0x2000. Lit when the host certificate is signed by the server. LPT 0x4000. Lit when the leapseconds table is received and validated. There are four additional status bits LST, LBK, DUP and SYN not included in the status word. All except SYN are association properties, while SYN is a host property. These bits may be lit or dim as the protocol proceeds; all except LST are active whether or not the protocol is running. LST is lit when the key list is regenerated and signed and comes dim after the autokey values have been transmitted. This is necessary to avoid livelock under some conditions. SYN is lit when the client has synchronized to a proventic source and never dim after that. There are two error bits: LBK indicates the received packet does not match the last one sent and DUP indicates a duplicate packet. These bits, which are described in Appendix C, are lit if the corresponding error has occurred for the current packet and dim otherwise. 10.1 State Variables Following is a list of state variables used by the server protocol. Host Name. The name of the host returned by the Unix gethostname() library function. The name must agree with the subject name in the host certificate. Host Status Word. This word is initialized when the host first starts up. The format is described above. Host Key. The RSA public/private key pair used to encrypt/decrypt cookies. This is also the default sign key. Sign Key. The RSA or DSA public/private key pair used to encrypt/decrypt signatures when the host key is not used for this purpose. Sign Digest. The message digest algorithm used to compute the signature before encryption. IFF Parameters. The parameters used in the optional IFF identity scheme described in Appendix E. GQ Parameters. The parameters used in the optional GQ identity scheme described in Appendix E. MV Parameters. The parameters used in the optional MV identity scheme described in Appendix E. Server Seed. The private value hashed with the IP addresses to construct the cookie. Certificate Information Structure (CIS). Certificates are used to construct certificate information structures (CIS) which are stored on the certificate list. The structure includes certain information fields from an X.509v3 certificate, together with the certificate itself encoded in ASN.1 syntax. Each structure carries the public value timestamp and the filestamp of the certificate file where it was generated. Elsewhere in this report the CIS will not be distinguished from the certificate unless noted otherwise. A flags field in the CIS determines the status of the certificate. The field is encoded as follows: TRST 0x01. The certificate has been signed by a trusted issuer. If the certificate is self-signed and contains “trustRoot” in the Extended Key Usage field, this bit will be lit when the CIS is constructed. SIGN 0x02. The certificate signature has been verified. If the certificate is self-signed and verified using the contained public key, this bit will be lit when the CIS is constructed. VALD 0x04. The certificate is valid and can be used to verify signatures. This bit is lit when a trusted certificate has been found on a valid certificate trail. PRIV 0x08. The certificate is private and not to be revealed. If the certificate is self-signed and contains “Private” in the Extended Key Usage field, this bit will be lit when the CIS is constructed. ERRR 0x80. The certificate is defective and not to be used in any way. Certificate List, CIS structures are stored on the certificate list in order of arrival, with the most recently received CIS placed first on the list. The list is initialized with the CIS for the host certificate, which is read from the certificate file. Additional CIS entries are pushed on the list as certificates are obtained from the servers during the certificate exchange. CIS entries are discarded if overtaken by newer ones or expire due to old age. Host Certificate. The self-signed X.509v3 certificate for the host. The subject and issuer fields consist of the host name, while the message digest/signature encryption scheme consists of the sign key and message digest defined above. Optional information used in the identity schemes is carried in X.509v3 extension fields compatible with [4]. Public Key Values. The public encryption key for the COOKIE request, which consists of the public value of the host key. It carries the public values timestamp and the filestamp of the host key file. Leapseconds Table Values. The NIST leapseconds table from the NIST leapseconds file. It carries the public values timestamp and the filestamp of the leapseconds file. Following is a list of state variables used by the client association protocol in all modes. Association ID. The association ID used in responses. It is assigned when the association is mobilized. Server Association ID. The server association ID used in requests. It is copied from the first nonzero association ID field in a response. Server Subject Name. The server host name determined in the parameter exchange. Server Issuer Name. The host name signing the certificate. It is extracted from the current server certificate upon arrival and used to request the next item on the certificate trail. Association Status Word. The host status word of the server determined in the parameter exchange. Server Public Key. The public key used to decrypt signatures. It is extracted from the first certificate received, which by design is the server host certificate. Server Message Digest. The digest/signature scheme determined in the parameter exchange. Identification Challenge. A 512-bit nonce used in the identification exchange. Group Key. A set of values used by the identification exchange. It identifies the cryptographic compartment shared by the server and client. Receive Cookie Values. The cookie returned in a COOKIE response, together with its timestamp and filestamp. Receive Autokey Values. The autokey values returned in an AUTO response, together with its timestamp and filestamp. Receive Leapsecond Values. The leapsecond table returned by a LEAP response, together with its timestamp and filestamp. Following is a list of server state variables used in broadcast and symmetric modes. Send Cookie Values. The cookie encryption values, signature and timestamps. Send Autokey Values. The autokey values, signature and timestamps. Key List. A sequence of key IDs starting with the autokey seed and each pointing to the next. It is computed, timestamped and signed at the next poll opportunity when the key list becomes empty. Current Key Number. The index of the entry on the Key List to be used at the next poll opportunity. 10.2 Protocol Messages There are currently eight Autokey requests and eight corresponding responses. A description of these messages is given below; the detailed field formats are described in Appendix A. No-operation (NULL 0). Does nothing except return an empty reply which can be used as a crypto-ping. Association Message (ASSOC 1). The Association message is used in the parameter exchange to obtain the host name and related values. The request contains the host status word in the filestamp field. The response contains the status word in the filestamp field and in addition the host name as the string returned by the Unix gethostname() library function. While minimum and maximum host name lengths remain to be established, the reference implementation uses the values 4 and 256, respectively. The remaining fields are defined previously in this report. If the server response is acceptable and both server and client share the same identity scheme, ENB is lit. When the PC identity scheme is in use, the ASSOC response lights VAL, IFF and SIG, since the IFF exchange is complete at this point. Certificate Message (CERT 2). The Certificate message is used in the certificate exchange to obtain a certificate and related values by subject name. The request contains the subject name. For the purposes of interoperability with older Autokey versions, if only the first two words are sent, the request is for the host certificate. The response contains the certificate encoded in X.509 format with ASN.1 syntax as described in Appendix G. If the subject name in the response does not match the issuer name, the exchange continues with the issuer name replacing the subject name in the request. The exchange continues until either the subject name matches the issuer name, indicating a self-signed certificate, or the trst bit is set in the CIS, indicating a trusted certificate. If a trusted certificate is found, the client stops the exchange and lights VAL.If a self-signed certificate is found without encountering a trusted certificate, the protocol loops until either a new certificate is signed or timeout. Cookie Message (COOKIE 3). The Cookie message is used in server and symmetric modes to obtain the server cookie. The request contains the host public key encoded with ASN.1 syntax as described in Appendix G. The response contains the cookie encrypted by the public key in the request. The signature and timestamps are determined when the cookie is encrypted. If the response is valid, the client lights CKY. Autokey Message (AUTO 4). The Autokey message is used to obtain the autokey values. The request contains no value. The response contains two 32-bit words in network order. The first word is the final key ID, while the second is the index of the final key ID. The signature and timestamps are determined when the key list is generated. If the response is valid, the client lights AUT. Leapseconds Table Message (LEAP 5). The Leapseconds Table message is used to exchange leapseconds tables. The request and response messages have the same format, except that the R bit is dim in the request and lit in the response. Both the request and response contains the leapseconds table as parsed from the leapseconds file from NIST. If the client already has a copy of the leapseconds data, it uses the one with the latest filestamp and discards the other. If the response is valid, the client lights LPT. Sign Message (SIGN 6). The Sign message requests the server to sign and return a certificate presented in the request. The request contains the client certificate encoded in X.509 format with ASN.1 syntax as described in Appendix G. The response contains the client certificate signed by the server private key. If the certificate is valid when received by the client, it is linked in the certificate list and the client lights SGN. Identity Messages (IFF 7, GQ 8, MV 9). The request contains the client challenge, usually a 160- or 512-bit nonce. The response contains the result of the mathematical operation defined in Appendix E. The Response is encoded in ASN.1 syntax as described in Appendix G. The response signature and timestamp are determined when the response is sent. If the response is valid, the client lights IFF. 10.3 Protocol State Transitions The protocol state machine is very simple but robust. The state is determined by the server status bits defined above. The state transitions of the three dances are shown below. The capitalized truth values represent the server status bits. All server bits are initialized dark and light up upon the arrival of a specific response message, as detailed above. When the system clock is first set and about once per day after that, or when the system clock is stepped, the server seed is refreshed, signatures and timestamps updated and the protocol restarted in all associations. When the server seed is refreshed or a new certificate or leapseconds table is received, the public values timestamp is reset to the current time and all signatures are recomputed. 10.3.1 Server Dance The server dance begins when the client sends an ASSOC request to the server. It ends when the first signature is verified and PRV is lit. Subsequent packets received without extension fields are validated by the autokey sequence. An optional LEAP exchange updates the leapseconds table. Note the order of the identity exchanges and that only the first one will be used if multiple schemes are available. Note also that the SIGN and LEAP requests are not issued until the client has synchronized to a proventic source. while (1) { wait_for_next_poll; make_NTP_header; if (response_ready) send_response; if (!ENB) /* parameters exchange */ ASSOC_request; else if (!VAL) /* certificate exchange */ CERT_request(Host_Name); else if (IDN & GQ && !IFF) /* GQ identity exchange */ GQ_challenge; else if (IDN & IFF && !IFF) /* IFF identity exchange */ IFF_challenge; else if (!IFF) /* TC identity exchange */ CERT_request(Issuer_Name); else if (!CKY) /* cookie exchange */ COOKIE_request; else if (SYN && !SIG) /* sign exchange */ SIGN_request(Host_Certificate); else if (SYN && LPF & !LPT) /* leapseconds exchange */ LEAP_request; } When the PC identity scheme is in use, the ASSOC response lights VAL, IFF and SIG, the COOKIE response lights CKY and AUT and the first valid signature lights PRV. 10.3.2 Broadcast Dance The only difference between the broadcast and server dances is the inclusion of an autokey values exchange following the cookie exchange. The broadcast dance begins when the client receives the first broadcast packet, which includes an ASSOC response with association ID. The broadcast client uses the association ID to initiate a server dance in order to calibrate the propagation delay. The dance ends when the first signature is verified and PRV is lit. Subsequent packets received without extension fields are validated by the autokey sequence. An optional LEAP exchange updates the leapseconds table. When the server generates a new key list, the server replaces the ASSOC response with an AUTO response in the first packet sent. while (1) { wait_for_next_poll; make_NTP_header; if (response_ready) send_response; if (!ENB) /* parameters exchange */ ASSOC_request; else if (!VAL) /* certificate exchange */ CERT_request(Host_Name); else if (IDN & GQ && !IFF) /* GQ identity exchange */ GQ_challenge; else if (IDN & IFF && !IFF) /* IFF identity exchange */ IFF_challenge; else if (!IFF) /* TC identity exchange */ CERT_request(Issuer_Name); else if (!CKY) /* cookie exchange */ COOKIE_request; else if (!AUT) /* autokey values exchange */ AUTO_request; else if (SYN &&! SIG) /* sign exchange */ SIGN_request(Host_Certificate); else if (SYN && LPF & !LPT) /* leapseconds exchange */ LEAP_request; } When the PC identity scheme is in use, the ASSOC response lights VAL, IFF and SIG, the COOKIE response lights CKY and AUT and the first valid signature lights PRV. 10.3.3 Symmetric Dance The symmetric dance is intricately choreographed. It begins when the active peer sends an ASSOC request to the passive peer. The passive peer mobilizes an association and both peers step the same dance from the beginning. Until the active peer is synchronized to a proventic source (which could be the passive peer) and can sign messages, the passive peer loops waiting for the timestamp in the ASSOC response to light up. Until then, the active peer dances the server steps, but skips the sign, cookie and leapseconds exchanges. while (1) { wait_for_next_poll; make_NTP_header; if (!ENB) /* parameters exchange */ ASSOC_request; else if (!VAL) /* certificate exchange */ CERT_request(Host_Name); else if (IDN & GQ && !IFF) /* GQ identity exchange */ GQ_challenge; else if (IDN & IFF && !IFF) /* IFF identity exchange */ IFF_challenge; else if (!IFF) /* TC identity exchange */ CERT_request(Issuer_Name); else if (SYN && !SIG) /* sign exchange */ SIGN_request(Host_Certificate); else if (SYN && !CKY) /* cookie exchange */ COOKIE_request; else if (!LST) /* autokey values response */ AUTO_response; else if (!AUT) /* autokey values exchange */ AUTO_request; else if (SYN && LPF & !LPT) /* leapseconds exchange */ LEAP_request; } When the PC identity scheme is in use, the ASSOC response lights VAL, IFF and SIG, the COOKIE response lights CKY and AUT and the first valid signature lights PRV. Once the active peer has synchronized to a proventic source, it includes timestamped signatures with its messages. The first thing it does after lighting timestamps is dance the sign exchange so that the passive peer can survive the default identity exchange, if necessary. This is pretty weird, since the passive peer will find the active certificate signed by its own public key. The passive peer, which has been stalled waiting for the active timestamps to light up, now mates the dance. The initial value of the cookie is zero. If a COOKIE response has not been received by either peer, the next message sent is a COOKIE request. The recipient rolls a random cookie, lights CKY and returns the encrypted cookie. The recipient decrypts the cookie and lights CKY. It is not a protocol error if both peers happen to send a COOKIE request at the same time. In this case both peers will have two values, one generated by itself peer and the other received from the other peer. In such cases the working cookie is constructed as the EXOR of the two values. At the next packet transmission opportunity, either peer generates a new key list and lights LST; however, there may already be an AUTO request queued for transmission and the rules say no more than one request in a packet. When available, either peer sends an AUTO response and dims LST. The recipient initializes the autokey values, dims LST and lights AUT. Subsequent packets received without extension fields are validated by the autokey sequence. The above description assumes the active peer synchronizes to the passive peer, which itself is synchronized to some other source, such as a radio clock or another NTP server. In this case, the active peer is operating at a stratum level one greater than the passive peer and so the passive peer will not synchronize to it unless it loses its own sources and the active peer itself has another source. 10.4 Error Recovery The Autokey protocol state machine includes provisions for various kinds of error conditions that can arise due to missing files, corrupted data, protocol violations and packet loss or misorder, not to mention hostile intrusion. This section describes how the protocol responds to reachability and timeout events which can occur due to such errors. Appendix C contains an extended discussion on error checking and timestamp validation. A persistent NTP association is mobilized by an entry in the configuration file, while an ephemeral association is mobilized upon the arrival of a broadcast, manycast or symmetric active packet with no matching association. If necessary, a general reset reinitializes all association variables to the initial state when first mobilized. In addition, if the association is ephemeral, the association is demobilized and all resources acquired are returned to the system. Every NTP association has two variables which maintain the liveness state of the protocol, the 8- bit reachability register defined in [11] and the watchdog timer, which is new in NTPv4. At every poll interval the reachability register is shifted left, the low order bit is dimmed and the high order bit is lost. At the same time the watchdog counter is incremented by one. If an arriving packet passes all authentication and sanity checks, the rightmost bit of the reachability register is lit and the watchdog counter is set to zero. If any bit in the reachability register is lit, the server is reachable, otherwise it is unreachable. When the first poll is sent from an association, the reachability register and watchdog counter are zero. If the watchdog counter reaches 16 before the server becomes reachable, a general reset occurs. This resets the protocol and clears any acquired resources before trying again. If the server was once reachable and then becomes unreachable, a general reset occurs. In addition, if the watchdog counter reaches 16 and the association is persistent, the poll interval is doubled. This reduces the network load for packets that are unlikely to elicit a response. At each state in the protocol the client expects a particular response from the server. A request is included in the NTP packet sent at each poll interval until a valid response is received or a general reset occurs, in which case the protocol restarts from the beginning. A general reset also occurs for an association when an unrecoverable protocol error occurs. A general reset occurs for all associations when the system clock is first synchronized or the clock is stepped or when the server seed is refreshed. There are special cases designed to quickly respond to broken associations, such as when a server restarts or refreshes keys. Since the client cookie is invalidated, the server rejects the next client request and returns a crypto-NAK packet. Since the crypto-NAK has no MAC, the problem for the client is to determine whether it is legitimate or the result of intruder mischief. In order to reduce the vulnerability in such cases, the crypto-NAK, as well as all responses, is believed only if the result of a previous packet sent by the client and not a replay, as confirmed by the LBK and DUP status bits described above. While this defense can be easily circumvented by a middleman, it does deflect other kinds of intruder warfare. There are a number of situations where some event happens that causes the remaining autokeys on the key list to become invalid. When one of these situations happens, the key list and associated autokeys in the key cache are purged. A new key list, signature and timestamp are generated when the next NTP message is sent, assuming there is one. Following is a list of these situations. 1. When the cookie value changes for any reason. 2. When a client switches from client mode to broadcast client mode. There is no further need for the key list, since the client will not transmit again. 3. When the poll interval is changed. In this case the calculated expiration times for the keys become invalid. 4. If a problem is detected when an entry is fetched from the key list. This could happen if the key was marked non-trusted or timed out, either of which implies a software bug. 11. References 1. Adams, C., S. Farrell. Internet X.509 public key infrastructure certificate management proto- cols. Network Working Group Request for Comments RFC-2510, Entrust Technologies, March 1999, 30 pp. 2. Bassham, L., W. Polk and R. Housley, “Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation Lists (CRL) Profile,” RFC- 3279, April 2002. 3. Guillou, L.C., and J.-J. Quisquatar. A “paradoxical” identity-based signature scheme result- ing from zero-knowledge. Proc. CRYPTO 88 Advanced in Cryptology, Springer-Verlag, 1990, 216-231. 4. Housley, R., et al. Internet X.509 public key infrastructure certificate and certificate revoca- tion list (CRL) profile. Network Working Group Request for Comments RFC-3280, RSA Laboratories, April 2002, 129 pp. 5. Karn, P., and W. Simpson, “Photuris: Session-key Management Protocol”, RFC-2522, March 1999. 6. Kent, S., R. Atkinson, “IP Authentication Header,” RFC-2402, November 1998. 7. Kent, S., and R. Atkinson, “IP Encapsulating Security Payload (ESP),” RFC-2406, Novem- ber 1998. 8. Maughan, D., M. Schertler, M. Schneider, and J. Turner, “Internet Security Association and Key Management Protocol (ISAKMP),” RFC-2408, November 1998. 9. Mills, D.L. Public key cryptography for the Network Time Protocol. Electrical Engineering Report 00-5-1, University of Delaware, May 2000. 23 pp. 10. Mills, D.L. Proposed authentication enhancements for the Network Time Protocol version 4. Electrical Engineering Report 96-10-3, University of Delaware, October 1996, 36 pp. 11. Mills, D.L., “Network Time Protocol (Version 3) Specification, Implementation and Analy- sis,” RFC-1305, March 1992. 12. Mu, Y., and V. Varadharajan. Robust and secure broadcasting. Proc. INDOCRYPT 2001, LNCS 2247, Springer Verlag, 2001, 223-231. 13. Orman, H., “The OAKLEY Key Determination Protocol,” RFC-2412, November 1998. 14. Prafullchandra, H., and J. Schaad. Diffie-Hellman proof-of-possession algorithms. Network Working Group Request for Comments RFC-2875, Critical Path, Inc., July 2000, 23 pp. 15. Schnorr, C.P. Efficient signature generation for smart cards. J. Cryptology 4, 3 (1991), 161- 174. 16. Stinson, D.R. Cryptography - Theory and Practice. CRC Press, Boca Raton, FA, 1995, ISBN 0-8493-8521-0.