Network Working Group                                   B. Haberman, Ed.
Internet-Draft                                                   JHU/APL
Obsoletes: RFC 1305                                             D. Mills
(if approved)                                                U. Delaware
Intended status: Informational                        September                         February 25, 2007 2008
Expires: March August 28, 2008

         Network Time Protocol Version 4 Autokey Specification
                       draft-ietf-ntp-autokey-00
                       draft-ietf-ntp-autokey-01

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on March August 28, 2008.

Copyright Notice

   Copyright (C) The IETF Trust (2007). (2008).

Abstract

   This memo describes the Autokey security model for authenticating
   servers to clients using the Network Time Protocol (NTP) and public
   key cryptography.  Its design is based on the premise that IPSEC
   schemes cannot be adopted intact, since that would preclude stateless
   servers and severely compromise timekeeping accuracy.  In addition,
   PKI schemes presume authenticated time values are always available to
   enforce certificate lifetimes; however, cryptographically verified
   timestamps require interaction between the timekeeping and
   authentication functions.

   This memo includes the Autokey requirements analysis, design
   principles and protocol specification.  A detailed description of the
   protocol states, events and transition functions is included.  A
   prototype of the Autokey design based on this report memo has been
   implemented, tested and documented in the NTP Version 4 (NTPv4)
   software distribution for Unix, Windows and VMS at
   http://www.ntp.org.

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
     1.1.  Requirements Notation  . . . . . . . . . . . . . . . . . .  4
   2.  NTP Security Model . . . . . . . . . . . . . . . . . . . . . .  4
   3.  Approach . . . . . . . . . . . . . . . . . . . . . . . . . . .  8  7
   4.  Autokey Cryptography . . . . . . . . . . . . . . . . . . . . .  9  8
   5.  NTP Secure Groups  . . . . . . . . . . . . . . . . . . . . . . . . 12 11
   6.  Identity Schemes . . . . . . . . . . . . . . . . . . . . . . . 18 15
   7.  Autokey Operations  Timestamps and Filestamps  . . . . . . . . . . . . . . . . . . 16
   8.  Autokey Protocol Overview  . . . . . 20
   8.  Public Key Signatures and Timestamps . . . . . . . . . . . . . 22 18
   9.  Autokey Protocol Overview Operations . . . . . . . . . . . . . . . . . . 24 . . . . 20
   10. Autokey State Machine Protocol Messages  . . . . . . . . . . . . . . . . . . 21
     10.1.  No-Operation  . . 26
     10.1. Status Word . . . . . . . . . . . . . . . . . . . . 23
     10.2.  Association Message (ASSOC) . . . 26
     10.2. Host State Variables . . . . . . . . . . . . 24
     10.3.  Certificate Message (CERT)  . . . . . . . 28
     10.3. Client State Variables (all modes) . . . . . . . . 24
     10.4.  Cookie Message (COOKIE) . . . . 30
     10.4. Server State Variables (broadcast and symmetric modes) . . 31 . . . . . . . . . . . 24
     10.5.  Autokey Protocol Messages Message (AUTO)  . . . . . . . . . . . . . . . . 31
       10.5.1.  No-Operation . 24
     10.6.  Leapseconds Values Message (LEAP) . . . . . . . . . . . . 25
     10.7.  Sign Message (SIGN) . . . . . . . . 33
       10.5.2.  Association Message (ASSOC) . . . . . . . . . . . 25
     10.8.  Identity Messages (IFF, GQ, MV) . . 33
       10.5.3.  Certificate Message (CERT) . . . . . . . . . . . 25
   11. Autokey State Machine  . . 34
       10.5.4.  Cookie Message (COOKIE) . . . . . . . . . . . . . . . 34
       10.5.5.  Autokey Message (AUTO) . . . 25
     11.1.  Status Word . . . . . . . . . . . . 34
       10.5.6.  Leapseconds Table Message (LEAP) . . . . . . . . . . 35
       10.5.7.  Sign Message (SIGN) . 25
     11.2.  Host State Variables  . . . . . . . . . . . . . . . . 35
       10.5.8.  Identity Messages (IFF, GQ, MV) . . 27
     11.3.  Client State Variables (all modes)  . . . . . . . . . . . 35
     10.6. 29
     11.4.  Server State Variables (broadcast and symmetric modes)  . 30
     11.5.  Protocol State Transitions  . . . . . . . . . . . . . . . . 35
       10.6.1. 30
       11.5.1.  Server Dance  . . . . . . . . . . . . . . . . . . . . 36
       10.6.2. 30
       11.5.2.  Broadcast Dance . . . . . . . . . . . . . . . . . . . 37
       10.6.3. 31
       11.5.3.  Symmetric Dance . . . . . . . . . . . . . . . . . . . 38
   11. 32
     11.6.  Error Recovery  . . . . . . . . . . . . . . . . . . . . . . . . 40
   12. 34
     11.7.  Security Considerations . . . . . . . . . . . . . . . . . . . 42
     12.1. 36
     11.8.  Protocol Vulnerability  . . . . . . . . . . . . . . . . . . 42
     12.2. 36
     11.9.  Clogging Vulnerability  . . . . . . . . . . . . . . . . . . 44
   13. 37
   12. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 45
   14. 38
   13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 45
   15. 38
   14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 46
     15.1. 38
     14.1.  Normative References  . . . . . . . . . . . . . . . . . . . 46
     15.2. 38
     14.2.  Informative References  . . . . . . . . . . . . . . . . . . 46 38
   Appendix A.  Cryptographic Key  Timestamps, Filestamps and Certificate Management Partial Ordering . . . . . 47 39
   Appendix B.  Autokey Error Checking  .  Identity Schemes  . . . . . . . . . . . . . . 48
     B.1.  Packet Processing Rules . . . . 40
     B.1.   Private Certificate (PC) Scheme . . . . . . . . . . . . . 49 41
     B.2.  Timestamps, Filestamps and Partial Ordering  . . . . . . . 51
   Appendix C.  Certificates  . . . . . . . . . . . . . . . . . . . . 52
   Appendix D.  Identity Schemes  . . . . . . . . . . . . . . . . . . 53
     D.1.  Private Certificate (PC) Scheme  . . . . . . . . . . . . . 53
     D.2.   Trusted Certificate (TC) Scheme . . . . . . . . . . . . . 54
     D.3. 41
     B.3.   Schnorr (IFF) Identity Scheme . . . . . . . . . . . . . . . . . . . 56
     D.4. 42
     B.4.   Guillard-Quisquater (GQ) Identity Scheme  . . . . . . . . . . . . . . . . . 58
     D.5. 44
     B.5.   Mu-Varadharajan (MV) Identity Scheme  . . . . . . . . . . . 60
     D.6.  Interoperability Issues  . . . . . . . . . . . . . . . . . 64 46
   Appendix E. C.  ASN.1 Encoding Rules  . . . . . . . . . . . . . . . . 66
     E.1. 48
     C.1.   COOKIE request, IFF response, GQ response, MV response  . 49
     C.2.   Certificates  . . . . . . . . 66
     E.2.  CERT response, SIGN request and response . . . . . . . . . 67 . . . . . 49
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 68 51
   Intellectual Property and Copyright Statements . . . . . . . . . . 70 53

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 ctually sent by the intended server and
   not manufactured or modified by an intruder.  Ubiquity requires that
   any
   a client can verify the authenticity of any a 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. attacks.

   This memo describes a cryptographically sound and efficient
   methodology for use in the Network Time Protocol (NTP) [1].  The
   various key agreement schemes [2][3][4] proposed 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.

   The Autokey protocol is based on a combination of PKI and a pseudo-random 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.

