tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Gloss.     Arch.     IMS     UICC    |    Misc.    |    search     info

RFC 5906

Pages: 58
Top     in Index     Prev     Next
in Group Index     Prev in Group     Next in Group     Group: NTP

Network Time Protocol Version 4: Autokey Specification

Part 1 of 3, p. 1 to 19
None       Next RFC Part


Top       ToC       Page 1 
Internet Engineering Task Force (IETF)                  B. Haberman, Ed.
Request for Comments: 5906                                       JHU/APL
Category: Informational                                         D. Mills
ISSN: 2070-1721                                              U. Delaware
                                                               June 2010

         Network Time Protocol Version 4: Autokey Specification


   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,
   Public Key Infrastructure (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 memo has been
   implemented, tested, and documented in the NTP version 4 (NTPv4)
   software distribution for the Unix, Windows, and Virtual Memory
   System (VMS) operating systems at

Status of This Memo

   This document is not an Internet Standards Track specification; it is
   published for informational purposes.

   This document is a product of the Internet Engineering Task Force
   (IETF).  It represents the consensus of the IETF community.  It has
   received public review and has been approved for publication by the
   Internet Engineering Steering Group (IESG).  Not all documents
   approved by the IESG are a candidate for any level of Internet
   Standard; see Section 2 of RFC 5741.

   Information about the current status of this document, any errata,
   and how to provide feedback on it may be obtained at

Page 2 
Copyright Notice

   Copyright (c) 2010 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   ( in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

   This document may contain material from IETF Documents or IETF
   Contributions published or made publicly available before November
   10, 2008.  The person(s) controlling the copyright in some of this
   material may not have granted the IETF Trust the right to allow
   modifications of such material outside the IETF Standards Process.
   Without obtaining an adequate license from the person(s) controlling
   the copyright in such materials, this document may not be modified
   outside the IETF Standards Process, and derivative works of it may
   not be created outside the IETF Standards Process, except to format
   it for publication as an RFC or to translate it into languages other
   than English.

Top       Page 3 
Table of Contents

   1. Introduction ....................................................4
   2. NTP Security Model ..............................................4
   3. Approach ........................................................7
   4. Autokey Cryptography ............................................8
   5. Autokey Protocol Overview ......................................12
   6. NTP Secure Groups ..............................................14
   7. Identity Schemes ...............................................19
   8. Timestamps and Filestamps ......................................20
   9. Autokey Operations .............................................22
   10. Autokey Protocol Messages .....................................23
      10.1. No-Operation .............................................26
      10.2. Association Message (ASSOC) ..............................26
      10.3. Certificate Message (CERT) ...............................26
      10.4. Cookie Message (COOKIE) ..................................27
      10.5. Autokey Message (AUTO) ...................................27
      10.6. Leapseconds Values Message (LEAP) ........................27
      10.7. Sign Message (SIGN) ......................................27
      10.8. Identity Messages (IFF, GQ, MV) ..........................27
   11. Autokey State Machine .........................................28
      11.1. Status Word ..............................................28
      11.2. Host State Variables .....................................30
      11.3. Client State Variables (all modes) .......................33
      11.4. Protocol State Transitions ...............................34
           11.4.1. Server Dance ......................................34
           11.4.2. Broadcast Dance ...................................35
           11.4.3. Symmetric Dance ...................................36
      11.5. Error Recovery ...........................................37
   12. Security Considerations .......................................39
      12.1. Protocol Vulnerability ...................................39
      12.2. Clogging Vulnerability ...................................40
   13. IANA Considerations ...........................................42
   14. References ....................................................42
      14.1. Normative References .....................................42
      14.2. Informative References ...................................43
   Appendix A.  Timestamps, Filestamps, and Partial Ordering .........45
   Appendix B.  Identity Schemes .....................................46
   Appendix C.  Private Certificate (PC) Scheme ......................47
   Appendix D.  Trusted Certificate (TC) Scheme ......................47
   Appendix E.  Schnorr (IFF) Identity Scheme ........................48
   Appendix F.  Guillard-Quisquater (GQ) Identity Scheme .............49
   Appendix G.  Mu-Varadharajan (MV) Identity Scheme .................51
   Appendix H.  ASN.1 Encoding Rules .................................54
   Appendix I.  COOKIE Request, IFF Response, GQ Response, MV
                Response .............................................54
   Appendix J.  Certificates .........................................55

Top      ToC       Page 4 
1.  Introduction

   A distributed network service requires reliable, ubiquitous, and
   survivable provisions to prevent accidental or malicious attacks on
   the servers and clients in the network or the values they exchange.
   Reliability requires that clients can determine that received packets
   are authentic; that is, were actually sent by the intended server and
   not manufactured or modified by an intruder.  Ubiquity requires that
   a client can verify the authenticity of a server using only public
   information.  Survivability requires protection from faulty
   implementations, improper operation, and possibly malicious clogging
   and replay attacks.

   This memo describes a cryptographically sound and efficient
   methodology for use in the Network Time Protocol (NTP) [RFC5905].
   The various key agreement schemes [RFC4306][RFC2412][RFC2522]
   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, e.g., 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 sequence generated by repeated hashes of a cryptographic value
   involving both public and private components.  This scheme has been
   implemented, tested, and deployed in the Internet of today.  A
   detailed description of the security model, design principles, and
   implementation is presented in this memo.

   This informational document describes the NTP extensions for Autokey
   as implemented in an NTPv4 software distribution available from  This description is provided to offer a basis
   for future work and a reference for the software release.  This
   document also describes the motivation for the extensions within the

2.  NTP Security Model

   NTP security requirements are even more stringent than most other
   distributed services.  First, the operation of the authentication
   mechanism and the time synchronization mechanism are inextricably
   intertwined.  Reliable time synchronization requires cryptographic
   keys that are valid only over designated time intervals; but, time
   intervals can be enforced only when participating servers and clients
   are reliably synchronized to UTC.  In addition, the NTP subnet is

Top      ToC       Page 5 
   hierarchical by nature, so time and trust flow from the primary
   servers at the root through secondary servers to the clients at the

   A client can claim authentic to dependent applications only if all
   servers on the path to the primary servers are bona fide authentic.
   In order to emphasize this requirement, in this memo, the notion of
   "authentic" is replaced by "proventic", an adjective 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 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.  An NTP client mobilizes a
   number of concurrent associations with different servers and uses a
   crafted agreement algorithm to pluck truechimers from the population
   possibly including falsetickers.  A particular association is
   proventic if the server certificate and identity have been verified
   by the means described in this 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.

   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) [RFC4303] and Authentication Header (AH)
   [RFC4302] for IPv4 and IPv6.  Cryptographic algorithms that use these
   headers for various purposes include those developed for the PKI,
   including various message digest, digital signature, and key
   agreement algorithms.  This memo takes no position on which message
   digest or digital signature algorithm is used.  This is established
   by a profile for each community of users.

   It will facilitate the discussion in this memo to refer to the
   reference implementation available at  It
   includes Autokey as described in this memo and is available to the
   general public; however, it is not part of the specification itself.
   The cryptographic means used by the reference implementation and its
   user community are based on the OpenSSL cryptographic software
   library available at, but other libraries with
   equivalent functionality could be used as well.  It is important for

Top      ToC       Page 6 
   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.

   The fundamental assumption in NTP about the security model is that
   packets transmitted over the Internet can be intercepted by those
   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 memo is to detect and discard
   spurious packets sent by someone other than the intended sender or
   sent by the intended sender, but modified or replayed by an intruder.

   There are a number of defense mechanisms already built in the NTP
   architecture, protocol, and algorithms.  The on-wire timestamp
   exchange scheme is inherently resistant to 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

   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 the unlikely
       cases considered in Section 12, the modified packet cannot arrive
       at the victim before the original packet, nor does it have the
       server private keys or identity parameters.

Top      ToC       Page 7 
   4.  In a man-in-the-middle 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, the middleman does not have the server private 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 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.  Client security functions must involve only public values
       transmitted over the net.  Private values must never be disclosed
       beyond the machine on which they were created, except in the case
       of a special trusted agent (TA) assigned for this purpose.

   Unlike the Secure Shell (SSH) 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.

3.  Approach

   The Autokey protocol described in this 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 [RFC5905].

Top      ToC       Page 8 
   1.  It must interoperate with the existing NTP architecture model and
       protocol design.  In particular, it must support the symmetric
       key scheme described in [RFC1305].  As a practical matter, the
       reference implementation must use the same internal key
       management system, including the use of 32-bit key IDs and
       existing mechanisms to store, activate, and revoke keys.

   2.  It must provide for the independent collection of cryptographic
       values and time values.  An 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

   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 disorder, or suboptimal configurations.

   5.  It must build on a widely available suite of cryptographic
       algorithms, yet be independent of the particular choice.  In
       particular, it must not require data encryption other than that
       which is incidental to signature and cookie encryption

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

4.  Autokey Cryptography

   Autokey cryptography is based on the PKI algorithms commonly used in
   the Secure Shell and Secure Sockets Layer (SSL) applications.  As in
   these applications, Autokey uses message digests to detect packet
   modification, digital signatures to verify credentials, and public
   certificates to 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.

   Autokey, like many other remote procedure call (RPC) protocols,
   depends on message digests for basic authentication; however, it is
   important to understand that message digests are also used by NTP
   when Autokey is not available or not configured.  Selection of the
   digest algorithm is a function of NTP configuration and is
   transparent to Autokey.

Top      ToC       Page 9 
   The protocol design and reference implementation support both 128-bit
   and 160-bit message digest algorithms, each with a 32-bit key ID.  In
   order to retain backwards 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 Authentication Code |
                     \|/     \|/       +              (MAC)            +
                ********************   | +-------------------------+   |
                *   Compute Hash   *<----| Key ID | Message Digest |   +
                ********************   | +-------------------------+   |
                          |            +-+-+-+-+-+-+-|-+-+-+-+-+-+-+-+-+
                         \|/                        \|/
                +------------------+       +-------------+
                |  Message Digest  |------>|   Compare   |
                +------------------+       +-------------+

                     Figure 1: Message Authentication

   Autokey uses specially contrived session keys, called autokeys, and a
   precomputed pseudo-random sequence of autokeys that are saved in 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

Top      ToC       Page 10 
   An autokey is computed from four fields in network byte order as
   shown in Figure 2.  The four values are hashed using the MD5
   algorithm to produce the 128-bit autokey value, which in the
   reference implementation is stored along with the key ID in a cache
   used for symmetric keys as well as autokeys.  Keys are retrieved from
   the cache by key ID using hash tables and a fast lookup algorithm.

   For use with IPv4, the Src Address and Dst Address fields contain 32
   bits; for use with IPv6, these fields contain 128 bits.  In either
   case, the Key ID and Cookie fields contain 32 bits.  Thus, an IPv4
   autokey has four 32-bit words, while an IPv6 autokey has ten 32-bit
   words.  The source and destination addresses and key ID are public
   values visible in the packet, while the cookie can be a public value
   or shared private value, depending on the 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.  For packets without extension fields, the cookie is a shared
   private value.  For packets with extension fields, the cookie has a
   default public value of zero, since these packets 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 that are visible in the transmitted packet must be the same as
   those used to construct the autokey list and that these fields be the
   same as those visible in the received packet.  (The use of
   alternative means, such as Autokey host names (discussed later) or
   hashes of these names may be a topic for future study.)

Top      ToC       Page 11 
+-----------+-----------+------+------+   +---------+  +-----+------+
|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 3 shows how the autokey list and autokey values are computed.
   The key IDs used in the autokey list consist of a sequence starting
   with a random 32-bit nonce (autokey seed) greater than or equal to
   the pivot as the first key ID.  The first autokey is computed as
   above using the given cookie and autokey seed and assigned index 0.
   The first 32 bits of the result in network byte order become the next
   key ID.  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, 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.

Top      ToC       Page 12 
                   |  NTP Header and  |
                   | Extension Fields |
                        |       |
                       \|/     \|/                     +---------+
                     ****************    +--------+    | Session |
                     * COMPUTE HASH *<---| Key ID |<---| Key ID  |
                     ****************    +--------+    |  List   |
                             |                |        +---------+
                            \|/              \|/
                   | Message Authentication Code (MAC) |

                      Figure 4: Transmitting Messages

   The index of the last autokey in the list is saved along with the key
   ID for that entry, collectively called the autokey values.  The
   autokey values are then 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.  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 expects a server response message with
   data.  Requests and responses are contained 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.
   The following is a list of these messages.

   o  Parameter exchange.  The request includes the client host name and
      status word; the response includes the server host name and status
      word.  The status word specifies the digest/signature scheme to
      use and the identity schemes supported.

Top      ToC       Page 13 
   o  Certificate exchange.  The request includes the subject name of a
      certificate; the response consists of a signed certificate with
      that subject name.  If the issuer name is not the same as the
      subject name, it has been signed by a host one step closer to a
      trusted host, so certificate retrieval continues for the issuer
      name.  If it is trusted and self-signed, the trail concludes at
      the trusted host.  If nontrusted and self-signed, the host
      certificate has not yet been signed, so the trail temporarily
      loops.  Completion of this exchange lights the VAL bit as
      described below.

   o  Identity exchange.  The certificate trail is generally not
      considered sufficient protection against man-in-the-middle attacks
      unless additional protection such as the proof-of-possession
      scheme described in [RFC2875] is available, but this is expensive
      and requires servers to retain state.  Autokey can use one of the
      challenge/response identity schemes described in Appendix B.
      Completion of this exchange lights the IFF bit as described below.

   o  Cookie exchange.  The request includes the public key of the
      server.  The response includes the server cookie encrypted with
      this key.  The client uses this value when constructing the key
      list.  Completion of this exchange lights the COOK bit as
      described below.

   o  Autokey exchange.  The request includes either no data or the
      autokey values in symmetric modes.  The response includes the
      autokey values of the server.  These values are used to verify the
      autokey sequence.  Completion of this exchange lights the AUT bit
      as described below.

   o  Sign exchange.  This exchange is executed only when the client has
      synchronized to a proventic source.  The request includes the
      self-signed client certificate.  The server acting as
      certification authority (CA) interprets the certificate as a
      X.509v3 certificate request.  It extracts the subject, issuer, and
      extension fields, builds a new certificate with these data along
      with its own serial number and expiration time, then signs it
      using its own private key and includes it in the response.  The
      client uses the signed certificate in its own role as server for
      dependent clients.  Completion of this exchange lights the SIGN
      bit as described below.

   o  Leapseconds exchange.  This exchange is executed only when the
      client has synchronized to a proventic source.  This exchange
      occurs when the server has the leapseconds values, as indicated in
      the host status word.  If so, the client requests the values and
      compares them with its own values, if available.  If the server

Top      ToC       Page 14 
      values 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 lights the LPT bit as
      described below.

   Once the certificates and identity have been validated, subsequent
   packets are validated by digital signatures and the autokey sequence.
   The association is now proventic with respect to the downstratum
   trusted host, but is not yet selectable to discipline the system
   clock.  The associations accumulate time values, and the mitigation
   algorithms continue in the usual way.  When these algorithms have
   culled the falsetickers and cluster outliers and at least three
   survivors remain, the system clock has been synchronized to a
   proventic source.

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

6.  NTP Secure Groups

   NTP secure groups are used to define cryptographic compartments and
   security hierarchies.  A 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 THs do not have to be, but
   often are, primary (stratum 1) servers.  A trusted authority (TA),
   not necessarily a group host, generates private identity keys for
   servers and public identity keys for clients at the leaves of the
   forest.  The TA deploys the server keys to the THs and other
   designated servers using secure means and posts the client keys on a
   public web site.

   For Autokey purposes, all hosts belonging to a secure group have the
   same group 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 use of the Autokey protocol, a client requests that the
   server sign its certificate and caches the result.  A certificate

Top      ToC       Page 15 
   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
   certificates 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, THs for groups RED and GREEN can be
   cryptographically distinct, but both be clients of group BLUE
   operating at a lower stratum.  In another scenario, THs for group
   CYAN can be clients 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 group keys have been
   previously installed on Brenda and Denise and the client group keys
   installed on all machines.

Top      ToC       Page 16 
                     +-------------+ +-------------+ +-------------+
                     | Alice Group | |    Brenda   | |    Denise   |
                     |    Alice    | |             | |             |
                     | +-+-+-+-+   | | +-+-+-+-+   | | +-+-+-+-+   |
   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     | Alice Group | | +-+-+-+-+   | | +-+-+-+-+   |
   +=========+       |     Carol   | |             | |             |
                     | +-+-+-+-+   | | +-+-+-+-+   | | +-+-+-+-+   |
    S = step         | | Carol |   | | | Brenda|   | | | Denise|   |
    * = trusted      | +-+-+-+-+   | | +-+-+-+-+   | | +-+-+-+-+   |
                     | | Carol*| 1 | | | Brenda| 1 | | | Denise| 1 |
                     | +-+-+-+-+   | | +-+-+-+-+   | | +-+-+-+-+   |
                     |             | |             | |             |
                     | +=======+   | | +=======+   | | +=======+   |
                     | ||Alice|| 3 | | ||Alice|| 3 | | ||Alice|| 3 |
                     | +=======+   | | +=======+   | | +=======+   |
                     +-------------+ +-------------+ +-------------+
                        Stratum 1                Stratum 2

Top      ToC       Page 17 
                     |                  Eileen                     |
                     |                                             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Eileen|   | Eileen|             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Brenda| 4 | Carol | 4           |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |                                             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Alice |   | Carol |             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Alice*| 2 | Carol*| 2           |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |                                             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Brenda|   | Denise|             |
                     |           +-+-+-+-+   +-+-+-+-+             |
                     |           | Alice | 2 | 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.  The girls start by loading the host key, sign key, self-signed
       certificate, and group key.  Each client and server acting as a
       client starts the Autokey protocol by retrieving the server host
       name and digest/signature.  This is done using the ASSOC exchange
       described later.

   2.  They continue to load certificates recursively until a self-
       signed trusted certificate is found.  Brenda and Denise
       immediately find trusted certificates for Alice and Carol,

Top      ToC       Page 18 
       respectively, but Eileen will loop because neither Brenda nor
       Denise have their own certificates signed by either Alice or
       Carol.  This is done using the CERT exchange described later.

   3.  Brenda and Denise continue with the selected identity schemes to
       verify that Alice and Carol have the correct group key previously
       generated by Alice.  This is done using one of the identity
       schemes IFF, GQ, or MV, described later.  If this succeeds, each
       continues in step 4.

   4.  Brenda and Denise present their certificates for signature using
       the SIGN exchange described later.  If this succeeds, either one
       of or both Brenda and Denise can now provide these signed
       certificates to Eileen, which may be looping in step 2.  Eileen
       can now 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 did.

   For various reasons, it may be convenient for a server to have client
   keys for more than one group.  For example, Figure 6 shows three
   secure groups Alice, Helen, and Carol arranged in a hierarchy.  Hosts
   A, B, C, and D belong to Alice with A and B as her THs.  Hosts R and
   S belong to Helen with R as her TH.  Hosts X and Y belong to Carol
   with X as her TH.  Note that the TH for a group is always the lowest
   stratum and that the hosts of the combined groups form an acyclic
   graph.  Note also that the certificate trail for each group
   terminates on a TH for that group.

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

                 Figure 6: Hierarchical Overlapping Groups

Top      ToC       Page 19 
   The intent of the scenario is to provide security separation, so that
   servers cannot masquerade as clients in other groups and clients
   cannot masquerade as servers.  Assume, for example, that Alice and
   Helen belong to national standards laboratories and their server keys
   are used to confirm identity between members of each group.  Carol is
   a prominent corporation receiving standards products and requiring
   cryptographic authentication.  Perhaps under contract, host X
   belonging to Carol has client keys for both Alice and Helen and
   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.

(page 19 continued on part 2)

Next RFC Part