draft-ietf-ntp-autokey-08.txt   rfc5906.txt 
Network Working Group B. Haberman, Ed. Internet Engineering Task Force (IETF) B. Haberman, Ed.
Internet-Draft JHU/APL Request for Comments: 5906 JHU/APL
Intended status: Informational D. Mills Category: Informational D. Mills
Expires: September 6, 2010 U. Delaware ISSN: 2070-1721 U. Delaware
March 5, 2010 June 2010
Network Time Protocol Version 4 Autokey Specification Network Time Protocol Version 4: Autokey Specification
draft-ietf-ntp-autokey-08
Abstract Abstract
This memo describes the Autokey security model for authenticating This memo describes the Autokey security model for authenticating
servers to clients using the Network Time Protocol (NTP) and public servers to clients using the Network Time Protocol (NTP) and public
key cryptography. Its design is based on the premise that IPsec key cryptography. Its design is based on the premise that IPsec
schemes cannot be adopted intact, since that would preclude stateless schemes cannot be adopted intact, since that would preclude stateless
servers and severely compromise timekeeping accuracy. In addition, servers and severely compromise timekeeping accuracy. In addition,
PKI schemes presume authenticated time values are always available to Public Key Infrastructure (PKI) schemes presume authenticated time
enforce certificate lifetimes; however, cryptographically verified values are always available to enforce certificate lifetimes;
timestamps require interaction between the timekeeping and however, cryptographically verified timestamps require interaction
authentication functions. between the timekeeping and authentication functions.
This memo includes the Autokey requirements analysis, design This memo includes the Autokey requirements analysis, design
principles and protocol specification. A detailed description of the principles, and protocol specification. A detailed description of
protocol states, events and transition functions is included. A the protocol states, events, and transition functions is included. A
prototype of the Autokey design based on this memo has been prototype of the Autokey design based on this memo has been
implemented, tested and documented in the NTP Version 4 (NTPv4) implemented, tested, and documented in the NTP version 4 (NTPv4)
software distribution for Unix, Windows and VMS at software distribution for the Unix, Windows, and Virtual Memory
http://www.ntp.org. System (VMS) operating systems at http://www.ntp.org.
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and 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 Status of This Memo
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 This document is not an Internet Standards Track specification; it is
http://www.ietf.org/ietf/1id-abstracts.txt. published for informational purposes.
The list of Internet-Draft Shadow Directories can be accessed at This document is a product of the Internet Engineering Task Force
http://www.ietf.org/shadow.html. (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.
This Internet-Draft will expire on September 6, 2010. Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
http://www.rfc-editor.org/info/rfc5906.
Copyright Notice Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the BSD License. described in the Simplified BSD License.
This document may contain material from IETF Documents or IETF This document may contain material from IETF Documents or IETF
Contributions published or made publicly available before November Contributions published or made publicly available before November
10, 2008. The person(s) controlling the copyright in some of this 10, 2008. The person(s) controlling the copyright in some of this
material may not have granted the IETF Trust the right to allow material may not have granted the IETF Trust the right to allow
modifications of such material outside the IETF Standards Process. modifications of such material outside the IETF Standards Process.
Without obtaining an adequate license from the person(s) controlling Without obtaining an adequate license from the person(s) controlling
the copyright in such materials, this document may not be modified the copyright in such materials, this document may not be modified
outside the IETF Standards Process, and derivative works of it may outside the IETF Standards Process, and derivative works of it may
not be created outside the IETF Standards Process, except to format not be created outside the IETF Standards Process, except to format
it for publication as an RFC or to translate it into languages other it for publication as an RFC or to translate it into languages other
than English. than English.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Introduction ....................................................4
2. NTP Security Model . . . . . . . . . . . . . . . . . . . . . . 4 2. NTP Security Model ..............................................4
3. Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3. Approach ........................................................7
4. Autokey Cryptography . . . . . . . . . . . . . . . . . . . . . 8 4. Autokey Cryptography ............................................8
5. Autokey Protocol Overview . . . . . . . . . . . . . . . . . . 12 5. Autokey Protocol Overview ......................................12
6. NTP Secure Groups . . . . . . . . . . . . . . . . . . . . . . 14 6. NTP Secure Groups ..............................................14
7. Identity Schemes . . . . . . . . . . . . . . . . . . . . . . . 18 7. Identity Schemes ...............................................19
8. Timestamps and Filestamps . . . . . . . . . . . . . . . . . . 20 8. Timestamps and Filestamps ......................................20
9. Autokey Operations . . . . . . . . . . . . . . . . . . . . . . 21 9. Autokey Operations .............................................22
10. Autokey Protocol Messages . . . . . . . . . . . . . . . . . . 23 10. Autokey Protocol Messages .....................................23
10.1. No-Operation . . . . . . . . . . . . . . . . . . . . . . 26 10.1. No-Operation .............................................26
10.2. Association Message (ASSOC) . . . . . . . . . . . . . . . 26 10.2. Association Message (ASSOC) ..............................26
10.3. Certificate Message (CERT) . . . . . . . . . . . . . . . 26 10.3. Certificate Message (CERT) ...............................26
10.4. Cookie Message (COOKIE) . . . . . . . . . . . . . . . . . 26 10.4. Cookie Message (COOKIE) ..................................27
10.5. Autokey Message (AUTO) . . . . . . . . . . . . . . . . . 26 10.5. Autokey Message (AUTO) ...................................27
10.6. Leapseconds Values Message (LEAP) . . . . . . . . . . . . 27 10.6. Leapseconds Values Message (LEAP) ........................27
10.7. Sign Message (SIGN) . . . . . . . . . . . . . . . . . . . 27 10.7. Sign Message (SIGN) ......................................27
10.8. Identity Messages (IFF, GQ, MV) . . . . . . . . . . . . . 27 10.8. Identity Messages (IFF, GQ, MV) ..........................27
11. Autokey State Machine . . . . . . . . . . . . . . . . . . . . 27 11. Autokey State Machine .........................................28
11.1. Status Word . . . . . . . . . . . . . . . . . . . . . . . 27 11.1. Status Word ..............................................28
11.2. Host State Variables . . . . . . . . . . . . . . . . . . 30 11.2. Host State Variables .....................................30
11.3. Client State Variables (all modes) . . . . . . . . . . . 32 11.3. Client State Variables (all modes) .......................33
11.4. Protocol State Transitions . . . . . . . . . . . . . . . 32 11.4. Protocol State Transitions ...............................34
11.4.1. Server Dance . . . . . . . . . . . . . . . . . . . . 33 11.4.1. Server Dance ......................................34
11.4.2. Broadcast Dance . . . . . . . . . . . . . . . . . . . 33 11.4.2. Broadcast Dance ...................................35
11.4.3. Symmetric Dance . . . . . . . . . . . . . . . . . . . 35 11.4.3. Symmetric Dance ...................................36
11.5. Error Recovery . . . . . . . . . . . . . . . . . . . . . 36 11.5. Error Recovery ...........................................37
12. Security Considerations . . . . . . . . . . . . . . . . . . . 37 12. Security Considerations .......................................39
12.1. Protocol Vulnerability . . . . . . . . . . . . . . . . . 37 12.1. Protocol Vulnerability ...................................39
12.2. Clogging Vulnerability . . . . . . . . . . . . . . . . . 38 12.2. Clogging Vulnerability ...................................40
13. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 39 13. IANA Considerations ...........................................42
14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 39 13. References ....................................................42
14.1. Normative References . . . . . . . . . . . . . . . . . . 39 13.1. Normative References .....................................42
14.2. Informative References . . . . . . . . . . . . . . . . . 39 13.2. Informative References ...................................43
Appendix A. Timestamps, Filestamps and Partial Ordering . . . . . 41 Appendix A. Timestamps, Filestamps, and Partial Ordering .........45
Appendix B. Identity Schemes . . . . . . . . . . . . . . . . . . 42 Appendix B. Identity Schemes .....................................46
Appendix C. Private Certificate (PC) Scheme . . . . . . . . . . . 42 Appendix C. Private Certificate (PC) Scheme ......................47
Appendix D. Trusted Certificate (TC) Scheme . . . . . . . . . . . 43 Appendix D. Trusted Certificate (TC) Scheme ......................47
Appendix E. Schnorr (IFF) Identity Scheme . . . . . . . . . . . . 44 Appendix E. Schnorr (IFF) Identity Scheme ........................48
Appendix F. Guillard-Quisquater (GQ) Identity Scheme . . . . . . 45 Appendix F. Guillard-Quisquater (GQ) Identity Scheme .............49
Appendix G. Mu-Varadharajan (MV) Identity Scheme . . . . . . . . 47 Appendix G. Mu-Varadharajan (MV) Identity Scheme .................51
Appendix H. ASN.1 Encoding Rules . . . . . . . . . . . . . . . . 50 Appendix H. ASN.1 Encoding Rules .................................54
Appendix I. COOKIE request, IFF response, GQ response, MV Appendix I. COOKIE Request, IFF Response, GQ Response, MV
response . . . . . . . . . . . . . . . . . . . . . . 50 Response .............................................54
Appendix J. Certificates . . . . . . . . . . . . . . . . . . . . 51 Appendix J. Certificates .........................................55
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 53
1. Introduction 1. Introduction
A distributed network service requires reliable, ubiquitous and A distributed network service requires reliable, ubiquitous, and
survivable provisions to prevent accidental or malicious attacks on survivable provisions to prevent accidental or malicious attacks on
the servers and clients in the network or the values they exchange. the servers and clients in the network or the values they exchange.
Reliability requires that clients can determine that received packets Reliability requires that clients can determine that received packets
are authentic; that is, were actually sent by the intended server and are authentic; that is, were actually sent by the intended server and
not manufactured or modified by an intruder. Ubiquity requires that not manufactured or modified by an intruder. Ubiquity requires that
a client can verify the authenticity of a server using only public a client can verify the authenticity of a server using only public
information. Survivability requires protection from faulty information. Survivability requires protection from faulty
implementations, improper operation and possibly malicious clogging implementations, improper operation, and possibly malicious clogging
and replay attacks. and replay attacks.
This memo describes a cryptographically sound and efficient This memo describes a cryptographically sound and efficient
methodology for use in the Network Time Protocol (NTP) methodology for use in the Network Time Protocol (NTP) [RFC5905].
[I-D.ietf-ntp-ntpv4-proto]. The various key agreement schemes The various key agreement schemes [RFC4306][RFC2412][RFC2522]
[RFC2408][RFC2412][RFC2522] proposed require per-association state proposed require per-association state variables, which contradicts
variables, which contradicts the principles of the remote procedure the principles of the remote procedure call (RPC) paradigm in which
call (RPC) paradigm in which servers keep no state for a possibly servers keep no state for a possibly large client population. An
large client population. An evaluation of the PKI model and evaluation of the PKI model and algorithms, e.g., as implemented in
algorithms, e.g., as implemented in the OpenSSL library, leads to the the OpenSSL library, leads to the conclusion that any scheme
conclusion that any scheme requiring every NTP packet to carry a PKI requiring every NTP packet to carry a PKI digital signature would
digital signature would result in unacceptably poor timekeeping result in unacceptably poor timekeeping performance.
performance.
The Autokey protocol is based on a combination of PKI and a pseudo- The Autokey protocol is based on a combination of PKI and a pseudo-
random sequence generated by repeated hashes of a cryptographic value random sequence generated by repeated hashes of a cryptographic value
involving both public and private components. This scheme has been involving both public and private components. This scheme has been
implemented, tested and deployed in the Internet of today. A implemented, tested, and deployed in the Internet of today. A
detailed description of the security model, design principles and detailed description of the security model, design principles, and
implementation is presented in this memo. implementation is presented in this memo.
This informational document describes the NTP extensions for Autokey This informational document describes the NTP extensions for Autokey
as implemented in an NTPv4 software distribution available from as implemented in an NTPv4 software distribution available from
http://www.ntp.org. This description is provided to offer a basis http://www.ntp.org. This description is provided to offer a basis
for future work and a reference for the software release. This for future work and a reference for the software release. This
document also describes the motivation for the extensions within the document also describes the motivation for the extensions within the
protocol. protocol.
2. NTP Security Model 2. NTP Security Model
NTP security requirements are even more stringent than most other NTP security requirements are even more stringent than most other
distributed services. First, the operation of the authentication distributed services. First, the operation of the authentication
mechanism and the time synchronization mechanism are inextricably mechanism and the time synchronization mechanism are inextricably
intertwined. Reliable time synchronization requires cryptographic intertwined. Reliable time synchronization requires cryptographic
keys which are valid only over a designated time intervals; but, time keys that are valid only over designated time intervals; but, time
intervals can be enforced only when participating servers and clients intervals can be enforced only when participating servers and clients
are reliably synchronized to UTC. In addition, the NTP subnet is are reliably synchronized to UTC. In addition, the NTP subnet is
hierarchical by nature, so time and trust flow from the primary hierarchical by nature, so time and trust flow from the primary
servers at the root through secondary servers to the clients at the servers at the root through secondary servers to the clients at the
leaves. leaves.
A client can claim authentic to dependent applications only if all A client can claim authentic to dependent applications only if all
servers on the path to the primary servers are bone-fide authentic. servers on the path to the primary servers are bona fide authentic.
In order to emphasize this requirement, in this memo the notion of In order to emphasize this requirement, in this memo, the notion of
"authentic" is replaced by "proventic", a noun new to English and "authentic" is replaced by "proventic", an adjective new to English
derived from provenance, as in the provenance of a painting. Having and derived from "provenance", as in the provenance of a painting.
abused the language this far, the suffixes fixable to the various Having abused the language this far, the suffixes fixable to the
derivatives of authentic will be adopted for proventic as well. In various derivatives of authentic will be adopted for proventic as
NTP each server authenticates the next lower stratum servers and well. In NTP, each server authenticates the next-lower stratum
proventicates (authenticates by induction) the lowest stratum servers and proventicates (authenticates by induction) the lowest
(primary) servers. Serious computer linguists would correctly stratum (primary) servers. Serious computer linguists would
interpret the proventic relation as the transitive closure of the correctly interpret the proventic relation as the transitive closure
authentic relation. of the authentic relation.
It is important to note that the notion of proventic does not It is important to note that the notion of proventic does not
necessarily imply the time is correct. A NTP client mobilizes a necessarily imply the time is correct. An NTP client mobilizes a
number of concurrent associations with different servers and uses a number of concurrent associations with different servers and uses a
crafted agreement algorithm to pluck truechimers from the population crafted agreement algorithm to pluck truechimers from the population
possibly including falsetickers. A particular association is possibly including falsetickers. A particular association is
proventic if the server certificate and identity have been verified proventic if the server certificate and identity have been verified
by the means described in this memo. However, the statement "the by the means described in this memo. However, the statement "the
client is synchronized to proventic sources" means that the system client is synchronized to proventic sources" means that the system
clock has been set using the time values of one or more proventic clock has been set using the time values of one or more proventic
associations and according to the NTP mitigation algorithms. associations and according to the NTP mitigation algorithms.
Over the last several years the IETF has defined and evolved the Over the last several years, the IETF has defined and evolved the
IPsec infrastructure for privacy protection and source authentication IPsec infrastructure for privacy protection and source authentication
in the Internet. The infrastructure includes the Encapsulating in the Internet. The infrastructure includes the Encapsulating
Security Payload (ESP) [RFC2406] and Authentication Header (AH) Security Payload (ESP) [RFC4303] and Authentication Header (AH)
[RFC2402] for IPv4 and IPv6. Cryptographic algorithms that use these [RFC4302] for IPv4 and IPv6. Cryptographic algorithms that use these
headers for various purposes include those developed for the PKI, headers for various purposes include those developed for the PKI,
including various message digest, digital signature and key agreement including various message digest, digital signature, and key
algorithms. This memo takes no position on which message digest or agreement algorithms. This memo takes no position on which message
which digital signature algorithm is used. This is established by a digest or digital signature algorithm is used. This is established
profile for each community of users. by a profile for each community of users.
It will facilitate the discussion in this memo to refer to the It will facilitate the discussion in this memo to refer to the
reference implementation available at http://www.ntp.org. It reference implementation available at http://www.ntp.org. It
includes Autokey as described in this memo and is available to the includes Autokey as described in this memo and is available to the
general public; however, it is not part of the specification itself. general public; however, it is not part of the specification itself.
The cryptographic means used by the reference implementation and its The cryptographic means used by the reference implementation and its
user community are based on the OpenSSL cryptographic software user community are based on the OpenSSL cryptographic software
library available at http://www.openssl.org, but other libraries with library available at http://www.openssl.org, but other libraries with
equivalent functionality could be used as well. It is important for equivalent functionality could be used as well. It is important for
distribution and export purposes that the way in which these distribution and export purposes that the way in which these
algorithms are used precludes encryption of any data other than algorithms are used precludes encryption of any data other than
incidental to the construction of digital signatures. incidental to the construction of digital signatures.
The fundamental assumption in NTP the security model is that packets The fundamental assumption in NTP about the security model is that
transmitted over the Internet can be intercepted by other than the packets transmitted over the Internet can be intercepted by those
intended recipient, remanufactured in various ways and replayed in other than the intended recipient, remanufactured in various ways,
whole or part. These packets can cause the client to believe or and replayed in whole or part. These packets can cause the client to
produce incorrect information, cause protocol operations to fail, believe or produce incorrect information, cause protocol operations
interrupt network service or consume precious network and processor to fail, interrupt network service, or consume precious network and
resources. processor resources.
In the case of NTP, the assumed goal of the intruder is to inject 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 false time values, disrupt the protocol or clog the network, servers,
or clients with spurious packets that exhaust resources and deny or clients with spurious packets that exhaust resources and deny
service to legitimate applications. The mission of the algorithms service to legitimate applications. The mission of the algorithms
and protocols described in this memo is to detect and discard and protocols described in this memo is to detect and discard
spurious packets sent by other than the intended sender or sent by spurious packets sent by someone other than the intended sender or
the intended sender, but modified or replayed by an intruder. sent by the intended sender, but modified or replayed by an intruder.
There are a number of defense mechanisms already built in the NTP There are a number of defense mechanisms already built in the NTP
architecture, protocol and algorithms. The on-wire timestamp architecture, protocol, and algorithms. The on-wire timestamp
exchange scheme is inherently resistant to spoofing, packet loss and exchange scheme is inherently resistant to spoofing, packet-loss, and
replay attacks. The engineered clock filter, selection and replay attacks. The engineered clock filter, selection, and
clustering algorithms are designed to defend against evil cliques of clustering algorithms are designed to defend against evil cliques of
Byzantine traitors. While not necessarily designed to defeat Byzantine traitors. While not necessarily designed to defeat
determined intruders, these algorithms and accompanying sanity checks determined intruders, these algorithms and accompanying sanity checks
have functioned well over the years to deflect improperly operating have functioned well over the years to deflect improperly operating
but presumably friendly scenarios. However, these mechanisms do not but presumably friendly scenarios. However, these mechanisms do not
securely identify and authenticate servers to clients. Without securely identify and authenticate servers to clients. Without
specific further protection, an intruder can inject any or all of the specific further protection, an intruder can inject any or all of the
following attacks. following attacks.
1. An intruder can intercept and archive packets forever, as well as 1. An intruder can intercept and archive packets forever, as well as
all the public values ever generated and transmitted over the all the public values ever generated and transmitted over the
net. net.
2. An intruder can generate packets faster than the server, network 2. An intruder can generate packets faster than the server, network,
or client can process them, especially if they require expensive or client can process them, especially if they require expensive
cryptographic computations. cryptographic computations.
3. In a wiretap attack the intruder can intercept, modify and replay 3. In a wiretap attack, the intruder can intercept, modify, and
a packet. However, it cannot permanently prevent onward replay a packet. However, it cannot permanently prevent onward
transmission of the original packet; that is, it cannot break the transmission of the original packet; that is, it cannot break the
wire, only tell lies and congest it. Except in unlikely cases wire, only tell lies and congest it. Except in the unlikely
considered in Section 12, the modified packet cannot arrive at cases considered in Section 12, the modified packet cannot arrive
the victim before the original packet, nor does it have the at the victim before the original packet, nor does it have the
server private keys or identity parameters. server private keys or identity parameters.
4. In a man-in-the-middle or masquerade attack the intruder is 4. In a man-in-the-middle or masquerade attack, the intruder is
positioned between the server and client, so it can intercept, positioned between the server and client, so it can intercept,
modify and replay a packet and prevent onward transmission of the modify, and replay a packet and prevent onward transmission of
original packet. Except in unlikely cases considered in the original packet. Except in unlikely cases considered in
Section 12, the middleman does not have the server private keys. Section 12, the middleman does not have the server private keys.
The NTP security model assumes the following possible limitations. The NTP security model assumes the following possible limitations.
1. The running times for public key algorithms are relatively long 1. The running times for public key algorithms are relatively long
and highly variable. In general, the performance of the time and highly variable. In general, the performance of the time
synchronization function is badly degraded if these algorithms synchronization function is badly degraded if these algorithms
must be used for every NTP packet. must be used for every NTP packet.
2. In some modes of operation it is not feasible for a server to 2. In some modes of operation, it is not feasible for a server to
retain state variables for every client. It is however feasible retain state variables for every client. It is however feasible
to regenerated them for a client upon arrival of a packet from to regenerated them for a client upon arrival of a packet from
that client. that client.
3. The lifetime of cryptographic values must be enforced, which 3. The lifetime of cryptographic values must be enforced, which
requires a reliable system clock. However, the sources that requires a reliable system clock. However, the sources that
synchronize the system clock must be cryptographically synchronize the system clock must be cryptographically
proventicated. This circular interdependence of the timekeeping proventicated. This circular interdependence of the timekeeping
and proventication functions requires special handling. and proventication functions requires special handling.
4. Client security functions must involve only public values 4. Client security functions must involve only public values
transmitted over the net. Private values must never be disclosed transmitted over the net. Private values must never be disclosed
beyond the machine on which they were created, except in the case beyond the machine on which they were created, except in the case
of a special trusted agent (TA) assigned for this purpose. of a special trusted agent (TA) assigned for this purpose.
Unlike the Secure Shell security model, where the client must be Unlike the Secure Shell (SSH) security model, where the client must
securely authenticated to the server, in NTP the server must be be securely authenticated to the server, in NTP, the server must be
securely authenticated to the client. In ssh each different securely authenticated to the client. In SSH, each different
interface address can be bound to a different name, as returned by a interface address can be bound to a different name, as returned by a
reverse-DNS query. In this design separate public/private key pairs reverse-DNS query. In this design, separate public/private key pairs
may be required for each interface address with a distinct name. A may be required for each interface address with a distinct name. A
perceived advantage of this design is that the security compartment perceived advantage of this design is that the security compartment
can be different for each interface. This allows a firewall, for can be different for each interface. This allows a firewall, for
instance, to require some interfaces to authenticate the client and instance, to require some interfaces to authenticate the client and
others not. others not.
3. Approach 3. Approach
The Autokey protocol described in this memo is designed to meet the The Autokey protocol described in this memo is designed to meet the
following objectives. In-depth discussions on these objectives is in following objectives. In-depth discussions on these objectives is in
the web briefings and will not be elaborated in this memo. Note that the web briefings and will not be elaborated in this memo. Note that
here and elsewhere in this memo mention of broadcast mode means here, and elsewhere in this memo, mention of broadcast mode means
multicast mode as well, with exceptions as noted in the NTP software multicast mode as well, with exceptions as noted in the NTP software
documentation. documentation [RFC5905].
1. It must interoperate with the existing NTP architecture model and 1. It must interoperate with the existing NTP architecture model and
protocol design. In particular, it must support the symmetric protocol design. In particular, it must support the symmetric
key scheme described in [RFC1305]. As a practical matter, the key scheme described in [RFC1305]. As a practical matter, the
reference implementation must use the same internal key reference implementation must use the same internal key
management system, including the use of 32-bit key IDs and management system, including the use of 32-bit key IDs and
existing mechanisms to store, activate and revoke keys. existing mechanisms to store, activate, and revoke keys.
2. It must provide for the independent collection of cryptographic 2. It must provide for the independent collection of cryptographic
values and time values. A NTP packet is accepted for processing values and time values. An NTP packet is accepted for processing
only when the required cryptographic values have been obtained only when the required cryptographic values have been obtained
and verified and the packet has passed all header sanity checks. and verified and the packet has passed all header sanity checks.
3. It must not significantly degrade the potential accuracy of the 3. It must not significantly degrade the potential accuracy of the
NTP synchronization algorithms. In particular, it must not make NTP synchronization algorithms. In particular, it must not make
unreasonable demands on the network or host processor and memory unreasonable demands on the network or host processor and memory
resources. resources.
4. It must be resistant to cryptographic attacks, specifically those 4. It must be resistant to cryptographic attacks, specifically those
identified in the security model above. In particular, it must identified in the security model above. In particular, it must
be tolerant of operational or implementation variances, such as be tolerant of operational or implementation variances, such as
packet loss or disorder, or suboptimal configurations. packet loss or disorder, or suboptimal configurations.
5. It must build on a widely available suite of cryptographic 5. It must build on a widely available suite of cryptographic
algorithms, yet be independent of the particular choice. In algorithms, yet be independent of the particular choice. In
particular, it must not require data encryption other than particular, it must not require data encryption other than that
incidental to signature and cookie encryption operations. which is incidental to signature and cookie encryption
operations.
6. It must function in all the modes supported by NTP, including 6. It must function in all the modes supported by NTP, including
server, symmetric and broadcast modes. server, symmetric, and broadcast modes.
4. Autokey Cryptography 4. Autokey Cryptography
Autokey cryptography is based on the PKI algorithms commonly used in Autokey cryptography is based on the PKI algorithms commonly used in
the Secure Shell and Secure Sockets Layer applications. As in these the Secure Shell and Secure Sockets Layer (SSL) applications. As in
applications Autokey uses message digests to detect packet these applications, Autokey uses message digests to detect packet
modification, digital signatures to verify credentials and public modification, digital signatures to verify credentials, and public
certificates to provide traceable authority. What makes Autokey certificates to provide traceable authority. What makes Autokey
cryptography unique is the way in which these algorithms are used to cryptography unique is the way in which these algorithms are used to
deflect intruder attacks while maintaining the integrity and accuracy deflect intruder attacks while maintaining the integrity and accuracy
of the time synchronization function. of the time synchronization function.
Autokey, like many other remote procedure call (RPC) protocols, Autokey, like many other remote procedure call (RPC) protocols,
depends on message digests for basic authentication; however, it is depends on message digests for basic authentication; however, it is
important to understand that message digests are also used by NTP important to understand that message digests are also used by NTP
when Autokey is not available or not configured. Selection of the when Autokey is not available or not configured. Selection of the
digest algorithm is a function of NTP configuration and is digest algorithm is a function of NTP configuration and is
transparent to Autokey. transparent to Autokey.
The protocol design and reference implementation support both 128-bit The protocol design and reference implementation support both 128-bit
and 160-bit message digest algorithms, each with a 32-bit key ID. In and 160-bit message digest algorithms, each with a 32-bit key ID. In
order to retain backward compatibility with NTPv3, the NTPv4 key ID order to retain backwards compatibility with NTPv3, the NTPv4 key ID
space is partitioned in two subspaces at a pivot point of 65536. space is partitioned in two subspaces at a pivot point of 65536.
Symmetric key IDs have values less than the pivot and indefinite Symmetric key IDs have values less than the pivot and indefinite
lifetime. Autokey key IDs have pseudo-random values equal to or lifetime. Autokey key IDs have pseudo-random values equal to or
greater than the pivot and are expunged immediately after use. greater than the pivot and are expunged immediately after use.
Both symmetric key and public key cryptography authenticate as shown Both symmetric key and public key cryptography authenticate as shown
in Figure 1. The server looks up the key associated with the key ID 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 and calculates the message digest from the NTP header and extension
fields together with the key value. The key ID and digest form the fields together with the key value. The key ID and digest form the
message authentication code (MAC) included with the message. The message authentication code (MAC) included with the message. The
client does the same computation using its local copy of the key and 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, compares the result with the digest in the MAC. If the values agree,
the message is assumed authentic. the message is assumed authentic.
+------------------+ +------------------+
| NTP Header and | | NTP Header and |
| Extension Fields | | Extension Fields |
+------------------+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +------------------+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | Message Authenticator Code | | | | Message Authentication Code |
\|/ \|/ + (MAC) + \|/ \|/ + (MAC) +
******************** | +-------------------------+ | ******************** | +-------------------------+ |
* Compute Hash *<----| Key ID | Message Digest | + * Compute Hash *<----| Key ID | Message Digest | +
******************** | +-------------------------+ | ******************** | +-------------------------+ |
| +-+-+-+-+-+-+-|-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-|-+-+-+-+-+-+-+-+-+
\|/ \|/ \|/ \|/
+------------------+ +-------------+ +------------------+ +-------------+
| Message Digest |------>| Compare | | Message Digest |------>| Compare |
+------------------+ +-------------+ +------------------+ +-------------+
Figure 1: Message Authentication Figure 1: Message Authentication
Autokey uses specially contrived session keys, called autokeys, and a Autokey uses specially contrived session keys, called autokeys, and a
precomputed pseudo-random sequence of autokeys which are saved in the precomputed pseudo-random sequence of autokeys that are saved in the
autokey list. The Autokey protocol operates separately for each autokey list. The Autokey protocol operates separately for each
association, so there may be several autokey sequences operating association, so there may be several autokey sequences operating
independently at the same time. independently at the same time.
+-------------+-------------+--------+--------+ +-------------+-------------+--------+--------+
| Src Address | Dst Address | Key ID | Cookie | | Src Address | Dst Address | Key ID | Cookie |
+-------------+-------------+--------+--------+ +-------------+-------------+--------+--------+
Figure 2: NTPv4 Autokey Figure 2: NTPv4 Autokey
An autokey is computed from four fields in network byte order as An autokey is computed from four fields in network byte order as
shown in Figure 2. The four values are hashed using the MD5 shown in Figure 2. The four values are hashed using the MD5
algorithm to produce the 128-bit autokey value, which in the algorithm to produce the 128-bit autokey value, which in the
reference implementation is stored along with the key ID in a cache reference implementation is stored along with the key ID in a cache
used for symmetric keys as well as autokeys. Keys are retrieved from 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. 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 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 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 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 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 words. The source and destination addresses and key ID are public
values visible in the packet, while the cookie can be a public value values visible in the packet, while the cookie can be a public value
or shared private value, depending on the NTP mode. or shared private value, depending on the NTP mode.
The NTP packet format has been augmented to include one or more The NTP packet format has been augmented to include one or more
extension fields piggybacked between the original NTP header and the extension fields piggybacked between the original NTP header and the
MAC. For packets without extension fields, the cookie is a shared MAC. For packets without extension fields, the cookie is a shared
private value. For packets with extension fields, the cookie has a private value. For packets with extension fields, the cookie has a
default public value of zero, since these packets are validated default public value of zero, since these packets are validated
independently using digital signatures. independently using digital signatures.
There are some scenarios where the use of endpoint IP addresses may There are some scenarios where the use of endpoint IP addresses may
be difficult or impossible. These include configurations where be difficult or impossible. These include configurations where
network address translation (NAT) devices are in use or when network address translation (NAT) devices are in use or when
addresses are changed during an association lifetime due to mobility addresses are changed during an association lifetime due to mobility
constraints. For Autokey, the only restriction is that the address constraints. For Autokey, the only restriction is that the address
fields visible in the transmitted packet must be the same as those fields that are visible in the transmitted packet must be the same as
used to construct the autokey list and that these fields be the same those used to construct the autokey list and that these fields be the
as those visible in the received packet. [The use of alternative same as those visible in the received packet. (The use of
means, such as Autokey host names (discussed later) or hashes of alternative means, such as Autokey host names (discussed later) or
these names may be a topic for future study.] hashes of these names may be a topic for future study.)
+-----------+-----------+------+------+ +---------+ +-----+------+ +-----------+-----------+------+------+ +---------+ +-----+------+
|Src Address|Dst Address|Key ID|Cookie|-->| | |Final|Final | |Src Address|Dst Address|Key ID|Cookie|-->| | |Final|Final |
+-----------+-----------+------+------+ | Session | |Index|Key ID| +-----------+-----------+------+------+ | Session | |Index|Key ID|
| | | | | Key ID | +-----+------+ | | | | | Key ID | +-----+------+
\|/ \|/ \|/ \|/ | List | | | \|/ \|/ \|/ \|/ | List | | |
************************************* +---------+ \|/ \|/ ************************************* +---------+ \|/ \|/
* COMPUTE HASH * ******************* * COMPUTE HASH * *******************
************************************* *COMPUTE SIGNATURE* ************************************* *COMPUTE SIGNATURE*
| Index n ******************* | Index n *******************
\|/ | \|/ |
+--------+ | +--------+ |
| Next | \|/ | Next | \|/
| Key ID | +-----------+ | Key ID | +-----------+
+--------+ | Signature | +--------+ | Signature |
Index n+1 +-----------+ Index n+1 +-----------+
Figure 3: Constructing the Key List Figure 3: Constructing the Key List
Figure 3 shows how the autokey list and autokey values are computed. Figure 3 shows how the autokey list and autokey values are computed.
The key IDs used in the autokey list consists of a sequence starting The key IDs used in the autokey list consist of a sequence starting
with a random 32-bit nonce (autokey seed) equal to or greater than 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 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. 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 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 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 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. the key ID for the next autokey assigned index 1.
Operations continue to generate the entire list. It may happen that Operations continue to generate the entire list. It may happen that
a newly generated key ID is less than the pivot or collides with a newly generated key ID is less than the pivot or collides with
another one already generated (birthday event). When this happens, another one already generated (birthday event). When this happens,
which occurs only rarely, the key list is terminated at that point. 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 The lifetime of each key is set to expire one poll interval after its
scheduled use. In the reference implementation, the list is scheduled use. In the reference implementation, the list is
terminated when the maximum key lifetime is about one hour, so for 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 poll intervals above one hour, a new key list containing only a
entry is regenerated for every poll. single entry is regenerated for every poll.
+------------------+ +------------------+
| NTP Header and | | NTP Header and |
| Extension Fields | | Extension Fields |
+------------------+ +------------------+
| | | |
\|/ \|/ +---------+ \|/ \|/ +---------+
**************** +--------+ | Session | **************** +--------+ | Session |
* COMPUTE HASH *<---| Key ID |<---| Key ID | * COMPUTE HASH *<---| Key ID |<---| Key ID |
**************** +--------+ | List | **************** +--------+ | List |
| | +---------+ | | +---------+
\|/ \|/ \|/ \|/
+----------------------------------+ +-----------------------------------+
| Message Authenticator Code (MAC) | | Message Authentication Code (MAC) |
+----------------------------------+ +-----------------------------------+
Figure 4: Transmitting Messages Figure 4: Transmitting Messages
The index of the last autokey in the list is saved along with the key 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 ID for that entry, collectively called the autokey values. The
autokey values are then signed for use later. The list is used in 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 reverse order as shown in Figure 4, so that the first autokey used is
the last one generated. the last one generated.
The Autokey protocol includes a message to retrieve the autokey The Autokey protocol includes a message to retrieve the autokey
values and verify the signature, so that subsequent packets can be values and verify the signature, so that subsequent packets can be
validated using one or more hashes that eventually match the last key validated using one or more hashes that eventually match the last key
ID (valid) or exceed the index (invalid). This is called the autokey ID (valid) or exceed the index (invalid). This is called the autokey
test in the following and is done for every packet, including those test in the following and is done for every packet, including those
with and without extension fields. In the reference implementation with and without extension fields. In the reference implementation,
the most recent key ID received is saved for comparison with the 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. 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 This minimizes the number of hash operations in case a single packet
is lost. is lost.
5. Autokey Protocol Overview 5. Autokey Protocol Overview
The Autokey protocol includes a number of request/response exchanges The Autokey protocol includes a number of request/response exchanges
that must be completed in order. In each exchange a client sends a that must be completed in order. In each exchange, a client sends a
request message with data and expects a server response message with request message with data and expects a server response message with
data. Requests and responses are contained in extension fields, one data. Requests and responses are contained in extension fields, one
request or response in each field, as described later. An NTP packet request or response in each field, as described later. An NTP packet
can contain one request message and one or more response messages. can contain one request message and one or more response messages.
Following is a list of these messages. The following is a list of these messages.
o Parameter exchange. The request includes the client host name and o Parameter exchange. The request includes the client host name and
status word; the response includes the server host name and status status word; the response includes the server host name and status
word. The status word specifies the digest/signature scheme to word. The status word specifies the digest/signature scheme to
use and the identity schemes supported. use and the identity schemes supported.
o Certificate exchange. The request includes the subject name of a o Certificate exchange. The request includes the subject name of a
certificate; the response consists of a signed certificate with certificate; the response consists of a signed certificate with
that subject name. If the issuer name is not the same as the 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 subject name, it has been signed by a host one step closer to a
skipping to change at page 13, line 39 skipping to change at page 13, line 38
described below. described below.
o Autokey exchange. The request includes either no data or the o Autokey exchange. The request includes either no data or the
autokey values in symmetric modes. The response includes the autokey values in symmetric modes. The response includes the
autokey values of the server. These values are used to verify the autokey values of the server. These values are used to verify the
autokey sequence. Completion of this exchange lights the AUT bit autokey sequence. Completion of this exchange lights the AUT bit
as described below. as described below.
o Sign exchange. This exchange is executed only when the client has o Sign exchange. This exchange is executed only when the client has
synchronized to a proventic source. The request includes the synchronized to a proventic source. The request includes the
self-signed client certificate. The server acting as CA self-signed client certificate. The server acting as
interprets the certificate as a X.509v3 certificate request. It certification authority (CA) interprets the certificate as a
extracts the subject, issuer, and extension fields, builds a new X.509v3 certificate request. It extracts the subject, issuer, and
certificate with these data along with its own serial number and extension fields, builds a new certificate with these data along
expiration time, then signs it using its own private key and with its own serial number and expiration time, then signs it
includes it in the response. The client uses the signed using its own private key and includes it in the response. The
certificate in its own role as server for dependent clients. client uses the signed certificate in its own role as server for
Completion of this exchange lights the SIGN bit as described dependent clients. Completion of this exchange lights the SIGN
below. bit as described below.
o Leapseconds exchange. This exchange is executed only when the o Leapseconds exchange. This exchange is executed only when the
client has synchronized to a proventic source. This exchange client has synchronized to a proventic source. This exchange
occurs when the server has the leapseconds values, as indicated in occurs when the server has the leapseconds values, as indicated in
the host status word. If so, the client requests the values and the host status word. If so, the client requests the values and
compares them with its own values, if available. If the server compares them with its own values, if available. If the server
values are newer than the client values, the client replaces its values are newer than the client values, the client replaces its
own with the server values. The client, acting as server, can now own with the server values. The client, acting as server, can now
provide the most recent values to its dependent clients. In provide the most recent values to its dependent clients. In
symmetric mode, this results in both peers having the newest symmetric mode, this results in both peers having the newest
values. Completion of this exchange lights the LPT bit as values. Completion of this exchange lights the LPT bit as
described below. described below.
Once the certificates and identity have been validated, subsequent Once the certificates and identity have been validated, subsequent
packets are validated by digital signatures and the autokey sequence. packets are validated by digital signatures and the autokey sequence.
The association is now proventic with respect to the downstratum The association is now proventic with respect to the downstratum
trusted host, but is not yet selectable to discipline the system trusted host, but is not yet selectable to discipline the system
clock. The associations accumulate time values and the mitigation clock. The associations accumulate time values, and the mitigation
algorithms continue in the usual way. When these algorithms have algorithms continue in the usual way. When these algorithms have
culled the falsetickers and cluster outlyers and at least three culled the falsetickers and cluster outliers and at least three
survivors remain, the system clock has been synchronized to a survivors remain, the system clock has been synchronized to a
proventic source. proventic source.
The time values for truechimer sources form a proventic partial The time values for truechimer sources form a proventic partial
ordering relative to the applicable signature timestamps. This ordering relative to the applicable signature timestamps. This
raises the interesting issue of how to mitigate between the raises the interesting issue of how to differentiate between the
timestamps of different associations. It might happen, for instance, timestamps of different associations. It might happen, for instance,
that the timestamp of some Autokey message is ahead of the system that the timestamp of some Autokey message is ahead of the system
clock by some presumably small amount. For this reason, timestamp clock by some presumably small amount. For this reason, timestamp
comparisons between different associations and between associations comparisons between different associations and between associations
and the system clock are avoided, except in the NTP intersection and and the system clock are avoided, except in the NTP intersection and
clustering algorithms and when determining whether a certificate has clustering algorithms and when determining whether a certificate has
expired. expired.
6. NTP Secure Groups 6. NTP Secure Groups
skipping to change at page 14, line 47 skipping to change at page 14, line 45
security hierarchies. A secure group consists of a number of hosts security hierarchies. A secure group consists of a number of hosts
dynamically assembled as a forest with roots the trusted hosts (THs) 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 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), often are, primary (stratum 1) servers. A trusted authority (TA),
not necessarily a group host, generates private identity keys for not necessarily a group host, generates private identity keys for
servers and public identity keys for clients at the leaves of the servers and public identity keys for clients at the leaves of the
forest. The TA deploys the server keys to the THs and other forest. The TA deploys the server keys to the THs and other
designated servers using secure means and posts the client keys on a designated servers using secure means and posts the client keys on a
public web site. public web site.
For Autokey purposes all hosts belonging to a secure group have the For Autokey purposes, all hosts belonging to a secure group have the
same group name but different host names, not necessarily related to same group name but different host names, not necessarily related to
the DNS names. The group name is used in the subject and issuer 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 fields of the TH certificates; the host name is used in these fields
for other hosts. Thus, all host certificates are self-signed. for other hosts. Thus, all host certificates are self-signed.
During the Autokey protocol a client requests the server to sign its During the use of the Autokey protocol, a client requests that the
certificate and caches the result. A certificate trail is server sign its certificate and caches the result. A certificate
constructed by each host, possibly via intermediate hosts and ending trail is constructed by each host, possibly via intermediate hosts
at a TH. Thus, each host along the trail retrieves the entire trail and ending at a TH. Thus, each host along the trail retrieves the
from its server(s) and provides this plus its own signed certificates entire trail from its server(s) and provides this plus its own signed
to its clients. certificates to its clients.
Secure groups can be configured as hierarchies where a TH of one 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 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 lower stratum. In one scenario, THs for groups RED and GREEN can be
cryptographically distinct, but both be clients of group BLUE cryptographically distinct, but both be clients of group BLUE
operating at a lower stratum. In another scenario, THs for group operating at a lower stratum. In another scenario, THs for group
CYAN can be clients of multiple groups YELLOW and MAGENTA, both CYAN can be clients of multiple groups YELLOW and MAGENTA, both
operating at a lower stratum. There are many other scenarios, but operating at a lower stratum. There are many other scenarios, but
all must be configured to include only acyclic certificate trails. all must be configured to include only acyclic certificate trails.
skipping to change at page 16, line 49 skipping to change at page 17, line 45
+---------------------------------------------+ +---------------------------------------------+
Stratum 3 Stratum 3
Figure 5: NTP Secure Groups Figure 5: NTP Secure Groups
The steps in hiking the certificate trails and verifying identity are The steps in hiking the certificate trails and verifying identity are
as follows. Note the step number in the description matches the step as follows. Note the step number in the description matches the step
number in the figure. number in the figure.
1. The girls start by loading the host key, sign key, self-signed 1. The girls start by loading the host key, sign key, self-signed
certificate and group key. Each client and server acting as a certificate, and group key. Each client and server acting as a
client starts the Autokey protocol by retrieving the server host client starts the Autokey protocol by retrieving the server host
name and digest/signature. This is done using the ASSOC exchange name and digest/signature. This is done using the ASSOC exchange
described later. described later.
2. They continue to load certificates recursively until a self- 2. They continue to load certificates recursively until a self-
signed trusted certificate is found. Brenda and Denise signed trusted certificate is found. Brenda and Denise
immediately find trusted certificates for Alice and Carol, immediately find trusted certificates for Alice and Carol,
respectively, but Eileen will loop because neither Brenda nor respectively, but Eileen will loop because neither Brenda nor
Denise have their own certificates signed by either Alice or Denise have their own certificates signed by either Alice or
Carol. This is done using the CERT exchange described later. Carol. This is done using the CERT exchange described later.
3. Brenda and Denise continue with the selected identity schemes to 3. Brenda and Denise continue with the selected identity schemes to
verify that Alice and Carol have the correct group key previously verify that Alice and Carol have the correct group key previously
generated by Alice. This is done using one of the identity generated by Alice. This is done using one of the identity
schemes IFF, GQ or MV described later. If this succeeds, each schemes IFF, GQ, or MV, described later. If this succeeds, each
continues in step 4. continues in step 4.
4. Brenda and Denise present their certificates for signature using 4. Brenda and Denise present their certificates for signature using
the SIGN exchange described later. If this succeeds, either or the SIGN exchange described later. If this succeeds, either one
both Brenda and Denise can now provide these signed certificates of or both Brenda and Denise can now provide these signed
to Eileen, which may be looping in step 2. Eileen can now verify certificates to Eileen, which may be looping in step 2. Eileen
the trail via either Brenda or Denise to the trusted certificates can now verify the trail via either Brenda or Denise to the
for Alice and Carol. Once this is done, Eileen can complete the trusted certificates for Alice and Carol. Once this is done,
protocol just as Brenda and Denise. Eileen can complete the protocol just as Brenda and Denise did.
For various reasons it may be convenient for a server to have client 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 keys for more than one group. For example, Figure 6 shows three
secure groups Alice, Helen and Carol arranged in a hierarchy. Hosts secure groups Alice, Helen, and Carol arranged in a hierarchy. Hosts
A, B, C and D belong to Alice with A and B her THs. Hosts R and S A, B, C, and D belong to Alice with A and B as her THs. Hosts R and
belong to Helen with R her TH. Hosts X and Y belong to Carol withi X S belong to Helen with R as her TH. Hosts X and Y belong to Carol
her TH. Note that the TH for a group is always the lowest stratum with X as her TH. Note that the TH for a group is always the lowest
and that the hosts of the combined groups form an acyclic graph. stratum and that the hosts of the combined groups form an acyclic
Note also that the certificate trail for each group terminates on a graph. Note also that the certificate trail for each group
TH for that group. terminates on a TH for that group.
***** ***** @@@@@ ***** ***** @@@@@
Stratum 1 * A * * B * @ R @ Stratum 1 * A * * B * @ R @
***** ***** @@@@@ ***** ***** @@@@@
\ / / \ / /
\ / / \ / /
***** @@@@@ ********* ***** @@@@@ *********
2 * C * @ S @ * Alice * 2 * C * @ S @ * Alice *
***** @@@@@ ********* ***** @@@@@ *********
/ \ / / \ /
skipping to change at page 18, line 27 skipping to change at page 19, line 6
***** ##### ***** #####
/ \ ######### / \ #########
/ \ # Carol # / \ # Carol #
##### ##### ######### ##### ##### #########
4 # Y # # Z # 4 # Y # # Z #
##### ##### ##### #####
Figure 6: Hierarchical Overlapping Groups Figure 6: Hierarchical Overlapping Groups
The intent of the scenario is to provide security separation, so that The intent of the scenario is to provide security separation, so that
servers cannot masquerade as in other groups and clients cannot servers cannot masquerade as clients in other groups and clients
masquerade as servers. Assume for example that Alice and Helen cannot masquerade as servers. Assume, for example, that Alice and
belong to national standards laboratories and their server keys are Helen belong to national standards laboratories and their server keys
used to confirm identity between members of each group. Carol is a are used to confirm identity between members of each group. Carol is
prominent corporation receiving standards products and requiring a prominent corporation receiving standards products and requiring
cryptographic authentication. Perhaps under contract, host X cryptographic authentication. Perhaps under contract, host X
belonging to Carol has client keys for both Alice and Helen and belonging to Carol has client keys for both Alice and Helen and
server keys for Carol. The Autokey protocol operates for each group server keys for Carol. The Autokey protocol operates for each group
separately while preserving security separation. Host X can prove separately while preserving security separation. Host X can prove
identity in Carol to clients Y and Z, but cannot prove to anybody identity in Carol to clients Y and Z, but cannot prove to anybody
that it belongs to either Alice or Helen. that it belongs to either Alice or Helen.
7. Identity Schemes 7. Identity Schemes
A digital signature scheme provides secure server authentication, but A digital signature scheme provides secure server authentication, but
it does not provide protection against masquerade, unless the server it does not provide protection against masquerade, unless the server
identity is verified by other means. The PKI model requires a server identity is verified by other means. The PKI model requires a server
to prove identity to the client by a certificate trail, but to prove identity to the client by a certificate trail, but
independent means such as a driver's license are required for a CA to independent means such as a driver's license are required for a CA to
sign the server certificate. While Autokey supports this model by sign the server certificate. While Autokey supports this model by
default, in a hierarchical ad-hoc network, especially with server default, in a hierarchical ad hoc network, especially with server
discovery schemes like NTP Manycast, proving identity at each rest discovery schemes like NTP manycast, proving identity at each rest
stop on the trail must be an intrinsic capability of Autokey itself. stop on the trail must be an intrinsic capability of Autokey itself.
While the identity scheme described in [RFC2875] is based on a While the identity scheme described in [RFC2875] is based on a
ubiquitous Diffie-Hellman infrastructure, it is expensive to generate ubiquitous Diffie-Hellman infrastructure, it is expensive to generate
and use when compared to others described in Appendix B. In and use when compared to others described in Appendix B. In
principle, an ordinary public key scheme could be devised for this principle, an ordinary public key scheme could be devised for this
purpose, but the most stringent Autokey design requires that every purpose, but the most stringent Autokey design requires that every
challenge, even if duplicated, results in a different acceptable challenge, even if duplicated, results in a different acceptable
response. response.
1. The scheme must have a relatively long lifetime, certainly longer 1. The scheme must have a relatively long lifetime, certainly longer
than a typical certificate, and have no specific lifetime or than a typical certificate, and have no specific lifetime or
expiration date. At the time the scheme is used the host has not expiration date. At the time the scheme is used, the host has
yet synchronized to a proventic source, so the scheme cannot not yet synchronized to a proventic source, so the scheme cannot
depend time.. depend on time.
2. As the scheme can be used many times where the data might be 2. As the scheme can be used many times where the data might be
exposed to potential intruders, the data must be either nonces or exposed to potential intruders, the data must be either nonces or
encrypted nonces. encrypted nonces.
3. The scheme should allow designated servers to prove identity to 3. The scheme should allow designated servers to prove identity to
designated clients, but not allow clients acting as servers to designated clients, but not allow clients acting as servers to
prove identity to dependent clients. prove identity to dependent clients.
4. To the geatest extent possible, the scheme should represent a 4. To the greatest extent possible, the scheme should represent a
zero-knowledge proof; that is, the client should be able to zero-knowledge proof; that is, the client should be able to
verify the server has the correct group key, but without knowing verify that the server has the correct group key, but without
the key itself. knowing the key itself.
There are five schemes now implemented in the NTPv4 reference There are five schemes now implemented in the NTPv4 reference
implementation to prove identity: (1) private certificate (PC), (2) implementation to prove identity: (1) private certificate (PC), (2)
trusted certificate (TC), (3) a modified Schnorr algorithm (IFF aka trusted certificate (TC), (3) a modified Schnorr algorithm (IFF aka
Identify Friendly or Foe), (4) a modified Guillou-Quisquater Identify Friendly or Foe), (4) a modified Guillou-Quisquater (GQ)
algorithm (GQ), and (5) a modified Mu-Varadharajan algorithm (MV). algorithm, and (5) a modified Mu-Varadharajan (MV) algorithm. Not
Not all of these provide the same level of protection and one, TC, all of these provide the same level of protection and one, TC,
provides no protection but is included for comparison. Following is provides no protection but is included for comparison. The following
a brief summary description of each; details are given in Appendix B. is a brief summary description of each; details are given in
Appendix B.
The PC scheme involves a private certificate as group key. The The PC scheme involves a private certificate as group key. The
certificate is distributed to all other group members by secure means certificate is distributed to all other group members by secure means
and is never revealed outside the group. In effect, the private and is never revealed outside the group. In effect, the private
certificate is used as a symmetric key. This scheme is used certificate is used as a symmetric key. This scheme is used
primarily for testing and development and is not recommended for primarily for testing and development and is not recommended for
regular use and is not considered further in this memo. regular use and is not considered further in this memo.
All other schemes involve a conventional certificate trail as All other schemes involve a conventional certificate trail as
described in [RFC5280]. This is the default scheme when an identity described in [RFC5280]. This is the default scheme when an identity
scheme is not required. While the remaining identity schemes scheme is not required. While the remaining identity schemes
incorporate TC, it is not by itself considered further in this memo. incorporate TC, it is not by itself considered further in this memo.
The three remaining schemes IFF, GQ and MV involve a The three remaining schemes IFF, GQ, and MV involve a
cryptographically strong challenge-response exchange where an cryptographically strong challenge-response exchange where an
intruder cannot deduce the server key, even after repeated intruder cannot deduce the server key, even after repeated
observations of multiple exchanges. In addition, the MV scheme is observations of multiple exchanges. In addition, the MV scheme is
properly described as a zero-knowledge proof, because the client can properly described as a zero-knowledge proof, because the client can
verify the server has the correct group key without either the server verify the server has the correct group key without either the server
or client knowing its value. These schemes start when the client or client knowing its value. These schemes start when the client
sends a nonce to the server, which then rolls its own nonce, performs sends a nonce to the server, which then rolls its own nonce, performs
a mathematical operation and sends the results to the client. The a mathematical operation and sends the results to the client. The
client performs another mathematical operation and verifies the client performs another mathematical operation and verifies the
results are correct. results are correct.
skipping to change at page 20, line 26 skipping to change at page 21, line 6
While public key signatures provide strong protection against While public key signatures provide strong protection against
misrepresentation of source, computing them is expensive. This misrepresentation of source, computing them is expensive. This
invites the opportunity for an intruder to clog the client or server invites the opportunity for an intruder to clog the client or server
by replaying old messages or originating bogus messages. A client by replaying old messages or originating bogus messages. A client
receiving such messages might be forced to verify what turns out to receiving such messages might be forced to verify what turns out to
be an invalid signature and consume significant processor resources. be an invalid signature and consume significant processor resources.
In order to foil such attacks, every Autokey message carries a In order to foil such attacks, every Autokey message carries a
timestamp in the form of the NTP seconds when it was created. If the timestamp in the form of the NTP seconds when it was created. If the
system clock is synchronized to a proventic source, a signature is system clock is synchronized to a proventic source, a signature is
produced with valid (nonzero) timestamp. Otherwise, there is no produced with a valid (nonzero) timestamp. Otherwise, there is no
signature and the timestamp is invalid (zero). The protocol detects signature and the timestamp is invalid (zero). The protocol detects
and discards extension fields with old or duplicate timestamps, and discards extension fields with old or duplicate timestamps,
before any values are used or signatures are verified. before any values are used or signatures are verified.
Signatures are computed only when cryptographic values are created or Signatures are computed only when cryptographic values are created or
modified, which is by design not very often. Extension fields modified, which is by design not very often. Extension fields
carrying these signatures are copied to messages as needed, but the carrying these signatures are copied to messages as needed, but the
signatures are not recomputed. There are three signature types: signatures are not recomputed. There are three signature types:
1. Cookie signature/timestamp. The cookie is signed when created by 1. Cookie signature/timestamp. The cookie is signed when created by
the server and sent to the client. the server and sent to the client.
2. Autokey signature/timestamp. The autokey values are signed when 2. Autokey signature/timestamp. The autokey values are signed when
the key list is created. the key list is created.
3. Public values signature/timestamp. The public key, certificate 3. Public values signature/timestamp. The public key, certificate,
and leapsecond values are signed at the time of generation, which and leapsecond values are signed at the time of generation, which
occurs when the system clock is first synchronized to a proventic occurs when the system clock is first synchronized to a proventic
source, when the values have changed and about once per day after source, when the values have changed and about once per day after
that, even if these values have not changed. that, even if these values have not changed.
The most recent timestamp received of each type is saved for The most recent timestamp received of each type is saved for
comparison. Once a signature with valid timestamp has been received, comparison. Once a signature with a valid timestamp has been
messages with invalid timestamps or earlier valid timestamps of the received, messages with invalid timestamps or earlier valid
same type are discarded before the signature is verified. This is timestamps of the same type are discarded before the signature is
most important in broadcast mode, which could be vulnerable to a verified. This is most important in broadcast mode, which could be
clogging attack without this test. vulnerable to a clogging attack without this test.
All cryptographic values used by the protocol are time sensitive and All cryptographic values used by the protocol are time sensitive and
are regularly refreshed. In particular, files containing are regularly refreshed. In particular, files containing
cryptographic values used by signature and encryption algorithms are cryptographic values used by signature and encryption algorithms are
regenerated from time to time. It is the intent that file regenerated from time to time. It is the intent that file
regenerations occur without specific advance warning and without regenerations occur without specific advance warning and without
requiring prior distribution of the file contents. While requiring prior distribution of the file contents. While
cryptographic data files are not specifically signed, every file is cryptographic data files are not specifically signed, every file is
associated with a filestamp showing the NTP seconds at the creation associated with a filestamp showing the NTP seconds at the creation
epoch. epoch.
skipping to change at page 21, line 28 skipping to change at page 22, line 9
Filestamps and timestamps can be compared in any combination and use Filestamps and timestamps can be compared in any combination and use
the same conventions. It is necessary to compare them from time to the same conventions. It is necessary to compare them from time to
time to determine which are earlier or later. Since these quantities time to determine which are earlier or later. Since these quantities
have a granularity only to the second, such comparisons are ambiguous have a granularity only to the second, such comparisons are ambiguous
if the values are in the same second. if the values are in the same second.
It is important that filestamps be proventic data; thus, they cannot It is important that filestamps be proventic data; thus, they cannot
be produced unless the producer has been synchronized to a proventic be produced unless the producer has been synchronized to a proventic
source. As such, the filestamps throughout the NTP subnet represent source. As such, the filestamps throughout the NTP subnet represent
a partial ordering of all creation epochs and serve as means to 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 expunge old data and ensure new data are consistent. As the data are
forwarded from server to client, the filestamps are preserved, forwarded from server to client, the filestamps are preserved,
including those for certificate and leapseconds values. Packets with including those for certificate and leapseconds values. Packets with
older filestamps are discarded before spending cycles to verify the older filestamps are discarded before spending cycles to verify the
signature. signature.
9. Autokey Operations 9. Autokey Operations
The NTP protocol has three principal modes of operation: client/ The NTP protocol has three principal modes of operation: client/
server, symmetric and broadcast and each has its own Autokey program, server, symmetric, and broadcast and each has its own Autokey
or dance. Autokey choreography is designed to be nonintrusive and to program, or dance. Autokey choreography is designed to be non-
require no additional packets other than for regular NTP operations. intrusive and to require no additional packets other than for regular
The NTP and Autokey protocols operate simultaneously and NTP operations. The NTP and Autokey protocols operate simultaneously
independently. When the dance is complete, subsequent packets are and independently. When the dance is complete, subsequent packets
validated by the autokey sequence and thus considered proventic as are validated by the autokey sequence and thus considered proventic
well. Autokey assumes NTP clients poll servers at a relatively low as well. Autokey assumes NTP clients poll servers at a relatively
rate, such as once per minute or slower. In particular, it assumes low rate, such as once per minute or slower. In particular, it
that a request sent at one poll opportunity will normally result in a assumes that a request sent at one poll opportunity will normally
response before the next poll opportunity; however the protocol is result in a response before the next poll opportunity; however, the
robust against a missed or duplicate response. protocol is robust against a missed or duplicate response.
The server dance was suggested by Steve Kent over lunch some time The server dance was suggested by Steve Kent over lunch some time
ago, but considerably modified since that meal. The server keeps no 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 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 private value (server seed) to regenerate the cookie upon arrival of
a client packet. The cookie is calculated as the first 32 bits of a client packet. The cookie is calculated as the first 32 bits of
the autokey computed from the client and server addresses, key ID the autokey computed from the client and server addresses, key ID
zero and the server seed as cookie. The cookie is used for the 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 actual autokey calculation by both the client and server and is thus
specific to each client separately. specific to each client separately.
In the server dance the client uses the cookie and each key ID on the In the server dance, the client uses the cookie and each key ID on
key list in turn to retrieve the autokey and generate the MAC. The the key list in turn to retrieve the autokey and generate the MAC.
server uses the same values to generate the message digest and The server uses the same values to generate the message digest and
verifies it matches the MAC. It then generates the MAC for the verifies it matches the MAC. It then generates the MAC for the
response using the same values, but with the client and server response using the same values, but with the client and server
addresses interchanged. The client generates the message digest and addresses interchanged. The client generates the message digest and
verifies it matches the MAC. In order to deflect old replays, the verifies it matches the MAC. In order to deflect old replays, the
client verifies the key ID matches the last one sent. In this dance client verifies that the key ID matches the last one sent. In this
the sequential structure of the key list is not exploited, but doing dance, the sequential structure of the key list is not exploited, but
it this way simplifies and regularizes the implementation while doing it this way simplifies and regularizes the implementation while
making it nearly impossible for an intruder to guess the next key ID. 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 In the broadcast dance, clients normally do not send packets to the
server, except when first starting up. At that time the client runs server, except when first starting up. At that time, the client runs
the server dance to verify the server credentials and calibrate the the server dance to verify the server credentials and calibrate the
propagation delay. The dance requires the association ID of the propagation delay. The dance requires the association ID of the
particular server association, since there can be more than one particular server association, since there can be more than one
operating in the same server. For this purpose, the server packet operating in the same server. For this purpose, the server packet
includes the association ID in every response message sent and, when includes the association ID in every response message sent and, when
sending the first packet after generating a new key list, it sends sending the first packet after generating a new key list, it sends
the autokey values as well. After obtaining and verifying the the autokey values as well. After obtaining and verifying the
autokey values, no extension fields are necessary and the client autokey values, no extension fields are necessary and the client
verifies further server packets using the autokey sequence. verifies further server packets using the autokey sequence.
The symmetric dance is similar to the server dance and requires only The symmetric dance is similar to the server dance and requires only
a small amount of state between the arrival of a request and a small amount of state between the arrival of a request and
departure of the response. The key list for each direction is departure of the response. The key list for each direction is
generated separately by each peer and used independently, but each is generated separately by each peer and used independently, but each is
generated with the same cookie. The cookie is conveyed in a way generated with the same cookie. The cookie is conveyed in a way
similar to the server dance, except that the cookie is a simple similar to the server dance, except that the cookie is a simple
nonce. There exists a possible race condition where each peer sends nonce. There exists a possible race condition where each peer sends
a cookie request before receiving the cookie response from the other a cookie request before receiving the cookie response from the other
peer. In this case each peer winds up with two values, one it peer. In this case, each peer winds up with two values, one it
generated and one the other peer generated. The ambiguity is generated and one the other peer generated. The ambiguity is
resolved simply by computing the working cookie as the EXOR of the resolved simply by computing the working cookie as the EXOR of the
two values. two values.
Once the autokey dance has completed, it is normally dormant. In all Once the Autokey dance has completed, it is normally dormant. In all
except the broadcast dance, packets are normally sent without except the broadcast dance, packets are normally sent without
extension fields, unless the packet is the first one sent after extension fields, unless the packet is the first one sent after
generating a new key list or unless the client has requested the generating a new key list or unless the client has requested the
cookie or autokey values. If for some reason the client clock is cookie or autokey values. If for some reason the client clock is
stepped, rather than slewed, all cryptographic and time values for stepped, rather than slewed, all cryptographic and time values for
all associations are purged and the dances in all associations all associations are purged and the dances in all associations
restarted from scratch. This insures that stale values never restarted from scratch. This ensures that stale values never
propagate beyond a clock step. propagate beyond a clock step.
10. Autokey Protocol Messages 10. Autokey Protocol Messages
The Autokey protocol data unit is the extension field, one or more of The Autokey protocol data unit is the extension field, one or more of
which can be piggybacked in the NTP packet. An extension field which can be piggybacked in the NTP packet. An extension field
contains either a request with optional data or a response with contains either a request with optional data or a response with
optional data. To avoid deadlocks, any number of responses can be optional data. To avoid deadlocks, any number of responses can be
included in a packet, but only one request. A response is generated included in a packet, but only one request can be. A response is
for every request, even if the requestor is not synchronized to a generated for every request, even if the requestor is not
proventic source, but most contain meaningful data only if the synchronized to a proventic source, but most contain meaningful data
responder is synchronized to a proventic source. Some requests and only if the responder is synchronized to a proventic source. Some
most responses carry timestamped signatures. The signature covers requests and most responses carry timestamped signatures. The
the entire extension field, including the timestamp and filestamp, signature covers the entire extension field, including the timestamp
where applicable. Only if the packet has correct format, length and and filestamp, where applicable. Only if the packet has correct
message digest are cycles spent to verify the signature. format, length, and message digest are cycles spent to verify the
signature.
There are currently eight Autokey requests and eight corresponding There are currently eight Autokey requests and eight corresponding
responses. The NTP packet format is described in responses. The NTP packet format is described in [RFC5905] and the
[I-D.ietf-ntp-ntpv4-proto] and the extension field format used for extension field format used for these messages is illustrated in
these messages is illustrated in Figure 7. 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 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|R|E| Code | Field Type | Length | |R|E| Code | Field Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Association ID | | Association ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Timestamp | | Timestamp |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Filestamp | | Filestamp |
skipping to change at page 24, line 49 skipping to change at page 25, line 12
length remains to be established. The reference implementation length remains to be established. The reference implementation
discards any packet with a field length more than 1024 octets. discards any packet with a field length more than 1024 octets.
One or more extension fields follow the NTP packet header and the One or more extension fields follow the NTP packet header and the
last followed by the MAC. The extension field parser initializes a last followed by the MAC. The extension field parser initializes a
pointer to the first octet beyond the NTP packet header and pointer to the first octet beyond the NTP packet header and
calculates the number of octets remaining to the end of the packet. calculates the number of octets remaining to the end of the packet.
If the remaining length is 20 (128-bit digest plus 4-octet key ID) or If the remaining length is 20 (128-bit digest plus 4-octet key ID) or
22 (160-bit digest plus 4-octet key ID), the remaining data are the 22 (160-bit digest plus 4-octet key ID), the remaining data are the
MAC and parsing is complete. If the remaining length is greater than MAC and parsing is complete. If the remaining length is greater than
22 an extension field is present. If the remaining length is less 22, an extension field is present. If the remaining length is less
than 8 or not a multiple of 4, a format error has occurred and the than 8 or not a multiple of 4, a format error has occurred and the
packet is discarded; otherwise, the parser increments the pointer by packet is discarded; otherwise, the parser increments the pointer by
the extension field length and then uses the same rules as above to the extension field length and then uses the same rules as above to
determine whether a MAC is present or another extension field. determine whether a MAC is present or another extension field.
In Autokey the 8-bit Field Type field is interpreted as the version In Autokey the 8-bit Field Type field is interpreted as the version
number, currently 2. For future versions values 1-7 have been number, currently 2. For future versions, values 1-7 have been
reserved for Autokey; other values may be assigned for other reserved for Autokey; other values may be assigned for other
applications. The 6-bit Code field specifies the request or response applications. The 6-bit Code field specifies the request or response
operation. There are two flag bits: bit 0 is the Response Flag (R) operation. There are two flag bits: bit 0 is the Response Flag (R)
and bit 1 is the Error Flag (E); the Reserved field is unused and and bit 1 is the Error Flag (E); the Reserved field is unused and
should be set to 0. The remaining fields will be described later. 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 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 server with an operation code specified in the Code field and both
the R bit and E bit dim. The server returns a response with the same the R bit and E bit dim. The server returns a response with the same
operation code in the Code field and lights the R bit. The server operation code in the Code field and lights the R bit. The server
can also light the E bit in case of error. Note that it is not can also light the E bit in case of error. Note that it is not
necessarily a protocol error to send an unsolicited response with no necessarily a protocol error to send an unsolicited response with no
matching request. If the R bit is dim, the client sets the matching request. If the R bit is dim, the client sets the
Association ID field to the client association ID which the servert Association ID field to the client association ID, which the server
returns for verification. If the two values do not match, the returns for verification. If the two values do not match, the
response is discarded as if never sent. If the R bit is lit, the response is discarded as if never sent. If the R bit is lit, the
Association ID field is set the the server association ID obtained in Association ID field is set to the server association ID obtained in
the initial protocol exchange. If the Association ID field does not the initial protocol exchange. If the Association ID field does not
match any mobilized association ID, the request is discarded as if match any mobilized association ID, the request is discarded as if
never sent. never sent.
In some cases not all fields may be present. For requests, until a In some cases, not all fields may be present. For requests, until a
client has synchronized to a proventic source, signatures are not client has synchronized to a proventic source, signatures are not
valid. In such cases the Timestamp field and Signature Length field valid. In such cases, the Timestamp field and Signature Length field
(which specifies the length of the Signature) are zero and the (which specifies the length of the Signature) are zero and the
Signature field is absent. Some request and error response messages Signature field is absent. Some request and error response messages
carry no value or signature fields, so in these messages only the carry no value or signature fields, so in these messages only the
first two words (8 octests) are present. first two words (8 octets) are present.
The Timestamp and Filestamp words carry the seconds field of an NTP The Timestamp and Filestamp words carry the seconds field of an NTP
timestamp. The timestamp establishes the signature epoch of the data timestamp. The timestamp establishes the signature epoch of the data
field in the message, while the filestamp establishes the generation field in the message, while the filestamp establishes the generation
epoch of the file that ultimately produced the data that is signed. epoch of the file that ultimately produced the data that is signed.
A signature and timestamp are valid only when the signing host is A signature and timestamp are valid only when the signing host is
synchronized to a proventic source; otherwise, the timestamp is zero. synchronized to a proventic source; otherwise, the timestamp is zero.
A cryptographic data file can only be generated if a signature is A cryptographic data file can only be generated if a signature is
possible; otherwise, the filestamp is zero, except in the ASSOC possible; otherwise, the filestamp is zero, except in the ASSOC
response message, where it contains the server status word. response message, where it contains the server status word.
As in all other TCP/IP protocol designs, all data are sent in network As in all other TCP/IP protocol designs, all data are sent in network
byte order. Unless specified otherwise in the descriptions to byte order. Unless specified otherwise in the descriptions to
follow, the data referred to are stored in the Value field. The follow, the data referred to are stored in the Value field. The
Value Length field specifies the length of the data in the Value Value Length field specifies the length of the data in the Value
skipping to change at page 26, line 8 skipping to change at page 26, line 20
As in all other TCP/IP protocol designs, all data are sent in network As in all other TCP/IP protocol designs, all data are sent in network
byte order. Unless specified otherwise in the descriptions to byte order. Unless specified otherwise in the descriptions to
follow, the data referred to are stored in the Value field. The follow, the data referred to are stored in the Value field. The
Value Length field specifies the length of the data in the Value Value Length field specifies the length of the data in the Value
field. field.
10.1. No-Operation 10.1. No-Operation
A No-operation request (Code 0) does nothing except return an empty A No-operation request (Code 0) does nothing except return an empty
response which can be used as a crypto-ping. response, which can be used as a crypto-ping.
10.2. Association Message (ASSOC) 10.2. Association Message (ASSOC)
An Association Message (Code 1) is used in the parameter exchange to An Association Message (Code 1) is used in the parameter exchange to
obtain the host name and status word. The request contains the obtain the host name and status word. The request contains the
client status word in the Filestamp field and the Autokey host name client status word in the Filestamp field and the Autokey host name
in the Value field. The response contains the server status word in in the Value field. The response contains the server status word in
the Filestamp field and the Autokey host name in the Value field. the Filestamp field and the Autokey host name in the Value field.
The Autokey host name is not necessarily the DNS host name. A valid The Autokey host name is not necessarily the DNS host name. A valid
response lights the ENAB bit and possibly others in the association response lights the ENAB bit and possibly others in the association
status word. status word.
When multiple identity schemes are supported, the host status word When multiple identity schemes are supported, the host status word
determine which ones are available. In server and symmetric modes determines which ones are available. In server and symmetric modes,
the response status word contains bits corresponding to the supported the response status word contains bits corresponding to the supported
schemes. In all modes the scheme is selected based on the client schemes. In all modes, the scheme is selected based on the client
identity parameters which are loaded at startup. identity parameters that are loaded at startup.
10.3. Certificate Message (CERT) 10.3. Certificate Message (CERT)
A Certificate Message (Code 2) is used in the certificate exchange to A Certificate Message (Code 2) is used in the certificate exchange to
obtain a certificate by subject name. The request contains the obtain a certificate by subject name. The request contains the
subject name; the response contains the certificate encoded in X.509 subject name; the response contains the certificate encoded in X.509
format with ASN.1 syntax as described in Appendix H. format with ASN.1 syntax as described in Appendix H.
If the subject name in the response does not match the issuer name, If the subject name in the response does not match the issuer name,
the exchange continues with the issuer name replacing the subject the exchange continues with the issuer name replacing the subject
skipping to change at page 27, line 10 skipping to change at page 27, line 24
The Autokey Message (Code 4) is used to obtain the autokey values. The Autokey Message (Code 4) is used to obtain the autokey values.
The request contains no value for a client or the autokey values for The request contains no value for a client or the autokey values for
a symmetric peer. The response contains two 32-bit words, the first a symmetric peer. The response contains two 32-bit words, the first
is the final key ID, while the second is the index of the final key is the final key ID, while the second is the index of the final key
ID. A valid response lights the AUTO bit in the association status ID. A valid response lights the AUTO bit in the association status
word. word.
10.6. Leapseconds Values Message (LEAP) 10.6. Leapseconds Values Message (LEAP)
The Leapseconds Values Message (Cpde 5) is used to obtain the The Leapseconds Values Message (Code 5) is used to obtain the
leapseconds values as parsed from the leapseconds table from NIST. leapseconds values as parsed from the leapseconds table from the
The request contains no values. The response contains three 32-bit National Institute of Standards and Technology (NIST). The request
integers: first the NTP seconds of the latest leap event followed by contains no values. The response contains three 32-bit integers:
the NTP seconds when the latest NIST table expires and then the TAI first the NTP seconds of the latest leap event followed by the NTP
offset following the leap event. A valid response lights the LEAP seconds when the latest NIST table expires and then the TAI offset
bit in the association status word. following the leap event. A valid response lights the LEAP bit in
the association status word.
10.7. Sign Message (SIGN) 10.7. Sign Message (SIGN)
The Sign Message (Code 6) requests the server to sign and return a The Sign Message (Code 6) requests that the server sign and return a
certificate presented in the request. The request contains the certificate presented in the request. The request contains the
client certificate encoded in X.509 format with ASN.1 syntax as client certificate encoded in X.509 format with ASN.1 syntax as
described in Appendix H. The response contains the client described in Appendix H. The response contains the client
certificate signed by the server private key. A valid response certificate signed by the server private key. A valid response
lights the SIGN bit in the association status word. lights the SIGN bit in the association status word.
10.8. Identity Messages (IFF, GQ, MV) 10.8. Identity Messages (IFF, GQ, MV)
The Identity Messages (Code 7 (IFF), 8 (GQ), or 9 (MV)) contains the The Identity Messages (Code 7 (IFF), 8 (GQ), or 9 (MV)) contains the
client challenge, usually a 160- or 512-bit nonce. The response client challenge, usually a 160- or 512-bit nonce. The response
skipping to change at page 27, line 45 skipping to change at page 28, line 14
11. Autokey State Machine 11. Autokey State Machine
This section describes the formal model of the Autokey state machine, This section describes the formal model of the Autokey state machine,
its state variables and the state transition functions. its state variables and the state transition functions.
11.1. Status Word 11.1. Status Word
The server implements a host status word, while each client The server implements a host status word, while each client
implements an association status word. These words have the format implements an association status word. These words have the format
and content shown in Figure 8. The low order 16 bits of the status and content shown in Figure 8. The low-order 16 bits of the status
word define the state of the Autokey dance, while the high order 16 word define the state of the Autokey dance, while the high-order 16
bits specify the Numerical Identifier (NID) as generated by the bits specify the Numerical Identifier (NID) as generated by the
OpenSSL library of the OID for one of the message digest/signature OpenSSL library of the OID for one of the message digest/signature
encryption schemes defined in [RFC3279]. The NID values for the encryption schemes defined in [RFC3279]. The NID values for the
digest/signature algorithms defined in RFC 3279 are as follows: digest/signature algorithms defined in RFC 3279 are as follows:
+------------------------+----------------------+-----+ +------------------------+----------------------+-----+
| Algorithm | OID | NID | | Algorithm | OID | NID |
+------------------------+----------------------+-----+ +------------------------+----------------------+-----+
| pkcs-1 | 1.2.840.113549.1.1 | 2 | | pkcs-1 | 1.2.840.113549.1.1 | 2 |
| md2 | 1.2.840.113549.2.2 | 3 | | md2 | 1.2.840.113549.2.2 | 3 |
skipping to change at page 28, line 21 skipping to change at page 28, line 37
| rsaEncryption | 1.2.840.113549.1.1.1 | 6 | | rsaEncryption | 1.2.840.113549.1.1.1 | 6 |
| md2WithRSAEncryption | 1.2.840.113549.1.1.2 | 7 | | md2WithRSAEncryption | 1.2.840.113549.1.1.2 | 7 |
| md5WithRSAEncryption | 1.2.840.113549.1.1.4 | 8 | | md5WithRSAEncryption | 1.2.840.113549.1.1.4 | 8 |
| id-sha1 | 1.3.14.3.2.26 | 64 | | id-sha1 | 1.3.14.3.2.26 | 64 |
| sha-1WithRSAEncryption | 1.2.840.113549.1.1.5 | 65 | | sha-1WithRSAEncryption | 1.2.840.113549.1.1.5 | 65 |
| id-dsa-wth-sha1 | 1.2.840.10040.4.3 | 113 | | id-dsa-wth-sha1 | 1.2.840.10040.4.3 | 113 |
| id-dsa | 1.2.840.10040.4.1 | 116 | | id-dsa | 1.2.840.10040.4.1 | 116 |
+------------------------+----------------------+-----+ +------------------------+----------------------+-----+
Bits 24-31 are reserved for server use, while bits 16-23 are reserved Bits 24-31 are reserved for server use, while bits 16-23 are reserved
for client use. In the host portion bits 24-27 specify the available for client use. In the host portion, bits 24-27 specify the
identity schemes, while bits 28-31 specify the server capabilities. available identity schemes, while bits 28-31 specify the server
There are two additional bits implemented separately. capabilities. There are two additional bits implemented separately.
1 2 3 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 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 | | Digest / Signature NID | Client | Ident | Host |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 8: Status Word Figure 8: Status Word
The host status word is included in the ASSOC request and response The host status word is included in the ASSOC request and response
messages. The client copies this word to the association status word messages. The client copies this word to the association status word
and then lights additional bits as the dance proceeds. Once enabled, and then lights additional bits as the dance proceeds. Once enabled,
these bits ordinarily never come dark unless a general reset occurs these bits ordinarily never become dark unless a general reset occurs
and the protocol is restarted from the beginning. and the protocol is restarted from the beginning.
The host status bits are defined as follows: The host status bits are defined as follows:
o ENAB (31) Lit if the server implements the Autokey protocol. o ENAB (31) is lit if the server implements the Autokey protocol.
o LVAL (30) Lit if the server has installed leapseconds values, o LVAL (30) is lit if the server has installed leapseconds values,
either from the NIST leapseconds file or from another server. either from the NIST leapseconds file or from another server.
o Bits (28-29) are reserved - always dark. o Bits (28-29) are reserved - always dark.
o Bits 24-27 select which server identity schemes are available. o Bits 24-27 select which server identity schemes are available.
While specific coding for various schemes is yet to be determined, While specific coding for various schemes is yet to be determined,
the schemes available in the reference implementation and the schemes available in the reference implementation and
described in Appendix B include the following: described in Appendix B include the following:
* none - Trusted Certificate (TC) Scheme (default). * none - Trusted Certificate (TC) Scheme (default).
* PC (27) Private Certificate Scheme. * PC (27) Private Certificate Scheme.
* IFF (26) Schnorr aka Identify-Friendly-or-Foe Scheme. * IFF (26) Schnorr aka Identify-Friendly-or-Foe Scheme.
* GQ (25) Guillard-Quisquater Scheme. * GQ (25) Guillard-Quisquater Scheme.
* MV (24) Mu-Varadharajan Scheme. * MV (24) Mu-Varadharajan Scheme.
o The PC scheme is exclusive of any other scheme. Otherwise, the o The PC scheme is exclusive of any other scheme. Otherwise, the
IFF, GQ and MV bits can be enabled in any combination. IFF, GQ, and MV bits can be enabled in any combination.
The association status bits are defined as follows: The association status bits are defined as follows:
o CERT (23) Lit when the trusted host certificate and public key are o CERT (23): Lit when the trusted host certificate and public key
validated. are validated.
o VRFY (22) Lit when the trusted host identity credentials are o VRFY (22): Lit when the trusted host identity credentials are
confirmed. confirmed.
o PROV (21) Lit when the server signature is verified using its o PROV (21): Lit when the server signature is verified using its
public key and identity credentials. Also called the proventic public key and identity credentials. Also called the proventic
bit elsewhere in this memo. When enabled, signed values in bit elsewhere in this memo. When enabled, signed values in
subsequent messages are presumed proventic. subsequent messages are presumed proventic.
o COOK (20) Lit when the cookie is received and validated. When o COOK (20): Lit when the cookie is received and validated. When
lit, key lists with nonzero cookies are generated; when dim, the lit, key lists with nonzero cookies are generated; when dim, the
cookie is zero. cookie is zero.
o AUTO (19) Lit when the autokey values are received and validated. o AUTO (19): Lit when the autokey values are received and validated.
When lit, clients can validate packets without extension fields When lit, clients can validate packets without extension fields
according to the autokey sequence. according to the autokey sequence.
o SIGN (18) Lit when the host certificate is signed by the server. o SIGN (18): Lit when the host certificate is signed by the server.
o LEAP (17) Lit when the leapseconds values are received and o LEAP (17): Lit when the leapseconds values are received and
validated. validated.
o Bit 16 is reserved - always dark. o Bit 16: Reserved - always dark.
There are three additional bits: LIST, SYNC and PEER not included in There are three additional bits: LIST, SYNC, and PEER not included in
the association status word. LIST is lit when the key list is the association status word. LIST is lit when the key list is
regenerated and dim when the autokey values have been transmitted. regenerated and dim when the autokey values have been transmitted.
This is necessary to avoid livelock under some conditions. SYNC is This is necessary to avoid livelock under some conditions. SYNC is
lit when the client has synchronized to a proventic source and never lit when the client has synchronized to a proventic source and never
dim after that. PEER is lit when the server has synchronized, as dim after that. PEER is lit when the server has synchronized, as
indicated in the NTP header, and never dim after that. indicated in the NTP header, and never dim after that.
11.2. Host State Variables 11.2. Host State Variables
Following is a list of host state variables. The following is a list of host state variables.
Host Name - The name of the host, by default the string returned by Host Name: The name of the host, by default the string
the Unix gethostname() library function. In the reference returned by the Unix gethostname() library
implementation this is a configurable value. function. In the reference implementation, this
is a configurable value.
Host Status Word - This word is initialized when the host first Host Status Word: This word is initialized when the host first
starts up. The format is described above. starts up. The format is described above.
Host Key - The RSA public/private key pair used to encrypt/decrypt Host Key: The RSA public/private key pair used to encrypt/
cookies. This is also the default sign key. decrypt cookies. This is also the default sign
key.
Sign Key - The RSA or DSA public/private key pair used to encrypt/ Sign Key: The RSA or Digital Signature Algorithm (DSA)
decrypt signatures when the host key is not used for this purpose. public/private key pair used to encrypt/decrypt
signatures when the host key is not used for
this purpose.
Sign Digest - The message digest algorithm used to compute the Sign Digest: The message digest algorithm used to compute the
message digest before encryption. message digest before encryption.
IFF Parameters - The parameters used in the optional IFF identity IFF Parameters: The parameters used in the optional IFF identity
scheme described in Appendix B. scheme described in Appendix B.
GQ Parameters - The parameters used in the optional GQ identity GQ Parameters: The parameters used in the optional GQ identity
scheme described in Appendix B. scheme described in Appendix B.
MV Parameters - The parameters used in the optional MV identity MV Parameters: The parameters used in the optional MV identity
scheme described in Appendix B. scheme described in Appendix B.
Server Seed - The private value hashed with the IP addresses and key Server Seed: The private value hashed with the IP addresses
identifier to construct the cookie. and key identifier to construct the cookie.
Certificate Information Structure (CIS) - This structure includes CIS: Certificate Information Structure. This
certain information fields from an X.509v3 certificate, together with structure includes certain information fields
the certificate itself. The fields extracted include the subject and from an X.509v3 certificate, together with the
issuer names, subject public key and message digest algorithm certificate itself. The fields extracted
(pointers), and the beginning and end of the valid period in NTP include the subject and issuer names, subject
seconds. public key and message digest algorithm
(pointers), and the beginning and end of the
valid period in NTP seconds.
The certificate itself is stored as an extension field in network The certificate itself is stored as an extension
byte order so it can be copied intact to the message. The structure field in network byte order so it can be copied
is signed using the sign key and carries the public values timestamp intact to the message. The structure is signed
at signature time and the filestamp of the original certificate file. using the sign key and carries the public values
The structure is used by the CERT response message and SIGN request timestamp at signature time and the filestamp of
and response messages. the original certificate file. The structure is
used by the CERT response message and SIGN
request and response messages.
A flags field in the CIS determines the status of the certificate. A flags field in the CIS determines the status
The field is encoded as follows: of the certificate. The field is encoded as
follows:
o TRUST (0x01) - The certificate has been signed by a trusted * TRUST (0x01) - The certificate has been
issuer. If the certificate is self-signed and contains signed by a trusted issuer. If the
"trustRoot" in the Extended Key Usage field, this bit is lit when certificate is self-signed and contains
the CIS is constructed. "trustRoot" in the Extended Key Usage field,
this bit is lit when the CIS is constructed.
o SIGN (0x02) - The certificate signature has been verified. If the * SIGN (0x02) - The certificate signature has
certificate is self-signed and verified using the contained public been verified. If the certificate is self-
key, this bit is lit when the CIS is constructed. signed and verified using the contained
public key, this bit is lit when the CIS is
constructed.
o VALID (0x04) - The certificate is valid and can be used to verify * VALID (0x04) - The certificate is valid and
signatures. This bit is lit when a trusted certificate has been can be used to verify signatures. This bit
found on a valid certificate trail. is lit when a trusted certificate has been
found on a valid certificate trail.
o PRIV (0x08) - The certificate is private and not to be revealed. * PRIV (0x08) - The certificate is private and
If the certificate is self-signed and contains "Private" in the not to be revealed. If the certificate is
Extended Key Usage field, this bit is lit when the CIS is self-signed and contains "Private" in the
constructed. Extended Key Usage field, this bit is lit
when the CIS is constructed.
o ERROR (0x80) - The certificate is defective and not to be used in * ERROR (0x80) - The certificate is defective
any way. and not to be used in any way.
Certificate List - CIS structures are stored on the certificate list Certificate List: CIS structures are stored on the certificate
in order of arrival, with the most recently received CIS placed first list in order of arrival, with the most recently
on the list. The list is initialized with the CIS for the host received CIS placed first on the list. The list
certificate, which is read from the host certificate file. is initialized with the CIS for the host
Additional CIS entries are added to the list as certificates are certificate, which is read from the host
obtained from the servers during the certificate exchange. CIS certificate file. Additional CIS entries are
entries are discarded if overtaken by newer ones. added to the list as certificates are obtained
from the servers during the certificate
exchange. CIS entries are discarded if
overtaken by newer ones.
The following values are stored as an extension field structure in The following values are stored as an extension
network byte order so they can be copied intact to the message. They field structure in network byte order so they
are used to send some Autokey requests and responses. All but the can be copied intact to the message. They are
Host Name Values structure are signed using the sign key and all used to send some Autokey requests and
carry the public values timestamp at signature time. responses. All but the Host Name Values
structure are signed using the sign key and all
carry the public values timestamp at signature
time.
Host Name Values. This is used to send ASSOC request and response Host Name Values: This is used to send ASSOC request and response
messages. It contains the host status word and host name. messages. It contains the host status word and
host name.
Public Key Values - This is used to send the COOKIE request message. Public Key Values: This is used to send the COOKIE request message.
It contains the public encryption key used for the COOKIE response It contains the public encryption key used for
message. the COOKIE response message.
Leapseconds Values. This is used to send the LEAP response message. Leapseconds Values: This is used to send the LEAP response message.
In contains the leapseconds values in the LEAP message description. It contains the leapseconds values in the LEAP
message description.
11.3. Client State Variables (all modes) 11.3. Client State Variables (all modes)
Following is a list of state variables used by the various dances in The following is a list of state variables used by the various dances
all modes. in all modes.
Association ID - The association ID used in responses. It is Association ID: The association ID used in responses. It
assigned when the association is mobilized. is assigned when the association is
mobilized.
Association Status Word - The status word copied from the ASSOC Association Status Word: The status word copied from the ASSOC
response; subsequently modified by the state machine. response; subsequently modified by the
state machine.
Subject Name - The server host name copied from the ASSOC response. Subject Name: The server host name copied from the ASSOC
response.
Issuer Name - The host name signing the certificate. It is extracted Issuer Name: The host name signing the certificate. It
from the current server certificate upon arrival and used to request is extracted from the current server
the next host on the certificate trail. certificate upon arrival and used to
request the next host on the certificate
trail.
Server Public Key - The public key used to decrypt signatures. It is Server Public Key: The public key used to decrypt signatures.
extracted from the server host certificate. It is extracted from the server host
certificate.
Server Message Digest - The digest/signature scheme determined in the Server Message Digest: The digest/signature scheme determined in
parameter exchange. the parameter exchange.
Group Key - A set of values used by the identity exchange. It Group Key: A set of values used by the identity
identifies the cryptographic compartment shared by the server and exchange. It identifies the cryptographic
client. compartment shared by the server and
client.
Receive Cookie Values - The cookie returned in a COOKIE response, Receive Cookie Values: The cookie returned in a COOKIE response,
together with its timestamp and filestamp together with its timestamp and filestamp.
Receive Autokey Values - The autokey values returned in an AUTO Receive Autokey Values: The autokey values returned in an AUTO
response, together with its timestamp and filestamp. response, together with its timestamp and
filestamp.
Send Autokey Values - The autokey values with signature and Send Autokey Values: The autokey values with signature and
timestamps. timestamps.
Key List - A sequence of key IDs starting with the autokey seed and Key List: A sequence of key IDs starting with the
each pointing to the next. It is computed, timestamped and signed at autokey seed and each pointing to the next.
the next poll opportunity when the key list becomes empty. It is computed, timestamped, and signed at
the next poll opportunity when the key list
becomes empty.
Current Key Number - The index of the entry on the Key List to be Current Key Number: The index of the entry on the Key List to
used at the next poll opportunity. be used at the next poll opportunity.
11.4. Protocol State Transitions 11.4. Protocol State Transitions
The protocol state machine is very simple but robust. The state is The protocol state machine is very simple but robust. The state is
determined by the client status word bits defined above. The state determined by the client status word bits defined above. The state
transitions of the three dances are shown below. The capitalized transitions of the three dances are shown below. The capitalized
truth values represent the client status bits. All bits are truth values represent the client status bits. All bits are
initialized dark and are lit upon the arrival of a specific response initialized as dark and are lit upon the arrival of a specific
message as detailed above. response message as detailed above.
11.4.1. Server Dance 11.4.1. Server Dance
The server dance begins when the client sends an ASSOC request to the The server dance begins when the client sends an ASSOC request to the
server. The clock is updated when PREV is lit and the dance ends server. The clock is updated when PREV is lit and the dance ends
when LEAP is lit. In this dance the autokey values are not used, so when LEAP is lit. In this dance, the autokey values are not used, so
an autokey exchange is not necessary. Note that the SIGN and LEAP an autokey exchange is not necessary. Note that the SIGN and LEAP
requests are not issued until the client has synchronized to a requests are not issued until the client has synchronized to a
proventic source. Subsequent packets without extension fields are proventic source. Subsequent packets without extension fields are
validated by the autokey sequence. This example and others assumes validated by the autokey sequence. This example and others assumes
the IFF identity scheme has been selected in the parameter exchange.. the IFF identity scheme has been selected in the parameter exchange.
1 while (1) { 1 while (1) {
2 wait_for_next_poll; 2 wait_for_next_poll;
3 make_NTP_header; 3 make_NTP_header;
4 if (response_ready) 4 if (response_ready)
5 send_response; 5 send_response;
6 if (!ENB) /* parameter exchange */ 6 if (!ENB) /* parameter exchange */
7 ASSOC_request; 7 ASSOC_request;
8 else if (!CERT) /* certificate exchange */ 8 else if (!CERT) /* certificate exchange */
9 CERT_request(Host_Name); 9 CERT_request(Host_Name);
10 else if (!IFF) /* identity exchange */ 10 else if (!IFF) /* identity exchange */
11 IFF_challenge; 11 IFF_challenge;
12 else if (!COOK) /* cookie exchange */ 12 else if (!COOK) /* cookie exchange */
13 COOKIE_request; 13 COOKIE_request;
14 else if (!SYNC) /* wait for synchronization */ 14 else if (!SYNC) /* wait for synchronization */
15 continue; 15 continue;
16 else if (!SIGN) /* sign exchange */ 16 else if (!SIGN) /* sign exchange */
17 SIGN_request(Host_Certificate); 17 SIGN_request(Host_Certificate);
18 else if (!LEAP) /* leapsecond values exchange */ 18 else if (!LEAP) /* leapsecond values exchange */
19 LEAP_request; 19 LEAP_request;
20 send packet; 20 send packet;
21 } 21 }
Figure 9: Server Dance Figure 9: Server Dance
If the server refreshes the private seed, the cookie becomes invalid. If the server refreshes the private seed, the cookie becomes invalid.
The server responds to an invalid cookie with a crypto_NAK message, The server responds to an invalid cookie with a crypto-NAK message,
which causes the client to restart the protocol from the beginning. which causes the client to restart the protocol from the beginning.
11.4.2. Broadcast Dance 11.4.2. Broadcast Dance
The broadcast dance is similar to the server dance with the cookie The broadcast dance is similar to the server dance with the cookie
exchange replaced by the autokey values exchange. The broadcast exchange replaced by the autokey values exchange. The broadcast
dance begins when the client receives a broadcast packet including an dance begins when the client receives a broadcast packet including an
ASSOC response with the server association ID. This mobilizes a ASSOC response with the server association ID. This mobilizes a
client association in order to proventicate the source and calibrate client association in order to proventicate the source and calibrate
the propagation delay. The dance ends when the LEAP bit is lit, the propagation delay. The dance ends when the LEAP bit is lit,
after which the client sends no further packets. Normally, the after which the client sends no further packets. Normally, the
broadcast server includes an ASSOC response in each transmitted broadcast server includes an ASSOC response in each transmitted
packet. However, when the server generates a new key list, it packet. However, when the server generates a new key list, it
includes an AUTO response instead. includes an AUTO response instead.
In the broadcast dance extension fields are used with every packet, In the broadcast dance, extension fields are used with every packet,
so the cookie is always zero and no cookie exchange is necessary. As so the cookie is always zero and no cookie exchange is necessary. As
in the server dance, the clock is updated when PREV is lit and the in the server dance, the clock is updated when PREV is lit and the
dance ends when LEAP is lit. Note that the SIGN and LEAP requests dance ends when LEAP is lit. Note that the SIGN and LEAP requests
are not issued until the client has synchronized to a proventic are not issued until the client has synchronized to a proventic
source. Subsequent packets without extension fields are validated by source. Subsequent packets without extension fields are validated by
the autokey sequence. the autokey sequence.
1 while (1) {
2 wait_for_next_poll;
3 make_NTP_header;
4 if (response_ready)
5 send_response;
6 if (!ENB) /* parameters exchange */
7 ASSOC_request;
8 else if (!CERT) /* certificate exchange */
9 CERT_request(Host_Name);
10 else if (!IFF) /* identity exchange */
11 IFF_challenge;
12 else if (!AUT) /* autokey values exchange */
13 AUTO_request;
14 else if (!SYNC) /* wait for synchronization */
15 continue;
16 else if (!SIGN) /* sign exchange */
17 SIGN_request(Host_Certificate);
18 else if (!LEAP) /* leapsecond values exchange */
19 LEAP_request;
20 send NTP_packet;
21 }
1 while (1) { Figure 10: Broadcast Dance
2 wait_for_next_poll;
3 make_NTP_header;
4 if (response_ready)
5 send_response;
6 if (!ENB) /* parameters exchange */
7 ASSOC_request;
8 else if (!CERT) /* certificate exchange */
9 CERT_request(Host_Name);
10 else if (!IFF) /* identity exchange */
11 IFF_challenge;
12 else if (!AUT) /* autokey values exchange */
13 AUTO_request;
14 else if (!SYNC) /* wait for synchronization */
15 continue;
16 else if (!SIGN) /* sign exchange */
17 SIGN_request(Host_Certificate);
18 else if (!LEAP) /* leapsecond values exchange */
19 LEAP_request;
20 send NTP_packet;
21 }
Figure 10: Broadcast Dance
If a packet is lost and the autokey sequence is broken, the client If a packet is lost and the autokey sequence is broken, the client
hashes the current autokey until either it matches the previous hashes the current autokey until either it matches the previous
autokey or the number of hashes exceeds the count given in the autokey or the number of hashes exceeds the count given in the
autokey values. If the latter, the client sends an AUTO request to autokey values. If the latter, the client sends an AUTO request to
retrieve the autokey values. If the client receives a crypto-NAK retrieve the autokey values. If the client receives a crypto-NAK
during the dance, or if the association ID changes, the client during the dance, or if the association ID changes, the client
restarts the protocol from the beginning. restarts the protocol from the beginning.
11.4.3. Symmetric Dance 11.4.3. Symmetric Dance
The symmetric dance is intricately choreographed. It begins when the The symmetric dance is intricately choreographed. It begins when the
active peer sends an ASSOC request to the passive peer. The passive active peer sends an ASSOC request to the passive peer. The passive
peer mobilizes an association and both peers step a three-way dance peer mobilizes an association and both peers step a three-way dance
where each peer completes a parameter exchange with the other. Until where each peer completes a parameter exchange with the other. Until
one of the peers has synchronized to a proventic source (which could one of the peers has synchronized to a proventic source (which could
be the other peer) and can sign messages, the other peer loops be the other peer) and can sign messages, the other peer loops
waiting for a valid timestamp in the ensuing CERT response. waiting for a valid timestamp in the ensuing CERT response.
1 while (1) { 1 while (1) {
2 wait_for_next_poll; 2 wait_for_next_poll;
3 make_NTP_header; 3 make_NTP_header;
4 if (!ENB) /* parameters exchange */ 4 if (!ENB) /* parameters exchange */
5 ASSOC_request; 5 ASSOC_request;
6 else if (!CERT) /* certificate exchange */ 6 else if (!CERT) /* certificate exchange */
7 CERT_request(Host_Name); 7 CERT_request(Host_Name);
8 else if (!IFF) /* identity exchange */ 8 else if (!IFF) /* identity exchange */
9 IFF_challenge; 9 IFF_challenge;
10 else if (!COOK && PEER) /* cookie exchange */ 10 else if (!COOK && PEER) /* cookie exchange */
11 COOKIE_request); 11 COOKIE_request);
12 else if (!AUTO) /* autokey values exchange */ 12 else if (!AUTO) /* autokey values exchange */
13 AUTO_request; 13 AUTO_request;
14 else if (LIST) /* autokey values response */ 14 else if (LIST) /* autokey values response */
15 AUTO_response; 15 AUTO_response;
16 else if (!SYNC) /* wait for synchronization */ 16 else if (!SYNC) /* wait for synchronization */
17 continue; 17 continue;
18 else if (!SIGN) /* sign exchange */ 18 else if (!SIGN) /* sign exchange */
19 SIGN_request; 19 SIGN_request;
20 else if (!LEAP) /* leapsecond values exchange */ 20 else if (!LEAP) /* leapsecond values exchange */
21 LEAP_request; 21 LEAP_request;
22 send NTP_packet; 22 send NTP_packet;
23 } 23 }
Figure 11: Symmetric Dance Figure 11: Symmetric Dance
Once a peer has synchronized to a proventic source, it includes Once a peer has synchronized to a proventic source, it includes
timestamped signatures in its messages. The other peer, which has timestamped signatures in its messages. The other peer, which has
been stalled waiting for valid timestamps, now mates the dance. It been stalled waiting for valid timestamps, now mates the dance. It
retrives the now nonzero cookie using a cookie exchange and then the retrieves the now nonzero cookie using a cookie exchange and then the
updated autokey values using an autokey exchange. updated autokey values using an autokey exchange.
As in the broadcast dance, if a packet is lost and the autokey As in the broadcast dance, if a packet is lost and the autokey
sequence broken, the peer hashes the current autokey until either it sequence broken, the peer hashes the current autokey until either it
matches the previous autokey or the number of hashes exceeds the matches the previous autokey or the number of hashes exceeds the
count given in the autokey values. If the latter, the client sends count given in the autokey values. If the latter, the client sends
an AUTO request to retrive the autokey values. If the peer receives an AUTO request to retrieve the autokey values. If the peer receives
a crypto-NAK during the dance, or if the association ID changes, the a crypto-NAK during the dance, or if the association ID changes, the
peer restarts the protocol from the beginning. peer restarts the protocol from the beginning.
11.5. Error Recovery 11.5. Error Recovery
The Autokey protocol state machine includes provisions for various The Autokey protocol state machine includes provisions for various
kinds of error conditions that can arise due to missing files, kinds of error conditions that can arise due to missing files,
corrupted data, protocol violations and packet loss or misorder, not corrupted data, protocol violations, and packet loss or misorder, not
to mention hostile intrusion. This section describes how the to mention hostile intrusion. This section describes how the
protocol responds to reachability and timeout events which can occur protocol responds to reachability and timeout events that can occur
due to such errors. due to such errors.
A persistent NTP association is mobilized by an entry in the A persistent NTP association is mobilized by an entry in the
configuration file, while an ephemeral association is mobilized upon configuration file, while an ephemeral association is mobilized upon
the arrival of a broadcast or symmetric active packet with no the arrival of a broadcast or symmetric active packet with no
matching association. Subsequently, a general reset reinitializes matching association. Subsequently, a general reset reinitializes
all association variables to the initial state when first mobilized. all association variables to the initial state when first mobilized.
In addition, if the association is ephemeral, the association is In addition, if the association is ephemeral, the association is
demobilized and all resources acquired are returned to the system. demobilized and all resources acquired are returned to the system.
Every NTP association has two variables which maintain the liveness Every NTP association has two variables that maintain the liveness
state of the protocol, the 8-bit reach register and the unreach state of the protocol, the 8-bit reach register and the unreach
counter defined in [I-D.ietf-ntp-ntpv4-proto]. At every poll counter defined in [RFC5905]. At every poll interval, the reach
interval the reach register is shifted left, the low order bit is register is shifted left, the low order bit is dimmed and the high
dimmed and the high order bit is lost. At the same time the unreach order bit is lost. At the same time, the unreach counter is
counter is incremented by one. If an arriving packet passes all incremented by one. If an arriving packet passes all authentication
authentication and sanity checks, the rightmost bit of the reach and sanity checks, the rightmost bit of the reach register is lit and
register is lit and the unreach counter is set to zero. If any bit the unreach counter is set to zero. If any bit in the reach register
in the reach register is lit, the server is reachable, otherwise it is lit, the server is reachable; otherwise, it is unreachable.
is unreachable.
When the first poll is sent from an association, the reach register When the first poll is sent from an association, the reach register
and unreach counter are set to zero. If the unreach counter reaches and unreach counter are set to zero. If the unreach counter reaches
16, the poll interval is doubled. In addition, if association is 16, the poll interval is doubled. In addition, if association is
persistent, it is demobilized. This reduces the network load for persistent, it is demobilized. This reduces the network load for
packets that are unlikely to elicit a response. packets that are unlikely to elicit a response.
At each state in the protocol the client expects a particular At each state in the protocol, the client expects a particular
response from the server. A request is included in the NTP packet 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 sent at each poll interval until a valid response is received or a
general reset occurs, in which case the protocol restarts from the general reset occurs, in which case the protocol restarts from the
beginning. A general reset also occurs for an association when an beginning. A general reset also occurs for an association when an
unrecoverable protocol error occurs. A general reset occurs for all unrecoverable protocol error occurs. A general reset occurs for all
associations when the system clock is first synchronized or the clock associations when the system clock is first synchronized or the clock
is stepped or when the server seed is refreshed. is stepped or when the server seed is refreshed.
There are special cases designed to quickly respond to broken There are special cases designed to quickly respond to broken
associations, such as when a server restarts or refreshes keys. associations, such as when a server restarts or refreshes keys.
skipping to change at page 37, line 16 skipping to change at page 39, line 4
legitimate or the result of intruder mischief. In order to reduce legitimate or the result of intruder mischief. In order to reduce
the vulnerability in such cases, the crypto-NAK, as well as all the vulnerability in such cases, the crypto-NAK, as well as all
responses, is believed only if the result of a previous packet sent responses, is believed only if the result of a previous packet sent
by the client and not a replay, as confirmed by the NTP on-wire by the client and not a replay, as confirmed by the NTP on-wire
protocol. While this defense can be easily circumvented by a man-in- protocol. While this defense can be easily circumvented by a man-in-
the-middle, it does deflect other kinds of intruder warfare. the-middle, it does deflect other kinds of intruder warfare.
There are a number of situations where some event happens that causes There are a number of situations where some event happens that causes
the remaining autokeys on the key list to become invalid. When one the remaining autokeys on the key list to become invalid. When one
of these situations happens, the key list and associated autokeys in of these situations happens, the key list and associated autokeys in
the key cache are purged. A new key list, signature and timestamp the key cache are purged. A new key list, signature, and timestamp
are generated when the next NTP message is sent, assuming there is are generated when the next NTP message is sent, assuming there is
one. Following is a list of these situations: one. The following is a list of these situations:
1. When the cookie value changes for any reason. 1. When the cookie value changes for any reason.
2. When the poll interval is changed. In this case the calculated 2. When the poll interval is changed. In this case, the calculated
expiration times for the keys become invalid. expiration times for the keys become invalid.
3. If a problem is detected when an entry is fetched from the key 3. If a problem is detected when an entry is fetched from the key
list. This could happen if the key was marked non-trusted or list. This could happen if the key was marked non-trusted or
timed out, either of which implies a software bug. timed out, either of which implies a software bug.
12. Security Considerations 12. Security Considerations
This section discusses the most obvious security vulnerabilities in This section discusses the most obvious security vulnerabilities in
the various Autokey dances. In the following discussion the the various Autokey dances. In the following discussion, the
cryptographic algorithms and private values themselves are assumed cryptographic algorithms and private values themselves are assumed
secure; that is, a brute force cryptanalytic attack will not reveal secure; that is, a brute force cryptanalytic attack will not reveal
the host private key, sign private key, cookie value, identity the host private key, sign private key, cookie value, identity
parameters, server seed or autokey seed. In addition, an intruder parameters, server seed or autokey seed. In addition, an intruder
will not be able to predict random generator values. will not be able to predict random generator values.
12.1. Protocol Vulnerability 12.1. Protocol Vulnerability
While the protocol has not been subjected to a formal analysis, a few While the protocol has not been subjected to a formal analysis, a few
preliminary assertions can be made. In the client/server and preliminary assertions can be made. In the client/server and
symmetric dances the underlying NTP on-wire protocol is resistant to symmetric dances, the underlying NTP on-wire protocol is resistant to
lost, duplicate and bogus packets, even if the clock is not lost, duplicate, and bogus packets, even if the clock is not
synchronized, so the protocol is not vulnerable to a wiretapper synchronized, so the protocol is not vulnerable to a wiretapper
attack. The on-wire protocol is resistant to replays of both the attack. The on-wire protocol is resistant to replays of both the
client request packet and the server reply packet. A man-in-the- client request packet and the server reply packet. A man-in-the-
middle attack, even if it could simulate a valid cookie, could not middle attack, even if it could simulate a valid cookie, could not
prove identity. prove identity.
In the broadcast dance the client begins with a volley in client/ In the broadcast dance, the client begins with a volley in client/
server mode to obtain the autokey values and signature, so has the server mode to obtain the autokey values and signature, so has the
same protection as in that mode. When continuing in receive-only same protection as in that mode. When continuing in receive-only
mode, a wiretapper cannot produce a key list with valid signed mode, a wiretapper cannot produce a key list with valid signed
autokey values. If it replays an old packet, the client will reject autokey values. If it replays an old packet, the client will reject
it by the timestamp check. The most it can do is manufacture a it by the timestamp check. The most it can do is manufacture a
future packet causing clients to repeat the autokey hash operations future packet causing clients to repeat the autokey hash operations
until exceeding the maximum key number. If this happens the until exceeding the maximum key number. If this happens the
broadcast client temporarily reverts to client mode to refresh the broadcast client temporarily reverts to client mode to refresh the
autokey values. autokey values.
By assumption, a man-in-the-middle attacker that intercepts a packet By assumption, a man-in-the-middle attacker that intercepts a packet
cannot break the wire or delay an intercepted packet. If this cannot break the wire or delay an intercepted packet. If this
assumption is removed, the middleman could intercept a broadcast assumption is removed, the middleman could intercept a broadcast
packet and replace the data and message digest without detection by packet and replace the data and message digest without detection by
the clients. the clients.
As mentioned previously in this memo, the TC identity scheme is As mentioned previously in this memo, the TC identity scheme is
vulnerable to a man-in-the-middle attack where an intruder could vulnerable to a man-in-the-middle attack where an intruder could
create a bogus certificate trail. To foil this kind of attack, create a bogus certificate trail. To foil this kind of attack,
either the PC, IFF, GQ or MV identity schemes must be used. either the PC, IFF, GQ, or MV identity schemes must be used.
A client instantiates cryptographic variables only if the server is A client instantiates cryptographic variables only if the server is
synchronized to a proventic source. A server does not sign values or synchronized to a proventic source. A server does not sign values or
generate cryptographic data files unless synchronized to a proventic generate cryptographic data files unless synchronized to a proventic
source. This raises an interesting issue: how does a client generate source. This raises an interesting issue: how does a client generate
proventic cryptographic files before it has ever been synchronized to proventic cryptographic files before it has ever been synchronized to
a proventic source? [Who shaves the barber if the barber shaves a proventic source? (Who shaves the barber if the barber shaves
everybody in town who does not shave himself?] In principle, this everybody in town who does not shave himself?) In principle, this
paradox is resolved by assuming the primary (stratum 1) servers are paradox is resolved by assuming the primary (stratum 1) servers are
proventicated by external phenomenological means. proventicated by external phenomenological means.
12.2. Clogging Vulnerability 12.2. Clogging Vulnerability
A self-induced clogging incident cannot happen, since signatures are A self-induced clogging incident cannot happen, since signatures are
computed only when the data have changed and the data do not change computed only when the data have changed and the data do not change
very often. For instance, the autokey values are signed only when very often. For instance, the autokey values are signed only when
the key list is regenerated, which happens about once an hour, while the key list is regenerated, which happens about once an hour, while
the public values are signed only when one of them is updated during the public values are signed only when one of them is updated during
skipping to change at page 39, line 6 skipping to change at page 40, line 44
day. day.
There are two clogging vulnerabilities exposed in the protocol There are two clogging vulnerabilities exposed in the protocol
design: an encryption attack where the intruder hopes to clog the design: an encryption attack where the intruder hopes to clog the
victim server with needless cryptographic calculations, and a victim server with needless cryptographic calculations, and a
decryption attack where the intruder attempts to clog the victim decryption attack where the intruder attempts to clog the victim
client with needless cryptographic calculations. Autokey uses public client with needless cryptographic calculations. Autokey uses public
key cryptography and the algorithms that perform these functions key cryptography and the algorithms that perform these functions
consume significant resources. consume significant resources.
In client/server and peer dances an encryption hazard exists when a In client/server and peer dances, an encryption hazard exists when a
wiretapper replays prior cookie request messages at speed. There is wiretapper replays prior cookie request messages at speed. There is
no obvious way to deflect such attacks, as the server retains no no obvious way to deflect such attacks, as the server retains no
state between requests. Replays of cookie request or response state between requests. Replays of cookie request or response
messages are detected and discarded by the client on-wire protocol. messages are detected and discarded by the client on-wire protocol.
In broadcast mode a client a decryption hazard exists when a In broadcast mode, a decryption hazard exists when a wiretapper
wiretapper replays autokey response messages at speed. Once replays autokey response messages at speed. Once synchronized to a
synchronized to a proventic source, a legitimate extension field with proventic source, a legitimate extension field with timestamp the
timestamp the same as or earlier than the most recently received of same as or earlier than the most recently received of that type is
that type is immediately discarded. This foils a man-in-the-middle immediately discarded. This foils a man-in-the-middle cut-and-paste
cut-and-paste attack using an earlier response, for example. A attack using an earlier response, for example. A legitimate
legitimate extension field with timestamp in the future is unlikely, extension field with timestamp in the future is unlikely, as that
as that would require predicting the autokey sequence. However, this would require predicting the autokey sequence. However, this causes
causes the client to refresh and verify the autokey values and the client to refresh and verify the autokey values and signature.
signature.
A determined attacker can destabilize the on-wire protocol or an A determined attacker can destabilize the on-wire protocol or an
Autokey dance in various ways by replaying old messages before the Autokey dance in various ways by replaying old messages before the
client or peer has synchronized for the first time. For instance, client or peer has synchronized for the first time. For instance,
replaying an old symmetric mode message before the peers have replaying an old symmetric mode message before the peers have
synchronize will prevent the peers from ever synchronizing. synchronize will prevent the peers from ever synchronizing.
Replaying out of order Autokey messages in any mode during a dance Replaying out of order Autokey messages in any mode during a dance
could prevent the dance from ever completing. There is nothing new could prevent the dance from ever completing. There is nothing new
in these kinds of attack; a similar vulnerabily even exists in TCP. in these kinds of attack; a similar vulnerability even exists in TCP.
13. IANA Considerations 13. IANA Consideration
This document has no IANA Actions. The IANA has added the following entries to the NTP Extensions Field
Types registry:
+------------+------------------------------------------+
| Field Type | Meaning |
+------------+------------------------------------------+
| 0x0002 | No-Operation Request |
| 0x8002 | No-Operation Response |
| 0xC002 | No-Operation Error Response |
| 0x0102 | Association Message Request |
| 0x8102 | Association Message Response |
| 0xC102 | Association Message Error Response |
| 0x0202 | Certificate Message Request |
| 0x8202 | Certificate Message Response |
| 0xC202 | Certificate Message Error Response |
| 0x0302 | Cookie Message Request |
| 0x8302 | Cookie Message Response |
| 0xC302 | Cookie Message Error Response |
| 0x0402 | Autokey Message Request |
| 0x8402 | Autokey Message Response |
| 0xC402 | Autokey Message Error Response |
| 0x0502 | Leapseconds Value Message Request |
| 0x8502 | Leapseconds Value Message Response |
| 0xC502 | Leapseconds Value Message Error Response |
| 0x0602 | Sign Message Request |
| 0x8602 | Sign Message Response |
| 0xC602 | Sign Message Error Response |
| 0x0702 | IFF Identity Message Request |
| 0x8702 | IFF Identity Message Response |
| 0xC702 | IFF Identity Message Error Response |
| 0x0802 | GQ Identity Message Request |
| 0x8802 | GQ Identity Message Response |
| 0xC802 | GQ Identity Message Error Response |
| 0x0902 | MV Identity Message Request |
| 0x8902 | MV Identity Message Response |
| 0xC902 | MV Identity Message Error Response |
+------------+------------------------------------------+
14. References 14. References
14.1. Normative References 14.1. Normative References
[I-D.ietf-ntp-ntpv4-proto] [RFC5905] Mills, D., Martin, J., Ed., Burbank, J., and W. Kasch,
Kasch, W., Mills, D., and J. Burbank, "Network Time "Network Time Protocol Version 4: Protocol and Algorithms
Protocol Version 4 Protocol And Algorithms Specification", Specification", RFC 5905, June 2010.
draft-ietf-ntp-ntpv4-proto-13 (work in progress),
October 2009.
14.2. Informative References 14.2. Informative References
[DASBUCH] Mills, D., "Computer Network Time Synchronization - the [DASBUCH] Mills, D., "Computer Network Time Synchronization - the
Network Time Protocol", 2006. Network Time Protocol", 2006.
[GUILLOU] Guillou, L. and J. Quisquatar, "A "paradoxical" identity- [GUILLOU] Guillou, L. and J. Quisquatar, "A "paradoxical" identity-
based signature scheme resulting from zero-knowledge", based signature scheme resulting from zero-knowledge",
1990. 1990.
[MV] Mu, Y. and V. Varadharajan, "Robust and secure [MV] Mu, Y. and V. Varadharajan, "Robust and secure
broadcasting", 2001. broadcasting", 2001.
[RFC1305] Mills, D., "Network Time Protocol (Version 3) [RFC1305] Mills, D., "Network Time Protocol (Version 3)
Specification, Implementation", RFC 1305, March 1992. Specification, Implementation", RFC 1305, March 1992.
[RFC2402] Kent, S. and R. Atkinson, "IP Authentication Header",
RFC 2402, November 1998.
[RFC2406] Kent, S. and R. Atkinson, "IP Encapsulating Security
Payload (ESP)", RFC 2406, November 1998.
[RFC2408] Maughan, D., Schneider, M., and M. Schertler, "Internet
Security Association and Key Management Protocol
(ISAKMP)", RFC 2408, November 1998.
[RFC2412] Orman, H., "The OAKLEY Key Determination Protocol", [RFC2412] Orman, H., "The OAKLEY Key Determination Protocol",
RFC 2412, November 1998. RFC 2412, November 1998.
[RFC2510] Adams, C. and S. Farrell, "Internet X.509 Public Key
Infrastructure Certificate Management Protocols",
RFC 2510, March 1999.
[RFC2522] Karn, P. and W. Simpson, "Photuris: Session-Key Management [RFC2522] Karn, P. and W. Simpson, "Photuris: Session-Key Management
Protocol", RFC 2522, March 1999. Protocol", RFC 2522, March 1999.
[RFC2875] Prafullchandra, H. and J. Schaad, "Diffie-Hellman Proof- [RFC2875] Prafullchandra, H. and J. Schaad, "Diffie-Hellman Proof-
of-Possession Algorithms", RFC 2875, July 2000. of-Possession Algorithms", RFC 2875, July 2000.
[RFC3279] Bassham, L., Polk, W., and R. Housley, "Algorithms and [RFC3279] Bassham, L., Polk, W., and R. Housley, "Algorithms and
Identifiers for the Internet X.509 Public Key Identifiers for the Internet X.509 Public Key
Infrastructure Certificate and Certificate Revocation List Infrastructure Certificate and Certificate Revocation List
(CRL) Profile", RFC 3279, April 2002. (CRL) Profile", RFC 3279, April 2002.
[RFC4210] Adams, C., Farrell, S., Kause, T., and T. Mononen,
"Internet X.509 Public Key Infrastructure Certificate
Management Protocol (CMP)", RFC 4210, September 2005.
[RFC4302] Kent, S., "IP Authentication Header", RFC 4302,
December 2005.
[RFC4303] Kent, S., "IP Encapsulating Security Payload (ESP)",
RFC 4303, December 2005.
[RFC4306] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol",
RFC 4306, December 2005.
[RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S.,
Housley, R., and W. Polk, "Internet X.509 Public Key Housley, R., and W. Polk, "Internet X.509 Public Key
Infrastructure Certificate and Certificate Revocation List Infrastructure Certificate and Certificate Revocation List
(CRL) Profile", RFC 5280, May 2008. (CRL) Profile", RFC 5280, May 2008.
[SCHNORR] Schnorr, C., "Efficient signature generation for smart [SCHNORR] Schnorr, C., "Efficient signature generation for smart
cards", 1991. cards", 1991.
[STINSON] Stinson, D., "Cryptography - Theory and Practice", 1995. [STINSON] Stinson, D., "Cryptography - Theory and Practice", 1995.
Appendix A. Timestamps, Filestamps and Partial Ordering Appendix A. Timestamps, Filestamps, and Partial Ordering
When the host starts, it reads the host key and host certificate When the host starts, it reads the host key and host certificate
files, which are required for continued operation. It also reads the files, which are required for continued operation. It also reads the
sign key and leapseconds values, when available. When reading these sign key and leapseconds values, when available. When reading these
files the host checks the file formats and filestamps for validity; files, the host checks the file formats and filestamps for validity;
for instance, all filestamps must be later than the time the UTC for instance, all filestamps must be later than the time the UTC
timescale was established in 1972 and the certificate filestamp must timescale was established in 1972 and the certificate filestamp must
not be earlier than its associated sign key filestamp. At the time not be earlier than its associated sign key filestamp. At the time
the files are read the host is not synchronized, so it cannot the files are read, the host is not synchronized, so it cannot
determine whether the filestamps are bogus other than these simple determine whether the filestamps are bogus other than by using these
checks. It must not produce filestamps or timestamps until simple checks. It must not produce filestamps or timestamps until
synchronized to a proventic source. synchronized to a proventic source.
In the following the relation A --> B is Lamport's "happens before" In the following, the relation A --> B is Lamport's "happens before"
relation, which is true if event A happens before event B. When relation, which is true if event A happens before event B. When
timestamps are compared to timestamps, the relation is false if A timestamps are compared to timestamps, the relation is false if A
<--> B; that is, false if the events are simultaneous. For <--> B; that is, false if the events are simultaneous. For
timestamps compared to filestamps and filestamps compared to timestamps compared to filestamps and filestamps compared to
filestamps, the relation is true if A <--> B. Note that the current filestamps, the relation is true if A <--> B. Note that the current
time plays no part in these assertions except in (6) below; however, time plays no part in these assertions except in (6) below; however,
the NTP protocol itself insures a correct partial ordering for all the NTP protocol itself ensures a correct partial ordering for all
current time values. current time values.
The following assertions apply to all relevant responses: The following assertions apply to all relevant responses:
1. The client saves the most recent timestamp T0 and filestamp F0 1. The client saves the most recent timestamp T0 and filestamp F0
for the respective signature type. For every received message for the respective signature type. For every received message
carrying timestamp T1 and filestamp F1, the message is discarded carrying timestamp T1 and filestamp F1, the message is discarded
unless T0 --> T1 and F0 --> F1. The requirement that T0 --> T1 unless T0 --> T1 and F0 --> F1. The requirement that T0 --> T1
is the primary defense against replays of old messages. is the primary defense against replays of old messages.
2. For timestamp T and filestamp F, F --> T; that is, the filestamp 2. For timestamp T and filestamp F, F --> T; that is, the filestamp
must happen before the timestamp. If not, this could be due to a must happen before the timestamp. If not, this could be due to a
file generation error or a significant error in the system clock file generation error or a significant error in the system clock
time. time.
3. For sign key filestamp S, certificate filestamp C, cookie 3. For sign key filestamp S, certificate filestamp C, cookie
timestamp D and autokey timestamp A, S --> C --> D --> A; that timestamp D and autokey timestamp A, S --> C --> D --> A; that
is, the autokey must be generated after the cookie, the cookie is, the autokey must be generated after the cookie, the cookie
after the certificate and the certificate after the sign key. after the certificate, and the certificate after the sign key.
4. For sign key filestamp S and certificate filestamp C specifying 4. For sign key filestamp S and certificate filestamp C specifying
begin time B and end time E, S --> C--> B --> E; that is, the begin time B and end time E, S --> C--> B --> E; that is, the
valid period must not be retroactive. valid period must not be retroactive.
5. A certificate for subject S signed by issuer I and with filestamp 5. A certificate for subject S signed by issuer I and with filestamp
C1 obsoletes, but does not necessarily invalidate, another C1 obsoletes, but does not necessarily invalidate, another
certificate with the same subject and issuer but with filestamp certificate with the same subject and issuer but with filestamp
C0, where C0 --> C1. C0, where C0 --> C1.
6. A certificate with begin time B and end time E is invalid and can 6. A certificate with begin time B and end time E is invalid and
not be used to verify signatures if t --> B or E --> t, where t cannot be used to verify signatures if t --> B or E --> t, where
is the current proventic time. Note that the public key t is the current proventic time. Note that the public key
previously extracted from the certificate continues to be valid previously extracted from the certificate continues to be valid
for an indefinite time. This raises the interesting possibility for an indefinite time. This raises the interesting possibility
where a truechimer server with expired certificate or a where a truechimer server with expired certificate or a
falseticker with valid certificate are not detected until the falseticker with valid certificate are not detected until the
client has synchronized to a proventic source. client has synchronized to a proventic source.
Appendix B. Identity Schemes Appendix B. Identity Schemes
There are five identity schemes in the NTPv4 reference There are five identity schemes in the NTPv4 reference
implementation: (1) private certificate (PC), (2) trusted certificate implementation: (1) private certificate (PC), (2) trusted certificate
(TC), (3) a modified Schnorr algorithm (IFF - Identify Friend or (TC), (3) a modified Schnorr algorithm (IFF - Identify Friend or
Foe), (4) a modified Guillou-Quisquater algorithm (GQ), and (5) a Foe), (4) a modified Guillou-Quisquater (GQ) algorithm, and (5) a
modified Mu-Varadharajan algorithm (MV). modified Mu-Varadharajan (MV) algorithm.
The PC scheme is intended for testing and development and not The PC scheme is intended for testing and development and not
recommended for general use. The TC scheme uses a certificate trail, recommended for general use. The TC scheme uses a certificate trail,
but not an identity scheme. The IFF, GQ and MV identity schemes use but not an identity scheme. The IFF, GQ, and MV identity schemes use
a cryptographically strong challenge-response exchange where an a cryptographically strong challenge-response exchange where an
intruder cannot learn the group key, even after repeated observations intruder cannot learn the group key, even after repeated observations
of multiple exchanges. These schemes begin when the client sends a of multiple exchanges. These schemes begin when the client sends a
nonce to the server, which then rolls its own nonce, performs a nonce to the server, which then rolls its own nonce, performs a
mathematical operation and sends the results to the client. The mathematical operation and sends the results to the client. The
client performs a second mathematical operation to prove the server client performs a second mathematical operation to prove the server
has the same group key as the client. has the same group key as the client.
Appendix C. Private Certificate (PC) Scheme Appendix C. Private Certificate (PC) Scheme
skipping to change at page 43, line 19 skipping to change at page 47, line 24
| +-------------+ | | +-------------+ |
| | | |
\|/ \|/ \|/ \|/
+-------------+ +-------------+ +-------------+ +-------------+
| Certificate | | Certificate | | Certificate | | Certificate |
+-------------+ +-------------+ +-------------+ +-------------+
Server Client Server Client
Figure 12: Private Certificate (PC) Identity Scheme Figure 12: Private Certificate (PC) Identity Scheme
A certificate is designated private when the X509v3 Extended Key A certificate is designated private when the X.509v3 Extended Key
Usage extension field is present and contains "Private". The private Usage extension field is present and contains "Private". The private
certificate is distributed to all other group members by secret certificate is distributed to all other group members by secret
means, so in fact becomes a symmetric key. Private certificates are means, so in fact becomes a symmetric key. Private certificates are
also trusted, so there is no need for a certificate trail or identity also trusted, so there is no need for a certificate trail or identity
scheme. scheme.
Appendix D. Trusted Certificate (TC) Scheme Appendix D. Trusted Certificate (TC) Scheme
All other schemes involve a conventional certificate trail as shown All other schemes involve a conventional certificate trail as shown
in Figure 13. in Figure 13.
skipping to change at page 43, line 43 skipping to change at page 47, line 47
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+
+--->| Subject | +--->| Subject | +--->| Subject | +--->| Subject | +--->| Subject | +--->| Subject |
| +-----------+ | +-----------+ | +-----------+ | +-----------+ | +-----------+ | +-----------+
...---+ | Issuer |---+ | Issuer |---+ | Issuer | ...---+ | Issuer |---+ | Issuer |---+ | Issuer |
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+
| Signature | | Signature | | Signature | | Signature | | Signature | | Signature |
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+
Figure 13: Trusted Certificate (TC) Identity Scheme Figure 13: Trusted Certificate (TC) Identity Scheme
As described in RFC-2510 [RFC2510], each certificate is signed by an As described in RFC 4210 [RFC4210], each certificate is signed by an
issuer one step closer to the trusted host, which has a self-signed issuer one step closer to the trusted host, which has a self-signed
trusted certificate. A certificate is designated trusted when an trusted certificate. A certificate is designated trusted when an
X509v3 Extended Key Usage extension field is present and contains X.509v3 Extended Key Usage extension field is present and contains
"trustRoot". If no identity scheme is specified in the parameter "trustRoot". If no identity scheme is specified in the parameter
exchange, this is the default scheme. exchange, this is the default scheme.
Appendix E. Schnorr (IFF) Identity Scheme Appendix E. Schnorr (IFF) Identity Scheme
The IFF scheme is useful when the group key is concealed, so that The IFF scheme is useful when the group key is concealed, so that
client keys need not be protected. The primary disadvantage is that client keys need not be protected. The primary disadvantage is that
when the server key is refreshed all hosts must update the client when the server key is refreshed all hosts must update the client
key. The scheme shown in Figure 14 involves a set of public key. The scheme shown in Figure 14 involves a set of public
parameters and a group key including both private and public parameters and a group key including both private and public
skipping to change at page 44, line 33 skipping to change at page 48, line 33
| Parameters |<------------------------| Parameters | | Parameters |<------------------------| Parameters |
+------------+ +------------+ +------------+ +------------+
| Group Key |------------------------>| Client Key | | Group Key |------------------------>| Client Key |
+------------+ Response +------------+ +------------+ Response +------------+
Server Client Server Client
Figure 14: Schnorr (IFF) Identity Scheme Figure 14: Schnorr (IFF) Identity Scheme
By happy coincidence, the mathematical principles on which IFF is By happy coincidence, the mathematical principles on which IFF is
based are similar to DSA. The scheme is a modification an algorithm based are similar to DSA. The scheme is a modification an algorithm
described in [SCHNORR] and [STINSON] p. 285. The parameters are described in [SCHNORR] and [STINSON] (p. 285). The parameters are
generated by routines in the OpenSSL library, but only the moduli p, generated by routines in the OpenSSL library, but only the moduli p,
q and generator g are used. The p is a 512-bit prime, g a generator 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 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 (p-1) and is a qth root of 1 mod p; that is, g^q = 1 mod p. The TA
rolls a private random group key b (0 < b < q), then computes public rolls a private random 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 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 servers using secure means and (p, q, g, v) to all clients not
necessarily using secure means. necessarily using secure means.
The TA hides IFF parameters and keys in an OpenSSL DSA cuckoo The TA hides IFF parameters and keys in an OpenSSL DSA cuckoo
structure. The IFF parameters are identical to the DSA parameters, structure. The IFF parameters are identical to the DSA parameters,
so the OpenSSL library can be used directly. The structure shown in so the OpenSSL library can be used directly. The structure shown in
FigureFigure 15 is written to a file as a DSA private key encoded in Figure 15 is written to a file as a DSA private key encoded in PEM.
PEM. Unused structure members are set to one. Unused structure members are set to one.
+----------------------------------+-------------+ +----------------------------------+-------------+
| IFF | DSA | Item | Include | | IFF | DSA | Item | Include |
+=========+==========+=============+=============+ +=========+==========+=============+=============+
| p | p | modulus | all | | p | p | modulus | all |
+---------+----------+-------------+-------------+ +---------+----------+-------------+-------------+
| q | q | modulus | all | | q | q | modulus | all |
+---------+----------+-------------+-------------+ +---------+----------+-------------+-------------+
| g | g | generator | all | | g | g | generator | all |
+---------+----------+-------------+-------------+ +---------+----------+-------------+-------------+
skipping to change at page 45, line 43 skipping to change at page 49, line 43
Besides making the response shorter, the hash makes it effectively Besides making the response shorter, the hash makes it effectively
impossible for an intruder to solve for b by observing a number of impossible for an intruder to solve for b by observing a number of
these messages. The signed response binds this knowledge to Bob's these messages. The signed response binds this knowledge to Bob's
private key and the public key previously received in his private key and the public key previously received in his
certificate. certificate.
Appendix F. Guillard-Quisquater (GQ) Identity Scheme Appendix F. Guillard-Quisquater (GQ) Identity Scheme
The GQ scheme is useful when the server key must be refreshed from The GQ scheme is useful when the server key must be refreshed from
time to time without changing the group key. The NTP utility time to time without changing the group key. The NTP utility
programs include the GQ client key in the X509v3 Subject Key programs include the GQ client key in the X.509v3 Subject Key
Identifier extension field. The primary disadvantage of the scheme Identifier extension field. The primary disadvantage of the scheme
is that the group key must be protected in both the server and is that the group key must be protected in both the server and
client. A secondary disadvantage is that when a server key is client. A secondary disadvantage is that when a server key is
refreshed, old extension fields no longer work. The scheme is shown refreshed, old extension fields no longer work. The scheme shown in
in Figure 16a involves a set of public parameters and group key used Figure 16 involves a set of public parameters and a group key used to
to generate private server keys and client keys. generate private server keys and client keys.
Trusted Trusted
Authority Authority
+------------+ +------------+
| Parameters | | Parameters |
Secure +------------+ Secure Secure +------------+ Secure
+-------------| Group Key |-----------+ +-------------| Group Key |-----------+
| +------------+ | | +------------+ |
\|/ \|/ \|/ \|/
+------------+ Challenge +------------+ +------------+ Challenge +------------+
skipping to change at page 46, line 26 skipping to change at page 50, line 26
| Group Key | | Group Key | | Group Key | | Group Key |
+------------+ Response +------------+ +------------+ Response +------------+
| Server Key |------------------------>| Client Key | | Server Key |------------------------>| Client Key |
+------------+ +------------+ +------------+ +------------+
Server Client Server Client
Figure 16: Schnorr (IFF) Identity Scheme Figure 16: Schnorr (IFF) Identity Scheme
By happy coincidence, the mathematical principles on which GQ is By happy coincidence, the mathematical principles on which GQ is
based are similar to RSA. The scheme is a modification of an based are similar to RSA. The scheme is a modification of an
algorithm described in [GUILLOU] and [STINSON] p. 300 (with errors). algorithm described in [GUILLOU] and [STINSON] (p. 300) (with
The parameters are generated by routines in the OpenSSL library, but errors). The parameters are generated by routines in the OpenSSL
only the moduli p and q are used. The 512-bit public modulus is library, but only the moduli p and q are used. The 512-bit public
n=pq, where p and q are secret large primes. The TA rolls random modulus is n=pq, where p and q are secret large primes. The TA rolls
large prime b (0 < b < n) and distributes (n, b) to all group servers random large prime b (0 < b < n) and distributes (n, b) to all group
and clients using secure means, since an intruder in possession of servers and clients using secure means, since an intruder in
these values could impersonate a legitimate server. The private possession of these values could impersonate a legitimate server.
server key and public client key are constructed later. The private server key and public client key are constructed later.
The TA hides GQ parameters and keys in an OpenSSL RSA cuckoo The TA hides GQ parameters and keys in an OpenSSL RSA cuckoo
structure. The GQ parameters are identical to the RSA parameters, so structure. The GQ parameters are identical to the RSA parameters, so
the OpenSSL library can be used directly. When generating a the OpenSSL library can be used directly. When generating a
certificate, the server rolls random server key u (0 < u < n) and certificate, the server rolls random server key u (0 < u < n) and
client key its inverse obscured by the group key v = (u^-1)^b mod n. client key its inverse obscured by the group key v = (u^-1)^b mod n.
These values replace the private and public keys normally generated These values replace the private and public keys normally generated
by the RSA scheme. The client key is conveyed in a X.509 certificate by the RSA scheme. The client key is conveyed in a X.509 certificate
extension. The updated GQ structure shown in Figure 17 is written as extension. The updated GQ structure shown in Figure 17 is written as
an RSA private key encoded in PEM. Unused structure members are set an RSA private key encoded in PEM. Unused structure members are set
skipping to change at page 48, line 4 skipping to change at page 51, line 51
is most useful when a small number of servers provide synchronization is most useful when a small number of servers provide synchronization
to a large client population where there might be considerable risk to a large client population where there might be considerable risk
of compromise between and among the servers and clients. The client of compromise between and among the servers and clients. The client
population can be partitioned into a modest number of subgroups, each population can be partitioned into a modest number of subgroups, each
associated with an individual client key. associated with an individual client key.
The TA generates an intricate cryptosystem involving encryption and The TA generates an intricate cryptosystem involving encryption and
decryption keys, together with a number of activation keys and decryption keys, together with a number of activation keys and
associated client keys. The TA can activate and revoke individual associated client keys. The TA can activate and revoke individual
client keys without changing the client keys themselves. The TA client keys without changing the client keys themselves. The TA
provides to the servers an encryption key E and partial decryption provides to the servers an encryption key E, and partial decryption
keys g-bar and g-hat which depend on the activated keys. The servers keys g-bar and g-hat which depend on the activated keys. The servers
have no additional information and, in particular, cannot masquerade have no additional information and, in particular, cannot masquerade
as a TA. In addition, the TA provides to each client j individual as a 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 partial decryption keys x-bar_j and x-hat_j, which do not need to be
changed if the TA activates or deactivates any client key. The changed if the TA activates or deactivates any client key. The
clients have no further information and, in particular, cannot clients have no further information and, in particular, cannot
masquerade as a server or TA. masquerade as a server or TA.
The scheme uses an encryption algorithm similar to El Gamal The scheme uses an encryption algorithm similar to El Gamal
cryptography and a polynomial formed from the expansion of product cryptography and a polynomial formed from the expansion of product
terms (x-x_1)(x-x_2)(x-x_3)...(x-x_n), as described in [MV]. The terms (x-x_1)(x-x_2)(x-x_3)...(x-x_n), as described in [MV]. The
paper has significant errors and serious omissions. The cryptosystem paper has significant errors and serious omissions. The cryptosystem
is constructed so that, for every encryption key E its inverse is is constructed so that, for every encryption key E its inverse is
(g-bar^x-hat_j)(g-hat^x-bar_j) mod p for every j. This remains true (g-bar^x-hat_j)(g-hat^x-bar_j) mod p for every j. This remains true
if both quantities are raised to the power k mod p. The difficulty if both quantities are raised to the power k mod p. The difficulty
in finding E is equivalent to the discrete log problem. in finding E is equivalent to the discrete log problem.
The scheme is shown in Figure 18. The TA generates the parameters, The scheme is shown in Figure 18. The TA generates the parameters,
group key, server keys and client keys, one for each client, all of group key, server keys, and client keys, one for each client, all of
which must be protected to prevent theft of service. Note that only which must be protected to prevent theft of service. Note that only
the TA has the group key, which is not known to either the servers or the TA has the group key, which is not known to either the servers or
clients. In this sense the MV scheme is a zero-knowledge proof. clients. In this sense, the MV scheme is a zero-knowledge proof.
Trusted Trusted
Authority Authority
+------------+ +------------+
| Parameters | | Parameters |
+------------+ +------------+
| Group Key | | Group Key |
+------------+ +------------+
| Server Key | | Server Key |
Secure +------------+ Secure Secure +------------+ Secure
skipping to change at page 49, line 4 skipping to change at page 52, line 48
+------------+ Challenge +------------+ +------------+ Challenge +------------+
| Parameters |<------------------------| Parameters | | Parameters |<------------------------| Parameters |
+------------+ +------------+ +------------+ +------------+
| Server Key |------------------------>| Client Key | | Server Key |------------------------>| Client Key |
+------------+ Response +------------+ +------------+ Response +------------+
Server Client Server Client
Figure 18: Mu-Varadharajan (MV) Identity Scheme Figure 18: Mu-Varadharajan (MV) Identity Scheme
The TA hides MV parameters and keys in OpenSSL DSA cuckoo structures. The TA hides MV parameters and keys in OpenSSL DSA cuckoo structures.
The MV parameters are identical to the DSA parameters, so the OpenSSL The MV parameters are identical to the DSA parameters, so the OpenSSL
library can be used directly. The structure shown in the figures library can be used directly. The structure shown in the figures
below are written to files as a the fkey encoded in PEM. Unused below are written to files as a the fkey encoded in PEM. Unused
structure members are set to one. The Figure 19 shows the data structure members are set to one. The Figure 19 shows the data
structure used by the servers, while Figure Figure 20 shows the structure used by the servers, while Figure 20 shows the client data
client data structure associated with each activation key. structure associated with each activation key.
+---------------------------------+-------------+ +---------------------------------+-------------+
| MV | DSA | Item | Include | | MV | DSA | Item | Include |
+=========+==========+============+=============+ +=========+==========+============+=============+
| p | p | modulus | all | | p | p | modulus | all |
+---------+----------+------------+-------------+ +---------+----------+------------+-------------+
| q | q | modulus | server | | q | q | modulus | server |
+---------+----------+------------+-------------+ +---------+----------+------------+-------------+
| E | g | private | server | | E | g | private | server |
| | | encrypt | | | | | encrypt | |
skipping to change at page 49, line 47 skipping to change at page 53, line 42
| | | decrypt | | | | | decrypt | |
+---------+----------+------------+-------------+ +---------+----------+------------+-------------+
| x-hat_j | pub_key | public | client | | x-hat_j | pub_key | public | client |
| | | decrypt | | | | | decrypt | |
+---------+----------+------------+-------------+ +---------+----------+------------+-------------+
Figure 20: MV Scheme Client Structure Figure 20: MV Scheme Client Structure
The devil is in the details, which are beyond the scope of this memo. The devil is in the details, which are beyond the scope of this memo.
The steps in generating the cryptosystem activating the keys and The steps in generating the cryptosystem activating the keys and
generating the partial decryption keys are in [DASBUCH] page 170 ff. ff).
Alice challenges Bob to confirm identity using the following Alice challenges Bob to confirm identity using the following
exchange. exchange.
1. Alice rolls random r (0 < r < q) and sends to Bob. 1. Alice rolls random r (0 < r < q) and sends to Bob.
2. Bob rolls random k (0 < k < q) and computes the session 2. Bob rolls random k (0 < k < q) and computes the session
encryption key E-prime = E^k mod p and partial decryption keys encryption key E-prime = E^k mod p and partial decryption keys
g-bar-prime = g-bar^k mod p and g-hat-prime = g-hat^k mod p. He g-bar-prime = g-bar^k mod p and g-hat-prime = g-hat^k mod p. He
encrypts x = E-prime * r mod p and sends (x, g-bar-prime, g-hat- encrypts x = E-prime * r mod p and sends (x, g-bar-prime, g-hat-
skipping to change at page 50, line 30 skipping to change at page 54, line 25
Certain value fields in request and response messages contain data Certain value fields in request and response messages contain data
encoded in ASN.1 distinguished encoding rules (DER). The BNF grammar encoded in ASN.1 distinguished encoding rules (DER). The BNF grammar
for each encoding rule is given below along with the OpenSSL routine for each encoding rule is given below along with the OpenSSL routine
used for the encoding in the reference implementation. The object used for the encoding in the reference implementation. The object
identifiers for the encryption algorithms and message digest/ identifiers for the encryption algorithms and message digest/
signature encryption schemes are specified in [RFC3279]. The signature encryption schemes are specified in [RFC3279]. The
particular algorithms required for conformance are not specified in particular algorithms required for conformance are not specified in
this memo. this memo.
Appendix I. COOKIE request, IFF response, GQ response, MV response Appendix I. COOKIE Request, IFF Response, GQ Response, MV Response
The value field of the COOKIE request message contains a sequence of The value field of the COOKIE request message contains a sequence of
two integers (n, e) encoded by the i2d_RSAPublicKey() routine in the two integers (n, e) encoded by the i2d_RSAPublicKey() routine in the
OpenSSL distribution. In the request, n is the RSA modulus in bits OpenSSL distribution. In the request, n is the RSA modulus in bits
and e is the public exponent. and e is the public exponent.
RSAPublicKey ::= SEQUENCE { RSAPublicKey ::= SEQUENCE {
n ::= INTEGER, n ::= INTEGER,
e ::= INTEGER e ::= INTEGER
} }
skipping to change at page 51, line 19 skipping to change at page 55, line 15
DSAparameters ::= SEQUENCE { DSAparameters ::= SEQUENCE {
p ::= INTEGER, p ::= INTEGER,
q ::= INTEGER, q ::= INTEGER,
g ::= INTEGER g ::= INTEGER
} }
Appendix J. Certificates Appendix J. Certificates
Certificate extension fields are used to convey information used by Certificate extension fields are used to convey information used by
the identity schemes. While the semantics of these fields generally the identity schemes. While the semantics of these fields generally
conforms with conventional usage, there are subtle variations. The conform with conventional usage, there are subtle variations. The
fields used by Autokey Version 2 include: fields used by Autokey version 2 include:
o Basic Constraints. This field defines the basic functions of the o Basic Constraints. This field defines the basic functions of the
certificate. It contains the string "critical,CA:TRUE", which certificate. It contains the string "critical,CA:TRUE", which
means the field must be interpreted and the associated private key means the field must be interpreted and the associated private key
can be used to sign other certificates. While included for can be used to sign other certificates. While included for
compatibility, Autokey makes no use of this field. compatibility, Autokey makes no use of this field.
o Key Usage. This field defines the intended use of the public key o Key Usage. This field defines the intended use of the public key
contained in the certificate. It contains the string contained in the certificate. It contains the string
"digitalSignature,keyCertSign", which means the contained public "digitalSignature,keyCertSign", which means the contained public
skipping to change at page 51, line 46 skipping to change at page 55, line 42
of the public key contained in the certificate and is present only of the public key contained in the certificate and is present only
in self-signed certificates. It contains the string "Private" if in self-signed certificates. It contains the string "Private" if
the certificate is designated private or the string "trustRoot" if the certificate is designated private or the string "trustRoot" if
it is designated trusted. A private certificate is always it is designated trusted. A private certificate is always
trusted. trusted.
o Subject Key Identifier. This field contains the client identity o Subject Key Identifier. This field contains the client identity
key used in the GQ identity scheme. It is present only if the GQ key used in the GQ identity scheme. It is present only if the GQ
scheme is in use. scheme is in use.
The value field contains a X509v3 certificate encoded by the The value field contains an X.509v3 certificate encoded by the
i2d_X509() routine in the OpenSSL distribution. The encoding follows i2d_X509() routine in the OpenSSL distribution. The encoding follows
the rules stated in [RFC5280], including the use of X509v3 extension the rules stated in [RFC5280], including the use of X.509v3 extension
fields. fields.
Certificate ::= SEQUENCE { Certificate ::= SEQUENCE {
tbsCertificate TBSCertificate, tbsCertificate TBSCertificate,
signatureAlgorithm AlgorithmIdentifier, signatureAlgorithm AlgorithmIdentifier,
signatureValue BIT STRING signatureValue BIT STRING
} }
The signatureAlgorithm is the object identifier of the message The signatureAlgorithm is the object identifier of the message
digest/signature encryption scheme used to sign the certificate. The digest/signature encryption scheme used to sign the certificate. The
signatureValue is computed by the certificate issuer using this signatureValue is computed by the certificate issuer using this
algorithm and the issuer private key. algorithm and the issuer private key.
TBSCertificate ::= SEQUENCE { TBSCertificate ::= SEQUENCE {
version EXPLICIT v3(2), version EXPLICIT v3(2),
serialNumber CertificateSerialNumber, serialNumber CertificateSerialNumber,
signature AlgorithmIdentifier, signature AlgorithmIdentifier,
issuer Name, issuer Name,
skipping to change at page 53, line 19 skipping to change at page 57, line 19
extnValue OCTET STRING extnValue OCTET STRING
} }
SET { SET {
Name ::= SEQUENCE { Name ::= SEQUENCE {
OBJECT IDENTIFIER commonName OBJECT IDENTIFIER commonName
PrintableString HostName PrintableString HostName
} }
} }
For trusted host certificates the subject and issuer HostName is the For trusted host certificates, the subject and issuer HostName is the
NTP name of the group, while for all other host certificates the NTP name of the group, while for all other host certificates the
subject and issuer HostName is the NTP name of the host. In the subject and issuer HostName is the NTP name of the host. In the
reference implementation if these names are not explicitly specified, reference implementation, if these names are not explicitly
they default to the string returned by the Unix gethostname() routine specified, they default to the string returned by the Unix
(trailing NUL removed). For other than self-signed certificates, the gethostname() routine (trailing NUL removed). For other than self-
issuer HostName is the unique DNS name of the host signing the signed certificates, the issuer HostName is the unique DNS name of
certificate. the host signing the certificate.
It should be noted that the Autokey protocol itself has no provisions It should be noted that the Autokey protocol itself has no provisions
to revoke certificates. The reference implementation is purposely to revoke certificates. The reference implementation is purposely
restarted about once a week, leading to the regeneration of the restarted about once a week, leading to the regeneration of the
certificate and a restart of the Auokey protocol. This restart is certificate and a restart of the Autokey protocol. This restart is
not enforced for the Autokey protocol but rather for NTP not enforced for the Autokey protocol but rather for NTP
functionality reasons. functionality reasons.
Each group host operates with only one certificate at a time and Each group host operates with only one certificate at a time and
constructs a trail by induction. Since the group configuration must constructs a trail by induction. Since the group configuration must
form an acyclic graph, with roots at the trusted hosts, it does not form an acyclic graph, with roots at the trusted hosts, it does not
matter which, of possibly several, signed certificates is used. The matter which, of possibly several, signed certificates is used. The
reference implementation chooses a single certificate and operates reference implementation chooses a single certificate and operates
with only that certificate until the protocol is restarted. with only that certificate until the protocol is restarted.
Authors' Addresses Authors' Addresses
Brian Haberman (editor) Brian Haberman (editor)
The Johns Hopkins University Applied Physics Laboratory The Johns Hopkins University Applied Physics Laboratory
11100 Johns Hopkins Road 11100 Johns Hopkins Road
Laurel, MD 20723-6099 Laurel, MD 20723-6099
US US
Phone: +1 443 778 1319 Phone: +1 443 778 1319
Email: brian@innovationslab.net EMail: brian@innovationslab.net
Dr. David L. Mills Dr. David L. Mills
University of Delaware University of Delaware
Newark, DE 19716 Newark, DE 19716
US US
Phone: +1 302 831 8247 Phone: +1 302 831 8247
Email: mills@udel.edu EMail: mills@udel.edu
 End of changes. 215 change blocks. 
590 lines changed or deleted 645 lines changed or added

This html diff was produced by rfcdiff 1.38. The latest version is available from http://tools.ietf.org/tools/rfcdiff/