1.1.  Requirements Notation

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [5]. memo.

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
   media
   keys which are valid only over designated esignated 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 memo 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 mitigation 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. memo.  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) [6] [5] and Authentication Header (AH) [7] [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 memo 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 on-wire timestamp
   exchange scheme is inherently resistant to spoofing spoofing, packet loss 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 attacks.

   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 Section 12, 11.7, 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 Section 12, 11.7, the
       middleman does not have the server private keys or identity
       parameters. keys.

   The NTP security model assumes the following possible limitations.

   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 efficiently 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  Client security 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. net.  Private values must never be disclosed
       beyond the machine on which they were created 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, by default the string 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 memo is designed to meet the
   following objectives.  In-depth discussions on these objectives is in
   the web briefings and will not be elaborated in this memo.  Note that
   here and elsewhere in this memo 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 [8]. [7].  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 not significantly degrade provide for the potential accuracy 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 packet has passed all header 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.

   3.

   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.

   4.

   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.

   5.

   6.  It must function in all the modes supported by NTP, including
       server, symmetric and broadcast modes.

   6.  It must not require intricate per-client or per-server
       configuration other than the availability of the required
       cryptographic keys and certificates.

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 credentials and public key algorithms
   certificates to encrypt cookies. provide traceable authority.  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.

                +------------------+
                | NTP Header and   |
                | Extension Fields |
                +------------------+   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                      |       |        |    Message Authenticator Code |
                     \|/     \|/       +              (MAC)            +
                ********************   | +-------------------------+   |
                *   Compute Hash   *<----| Key ID | Message Digest |   +
                ********************   | +-------------------------+   |
                          |            +-+-+-+-+-+-+-|-+-+-+-+-+-+-+-+-+
                         \|/                        \|/
                +------------------+       +-------------+
                |  Message Digest  |------>|   Compare   |
                +------------------+       +-------------+

                     Figure 1: Message Authentication

   There are three

   Autokey protocol variants corresponding to each of
   the three NTP modes: server, symmetric and broadcast.  All three
   variants make use of uses 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 list.  The Autokey protocol operates separately for each
   association, so there may be several autokey sequences operating
   independently at the same time.

                   +-------------+-------------+--------+--------+
                   | Src Address | Dst Address | Key ID | Cookie |
                   +-------------+-------------+--------+--------+

                          Figure 2: NTPv4 Autokey

   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, IPv4 the Source Address and Dest Address fields contain
   32 bits; for use with IPv6, 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 NTP 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.
   MAC.  For packets without extension fields, the cookie is a shared
   private value conveyed in encrypted form. value.  For packets with extension fields, the cookie has a
   default public value of zero, since these packets can be are 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.

   For scenarios where the endpoint IP addresses are not available, an
   optional public identification value could be used instead  [The use of the
   addresses.  Examples include the Interplanetary Internet, where
   bundles are identified by name rather than address.  Specific
   provisions are alternative
   means, such as Autokey host names (discussed later) or hashes of
   these names may be a topic for further study. future study.]

+-----------+-----------+------+------+   +---------+  +-----+------+
|Src Address|Dst Address|Key ID|Cookie|-->|         |  |Final|Final |
+-----------+-----------+------+------+   | Session |  |Index|Key ID|
     |           |         |        |     | Key ID  |  +-----+------+
    \|/         \|/       \|/      \|/    |  List   |     |       |
   *************************************  +---------+    \|/     \|/
   *          COMPUTE HASH             *             *******************
   *************************************             *COMPUTE SIGNATURE*
     |                    Index n                    *******************
    \|/                                                       |
   +--------+                                                 |
   |  Next  |                                                \|/
   | Key ID |                                           +-----------+
   +--------+                                           | Signature |
   Index n+1                                            +-----------+

                    Figure 3: Constructing the Key List

   Figure Figure 3 shows how the autokey list and autokey values are
   computed.  The key IDs used in the autokey 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 autokey seed and
   assigned index 0.  The first 32 bits of the result in network byte
   order become the next THe MD5 hash of the autokey is the key value
   saved in the key cache along with the key ID.  The first 32 bits of
   the key become the key ID for the next autokey assigned index 1.

   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 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.

                   +------------------+
                   |  NTP Header and  |
                   | Extension Fields |
                   +------------------+
                        |       |
                       \|/     \|/                     +---------+
                     ****************    +--------+    | Session |
                     * COMPUTE HASH *<---| Key ID |<---| Key ID  |
                     ****************    +--------+    |  List   |
                             |                |        +---------+
                            \|/              \|/
                   +----------------------------------+
                   | Message Authenticator Code (MAC) |
                   +----------------------------------+

                      Figure 4: Transmitting Messages

   The index of the last key ID autokey 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. signed for use later.  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 verify the 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.  NTP Secure Groups

   A digital signature scheme provides an authentic certificate trail,
   but does not provide protection against masquerade, unless the server
   identity is verified by other means.  The PKI security model assumes
   each host is able to verify the certificate trail to a trusted
   certificate authority (CA), where each ascendant host must prove
   identity to the immediately descendant host 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 D.  Certificate trails and identification schemes secure groups are at
   the heart of the NTP security model preventing masquerade and
   middleman attacks.  The Autokey protocol operates used to hike the trails define cryptographic compartments and then run the identity schemes.
   security hierarchies.  A NTP secure group consists of a number of hosts
   dynamically assembled as a forest with roots the trusted hosts (THs)
   at the lowest stratum of the group.  The trusted hosts THs do not have to be, but
   often are, primary (stratum 1) servers.  A trusted authority (TA), usually
   one of the trusted hosts,
   not necessarily a group host, generates private identity keys for
   servers and public identity media
   and deploys selected values to keys for clients at the group members.  The identity
   values are leaves of two kinds, encrypted private the
   forest.  The TA deploys the server keys used by to the THs and other
   designated servers with
   dependent clients using secure means and nonencrypted posts the client keys on a
   public parameters used by web site.

   For Autokey purposes all
   hosts, including those that are not hosts belonging to a secure group members, but depend on have the
   same group members for authentication purposes.Figure 5

                     +-------------+ +-------------+ +-------------+
                     | name but different host names, not necessarily related to
   the DNS names.  The group name is used in the subject and issuer
   fields of the TH certificates; the host name is used in these fields
   for other hosts.  Thus, all host certificates are self-signed.
   During the Autokey protocol a client requests the server to sign its
   certificate and caches the result.  A certificate trail is
   constructed by each host, possibly via intermediate hosts and ending
   at a TH.  Thus, each host along the trail retrieves the entire trail
   from its server(s) and provides this plus its own signed certicicates
   to its clients.

   Secure groups can be configured as hierarchies where a TH of one
   group can be a client of one or more other groups operating at a
   lower stratum.  In one scenario, groups RED and GREEN can be
   cryptographically distinct, but both be clients of group BLUE
   operating at a lower stratum.  In another scenario, group CYAN can be
   a client of multiple groups YELLOW and MAGENTA, both operating at a
   lower stratum.  There are many other scenarios, but all must be
   configured to include only acyclic certificate trails.

   In Figure 5, the Alice group consists of THs 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.  Public certificates are identified by the subject and
   signed by the issuer.  Note that the server keys have been previously
   installed on Brenda and Denise and the client keys installed on all
   machines.

                     +-------------+ +-------------+ +-------------+
                     |   Alice     | |   Brenda    | |   Denise    |
                     |             | |             | |             |
                     | +-+-+-+-+   | | +-+-+-+-+   | | +-+-+-+-+   |
   Certificate       | | Alice |   | | | Brenda|   | | | Denise|   |
   +-+-+-+-+-+       | +-+-+-+-+   | | +-+-+-+-+   | | +-+-+-+-+   |
   | Subject |       | | Alice*| 1 | | | Alice | 4 | | | Carol | 4 |
   +-+-+-+-+-+       | +-+-+-+-+   | | +-+-+-+-+   | | +-+-+-+-+   |
   | Issuer  | S     |             | |             | |             |
   +-+-+-+-+-+       | +=======+   | | +-+-+-+-+   | | +-+-+-+-+   |
                     | ||Alice|| 3 | | | Alice |   | | | Carol |   |
    Group Key        | +=======+   | | +-+-+-+-+   | | +-+-+-+-+   |
   +=========+       +-------------+ | | Alice*| 2 | | | Carol*| 2 |
   || Group || S     |     Carol   | | +-+-+-+-+   | | +-+-+-+-+   |
   +=========+       |             | |             | |             |
                     | +-+-+-+-+   | | +-+-+-+-+   | | +-+-+-+-+   |
    S = step         | | Carol |   | | | Brenda|   | | | Denise|   |
    * = trusted      | +-+-+-+-+   | | +-+-+-+-+   | | +-+-+-+-+   |
                     | | Carol*| 1 | | | Brenda| 1 | | | Denise| 1 |
                     | +-+-+-+-+   | | +-+-+-+-+   | | +-+-+-+-+   |
                     |             | |             | |             |
                     | +=======+   | | +=======+   | | +=======+   |
                     | ||Alice|| 3 | | ||Alice|| 3 | | ||Alice|| 3 |
                     | +=======+   | | +=======+   | | +=======+   |
                     +-------------+ +-------------+ +-------------+
                        Stratum 1                Stratum 2

                     +---------------------------------------------+
                     |                  Eileen                     |
                     |                                             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Eileen|   | Eileen|             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Brenda|   | Carol | 4           |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |                                             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Alice |   | Carol |             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Alice*|   | Carol*| 2           |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |                                             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Brenda|   | Denise|             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Alice |   | Carol | 2           |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |                                             |
                     |                 +-+-+-+-+                   |
                     |                 | Eileen|                   |
                     |                 +-+-+-+-+                   |
                     |                 | Eileen| 1                 |
                     |                 +-+-+-+-+                   |
                     |                                             |
                     |                 +=======+                   |
                     |                 ||Alice|| 3                 |
                     |                 +=======+                   |
                     +---------------------------------------------+
                                       Stratum 3

                        Figure 5: NTP Secure Groups
   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  The girls start by loading the host loads its key, sign key, 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 group key.  They start the Autokey protocol which establishes the server
       name, signature scheme, certificate by
       exchanging host names and negotiating digest/signature schemes
       and identity scheme for each
       group host. schemes.

   2.  They continue to load certificates recursively until a self-signed 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 selected identity schemes
       described below to
       verify each has that Alice and Carol have the correct group keys key previously
       deployed
       generated by Alice.  If this succeeds, each continues in step 4.

   4.  Brenda and Denise present their certificates to Alice and Carol 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 verify 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.  Every host holds the public parameters generated by a TA.  Those
       hosts with clients hold in addition the secret group key.

   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 can prove it has
       the same key as the client and has an unbroken certificate trail
       to a trusted host.

   For various reasons it may be convenient for the trusted hosts a server to
   hold parameters have client
   keys for one or more groups operating at a lower stratum. 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 and Alice, R, S to the Helen group and hosts X, Y and Z belong to
   the Carol group.
   Carol.  While not strictly necessary, hosts A, B and R are stratum 1
   and presumed trusted; trusted, but the TA generating the group identity keys and
   parameters could
   be one of them or another not shown.

                         *****     *****     @@@@@
           Stratum 1     * A *     * B *     @ R @
                         *****     *****     @@@@@
                             \     /         /
                              \   /         /
                              *****     @@@@@                *********
                   2          * C *     @ S @                * Alice *
                              *****     @@@@@                *********
                              /   \     /
                             /     \   /                     @@@@@@@@@
                         *****     #####                     @ Helen @
                   3     * D *     # X #                     @@@@@@@@@
                         *****     #####
                                   /   \                     #########
                                  /     \                    # Carol #
                              #####     #####                #########
                   4          # Y #     # Z #
                              #####     #####

                 Figure 6: Hierarchical Overlapping Groups

   The intent of the design scenario is to provide security separation, so that
   servers cannot masquerade as TAs in other groups and clients cannot
   masquerade as servers.  Assume for example that Alice and Helen
   belong to national standards laboratories and their group server 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 group parameters client keys for both Alice and Helen and has group
   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 it belongs to either Alice or Helen.

   In some scenarios

6.  Identity Schemes

   A digital signature scheme provides secure server authentication, but
   it would be desirable that servers cannot
   masquerade as does not provide protection against masquerade, unless the TA and clients cannot masquerade server
   identity is verified by other means.  The PKI model requires a server
   to prove identity to the client by a certificate trail, but
   independent means such as servers.  This
   can a drivers license are required for a CA to
   sign the server certificate.  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 assured using an intrinsic capability of Autokey itself.

   While the MV identity scheme described later.  It
   allows the same broadcast transmission in [8] is based on a ubiquitous
   Diffie-Hellman infrastructure, it is expensive to be authenticated by more
   than one key, one used internally by the laboratories (Alice and/or
   Helen) generate and the other handed out use
   when compared to clients like Carol. others described in Appendix B.  In the MV principle, an
   ordinary public key scheme these keys can could be separately activated upon subscription and
   deactivated if the subscriber fails to pay the bill.  In devised for this purpose, but the MV
   scheme
   most stringent Autokey design requires that every challenge, even if
   duplicated, results in a key can be deactivated without requiring different acceptable response.

   There are five schemes now implemented in the other keys NTPv4 reference
   implementation to
   be recomputed.

   Figure 7 shows operational details where more than one group is
   involved, in this case Carol 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 Alice.  As (5) a modified Mu-Varadharajan algorithm (MV).
   Following is a summary description of each; details are given in the previous example,
   Brenda has configured Alice as her time source and Denise has
   configured Carol
   Appendix B.

   The PC scheme involves a private certificate as her time source.  Alice and Brenda have group
   keys key.  The
   certificate is distributed to all other group members by secure means
   and parameters for is never revealed outside the Alice group; Carol group.  In effect, the private
   certificate is used as a symmetric key.  This scheme is used
   primarily for testing and Denise have group
   keys development and parameters is not recommended for
   regular use and is not considered further in this memo.

   All other schemes involve a conventional certificate trail as
   described in RFC 2510 [9].  This is the Carol group.  Eileen has parameters for
   both groups. default scheme when an
   identity scheme is not specified.  While the remaining identity
   schemes incorporate TC, it is not by itself considered further in
   this memo.

   The protocol operates as previously three remaining schemes IFF, GQ and MV involve a
   cryptographically strong challenge-response exchange where an
   intruder cannot deduce the server key, even after repeated
   observations of multiple exchanges.  In addition, the MV scheme is
   properly described to as a zero-knowledge proof, because the client can
   verify
   Alice to Brenda and Carol to Denise.

                     +-------------+ +-------------+ +-------------+
                     |   Alice     | |   Brenda    | |   Denise    |
                     |             | |             | |             |
                     | +-+-+-+-+   | | +-+-+-+-+   | | +-+-+-+-+   |
   Certificate       | | Alice |   | | | Brenda|   | | | Denise|   |
   +-+-+-+-+-+       | +-+-+-+-+   | | +-+-+-+-+   | | +-+-+-+-+   |
   | Subject |       | | Alice*| 1 | | | Alice | 4 | | | Carol | 4 |
   +-+-+-+-+-+       | +-+-+-+-+   | | +-+-+-+-+   | | +-+-+-+-+   |
   | Issuer  | S     |             | |             | |             |
   +-+-+-+-+-+       | +=======+   | | +-+-+-+-+   | | +-+-+-+-+   |
                     | ||Alice|| 3 | | | Alice |   | | | Carol |   |
    Group Key        | +=======+   | | +-+-+-+-+   | | +-+-+-+-+   |
   +=========+       +-------------+ | | Alice*| 2 | | | Carol*| 2 |
   || Group || S     |     Carol   | | +-+-+-+-+   | | +-+-+-+-+   |
   +=========+       |             | |             | |             |
                     | +-+-+-+-+   | | +-+-+-+-+   | | +-+-+-+-+   |
    S = step         | | Carol |   | | | Brenda|   | | | Denise|   |
    * = trusted      | +-+-+-+-+   | | +-+-+-+-+   | | +-+-+-+-+   |
                     | | Carol*| 1 | | | Brenda| 1 | | | Denise| 1 |
                     | +-+-+-+-+   | | +-+-+-+-+   | | +-+-+-+-+   |
                     |             | |             | |             |
                     | +=======+   | | +=======+   | | +=======+   |
                     | ||Carol|| 3 | | ||Alice|| 3 | | ||Carol|| 3 |
                     | +=======+   | | +=======+   | | +=======+   |
                     +-------------+ +-------------+ +-------------+
                        Stratum 1                Stratum 2

                     +---------------------------------------------+
                     |                  Eileen                     |
                     |                                             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Eileen|   | Eileen|             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Brenda|   | Carol | 4           |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |                                             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Alice |   | Carol |             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Alice*|   | Carol*| 2           |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |                                             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Brenda|   | Denise|             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Alice |   | Carol | 2           |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |                                             |
                     |                 +-+-+-+-+                   |
                     |                 | Eileen|                   |
                     |                 +-+-+-+-+                   |
                     |                 | Eileen| 1                 |
                     |                 +-+-+-+-+                   |
                     |                                             |
                     |          +=======+    +=======+             |
                     |          ||Alice||    ||Carol|| 3           |
                     |          +=======+    +=======+             |
                     +---------------------------------------------+
                                       Stratum 3

                   Figure 7: Multiple Overlapping Groups

   The interesting case is Eileen, who may verify identity either via
   Brenda or Denise or both.  To do that she uses the public pameters of
   either Alice and Carol or both.  But, Eileen doesn't know which of
   the two parameters to use until hiking the certificate trail to find
   the trusted certificate of either Alice or Carol and then loading the
   associated parameters.  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 parameters for all the
   lowest-stratum trusted hosts it is ever likely to find.

6.  Identity Schemes

   While the identity scheme described in [9] is based on a ubiquitous
   Diffie-Hellman infrastructure, it is expensive to generate and use
   when compared to others described in Appendix D.  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 D.

   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.  It is
   included here primarily as a yardstick and protocol exercise.

   All other schemes involve a conventional certificate trail as
   described in RFC 4210 [10], where each certificate is signed by an
   issuer one step closer to the trusted hosts, which have self-signed
   trusted certificates.  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 ending at a trusted host, 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, parameters 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.

   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
   NTPv4 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:

   1.  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.

   2.  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.

   3.  Public values signature/timestamp.  All public key and
       certificate 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 A.

   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 B.

   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 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 hosts 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 or
   without 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 host 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 host 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 D or proof-of-possession scheme in [9] 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 host continues with the cookie and autokey exchanges
   as necessary to complete the protocol.  Upon completion the host
   verifies packets using digital signatures and/or the autokey
   sequence.

   Once synchronized to a proventic source, the host continues with the
   sign exchange where the server acting as CA signs the host
   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 host uses the signed certificate in its own role as
   CA for dependent clients.

   A final exchange occurs when the server has the NIST leapseconds
   table, as indicated in the host status word.  If so, the host
   requests the table and compares the filestamp with its own
   leapseconds table filestamp, if available.  If the server table is
   newer than the host table, the host replaces its table with the
   server table.  The host, acting as server, can now provide the most
   recent table to 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.

10.1.  Status Word

   Each server and client operating also as a server implements a host
   status word, while each client implements an association status word
   for each server.  Both words have the format and content shown in
   Figure 8.  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.

                        1                   2                   3
    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    Digest / Signature NID     |    Client     | Ident |  Host |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                           Figure 8: Status Word

   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
   enabled, these bits never come dim unless a general reset occurs and
   the protocol is restarted from the beginning.  The status bits are
   defined as follows:

   o  ENB (31) - Lit if the server implements the Autokey protocol

   o  LPF (30) - Lit if the server has loaded a valid leapseconds file

   o  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 D 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:

   o  VAL (0x0100) - Lit when the server certificate and public key are
      validated.

   o  IFF (0x0200) - Lit when the server identity credentials are
      confirmed.

   o  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 enabled, signed values in
      subsequent messages are presumed proventic.

   o  CKY (0x0800) - Lit when the cookie is received and validated.
      When enabled, key lists can be generated.

   o  AUT (0x1000) - Lit when the autokey values are received and
      validated.  When enabled, clients can validate packets without
      extension fields according to the autokey sequence.

   o  SGN (0x2000) - Lit when the host certificate is signed by the
      server.

   o  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 enabled
   (set to 1) or disabled (set to 0) as the protocol proceeds; all
   except LST are active whether or not the protocol is running.  LST is
   enabled 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 enabled when the client
   has synchronized to a proventic source and never dim after that.
   There are two error bits maintained by the NTP on-wire protocol:

   o  LBK - indicates the received packet does not match the last one
      sent
   o  DUP - indicates a duplicate packet

   These bits, which are described in Appendix B, are lit if the
   corresponding error has occurred for the current packet and dim
   otherwise.

10.2.  Host State Variables

   Following is a list of state variables used by the server protocol.

   o  Host Name - The name of the server; by default, the string
      returned by the Unix gethostname() library function.  The name
      must agree with the subject name in the server certificate

   o  Host Status Word - This word is initialized when the host first
      starts up.  The format is described above

   o  Host Key - The RSA public/private key pair used to encrypt/decrypt
      cookies.  This is also the default sign key

   o  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

   o  Sign Digest - The message digest algorithm used to compute the
      signature before encryption

   o  IFF identity - The keys and parameters used in the optional IFF
      identity scheme described in Appendix D

   o  GQ identity - The keys and parameters used in the optional GQ
      identity scheme described in Appendix D

   o  MV identity - The keys and parameters used in the optional MV
      identity scheme described in Appendix D

   o  Server Seed - The private value hashed with the IP addresses to
      construct the cookie

   o  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 when 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 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

   o  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

   o  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 [11]

   o  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

   o  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

10.3.  Client State Variables (all modes)

   Following is a list of state variables used by the client association
   protocol in all modes.

   o  Association ID - The association ID used in responses.  It is
      assigned when the association is mobilized

   o  Server Association ID - The server association ID used in
      requests.  It is copied from the first nonzero association ID
      field in a response

   o  Server Host Name - The server host name determined in the
      parameter exchange

   o  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

   o  Association Status Word - The host status word of the server
      determined in the parameter exchange

   o  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

   o  Server Message Digest - The digest/signature scheme determined in
      the parameter exchange

   o  Identification Challenge - A 512-bit nonce used in the
      identification exchange

   o  Group Key - A set of values used by the identification exchange.
      It identifies the cryptographic compartment shared by the server
      and client

   o  Receive Cookie Values - The cookie returned in a COOKIE response,
      together with its timestamp and filestamp

   o  Receive Autokey Values - The autokey values returned in an AUTO
      response, together with its timestamp and filestamp

   o  Receive Leapsecond Values - The leapsecond table returned by a
      LEAP response, together with its timestamp and filestamp

10.4.  Server State Variables (broadcast and symmetric modes)

   Following is a list of server state variables used in broadcast and
   symmetric modes.

   o  Send Cookie Values - The cookie encryption values, signature and
      timestamps

   o  Send Autokey Values - The autokey values, signature and timestamps

   o  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

   o  Current Key Number - The index of the entry on the Key List to be
      used at the next poll opportunity

10.5.  Autokey Protocol Messages

   There are currently eight Autokey requests and eight corresponding
   responses.  The NTPv4 packet format is described in [1] and the
   extension field format used for these messages is illustrated in
   Figure 9.

    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |          Field Type           |            Length             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                         Association ID                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           Timestamp                           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           Filestamp                           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                          Value Length                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   \                                                               /
   /                             Value                             \
   \                                                               /
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        Signature Length                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   \                                                               /
   /                           Signature                           \
   \                                                               /
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   \                                                               /
   /                      Padding (if needed)                      \
   \                                                               /
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                  Figure 9: NTPv4 Extension Field Format

   Each extension field is zero-padded to a 4-octet boundary.  The
   Length field covers the entire extension field, including the Length
   and Padding fields.  While the minimum field length is 8 octets, a
   maximum field length remains to be established.  The reference
   implementation discards any packet with a total field length more
   than 1024 octets.

   If an extension field is present, the parser examines the Length
   field.  If the length is less than 4 or not a multiple of 4, a format
   error has occurred and the packet MUST be discarded; otherwise, the
   parser increments the pointer by the length value.  The parser now
   uses the same rules as above to determine whether a MAC is present
   and/or another extension field.

   The 8-bit Code field specifies the request or response operation,
   while the 4-bit Version Number (VN) field is 2 for the current
   protocol version.  There are four flag bits: bit 0 is the Response
   Flag (R) and bit 1 is the Error Flag (E); the other two bits are
   presently unused and should be set to 0.  The remaining fields will
   be described later.

   In the most common protocol operations, a client sends a request to a
   server with an operation code specified in the Code field and both
   the R bit and E bit dim.  The Association ID field is set to the
   value previously received from the server or 0 otherwise.  The server
   returns a response with the same operation code in the Code field and
   lights the R bit.  The server can also light the E bit in case of
   error.  The Association ID field is set to the association ID of the
   server as a handle for subsequent exchanges.  If for some reason the
   association ID value in a request does not match the association ID
   of any mobilized association, the server returns the request with
   both the R and E bits lit.  Note that it is not necessarily a
   protocol error to send an unsolicited response with no matching
   request.

   In some cases not all fields may be present.  For requests, until a
   client has synchronized to a proventic source, signatures are not
   valid.  In such cases the Timestamp and Signature Length fields are 0
   and the Signature field is empty.  Responses are generated only when
   the responder has synchronized to a proventic source; otherwise, an
   empty response message is sent.  Some request and error response
   messages carry no value or signature fields, so in these messages
   only the first two words are present.

   The Timestamp and Filestamp words carry the seconds field of an NTP
   timestamp.  The Timestamp field establishes the signature epoch of
   the data field in the message, while the filestamp establishes the
   generation epoch of the file that ultimately produced the data that
   is signed.  A signature and timestamp are valid only when the signing
   host is synchronized to a proventic source; otherwise, the timestamp
   is zero.  A cryptographic data file can only be generated if a
   signature is possible; otherwise, the filestamp is zero, except in
   the ASSOC response message, where it contains the server status word.

10.5.1.  No-Operation

   A No-operation request (Field Type = 0) does nothing except return an
   empty reply which can be used as a crypto-ping.

10.5.2.  Association Message (ASSOC)

   An Association Message (Field Type = 1) 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 server status word in the filestamp field and in
   addition the host name, which by default is 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 PC
   exchange is complete at this point.

10.5.3.  Certificate Message (CERT)

   A Certificate Message (Field Type = 2) is used in the certificate
   exchange to obtain a certificates 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 server host certificate.  The
   response contains the certificate encoded in X.509 format with ASN.1
   syntax as described in Appendix E.

   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 server has the CIS, indicating a trusted certificate.
   If a trusted certificate is found, correct group key without either the server
   or client stops knowing its value.  These schemes start when the exchange and
   lights VAL.  If client
   sends a self-signed certificate is found but not trusted, nonce to the protocol loops at polite intervals until one is found or timeout.

10.5.4.  Cookie Message (COOKIE)

   The Cookie Message (Field Type = 3) is used in server server, which then rolls its own nonce, performs
   a mathematical operation and symmetric
   modes sends the results to obtain the server cookie. client.  The request contains
   client performs another mathematical operation and verifies the host
   results are correct.

7.  Timestamps and Filestamps

   While public key encoded with ASN.1 syntax as described in Appendix E.  The
   response contains the cookie encrypted by signatures provide strong protection against
   misrepresentation of source, computing them is expensive.  This
   invites the public key in opportunity for an intruder to clog the
   request.  The client or server
   by replaying old messages or originating bogus messages.  A client
   receiving such messages might be forced to verify what turns out to
   be an invalid signature and timestamps are determined when consume significant processor resources.

   In order to foil such attacks, every Autokey message carries a
   timestamp in the cookie
   is encrypted.  If form of the response is valid, NTP seconds when it was.  If the client lights CKY.

10.5.5.  Autokey Message (AUTO)

   The Autokey Message (Field Type = 4) system
   clock is used synchronized to obtain the autokey
   values.  The request contains no value.  The response contains two
   32-bit words in network order.  The first word a proventic source, a signature is the final key ID,
   while the second produced
   with valid (nonzero) timestamp.  Otherwise, there is the index of the final key ID.  The no signature and
   timestamps are determined when the key list is generated.  If
   the
   response timestamp is valid, the client lights AUT.

10.5.6.  Leapseconds Table Message (LEAP) invalid (zero).  The Leapseconds Table Message (Field Type = 5) is protocol detects and discards
   extension fields with old or duplicate timestamps, before any values
   are used or signatures are verified.

   Signatures are computed only when cryptgraphic values are created or
   modified, which is by design not very ofter.  Extension fields
   carrying these signatures are copied to exchange
   leapseconds tables.  The request and response messages have the same
   format, except that as needed, but the R bit
   signarutres are not recomputed.  There are three signature tyupes:

   1.  Cookie signature/timestamp.  The cookie is dim in signed when created by
       the request server and lit in sent to the
   response.  Both cliente.

   2.  Autokey signature/timestamp.  The autokey values are signed when
       the request key list is created.

   3.  Public values signature/timestamp.  The public key, certificate
       and response contains the leapseconds
   table as parsed from the NIST leapseconds file.  If leapsecond values are signed at the client
   already has a copy time of generation, which
       occurs when the leapseconds data, it uses the one with the
   latest filestamp and discards the other.  If the response system clock is valid,
   the client lights LPT.

10.5.7.  Sign Message (SIGN)

   The Sign Message (Field Type = 6) requests the server first synchronized to sign and
   return the certificate presented in a proventic
       source, when the request. values have changed and about once per day after
       that, even if these values have not changed.

   The request
   contains the client certificate encoded in X.509 format most recent timestamp received of each type is saved for
   comparison.  Once a signature with ASN.1
   syntax as described in Appendix E.  The response contains the client
   certificate signed by valid timestamp has been received,
   messages with invalid timestamps or earlier valid timestamps of the server private key.  If
   same type are discarded before the certificate signature is
   valid when received by the host, it verified.  This is linked
   most important in broadcast mode, which could be vulnerable to a
   clogging attack without this test.

   All cryptographic values used by the certificate list protocol are time sensitive and SGN
   are regularly refreshed.  In particular, files containing
   cryptographic values used by signature and encryption algorithms are
   regenerated from time to time.  It is lit.

10.5.8.  Identity Messages (IFF, GQ, MV)

   The Identity Messages (Field Type = 7 (IFF), 8 (GQ), or 9 (MV))
   contains the host challenge, usually a 160- or 512-bit nonce.  The
   response contains the result intent that file
   regenerations occur without specific advance warning and without
   requiring prior distribution of the mathematical operation defined in
   Appendix D.  The Response file contents.  While
   cryptographic data files are not specifically signed, every file is encoded in ASN.1 syntax as described
   associated with a filestamp showing the NTP seconds at the creation
   epoch.

   Filestamps and timestamps can be compared in
   Appendix E.  The response signature any combination and timestamp are determined when
   the response is sent.  If use
   the response is valid, IFF is lit.

10.6.  Protocol State Transitions

   The protocol state machine is very simple but robust.  The state same conventions.  It is
   determined by the server status bits defined above.  The state
   transitions of necessary to compare them from time to
   time to determine which are earlier or later.  Since these quantities
   have a granularity only to the three dances second, such comparisons are shown below.  The capitalized
   truth values represent ambiguous
   if the server status bits.  All server bits values are
   initialized dim and lit upon the arrival of a specific response
   message, as detailed above.

   When in the system clock same second.

   It is first set and about once per day after that,
   or when important that filestamps be proventic data; thus, they cannot
   be produced unless the system clock is stepped, producer has been synchronized to a proventic
   source.  As such, the server seed is refreshed,
   signatures and timestamps updated and filestamps throughout the protocol restarted in NTP subnet represent
   a partial ordering of all
   associations.  When creation epochs and serve as means to
   expunge old data and insure new data are consistent.  As the data are
   forwarded from server seed is refreshed or a new to client, the filestamps are preserved,
   including those for certificate
   or and leapseconds table is received, the public values timestamp is
   reset values.  Packets with
   older filestamps are discarded before spending cycles to verify the current time
   signature.

8.  Autokey Protocol Overview

   The Autokey protocol includes a number of request/response exchanges
   that must be completed in order.  In each exchange a client sends a
   request message with data and all signatures expects a server response message with
   data.  Requests and responses are recomputed.

10.6.1.  Server Dance containined in extension fields,
   one request or response in each field, as described later.  An NTP
   packet can contain one request message and one or more response
   messages.  Following is a list of these messages.

   o  Parameter exchange.  The server dance begins when request includes the client host sends an ASSOC request to name;
      the
   server.  It ends when response one contains the first signature is verified server host name and PRV is lit.
   Subsequent packets received without extension fields are validated by status word.
      The status word specifies the autokey sequence.  An optional LEAP exchange updates digest/signature scheme it will use
      and the
   leapseconds table.  Note identity schemes it supports.

   o  Certificate exchange.  The request includes the order subject name of a
      certificate; the identity exchanges and response consists of a signed certificate with
      that
   only subject name.  If the first one will be used if multiple schemes are available.
   Note also that the SIGN and LEAP requests are issuer name is not issued until the
   client same as the
      subject name, it has synchronized been signed by a host one step closer 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)
                           /*
      trusted host and 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)
                           /* signe exchange */
                           SIGN_request(Host_Certificate);
                   else if (SYN && LPF & !LPT)
                           /* leapseconds exchange */
                           LEAP_request;

           }

   When retrieval continues for the PC identity scheme issuer
      name.  If it is in use, the ASSOC response lights VAL,
   IFF, and SIG; the COOKIE response lights CKY and AUT; trusted and self-signed, the first
   valid signature lights PRV.

10.6.2.  Broadcast Dance

   The only difference between trail concludes at
      the broadcast trusted host.  If nontrusted and server dances is self-signed, the
   inclusion host
      certificate has not yet been signed, so the trail temporarily
      loops.  Completion of an autokey values this exchange following lights the cookie VAL bit as
      described below.

   o  Indentity exchange.  The broadcast dance begins when the host receives the
   first broadcast packet, which includes an ASSOC response with
   association ID.  The host uses the association ID to initiate a
   server dance certificate trail is generally not
      considered sufficient protection against middleman attacks unless
      additional protection such as described inor proof-of-possession
      scheme in order to calibrate the propagation delay.

   The dance ends when the first signature [8] is verified and PRV available, but this is lit.
   Subsequent packets received without extension fields are validated by expensive and requires
      servers to retain state.  Autokey can use one of the autokey sequence.  An optional LEAP challenge/
      response identity schemes described in Appendix B.  Completion of
      this exchange updates lights the
   leapseconds table.  When IFF bit as described below.

   o  Cookie exchange.  The request includes the server generates a new public key list, the
   server replaces of the ASSOC response with an AUTO
      client.  THe response in includes 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)
                           /* server cookie encrypted with
      thise key.  The client uses this value when constructing the key
      list.  Completion of this exchange */
                           COOKIE_request;
                   else if (!AUT)
                           /* lights the CKY bit as described
      below.

   o  Autokey exchange.  The request includes either no data or the
      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 of the PC identity scheme is peer in use, the ASSOC symmetric modes.  The response sets VAL,
   IFF, and SIG to 1;
      includes the COOKIE response sets CKY and AUT to 1; and autiokey values of the
   first valid signature set PRV server or peer.  These values
      are used to 1.

10.6.3.  Symmetric Dance

   The symmetric dance verify the autokey sequence.  Completion of this
      exchange lights the AUT bit as described below.

   o  Sign exchange.  This exchange is intricately choreographed.  It begins executed only when the
   active peer sends an ASSOC request client has
      synchronized to a proventic source.  The request includes the passive peer.
      self-signed client certificate.  The passive
   peer mobilizes an association server acting as CA
      interprets the certificate as a X.509v3 certificate request.  It
      extracts the subject, issuer, and both peers step extension fields, builds a new
      certificate with these data along with its own serial number and
      expiration time, then signs it using its own public key and
      includes it in the same dance from response.  The client uses the beginning.  Until signed
      certificate in its own role as server for dependent clients.
      Completion of this exchange lights the active peer SGN bit as described below.

   o  Leapseconds exchange.  This exchange is executed only when the
      client has synchronized to a proventic
   source (which could be the passive peer) and can sign messages, source.  This exchange
      occurs when the
   passive peer loops waiting for server has the timestamp leapseconds values, as indicated in
      the ASSOC response to
   be lit.  Until then, the active peer dances host status word.  If so, the server steps, but
   skips client requests the sign, cookie values 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
      compares them with its own values, if (!LST)
                           /* autokey available.  If the server
      values response */
                           AUTO_response;
                   else if (!AUT)
                           /* autokey are newer than the client values, the client replaces its
      own with the server values.  The client, acting as server, can now
      provide the most recent values to its dependent clients.  In
      symmetric mode, this results in both peers having the newest
      values.  Completion of this exchange */
                           AUTO_request;
                   else if (SYN && LPF & !LPT)
                           /* leapseconds exchange */
                           LEAP_request;
           }

   When lights the PC LPT bit as
      described below.

   Once the certificates and identity scheme have been validated, subsequent
   packets are validated by digital signatures and autokey sequences.
   The association is now proventic with respect to the downstratum
   trusted host, but in use, not yet selectable to discipline the ASSOC response lights VAL,
   IFF, system
   clock.  The associations accumulate time values and SIG; the COOKIE response lights CKY mitigation
   algorithms continue in the usual way.  When these algorithms have
   culled the falsetickers and AUT; cluster outlyers and at least three
   survivors remain, the first
   valid signature lights PRV.

   Once the active peer system clock has been synchronized to a
   proventic source, it
   includes timestamped signatures with its messages. sourc.

   The first thing
   it does after lighting timestamps is dance time values for truechimer sources form a proventic partial
   ordering relative to the sign exchange so that applicable signature timestamps.  This
   raises the passive peer can survive interesting issue of how to mitigate between the default identity exchange, if
   necessary.  This
   timestamps of different associations.  It might happen, for instance,
   that the timestamp of some Autokey message is pretty weird, since ahead of the passive peer will find system
   clock by some presumably small amount.  For this reason, timestamp
   comparisons between different associations and between associations
   and the active system clock are avoided, except in the NTP intersection and
   clustering algorithms and when determining whether a certificate signed by its own public key. has
   expired.

9.  Autokey Operations

   The passive peer, which NTP protocol has been stalled waiting for the active
   timestamps three principal modes of operation: client/
   server, symmetric and broadast and each has its own Autokey program,
   or dance.  Autokey choreography is designed to be lit, now mates the dance. nonintrusive and to
   require no additional packets other than for regular NTP operations.
   The initial value of NTP and Autokey protocols operate simultaneously and
   independently.  When the
   cookie dance is zero.  If complete, subsequent packets are
   validated by the autokey sequence and thus considered proventic as
   well.  Autokey assumes NTP 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 COOKIE response has not been received by either
   peer, before the next message sent poll opportunity; however the
   protocol is robust against a COOKIE request. missed or duplicate response.

   The recipient rolls 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 random cookie, lights CKY fast algorithm and returns a 32-bit random
   private value (server seed) to regenerate the encrypted cookie. cookie upon arrival of
   a client packet.  The
   recipient decrypts the cookie and lights CKY.  It is not a protocol
   error if both peers happen to send a COOKIE request at calculated as the same time.
   In this case both peers will have two values, one generated by itself
   and first 32 bits of
   the other received autokey computed from the other peer.  In such cases client and server addresses, key ID
   zero and the
   working server seed as cookie.  The cookie is constructed as used for the EXOR of
   actual autokey calculation by both the two values.

   At client and server and is thus
   specific to each client separately.

   In the server dance the client uses the cookie and each key ID on the next packet transmission opportunity, either peer generates a
   new
   key list in turn to retrieve the autokey and lights LST; however, there may already be an AUTO
   request queued for transmission generate the MAC.  The
   server uses the same values to generate the message digest and
   verifies it matches the MAC.  It then generates the MAC for the rules say no more than one
   request in a packet.  When available, either peer sends an AUTO
   response using the same values, but with the client and dims LST. server
   addresses interchanged.  The recipient initializes client generates the autokey values
   and lights LST message digest and AUT.  Subsequent packets received without
   extension fields are validated by the autokey sequence.

   The above description assumes
   verifies it matches the active peer synchronizes MAC.  In order to deflect old replays, the
   passive peer, which itself is synchronized to some other source, such
   as a radio clock or another NTP server.  In this case,
   client verifies the active
   peer is operating at a stratum level key ID matches the last one greater than sent.  In this dance
   the passive
   peer and so sequential structure of the passive peer will key list is not synchronize to it unless exploited, but doing
   it
   loses its own sources this way simplifies and regularizes the active peer itself has another source.
   Various other intricate scenarios are possible.

11.  Error Recovery

   The Autokey protocol state machine includes provisions implementation while
   making it nearly impossible 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 B contains an extended discussion on
   error checking and timestamp validation.

   A persistent NTP association is mobilized by an entry in intruder to guess the
   configuration file, while an ephemeral association is mobilized upon next key ID.

   In the arrival of a broadcast, manycast or symmetric active packet with
   no matching association.  If necessary, a general reset reinitializes
   all association variables broadcast dance clients normally do not send packets to the initial state
   server, except when first mobilized.
   In addition, if starting up.  At that time the association is ephemeral, client runs
   the association is
   demobilized and all resources acquired are returned server dance to verify the system.

   Every NTP association has two variables which maintain server credentials and calibrate the liveness
   state of
   propagation delay.  The dance requires the protocol, association ID of the 8-bit reachability register defined
   particular server association, since there can be more than one
   operating in [8]
   and the watchdog timer, which is new same server.  For this purpose, the server packet
   includes the association ID in NTPv4.  At every poll
   interval response message sent and, when
   sending the reachability register is shifted left, first packet after generating a new key list, it sends
   the low order bit
   is dimmed autokey values as well.  After obtaining and verifying the high order bit is lost.  At the same time the
   watchdog counter is incremented by one.  If an arriving packet passes
   all authentication
   autokey values, no extension fields are necessary and sanity checks, the rightmost bit of the
   reachability register is lit and client
   verifies further server packets using the watchdog counter autokey sequence.

   The symmetric dance is set similar 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 dance and watchdog counter are zero.  If the watchdog counter
   reaches requires only
   a preset threshold before small amount of state between the server becomes reachable, arrival of a
   general reset occurs.  This resets the protocol request and clears any
   acquired resources before trying again.  If
   departure of the association response.  The key list for each direction is
   ephemerable, it
   generated separately by each peer and used independently, but each is demobilized; otherwise,
   generated with the poll interval same cookie.  The cookie is
   doubled.  This reduces conveyed in a way
   similar to the network load for packets server dance, except that are unlikely
   to elicit the cookie is a response.

   At simple
   nonce.  There exists a possible race condition where each state in the protocol the client expects peer sends
   a particular cookie request before receiving the cookie response from the server.  A request is included in the NTP packet
   sent at other
   peer.  In this case, each poll interval until a valid response peer winds up with two values, one it
   generated and one the other peer generated.  The ambiguity is received or a
   general reset occurs, in which case
   resolved simply by computing the protocol restarts from working cookie as the
   beginning.  A general reset also occurs for an association when an
   unrecoverable protocol error occurs.  A general reset occurs for all
   associations when EXOR of the system clock is first synchronized or
   two values.

   Once the clock autokey dance has completed, it is stepped or when normally dormant.  In all
   except the server seed is refreshed.

   There broadcast dance, packets are special cases designed to quickly respond to broken
   associations, such as when a server restarts or refreshes keys.
   Since normally sent without
   extension fields, unless the client cookie packet is invalidated, the server rejects first one sent after
   generating a new key list or unless the next client request and returns a crypto-NAK packet.  A cryoti-NAK packet has a runt MAC with a key ID of zero and no message digest.  The
   problem requested the
   cookie or autokey values.  If for some reason the host is to determine whether it client clock is legitimate or
   stepped, rather than slewed, all cryptographic and time values for
   all associations are purged and the
   result of intruder mischief. dances in all associations
   restarted from scratch.  This insures that stale values never
   propagate beyond a clock step.

10.  Autokey Protocol Messages

   The Autokey protocol data unit is done using the NTPv4 on-wire
   protocol, extension field, one or more of
   which requites the crypto-NAK, as well as all responses, to can be believed only if piggybacked in the result of NTP packet.  An extension field
   contains either a previous packet sent by the host
   and not request with optional data or a replay, as confirmed by the LBK and DUP status bits
   described above.  While this defense response with
   optional data.  To avoid deadlocks, any number of responses can be easily circumvented by a
   middleman, it does deflect other kinds of intruder warfare.

   There are
   included in a number of situations where some event happens that causes
   the remaining autokeys on the key list to become invalid.  When packet, but only one
   of these situations happens, the key list and associated autokeys in
   the key cache are purged. request.  A new key list, signature and timestamp
   are response is generated when
   for every request, even if the next NTP message is sent, assuming there is
   one.  Following requestor is not synchronized to a list of these situations:

   1.  When
   proventic source, but most contain meaningful data only if the cookie value changes for any reason.

   2.  When a client switches from client mode to broadcast client mode.
       There
   responder is no further need for synchronized to a proventic source.  Some requests and
   most responses carry timestamped signatures.  The signature covers
   the key list, since entire extension field, including the client will
       not transmit again.

   3.  When timestamp and filestamp,
   where applicable.  Only if the poll interval packet passes all extension field
   tests are cycles spent to verify the signature.

   There are currently eight Autokey requests and eight corresponding
   responses.  The NTP packet format is changed.  In this case described in [1] and the calculated
       expiration times
   extension field format used for the keys become invalid.

   4.  If a problem these messages is detected when an entry illustrated in
   Figure 7.

    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |          Field Type           |            Length             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                         Association ID                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           Timestamp                           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           Filestamp                           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                          Value Length                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   \                                                               /
   /                             Value                             \
   \                                                               /
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        Signature Length                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   \                                                               /
   /                           Signature                           \
   \                                                               /
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   \                                                               /
   /                      Padding (if needed)                      \
   \                                                               /
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                  Figure 7: NTPv4 Extension Field Format

   Each extension field is fetched from zero-padded to a 4 octet boundary.  The
   Length field covers the key
       list.  This could happen if entire extension field, including the key was marked non-trusted or
       timed out, either of which implies Length
   and Padding fields.  While the minimum field length is 8 octets, a
   maximum field length remains to be established.  The reference
   implementation discards any packet with a software bug.

12.  Security Considerations

   This section discusses the most obvious security vulnerabilities in field length more than 1024
   octets.

   If an extension field is present, the various Autokey dances.  First, some observations on parser examines the
   particular engineering parameters of Length
   field.  If the Autokey protocol are in
   order.  The number of bits in some cryptographic values are
   considerably smaller length is less than would ordinarily be expected for strong
   cryptography.  One 4 or not a multiple of 4, a format
   error has occurred and the reasons for this is the need for
   compatibility with previous NTP versions; another packet is discarded; otherwise, the need for
   small and constant latencies and minimal processing requirements.
   Therefore, what the scheme gives up on parser
   increments the strength of these values
   must be regained pointer by agility in the rate of change of length value.  The parser now uses the
   cryptographic basis values.  Thus, autokeys are used only once and
   seed values are regenerated frequently.  However, in most cases even
   a successful cryptanalysis of these values compromises only a
   particular association and does not represent a danger
   same rules as above to determine whether a MAC is present and/or
   another extension field.

   The 8-bit Code field specifies the general
   population.

   Throughout request or response operation,
   while the following discussion 4-bit Version Number (VN) field is 2 for the cryptographic algorithms and
   private values themselves current
   protocol version.  There are assumed secure; that is, a brute force
   cryptanalytic attack will not reveal four flag bits: bit 0 is the host private key, sign
   private key, cookie value, identity parameters, server seed or
   autokey seed.  In addition, an intruder will not be able to predict
   random generator values or predict Response
   Flag (R) and bit 1 is the next autokey.  On Error Flag (E); the other
   hand, the intruder can remember the totality of all past values for
   all packets ever sent.  Ordinarily, the timestamp/filestamp
   provisions two bits are
   presently unused and should be set to 0.  The remaining fields will make such possesions unusable.

12.1.  Protocol Vulnerability

   While
   be described later.

   In the most common protocol has not been subjected to operations, a formal analysis, client sends a few
   preliminary assertions can be made.  The protocol cannot loop forever request to a
   server with an operation code specified in any state, since the watchdog counter Code field and general reset insure
   that both
   the association variables will eventually be purged R bit and E bit dim.  The Association ID field is set to the
   protocol restarted
   value previously received from the beginning.  However, if something is
   seriously wrong, the timeout/restart cycle could continue
   indefinitely until whatever is wrong is fixed.  This is not server or 0 otherwise.  The server
   returns a
   clogging hazard, as response with the timeout period is very long compared to
   expected network delays.

   The LBK and DUP bits described same operation code in the main body Code field and Appendix B are
   effective whether or not cryptographic means are in use.
   lights the R bit.  The DUP bit
   deflects duplicate packets in any mode, while server can also light the LBK E bit deflects
   bogus packets in all except broadcast mode.  All packets must have case of
   error.  The Association ID field is set to the correct MAC, association ID of the
   server as verified with correct key a handle for subsequent exchanges.  If for some reason the
   association ID value in a request does not match the association ID
   of any mobilized association, the server returns the request with
   both the R and cookie. E bits lit.  Note that it is not necessarily a
   protocol error to send an unsolicited response with no matching
   request.

   In some cases not all
   modes the next key ID cannot fields may be predicted by present.  For requests, until a wiretapper, so are of
   no use for cryptanalysis.

   As long as the
   client has validated the server certificate trail, a
   wiretapper cannot produce a convincing signature and cannot produce
   cryptographic values acceptable synchronized to the client.  As long as the
   identity values a proventic source, signatures are not compromised, a middleman cannot masquerade as
   a legitimate group member and produce convincing certificates or
   signatures.
   valid.  In server and symmetric modes after such cases the preliminary
   exchanges have concluded, extension Timestamp and Signature Length fields are no longer used, a
   client validates the packet using 0
   and the autokey sequence.  A wiretapper
   cannot predict Signature field is empty.  Responses are generated only when
   the next Key IDs, so cannot produce responder has synchronized to a valid MAC.  A
   middleman cannot successfully modify proventic source; otherwise, an
   error response message is sent.  Some request and replay a message, since he
   does not know error response
   messages carry no value or signature fields, so in these messages
   only the cookie first two words are present.

   The Timestamp and without Filestamp words carry the cookie cannot produce a
   valid MAC.

   In broadcast mode a wiretapper cannot produce a key list with signed
   autokey values that a client will accept.  The most it can do is
   replay seconds field of an old packet causing clients to repeat NTP
   timestamp.  The Timestamp field establishes the autokey hash
   operations until exceeding signature epoch of
   the maximum key number.  However, a
   middleman could intercept an otherwise valid broadcast packet and
   produce a bogus packet with acceptable MAC, since data field in this case it
   knows the key ID before message, while the clients do.  Of course, filestamp establishes the middleman key
   list would eventually be used up and clients would discover
   generation epoch of the ruse
   when verifying file that ultimately produced the data that
   is signed.  A signature of and timestamp are valid only when the autokey values.  There does not
   seem signing
   host is synchronized to a proventic source; otherwise, the timestamp
   is zero.  A cryptographic data file can only be generated if a suitable defense against this attack.

   During
   signature is possible; otherwise, the exchanges filestamp is zero, except in
   the ASSOC response message, where extension fields it contains the server status word.

   Unless specified otherwise in the descriptions to follow, the data
   referred to are stored in use, the cookie is
   a public value rather than a shared secret and Value field.

10.1.  No-Operation

   A No-operation request (Field Type = 0) does nothing except return an intruder
   empty response which can easily
   construct a packet with a valid MAC, but not be used as a valid signature.  In crypto-ping.

10.2.  Association Message (ASSOC)

   An Association Message (Field Type = 1) is used in the certificate parameter
   exchange to obtain the host name and identity exchanges an intruder can generate fake status word.  The request messages which may evade
   contains the client status word in the Filestamp field and the host
   name in the Value field.  The response contains the server detection; however, status
   word in the Filestamp field and the host name in the Value field.  By
   default the host name is 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.

   When multiple identity schemes are supported, the LBK
   and DUP status words
   determine which one is used.  The request message contains bits minimize
   corresponding to the schemes the client exposure to supports, while the resulting rogue
   responses.  A wiretapper might be able to intercept a request,
   manufacture a fake response and loft it swiftly
   message contains bits corresponding to the client before schemes the real server response.  A middleman could
   supports.  The server and client do this without even
   being swift.  However, once an AND operation on the status
   words to select compatible identity exchange has completed and schemes.  If multiple schemes
   result, the PRV bit lit, these attacks bits are readily deflected.

   A client instantiates cryptographic variables only if the server is
   synchronized ranked from right to a proventic source. left.

10.3.  Certificate Message (CERT)

   A server does not sign values or
   generate cryptographic data files unless synchronized to a proventic
   source.  This raises an interesting issue: how does a client generate
   proventic cryptographic files before it has ever been synchronized Certificate Message (Field Type = 2) is used in the certificate
   exchange to obtain a proventic source?  [Who shaves certificate by name.  The request contains the barber if
   subject name; the barber shaves
   everybody response contains the certificate encoded in town who X.509
   format with ASN.1 syntax as described in Appendix C.

   If the subject name in the response does not shave himself?]  In principle, this
   paradox is resolved by assuming match the primary (stratum 1) servers are
   proventicated by external phenomenological means.

   There is issuer name,
   the exchange continues with the issuer name replacing the subject
   name in the request.  The exchange continues until a significant vulnerability trusted, self-
   signed certificate is found.

10.4.  Cookie Message (COOKIE)

   The Cookie Message (Field Type = 3) is used in server and symmetric
   modes to obtain the underlying NTP on-wire
   protocol.  Until confirming server cookie.  The request contains the first exchange when a host first
   comes up, an intruder can replay an old message, which cause
   public key encoded with ASN.1 syntax as described in Appendix C.  The
   response contains the LBK
   and DUP bits to be reset.  If cookie encrypted by the intruder does this repeatedly, public key in the
   host may never synchronize.  This vulnerability
   request.

10.5.  Autokey Message (AUTO)

   The Autokey Message (Field Type = 4) is used to obtain the same as with
   TCP.

12.2.  Clogging Vulnerability

   There are autokey
   values.  The request contains no value.  The response contains two clogging vulnerabilities exposed
   32-bit words in network byte order.  The first word is the protocol
   design: an encryption attack where final key
   ID, while the intruder hopes to clog second is the
   victim server with needless cookie or signature encryptions or
   identity calculations, and a decryption attack where index of the intruder
   attempts final key ID.

10.6.  Leapseconds Values Message (LEAP)

   The Leapseconds Values Message (Field Type = 5) is used to clog obtain the victim client with needless cookie or
   verification decryptions.  Autokey uses public key cryptography
   leapseconds values as parsed from the leapseconds table from NIST.
   The request and response messages have the algorithms same format, except that perform these functions consume significant
   processor resources.

   In order to reduce exposure
   the R bit is set to decryption attacks 0 in the LBK and DUP
   bits deflect bogus request and replayed packets before invoking any
   cryptographic operations.  In order to reduce exposure set to encryption
   attacks, signatures are computed only when 1 in the data have changed.
   For instance, response.
   Both the request and response contains three 32-bit integers, the NTP
   seconds of the latest leap event followed by the autokey values are signed only NTP seconds when the key list is
   regenerated, which happens about once an hour, while
   latest NIST table expires and then the public
   values are signed only when one of them changes or TAI offset following the server seed is
   refreshed, which happens about once per day.

   In some Autokey dances leap
   event.

10.7.  Sign Message (SIGN)

   The Sign Message (Field Type = 6) requests the protocol precludes server state variables
   on behalf of an individual client, so to sign and
   return a certificate presented in the request.  The request message must be
   processed and contains
   the client certificate encoded in X.509 format with ASN.1 syntax as
   described in Appendix C.  The response message sent without delay. contains the client
   certificate signed by the server private key.

10.8.  Identity Messages (IFF, GQ, MV)

   The identity,
   cookie and sign exchanges are particularly vulnerable to a clogging
   attack, since these exchanges can involve expensive cryptographic
   algorithms as well as digital signatures.  A determined intruder
   could replay identity, cookie Identity Messages (Field Type = 7 (IFF), 8 (GQ), or sign requests at high rate, which
   may very well be 9 (MV))
   contains the client challenge, usually a useful munition for an encryption attack.
   Ordinarily, these requests are seldom used, except when 160- or 512-bit nonce.  The
   response contains the protocol result of the mathematical operation defined in
   Appendix B.  The Response is restarted or encoded in ASN.1 syntax as described in
   Appendix C.

11.  Autokey State Machine

   This section describes the server seed or public values are refreshed.

   Once synchronized to a proventic source, a legitimate extension field
   with timestamp formal model of the same Autokey state machine,
   its state variables and the state transition functions.

11.1.  Status Word

   Each server and client operating also as or earlier than the most recent received
   of that type is immediately discarded.  This foils a middleman cut-
   and-paste attack using server implements a host
   status word, while each client implements an earlier AUTO response, association status word
   for example.  A
   legitimate extension field with timestamp each server.  Both words have the format and content shown in
   Figure 8.  The low order 16 bits of the future is unlikely, status word define the state
   of the Autokey protocol, while the high order 16 bits specify the
   message digest/signature encryption scheme as that would require predicting encoded in the autokey sequence. 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 either
   case the extension field is discarded before expensive signature
   computations.  This defense is most useful in symmetric mode, but a
   useful redundancy in other modes.
   host portion bits 24-27 specify the available identity schemes, while
   bits 28-31 specify the server capabilities.  There are two additional
   bits implemented separately.

                        1                   2                   3
    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    Digest / Signature NID     |    Client     | Ident |  Host |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                           Figure 8: Status Word

   The client host status word is vulnerable to a certificate clogging attack until
   declared proventic, after which CERT responses are discarded.  Before
   that, a determined intruder could flood the client with bogus
   certificate responses and force spurious signature verifications,
   which of course would fail. included in the ASSOC request and response
   messages.  The intruder could flood client copies this word to the server with
   bogus certificate requests association status word
   and cause similar mischief. then lights additional status bits as the dance proceeds.  Once declared
   proventic, further certificate responses are discard, so
   enabled, these
   attacks would fail.  The intruder could flood the server with
   replayed sign requests bits never come dark unless a general reset occurs and cause
   the server to verify protocol is restarted from the request and
   sign beginning.  The status bits are
   defined as follows:

   o  ENB (31) - Lit if the response, although server implements the client would drop Autokey protocol

   o  LPF (30) - Lit if the response due
   invalid timestamp.

   An interesting adventure is when an intruder replays a recent packet
   with an intentional bit error.  A stateless server will return a
   crypto-NAK message has loaded leapseconds values

   o  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 client will notice schemes available in the reference implementation
      and discard, since described in Appendix B include the LBK bit is lit.  However, a legitimate crypto-NAK 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 sent if exclusive of any other scheme.  Otherwise, the IFF,
   GQ and MV bits can be enabled in any combination.

   The association status bits are defined as follows:

   o  VAL (0x0100) - Lit when the server has just refreshed certificate and public key are
      validated.

   o  IFF (0x0200) - Lit when the server seed.  In this case identity credentials are
      confirmed.

   o  PRV (0x0400) - Lit when the LBK bit server signature is dim and verified using the client performs a general reset
      public key and restarts identity credentials.  Also called the
   protocol as expected.  Another adventure proventic
      bit elsewhere in this memo.  When enabled, signed values in
      subsequent messages are presumed proventic.

   o  CKY (0x0800) - Lit when the cookie is to replay broadcast mode
   packets at high rate.  These will received and validated.
      When enabled, key lists with nonzero cookies can be rejected by generated.

   o  AUT (0x1000) - Lit when the autokey values are received and
      validated.  When enabled, clients by can validate packets without
      extension fields according to the
   timestamp check and before consuming signature cycles.

   In broadcast and symmetric modes autokey sequence.

   o  SGN (0x2000) - Lit when the client must include host certificate is signed by the
   association ID in
      server.

   o  LPT (0x4000) - Lit when the AUTO request.  Since association ID leapseconds values for
   different invocations of the NTP daemon are randomized over received and
      validated.

   There are four additional status bits LST and SYN not included in the 16-
   bit space, it
   status word.  LST is unlikely that a bogus request would match client propertie, while SYN is a valid
   association with different IP addresses, for example, and cause
   confusion.

13.  IANA Considerations

   Any IANA registries needed?

14.  Acknowledgements

   ...

15.  References

15.1.  Normative References

   [1]   Burbank, J., "Network Time Protocol Version 4 Protocol And
         Algorithms Specification", draft-ietf-ntp-ntpv4-proto-07 (work
         in progress), July 2007.

15.2.  Informative References

   [2]   Kaufman, C., "Internet Key Exchange (IKEv2) Protocol",
         RFC 4306, December 2005.

   [3]   Orman, H., "The OAKLEY Key Determination Protocol", RFC 2412,
         November 1998.

   [4]   Karn, P. host
   property.  LST is lit when the key list is regenerated and W. Simpson, "Photuris: Session-Key Management
         Protocol", RFC 2522, March 1999.

   [5]   Bradner, S., "Key words for use in RFCs to Indicate Requirement
         Levels", BCP 14, RFC 2119, March 1997.

   [6]   Kent, S., "IP Encapsulating Security Payload (ESP)", RFC 4303,
         December 2005.

   [7]   Kent, S., "IP Authentication Header", RFC 4302, December 2005.

   [8]   Mills, D., "Network Time Protocol (Version 3) Specification,
         Implementation", RFC 1305, March 1992.

   [9]   Prafullchandra, H. signed and J. Schaad, "Diffie-Hellman Proof-of-
         Possession Algorithms", RFC 2875, July 2000.

   [10]  Adams, C., Farrell, S., Kause, T.,
   DIM when 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 T. Mononen, "Internet
         X.509 Public never dim after that.

11.2.  Host State Variables

   Following is a list of state variables used by the server protocol.

   o  Host Name - The name of the host, by default the string returned
      by the Unix gethostname() library function.

   o  Host Status Word - This word is initialized when the host first
      starts up.  The format is described above.

   o  Host Key Infrastructure Certificate Management Protocol
         (CMP)", RFC 4210, September 2005.

   [11]  Housley, R., Polk, W., Ford, W., and D. Solo, "Internet X.509
         Public - The RSA public/private key pair used to encrypt/decrypt
      cookies.  This is also the default sign key.

   o  Sign Key Infrastructure Certificate and Certificate
         Revocation List (CRL) Profile", RFC 3280, April 2002.

   [12]  Schnorr, C., "Efficient signature generation for smart cards",
         1991.

   [13]  Stinson, D., "Cryptography - Theory and Practice", 1995.

   [14]  Guillou, L. and J. Quisquatar, "A "paradoxical" identity-based The RSA or DSA public/private key pair used to encrypt/
      decrypt signatures when the host key is not used for this purpose.

   o  Sign Digest - The message digest algorithm used to compute the
      signature before encryption.

   o  IFF Parameters - The parameters used in the optional IFF identity
      scheme resulting described in Appendix B.

   o  GQ Parameters - The parameters used in the optional GQ identity
      scheme described in Appendix B.

   o  MV Parameters - The parameters used in the optional MV identity
      scheme described in Appendix B.

   o  Server Seed - The private value hashed with the IP addresses to
      construct the cookie.

   o  Certificate Information Structure (CIS) - Certificates are used to
      construct certificate information structures (CIS) which are
      stored on the certificate cache.  The structure includes certain
      information fields from zero-knowledge", 1990.

   [15]  Mu, Y. and V. Varadharajan, "Robust and secure broadcasting",
         2001.

   [16]  Bassham, L., Polk, W., and R. Housley, "Algorithms an X.509v3 certificate, together with the
      certificate itself encoded in ASN.1 syntax.  Each structure
      carries the public value timestamp and
         Identifiers for the Internet X.509 Public Key Infrastructure
         Certificate filestamp of the
      certificate file where it was generated.  Elsewhere in this memo
      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 Certificate Revocation List (CRL) Profile",
         RFC 3279, April 2002.

Appendix A.  Cryptographic contains
         "trustRoot" in the Extended Key Usage field, this bit is lit
         when the CIS is constructed

      *  SIGN (0x02) - The certificate signature has been verified.  If
         the certificate is self-signed and Certificate Management

   This appendix describes how cryptographic keys and certificates are
   generated and managed in verified using the NTPv4 reference implementation.  These
   means are not intended to become part of any standard that may be
   evolved from contained
         public key, this report, but to serve as an example of how these
   functions bit is lit when the CIS is constructed.

      *  VALD (0x04) - The certificate is valid and can be implemented and managed in used to
         verify signatures.  This bit is lit when a typical operational
   environment. trusted certificate
         has been found on a valid certificate trail.

      *  PRIV (0x08) - The ntp-keygen utility program certificate is private and not to be
         revealed.  If the certificate is self-signed and contains
         "Private" in the NTPv4 software library
   generates public/private key files, Extended Key Usage field, this bit is lit when
         the CIS is constructed.

      *  ERRR (0x80) - The certificate files is defective and identity
   key/parameter files.  By default not to be used
         in any way.

   o  Certificate List - CIS structures are stored on the modulus certificate
      list in order of all encryption and
   identity keys arrival, with the most recently received CIS
      placed first on the list.  The list is 512 bits.  All random cryptographic data initialized with the CIS
      for the host certificate, which is read from the certificate file.
      Additional CIS entries are based pushed on a pseudo-random number generator seeded in such a way that random
   values the list as certificates are exceedingly unlikely to repeat.  The files
      obtained from the servers during the certificate exchange.  CIS
      entries are in ASN.1
   format, encrypted is necessary, then PEM encoded in printable ASCII
   format suitable discarded if overtaken by newer ones or expire due to
      old age.

   o  Host Certificate - The self-signed X.509v3 certificate for mailing as MIME objects.

   Every file has a filestamp, which is a string of decimal digits
   representing the NTP seconds when the file was created.
      host.  The file
   name is formed from the concatenation subject and issuer fields consist of the host name, filestamp and
   constant strings, so files can be copied from one environment to
   another
      while preserving the original filestamp.  The file header
   includes message digest/signature encryption scheme consists of
      the file name and date sign key and generation time message digest defined above.  Optional
      information used in the identity schemes is carried in printable
   ASCII. X.509v3
      extension fields compatible with [10].

   o  Public Key Values - The utility assumes public encryption key for the COOKIE
      request, which consists of the public value of the host is synchronized to a proventic
   source at key.  It
      carries the time public values timestamp and the filestamp of generation, so that filestamps are proventic
   data.  This raises an interesting circularity issue that will not be
   further explored here. the host
      key file.

   o  Leapseconds Values.  The generated files are typically stored in NFS mounted file systems,
   with files containing private keys obscured to all but root.
   Symbolic links are installed leapseconds values parsed from default file names assumed by the
   NTP daemon to NIST
      leapseconds file.  It carries the selected files.  Since public values timestamp and the files
      filestamp of successive
   generations and different hosts have unique names, there the leapseconds values.

11.3.  Client State Variables (all modes)

   Following is no
   possibility a list of name collisions.

   Public/private host and sign keys and certificates must be generated state variables used by the client association
   protocol in all modes.

   o  Association ID - The association ID used in responses.  It is
      assigned when the association is mobilized

   o  Server Association ID - The server association ID used in
      requests.  It is copied from the first nonzero association ID
      field in a response

   o  Server Subject Name - The server host to which they belong. name determined in the
      parameter exchange

   o  Server Issuer Name - The host key must be RSA, since it name signing the certificate.  It is
      extracted from the current server certificate upon arrival and
      used to encrypt request the cookie, as well as encrypt signatures by
   default. next item on the certificate trail

   o  Association Status Word - The optional sign host status word of the server
      determined in the parameter exchange

   o  Server Public Key - The public key can be RSA or DSA, since it is used
   only to encrypt decrypt signatures.  In principle, certificates could be
   generated directly by OpenSSL utility programs, as long as  It
      is extracted from the
   symbolic links are consistent.

   Identity keys and parameters must be generated first certificate received, which by design
      is the ntp-keygen
   utility, since they have proprietary formats.  Since these are
   private to the group, they are generated by one server host acting as a
   trusted authority and then distributed to all other members of certificate

   o  Server Message Digest - The digest/signature scheme determined in
      the
   group by secure means.

   Certificates are usually, but not necessarily, generated parameter exchange

   o  Identification Challenge - A 512-bit nonce used in the
      identification exchange
   o  Group Key - A set of values used by the host
   to which they belong.  The ntp-keygen utility generates self-signed
   X.509v3 host certificate files with optional extension fields.
   Certificate requests are not used, since identification exchange.
      It identifies the certificate itself is
   used as a request to be signed.  OpenSSL X.509v3 certificates are
   generated as an OpenSSL structure, which is then PEM encoded cryptographic compartment shared by the server
      and client

   o  Receive Cookie Values - The cookie returned in ASN.1
   syntax a COOKIE response,
      together with its timestamp and written to the host certificate file. filestamp

   o  Receive Autokey Values - The string autokey values returned
   by the Unix gethostname() routine in an AUTO
      response, together with its timestamp and filestamp

11.4.  Server State Variables (broadcast and symmetric modes)

   Following is a list of server state variables used by default for both the
   subject in broadcast and issuer fields.
   symmetric modes.

   o  Send Cookie Values - The serial number cookie encryption values, signature and begin time fields
   are derived from
      timestamps

   o  Send Autokey Values - The autokey values, signature and timestamps

   o  Key List - A sequence of key IDs starting with the filestamp; autokey seed
      and each pointing to the end time is one year hence.  The
   host certificate next.  It is computed, timestamped and
      signed by at the next poll opportunity when the sign key or host key if a sign key
   is not present.

   An important design goal is list becomes
      empty

   o  Current Key Number - The index of the entry on the Key List to make cryptographic data refreshment as
   simple and intuitive as possible, so it can be driven by scripts on a
   periodic basis.  When
      used at the ntp-keygen utility next poll opportunity

11.5.  Protocol State Transitions

   The protocol state machine is run for the first
   time, it creates very simple but robust.  The state is
   determined by default a RSA host key file and RSA-MD5 host
   certificate file and necessary symbolic links.  After that, it
   creates a new certificate file 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 symbolic link using are lit upon the existing
   host key.  The program run with given options creates identity key/
   parameter files for one or more IFF, GQ or MV identity schemes. arrival of a specific response
   message, as detailed above.

11.5.1.  Server Dance

   The
   key files must then be securely copied to all other group members and
   symbolic links installed from server dance begins when the default names client sends an ASSOC request to the installed
   files.  In the GQ scheme
   server.  It ends when the next first signature is verified and each subsequent time PRV is lit.
   Subsequent packets received without extension fields are validated by
   the ntp-
   keygen utility runs, it automatically creates or autokey sequence.  An optional LEAP exchange updates the private/
   public
   leapseconds values.  Note the order of the identity key files exchanges and certificate file using
   that only the existing
   identity parameters.

Appendix B.  Autokey Error Checking

   Exhaustive examination of possible vulnerabilities at first one will be used if multiple schemes are
   available.  Note also that the various
   processing steps of 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)
                           /* signe exchange */
                           SIGN_request(Host_Certificate);
                   else if (SYN && LPF & !LPT)
                           /* leapseconds exchange */
                           LEAP_request;

           }

   When the NTPv3 protocol as specified in [8] have
   resulted in a revised list of packet sanity tests.  There are 12
   tests PC identity scheme is in use, the NTPv4 reference implementation, called TEST1 through
   TEST12, which are performed in a specific order designed ASSOC response sets VAL,
   IFF, and SIG to gain
   maximum diagnostic information while protecting against an accidental
   or malicious clogging attacks.  These tests are described in detail
   in 1; the NTP software documentation.  Those relevant COOKIE response sets CKY and AUT to the Autokey
   protocol are described in this appendix.

   The sanity tests are classified in four tiers.  The first tier
   deflects access control 1; and message digest violations.  The second,
   represented by the autokey sequence, deflects spoofed or replayed
   packets.  The third, represented by timestamped digital signatures,
   binds cryptographic values
   first valid signature sets PRV to verifiable credentials. 1.

11.5.2.  Broadcast Dance

   The fourth
   deflects packets with invalid NTP header fields or out of bounds time
   values.  However, only difference between the tests in this last group do not directly affect
   cryptographic protocol vulnerability, so are beyond broadcast and server dances is the scope
   inclusion of
   discussion here.

B.1.  Packet Processing Rules

   Every arriving NTP packet is checked enthusiastically for format,
   content and protocol errors.  Some packet header fields are checked
   by an autokey values exchange following the main NTP code path both before and after cookie
   exchange.  The broadcast dance begins when the Autokey protocol
   engine cranks.  These include client receives the NTP version number, overall packet
   length and extension field lengths.
   first broadcast packet, which includes an ASSOC response with
   association ID.  The total length of all
   extension fields may be no longer than 1024 octets broadcast client uses the association ID to
   initiate a server dance in order to calibrate the reference
   implementation.  Packets failing any of these checks propagation delay.

   The dance ends when the first signature is verified and PRV is lit.
   Subsequent packets received without extension fields are discarded
   immediately.  Packets denied validated by
   the access control mechanism will be
   discarded later, but processing continues temporarily in order to
   gather further information useful for error recovery and reporting.

   Next, autokey sequence.  An optional LEAP exchange updates the cookie and session key are determined and
   leapseconds values.  When the MAC computed
   as described above.  If server generates a new key list, the MAC fails to match
   server replaces the value included ASSOC response with an AUTO response in the packet, 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 action depends on PC identity scheme is in use, the mode ASSOC response lights VAL,
   IFF, and SIG; the type of packet.
   Packets failing the MAC check will be discarded later, but processing
   continues temporarily in order to gather further information useful
   for error recovery COOKIE response lights CKY and reporting.

   The NTP transmit AUT; and receive timestamps are in effect nonces, since the first
   valid signature lights PRV.

11.5.3.  Symmetric Dance

   The symmetric dance is intricately choreographed.  It begins when the
   active peer sends an intruder cannot effectively guess either value in advance.  To
   minimize ASSOC request to the possibility that passive peer.  The passive
   peer mobilizes an intruder can guess association and both peers step the nonces, same dance from
   the
   low order unused bits in all timestamps are obscured with random
   values.  If beginning.  Until the transmit timestamp matches 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 transmit timestamp in the last packet received, ASSOC response to
   light up.  Until then, the packet is a duplicate, so active peer dances the DUP bit
   is lit.  If server steps, but
   skips the packet mode 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 not broadcast in use, the ASSOC response lights VAL,
   IFF, and SIG; the last transmit
   timestamp does not match COOKIE response lights CKY and AUT; and the originate timestamp in 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 packet,
   either it was delivered out of order or an intruder has injected a
   rogue packet, sign exchange so that
   the LBK bit passive peer can survive the default identity exchange, if
   necessary.  This is lit.  Packets with either pretty weird, since the DUP or
   LBK bit passive peer will be discarded later, but processing continues temporarily
   in order to gather further information useful for error recovery and
   reporting.

   Further indicators of find
   the server and client state are apparent from active certificate signed by its own public key.

   The passive peer, which has been stalled waiting for the transmit and receive active
   timestamps to light up, now mates the dance.  The initial value of both
   the packet and cookie is zero.  If a COOKIE response has not been received by
   either peer, the
   association. next message sent is a COOKIE request.  The quite intricate rules take into account these
   recipient rolls a random cookie, lights CKY and returns the above error indicators They are designed to discriminate between
   legitimate cases where encrypted
   cookie.  The recipient decrypts the server or client are in inconsistent
   states and recoverable, cookie and when an intruder lights CKY.  It is trying not
   a protocol error if both peers happen to destabilize send a COOKIE request at the protocol or force consumption of needless resources.  The exact
   behavior is beyond
   same time.  In this case both peers will have two values, one
   generated by itself and the scope of discussion, but is clearly described
   in other received from the source code documentation.

   Next, other peer.  In
   such cases the Autokey protocol engine working cookie is cranked and the dances evolve constructed as
   described above.  Some requests and all responses have value fields
   which carry timestamps and filestamps.  When the server or client is
   synchronized to EXOR of the two
   values.

   At the next packet transmission opportunity, either peer generates a proventic source, most requests
   new key list and responses with
   value fields carry signatures with valid timestamps.  When not
   synchronized sets LST to a proventic source, value fields carry 1; however, there may already be an invalid
   (zero) timestamp AUTO
   request queued for transmission and the signature field rules say no more than one
   request in a packet.  When available, either peer sends an AUTO
   response and signature length word
   are omitted. dims LST.  The extension field parser checks that recipient initializes the Autokey version number,
   operation code autokey values
   and field length lights LST and AUT.  Subsequent packets received without
   extension fields are valid.  If the error bit is lit
   in a request, validated by the request is discarded without response; if an error
   is discovered in processing autokey sequence.

   The above description assumes the request, or if active peer synchronizes to the responder
   passive peer, which itself is not synchronized to a proventic some other source, the response contains only the
   first two words of the request with the response and error bits lit.
   For messages with signatures, the parser requires that timestamps and
   filestamps are valid and not such
   as a replay, that radio clock or another NTP server.  In this case, the signature length
   matches active
   peer is operating at a stratum level one greater than the certificate public key length passive
   peer and only then verifies the
   signature.  Errors are reported via so the security logging facility.

   All certificates must have correct ASN.1 encoding, supported digest/
   signature scheme passive peer will not synchronize to it unless it
   loses its own sources and valid subject, issuer, public key and, for self-
   signed certificates, valid signature.  While the begin and end times active peer itself has another source.

11.6.  Error Recovery

   The Autokey protocol state machine includes provisions for various
   kinds of error conditions that can be checked relative arise due to the filestamp missing files,
   corrupted data, protocol violations and each other, whether the
   certificate is valid relative packet loss or misorder, not
   to mention hostile intrusion.  This section describes how the actual time cannot be determined
   until the client is synchronized
   protocol responds to a proventic source reachability and the
   certificate timeout events which can occur
   due to such errors.

   A persistent NTP association is signed and verified mobilized by an entry in the server.

   When the protocol starts the only response accepted
   configuration file, while an ephemeral association is ASSOC mobilized upon
   the arrival of a broadcast, manycast or symmetric active packet with
   valid timestamp, after which
   no matching association.  Subsequently, a general reset reinitializes
   all association variables to the server status word must be nonzero.
   ASSOC responses are discarded initial state when first mobilized.
   In addition, if this word is nonzero.  The only
   responses accepted after that and until the PRV bit association is lit are CERT,
   IFF and GQ.  Once identity ephemeral, the association is confirmed
   demobilized and IFF is lit, these
   responses are no longer accepted, but all other responses resources acquired are
   accepted only if in response returned to a previously sent request and only in
   the order prescribed in the protocol dances.  Additional checks are
   implemented for each request type and dance step.

B.2.  Timestamps, Filestamps and Partial Ordering

   When the host starts, it reads the host key and certificate files, system.

   Every NTP association has two variables which are required for continued operation.  It also reads maintain the sign
   key and leapseconds file, when available.  When reading these files liveness
   state of the host checks protocol, the file formats 8-bit reachability register defined in [7]
   and filestamps for validity; for
   instance, all filestamps must be later than the time the UTC
   timescale was established watchdog timer, which is new in 1972 NTPv4.  At every poll
   interval the reachability register is shifted left, the low order bit
   is dimmed and the certificate filestamp must
   not be earlier than its associated sign key filestamp.  In general,
   at high order bit is lost.  At the same time the files are read,
   watchdog counter is incremented by one.  If an arriving packet passes
   all authentication and sanity checks, the host rightmost bit of the
   reachability register is not synchronized, so it
   cannot determine whether lit and the filestamps are bogus other than these
   simple checks.

   In watchdog counter is set to zero.
   If any bit in the following reachability register is lit, the relation A --> B server is Lamport's "happens before"
   relation, which
   reachable, otherwise it is true if event A happens before event B. unreachable.

   When
   timestamps are compared to timestamps, the relation first poll is false if A
   <--> B; that is, false if sent from an association, the events are simultaneous.  For
   timestamps compared to filestamps reachability
   register and filestamps compared to
   filestamps, watchdog counter are zero.  If the relation is true if A <--> B. Note that watchdog counter
   reaches 16 before the current
   time plays no part in these assertions except in (6) below; however, server becomes reachable, a general reset
   occurs.  This resets the NTP protocol itself insures a correct partial ordering for all
   current time values.

   The following assertions apply to all relevant responses:

   1.  The client saves and clears any acquired resources
   before trying again.  If the most recent timestamp T0 server was once reachable and filestamp F0
       for then
   becomes unreachable, a general reset occurs.  In addition, if the respective signature type.  For every received message
       carrying timestamp T1
   watchdog counter reaches 16 and filestamp F1, the message association is discarded
       unless T0 --> T1 and F0 --> F1.  The requirement that T0 --> T1 persistent, the
   poll interval is doubled.  This reduces the primary defense against replays of old messages.

   2.  For timestamp T and filestamp F, F --> T; network load for packets
   that is, are unlikely to elicit a response.

   At each state in the filestamp
       must happen before protocol the timestamp.  If not, this could be due to client expects a
       file generation error 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 significant error
   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
       time.

   3.  For sign key filestamp S, certificate filestamp C, 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
       timestamp D is invalidated, the server rejects the next
   client request and autokey timestamp A, S --> C --> D --> A; that
       is, returns a crypto-NAK packet.  Since the crypto-NAK
   has no MAC, the autokey must be generated after problem for the cookie, client is to determine whether it is
   legitimate or the cookie
       after result of intruder mischief.  In order to reduce
   the certificate and vulnerability in such cases, the certificate after crypto-NAK, as well as all
   responses, is believed only if the sign key.

   4.  For sign key filestamp S and certificate filestamp C specifying
       begin time B and end time E, S --> C--> B --> E; that is, result of a previous packet sent
   by the
       valid period must client and not a replay, as confirmed by the NTP on-wire
   protocol.  While this defense can be retroactive.

   5.  A certificate for subject S signed easily circumvented by issuer I and with filestamp
       C1 obsoletes, but a
   middleman, it does not necessarily invalidate, another
       certificate with deflect other kinds of intruder warfare.

   There are a number of situations where some event happens that causes
   the same subject remaining autokeys on the key list to become invalid.  When one
   of these situations happens, the key list and issuer but with filestamp
       C0, where C0 --> C1.

   6. associated autokeys in
   the key cache are purged.  A certificate with begin time B new key list, signature and end time E timestamp
   are generated when the next NTP message is invalid and can
       not be used to verify signatures if t --> B or E --> t, where t sent, assuming there is
   one.  Following is a list of these situations:

   1.  When the current proventic time.  Note that 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 public key
       previously extracted from list, since the certificate continues to be valid 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 indefinite time. entry is fetched from the key
       list.  This raises could happen if the interesting possibility
       where a truechimer server with expired certificate key was marked non-trusted or
       timed out, either of which implies a
       falseticker with valid certificate software bug.

11.7.  Security Considerations

   This section discusses the most obvious security vulnerabilities in
   the various Autokey dances.  In the following discussion the
   cryptographic algorithms and private values themselves are assumed
   secure; that is, a brute force cryptanalytic attack will not detected until reveal
   the
       client host private key, sign private key, cookie value, identity
   parameters, server seed or autokey seed.  In addition, an intruder
   will not be able to predict random generator values.

11.8.  Protocol Vulnerability

   While the protocol has synchronized not been subjected to a clique of proventic truechimers.

Appendix C.  Certificates

   Certificate extension fields are used to convey information used by formal analysis, a few
   preliminary assertions can be made.  In the identity schemes, such as whether client/server and
   symmetric dances the certificate underlying NTP on-wire protocol is private,
   trusted or contains a public identity key.  While resistant to
   lost, duplicate and bogus packets, even if the semantics of
   these fields generally conforms with conventional usage, there are
   subtle variations.  The fields used by Autokey Version 2 include:

   o  Basic Constraints.  This field defines clock is not
   synchronized, so the basic functions of protocol is not vulnerable to a wiretapper
   attack.  A middleman attack, even if it could simulate a valid
   cookie, could not present a valid signature.

   In the
      certificate.  It contains broadcast dance the string "critical,CA:TRUE", which
      means client begins with a volley in client/
   server mode to obtain the field must be interpreted autokey values and signature, so has the associated private
   same protection as in that mode.  When continuing in receive-only
   mode, a wiretapper cannot produce a key list with valid signed
   autokey values.  The most it can be used do is replay an old packet causing
   clients to sign other certificates.  While included for
      compatibility, Autokey makes no use of this field.

   o  Key Usage.  This field defines repeat the intended use of autokey hash operations until exceeding the public
   maximum key
      contained in the certificate.  It contains the string
      "digitalSignature,keyCertSign", which means number.

   A client instantiates cryptographic variables only if the contained public
      key can be used server is
   synchronized to verify signatures on a proventic source.  A server does not sign values or
   generate cryptographic data and other
      certificates.  While included for compatibility, Autokey makes no
      use of this field.

   o  Extended Key Usage. files unless synchronized to a proventic
   source.  This field further refines raises an interesting issue: how does a client generate
   proventic cryptographic files before it has ever been synchronized to
   a proventic source?  [Who shaves the intended use
      of barber if the public key contained barber shaves
   everybody in the certificate and town who does not shave himself?]  In principle, this
   paradox is present resolved by assuming the primary (stratum 1) servers are
   proventicated by external phenomenological means.

11.9.  Clogging Vulnerability

   A self-induced clogging incident cannot happen, since signatures are
   computed only
      in self-signed certificates.  It contains when the string "Private" if data have changed and the certificate is designated private or data do not change
   very often.  For instance, the string "trustRoot" if
      it is designated trusted.  A private certificate is always
      trusted.

   o  Subject Key Identifier.  This field contains autokey values are signed only when
   the public identity key used in the GQ identity scheme.  It list is present regenerated, which happens about once an hour, while
   the public values are signed only if when one of them is updated during
   a dance or the GQ
      scheme server seed is configured.

Appendix D.  Identity Schemes

   The Internet infrastructure model described refreshed, which happens about once per
   day.

   There are two clogging vulnerabilities exposed in [10] is based on
   certificate trails where a subject proves identity to a certificate
   authority (CA) who then signs the subject certificate using protocol
   design: an encryption attack where the CA
   issuer key.  The CA in turn proves identity intruder hopes to clog the next CA and
   obtains its own signed certificate.  The trail continues to a CA
   victim server with needless cryptographic calculations, and a self-signed trusted root certificate independently validated by
   other means.  If it is possible to prove identity at each step, each
   certificate along
   decryption attack where the trail can be considered trusted relative intruder attempts to clog the
   identity scheme and trusted root certificate.

   The important issue victim
   client with respect to NTP needless cryptographic calculations.  Autokey uses public
   key cryptography and the algorithms that perform these functions
   consume significant resources.

   In client/server and peer dances an encryption hazard exists when a
   wiretapper replays prior cookie request messages at speed.  There is
   no obvious way to deflect such attacks, as the cryptographic strength server retains no
   state between requests.  Replays of the identity scheme, since if a middleman could compromise it, the
   trail would have a security breach.  In electric mail cookie response messages are
   detected and commerce discarded by the identity scheme can be based on handwritten signatures,
   photographs, fingerprints and other things very hard to counterfeit.
   As applied to NTP subnets and identity proofs, the scheme must allow on-wire protocol.

   In broadcast mode a client a decription hazard exists when a
   wiretapper replays autokey response messages at speed.  Once
   synchronized to securely verify that a server knows proventic source, a legitimate extension field with
   timestamp the same secret that
   it does, presuming the secret was previously instantiated by secure
   means, but without revealing the secret to members outside the group.

   While as or earlier than the identity scheme described in RFC-2875 [9] most recently received of
   that type is based on immediately discarded.  This foils a
   ubiquitous Diffie-Hellman infrastructure, it is expensive to generate
   and use when compared to others described in this appendix.  There
   are five schemes now implemented middleman cut-and-
   paste attack using an earlier response, for example.  A legitimate
   extension field with timestamp 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).
   The available schemes are selected during the key generation phase,
   with future is unlikely, as that
   would require predicting the particular scheme selected during autokey sequence.  In either case the parameter exchange.

   The IFF, GQ and MV schemes involve
   extension field is discarded before expensive signature computations.
   This defense is most useful in symmetric mode, but a cryptographically strong
   challenge-response exchange where useful
   redundancy in other modes.

   An interesting adventure is when an intruder cannot learn the group
   key, even after repeated observations of multiple exchanges.  These
   schemes begin when the client sends a nonce to the server, which then
   rolls its own nonce, performs replays a mathematical operation and sends the
   results along recent packet
   with an intentional bit error.  A stateless server will return a
   crypto-NAK message digest to which will be discarded by the client.  The client
   performs a second mathematical operation to produce NTP on-wire
   protocol.  However, a digest that
   must match the one included in legitimate crypto-NAK is sent if the message.  To server has
   just refreshed the extent that a server can prove identity to a client without either knowing seed.  In this case the
   group key, a scheme is properly described as a zero-knowledge proof.

D.1.  Private Certificate (PC) Scheme

   The PC scheme shown in Figure Figure 13 involves the use of client performs
   a private
   certificate general reset and restarts the protocol as group key.  A certificate is designated private by a
   X509 expected.

12.  IANA Considerations

   Any IANA registries needed?

13.  Acknowledgements

   ...

14.  References

14.1.  Normative References

   [1]   Burbank, J., "Network Time Protocol Version 3 extension field when generated by utility routines 4 Protocol And
         Algorithms Specification", draft-ietf-ntp-ntpv4-proto-08 (work
         in
   the NTP software distribution.  The certificate is distributed to all
   other group members by secure means progress), November 2007.

14.2.  Informative References

   [2]   Maughan, D., Schneider, M., and M. Schertler, "Internet
         Security Association and Key Management Protocol (ISAKMP)",
         RFC 2408, November 1998.

   [3]   Orman, H., "The OAKLEY Key Determination Protocol", RFC 2412,
         November 1998.

   [4]   Karn, P. and W. Simpson, "Photuris: Session-Key Management
         Protocol", RFC 2522, March 1999.

   [5]   Kent, S. and R. Atkinson, "IP Encapsulating Security Payload
         (ESP)", RFC 2406, November 1998.

   [6]   Kent, S. and is never revealed outside the
   group.  A client is marked trusted in the Parameter Exchange R. Atkinson, "IP Authentication Header", RFC 2402,
         November 1998.

   [7]   Mills, D., "Network Time Protocol (Version 3) Specification,
         Implementation", RFC 1305, March 1992.

   [8]   Prafullchandra, H. and
   authentic when the first signature is verified.  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 J. Schaad, "Diffie-Hellman Proof-of-
         Possession Algorithms", RFC 2875, July 2000.

   [9]   Adams, C. and activated simultaneously.

                             Trusted
                            Authority
              Secure     +-------------+    Secure
          +--------------| Certificate |-------------+
          |              +-------------+             |
          |                                          |
         \|/                                        \|/
   +-------------+                            +-------------+
   | S. Farrell, "Internet X.509 Public Key
         Infrastructure Certificate |                            | Management Protocols", RFC 2510,
         March 1999.

   [10]  Housley, R., Polk, W., Ford, W., and D. Solo, "Internet X.509
         Public Key Infrastructure Certificate |
   +-------------+                            +-------------+
       Server                                     Client

            Figure 13: Private and Certificate (PC) Identity Scheme

   The PC scheme uses a private certificate as group key.  A certificate
   is designated private
         Revocation List (CRL) Profile", RFC 3280, April 2002.

   [11]  Schnorr, C., "Efficient signature generation for the purpose of the this smart cards",
         1991.

   [12]  Stinson, D., "Cryptography - Theory and Practice", 1995.

   [13]  Guillou, L. and J. Quisquatar, "A "paradoxical" identity-based
         signature scheme if resulting from zero-knowledge", 1990.

   [14]  Mu, Y. and V. Varadharajan, "Robust and secure broadcasting",
         2001.

   [15]  Mills, D., ""Compouter Network Time Synchronization - the CIS
   Private bit is lit.  The certificate is distributed to all other
   group members by secret means
         Network Time Protocol"", 2006.

   [16]  Bassham, L., Polk, W., and never revealed outside R. Housley, "Algorithms and
         Identifiers for the group.
   There is no identity exchange, since Internet X.509 Public Key Infrastructure
         Certificate and Certificate Revocation List (CRL) Profile",
         RFC 3279, April 2002.

Appendix A.  Timestamps, Filestamps and Partial Ordering

   When the host starts, it reads the host key and host certificate itself is
   files, which are required for continued operation.  It also reads the
   group key.  Therefore,
   sign key and leapseconds values, when available.  When reading these
   files the parameter exchange completes host checks the VAL,
   IFF file formats and SGN bits are lit filestamps for validity;
   for instance, all filestamps must be later than the time the UTC
   timescale was established in 1972 and the server status word.  When certificate filestamp must
   not be earlier than its associated sign key filestamp.  At the
   following cookie exchange is complete, time
   the PRV bit files are read the host is lit and
   operation continues as described in not synchronized, so it cannot
   determine whether the main body of this report.

D.2.  Trusted Certificate (TC) Scheme

   All filestamps are bogus other schemes involve a conventional certificate trail as shown
   in Figure Figure 14.  As described in RFC-4210 [10], each certificate
   is signed by an issuer one step closer than these simple
   checks.  It must not produce filestamps or timestamps until
   sunchronized to the trusted host, which has a self-signed trusted certificate, proventic source.

   In the following the relation A certificate --> B is designated
   trusted by a X509 Version 3 extension field when generated by utility
   routines in the NTP software distribution. Lamport's "happens before"
   relation, which is true if event A host obtains the
   certificates of all other hosts along the trail leading happens before event B. When
   timestamps are compared to a trusted
   host by timestamps, the Autokey protocol, then requests relation is false if A
   <--> B; that is, false if the immediately ascendant
   host to sign its certificate.  Subsequently, these certificates events are
   provided simultaneous.  For
   timestamps compared to descendent hosts by the Autokey protocol.  In this scheme
   keys filestamps and certificates can be refreshed at any time, but a masquerade
   vulnerability remains unless a request filestamps compared to sign a client certificate
   is validated by some means such as reverse-DNS.  If no specific
   identity scheme is specified in
   filestamps, the Identification Exchange, this relation is true if A <--> B. Note that the default TC scheme.

                                                           Trusted
                   Host                 Host                 Host
              +-----------+        +-----------+        +-----------+
         +--->|  Subject  |   +--->|  Subject  |   +--->|  Subject  |
         |    +-----------+   |    +-----------+   |    +-----------+
   ...---+    |  Issuer   |---+    |  Issuer   |---+    |  Issuer   |
              +-----------+        +-----------+        +-----------+
              | Signature |        | Signature |        | Signature |
              +-----------+        +-----------+        +-----------+

            Figure 14: Private Certificate (PC) Identity Scheme

   The TC identification exchange follows the parameter exchange current
   time plays no part in
   which these assertions except in (6) below; however,
   the VAL bit is lit.  It involves a conventional certificate
   trail and NTP protocol itself insures a sequence of certificates, each signed by an issuer one
   stratum level lower than correct partial ordering for all
   current time values.

   The following assertions apply to all relevant responses:

   1.  The client saves the client, most recent timestamp T0 and terminating at a trusted
   certificate, as described in [10].  A certificate is designated
   trusted filestamp F0
       for the purpose of the TC scheme if respective signature type.  For every received message
       carrying timestamp T1 and filestamp F1, the CIS Trust bit message is lit discarded
       unless T0 --> T1 and the certificate F0 --> F1.  The requirement that T0 --> T1
       is self-signed.  Such would normally be the case
   when the trail ends at a primary (stratum 1) server, but defense against replays of old messages.

   2.  For timestamp T and filestamp F, F --> T; that is, the trail
   can end at a secondary server if filestamp
       must happen before the security model permits this.

   When a certificate is obtained from timestamp.  If not, this could be due to a server,
       file generation error or when a certificate
   is signed by a server, A CIS for the new certificate is pushed on the
   certificate list, but only if significant error in the system clock
       time.

   3.  For sign key filestamp S, certificate filestamp is greater
   than any with the same subject name C, cookie
       timestamp D and issuer name already on autokey timestamp A, S --> C --> D --> A; that
       is, the
   list.  The list is then scanned looking for signature opportunities.
   If a CIS issuer name matches autokey must be generated after the subject name of another CIS cookie, the cookie
       after the certificate and the
   issuer certificate is verified using after the public sign key.

   4.  For sign key of the subject
   certificate, the CIS Sign bit is lit in the issuer CIS.  Furthermore,
   if the Trust bit is lit in filestamp S and certificate filestamp C specifying
       begin time B and end time E, S --> C--> B --> E; that is, the
       valid period must not be retroactive.

   5.  A certificate for subject CIS, the Trust bit is lit in
   the S signed by issuer CIS.

   The client continues to follow the I and with filestamp
       C1 obsoletes, but does not necessarily invalidate, another
       certificate trail to a self-signed
   certificate, lighting with the Sign same subject and Trust bits as it proceeds.  If it
   finds a self-signed issuer but with filestamp
       C0, where C0 --> C1.

   6.  A certificate with Trust bit lit, the client lights
   the IFF begin time B and PRV bits end time E is invalid and can
       not be used to verify signatures if t --> B or E --> t, where t
       is the exchange completes.  It can, however,
   happen current proventic time.  Note that the client finds a self-signed public key
       previously extracted from the certificate with Trust bit
   dark. continues to be valid
       for an indefinite time.  This can happen when raises the interesting possibility
       where a truechimer server is just coming up, with expired certificate or a
       falseticker with valid certificate are not detected until the
       client has synchronized to a proventic source, but has not yet completed the
   Sign exchange.  This is considered a temporary condition, so the
   client simply retries at poll opportunities until the server
   certificate is signed.

D.3.  Schnorr (IFF) Scheme

   The Schnorr (IFF) identity scheme is useful when certificates source.

Appendix B.  Identity Schemes

   There are
   generated by means other than the NTP software library, such as a
   trusted public authority.  In this case a X.509v3 extension field
   might not be available to convey the five identity public key.  The scheme
   involves a set of parameters which persist for the life of the
   scheme.  New generations of these parameters must be securely
   transmitted to all members of schemes in the group before use. NTPv4 reference
   implementation: (1) private certificate (PC), (2) trusted certificate
   (TC), (3) a modified Schnorr algorithm (IFF - Identify Friend or
   Foe), (4) a modified Guillou-Quisquater algorithm (GQ), and (5) a
   modified Mu-Varadharajan algorithm (MV).

   The PC scheme is
   self contained intended for testing and independent of new generations of host keys, sign
   keys development and certificates.

   Certificates can be generated by the OpenSSL library or an external
   public certificate authority, but conveying an arbitrary public value
   in not
   recommended for general use.  The TC scheme uses a certificate extension field might trail,
   but not be possible. an identity scheme.  The TA
   generates IFF parameters and keys IFF, GQ and distributes them by secure
   means to all servers, then removes MV identity schemes use
   a cryptographically strong challenge-response exchange where an
   intruder cannot learn the group key and redistributes
   these data to dependent clients.  Without key, even after repeated observations
   of multiple exchanges.  These schemes begin when the group key a client
   cannot masquerade as sends a legitimate server.

   The IFF parameters are generated by OpenSSL routines normally used
   nonce to
   generate DSA keys.  By happy coincidence, the mathematical principles
   on server, which IFF is based are similar to DSA, but only the moduli p, q
   and generator g are used in identity calculations.  The parameters
   hide in then rolls its own nonce, performs a DSA cuckoo structure
   mathematical operation and use sends the same members.  The values
   are used by an identity scheme based on DSA cryptography and
   described in [12] and [13] p. 285. results to the client.  The p is a 512-bit prime, g
   client performs a
   generator of second mathematical operation to prove the multiplicative server
   has the same group Zp* and q a 160-bit prime that
   divides (p-1) and is a qth root of 1 mod p; that is, g^q mod p. key as the client.

B.1.  Private Certificate (PC) Scheme

   The
   TA rolls PC scheme shown in Figure Figure 12 uses a private random certificate as
   the group key b (0 < b < q), then computes
   public client key v = g^(q-b) mod p.  The TA distributes (p, q, g, b)
   to all servers using secure means and (p, q, g, v) to all clients not
   necessarily using secure means. key.

                             Trusted
                            Authority
                                  +------------+
                                  | Parameters |
              Secure     +------------+   Insecure
                    +-------------| Group Key  |-----------+
                    |             +------------+           |
                    |             | Client Key     +-------------+    Secure
          +--------------| Certificate |-------------+
          |              +-------------+             |
          |             +------------+                                          |
         \|/                                        \|/
              +------------+         Challenge       +------------+
   +-------------+                            +-------------+
   | Parameters |<------------------------| Parameters Certificate |
              +------------+                         +------------+                            |  Group Key |------------------------>| Client Key Certificate |
              +------------+         Response        +------------+
   +-------------+                            +-------------+
       Server                                     Client

            Figure 15: Schnorr (IFF) 12: Private Certificate (PC) Identity Scheme

   A certificate is designated private when the X509v3 Extended Key
   Usage extension field is present and contains "Private".  The IFF identity scheme private
   certificate is shown distributed to all other group members by secret
   means, so in Figure Figure 15.  The TA
   generates fact becomes a DSA parameter structure for use as IFF parameters.  The
   IFF parameters symmetric key.  Private certificates are identical to the DSA parameters,
   also trusted, so the OpenSSL
   library DSA parameter generation routine can be used directly.  The
   DSA parameter structure shown in Table Figure 16 there is written to a file
   as no need for a DSA private key encoded in PEM.  Unused structure members are
   set to one.

              +----------------------------------+-------------+
              |   IFF   |   DSA    |   Item      |   Include   |
              +=========+==========+=============+=============+
              |    p    |    p     | modulus     |    all      |
              +---------+----------+-------------+-------------+
              |    q    |    q     | modulus     |    all certificate trail or identity
   scheme.

B.2.  Trusted Certificate (TC) Scheme

   All other schemes involve a conventional certificate trail as shown
   in Figure Figure 13.

                                                           Trusted
                   Host                 Host                 Host
              +-----------+        +-----------+        +-----------+
         +--->|  Subject  |
              +---------+----------+-------------+-------------+   +--->|  Subject  |    g   +--->|  Subject  |    g
         | generator    +-----------+   |    all    +-----------+   |
              +---------+----------+-------------+-------------+    +-----------+
   ...---+    |    b  Issuer   |---+    | priv_key  Issuer   |---+    | group key  Issuer   |   server
              +-----------+        +-----------+        +-----------+
              |
              +---------+----------+-------------+-------------+ Signature |    v        | pub_key Signature | client keys        |   client Signature |
              +---------+----------+-------------+-------------+
              +-----------+        +-----------+        +-----------+

            Figure 16: IFF 13: Trusted Certificate (TC) Identity Scheme Parameters

   Alice challenges Bob to confirm identity using the following protocol
   exchange.

   1.  Alice rolls random r (0 < r < q) and sends to Bob.

   2.  Bob rolls random k (0 < k < q), computes y = k + br mod q and x =
       g^k mod p, then sends (y, hash(x)) to Alice.

   3.  Alice computes z = g^y * v^r mod p and verifies hash(z) =
       hash(x).

   If the hashes match, Alice knows that Bob has the group key b.
   Besides making the response shorter, the hash makes it effectively
   impossible for an intruder to solve for b by observing a number of
   these messages.  The signed response binds this knowledge to Bob's
   private key and the public key previously received in his
   certificate.  On success the IFF and PRV bits are lit

   As described in the server
   status word.

D.4.  Guillard-Quisquater (GQ)

   The Guillou-Quisquater (GQ) identity scheme RFC-2510 [9], each certificate is useful when
   certificates are generated using the NTP software library.  These
   routines convey the GQ public key in a X.509v3 extension field.  The
   scheme involves a set of parameters which persist for the life of signed by an issuer
   one step closer to the
   scheme and a private/public identity key, trusted host, which is refreshed each
   time has a new self-signed trusted
   certificate.  A certificate is generated.  The utility inserts the client
   key in designated trusted when an X.509 X509v3
   Extended Key Usage extension field when is present and contains
   "trustRoot".  If no identity scheme is specified in the certificate parameter
   exchange, this is generated. the default scheme.

B.3.  Schnorr (IFF) Identity Scheme

   The client key IFF scheme is used useful when computing the response to a challenge.
   The TA generates the GQ parameters and keys and distributes them by
   secure means to all group members.  The scheme key is self contained and
   independent of new generations of host keys and sign concealed, so that
   client keys and
   certificates. need not be protected.  The GQ parameters are generated by OpenSSL routines normally used to
   generate RSA keys.  By happy coincidence, the mathematical principles
   on which GQ primary disacvantage is based are similar to RSA, but only that
   when the modulus n server key is
   used in identity calculations.  The parameters hide in a RSA cuckoo
   structure and use refreshed all hosts must update the same members. client
   key.  The values are used in an
   identity scheme based on RSA cryptography and described shown in [14] and
   [13] p. 300 (with errors).  The 512-bit Figure Figure 14 involves a set of public modulus n=pq, where p
   parameters and q are secret large primes.  The TA rolls random a group key b (0 <
   b < n) and distributes (n, b) to all group members using secure
   means.  The including both private server key and public
   components.  The public component is the client key are constructed
   later. key.

                                     Trusted
                                    Authority
                                  +------------+
                                  | Parameters |
                       Secure     +------------+   Secure   Insecure
                    +-------------| Group Key  |-----------+
                    |             +------------+           |
                   \|/                                    \|/
              +------------+         Challenge       +------------+
              | Parameters |<------------------------| Parameters |
              +------------+                         +------------+
              |  Group Key |                         |  Group Key Parameters |<------------------------| Parameters |
              +------------+         Response                         +------------+
              | Server  Group Key |------------------------>| Client Key |
              +------------+         Response        +------------+
                  Server                                 Client

                 Figure 17: 14: Schnorr (IFF) Identity Scheme
   By happy coincidence, the mathematical principles on which IFF is
   based are similar to DSA.  The GQ identity scheme is shown a modification an algorithm
   described in [11] and [12] p. 285.  The parameters are generated by
   routines in Figure Figure 17.  When generating
   new certificates, the server OpenSSL library, but only the moduli p, q and
   generator g are used.  The p is a 512-bit prime, g a generator of the
   multiplicative group Z_p* and q a 160-bit prime that divides (p-1)
   and is a qth root of 1 mod p; that is, g^q = 1 mod p.  The TA rolls new random a
   private server random group key u b (0 < u b < n) and q), then computes public client
   key its inverse obscured by the group key v = (u^-1)^b g^(q-b) mod n.  These values replace the private p.  The TA distributes (p, q, g, b) to all
   servers using secure means and (p, q, g, v) to all clients not
   necessarily using secure means.

   The TA hides IFF parameters and public keys
   normally generated by in an OpenSSL DSA cuckoo
   structure.  The IFF parameters are identical to the RSA scheme.  In addition, DSA parameters,
   so the public client
   key is conveyed in a X.509 certificate extension. OpenSSL library can be used directly.  The updated GQ structure shown in Figure Figure 18
   FigureFigure 15 is written to a file as an RSA a DSA private key encoded in
   PEM.  Unused structure members are set to one.

              +---------------------------------+-------------+

              +----------------------------------+-------------+
              |   GQ   IFF   |   RSA   DSA    |   Item      |   Include   |
              +=========+==========+============+=============+
              +=========+==========+=============+=============+
              |    n    p    |    n    p     | modulus     |    all      |
              +---------+----------+------------+-------------+
              +---------+----------+-------------+-------------+
              |    b    q    |    e    q     | group key modulus     |   server    all      |
              +---------+----------+------------+-------------+
              +---------+----------+-------------+-------------+
              |    u    g    |    p    g     | server generator   |    all      |
              +---------+----------+-------------+-------------+
              |    b    | priv_key | group key   |   server    |
              +---------+----------+------------+-------------+
              +---------+----------+-------------+-------------+
              |    v    |    q pub_key  | client key  |   client    |
              +---------+----------+------------+-------------+
              +---------+----------+-------------+-------------+

                 Figure 18: 15: IFF Identity Scheme Parameters Structure

   Alice challenges Bob to confirm identity using the following protocol
   exchange.

   1.  Alice rolls random r (0 < r < n) and sends to Bob.

   2.  Bob rolls random k (0 < k < n) and computes y = ku^r mod n and x
       = k^b mod n, then sends (y, hash(x)) to Alice.

   3.  Alice computes z = (v^r)*(y^b) mod n and verifies hash(z) =
       hash(x).

   If the hashes match, Alice knows that Bob has the group key b.
   Besides making the response shorter, the hash makes it effectively
   impossible for an intruder to solve for b by observing a number of
   these messages.  The signed response binds this knowledge to Bob's
   private key and the public key previously received in his
   certificate.  Further evidence is the certificate containing the
   public identity key, since this is also signed with Bob's private
   key.  On success the IFF and PRV bits are lit in the server status
   word.

D.5.  Mu-Varadharajan (MV) Identity Scheme

   The Mu-Varadharajan (MV) scheme was originally intended to encrypt
   broadcast transmissions to receivers which do not transmit.  There is
   one encryption key for the broadcaster and a separate decryption key
   for each receiver.  It operates something like a pay-per-view
   satellite broadcasting system where the session key is encrypted by
   the broadcaster and the decryption keys are held in a tamper proof
   set-top box.  We don't use it this way, but read on.

   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 an intricate cryptosystem
   involving public < r < q) and private encryption keys, together with a number
   of activation keys sends to Bob.

   2.  Bob rolls random k (0 < k < q), computes y = k + br mod q and associated private client decryption keys.
   The activation keys are used by the TA x =
       g^k mod p, then sends (y, hash(x)) to activate Alice.

   3.  Alice computes z = g^y * v^r mod p and revoke
   individual client decryption keys without changing verifies hash(z) equals
       hash(x).

   If the decryption
   keys themselves.

   The TA provides hashes match, Alice knows that Bob has the server with a private encryption group key and public
   decryption key.  The server adjusts b.

   Besides making the keys response shorter, the hash makes it effectively
   impossible for an intruder to solve for b by observing 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. number of
   these messages.  The client computes the decryption key from
   its signed response binds this knowledge to Bob's
   private decryption key and the public decryption key previously received in the
   message.

   In the MV scheme the activation keys are known only to the TA.  The
   TA decides which keys to activate and provides to the servers a
   private encryption key E and public decryption keys g-bar and g-hat
   which depend on the activated keys. his
   certificate.

B.4.  Guillard-Quisquater (GQ) Identity Scheme

   The servers have no additional
   information and, in particular, cannot masquerade as a TA.  In
   addition, GQ scheme is useful when the TA provides to each client j individual private
   decryption keys x-bar_j and x-hat_j , which do not need to server key must be changed
   if refreshed from
   time to time without changing the TA activates or deactivates this group key.  The clients have no
   further information and, NTP utility
   programs include the GQ client key in particular, cannot masquerade as a server
   or TA. the X509v3 Subject Key
   Identifier extension field.  The MV values hide in a DSA cuckoo structure which uses primary disadvantage of the same
   parameters, but generated scheme
   is that the group key must be protected in both the server and
   client.  A secondary disadvantage is that when a different way. server key is
   refreshed, old extension fields no longer work.  The values are used in
   an encryption scheme similar to El Gamal cryptography and is shown
   in Figure Figure 16a involves a
   polynomial formed from the expansion set of product terms (x-x_1)*(x-
   x_2)*(x-x_3)*...*(x-x_n), as described in [15].  The paper has
   significant errors public parameters and serious omissions. group
   key used to generate private server keys and client keys.

                                     Trusted
                                    Authority
                                  +------------+
                                  | Parameters |
                                  +------------+
                                  | Group Key  |
                                  +------------+
                                  | Server Key |
                       Secure     +------------+   Secure
                    +-------------| Client Group Key  |-----------+
                    |             +------------+           |
                   \|/                                    \|/
              +------------+         Challenge       +------------+
              | Parameters |<------------------------| Parameters |
              +------------+                         +------------+
              |  Group Key |                         |  Group Key |
              +------------+         Response        +------------+
              | Server Key |------------------------>| Client Key |
              +------------+         Response                         +------------+
                  Server                                 Client

                 Figure 19: Mu-Varadharajan (MV) 16: Schnorr (IFF) Identity Scheme

   By happy coincidence, the mathematical principles on which GQ is
   based are similar to RSA.  The MV identity scheme is shown a modification of an
   algorithm described in [13] and [12] p. 300 (with errors).  The
   parameters are generated by routines in the OpenSSL library, but only
   the moduli p and q are used.  The 512-bit public modulus is n=pq,
   where p and q are secret large primes.  The TA rolls random large
   prime b (0 < b < n) and distributes (n, b) to all group servers and
   clients using secure means, since an intruder in Figure Figure 19. possesion of these
   values could impersonate a legitimate server.  The TA writes
   the server parameters, private encryption server key
   and public decryption
   keys for all servers as a DSA private client key encoded in PEM, as shown are constructed later.

   The TA hides GQ parameters and keys in an OpenSSL RSA cuckoo
   structure.  The GQ parameters are identical to the RSA parameters, so
   the OpenSSL library can be used directly.  When generating a
   certificate, the Figure Figure 20.

              +---------------------------------+-------------+
              |   MV    |   DSA    |   Item     |   Include   |
              +=========+==========+============+=============+
              |    p    |    p     | modulus    |    all      |
              +---------+----------+------------+-------------+
              |    q    |    q     | modulus    |   server    |
              +---------+----------+------------+-------------+
              |    E    |    g     | private    |   server    |
              |         |          | encrypt    |             |
              +---------+----------+------------+-------------+
              |  g-bar  | priv_key | public     | server    |
              |         |          | decrypt    |             |
              +---------+----------+------------+-------------+
              |  g-hat  | pub_key  | public     | rolls random server    |
              |         |          | decrypt    |             |
              +---------+----------+------------+-------------+

                  Figure 20: MV Scheme Server Parameters

   The TA writes the client parameters key u (0 < u < n) and
   client key its inverse obscured by the group key v = (u^-1)^b mod n.
   These values replace the private decryption and public keys for
   each normally generated
   by the RSA scheme.  The client as key is conveyed in a DSA X.509 certificate
   extension.  The updated GQ structure shown in Figure Figure 17 is
   written as an RSA private key encoded in PEM.  It is used only by
   the designated recipient(s) who pay a suitably outrageous fee for its
   use.  Unused structure
   members are set to one, as shown in Table
   Figure 21, one.

              +---------------------------------+-------------+
              |   MV   GQ    |   DSA   RSA    |   Item     |   Include   |
              +=========+==========+============+=============+
              |    p    n    |    p    n     | modulus    |    all      |
              +---------+----------+------------+-------------+
              | x-bar_j | priv_key | public     |   client    |
              |    b    |    e     | decrypt group key  |    all      |
              +---------+----------+------------+-------------+
              | x-hat_j    u    | pub_key    p     | public server key |   client   server    |
              +---------+----------+------------+-------------+
              |    v    |    q     | decrypt client key |   client    |
              +---------+----------+------------+-------------+

                  Figure 21: MV 17: GQ Identity Scheme Client Parameters

   The devil is in the details.  Let q be Structure

   Alice challenges Bob to confirm identity using the product of n distinct
   primes s'_j (j = 1...n), where each s'_j, also called an activation
   key, has m significant bits.  Let prime p = 2q + 1, so that q following
   exchange.

   1.  Alice rolls random r (0 < r < n) and
   each s'_j divide p-1 sends to Bob.

   2.  Bob rolls random k (0 < k < n) and p has M=nm+1 significant bits.  Let g be the
   generator of the multiplicative group Zp*; that is, gcd(g, p-1) computes y = 1 ku^r mod n and g^q x
       = 1 k^b mod p.  We do modular arithmetic over Zq and n, then project
   into Zp* as powers of g.  Sometimes we have sends (y, hash(x)) to compute an inverse
   b^-1 of random b in Zq, but for that purpose we require gcd(b, q) Alice.

   3.  Alice computes z =
   1.  We expect M to be in the 500-bit range and (v^r)*(y^b) mod n relatively small,
   like 30.  The TA uses a nasty probabilistic algorithm to generate and verifies hash(z) equals
       hash(x).

   If the
   cryptosystem.

   1.  Generate hashes match, Alice knows that Bob has the m-bit primes s'_j (0 < j < n), which may have to be
       replaced later.  As a practical matter, corresponding
   server key u.  Besides making the response shorter, the hash makes it is tough to find more
       than 30 distinct primes
   effectively impossible for M=512 or 60 primes an intruder to solve for M=1024.  The
       latter can take several hundred iterations and several minutes on
       a Sun Blade 1000.

   2.  Compute modulus q = s'_1 * s'_2 * ... * s'_n, then modulus p = 2q
       + 1.  If p is composite, the TA replaces one of the primes with a
       new distinct prime and tries again.  Note that q will hardly be u by observing a
       secret since p is revealed
   number of these messages.  The signed response binds this knowledge
   to servers Bob's private key and clients.  However,
       factoring q to find the primes should be adequately hard, as this client key previously received in his
   certificate.

B.5.  Mu-Varadharajan (MV) Identity Scheme

   The MV scheme is perhaps the same problem considered hard in RSA.  Question: most interesting and flexible of the
   three challenge/response schemes, but is it as
       hard to find n small prime factors totalling M bits as it devilishly complicated.  It
   is most useful when a small number of servers provide synchronization
   to
       find two a large prime factors totalling M bits?  Remember, the bad
       guy doesn't know n.

   3.  Associate with client population where there might be considerable risk
   of compromise between and among the servers and clients.  The client
   population can be partitioned into a modest number of subgroups, each s'_j
   associated with an element s_j such that s_j*s'_j = s'_j
       mod q.  One way to find individual client key.

   The TA generates an s_j is the quotient s_j = (q + s'_j) /
       s'_j.

   4.  Compute the generator g of Z_p using intricate cryptosystem involving encryption and
   decryption keys, together with a random roll such that
       gcd(g, p-1) = 1 number of activation keys and g^q = 1 mod p.  If not, roll again.

   Once the cryptosystem parameters have been determined,
   associated client keys.  The TA can activate and revoke individual
   client keys without changing the client keys themselves.  The TA sets up
   a specific instance of
   provides to the scheme servers an encryption key E and partial decryption
   keys g-bar and g-hat which depend on the activated keys.  The servers
   have no additional information and, in particular, cannot masquerade
   as follows.

   1.  Roll n random roots x_j (0 < x_j < q) for a polynomial of order
       n.  While it may TA.  In addition, the TA provides to each client j individual
   partial decryption keys x-bar_j and x-hat_j, which do not need to be strictly necessary, Make sure each root
       has
   changed if the TA activates or deactivates any client key.  The
   clients have no factors further information and, in common with q.

   2.  Expand particular, cannot
   masquerade as a server or TA.

   The scheme uses an encryption algorithm similar to El Gamal
   cryptography and a polynomial formed from the n expansion of product
   terms (x-x_0)*(x-x_1)*...*(x-x_n) to form n
       + 1 coefficients a_i mod q (0 <= i < n) (x-x_1)(x-x_2)(x-x_3)...(x-x_n), as described in powers of x using a
       fast method contributed by C. Boncelet.

   3.  Generate g_i = g^(a_i) [14].  The
   paper has significant errors and serious omissions.  The cryptosystem
   is constructed so that, for every encrytion key E its iniverse is
   (g-bar^x-hat_j)(g-hat^x-bar_j) mod p for all i and the generator g.
       Verify every j.  This remains true
   if both quantities are raised to the product g_i^(a_i*(x_j)^i) = 1 power k mod p p.  The difficulty
   in finding E is equivalent to the descrete log problem.

   The scheme is shown in Figure Figure 18.  The TA generates the
   parameters, group key, server keys and client keys, one for each
   client, all i, j (0 <=
       i < n, 0 <= j < n). of which must be protected to prevent theft of service.
   Note that only the TA has the a_i*(x_j)^i exponent group key, which is computed
       mod q, but not known to either
   the servers or clients.  In this sense the MV scheme is a zero-
   knowledge proof.

                                     Trusted
                                    Authority
                                  +------------+
                                  | Parameters |
                                  +------------+
                                  | Group Key  |
                                  +------------+
                                  | Server Key |
                       Secure     +------------+   Secure
                    +-------------| Client Key |-----------+
                    |             +------------+           |
                   \|/                                    \|/
              +------------+         Challenge       +------------+
              | Parameters |<------------------------| Parameters |
              +------------+                         +------------+
              | Server Key |------------------------>| Client Key |
              +------------+         Response        +------------+
                  Server                                 Client

              Figure 18: Mu-Varadharajan (MV) Identity Scheme

   The TA hides MV parameters and keys in OpenSSL DSA cuckoo structures.
   The MV parameters are identical to the g_i is computed mod p.  Also note DSA parameters, so the expression
       given OpenSSL
   library can be used directly.  The structure shown in the paper cited is incorrect.

   4.  Make master encryption key A = product of (g_i)^x_j mod p (0 <= i
       < n, 0 <= j < n).  Keep it around for awhile, since it is
       expensive Figures below
   are written to compute.

   5.  Roll files as a DSA private random group key b (0 < b < q), where gcd(b, q) = 1 encoded in PEM.  Unused
   structure members are set to guarantee one.  Figure Figure 19 shows the data
   structure used by the servers, while Figure Figure 20 shows the inverse exists, then compute b^-1 mod q.  If b
       is changed, all keys must be recomputed.

   6.  Make private
   client keys x-bar_j = b^-1 * ((x_1)^n + (x_2)^n +
       ... + (x_n)^n) mod data structure associated with each activation key.

              +---------------------------------+-------------+
              |   MV    |   DSA    |   Item     |   Include   |
              +=========+==========+============+=============+
              |    p    |    p     | modulus    |    all      |
              +---------+----------+------------+-------------+
              |    q (omitting (x_j)^n from the summation) and
       x-hat_j = s_j * (x_j)^n mod    |    q for     | modulus    |   server    |
              +---------+----------+------------+-------------+
              |    E    |    g     | private    |   server    |
              |         |          | encrypt    |             |
              +---------+----------+------------+-------------+
              |  g-bar  | priv_key | public     |   server    |
              |         |          | decrypt    |             |
              +---------+----------+------------+-------------+
              |  g-hat  | pub_key  | public     |   server    |
              |         |          | decrypt    |             |
              +---------+----------+------------+-------------+
                   Figure 19: MV Scheme Server Structure

              +---------------------------------+-------------+
              |   MV    |   DSA    |   Item     |   Include   |
              +=========+==========+============+=============+
              |    p    |    p     | modulus    |    all j.  Note that the keys for
       the jth      |
              +---------+----------+------------+-------------+
              | x-bar_j | priv_key | public     |   client    |
              |         |          | decrypt    |             |
              +---------+----------+------------+-------------+
              | x-hat_j | pub_key  | public     |   client involve only s_j, but not s'_j or s.  The TA sends
       (p, x-bar_j, x-hat_j) to the jth client(s) using secure means.

   7.    |
              |         |          | decrypt    |             |
              +---------+----------+------------+-------------+

                   Figure 20: MV Scheme Client Structure

   The activation key devil is initially q by construction.  The TA
       revokes client j by dividing q by s'_j.  The quotient becomes in the
       activation key s.  Note we always have to revoke one key;
       otherwise, details, which are beyond the plaintext and cryptotext would be identical. scope of this memo.
   The
       TA computes E = A^s, g-bar = x-bar^s mod p, g-hat = x-hat^sb mod
       p steps in generating the cryptosystem activating the keys and sends (p, E, g-bar, g-hat to
   generating the servers using secure
       means. partial decryption keys are in [15] page 170 ff.

   Alice challenges Bob to confirm identity using the following
   exchange.

   1.  Alice rolls random r (0 < r < q) and sends to Bob.

   2.  Bob rolls random k (0 < k < q) and computes the session
       encryption key E' E-prime = E^k mod p and public partial decryption key g-bar' keys
       g-bar-prime = g-bar^k mod p and g-hat' g-hat-prime = g-hat^k mod p.  He
       encrypts x = E' E-prime * r mod p and sends (hash(x), g-bar', g-hat') (x, g-bar-prime, g-hat-
       prime) to Alice.

   3.  Alice computes the session decryption key E^-1 = (g-bar')^x-hat_j
       * (g-hat')^x-bar_j mod p, recovers the encryption key E' =
       (E^-1)^-1 mod p, encrypts z = E' * r mod p, then verifies that
       hash(z) = hash(x).

D.6.  Interoperability Issues

   A specific combination of authentication scheme (none, symmetric key,
   Autokey), digest/signature scheme and identity scheme (PC, TC, IFF,
   GQ, MV) is called a cryptotype, although not all combinations are
   possible.  There may be management configurations where the servers
   and clients may not all support the same cryptotypes.  A secure NTPv4
   subnet can be configured in several ways while keeping in mind the
   principles explained in this section.  Note however that some
   cryptotype combinations may successfully interoperate with each
   other, but may not represent good security practice.

   The cryptotype of an association is determined at the time of
   mobilization, either at configuration time or some time later when a
   packet of appropriate cryptotype arrives.  When a client, broadcast
   or symmetric active association is mobilized at configuration time,
   it can be designated non-authentic, authenticated with symmetric key
   or authenticated with some Autokey scheme, key E^-1 = (g-bar-prime)^x-
       hat_j (g-hat-prime)^x-bar_j mod p and subsequently it will
   send packets with verifies that cryptotype.  When a responding server,
   broadcast client or symmetric passive association is mobilized, it r = E^-1 x.

Appendix C.  ASN.1 Encoding Rules

   Certain value fields in request and response messages contain data
   encoded in ASN.1 distinguished encoding rules (DER).  The BNF grammar
   for each encoding rule is
   designated given below along with the same cryptotype as OpenSSL routine
   used for the received packet.

   When multiple identity schemes are supported, encoding in the parameter exchange
   determines which one is used. reference implementation.  The request message contains bits
   corresponding to the schemes it supports, while object
   identifiers for the response encryption algorithms and message
   contains bits corresponding to the digest/
   signature encryption schemes it supports.  The client
   matches the server bits with its own and selects a compatible
   identity scheme. are specified in [16].  The server is driven entirely by the client
   selection and remains stateless.  When multiple selections particular
   algorithms required for conformance are
   possible, the order from most secure to least is GC, IFF, TC.  Note
   that PC does not interoperate with any of the others, since they
   require the host certificate which a PC server will not reveal.

   Following the principle that time is a public value, a server
   responds to any client packet that matches its cryptotype
   capabilities.  Thus, a server receiving a non-authenticated packet
   will respond with a non-authenticated packet, while the same server
   receiving a packet of a cryptotype it supports will respond with
   packets specified in this memo.

C.1.  COOKIE request, IFF response, GQ response, MV response

   The value field of that cryptotype.  However, new broadcast or manycast
   client associations or symmetric passive associations will not be
   mobilized unless the server supports COOKIE request message contains a cryptotype compatible with sequence of
   two integers (n, e) encoded by the
   first packet received.  By default, non-authenticated associations
   will not be mobilized unless overridden i2d_RSAPublicKey() routine in a decidedly dangerous way.

   Some examples may help to reduce confusion.  Client Alice has no
   specific cryptotype selected.  Server Bob supports both symmetric key the
   OpenSSL distribution.  In the request, n is the RSA modulus in bits
   and Autokey cryptography.  Alice's non-authenticated packets arrive
   at Bob, who replies with non-authenticated packets.  Cathy has e is the public exponent.

   RSAPublicKey ::= SEQUENCE {
           n ::= INTEGER,
           e ::= INTEGER
   }

   The IFF and GQ responses contain a copy sequence of Bob's symmetric key file and has selected key ID 4 two integers (r, s)
   encoded by the i2d_DSA_SIG() routine in packets to
   Bob. If Bob verifies the packet with key ID 4, he sends Cathy a reply
   with that key.  If authentication fails, Bob sends Cathy a thing
   called a crypto-NAK, which tells her something broke.  She can see OpenSSL distribution.  In
   the evidence using responses, r is the utility programs challenge response and s is the hash of the NTP software
   private value.

   DSAPublicKey ::= SEQUENCE {
           r ::= INTEGER,
           s ::= INTEGER
   }

   The MV response contains a sequence of three integers (p, q, g)
   encoded by the i2d_DSAparams() routine in the OpenSSL library.

   Symmetric peers Bob and Denise have rolled their own host keys,
   certificates and identity parameters and lit  In
   the host status bits for response, p is the identity schemes they can support.  Upon completion hash of the
   parameter exchange, both parties know the digest/signature scheme encrypted challenge value and
   available identity schemes (q,
   g) is the client portion of the other party.  They do not have decryption key.

   DSAparameters ::= SEQUENCE {
           p ::= INTEGER,
           q ::= INTEGER,
           g ::= INTEGER
   }

C.2.  Certificates

   Certificate extension fields are used to
   use convey information used by
   the same schemes, but each party must use identity schemes.  While the digest/signature
   scheme and one semantics of the identity schemes supported these fields generally
   conforms with conventional usage, there are subtle variations.  The
   fields used by Autokey Version 2 include:

   o  Basic Constraints.  This field defines the other party.

   It should be clear from basic functions of the above that Bob can support all
      certificate.  It contains the girls
   at string "critical,CA:TRUE", which
      means the same time, as long as he has compatible authentication field must be interpreted and
   identification credentials.  Now, Bob can act just like the girls in
   his own choice of servers; he associated private key
      can run multiple configured
   associations with multiple different servers (or the same server,
   although that might not be useful).  But, wise security policy might
   preclude some cryptotype combinations; used to sign other certificates.  While included for instance, running an
   identity scheme with one server and
      compatibility, Autokey makes no authentication with another
   might not be wise.

Appendix E.  ASN.1 Encoding Rules

   Certain value fields in request and response messages contain data
   encoded in ASN.1 distinguished encoding rules (DER).  The BNF grammar
   for each encoding rule is given below along with use of this field.

   o  Key Usage.  This field defines the OpenSSL routine
   used for intended use of the encoding public key
      contained in the reference implementation.  The object
   identifiers for certificate.  It contains the encryption algorithms string
      "digitalSignature,keyCertSign", which means the contained public
      key can be used to verify signatures on data and message digest/
   signature encryption schemes are specified in [16].  The particular
   algorithms required for conformance are not specified in this report.

E.1.  COOKIE request, IFF response, GQ response, MV response

   The value field other
      certificates.  While included for compatibility, Autokey makes no
      use of this field.

   o  Extended Key Usage.  This field further refines the COOKIE request message contains a sequence intended use
      of
   two integers (n, e) encoded by the i2d_RSAPublicKey() routine public key contained in the
   OpenSSL distribution.  In the request, n is the RSA modulus in bits certificate and e is the public exponent.

   RSAPublicKey ::= SEQUENCE {
           n ::= INTEGER,
           e ::= INTEGER
   }

   The IFF and GQ responses contain a sequence of two integers (r, s)
   encoded by the i2d_DSA_SIG() routine present only
      in self-signed certificates.  It contains the OpenSSL distribution.  In string "Private" if
      the responses, r certificate is designated private or the challenge response and s string "trustRoot" if
      it is the hash of the designated trusted.  A private value.

   DSAPublicKey ::= SEQUENCE {
           r ::= INTEGER,
           s ::= INTEGER
   }

   The MV response certificate is always
      trusted.

   o  Subject Key Identifier.  This field contains a sequence of three integers (p, q, g)
   encoded by the i2d_DSAparams() routine client identity
      key used in the OpenSSL library.  In
   the response, p GQ identity scheme.  It is present only if the hash of the encrypted challenge value and (q,
   g) GQ
      scheme is the client portion of the decryption key.

   DSAparameters ::= SEQUENCE {
           p ::= INTEGER,
           q ::= INTEGER,
           g ::= INTEGER
   }

E.2.  CERT response, SIGN request and response in use.

   The value field contains a X509v3 certificate encoded by the
   i2d_X509() routine in the OpenSSL distribution.  The encoding follows
   the rules stated in [11], [10], including the use of X509v3 extension
   fields.

   Certificate ::= SEQUENCE {
           tbsCertificate                  TBSCertificate,
           signatureAlgorithm              AlgorithmIdentifier,
           signatureValue                  BIT STRING
   }

   The signatureAlgorithm is the object identifier of the message
   digest/signature encryption scheme used to sign the certificate.  The
   signatureValue is computed by the certificate issuer using this
   algorithm and the issuer private key.

   TBSCertificate ::= SEQUENCE {
           version                         EXPLICIT v3(2),
           serialNumber                    CertificateSerialNumber,
           signature                       AlgorithmIdentifier,
           issuer                          Name,
           validity                        Validity,
           subject                         Name,
           subjectPublicKeyInfo            SubjectPublicKeyInfo,
           extensions                      EXPLICIT Extensions OPTIONAL
   }

   The serialNumber is an integer guaranteed to be unique for the
   generating host.  The reference implementation uses the NTP seconds
   when the certificate was generated.  The signature is the object
   identifier of the message digest/signature encryption scheme used to
   sign the certificate.  It must be identical to the
   signatureAlgorithm.

   CertificateSerialNumber ::= INTEGER
   Validity ::= SEQUENCE {
           notBefore                       UTCTime,
           notAfter                        UTCTime
   }

   The notBefore and notAfter define the period of validity as defined
   in Appendix D. B.

   SubjectPublicKeyInfo ::= SEQUENCE {
           algorithm                       AlgorithmIdentifier,
           subjectPublicKey                BIT STRING
   }

   The AlgorithmIdentifier specifies the encryption algorithm for the
   subject public key.  The subjectPublicKey is the public key of the
   subject.

   Extensions ::= SEQUENCE SIZE (1..MAX) OF Extension
   Extension ::= SEQUENCE {
           extnID                          OBJECT IDENTIFIER,
           critical                        BOOLEAN DEFAULT FALSE,
           extnValue                       OCTET STRING
   }

   Name ::= SEQUENCE {
           OBJECT IDENTIFIER               commonName
           PrintableString                 HostName
   }

   For all certificates, trusted host certificates the subject and issuer HostName is the unique DNS
   NTP name of the group, while for all other host to which certificates the
   subject and issuer HostName is the NTP name of the host.  In the public key belongs.  The
   reference implementation uses if these names are not explicitly specified,
   they default to the string returned by the Unix gethostname() routine
   (trailing NUL removed).  For other than self-signed certificates, the
   issuer HostName is the unique DNS name of the host signing the
   certificate.

Authors' Addresses

   Brian Haberman (editor)
   The Johns Hopkins University Applied Physics Laboratory
   11100 Johns Hopkins Road
   Laurel, MD  20723-6099
   US

   Phone: +1 443 778 1319
   Email: brian@innovationslab.net

   Dr. David L. Mills
   University of Delaware
   Newark, DE  19716
   US

   Phone: +1 302 831 8247
   Email: mills@udel.edu

Full Copyright Statement

   Copyright (C) The IETF Trust (2007). (2008).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.

Acknowledgment

   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).