draft-ietf-ntp-autokey-00.txt   draft-ietf-ntp-autokey-01.txt 
Network Working Group B. Haberman, Ed. Network Working Group B. Haberman, Ed.
Internet-Draft JHU/APL Internet-Draft JHU/APL
Obsoletes: RFC 1305 D. Mills Obsoletes: RFC 1305 D. Mills
(if approved) U. Delaware (if approved) U. Delaware
Intended status: Informational September 25, 2007 Intended status: Informational February 25, 2008
Expires: March 28, 2008 Expires: August 28, 2008
Network Time Protocol Version 4 Autokey Specification Network Time Protocol Version 4 Autokey Specification
draft-ietf-ntp-autokey-00 draft-ietf-ntp-autokey-01
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79. aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
skipping to change at page 1, line 36 skipping to change at page 1, line 36
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on March 28, 2008. This Internet-Draft will expire on August 28, 2008.
Copyright Notice Copyright Notice
Copyright (C) The IETF Trust (2007). Copyright (C) The IETF Trust (2008).
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 PKI schemes presume authenticated time values are always available to
enforce certificate lifetimes; however, cryptographically verified enforce certificate lifetimes; however, cryptographically verified
timestamps require interaction between the timekeeping and timestamps require interaction between the timekeeping and
authentication functions. 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 the
protocol states, events and transition functions is included. A protocol states, events and transition functions is included. A
prototype of the Autokey design based on this report 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 Unix, Windows and VMS at
http://www.ntp.org. http://www.ntp.org.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Requirements Notation . . . . . . . . . . . . . . . . . . 4
2. NTP Security Model . . . . . . . . . . . . . . . . . . . . . . 4 2. NTP Security Model . . . . . . . . . . . . . . . . . . . . . . 4
3. Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3. Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4. Autokey Cryptography . . . . . . . . . . . . . . . . . . . . . 9 4. Autokey Cryptography . . . . . . . . . . . . . . . . . . . . . 8
5. Secure Groups . . . . . . . . . . . . . . . . . . . . . . . . 12 5. NTP Secure Groups . . . . . . . . . . . . . . . . . . . . . . 11
6. Identity Schemes . . . . . . . . . . . . . . . . . . . . . . . 18 6. Identity Schemes . . . . . . . . . . . . . . . . . . . . . . . 15
7. Autokey Operations . . . . . . . . . . . . . . . . . . . . . . 20 7. Timestamps and Filestamps . . . . . . . . . . . . . . . . . . 16
8. Public Key Signatures and Timestamps . . . . . . . . . . . . . 22 8. Autokey Protocol Overview . . . . . . . . . . . . . . . . . . 18
9. Autokey Protocol Overview . . . . . . . . . . . . . . . . . . 24 9. Autokey Operations . . . . . . . . . . . . . . . . . . . . . . 20
10. Autokey State Machine . . . . . . . . . . . . . . . . . . . . 26 10. Autokey Protocol Messages . . . . . . . . . . . . . . . . . . 21
10.1. Status Word . . . . . . . . . . . . . . . . . . . . . . . 26 10.1. No-Operation . . . . . . . . . . . . . . . . . . . . . . 23
10.2. Host State Variables . . . . . . . . . . . . . . . . . . . 28 10.2. Association Message (ASSOC) . . . . . . . . . . . . . . . 24
10.3. Client State Variables (all modes) . . . . . . . . . . . . 30 10.3. Certificate Message (CERT) . . . . . . . . . . . . . . . 24
10.4. Server State Variables (broadcast and symmetric modes) . . 31 10.4. Cookie Message (COOKIE) . . . . . . . . . . . . . . . . . 24
10.5. Autokey Protocol Messages . . . . . . . . . . . . . . . . 31 10.5. Autokey Message (AUTO) . . . . . . . . . . . . . . . . . 24
10.5.1. No-Operation . . . . . . . . . . . . . . . . . . . . 33 10.6. Leapseconds Values Message (LEAP) . . . . . . . . . . . . 25
10.5.2. Association Message (ASSOC) . . . . . . . . . . . . . 33 10.7. Sign Message (SIGN) . . . . . . . . . . . . . . . . . . . 25
10.5.3. Certificate Message (CERT) . . . . . . . . . . . . . 34 10.8. Identity Messages (IFF, GQ, MV) . . . . . . . . . . . . . 25
10.5.4. Cookie Message (COOKIE) . . . . . . . . . . . . . . . 34 11. Autokey State Machine . . . . . . . . . . . . . . . . . . . . 25
10.5.5. Autokey Message (AUTO) . . . . . . . . . . . . . . . 34 11.1. Status Word . . . . . . . . . . . . . . . . . . . . . . . 25
10.5.6. Leapseconds Table Message (LEAP) . . . . . . . . . . 35 11.2. Host State Variables . . . . . . . . . . . . . . . . . . 27
10.5.7. Sign Message (SIGN) . . . . . . . . . . . . . . . . . 35 11.3. Client State Variables (all modes) . . . . . . . . . . . 29
10.5.8. Identity Messages (IFF, GQ, MV) . . . . . . . . . . . 35 11.4. Server State Variables (broadcast and symmetric modes) . 30
10.6. Protocol State Transitions . . . . . . . . . . . . . . . . 35 11.5. Protocol State Transitions . . . . . . . . . . . . . . . 30
10.6.1. Server Dance . . . . . . . . . . . . . . . . . . . . 36 11.5.1. Server Dance . . . . . . . . . . . . . . . . . . . . 30
10.6.2. Broadcast Dance . . . . . . . . . . . . . . . . . . . 37 11.5.2. Broadcast Dance . . . . . . . . . . . . . . . . . . . 31
10.6.3. Symmetric Dance . . . . . . . . . . . . . . . . . . . 38 11.5.3. Symmetric Dance . . . . . . . . . . . . . . . . . . . 32
11. Error Recovery . . . . . . . . . . . . . . . . . . . . . . . . 40 11.6. Error Recovery . . . . . . . . . . . . . . . . . . . . . 34
12. Security Considerations . . . . . . . . . . . . . . . . . . . 42 11.7. Security Considerations . . . . . . . . . . . . . . . . . 36
12.1. Protocol Vulnerability . . . . . . . . . . . . . . . . . . 42 11.8. Protocol Vulnerability . . . . . . . . . . . . . . . . . 36
12.2. Clogging Vulnerability . . . . . . . . . . . . . . . . . . 44 11.9. Clogging Vulnerability . . . . . . . . . . . . . . . . . 37
13. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 45 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 38
14. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 45 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 38
15. References . . . . . . . . . . . . . . . . . . . . . . . . . . 46 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 38
15.1. Normative References . . . . . . . . . . . . . . . . . . . 46 14.1. Normative References . . . . . . . . . . . . . . . . . . 38
15.2. Informative References . . . . . . . . . . . . . . . . . . 46 14.2. Informative References . . . . . . . . . . . . . . . . . 38
Appendix A. Cryptographic Key and Certificate Management . . . . 47 Appendix A. Timestamps, Filestamps and Partial Ordering . . . . . 39
Appendix B. Autokey Error Checking . . . . . . . . . . . . . . . 48 Appendix B. Identity Schemes . . . . . . . . . . . . . . . . . . 40
B.1. Packet Processing Rules . . . . . . . . . . . . . . . . . 49 B.1. Private Certificate (PC) Scheme . . . . . . . . . . . . . 41
B.2. Timestamps, Filestamps and Partial Ordering . . . . . . . 51 B.2. Trusted Certificate (TC) Scheme . . . . . . . . . . . . . 41
Appendix C. Certificates . . . . . . . . . . . . . . . . . . . . 52 B.3. Schnorr (IFF) Identity Scheme . . . . . . . . . . . . . . 42
Appendix D. Identity Schemes . . . . . . . . . . . . . . . . . . 53 B.4. Guillard-Quisquater (GQ) Identity Scheme . . . . . . . . 44
D.1. Private Certificate (PC) Scheme . . . . . . . . . . . . . 53 B.5. Mu-Varadharajan (MV) Identity Scheme . . . . . . . . . . 46
D.2. Trusted Certificate (TC) Scheme . . . . . . . . . . . . . 54 Appendix C. ASN.1 Encoding Rules . . . . . . . . . . . . . . . . 48
D.3. Schnorr (IFF) Scheme . . . . . . . . . . . . . . . . . . . 56 C.1. COOKIE request, IFF response, GQ response, MV response . 49
D.4. Guillard-Quisquater (GQ) . . . . . . . . . . . . . . . . . 58 C.2. Certificates . . . . . . . . . . . . . . . . . . . . . . 49
D.5. Mu-Varadharajan (MV) Identity Scheme . . . . . . . . . . . 60 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 51
D.6. Interoperability Issues . . . . . . . . . . . . . . . . . 64 Intellectual Property and Copyright Statements . . . . . . . . . . 53
Appendix E. ASN.1 Encoding Rules . . . . . . . . . . . . . . . . 66
E.1. COOKIE request, IFF response, GQ response, MV response . . 66
E.2. CERT response, SIGN request and response . . . . . . . . . 67
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 68
Intellectual Property and Copyright Statements . . . . . . . . . . 70
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 ctually 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
any client can verify the authenticity of any server using only a client can verify the authenticity of a server using only public
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 with or without data modification. These and replay attacks.
requirements are especially stringent with widely distributed network
services, since damage due to failures can propagate quickly
throughout the network, devastating archives, routing databases and
monitoring systems and even bring down major portions of the network.
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) [1]. The methodology for use in the Network Time Protocol (NTP) [1]. The
various key agreement schemes [2][3][4] proposed require per- various key agreement schemes [2][3][4] proposed require per-
association state variables, which contradicts the principles of the association state variables, which contradicts the principles of the
remote procedure call (RPC) paradigm in which servers keep no state remote procedure call (RPC) paradigm in which servers keep no state
for a possibly large client population. An evaluation of the PKI for a possibly large client population. An evaluation of the PKI
model and algorithms as implemented in the OpenSSL library leads to model and algorithms as implemented in the OpenSSL library leads to
the conclusion that any scheme requiring every NTP packet to carry a the conclusion that any scheme requiring every NTP packet to carry a
PKI digital signature would result in unacceptably poor timekeeping PKI digital signature would result in unacceptably poor timekeeping
performance. The Autokey protocol is based on a combination of PKI performance.
and a pseudo-random sequence generated by repeated hashes of a
cryptographic value involving both public and private components.
This scheme has been implemented, tested and widely deployed in the
Internet of today. A detailed description of the security model,
design principles and implementation experience is presented in this
report.
1.1. Requirements Notation
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The Autokey protocol is based on a combination of PKI and a pseudo-
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this random sequence generated by repeated hashes of a cryptographic value
document are to be interpreted as described in [5]. involving both public and private components. This scheme has been
implemented, tested and deployed in the Internet of today. A
detailed description of the security model, design principles and
implementation is presented in this memo.
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
media which are valid only over designated time intervals; but, time keys which are valid only over esignated 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 bone-fide authentic.
In order to emphasize this requirement, in this report 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", a noun new to English and
derived from provenance, as in the provenance of a painting. Having derived from provenance, as in the provenance of a painting. Having
abused the language this far, the suffixes fixable to the various abused the language this far, the suffixes fixable to the various
noun and verb derivatives of authentic will be adopted for proventic derivatives of authentic will be adopted for proventic as well. In
as well. In NTP each server authenticates the next lower stratum NTP each server authenticates the next lower stratum servers and
servers and proventicates (authenticates by induction) the lowest proventicates (authenticates by induction) the lowest stratum
stratum (primary) servers. Serious computer linguists would (primary) servers. Serious computer linguists would correctly
correctly interpret the proventic relation as the transitive closure interpret the proventic relation as the transitive closure of the
of the authentic relation. 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. A NTP client mobilizes a
number of concurrent associations with different servers and uses number of concurrent associations with different servers and uses a
crafted mitigation 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 report. 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. While a associations and according to the NTP mitigation algorithms.
certificate authority (CA) must satisfy this requirement when signing
a certificate request, the certificate itself can be stored in public
directories and retrieved over unsecured network paths.
Over the last several years the IETF has defined and evolved the 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) [6] and Authentication Header (AH) [7] for Security Payload (ESP) [5] and Authentication Header (AH) [6] for
IPv4 and IPv6. Cryptographic algorithms that use these headers for IPv4 and IPv6. Cryptographic algorithms that use these headers for
various purposes include those developed for the PKI, including MD5 various purposes include those developed for the PKI, including MD5
message digests, RSA digital signatures and several variations of message digests, RSA digital signatures and several variations of
Diffie-Hellman key agreements. The fundamental assumption in the Diffie-Hellman key agreements. The fundamental assumption in the
security model is that packets transmitted over the Internet can be security model is that packets transmitted over the Internet can be
intercepted by other than the intended recipient, remanufactured in intercepted by other than the intended recipient, remanufactured in
various ways and replayed in whole or part. These packets can cause various ways and replayed in whole or part. These packets can cause
the client to believe or produce incorrect information, cause the client to believe or produce incorrect information, cause
protocol operations to fail, interrupt network service or consume protocol operations to fail, interrupt network service or consume
precious network and processor resources. precious network and 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 report 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 other than the intended sender or sent by
the intended sender, but modified or replayed by an intruder. The the intended sender, but modified or replayed by an intruder. The
cryptographic means of the reference implementation are based on the cryptographic means of the reference implementation are based on the
OpenSSL cryptographic software library available at www.openssl.org, OpenSSL cryptographic software library available at www.openssl.org,
but other libraries with equivalent functionality could be used as but other libraries with equivalent functionality could be used as
well. It is important for distribution and export purposes that the well. It is important for distribution and export purposes that the
way in which these algorithms are used precludes encryption of any way in which these algorithms are used precludes encryption of any
data other than incidental to the construction of digital signatures. data other than incidental to the construction of digital signatures.
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 fundamental timestamp architecture, protocol and algorithms. The on-wire timestamp
exchange scheme is inherently resistant to spoofing and replay exchange scheme is inherently resistant to spoofing, packet loss and
attacks. The engineered clock filter, selection and clustering replay attacks. The engineered clock filter, selection and
algorithms are designed to defend against evil cliques of Byzantine clustering algorithms are designed to defend against evil cliques of
traitors. While not necessarily designed to defeat determined Byzantine traitors. While not necessarily designed to defeat
intruders, these algorithms and accompanying sanity checks have determined intruders, these algorithms and accompanying sanity checks
functioned well over the years to deflect improperly operating but have functioned well over the years to deflect improperly operating
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 replay
a packet. However, it cannot permanently prevent onward 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 unlikely cases
considered in Section 12, the modified packet cannot arrive at considered in Section 11.7, the modified packet cannot arrive at
the victim before the original packet, nor does it have the 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 middleman or masquerade attack the intruder is positioned 4. In a middleman or masquerade attack the intruder is positioned
between the server and client, so it can intercept, modify and between the server and client, so it can intercept, modify and
replay a packet and prevent onward transmission of the original replay a packet and prevent onward transmission of the original
packet. Except in unlikely cases considered in Section 12, the packet. Except in unlikely cases considered in Section 11.7, the
middleman does not have the server private keys or identity middleman does not have the server private keys.
parameters.
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 efficiently regenerated them for a client upon arrival of a to regenerated them for a client upon arrival of a packet from
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. All proventication functions must involve only public values 4. Client security functions must involve only public values
transmitted over the net with the single exception of encrypted transmitted over the net. Private values must never be disclosed
signatures and cookies intended only to authenticate the source. beyond the machine on which they were created, except in the case
Private values must never be disclosed beyond the machine on of a special trusted agent (TA) assigned for this purpose.
which they were created except in the case of a special trusted
agent (TA) assigned for this purpose.
5. Public encryption keys and certificates must be retrievable
directly from servers without requiring secured channels;
however, the fundamental security of identification credentials
and public values bound to those credentials must be a function
of certificate authorities and/or webs of trust.
6. Error checking must be at the enhanced paranoid level, as network
terrorists may be able to craft errored packets that consume
excessive cycles with needless result. While this report
includes an informal vulnerability analysis and error protection
paradigm, a formal model based on communicating finite-state
machine analysis remains to be developed.
Unlike the Secure Shell security model, where the client must be Unlike the Secure Shell security model, where the client must be
securely authenticated to the server, in NTP the server must be securely authenticated to the 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.
However, the NTP security model specifically assumes that access
control is performed by means external to the protocol and that all
time values and cryptographic values are public, so there is no need
to associate each interface with different cryptographic values. To
do so would create the possibility of a two-faced clock, which is
ordinarily considered a Byzantine hazard. In other words, there is
one set of private secrets for the host, not one for each interface.
In the NTP design the host name, by default the string returned by
the Unix gethostname() library function, represents all interface
addresses. Since at least in some host configurations the host name
may not be identifiable in a DNS query, the name must be either
configured in advance or obtained directly from the server using the
Autokey protocol.
3. Approach 3. Approach
The Autokey protocol described in this report is designed to meet the The Autokey protocol described in this memo is designed to meet the
following objectives. following objectives. In-depth discussions on these objectives is in
the web briefings and will not be elaborated in this memo. Note that
here and elsewhere in this memo mention of broadcast mode means
multicast mode as well, with exceptions as noted in the NTP software
documentation.
1. It must interoperate with the existing NTP architecture model and 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 [8]. key scheme described in [7]. As a practical matter, the
reference implementation must use the same internal key
management system, including the use of 32-bit key IDs and
existing mechanisms to store, activate and revoke keys.
2. It must not significantly degrade the potential accuracy of the 2. It must provide for the independent collection of cryptographic
values and time values. A NTP packet is accepted for processing
only when the required cryptographic values have been obtained
and verified and the packet has passed all header sanity checks.
3. It must not significantly degrade the potential accuracy of the
NTP synchronization algorithms. In particular, it must not make 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.
3. 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 misorder, or suboptimal configurations. packet loss or misorder, or suboptimal configurations.
4. 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
incidental to signature and cookie encryption operations. incidental to signature and cookie encryption operations.
5. 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.
6. It must not require intricate per-client or per-server
configuration other than the availability of the required
cryptographic keys and certificates.
4. Autokey Cryptography 4. Autokey Cryptography
Autokey public key cryptography is based on the PKI algorithms Autokey cryptography is based on the PKI algorithms commonly used in
commonly used in the Secure Shell and Secure Sockets Layer the Secure Shell and Secure Sockets Layer applications. As in these
applications. As in these applications Autokey uses keyed message applications Autokey uses message digests to detect packet
digests to detect packet modification, digital signatures to verify modification, digital signatures to verify credentials and public
the source and public key algorithms to encrypt cookies. What makes certificates to provide traceable authority. What makes Autokey
Autokey cryptography unique is the way in which these algorithms are cryptography unique is the way in which these algorithms are used to
used to deflect intruder attacks while maintaining the integrity and deflect intruder attacks while maintaining the integrity and accuracy
accuracy of the time synchronization function. of the time synchronization function.
NTPv3 and NTPv4 symmetric key cryptography uses keyed-MD5 message NTPv3 and NTPv4 symmetric key cryptography uses keyed-MD5 message
digests with a 128-bit private key and 32-bit key ID. In order to digests with a 128-bit private key and 32-bit key ID. In order to
retain backward compatibility with NTPv3, the NTPv4 key ID space is retain backward compatibility with NTPv3, the NTPv4 key ID space is
partitioned in two subspaces at a pivot point of 65536. Symmetric partitioned in two subspaces at a pivot point of 65536. Symmetric
key IDs have values less than the pivot and indefinite lifetime. key IDs have values less than the pivot and indefinite lifetime.
Autokey key IDs have pseudo-random values equal to or greater than Autokey key IDs have pseudo-random values equal to or greater than
the pivot and are expunged immediately after use. Both symmetric key the pivot and are expunged immediately after use.
and public key cryptography authenticate as shown in Figure 1. The
server looks up the key associated with the key ID and calculates the Both symmetric key and public key cryptography authenticate as shown
message digest from the NTP header and extension fields together with in Figure 1. The server looks up the key associated with the key ID
the key value. The key ID and digest form the message authentication and calculates the message digest from the NTP header and extension
code (MAC) included with the message. The client does the same fields together with the key value. The key ID and digest form the
computation using its local copy of the key and compares the result message authentication code (MAC) included with the message. The
with the digest in the MAC. If the values agree, the message is client does the same computation using its local copy of the key and
assumed authentic. compares the result with the digest in the MAC. If the values agree,
the message is assumed authentic.
+------------------+ +------------------+
| NTP Header and | | NTP Header and |
| Extension Fields | | Extension Fields |
+------------------+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +------------------+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | Message Authenticator Code | | | | Message Authenticator 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
There are three Autokey protocol variants corresponding to each of Autokey uses specially contrived session keys, called autokeys, and a
the three NTP modes: server, symmetric and broadcast. All three precomputed pseudo-random sequence of autokeys which are saved in the
variants make use of specially contrived session keys, called autokey list. The Autokey protocol operates separately for each
autokeys, and a precomputed pseudo-random sequence of autokeys which association, so there may be several autokey sequences operating
are saved along with the key IDs in a key list. As in the original independently at the same time.
NTPv3 authentication scheme, the Autokey protocol operates separately
for each association, so there may be several autokey sequences
operating independently at the same time.
+-------------+-------------+--------+--------+ +-------------+-------------+--------+--------+
| Src Address | Dst Address | Key ID | Cookie | | 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 by the MD5 message shown in Figure 2. The four values are hashed by the MD5 message
digest algorithm to produce the 128-bit autokey value, which in the digest 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 Source Address and Dest Address fields contain For use with IPv4 the Source Address and Dest Address fields contain
32 bits; for use with IPv6, these fields contain 128 bits. In either 32 bits; for use with IPv6 these fields contain 128 bits. In either
case the Key ID and Cookie fields contain 32 bits. Thus, an IPv4 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 private value, depending on the 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 at the end of the packet. For packets without extension fields, MAC. For packets without extension fields, the cookie is a shared
the cookie is a shared private value conveyed in encrypted form. For private value. For packets with extension fields, the cookie has a
packets with extension fields, the cookie has a default public value default public value of zero, since these packets are validated
of zero, since these packets can be validated independently using independently using digital signatures.
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 visible in the transmitted packet must be the same as those
used to construct the autokey sequence and key list and that these used to construct the autokey list and that these fields be the same
fields be the same as those visible in the received packet. as those visible in the received packet. [The use of alternative
means, such as Autokey host names (discussed later) or hashes of
For scenarios where the endpoint IP addresses are not available, an these names may be a topic for future study.]
optional public identification value could be used instead of the
addresses. Examples include the Interplanetary Internet, where
bundles are identified by name rather than address. Specific
provisions are for further study.
+-----------+-----------+------+------+ +---------+ +-----+------+ +-----------+-----------+------+------+ +---------+ +-----+------+
|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 Figure 3 shows how the autokey list and autokey values are
The key list consists of a sequence of key IDs starting with a random computed. The key IDs used in the autokey list consists of a
32-bit nonce (autokey seed) equal to or greater than the pivot as the sequence starting with a random 32-bit nonce (autokey seed) equal to
first key ID. The first autokey is computed as above using the given or greater than the pivot as the first key ID. The first autokey is
cookie and the first 32 bits of the result in network byte order computed as above using the given cookie and autokey seed and
become the next key ID. Operations continue to generate the entire assigned index 0. The first 32 bits of the result in network byte
list. It may happen that a newly generated key ID is less than the order become the next THe MD5 hash of the autokey is the key value
pivot or collides with another one already generated (birthday saved in the key cache along with the key ID. The first 32 bits of
event). When this happens, which occurs only rarely, the key list is the key become the key ID for the next autokey assigned index 1.
terminated at that point. The lifetime of each key is set to expire
one poll interval after its scheduled use. In the reference Operations continue to generate the entire list. It may happen that
implementation the list is terminated when the maximum key lifetime a newly generated key ID is less than the pivot or collides with
is about one hour, so for poll intervals above one hour a new key another one already generated (birthday event). When this happens,
list containing only a single entry is regenerated for every poll. which occurs only rarely, the key list is terminated at that point.
The lifetime of each key is set to expire one poll interval after its
scheduled use. In the reference implementation, the list is
terminated when the maximum key lifetime is about one hour, so for
poll intervals above one hour a new key list containing only a single
entry is regenerated for every poll.
+------------------+ +------------------+
| 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 |
skipping to change at page 12, line 4 skipping to change at page 11, line 22
| | | |
\|/ \|/ +---------+ \|/ \|/ +---------+
**************** +--------+ | Session | **************** +--------+ | Session |
* COMPUTE HASH *<---| Key ID |<---| Key ID | * COMPUTE HASH *<---| Key ID |<---| Key ID |
**************** +--------+ | List | **************** +--------+ | List |
| | +---------+ | | +---------+
\|/ \|/ \|/ \|/
+----------------------------------+ +----------------------------------+
| Message Authenticator Code (MAC) | | Message Authenticator Code (MAC) |
+----------------------------------+ +----------------------------------+
Figure 4: Transmitting Messages Figure 4: Transmitting Messages
The index of the last key ID in the list is saved along with the next The index of the last autokey in the list is saved along with the key
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. The list is used in reverse order as autokey values are then signed for use later. The list is used in
shown in Figure 4, so that the first autokey used is the last one reverse order as shown in Figure 4, so that the first autokey used is
generated. The Autokey protocol includes a message to retrieve the the last one generated.
autokey values and signature, so that subsequent packets can be
The Autokey protocol includes a message to retrieve the autokey
values and verify the signature, so that subsequent packets can be
validated using one or more hashes that eventually match the last key 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. Secure Groups 5. NTP Secure Groups
A digital signature scheme provides an authentic certificate trail, NTP secure groups are used to define cryptographic compartments and
but does not provide protection against masquerade, unless the server security hierarchies. A secure group consists of a number of hosts
identity is verified by other means. The PKI security model assumes dynamically assembled as a forest with roots the trusted hosts (THs)
each host is able to verify the certificate trail to a trusted at the lowest stratum of the group. The THs do not have to be, but
certificate authority (CA), where each ascendant host must prove often are, primary (stratum 1) servers. A trusted authority (TA),
identity to the immediately descendant host by independent means, not necessarily a group host, generates private identity keys for
such as a credit card number or PIN. While Autokey supports this servers and public identity keys for clients at the leaves of the
model by default, in a hierarchical ad-hoc network, especially with forest. The TA deploys the server keys to the THs and other
server discovery schemes like NTP Manycast, proving identity at each designated servers using secure means and posts the client keys on a
rest stop on the trail must be an intrinsic capability of Autokey public web site.
itself.
In the NTP security model every member of a closed group, such as For Autokey purposes all hosts belonging to a secure group have the
might be operated by a timestamping service, be in possession of a same group name but different host names, not necessarily related to
secret group key. This could take the form of a private certificate the DNS names. The group name is used in the subject and issuer
or one or another identification schemes described in the literature fields of the TH certificates; the host name is used in these fields
and Appendix D. Certificate trails and identification schemes are at for other hosts. Thus, all host certificates are self-signed.
the heart of the NTP security model preventing masquerade and During the Autokey protocol a client requests the server to sign its
middleman attacks. The Autokey protocol operates to hike the trails certificate and caches the result. A certificate trail is
and then run the identity schemes. constructed by each host, possibly via intermediate hosts and ending
at a TH. Thus, each host along the trail retrieves the entire trail
from its server(s) and provides this plus its own signed certicicates
to its clients.
A NTP secure group consists of a number of hosts dynamically Secure groups can be configured as hierarchies where a TH of one
assembled as a forest with roots the trusted hosts at the lowest group can be a client of one or more other groups operating at a
stratum of the group. The trusted hosts do not have to be, but often lower stratum. In one scenario, groups RED and GREEN can be
are, primary (stratum 1) servers. A trusted authority (TA), usually cryptographically distinct, but both be clients of group BLUE
one of the trusted hosts, generates private and public identity media operating at a lower stratum. In another scenario, group CYAN can be
and deploys selected values to the group members. The identity a client of multiple groups YELLOW and MAGENTA, both operating at a
values are of two kinds, encrypted private keys used by servers with lower stratum. There are many other scenarios, but all must be
dependent clients and nonencrypted public parameters used by all configured to include only acyclic certificate trails.
hosts, including those that are not group members, but depend on
group members for authentication purposes.Figure 5 In Figure 5, the Alice group consists of THs Alice, which is also the
TA, and Carol. Dependent servers Brenda and Denise have configured
Alice and Carol, respectively, as their time sources. Stratum 3
server Eileen has configured both Brenda and Denise as her time
sources. Public certificates are identified by the subject and
signed by the issuer. Note that the server keys have been previously
installed on Brenda and Denise and the client keys installed on all
machines.
+-------------+ +-------------+ +-------------+ +-------------+ +-------------+ +-------------+
| Alice | | Brenda | | Denise | | Alice | | Brenda | | Denise |
| | | | | | | | | | | |
| +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ |
Certificate | | Alice | | | | Brenda| | | | Denise| | Certificate | | Alice | | | | Brenda| | | | Denise| |
+-+-+-+-+-+ | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | +-+-+-+-+-+ | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ |
| Subject | | | Alice*| 1 | | | Alice | 4 | | | Carol | 4 | | Subject | | | Alice*| 1 | | | Alice | 4 | | | Carol | 4 |
+-+-+-+-+-+ | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | +-+-+-+-+-+ | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ |
| Issuer | S | | | | | | | Issuer | S | | | | | |
skipping to change at page 14, line 21 skipping to change at page 14, line 4
| | Eileen| 1 | | | Eileen| 1 |
| +-+-+-+-+ | | +-+-+-+-+ |
| | | |
| +=======+ | | +=======+ |
| ||Alice|| 3 | | ||Alice|| 3 |
| +=======+ | | +=======+ |
+---------------------------------------------+ +---------------------------------------------+
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. At startup each host loads its self-signed certificate from a 1. The girls start by loading the host key, sign key, self-signed
local file. By convention the lowest stratum certificates are certificate and group key. They start the Autokey protocol by
marked trusted in a X.509 extension field. As Alice and Carol exchanging host names and negotiating digest/signature schemes
have trusted certificates, they need do nothing further to and identity schemes.
validate the time. It could be that the trusted hosts depend on
servers in other groups; this scenario is discussed later.
2. The girls begin the Autokey protocol which establishes the server 2. They continue to load certificates recursively until a self-
name, signature scheme, certificate and identity scheme for each signed trusted certificate is found. Brenda and Denise
group host. They continue to load certificates recursively until immediately find trusted certificates for Alice and Carol,
a self-signed trusted certificate is found. Brenda and Denise respectively, but Eileen will loop because neither Brenda nor
immediately find self-signed trusted certificates for Alice and Denise have their own certificates signed by either Alice or
Carol, respectively, but Eileen will loop because neither Brenda
nor Denise have their own certificates signed by either Alice or
Carol. Carol.
3. Brenda and Denise continue with one of the identity schemes 3. Brenda and Denise continue with the selected identity schemes to
described below to verify each has the group keys previously verify that Alice and Carol have the correct group key previously
deployed by Alice. If this succeeds, each continues in step 4. generated by Alice. If this succeeds, each continues in step 4.
4. Brenda and Denise present their certificates to Alice and Carol
for signature. If this succeeds, either or both Brenda and
Denise can now provide these signed certificates to Eileen, which
may be looping in step 2. When Eileen receives them, she can now
follow the trail via either Brenda or Denise to the trusted
certificates for Alice and Carol. Once this is done, Eileen can
complete the protocol just as Brenda and Denise.
The NTP security model is based on multiple, hierarchical,
overlapping security compartments or groups. The example above
illustrates how groups can be used to construct closed compartments,
depending on how the identity credentials are deployed. The rules
can be summarized:
1. Every host holds the public parameters generated by a TA. Those
hosts with clients hold in addition the secret group key.
2. A host is trusted if it operates at the lowest stratum in the
group and has a trusted, self-signed certificate.
3. A host uses the identity scheme to prove to another host it has
the same group key, even as in some (zero knowledge) schemes
neither knows the exact key value.
4. A client verifies group membership if the server can prove it has 4. Brenda and Denise present their certificates for signature. If
the same key as the client and has an unbroken certificate trail this succeeds, either or both Brenda and Denise can now provide
to a trusted host. these signed certificates to Eileen, which may be looping in step
2. Eileen can now verify the trail via either Brenda or Denise
to the trusted certificates for Alice and Carol. Once this is
done, Eileen can complete the protocol just as Brenda and Denise.
For various reasons it may be convenient for the trusted hosts to For various reasons it may be convenient for a server to have client
hold parameters for one or more groups operating at a lower stratum. keys for more than one group. For example, Figure 6 shows three
For example, Figure 6 shows three secure groups Alice, Helen and secure groups Alice, Helen and Carol arranged in a hierarchy. Hosts
Carol arranged in a hierarchy. Hosts A, B, C and D belong to the A, B, C and D belong to Alice, R, S to Helen and X, Y and Z belong to
Alice group, hosts R and S to the Helen group and hosts X, Y and Z to Carol. While not strictly necessary, hosts A, B and R are stratum 1
the Carol group. While not strictly necessary, hosts A, B and R are and presumed trusted, but the TA generating the identity keys could
stratum 1 and presumed trusted; the TA generating the group keys and be one of them or another not shown.
parameters could be one of them or another not shown.
***** ***** @@@@@ ***** ***** @@@@@
Stratum 1 * A * * B * @ R @ Stratum 1 * A * * B * @ R @
***** ***** @@@@@ ***** ***** @@@@@
\ / / \ / /
\ / / \ / /
***** @@@@@ ********* ***** @@@@@ *********
2 * C * @ S @ * Alice * 2 * C * @ S @ * Alice *
***** @@@@@ ********* ***** @@@@@ *********
/ \ / / \ /
skipping to change at page 16, line 26 skipping to change at page 15, line 26
3 * D * # X # @@@@@@@@@ 3 * D * # X # @@@@@@@@@
***** ##### ***** #####
/ \ ######### / \ #########
/ \ # Carol # / \ # Carol #
##### ##### ######### ##### ##### #########
4 # Y # # Z # 4 # Y # # Z #
##### ##### ##### #####
Figure 6: Hierarchical Overlapping Groups Figure 6: Hierarchical Overlapping Groups
The intent of the design is to provide security separation, so that The intent of the scenario is to provide security separation, so that
servers cannot masquerade as TAs and clients cannot masquerade as servers cannot masquerade as in other groups and clients cannot
servers. Assume for example that Alice and Helen belong to national masquerade as servers. Assume for example that Alice and Helen
standards laboratories and their group keys are used to confirm belong to national standards laboratories and their server keys are
identity between members of each group. Carol is a prominent used to confirm identity between members of each group. Carol is a
corporation receiving standards products via broadcast satellite and prominent corporation receiving standards products and requiring
requiring cryptographic authentication. cryptographic authentication. Perhaps under contract, host X
belonging to Carol has client keys for both Alice and Helen and
server keys for Carol. The Autokey protocol operates for each group
separately while preserving security separation. Host X can prove
identity in Carol to clients Y and Z, but cannot prove to anybody
that it belongs to either Alice or Helen.
Perhaps under contract, host X belonging to the Carol group has 6. Identity Schemes
rented group parameters for both Alice and Helen and has group keys
for Carol. The Autokey protocol operates for each group separately
while preserving security separation. Host X can prove identity in
Carol to clients Y and Z, but cannot prove to anybody that it belongs
to either Alice or Helen.
In some scenarios it would be desirable that servers cannot A digital signature scheme provides secure server authentication, but
masquerade as the TA and clients cannot masquerade as servers. This it does not provide protection against masquerade, unless the server
can be assured using the MV identity scheme described later. It identity is verified by other means. The PKI model requires a server
allows the same broadcast transmission to be authenticated by more to prove identity to the client by a certificate trail, but
than one key, one used internally by the laboratories (Alice and/or independent means such as a drivers license are required for a CA to
Helen) and the other handed out to clients like Carol. In the MV sign the server certificate. While Autokey supports this model by
scheme these keys can be separately activated upon subscription and default, in a hierarchical ad-hoc network, especially with server
deactivated if the subscriber fails to pay the bill. In the MV discovery schemes like NTP Manycast, proving identity at each rest
scheme a key can be deactivated without requiring the other keys to stop on the trail must be an intrinsic capability of Autokey itself.
be recomputed.
Figure 7 shows operational details where more than one group is While the identity scheme described in [8] is based on a ubiquitous
involved, in this case Carol and Alice. As in the previous example, Diffie-Hellman infrastructure, it is expensive to generate and use
Brenda has configured Alice as her time source and Denise has when compared to others described in Appendix B. In principle, an
configured Carol as her time source. Alice and Brenda have group ordinary public key scheme could be devised for this purpose, but the
keys and parameters for the Alice group; Carol and Denise have group most stringent Autokey design requires that every challenge, even if
keys and parameters for the Carol group. Eileen has parameters for duplicated, results in a different acceptable response.
both groups. The protocol operates as previously described to verify
Alice to Brenda and Carol to Denise.
+-------------+ +-------------+ +-------------+ There are five schemes now implemented in the NTPv4 reference
| Alice | | Brenda | | Denise | implementation to prove identity: (1) private certificate (PC), (2)
| | | | | | trusted certificate (TC), (3) a modified Schnorr algorithm (IFF aka
| +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | Identify Friendly or Foe), (4) a modified Guillou-Quisquater
Certificate | | Alice | | | | Brenda| | | | Denise| | algorithm (GQ), and (5) a modified Mu-Varadharajan algorithm (MV).
+-+-+-+-+-+ | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ | Following is a summary description of each; details are given in
| Subject | | | Alice*| 1 | | | Alice | 4 | | | Carol | 4 | Appendix B.
+-+-+-+-+-+ | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ |
| Issuer | S | | | | | |
+-+-+-+-+-+ | +=======+ | | +-+-+-+-+ | | +-+-+-+-+ |
| ||Alice|| 3 | | | Alice | | | | Carol | |
Group Key | +=======+ | | +-+-+-+-+ | | +-+-+-+-+ |
+=========+ +-------------+ | | Alice*| 2 | | | Carol*| 2 |
|| Group || S | Carol | | +-+-+-+-+ | | +-+-+-+-+ |
+=========+ | | | | | |
| +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ |
S = step | | Carol | | | | Brenda| | | | Denise| |
* = trusted | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ |
| | Carol*| 1 | | | Brenda| 1 | | | Denise| 1 |
| +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ |
| | | | | |
| +=======+ | | +=======+ | | +=======+ |
| ||Carol|| 3 | | ||Alice|| 3 | | ||Carol|| 3 |
| +=======+ | | +=======+ | | +=======+ |
+-------------+ +-------------+ +-------------+
Stratum 1 Stratum 2
+---------------------------------------------+ The PC scheme involves a private certificate as group key. The
| Eileen | certificate is distributed to all other group members by secure means
| | and is never revealed outside the group. In effect, the private
| +-+-+-+-+ +-+-+-+-+ | certificate is used as a symmetric key. This scheme is used
| | Eileen| | Eileen| | primarily for testing and development and is not recommended for
| +-+-+-+-+ +-+-+-+-+ | regular use and is not considered further in this memo.
| | Brenda| | Carol | 4 |
| +-+-+-+-+ +-+-+-+-+ |
| |
| +-+-+-+-+ +-+-+-+-+ |
| | Alice | | Carol | |
| +-+-+-+-+ +-+-+-+-+ |
| | Alice*| | Carol*| 2 |
| +-+-+-+-+ +-+-+-+-+ |
| |
| +-+-+-+-+ +-+-+-+-+ |
| | Brenda| | Denise| |
| +-+-+-+-+ +-+-+-+-+ |
| | Alice | | Carol | 2 |
| +-+-+-+-+ +-+-+-+-+ |
| |
| +-+-+-+-+ |
| | Eileen| |
| +-+-+-+-+ |
| | Eileen| 1 |
| +-+-+-+-+ |
| |
| +=======+ +=======+ |
| ||Alice|| ||Carol|| 3 |
| +=======+ +=======+ |
+---------------------------------------------+
Stratum 3
Figure 7: Multiple Overlapping Groups All other schemes involve a conventional certificate trail as
described in RFC 2510 [9]. This is the default scheme when an
identity scheme is not specified. While the remaining identity
schemes incorporate TC, it is not by itself considered further in
this memo.
The interesting case is Eileen, who may verify identity either via The three remaining schemes IFF, GQ and MV involve a
Brenda or Denise or both. To do that she uses the public pameters of cryptographically strong challenge-response exchange where an
either Alice and Carol or both. But, Eileen doesn't know which of intruder cannot deduce the server key, even after repeated
the two parameters to use until hiking the certificate trail to find observations of multiple exchanges. In addition, the MV scheme is
the trusted certificate of either Alice or Carol and then loading the properly described as a zero-knowledge proof, because the client can
associated parameters. This scenario can of course become even more verify the server has the correct group key without either the server
complex as the number of servers and depth of the tree increase. The or client knowing its value. These schemes start when the client
bottom line is that every host must have the parameters for all the sends a nonce to the server, which then rolls its own nonce, performs
lowest-stratum trusted hosts it is ever likely to find. a mathematical operation and sends the results to the client. The
client performs another mathematical operation and verifies the
results are correct.
6. Identity Schemes 7. Timestamps and Filestamps
While the identity scheme described in [9] is based on a ubiquitous While public key signatures provide strong protection against
Diffie-Hellman infrastructure, it is expensive to generate and use misrepresentation of source, computing them is expensive. This
when compared to others described in Appendix D. There are five invites the opportunity for an intruder to clog the client or server
schemes now implemented in the NTPv4 reference implementation to by replaying old messages or originating bogus messages. A client
prove identity: (1) private certificate (PC), (2) trusted certificate receiving such messages might be forced to verify what turns out to
(TC), (3) a modified Schnorr algorithm (IFF aka Identify Friendly or be an invalid signature and consume significant processor resources.
Foe), (4) a modified Guillou-Quisquater algorithm (GQ), and (5) a
modified Mu-Varadharajan algorithm (MV). Following is a summary
description of each; details are given in Appendix D.
The PC scheme involves a private certificate as group key. A In order to foil such attacks, every Autokey message carries a
certificate is designated private by a X509 Version 3 extension field timestamp in the form of the NTP seconds when it was. If the system
when generated by utility routines in the NTP software distribution. clock is synchronized to a proventic source, a signature is produced
with valid (nonzero) timestamp. Otherwise, there is no signature and
the timestamp is invalid (zero). The protocol detects and discards
extension fields with old or duplicate timestamps, before any values
are used or signatures are verified.
The certificate is distributed to all other group members by secure Signatures are computed only when cryptgraphic values are created or
means and is never revealed outside the group. A client is marked modified, which is by design not very ofter. Extension fields
trusted when the first signature is verified. In effect, the private carrying these signatures are copied to messages as needed, but the
certificate is used as a symmetric key. This scheme is signarutres are not recomputed. There are three signature tyupes:
cryptographically strong as long as the private certificate is
protected; however, it can be very awkward to refresh the keys or
certificate, since new values must be securely distributed to a
possibly large population and activated simultaneously. It is
included here primarily as a yardstick and protocol exercise.
All other schemes involve a conventional certificate trail as 1. Cookie signature/timestamp. The cookie is signed when created by
described in RFC 4210 [10], where each certificate is signed by an the server and sent to the cliente.
issuer one step closer to the trusted hosts, which have self-signed
trusted certificates. A certificate is designated trusted by a X509
Version 3 extension field when generated by utility routines in the
NTP software distribution. A host obtains the certificates of all
other hosts along the trail ending at a trusted host, then requests
the immediately ascendant host to sign its own certificate.
Subsequently, these certificates are provided to descendent hosts by
the Autokey protocol. In this scheme keys, parameters and
certificates can be refreshed at any time, but a masquerade
vulnerability remains unless a request to sign a client certificate
is validated by some means such as reverse-DNS. If no specific
identity scheme is specified, this is the default TC identity scheme.
The three remaining schemes IFF, GQ and MV involve a 2. Autokey signature/timestamp. The autokey values are signed when
cryptographically strong challenge-response exchange where an the key list is created.
intruder cannot learn the group key, even after repeated observations
of multiple exchanges. In addition, the IFF and MV schemes are
properly described as zero-knowledge proofs, because the client can
verify the server has the group key without the client knowing its
value.
These schemes start when the client sends a nonce to the server, 3. Public values signature/timestamp. The public key, certificate
which then rolls its own nonce, performs a mathematical operation and and leapsecond values are signed at the time of generation, which
sends the results along with a message digest to the client. The occurs when the system clock is first synchronized to a proventic
client performs another mathematical operation and verifies the source, when the values have changed and about once per day after
results match the message digest. The IFF scheme is used when the that, even if these values have not changed.
certificate is generated by a third party, such as a commercial
service and in general has the same refreshment and distribution
problems as PC. However, this scheme has the advantage that the
group key is not known to the clients.
On the other hand, when certificates are generated by routines in the The most recent timestamp received of each type is saved for
NTPv4 distribution, the GQ scheme may be a better choice. In this comparison. Once a signature with valid timestamp has been received,
scheme the server further obscures the secret group key using a messages with invalid timestamps or earlier valid timestamps of the
public/private key pair which can be refreshed at any time. The same type are discarded before the signature is verified. This is
public member is conveyed in the certificate by a X509 Version 3 most important in broadcast mode, which could be vulnerable to a
extension field which changes for each regeneration of key pair and clogging attack without this test.
certificate.
The MV scheme is perhaps the most interesting and flexible of the All cryptographic values used by the protocol are time sensitive and
three challenge/response schemes. It can be used when a small number are regularly refreshed. In particular, files containing
of servers provide synchronization to a large client population where cryptographic values used by signature and encryption algorithms are
there might be considerable risk of compromise between and among the regenerated from time to time. It is the intent that file
servers and clients. The TA generates a deliciously intricate regenerations occur without specific advance warning and without
cryptosystem involving public and private encryption keys, together requiring prior distribution of the file contents. While
with a number of activation keys and associated private client cryptographic data files are not specifically signed, every file is
decryption keys. The activation keys are used by the TA to activate associated with a filestamp showing the NTP seconds at the creation
and revoke individual client decryption keys without changing the epoch.
decryption keys themselves.
The TA provides the server with a private encryption key and public Filestamps and timestamps can be compared in any combination and use
decryption key. The server adjusts the keys by a nonce for each the same conventions. It is necessary to compare them from time to
plaintext encryption, so they appear different on each use. The time to determine which are earlier or later. Since these quantities
encrypted ciphertext and adjusted public decryption key are provided have a granularity only to the second, such comparisons are ambiguous
in the client message. The client computes the decryption key from if the values are in the same second.
its private decryption key and the public decryption key in the
message.
7. Autokey Operations It is important that filestamps be proventic data; thus, they cannot
be produced unless the producer has been synchronized to a proventic
source. As such, the filestamps throughout the NTP subnet represent
a partial ordering of all creation epochs and serve as means to
expunge old data and insure new data are consistent. As the data are
forwarded from server to client, the filestamps are preserved,
including those for certificate and leapseconds values. Packets with
older filestamps are discarded before spending cycles to verify the
signature.
The Autokey protocol has three variations or dances corresponding to 8. Autokey Protocol Overview
the NTP server, symmetric and broadcast modes. The server dance was
suggested by Steve Kent over lunch some time ago, but considerably
modified since that meal. The server keeps no state for each client,
but uses a fast algorithm and a 32-bit random private value (server
seed) to regenerate the cookie upon arrival of a client packet. The
cookie is calculated as the first 32 bits of the autokey computed
from the client and server addresses, a key ID of zero and the server
seed as cookie. The cookie is used for the actual autokey
calculation by both the client and server and is thus specific to
each client separately.
In previous Autokey versions the cookie was transmitted in clear on The Autokey protocol includes a number of request/response exchanges
the assumption it was not useful to a wiretapper other than to launch that must be completed in order. In each exchange a client sends a
an ineffective replay attack. However, a middleman could intercept request message with data and expects a server response message with
the cookie and manufacture bogus messages acceptable to the client. data. Requests and responses are containined in extension fields,
In order to reduce the risk of such an attack, the Autokey Version 2 one request or response in each field, as described later. An NTP
server encrypts the cookie using a public key supplied by the client. packet can contain one request message and one or more response
While requiring additional processor resources for the encryption, messages. Following is a list of these messages.
this makes it effectively impossible to spoof a cookie or masquerade
as the server.
In the server dance the client uses the cookie and each key ID on the o Parameter exchange. The request includes the client host name;
key list in turn to retrieve the autokey and generate the MAC in the the response one contains the server host name and status word.
NTP packet. The server uses the same values to generate the message The status word specifies the digest/signature scheme it will use
digest and verifies it matches the MAC in the packet. It then and the identity schemes it supports.
generates the MAC for the response using the same values, but with
the client and server addresses exchanged. The client generates the
message digest and verifies it matches the MAC in the packet. In
order to deflect old replays, the client verifies the key ID matches
the last one sent. In this mode the sequential structure of the key
list is not exploited, but doing it this way simplifies and
regularizes the implementation while making it nearly impossible for
an intruder to guess the next key ID.
In the broadcast dance clients normally do not send packets to the o Certificate exchange. The request includes the subject name of a
server, except when first starting up to verify credentials and certificate; the response consists of a signed certificate with
calibrate the propagation delay. At the same time the client runs that subject name. If the the issuer name is not the same as the
the broadcast dance to obtain the autokey values. The dance requires subject name, it has been signed by a host one step closer to a
the association ID of the particular server association, since there trusted host and certificate retrieval continues for the issuer
can be more than one operating in the same server. For this purpose, name. If it is trusted and self-signed, the trail concludes at
the server packet includes the association ID in every response the trusted host. If nontrusted and self-signed, the host
message sent and, when sending the first packet after generating a certificate has not yet been signed, so the trail temporarily
new key list, it sends the autokey values as well. After obtaining loops. Completion of this exchange lights the VAL bit as
and verifying the autokey values, the client verifies further server described below.
packets using the autokey sequence.
The symmetric dance is similar to the server dance and keeps only a o Indentity exchange. The certificate trail is generally not
small amount of state between the arrival of a packet and departure considered sufficient protection against middleman attacks unless
of the reply. The key list for each direction is generated additional protection such as described inor proof-of-possession
separately by each peer and used independently, but each is generated scheme in [8] is available, but this is expensive and requires
with the same cookie. The cookie is conveyed in a way similar to the servers to retain state. Autokey can use one of the challenge/
server dance, except that the cookie is a random value. There exists response identity schemes described in Appendix B. Completion of
a possible race condition where each peer sends a cookie request this exchange lights the IFF bit as described below.
message before receiving the cookie response from the other peer. In
this case, each peer winds up with two values, one it generated and
one the other peer generated. The ambiguity is resolved simply by
computing the working cookie as the EXOR of the two values.
Autokey choreography includes one or more exchanges, each with a o Cookie exchange. The request includes the public key of the
specific purpose, that must be completed in order. The client client. THe response includes the server cookie encrypted with
obtains the server host name, digest/signature scheme and identity thise key. The client uses this value when constructing the key
scheme in the parameter exchange. It recursively obtains and list. Completion of this exchange lights the CKY bit as described
verifies certificates on the trail leading to a trusted certificate below.
in the certificate exchange and verifies the server identity in the
identity exchange. In the values exchange the client obtains the o Autokey exchange. The request includes either no data or the
cookie and autokey values, depending on the particular dance. autokey values of the peer in symmetric modes. The response
Finally, the client presents its self-signed certificate to the includes the autiokey values of the server or peer. These values
server for signature in the sign exchange. are used to verify the autokey sequence. Completion of this
exchange lights the AUT bit as described below.
o Sign exchange. This exchange is executed only when the client has
synchronized to a proventic source. The request includes the
self-signed client certificate. The server acting as CA
interprets the certificate as a X.509v3 certificate request. It
extracts the subject, issuer, and extension fields, builds a new
certificate with these data along with its own serial number and
expiration time, then signs it using its own public key and
includes it in the response. The client uses the signed
certificate in its own role as server for dependent clients.
Completion of this exchange lights the SGN bit as described below.
o Leapseconds exchange. This exchange is executed only when the
client has synchronized to a proventic source. This exchange
occurs when the server has the leapseconds values, as indicated in
the host status word. If so, the client requests the values and
compares them with its own values, if available. If the server
values are newer than the client values, the client replaces its
own with the server values. The client, acting as server, can now
provide the most recent values to its dependent clients. In
symmetric mode, this results in both peers having the newest
values. Completion of this exchange lights the LPT bit as
described below.
Once the certificates and identity have been validated, subsequent Once the certificates and identity have been validated, subsequent
packets are validated by digital signatures and autokey sequences. packets are validated by digital signatures and autokey sequences.
These packets are presumed to contain valid time values; however, The association is now proventic with respect to the downstratum
unless the system clock has already been set by some other proventic trusted host, but in not yet selectable to discipline the system
means, it is not known whether these values actually represent a clock. The associations accumulate time values and the mitigation
truechime or falsetick source. As the protocol evolves, the NTP algorithms continue in the usual way. When these algorithms have
associations continue to accumulate time values until a majority culled the falsetickers and cluster outlyers and at least three
clique is available in a population of at least three servers. At survivors remain, the system clock has been synchronized to a
this point the NTP mitigation algorithms cull the falsetickers and proventic sourc.
cluster outlyers from the population and the survivors are allowed to
discipline the system clock.
The time values for truechimer sources form a proventic partial 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 mitigate 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.
Once the Autokey values have been instantiated, the dances are 9. Autokey Operations
normally dormant. In all except the broadcast dance, packets are
normally sent without extension fields, unless the packet is the
first one sent after generating a new key list or unless the client
has requested the cookie or autokey values. If for some reason the
client clock is stepped, rather than slewed, all cryptographic and
time values for all associations are purged and the dances in all
associations restarted from scratch. This insures that stale values
never propagate beyond a clock step. At intervals of about one day
the reference implementation purges all associations, refreshes all
signatures, garbage collects expired certificates and refreshes the
server seed.
8. Public Key Signatures and Timestamps The NTP protocol has three principal modes of operation: client/
server, symmetric and broadast and each has its own Autokey program,
or dance. Autokey choreography is designed to be nonintrusive and to
require no additional packets other than for regular NTP operations.
The NTP and Autokey protocols operate simultaneously and
independently. When the dance is complete, subsequent packets are
validated by the autokey sequence and thus considered proventic as
well. Autokey assumes NTP clients poll servers at a relatively low
rate, such as once per minute or slower. In particular, it is
assumed that a request sent at one poll opportunity will normally
result in a response before the next poll opportunity; however the
protocol is robust against a missed or duplicate response.
While public key signatures provide strong protection against The server dance was suggested by Steve Kent over lunch some time
misrepresentation of source, computing them is expensive. This ago, but considerably modified since that meal. The server keeps no
invites the opportunity for an intruder to clog the client or server state for each client, but uses a fast algorithm and a 32-bit random
by replaying old messages or to originate bogus messages. A client private value (server seed) to regenerate the cookie upon arrival of
receiving such messages might be forced to verify what turns out to a client packet. The cookie is calculated as the first 32 bits of
be an invalid signature and consume significant processor resources. the autokey computed from the client and server addresses, key ID
zero and the server seed as cookie. The cookie is used for the
actual autokey calculation by both the client and server and is thus
specific to each client separately.
In order to foil such attacks, every signed extension field carries a In the server dance the client uses the cookie and each key ID on the
timestamp in the form of the NTP seconds at the signature epoch. The key list in turn to retrieve the autokey and generate the MAC. The
signature spans the entire extension field including the timestamp. server uses the same values to generate the message digest and
verifies it matches the MAC. It then generates the MAC for the
response using the same values, but with the client and server
addresses interchanged. The client generates the message digest and
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
the sequential structure of the key list is not exploited, but doing
it this way simplifies and regularizes the implementation while
making it nearly impossible for an intruder to guess the next key ID.
If the Autokey protocol has verified a proventic source and the NTP In the broadcast dance clients normally do not send packets to the
algorithms have validated the time values, the system clock can be server, except when first starting up. At that time the client runs
synchronized and signatures will then carry a nonzero (valid) the server dance to verify the server credentials and calibrate the
timestamp. Otherwise the system clock is unsynchronized and propagation delay. The dance requires the association ID of the
signatures carry a zero (invalid) timestamp. The protocol detects particular server association, since there can be more than one
and discards replayed extension fields with old or duplicate operating in the same server. For this purpose, the server packet
timestamps, as well as fabricated extension fields with bogus includes the association ID in every response message sent and, when
timestamps, before any values are used or signatures verified. sending the first packet after generating a new key list, it sends
the autokey values as well. After obtaining and verifying the
autokey values, no extension fields are necessary and the client
verifies further server packets using the autokey sequence.
There are three signature types currently defined: The symmetric dance is similar to the server dance and requires only
a small amount of state between the arrival of a request and
departure of the response. The key list for each direction is
generated separately by each peer and used independently, but each is
generated with the same cookie. The cookie is conveyed in a way
similar to the server dance, except that the cookie is a simple
nonce. There exists a possible race condition where each peer sends
a cookie request before receiving the cookie response from the other
peer. In this case, each peer winds up with two values, one it
generated and one the other peer generated. The ambiguity is
resolved simply by computing the working cookie as the EXOR of the
two values.
1. Cookie signature/timestamp. Each association has a cookie for Once the autokey dance has completed, it is normally dormant. In all
use when generating a key list. The cookie value is determined except the broadcast dance, packets are normally sent without
along with the cookie signature and timestamp upon arrival of a extension fields, unless the packet is the first one sent after
cookie request message. The values are returned in a a cookie generating a new key list or unless the client has requested the
response message. cookie or autokey values. If for some reason the client clock is
stepped, rather than slewed, all cryptographic and time values for
all associations are purged and the dances in all associations
restarted from scratch. This insures that stale values never
propagate beyond a clock step.
2. Autokey signature/timestamp. Each association has a key list for 10. Autokey Protocol Messages
generating the autokey sequence. The autokey values are
determined along with the autokey signature and timestamp when a
new key list is generated, which occurs about once per hour in
the reference implementation. The values are returned in a
autokey response message.
3. Public values signature/timestamp. All public key and The Autokey protocol data unit is the extension field, one or more of
certificate values are signed at the time of generation, which which can be piggybacked in the NTP packet. An extension field
occurs when the system clock is first synchronized to a proventic contains either a request with optional data or a response with
source, when the values have changed and about once per day after optional data. To avoid deadlocks, any number of responses can be
that, even if these values have not changed. During protocol included in a packet, but only one request. A response is generated
operations, each of these values and associated signatures and for every request, even if the requestor is not synchronized to a
timestamps are returned in the associated request or response proventic source, but most contain meaningful data only if the
message. While there are in fact several public value responder is synchronized to a proventic source. Some requests and
signatures, depending on the number of entries on the certificate most responses carry timestamped signatures. The signature covers
list, the values are all signed at the same time, so there is the entire extension field, including the timestamp and filestamp,
only one public value timestamp. where applicable. Only if the packet passes all extension field
tests are cycles spent to verify the signature.
The most recent timestamp received of each type is saved for There are currently eight Autokey requests and eight corresponding
comparison. Once a valid signature with valid timestamp has been responses. The NTP packet format is described in [1] and the
received, messages with invalid timestamps or earlier valid extension field format used for these messages is illustrated in
timestamps of the same type are discarded before the signature is Figure 7.
verified. For signed messages this deflects replays that otherwise
might consume significant processor resources. For other messages
the Autokey protocol deflects message modification or replay by a
wiretapper, but not necessarily by a middleman. In addition, the NTP
protocol itself is inherently resistant to replays and consumes only
minimal processor resources.
All cryptographic values used by the protocol are time sensitive and 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
are regularly refreshed. In particular, files containing +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
cryptographic basis values used by signature and encryption | Field Type | Length |
algorithms are regenerated from time to time. It is the intent that +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
file regenerations occur without specific advance warning and without | Association ID |
requiring prior distribution of the file contents. While +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
cryptographic data files are not specifically signed, every file is | Timestamp |
associated with a filestamp in the form of the NTP seconds at the +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
creation epoch. It is not the intent in this report to specify file | Filestamp |
formats or names or encoding rules; however, whatever conventions are +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
used must support a NTP filestamp in one form or another. Additional | Value Length |
details specific to the reference implementation are in Appendix A. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
\ /
/ Value \
\ /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Signature Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
\ /
/ Signature \
\ /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
\ /
/ Padding (if needed) \
\ /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Filestamps and timestamps can be compared in any combination and use Figure 7: NTPv4 Extension Field Format
the same conventions. It is necessary to compare them from time to
time to determine which are earlier or later. Since these quantities
have a granularity only to the second, such comparisons are ambiguous
if the values are in the same second. Thus, the ambiguity must be
resolved for each comparison operation as described in Appendix B.
It is important that filestamps be proventic data; thus, they cannot Each extension field is zero-padded to a 4 octet boundary. The
be produced unless the producer has been synchronized to a proventic Length field covers the entire extension field, including the Length
source. As such, the filestamps throughout the NTP subnet represent and Padding fields. While the minimum field length is 8 octets, a
a partial ordering of all creation epochs and serve as means to maximum field length remains to be established. The reference
expunge old data and insure new data are consistent. As the data are implementation discards any packet with a field length more than 1024
forwarded from server to client, the filestamps are preserved, octets.
including those for certificate files. Packets with older filestamps
are discarded before spending cycles to verify the signature.
9. Autokey Protocol Overview If an extension field is present, the parser examines the Length
field. If the length is less than 4 or not a multiple of 4, a format
error has occurred and the packet is discarded; otherwise, the parser
increments the pointer by the length value. The parser now uses the
same rules as above to determine whether a MAC is present and/or
another extension field.
This section presents an overview of the three dances: server, The 8-bit Code field specifies the request or response operation,
broadcast and symmetric. Each dance is designed to be nonintrusive while the 4-bit Version Number (VN) field is 2 for the current
and to require no additional packets other than for regular NTP protocol version. There are four flag bits: bit 0 is the Response
operations. The NTP and Autokey protocols operate independently and Flag (R) and bit 1 is the Error Flag (E); the other two bits are
simultaneously and use the same packets. When the preliminary dance presently unused and should be set to 0. The remaining fields will
exchanges are complete, subsequent packets are validated by the be described later.
autokey sequence and thus considered proventic as well. Autokey
assumes hosts poll servers at a relatively low rate, such as once per
minute or slower. In particular, it is assumed that a request sent
at one poll opportunity will normally result in a response before the
next poll opportunity; however the protocol is robust against a
missed or duplicate response.
The Autokey protocol data unit is the extension field, one or more of In the most common protocol operations, a client sends a request to a
which can be piggybacked in the NTP packet. An extension field server with an operation code specified in the Code field and both
contains either a request with optional data or a response with or the R bit and E bit dim. The Association ID field is set to the
without data. To avoid deadlocks, any number of responses can be value previously received from the server or 0 otherwise. The server
included in a packet, but only one request. A response is generated returns a response with the same operation code in the Code field and
for every request, even if the requestor is not synchronized to a lights the R bit. The server can also light the E bit in case of
proventic source, but contain meaningful data only if the responder error. The Association ID field is set to the association ID of the
is synchronized to a proventic source. Some requests and most server as a handle for subsequent exchanges. If for some reason the
responses carry timestamped signatures. The signature covers the association ID value in a request does not match the association ID
entire extension field, including the timestamp and filestamp, where of any mobilized association, the server returns the request with
applicable. Only if the packet passes all extension field tests are both the R and E bits lit. Note that it is not necessarily a
cycles spent to verify the signature. protocol error to send an unsolicited response with no matching
request.
All dances begin with the parameter exchange where the host obtains In some cases not all fields may be present. For requests, until a
the server host name and status word specifying the digest/signature client has synchronized to a proventic source, signatures are not
scheme it will use and the identity schemes it supports. The dance valid. In such cases the Timestamp and Signature Length fields are 0
continues with the certificate exchange where the host obtains and and the Signature field is empty. Responses are generated only when
verifies the certificates along the trail to a trusted, self-signed the responder has synchronized to a proventic source; otherwise, an
certificate usually, but not necessarily, provided by a primary error response message is sent. Some request and error response
(stratum 1) server. Primary servers are by design proventic with messages carry no value or signature fields, so in these messages
trusted, self-signed certificates. only the first two words are present.
However, the certificate trail is not sufficient protection against The Timestamp and Filestamp words carry the seconds field of an NTP
middleman attacks unless an identity scheme such as described in timestamp. The Timestamp field establishes the signature epoch of
Appendix D or proof-of-possession scheme in [9] is available. While the data field in the message, while the filestamp establishes the
the protocol for a generic challenge/response scheme is defined in generation epoch of the file that ultimately produced the data that
this report, the choice of one or another required or optional is signed. A signature and timestamp are valid only when the signing
identification schemes is yet to be determined. If all certificate host is synchronized to a proventic source; otherwise, the timestamp
signatures along the trail are verified and the server identity is is zero. A cryptographic data file can only be generated if a
confirmed, the host continues with the cookie and autokey exchanges signature is possible; otherwise, the filestamp is zero, except in
as necessary to complete the protocol. Upon completion the host the ASSOC response message, where it contains the server status word.
verifies packets using digital signatures and/or the autokey
sequence.
Once synchronized to a proventic source, the host continues with the Unless specified otherwise in the descriptions to follow, the data
sign exchange where the server acting as CA signs the host referred to are stored in the Value field.
certificate. The CA interprets the certificate as a X.509v3
certificate request, but verifies the signature if it is self-signed.
The CA extracts the subject, issuer, extension fields and public key,
then builds a new certificate with these data along with its own
serial number and begin and end times, then signs it using its own
public key. The host uses the signed certificate in its own role as
CA for dependent clients.
A final exchange occurs when the server has the NIST leapseconds 10.1. No-Operation
table, as indicated in the host status word. If so, the host
requests the table and compares the filestamp with its own
leapseconds table filestamp, if available. If the server table is
newer than the host table, the host replaces its table with the
server table. The host, acting as server, can now provide the most
recent table to its dependent clients. In symmetric mode, this
results in both peers having the newest table.
10. Autokey State Machine A No-operation request (Field Type = 0) does nothing except return an
empty response which can be used as a crypto-ping.
10.2. Association Message (ASSOC)
An Association Message (Field Type = 1) is used in the parameter
exchange to obtain the host name and status word. The request
contains the client status word in the Filestamp field and the host
name in the Value field. The response contains the server status
word in the Filestamp field and the host name in the Value field. By
default the host name is the string returned by the Unix
gethostname() library function. While minimum and maximum host name
lengths remain to be established, the reference implementation uses
the values 4 and 256, respectively.
When multiple identity schemes are supported, the status words
determine which one is used. The request message contains bits
corresponding to the schemes the client supports, while the response
message contains bits corresponding to the schemes the server
supports. The server and client do an AND operation on the status
words to select compatible identity schemes. If multiple schemes
result, the bits are ranked from right to left.
10.3. Certificate Message (CERT)
A Certificate Message (Field Type = 2) is used in the certificate
exchange to obtain a certificate by name. The request contains the
subject name; the response contains the certificate encoded in X.509
format with ASN.1 syntax as described in Appendix C.
If the subject name in the response does not match the issuer name,
the exchange continues with the issuer name replacing the subject
name in the request. The exchange continues until a trusted, self-
signed certificate is found.
10.4. Cookie Message (COOKIE)
The Cookie Message (Field Type = 3) is used in server and symmetric
modes to obtain the server cookie. The request contains the host
public key encoded with ASN.1 syntax as described in Appendix C. The
response contains the cookie encrypted by the public key in the
request.
10.5. Autokey Message (AUTO)
The Autokey Message (Field Type = 4) is used to obtain the autokey
values. The request contains no value. The response contains two
32-bit words in network byte order. The first word is the final key
ID, while the second is the index of the final key ID.
10.6. Leapseconds Values Message (LEAP)
The Leapseconds Values Message (Field Type = 5) is used to obtain the
leapseconds values as parsed from the leapseconds table from NIST.
The request and response messages have the same format, except that
the R bit is set to 0 in the request and set to 1 in the response.
Both the request and response contains three 32-bit integers, the NTP
seconds of the latest leap event followed by the NTP seconds when the
latest NIST table expires and then the TAI offset following the leap
event.
10.7. Sign Message (SIGN)
The Sign Message (Field Type = 6) requests the server to sign and
return a certificate presented in the request. The request contains
the client certificate encoded in X.509 format with ASN.1 syntax as
described in Appendix C. The response contains the client
certificate signed by the server private key.
10.8. Identity Messages (IFF, GQ, MV)
The Identity Messages (Field Type = 7 (IFF), 8 (GQ), or 9 (MV))
contains the client challenge, usually a 160- or 512-bit nonce. The
response contains the result of the mathematical operation defined in
Appendix B. The Response is encoded in ASN.1 syntax as described in
Appendix C.
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.
10.1. Status Word 11.1. Status Word
Each server and client operating also as a server implements a host Each server and client operating also as a server implements a host
status word, while each client implements an association status word status word, while each client implements an association status word
for each server. Both words have the format and content shown in for each server. Both words have the format and content shown in
Figure 8. The low order 16 bits of the status word define the state Figure 8. The low order 16 bits of the status word define the state
of the Autokey protocol, while the high order 16 bits specify the of the Autokey protocol, while the high order 16 bits specify the
message digest/signature encryption scheme. as encoded in the OpenSSL message digest/signature encryption scheme as encoded in the OpenSSL
library. Bits 24-31 of the status word are reserved for server use, library. Bits 24-31 of the status word are reserved for server use,
while bits 16-23 are reserved for client association use. In the while bits 16-23 are reserved for client association use. In the
host portion bits 24-27 specify the available identity schemes, while host portion bits 24-27 specify the available identity schemes, while
bits 28-31 specify the server capabilities. There are four bits 28-31 specify the server capabilities. There are two additional
additional bits implemented separately. 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 status bits as the dance proceeds. Once and then lights additional status bits as the dance proceeds. Once
enabled, these bits never come dim unless a general reset occurs and enabled, these bits never come dark unless a general reset occurs and
the protocol is restarted from the beginning. The status bits are the protocol is restarted from the beginning. The status bits are
defined as follows: defined as follows:
o ENB (31) - Lit if the server implements the Autokey protocol o ENB (31) - Lit if the server implements the Autokey protocol
o LPF (30) - Lit if the server has loaded a valid leapseconds file o LPF (30) - Lit if the server has loaded leapseconds values
o IDN (24-27) - These four bits select which identity scheme is in o IDN (24-27) - These four bits select which identity scheme is in
use. While specific coding for various schemes is yet to be use. While specific coding for various schemes is yet to be
determined, the schemes available in the reference implementation determined, the schemes available in the reference implementation
and described in Appendix D include the following: and described in Appendix B include the following:
* 0x0 Trusted Certificate (TC) Scheme (default) * 0x0 Trusted Certificate (TC) Scheme (default)
* 0x1 Private Certificate (PC) Scheme * 0x1 Private Certificate (PC) Scheme
* 0x2 Schnorr aka Identify-Friendly-or-Foe (IFF) Scheme * 0x2 Schnorr aka Identify-Friendly-or-Foe (IFF) Scheme
* 0x4 Guillard-Quisquater (GC) Scheme * 0x4 Guillard-Quisquater (GC) Scheme
* 0x8 Mu-Varadharajan (MV) Scheme * 0x8 Mu-Varadharajan (MV) Scheme
The PC scheme is exclusive of any other scheme. Otherwise, the IFF, The PC scheme is exclusive of any other scheme. Otherwise, the IFF,
GQ and MV bits can be lit in any combination. 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 VAL (0x0100) - Lit when the server certificate and public key are o VAL (0x0100) - Lit when the server certificate and public key are
validated. validated.
o IFF (0x0200) - Lit when the server identity credentials are o IFF (0x0200) - Lit when the server identity credentials are
confirmed. confirmed.
o PRV (0x0400) - Lit when the server signature is verified using the o PRV (0x0400) - Lit when the server signature is verified using the
public key and identity credentials. Also called the proventic public key and identity credentials. Also called the proventic
bit elsewhere in this report. 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 CKY (0x0800) - Lit when the cookie is received and validated. o CKY (0x0800) - Lit when the cookie is received and validated.
When enabled, key lists can be generated. When enabled, key lists with nonzero cookies can be generated.
o AUT (0x1000) - Lit when the autokey values are received and o AUT (0x1000) - Lit when the autokey values are received and
validated. When enabled, clients can validate packets without validated. When enabled, clients can validate packets without
extension fields according to the autokey sequence. extension fields according to the autokey sequence.
o SGN (0x2000) - Lit when the host certificate is signed by the o SGN (0x2000) - Lit when the host certificate is signed by the
server. server.
o LPT (0x4000) - Lit when the leapseconds table is received and o LPT (0x4000) - Lit when the leapseconds values are received and
validated. validated.
There are four additional status bits LST, LBK, DUP, and SYN not There are four additional status bits LST and SYN not included in the
included in the status word. All except SYN are association status word. LST is a client propertie, while SYN is a host
properties, while SYN is a host property. These bits may be enabled property. LST is lit when the key list is regenerated and signed and
(set to 1) or disabled (set to 0) as the protocol proceeds; all DIM when the autokey values have been transmitted. This is necessary
except LST are active whether or not the protocol is running. LST is to avoid livelock under some conditions. SYN is lit when the client
enabled when the key list is regenerated and signed and comes dim
after the autokey values have been transmitted. This is necessary to
avoid livelock under some conditions. SYN is enabled when the client
has synchronized to a proventic source and never dim after that. has synchronized to a proventic source and never dim after that.
There are two error bits maintained by the NTP on-wire protocol:
o LBK - indicates the received packet does not match the last one
sent
o DUP - indicates a duplicate packet
These bits, which are described in Appendix B, are lit if the 11.2. Host State Variables
corresponding error has occurred for the current packet and dim
otherwise.
10.2. Host State Variables
Following is a list of state variables used by the server protocol. Following is a list of state variables used by the server protocol.
o Host Name - The name of the server; by default, the string o Host Name - The name of the host, by default the string returned
returned by the Unix gethostname() library function. The name by the Unix gethostname() library function.
must agree with the subject name in the server certificate
o Host Status Word - This word is initialized when the host first o 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.
o Host Key - The RSA public/private key pair used to encrypt/decrypt o Host Key - The RSA public/private key pair used to encrypt/decrypt
cookies. This is also the default sign key cookies. This is also the default sign key.
o Sign Key - The RSA or DSA public/private key pair used to encrypt/ o Sign Key - The RSA or DSA public/private key pair used to encrypt/
decrypt signatures when the host key is not used for this purpose decrypt signatures when the host key is not used for this purpose.
o Sign Digest - The message digest algorithm used to compute the o Sign Digest - The message digest algorithm used to compute the
signature before encryption signature before encryption.
o IFF identity - The keys and parameters used in the optional IFF o IFF Parameters - The parameters used in the optional IFF identity
identity scheme described in Appendix D scheme described in Appendix B.
o GQ identity - The keys and parameters used in the optional GQ o GQ Parameters - The parameters used in the optional GQ identity
identity scheme described in Appendix D scheme described in Appendix B.
o MV identity - The keys and parameters used in the optional MV o MV Parameters - The parameters used in the optional MV identity
identity scheme described in Appendix D scheme described in Appendix B.
o Server Seed - The private value hashed with the IP addresses to o Server Seed - The private value hashed with the IP addresses to
construct the cookie construct the cookie.
o Certificate Information Structure (CIS) - Certificates are used to o Certificate Information Structure (CIS) - Certificates are used to
construct certificate information structures (CIS) which are construct certificate information structures (CIS) which are
stored on the certificate list. The structure includes certain stored on the certificate cache. The structure includes certain
information fields from an X.509v3 certificate, together with the information fields from an X.509v3 certificate, together with the
certificate itself encoded in ASN.1 syntax. Each structure certificate itself encoded in ASN.1 syntax. Each structure
carries the public value timestamp and the filestamp of the carries the public value timestamp and the filestamp of the
certificate file when it was generated. Elsewhere in this report certificate file where it was generated. Elsewhere in this memo
the CIS will not be distinguished from the certificate unless the CIS will not be distinguished from the certificate unless
noted otherwise. A flags field in the CIS determines the status noted otherwise. A flags field in the CIS determines the status
of the certificate. The field is encoded as follows: of the certificate. The field is encoded as follows:
* TRST (0x01) - The certificate has been signed by a trusted * TRST (0x01) - The certificate has been signed by a trusted
issuer. If the certificate is self-signed and contains issuer. If the certificate is self-signed and contains
"trustRoot" in the Extended Key Usage field, this bit will be "trustRoot" in the Extended Key Usage field, this bit is lit
lit when the CIS is constructed when the CIS is constructed
* SIGN (0x02) - The certificate signature has been verified. If * SIGN (0x02) - The certificate signature has been verified. If
the certificate is self-signed and verified using the contained the certificate is self-signed and verified using the contained
public key, this bit will lit when the CIS is constructed public key, this bit is lit when the CIS is constructed.
* VALD (0x04) - The certificate is valid and can be used to * VALD (0x04) - The certificate is valid and can be used to
verify signatures. This bit is lit when a trusted certificate verify signatures. This bit is lit when a trusted certificate
has been found on a valid certificate trail has been found on a valid certificate trail.
* PRIV (0x08) - The certificate is private and not to be * PRIV (0x08) - The certificate is private and not to be
revealed. If the certificate is self-signed and contains revealed. If the certificate is self-signed and contains
"Private" in the Extended Key Usage field, this bit will be lit "Private" in the Extended Key Usage field, this bit is lit when
when the CIS is constructed the CIS is constructed.
* ERRR (0x80) - The certificate is defective and not to be used * ERRR (0x80) - The certificate is defective and not to be used
in any way in any way.
o Certificate List - CIS structures are stored on the certificate o Certificate List - CIS structures are stored on the certificate
list in order of arrival, with the most recently received CIS list in order of arrival, with the most recently received CIS
placed first on the list. The list is initialized with the CIS placed first on the list. The list is initialized with the CIS
for the host certificate, which is read from the certificate file. for the host certificate, which is read from the certificate file.
Additional CIS entries are pushed on the list as certificates are Additional CIS entries are pushed on the list as certificates are
obtained from the servers during the certificate exchange. CIS obtained from the servers during the certificate exchange. CIS
entries are discarded if overtaken by newer ones or expire due to entries are discarded if overtaken by newer ones or expire due to
old age old age.
o Host Certificate - The self-signed X.509v3 certificate for the o Host Certificate - The self-signed X.509v3 certificate for the
host. The subject and issuer fields consist of the host name, host. The subject and issuer fields consist of the host name,
while the message digest/signature encryption scheme consists of while the message digest/signature encryption scheme consists of
the sign key and message digest defined above. Optional the sign key and message digest defined above. Optional
information used in the identity schemes is carried in X.509v3 information used in the identity schemes is carried in X.509v3
extension fields compatible with [11] extension fields compatible with [10].
o Public Key Values - The public encryption key for the COOKIE o Public Key Values - The public encryption key for the COOKIE
request, which consists of the public value of the host key. It request, which consists of the public value of the host key. It
carries the public values timestamp and the filestamp of the host carries the public values timestamp and the filestamp of the host
key file key file.
o Leapseconds Table Values. The NIST leapseconds table from the o Leapseconds Values. The leapseconds values parsed from the NIST
NIST leapseconds file. It carries the public values timestamp and leapseconds file. It carries the public values timestamp and the
the filestamp of the leapseconds file filestamp of the leapseconds values.
10.3. Client State Variables (all modes) 11.3. Client State Variables (all modes)
Following is a list of state variables used by the client association Following is a list of state variables used by the client association
protocol in all modes. protocol in all modes.
o Association ID - The association ID used in responses. It is o Association ID - The association ID used in responses. It is
assigned when the association is mobilized assigned when the association is mobilized
o Server Association ID - The server association ID used in o Server Association ID - The server association ID used in
requests. It is copied from the first nonzero association ID requests. It is copied from the first nonzero association ID
field in a response field in a response
o Server Host Name - The server host name determined in the o Server Subject Name - The server host name determined in the
parameter exchange parameter exchange
o Server Issuer Name - The host name signing the certificate. It is o Server Issuer Name - The host name signing the certificate. It is
extracted from the current server certificate upon arrival and extracted from the current server certificate upon arrival and
used to request the next item on the certificate trail used to request the next item on the certificate trail
o Association Status Word - The host status word of the server o Association Status Word - The host status word of the server
determined in the parameter exchange determined in the parameter exchange
o Server Public Key - The public key used to decrypt signatures. It o Server Public Key - The public key used to decrypt signatures. It
skipping to change at page 30, line 47 skipping to change at page 30, line 14
o Group Key - A set of values used by the identification exchange. o Group Key - A set of values used by the identification exchange.
It identifies the cryptographic compartment shared by the server It identifies the cryptographic compartment shared by the server
and client and client
o Receive Cookie Values - The cookie returned in a COOKIE response, o Receive Cookie Values - The cookie returned in a COOKIE response,
together with its timestamp and filestamp together with its timestamp and filestamp
o Receive Autokey Values - The autokey values returned in an AUTO o Receive Autokey Values - The autokey values returned in an AUTO
response, together with its timestamp and filestamp response, together with its timestamp and filestamp
o Receive Leapsecond Values - The leapsecond table returned by a 11.4. Server State Variables (broadcast and symmetric modes)
LEAP response, together with its timestamp and filestamp
10.4. Server State Variables (broadcast and symmetric modes)
Following is a list of server state variables used in broadcast and Following is a list of server state variables used in broadcast and
symmetric modes. symmetric modes.
o Send Cookie Values - The cookie encryption values, signature and o Send Cookie Values - The cookie encryption values, signature and
timestamps timestamps
o Send Autokey Values - The autokey values, signature and timestamps o Send Autokey Values - The autokey values, signature and timestamps
o Key List - A sequence of key IDs starting with the autokey seed o Key List - A sequence of key IDs starting with the autokey seed
and each pointing to the next. It is computed, timestamped and and each pointing to the next. It is computed, timestamped and
signed at the next poll opportunity when the key list becomes signed at the next poll opportunity when the key list becomes
empty empty
o Current Key Number - The index of the entry on the Key List to be o Current Key Number - The index of the entry on the Key List to be
used at the next poll opportunity used at the next poll opportunity
10.5. Autokey Protocol Messages 11.5. Protocol State Transitions
There are currently eight Autokey requests and eight corresponding
responses. The NTPv4 packet format is described in [1] and the
extension field format used for these messages is illustrated in
Figure 9.
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Field Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Association ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Timestamp |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Filestamp |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Value Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
\ /
/ Value \
\ /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Signature Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
\ /
/ Signature \
\ /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
\ /
/ Padding (if needed) \
\ /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 9: NTPv4 Extension Field Format
Each extension field is zero-padded to a 4-octet boundary. The
Length field covers the entire extension field, including the Length
and Padding fields. While the minimum field length is 8 octets, a
maximum field length remains to be established. The reference
implementation discards any packet with a total field length more
than 1024 octets.
If an extension field is present, the parser examines the Length
field. If the length is less than 4 or not a multiple of 4, a format
error has occurred and the packet MUST be discarded; otherwise, the
parser increments the pointer by the length value. The parser now
uses the same rules as above to determine whether a MAC is present
and/or another extension field.
The 8-bit Code field specifies the request or response operation,
while the 4-bit Version Number (VN) field is 2 for the current
protocol version. There are four flag bits: bit 0 is the Response
Flag (R) and bit 1 is the Error Flag (E); the other two bits are
presently unused and should be set to 0. The remaining fields will
be described later.
In the most common protocol operations, a client sends a request to a
server with an operation code specified in the Code field and both
the R bit and E bit dim. The Association ID field is set to the
value previously received from the server or 0 otherwise. The server
returns a response with the same operation code in the Code field and
lights the R bit. The server can also light the E bit in case of
error. The Association ID field is set to the association ID of the
server as a handle for subsequent exchanges. If for some reason the
association ID value in a request does not match the association ID
of any mobilized association, the server returns the request with
both the R and E bits lit. Note that it is not necessarily a
protocol error to send an unsolicited response with no matching
request.
In some cases not all fields may be present. For requests, until a
client has synchronized to a proventic source, signatures are not
valid. In such cases the Timestamp and Signature Length fields are 0
and the Signature field is empty. Responses are generated only when
the responder has synchronized to a proventic source; otherwise, an
empty response message is sent. Some request and error response
messages carry no value or signature fields, so in these messages
only the first two words are present.
The Timestamp and Filestamp words carry the seconds field of an NTP
timestamp. The Timestamp field establishes the signature epoch of
the data field in the message, while the filestamp establishes the
generation epoch of the file that ultimately produced the data that
is signed. A signature and timestamp are valid only when the signing
host is synchronized to a proventic source; otherwise, the timestamp
is zero. A cryptographic data file can only be generated if a
signature is possible; otherwise, the filestamp is zero, except in
the ASSOC response message, where it contains the server status word.
10.5.1. No-Operation
A No-operation request (Field Type = 0) does nothing except return an
empty reply which can be used as a crypto-ping.
10.5.2. Association Message (ASSOC)
An Association Message (Field Type = 1) is used in the parameter
exchange to obtain the host name and related values. The request
contains the host status word in the filestamp field. The response
contains the server status word in the filestamp field and in
addition the host name, which by default is the string returned by
the Unix gethostname() library function. While minimum and maximum
host name lengths remain to be established, the reference
implementation uses the values 4 and 256, respectively. The
remaining fields are defined previously in this report.
If the server response is acceptable and both server and client share
the same identity scheme, ENB is lit. When the PC identity scheme is
in use, the ASSOC response lights VAL, IFF, and SIG, since the PC
exchange is complete at this point.
10.5.3. Certificate Message (CERT)
A Certificate Message (Field Type = 2) is used in the certificate
exchange to obtain a certificates and related values by subject name.
The request contains the subject name. For the purposes of
interoperability with older Autokey versions, if only the first two
words are sent, the request is for the server host certificate. The
response contains the certificate encoded in X.509 format with ASN.1
syntax as described in Appendix E.
If the subject name in the response does not match the issuer name,
the exchange continues with the issuer name replacing the subject
name in the request. The exchange continues until either the subject
name matches the issuer name, indicating a self-signed certificate,
or the trst bit is set in the CIS, indicating a trusted certificate.
If a trusted certificate is found, the client stops the exchange and
lights VAL. If a self-signed certificate is found but not trusted,
the protocol loops at polite intervals until one is found or timeout.
10.5.4. Cookie Message (COOKIE)
The Cookie Message (Field Type = 3) is used in server and symmetric
modes to obtain the server cookie. The request contains the host
public key encoded with ASN.1 syntax as described in Appendix E. The
response contains the cookie encrypted by the public key in the
request. The signature and timestamps are determined when the cookie
is encrypted. If the response is valid, the client lights CKY.
10.5.5. Autokey Message (AUTO)
The Autokey Message (Field Type = 4) is used to obtain the autokey
values. The request contains no value. The response contains two
32-bit words in network order. The first word is the final key ID,
while the second is the index of the final key ID. The signature and
timestamps are determined when the key list is generated. If the
response is valid, the client lights AUT.
10.5.6. Leapseconds Table Message (LEAP)
The Leapseconds Table Message (Field Type = 5) is used to exchange
leapseconds tables. The request and response messages have the same
format, except that the R bit is dim in the request and lit in the
response. Both the request and response contains the leapseconds
table as parsed from the NIST leapseconds file. If the client
already has a copy of the leapseconds data, it uses the one with the
latest filestamp and discards the other. If the response is valid,
the client lights LPT.
10.5.7. Sign Message (SIGN)
The Sign Message (Field Type = 6) requests the server to sign and
return the certificate presented in the request. The request
contains the client certificate encoded in X.509 format with ASN.1
syntax as described in Appendix E. The response contains the client
certificate signed by the server private key. If the certificate is
valid when received by the host, it is linked in the certificate list
and SGN is lit.
10.5.8. Identity Messages (IFF, GQ, MV)
The Identity Messages (Field Type = 7 (IFF), 8 (GQ), or 9 (MV))
contains the host challenge, usually a 160- or 512-bit nonce. The
response contains the result of the mathematical operation defined in
Appendix D. The Response is encoded in ASN.1 syntax as described in
Appendix E. The response signature and timestamp are determined when
the response is sent. If the response is valid, IFF is lit.
10.6. 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 server status bits defined above. The state determined by the server status 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 server status bits. All server bits are truth values represent the server status bits. All server bits are
initialized dim and lit upon the arrival of a specific response initialized dark and are lit upon the arrival of a specific response
message, as detailed above. message, as detailed above.
When the system clock is first set and about once per day after that, 11.5.1. Server Dance
or when the system clock is stepped, the server seed is refreshed,
signatures and timestamps updated and the protocol restarted in all
associations. When the server seed is refreshed or a new certificate
or leapseconds table is received, the public values timestamp is
reset to the current time and all signatures are recomputed.
10.6.1. Server Dance
The server dance begins when the host sends an ASSOC request to the The server dance begins when the client sends an ASSOC request to the
server. It ends when the first signature is verified and PRV is lit. server. It ends when the first signature is verified and PRV is lit.
Subsequent packets received without extension fields are validated by Subsequent packets received without extension fields are validated by
the autokey sequence. An optional LEAP exchange updates the the autokey sequence. An optional LEAP exchange updates the
leapseconds table. Note the order of the identity exchanges and that leapseconds values. Note the order of the identity exchanges and
only the first one will be used if multiple schemes are available. that only the first one will be used if multiple schemes are
Note also that the SIGN and LEAP requests are not issued until the available. Note also that the SIGN and LEAP requests are not issued
client has synchronized to a proventic source. until the client has synchronized to a proventic source.
while (1) { while (1) {
wait_for_next_poll; wait_for_next_poll;
make_NTP_header; make_NTP_header;
if (response_ready) if (response_ready)
send_response; send_response;
if (!ENB) if (!ENB)
/ * parameters exchange */ / * parameters exchange */
ASSOC_request; ASSOC_request;
else if (!VAL) else if (!VAL)
skipping to change at page 36, line 48 skipping to change at page 31, line 37
COOKIE_request; COOKIE_request;
else if (SYN && !SIG) else if (SYN && !SIG)
/* signe exchange */ /* signe exchange */
SIGN_request(Host_Certificate); SIGN_request(Host_Certificate);
else if (SYN && LPF & !LPT) else if (SYN && LPF & !LPT)
/* leapseconds exchange */ /* leapseconds exchange */
LEAP_request; LEAP_request;
} }
When the PC identity scheme is in use, the ASSOC response lights VAL, When the PC identity scheme is in use, the ASSOC response sets VAL,
IFF, and SIG; the COOKIE response lights CKY and AUT; and the first IFF, and SIG to 1; the COOKIE response sets CKY and AUT to 1; and the
valid signature lights PRV. first valid signature sets PRV to 1.
10.6.2. Broadcast Dance 11.5.2. Broadcast Dance
The only difference between the broadcast and server dances is the The only difference between the broadcast and server dances is the
inclusion of an autokey values exchange following the cookie inclusion of an autokey values exchange following the cookie
exchange. The broadcast dance begins when the host receives the exchange. The broadcast dance begins when the client receives the
first broadcast packet, which includes an ASSOC response with first broadcast packet, which includes an ASSOC response with
association ID. The host uses the association ID to initiate a association ID. The broadcast client uses the association ID to
server dance in order to calibrate the propagation delay. initiate a server dance in order to calibrate the propagation delay.
The dance ends when the first signature is verified and PRV is lit. The dance ends when the first signature is verified and PRV is lit.
Subsequent packets received without extension fields are validated by Subsequent packets received without extension fields are validated by
the autokey sequence. An optional LEAP exchange updates the the autokey sequence. An optional LEAP exchange updates the
leapseconds table. When the server generates a new key list, the leapseconds values. When the server generates a new key list, the
server replaces the ASSOC response with an AUTO response in the first server replaces the ASSOC response with an AUTO response in the first
packet sent. packet sent.
while (1) { while (1) {
wait_for_next_poll; wait_for_next_poll;
make_NTP_header; make_NTP_header;
if (response_ready) if (response_ready)
send_response; send_response;
if (!ENB) if (!ENB)
/* parameters exchange */ /* parameters exchange */
skipping to change at page 38, line 6 skipping to change at page 32, line 42
/* autokey values exchange */ /* autokey values exchange */
AUTO_request; AUTO_request;
else if (SYN &&! SIG) else if (SYN &&! SIG)
/* sign exchange */ /* sign exchange */
SIGN_request(Host_Certificate); SIGN_request(Host_Certificate);
else if (SYN && LPF & !LPT) else if (SYN && LPF & !LPT)
/* leapseconds exchange */ /* leapseconds exchange */
LEAP_request; LEAP_request;
} }
When the PC identity scheme is in use, the ASSOC response sets VAL, When the PC identity scheme is in use, the ASSOC response lights VAL,
IFF, and SIG to 1; the COOKIE response sets CKY and AUT to 1; and the IFF, and SIG; the COOKIE response lights CKY and AUT; and the first
first valid signature set PRV to 1. valid signature lights PRV.
10.6.3. Symmetric Dance 11.5.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 the same dance from peer mobilizes an association and both peers step the same dance from
the beginning. Until the active peer is synchronized to a proventic the beginning. Until the active peer is synchronized to a proventic
source (which could be the passive peer) and can sign messages, the source (which could be the passive peer) and can sign messages, the
passive peer loops waiting for the timestamp in the ASSOC response to passive peer loops waiting for the timestamp in the ASSOC response to
be lit. Until then, the active peer dances the server steps, but light up. Until then, the active peer dances the server steps, but
skips the sign, cookie and leapseconds exchanges. skips the sign, cookie and leapseconds exchanges.
while (1) { while (1) {
wait_for_next_poll; wait_for_next_poll;
make_NTP_header; make_NTP_header;
if (!ENB) if (!ENB)
/* parameters exchange */ /* parameters exchange */
ASSOC_request; ASSOC_request;
else if (!VAL) else if (!VAL)
/* certificate exchange */ /* certificate exchange */
skipping to change at page 40, line 4 skipping to change at page 34, line 10
valid signature lights PRV. valid signature lights PRV.
Once the active peer has synchronized to a proventic source, it Once the active peer has synchronized to a proventic source, it
includes timestamped signatures with its messages. The first thing includes timestamped signatures with its messages. The first thing
it does after lighting timestamps is dance the sign exchange so that it does after lighting timestamps is dance the sign exchange so that
the passive peer can survive the default identity exchange, if the passive peer can survive the default identity exchange, if
necessary. This is pretty weird, since the passive peer will find necessary. This is pretty weird, since the passive peer will find
the active certificate signed by its own public key. the active certificate signed by its own public key.
The passive peer, which has been stalled waiting for the active The passive peer, which has been stalled waiting for the active
timestamps to be lit, now mates the dance. The initial value of the timestamps to light up, now mates the dance. The initial value of
cookie is zero. If a COOKIE response has not been received by either the cookie is zero. If a COOKIE response has not been received by
peer, the next message sent is a COOKIE request. The recipient rolls either peer, the next message sent is a COOKIE request. The
a random cookie, lights CKY and returns the encrypted cookie. The recipient rolls a random cookie, lights CKY and returns the encrypted
recipient decrypts the cookie and lights CKY. It is not a protocol cookie. The recipient decrypts the cookie and lights CKY. It is not
error if both peers happen to send a COOKIE request at the same time. a protocol error if both peers happen to send a COOKIE request at the
In this case both peers will have two values, one generated by itself same time. In this case both peers will have two values, one
and the other received from the other peer. In such cases the generated by itself and the other received from the other peer. In
working cookie is constructed as the EXOR of the two values. such cases the working cookie is constructed as the EXOR of the two
values.
At the next packet transmission opportunity, either peer generates a At the next packet transmission opportunity, either peer generates a
new key list and lights LST; however, there may already be an AUTO new key list and sets LST to 1; however, there may already be an AUTO
request queued for transmission and the rules say no more than one request queued for transmission and the rules say no more than one
request in a packet. When available, either peer sends an AUTO request in a packet. When available, either peer sends an AUTO
response and dims LST. The recipient initializes the autokey values response and dims LST. The recipient initializes the autokey values
and lights LST and AUT. Subsequent packets received without and lights LST and AUT. Subsequent packets received without
extension fields are validated by the autokey sequence. extension fields are validated by the autokey sequence.
The above description assumes the active peer synchronizes to the The above description assumes the active peer synchronizes to the
passive peer, which itself is synchronized to some other source, such passive peer, which itself is synchronized to some other source, such
as a radio clock or another NTP server. In this case, the active as a radio clock or another NTP server. In this case, the active
peer is operating at a stratum level one greater than the passive peer is operating at a stratum level one greater than the passive
peer and so the passive peer will not synchronize to it unless it peer and so the passive peer will not synchronize to it unless it
loses its own sources and the active peer itself has another source. loses its own sources and the active peer itself has another source.
Various other intricate scenarios are possible.
11. Error Recovery 11.6. 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 which can occur
due to such errors. Appendix B contains an extended discussion on due to such errors.
error checking and timestamp validation.
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, manycast or symmetric active packet with the arrival of a broadcast, manycast or symmetric active packet with
no matching association. If necessary, a general reset reinitializes no 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 which maintain the liveness
state of the protocol, the 8-bit reachability register defined in [8] state of the protocol, the 8-bit reachability register defined in [7]
and the watchdog timer, which is new in NTPv4. At every poll and the watchdog timer, which is new in NTPv4. At every poll
interval the reachability register is shifted left, the low order bit interval the reachability register is shifted left, the low order bit
is dimmed and the high order bit is lost. At the same time the is dimmed and the high order bit is lost. At the same time the
watchdog counter is incremented by one. If an arriving packet passes watchdog counter is incremented by one. If an arriving packet passes
all authentication and sanity checks, the rightmost bit of the all authentication and sanity checks, the rightmost bit of the
reachability register is lit and the watchdog counter is set to zero. reachability register is lit and the watchdog counter is set to zero.
If any bit in the reachability register is lit, the server is If any bit in the reachability register is lit, the server is
reachable, otherwise it is unreachable. reachable, otherwise it is unreachable.
When the first poll is sent from an association, the reachability When the first poll is sent from an association, the reachability
register and watchdog counter are zero. If the watchdog counter register and watchdog counter are zero. If the watchdog counter
reaches a preset threshold before the server becomes reachable, a reaches 16 before the server becomes reachable, a general reset
general reset occurs. This resets the protocol and clears any occurs. This resets the protocol and clears any acquired resources
acquired resources before trying again. If the association is before trying again. If the server was once reachable and then
ephemerable, it is demobilized; otherwise, the poll interval is becomes unreachable, a general reset occurs. In addition, if the
doubled. This reduces the network load for packets that are unlikely watchdog counter reaches 16 and the association is persistent, the
to elicit a response. poll interval is doubled. This reduces the network load for packets
that are unlikely to elicit a response.
At each state in the protocol the client expects a particular 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.
Since the client cookie is invalidated, the server rejects the next Since the client cookie is invalidated, the server rejects the next
client request and returns a crypto-NAK packet. A cryoti-NAK packet client request and returns a crypto-NAK packet. Since the crypto-NAK
has a runt MAC with a key ID of zero and no message digest. The has no MAC, the problem for the client is to determine whether it is
problem for the host is to determine whether it is legitimate or the legitimate or the result of intruder mischief. In order to reduce
result of intruder mischief. This is done using the NTPv4 on-wire the vulnerability in such cases, the crypto-NAK, as well as all
protocol, which requites the crypto-NAK, as well as all responses, to responses, is believed only if the result of a previous packet sent
be believed only if the result of a previous packet sent by the host by the client and not a replay, as confirmed by the NTP on-wire
and not a replay, as confirmed by the LBK and DUP status bits protocol. While this defense can be easily circumvented by a
described above. While this defense can be easily circumvented by a
middleman, it does deflect other kinds of intruder warfare. middleman, 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. 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.
skipping to change at page 42, line 16 skipping to change at page 36, line 18
There is no further need for the key list, since the client will There is no further need for the key list, since the client will
not transmit again. not transmit again.
3. When the poll interval is changed. In this case the calculated 3. 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.
4. If a problem is detected when an entry is fetched from the key 4. If a problem is detected when an entry is fetched from the key
list. This could happen if the key was marked non-trusted or 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 11.7. Security Considerations
This section discusses the most obvious security vulnerabilities in This section discusses the most obvious security vulnerabilities in
the various Autokey dances. First, some observations on the the various Autokey dances. In the following discussion the
particular engineering parameters of the Autokey protocol are in cryptographic algorithms and private values themselves are assumed
order. The number of bits in some cryptographic values are secure; that is, a brute force cryptanalytic attack will not reveal
considerably smaller than would ordinarily be expected for strong the host private key, sign private key, cookie value, identity
cryptography. One of the reasons for this is the need for parameters, server seed or autokey seed. In addition, an intruder
compatibility with previous NTP versions; another is the need for will not be able to predict random generator values.
small and constant latencies and minimal processing requirements.
Therefore, what the scheme gives up on the strength of these values
must be regained by agility in the rate of change of the
cryptographic basis values. Thus, autokeys are used only once and
seed values are regenerated frequently. However, in most cases even
a successful cryptanalysis of these values compromises only a
particular association and does not represent a danger to the general
population.
Throughout the following discussion the cryptographic algorithms and
private values themselves are assumed secure; that is, a brute force
cryptanalytic attack will not reveal the host private key, sign
private key, cookie value, identity parameters, server seed or
autokey seed. In addition, an intruder will not be able to predict
random generator values or predict the next autokey. On the other
hand, the intruder can remember the totality of all past values for
all packets ever sent. Ordinarily, the timestamp/filestamp
provisions will make such possesions unusable.
12.1. Protocol Vulnerability 11.8. 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. The protocol cannot loop forever preliminary assertions can be made. In the client/server and
in any state, since the watchdog counter and general reset insure symmetric dances the underlying NTP on-wire protocol is resistant to
that the association variables will eventually be purged and the lost, duplicate and bogus packets, even if the clock is not
protocol restarted from the beginning. However, if something is synchronized, so the protocol is not vulnerable to a wiretapper
seriously wrong, the timeout/restart cycle could continue attack. A middleman attack, even if it could simulate a valid
indefinitely until whatever is wrong is fixed. This is not a cookie, could not present a valid signature.
clogging hazard, as the timeout period is very long compared to
expected network delays.
The LBK and DUP bits described in the main body and Appendix B are
effective whether or not cryptographic means are in use. The DUP bit
deflects duplicate packets in any mode, while the LBK bit deflects
bogus packets in all except broadcast mode. All packets must have
the correct MAC, as verified with correct key ID and cookie. In all
modes the next key ID cannot be predicted by a wiretapper, so are of
no use for cryptanalysis.
As long as the client has validated the server certificate trail, a
wiretapper cannot produce a convincing signature and cannot produce
cryptographic values acceptable to the client. As long as the
identity values are not compromised, a middleman cannot masquerade as
a legitimate group member and produce convincing certificates or
signatures. In server and symmetric modes after the preliminary
exchanges have concluded, extension fields are no longer used, a
client validates the packet using the autokey sequence. A wiretapper
cannot predict the next Key IDs, so cannot produce a valid MAC. A
middleman cannot successfully modify and replay a message, since he
does not know the cookie and without the cookie cannot produce a
valid MAC.
In broadcast mode a wiretapper cannot produce a key list with signed
autokey values that a client will accept. The most it can do is
replay an old packet causing clients to repeat the autokey hash
operations until exceeding the maximum key number. However, a
middleman could intercept an otherwise valid broadcast packet and
produce a bogus packet with acceptable MAC, since in this case it
knows the key ID before the clients do. Of course, the middleman key
list would eventually be used up and clients would discover the ruse
when verifying the signature of the autokey values. There does not
seem to be a suitable defense against this attack.
During the exchanges where extension fields are in use, the cookie is In the broadcast dance the client begins with a volley in client/
a public value rather than a shared secret and an intruder can easily server mode to obtain the autokey values and signature, so has the
construct a packet with a valid MAC, but not a valid signature. In same protection as in that mode. When continuing in receive-only
the certificate and identity exchanges an intruder can generate fake mode, a wiretapper cannot produce a key list with valid signed
request messages which may evade server detection; however, the LBK autokey values. The most it can do is replay an old packet causing
and DUP bits minimize the client exposure to the resulting rogue clients to repeat the autokey hash operations until exceeding the
responses. A wiretapper might be able to intercept a request, maximum key number.
manufacture a fake response and loft it swiftly to the client before
the real server response. A middleman could do this without even
being swift. However, once the identity exchange has completed and
the PRV bit lit, these attacks are readily deflected.
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.
There is a significant vulnerability in the underlying NTP on-wire 11.9. Clogging Vulnerability
protocol. Until confirming the first exchange when a host first
comes up, an intruder can replay an old message, which cause the LBK
and DUP bits to be reset. If the intruder does this repeatedly, the
host may never synchronize. This vulnerability is the same as with
TCP.
12.2. Clogging Vulnerability A self-induced clogging incident cannot happen, since signatures are
computed only when the data have changed and the data do not change
very often. For instance, the autokey values are signed only when
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
a dance or the server seed is refreshed, which happens about once per
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 cookie or signature encryptions or victim server with needless cryptographic calculations, and a
identity calculations, and a decryption attack where the intruder decryption attack where the intruder attempts to clog the victim
attempts to clog the victim client with needless cookie or client with needless cryptographic calculations. Autokey uses public
verification decryptions. Autokey uses public key cryptography and key cryptography and the algorithms that perform these functions
the algorithms that perform these functions consume significant consume significant resources.
processor resources.
In order to reduce exposure to decryption attacks the LBK and DUP
bits deflect bogus and replayed packets before invoking any
cryptographic operations. In order to reduce exposure to encryption
attacks, signatures are computed only when the data have changed.
For instance, the autokey values are signed only when the key list is
regenerated, which happens about once an hour, while the public
values are signed only when one of them changes or the server seed is
refreshed, which happens about once per day.
In some Autokey dances the protocol precludes server state variables
on behalf of an individual client, so a request message must be
processed and the response message sent without delay. The identity,
cookie and sign exchanges are particularly vulnerable to a clogging
attack, since these exchanges can involve expensive cryptographic
algorithms as well as digital signatures. A determined intruder
could replay identity, cookie or sign requests at high rate, which
may very well be a useful munition for an encryption attack.
Ordinarily, these requests are seldom used, except when the protocol
is restarted or the server seed or public values are refreshed.
Once synchronized to a proventic source, a legitimate extension field In client/server and peer dances an encryption hazard exists when a
with timestamp the same as or earlier than the most recent received wiretapper replays prior cookie request messages at speed. There is
of that type is immediately discarded. This foils a middleman cut- no obvious way to deflect such attacks, as the server retains no
and-paste attack using an earlier AUTO response, for example. A state between requests. Replays of cookie response messages are
legitimate extension field with timestamp in the future is unlikely, detected and discarded by the NTP on-wire protocol.
as that would require predicting the autokey sequence. In either
case the extension field is discarded before expensive signature
computations. This defense is most useful in symmetric mode, but a
useful redundancy in other modes.
The client is vulnerable to a certificate clogging attack until In broadcast mode a client a decription hazard exists when a
declared proventic, after which CERT responses are discarded. Before wiretapper replays autokey response messages at speed. Once
that, a determined intruder could flood the client with bogus synchronized to a proventic source, a legitimate extension field with
certificate responses and force spurious signature verifications, timestamp the same as or earlier than the most recently received of
which of course would fail. The intruder could flood the server with that type is immediately discarded. This foils a middleman cut-and-
bogus certificate requests and cause similar mischief. Once declared paste attack using an earlier response, for example. A legitimate
proventic, further certificate responses are discard, so these extension field with timestamp in the future is unlikely, as that
attacks would fail. The intruder could flood the server with would require predicting the autokey sequence. In either case the
replayed sign requests and cause the server to verify the request and extension field is discarded before expensive signature computations.
sign the response, although the client would drop the response due This defense is most useful in symmetric mode, but a useful
invalid timestamp. redundancy in other modes.
An interesting adventure is when an intruder replays a recent packet An interesting adventure is when an intruder replays a recent packet
with an intentional bit error. A stateless server will return a with an intentional bit error. A stateless server will return a
crypto-NAK message which the client will notice and discard, since crypto-NAK message which will be discarded by the NTP on-wire
the LBK bit is lit. However, a legitimate crypto-NAK is sent if the protocol. However, a legitimate crypto-NAK is sent if the server has
server has just refreshed the server seed. In this case the LBK bit just refreshed the server seed. In this case the the client performs
is dim and the client performs a general reset and restarts the a general reset and restarts the protocol as expected.
protocol as expected. Another adventure is to replay broadcast mode
packets at high rate. These will be rejected by the clients by the
timestamp check and before consuming signature cycles.
In broadcast and symmetric modes the client must include the
association ID in the AUTO request. Since association ID values for
different invocations of the NTP daemon are randomized over the 16-
bit space, it is unlikely that a bogus request would match a valid
association with different IP addresses, for example, and cause
confusion.
13. IANA Considerations 12. IANA Considerations
Any IANA registries needed? Any IANA registries needed?
14. Acknowledgements 13. Acknowledgements
... ...
15. References 14. References
15.1. Normative References 14.1. Normative References
[1] Burbank, J., "Network Time Protocol Version 4 Protocol And [1] Burbank, J., "Network Time Protocol Version 4 Protocol And
Algorithms Specification", draft-ietf-ntp-ntpv4-proto-07 (work Algorithms Specification", draft-ietf-ntp-ntpv4-proto-08 (work
in progress), July 2007. in progress), November 2007.
15.2. Informative References 14.2. Informative References
[2] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol", [2] Maughan, D., Schneider, M., and M. Schertler, "Internet
RFC 4306, December 2005. Security Association and Key Management Protocol (ISAKMP)",
RFC 2408, November 1998.
[3] Orman, H., "The OAKLEY Key Determination Protocol", RFC 2412, [3] Orman, H., "The OAKLEY Key Determination Protocol", RFC 2412,
November 1998. November 1998.
[4] Karn, P. and W. Simpson, "Photuris: Session-Key Management [4] Karn, P. and W. Simpson, "Photuris: Session-Key Management
Protocol", RFC 2522, March 1999. Protocol", RFC 2522, March 1999.
[5] Bradner, S., "Key words for use in RFCs to Indicate Requirement [5] Kent, S. and R. Atkinson, "IP Encapsulating Security Payload
Levels", BCP 14, RFC 2119, March 1997. (ESP)", RFC 2406, November 1998.
[6] Kent, S., "IP Encapsulating Security Payload (ESP)", RFC 4303,
December 2005.
[7] Kent, S., "IP Authentication Header", RFC 4302, December 2005. [6] Kent, S. and R. Atkinson, "IP Authentication Header", RFC 2402,
November 1998.
[8] Mills, D., "Network Time Protocol (Version 3) Specification, [7] Mills, D., "Network Time Protocol (Version 3) Specification,
Implementation", RFC 1305, March 1992. Implementation", RFC 1305, March 1992.
[9] Prafullchandra, H. and J. Schaad, "Diffie-Hellman Proof-of- [8] Prafullchandra, H. and J. Schaad, "Diffie-Hellman Proof-of-
Possession Algorithms", RFC 2875, July 2000. Possession Algorithms", RFC 2875, July 2000.
[10] Adams, C., Farrell, S., Kause, T., and T. Mononen, "Internet [9] Adams, C. and S. Farrell, "Internet X.509 Public Key
X.509 Public Key Infrastructure Certificate Management Protocol Infrastructure Certificate Management Protocols", RFC 2510,
(CMP)", RFC 4210, September 2005. March 1999.
[11] Housley, R., Polk, W., Ford, W., and D. Solo, "Internet X.509 [10] Housley, R., Polk, W., Ford, W., and D. Solo, "Internet X.509
Public Key Infrastructure Certificate and Certificate Public Key Infrastructure Certificate and Certificate
Revocation List (CRL) Profile", RFC 3280, April 2002. Revocation List (CRL) Profile", RFC 3280, April 2002.
[12] Schnorr, C., "Efficient signature generation for smart cards", [11] Schnorr, C., "Efficient signature generation for smart cards",
1991. 1991.
[13] Stinson, D., "Cryptography - Theory and Practice", 1995. [12] Stinson, D., "Cryptography - Theory and Practice", 1995.
[14] Guillou, L. and J. Quisquatar, "A "paradoxical" identity-based [13] Guillou, L. and J. Quisquatar, "A "paradoxical" identity-based
signature scheme resulting from zero-knowledge", 1990. signature scheme resulting from zero-knowledge", 1990.
[15] Mu, Y. and V. Varadharajan, "Robust and secure broadcasting", [14] Mu, Y. and V. Varadharajan, "Robust and secure broadcasting",
2001. 2001.
[15] Mills, D., ""Compouter Network Time Synchronization - the
Network Time Protocol"", 2006.
[16] Bassham, L., Polk, W., and R. Housley, "Algorithms and [16] Bassham, L., Polk, W., and R. Housley, "Algorithms and
Identifiers for the Internet X.509 Public Key Infrastructure Identifiers for the Internet X.509 Public Key Infrastructure
Certificate and Certificate Revocation List (CRL) Profile", Certificate and Certificate Revocation List (CRL) Profile",
RFC 3279, April 2002. RFC 3279, April 2002.
Appendix A. Cryptographic Key and Certificate Management Appendix A. Timestamps, Filestamps and Partial Ordering
This appendix describes how cryptographic keys and certificates are
generated and managed in the NTPv4 reference implementation. These
means are not intended to become part of any standard that may be
evolved from this report, but to serve as an example of how these
functions can be implemented and managed in a typical operational
environment.
The ntp-keygen utility program in the NTPv4 software library
generates public/private key files, certificate files and identity
key/parameter files. By default the modulus of all encryption and
identity keys is 512 bits. All random cryptographic data are based
on a pseudo-random number generator seeded in such a way that random
values are exceedingly unlikely to repeat. The files are in ASN.1
format, encrypted is necessary, then PEM encoded in printable ASCII
format suitable for mailing as MIME objects.
Every file has a filestamp, which is a string of decimal digits
representing the NTP seconds when the file was created. The file
name is formed from the concatenation of the host name, filestamp and
constant strings, so files can be copied from one environment to
another while preserving the original filestamp. The file header
includes the file name and date and generation time in printable
ASCII. The utility assumes the host is synchronized to a proventic
source at the time of generation, so that filestamps are proventic
data. This raises an interesting circularity issue that will not be
further explored here.
The generated files are typically stored in NFS mounted file systems,
with files containing private keys obscured to all but root.
Symbolic links are installed from default file names assumed by the
NTP daemon to the selected files. Since the files of successive
generations and different hosts have unique names, there is no
possibility of name collisions.
Public/private host and sign keys and certificates must be generated
by the host to which they belong. The host key must be RSA, since it
is used to encrypt the cookie, as well as encrypt signatures by
default. The optional sign key can be RSA or DSA, since it is used
only to encrypt signatures. In principle, certificates could be
generated directly by OpenSSL utility programs, as long as the
symbolic links are consistent.
Identity keys and parameters must be generated by the ntp-keygen
utility, since they have proprietary formats. Since these are
private to the group, they are generated by one host acting as a
trusted authority and then distributed to all other members of the
group by secure means.
Certificates are usually, but not necessarily, generated by the host
to which they belong. The ntp-keygen utility generates self-signed
X.509v3 host certificate files with optional extension fields.
Certificate requests are not used, since the certificate itself is
used as a request to be signed. OpenSSL X.509v3 certificates are
generated as an OpenSSL structure, which is then PEM encoded in ASN.1
syntax and written to the host certificate file. The string returned
by the Unix gethostname() routine is used by default for both the
subject and issuer fields. The serial number and begin time fields
are derived from the filestamp; the end time is one year hence. The
host certificate is signed by the sign key or host key if a sign key
is not present.
An important design goal is to make cryptographic data refreshment as
simple and intuitive as possible, so it can be driven by scripts on a
periodic basis. When the ntp-keygen utility is run for the first
time, it creates by default a RSA host key file and RSA-MD5 host
certificate file and necessary symbolic links. After that, it
creates a new certificate file and symbolic link using the existing
host key. The program run with given options creates identity key/
parameter files for one or more IFF, GQ or MV identity schemes. The
key files must then be securely copied to all other group members and
symbolic links installed from the default names to the installed
files. In the GQ scheme the next and each subsequent time the ntp-
keygen utility runs, it automatically creates or updates the private/
public identity key files and certificate file using the existing
identity parameters.
Appendix B. Autokey Error Checking
Exhaustive examination of possible vulnerabilities at the various
processing steps of the NTPv3 protocol as specified in [8] have
resulted in a revised list of packet sanity tests. There are 12
tests in the NTPv4 reference implementation, called TEST1 through
TEST12, which are performed in a specific order designed to gain
maximum diagnostic information while protecting against an accidental
or malicious clogging attacks. These tests are described in detail
in the NTP software documentation. Those relevant to the Autokey
protocol are described in this appendix.
The sanity tests are classified in four tiers. The first tier
deflects access control and message digest violations. The second,
represented by the autokey sequence, deflects spoofed or replayed
packets. The third, represented by timestamped digital signatures,
binds cryptographic values to verifiable credentials. The fourth
deflects packets with invalid NTP header fields or out of bounds time
values. However, the tests in this last group do not directly affect
cryptographic protocol vulnerability, so are beyond the scope of
discussion here.
B.1. Packet Processing Rules
Every arriving NTP packet is checked enthusiastically for format,
content and protocol errors. Some packet header fields are checked
by the main NTP code path both before and after the Autokey protocol
engine cranks. These include the NTP version number, overall packet
length and extension field lengths. The total length of all
extension fields may be no longer than 1024 octets in the reference
implementation. Packets failing any of these checks are discarded
immediately. Packets denied by the access control mechanism will be
discarded later, but processing continues temporarily in order to
gather further information useful for error recovery and reporting.
Next, the cookie and session key are determined and the MAC computed
as described above. If the MAC fails to match the value included in
the packet, the action depends on the mode and the type of packet.
Packets failing the MAC check will be discarded later, but processing
continues temporarily in order to gather further information useful
for error recovery and reporting.
The NTP transmit and receive timestamps are in effect nonces, since
an intruder cannot effectively guess either value in advance. To
minimize the possibility that an intruder can guess the nonces, the
low order unused bits in all timestamps are obscured with random
values. If the transmit timestamp matches the transmit timestamp in
the last packet received, the packet is a duplicate, so the DUP bit
is lit. If the packet mode is not broadcast and the last transmit
timestamp does not match the originate timestamp in the packet,
either it was delivered out of order or an intruder has injected a
rogue packet, so the LBK bit is lit. Packets with either the DUP or
LBK bit will be discarded later, but processing continues temporarily
in order to gather further information useful for error recovery and
reporting.
Further indicators of the server and client state are apparent from
the transmit and receive timestamps of both the packet and the
association. The quite intricate rules take into account these and
the above error indicators They are designed to discriminate between
legitimate cases where the server or client are in inconsistent
states and recoverable, and when an intruder is trying to destabilize
the protocol or force consumption of needless resources. The exact
behavior is beyond the scope of discussion, but is clearly described
in the source code documentation.
Next, the Autokey protocol engine is cranked and the dances evolve as
described above. Some requests and all responses have value fields
which carry timestamps and filestamps. When the server or client is
synchronized to a proventic source, most requests and responses with
value fields carry signatures with valid timestamps. When not
synchronized to a proventic source, value fields carry an invalid
(zero) timestamp and the signature field and signature length word
are omitted.
The extension field parser checks that the Autokey version number,
operation code and field length are valid. If the error bit is lit
in a request, the request is discarded without response; if an error
is discovered in processing the request, or if the responder is not
synchronized to a proventic source, the response contains only the
first two words of the request with the response and error bits lit.
For messages with signatures, the parser requires that timestamps and
filestamps are valid and not a replay, that the signature length
matches the certificate public key length and only then verifies the
signature. Errors are reported via the security logging facility.
All certificates must have correct ASN.1 encoding, supported digest/
signature scheme and valid subject, issuer, public key and, for self-
signed certificates, valid signature. While the begin and end times
can be checked relative to the filestamp and each other, whether the
certificate is valid relative to the actual time cannot be determined
until the client is synchronized to a proventic source and the
certificate is signed and verified by the server.
When the protocol starts the only response accepted is ASSOC with
valid timestamp, after which the server status word must be nonzero.
ASSOC responses are discarded if this word is nonzero. The only
responses accepted after that and until the PRV bit is lit are CERT,
IFF and GQ. Once identity is confirmed and IFF is lit, these
responses are no longer accepted, but all other responses are
accepted only if in response to a previously sent request and only in
the order prescribed in the protocol dances. Additional checks are
implemented for each request type and dance step.
B.2. Timestamps, Filestamps and Partial Ordering
When the host starts, it reads the host key and certificate files, When the host starts, it reads the host key and host certificate
which are required for continued operation. It also reads the sign files, which are required for continued operation. It also reads the
key and leapseconds file, when available. When reading these files sign key and leapseconds values, when available. When reading these
the host checks the file formats and filestamps for validity; for files the host checks the file formats and filestamps for validity;
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. In general, not be earlier than its associated sign key filestamp. At the time
at the time the files are read, the host is not synchronized, so it the files are read the host is not synchronized, so it cannot
cannot determine whether the filestamps are bogus other than these determine whether the filestamps are bogus other than these simple
simple checks. checks. It must not produce filestamps or timestamps until
sunchronized 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 insures a correct partial ordering for all
current time values. current time values.
skipping to change at page 52, line 13 skipping to change at page 40, line 37
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 can
not be used to verify signatures if t --> B or E --> t, where t not be used to verify signatures if t --> B or E --> t, where t
is the current proventic time. Note that the public key 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 clique of proventic truechimers. client has synchronized to a proventic source.
Appendix C. Certificates
Certificate extension fields are used to convey information used by
the identity schemes, such as whether the certificate is private,
trusted or contains a public identity key. While the semantics of
these fields generally conforms with conventional usage, there are
subtle variations. The fields used by Autokey Version 2 include:
o Basic Constraints. This field defines the basic functions of the
certificate. It contains the string "critical,CA:TRUE", which
means the field must be interpreted and the associated private key
can be used to sign other certificates. While included for
compatibility, Autokey makes no use of this field.
o Key Usage. This field defines the intended use of the public key
contained in the certificate. It contains the string
"digitalSignature,keyCertSign", which means the contained public
key can be used to verify signatures on data and other
certificates. While included for compatibility, Autokey makes no
use of this field.
o Extended Key Usage. This field further refines the intended use
of the public key contained in the certificate and is present only
in self-signed certificates. It contains the string "Private" if
the certificate is designated private or the string "trustRoot" if
it is designated trusted. A private certificate is always
trusted.
o Subject Key Identifier. This field contains the public identity
key used in the GQ identity scheme. It is present only if the GQ
scheme is configured.
Appendix D. Identity Schemes
The Internet infrastructure model described in [10] is based on
certificate trails where a subject proves identity to a certificate
authority (CA) who then signs the subject certificate using the CA
issuer key. The CA in turn proves identity to the next CA and
obtains its own signed certificate. The trail continues to a CA with
a self-signed trusted root certificate independently validated by
other means. If it is possible to prove identity at each step, each
certificate along the trail can be considered trusted relative to the
identity scheme and trusted root certificate.
The important issue with respect to NTP is the cryptographic strength Appendix B. Identity Schemes
of the identity scheme, since if a middleman could compromise it, the
trail would have a security breach. In electric mail and commerce
the identity scheme can be based on handwritten signatures,
photographs, fingerprints and other things very hard to counterfeit.
As applied to NTP subnets and identity proofs, the scheme must allow
a client to securely verify that a server knows the same secret that
it does, presuming the secret was previously instantiated by secure
means, but without revealing the secret to members outside the group.
While the identity scheme described in RFC-2875 [9] is based on a There are five identity schemes in the NTPv4 reference
ubiquitous Diffie-Hellman infrastructure, it is expensive to generate implementation: (1) private certificate (PC), (2) trusted certificate
and use when compared to others described in this appendix. There (TC), (3) a modified Schnorr algorithm (IFF - Identify Friend or
are five schemes now implemented in the NTPv4 reference Foe), (4) a modified Guillou-Quisquater algorithm (GQ), and (5) a
implementation to prove identity: (1) private certificate (PC), (2) modified Mu-Varadharajan algorithm (MV).
trusted certificate (TC), (3) a modified Schnorr algorithm (IFF aka
Identify Friendly or Foe), (4) a modified Guillou-Quisquater
algorithm (GQ), and (5) a modified Mu-Varadharajan algorithm (MV).
The available schemes are selected during the key generation phase,
with the particular scheme selected during the parameter exchange.
The IFF, GQ and MV schemes involve a cryptographically strong The PC scheme is intended for testing and development and not
challenge-response exchange where an intruder cannot learn the group recommended for general use. The TC scheme uses a certificate trail,
key, even after repeated observations of multiple exchanges. These but not an identity scheme. The IFF, GQ and MV identity schemes use
schemes begin when the client sends a nonce to the server, which then a cryptographically strong challenge-response exchange where an
rolls its own nonce, performs a mathematical operation and sends the intruder cannot learn the group key, even after repeated observations
results along with a message digest to the client. The client of multiple exchanges. These schemes begin when the client sends a
performs a second mathematical operation to produce a digest that nonce to the server, which then rolls its own nonce, performs a
must match the one included in the message. To the extent that a mathematical operation and sends the results to the client. The
server can prove identity to a client without either knowing the client performs a second mathematical operation to prove the server
group key, a scheme is properly described as a zero-knowledge proof. has the same group key as the client.
D.1. Private Certificate (PC) Scheme B.1. Private Certificate (PC) Scheme
The PC scheme shown in Figure Figure 13 involves the use of a private The PC scheme shown in Figure Figure 12 uses a private certificate as
certificate as group key. A certificate is designated private by a the group key.
X509 Version 3 extension field when generated by utility routines in
the NTP software distribution. The certificate is distributed to all
other group members by secure means and is never revealed outside the
group. A client is marked trusted in the Parameter Exchange and
authentic when the first signature is verified. This scheme is
cryptographically strong as long as the private certificate is
protected; however, it can be very awkward to refresh the keys or
certificate, since new values must be securely distributed to a
possibly large population and activated simultaneously.
Trusted Trusted
Authority Authority
Secure +-------------+ Secure Secure +-------------+ Secure
+--------------| Certificate |-------------+ +--------------| Certificate |-------------+
| +-------------+ | | +-------------+ |
| | | |
\|/ \|/ \|/ \|/
+-------------+ +-------------+ +-------------+ +-------------+
| Certificate | | Certificate | | Certificate | | Certificate |
+-------------+ +-------------+ +-------------+ +-------------+
Server Client Server Client
Figure 13: Private Certificate (PC) Identity Scheme Figure 12: Private Certificate (PC) Identity Scheme
The PC scheme uses a private certificate as group key. A certificate A certificate is designated private when the X509v3 Extended Key
is designated private for the purpose of the this scheme if the CIS Usage extension field is present and contains "Private". The private
Private bit is lit. The certificate is distributed to all other certificate is distributed to all other group members by secret
group members by secret means and never revealed outside the group. means, so in fact becomes a symmetric key. Private certificates are
There is no identity exchange, since the certificate itself is the also trusted, so there is no need for a certificate trail or identity
group key. Therefore, when the parameter exchange completes the VAL, scheme.
IFF and SGN bits are lit in the server status word. When the
following cookie exchange is complete, the PRV bit is lit and
operation continues as described in the main body of this report.
D.2. Trusted Certificate (TC) Scheme B.2. 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 Figure 14. As described in RFC-4210 [10], each certificate in Figure Figure 13.
is signed by an issuer one step closer to the trusted host, which has
a self-signed trusted certificate, A certificate is designated
trusted by a X509 Version 3 extension field when generated by utility
routines in the NTP software distribution. A host obtains the
certificates of all other hosts along the trail leading to a trusted
host by the Autokey protocol, then requests the immediately ascendant
host to sign its certificate. Subsequently, these certificates are
provided to descendent hosts by the Autokey protocol. In this scheme
keys and certificates can be refreshed at any time, but a masquerade
vulnerability remains unless a request to sign a client certificate
is validated by some means such as reverse-DNS. If no specific
identity scheme is specified in the Identification Exchange, this is
the default TC scheme.
Trusted Trusted
Host Host Host Host Host Host
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+
+--->| Subject | +--->| Subject | +--->| Subject | +--->| Subject | +--->| Subject | +--->| Subject |
| +-----------+ | +-----------+ | +-----------+ | +-----------+ | +-----------+ | +-----------+
...---+ | Issuer |---+ | Issuer |---+ | Issuer | ...---+ | Issuer |---+ | Issuer |---+ | Issuer |
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+
| Signature | | Signature | | Signature | | Signature | | Signature | | Signature |
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+
Figure 14: Private Certificate (PC) Identity Scheme Figure 13: Trusted Certificate (TC) Identity Scheme
The TC identification exchange follows the parameter exchange in
which the VAL bit is lit. It involves a conventional certificate
trail and a sequence of certificates, each signed by an issuer one
stratum level lower than the client, and terminating at a trusted
certificate, as described in [10]. A certificate is designated
trusted for the purpose of the TC scheme if the CIS Trust bit is lit
and the certificate is self-signed. Such would normally be the case
when the trail ends at a primary (stratum 1) server, but the trail
can end at a secondary server if the security model permits this.
When a certificate is obtained from a server, or when a certificate
is signed by a server, A CIS for the new certificate is pushed on the
certificate list, but only if the certificate filestamp is greater
than any with the same subject name and issuer name already on the
list. The list is then scanned looking for signature opportunities.
If a CIS issuer name matches the subject name of another CIS and the
issuer certificate is verified using the public key of the subject
certificate, the CIS Sign bit is lit in the issuer CIS. Furthermore,
if the Trust bit is lit in the subject CIS, the Trust bit is lit in
the issuer CIS.
The client continues to follow the certificate trail to a self-signed
certificate, lighting the Sign and Trust bits as it proceeds. If it
finds a self-signed certificate with Trust bit lit, the client lights
the IFF and PRV bits and the exchange completes. It can, however,
happen that the client finds a self-signed certificate with Trust bit
dark. This can happen when a server is just coming up, has
synchronized to a proventic source, but has not yet completed the
Sign exchange. This is considered a temporary condition, so the
client simply retries at poll opportunities until the server
certificate is signed.
D.3. Schnorr (IFF) Scheme
The Schnorr (IFF) identity scheme is useful when certificates are As described in RFC-2510 [9], each certificate is signed by an issuer
generated by means other than the NTP software library, such as a one step closer to the trusted host, which has a self-signed trusted
trusted public authority. In this case a X.509v3 extension field certificate. A certificate is designated trusted when an X509v3
might not be available to convey the identity public key. The scheme Extended Key Usage extension field is present and contains
involves a set of parameters which persist for the life of the "trustRoot". If no identity scheme is specified in the parameter
scheme. New generations of these parameters must be securely exchange, this is the default scheme.
transmitted to all members of the group before use. The scheme is
self contained and independent of new generations of host keys, sign
keys and certificates.
Certificates can be generated by the OpenSSL library or an external B.3. Schnorr (IFF) Identity Scheme
public certificate authority, but conveying an arbitrary public value
in a certificate extension field might not be possible. The TA
generates IFF parameters and keys and distributes them by secure
means to all servers, then removes the group key and redistributes
these data to dependent clients. Without the group key a client
cannot masquerade as a legitimate server.
The IFF parameters are generated by OpenSSL routines normally used to The IFF scheme is useful when the group key is concealed, so that
generate DSA keys. By happy coincidence, the mathematical principles client keys need not be protected. The primary disacvantage is that
on which IFF is based are similar to DSA, but only the moduli p, q when the server key is refreshed all hosts must update the client
and generator g are used in identity calculations. The parameters key. The scheme shown in Figure Figure 14 involves a set of public
hide in a DSA cuckoo structure and use the same members. The values parameters and a group key including both private and public
are used by an identity scheme based on DSA cryptography and components. The public component is the client key.
described in [12] and [13] p. 285. The p is a 512-bit prime, g a
generator of the multiplicative group Zp* and q a 160-bit prime that
divides (p-1) and is a qth root of 1 mod p; that is, g^q mod p. The
TA 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 servers using secure means and (p, q, g, v) to all clients not
necessarily using secure means.
Trusted Trusted
Authority Authority
+------------+ +------------+
| Parameters | | Parameters |
Secure +------------+ Insecure Secure +------------+ Insecure
+-------------| Group Key |-----------+ +-------------| Group Key |-----------+
| +------------+ | | +------------+ |
| | Client Key | |
| +------------+ |
\|/ \|/ \|/ \|/
+------------+ Challenge +------------+ +------------+ Challenge +------------+
| Parameters |<------------------------| Parameters | | Parameters |<------------------------| Parameters |
+------------+ +------------+ +------------+ +------------+
| Group Key |------------------------>| Client Key | | Group Key |------------------------>| Client Key |
+------------+ Response +------------+ +------------+ Response +------------+
Server Client Server Client
Figure 15: Schnorr (IFF) Identity Scheme Figure 14: Schnorr (IFF) Identity Scheme
By happy coincidence, the mathematical principles on which IFF is
based are similar to DSA. The scheme is a modification an algorithm
described in [11] and [12] p. 285. The parameters are 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 of the
multiplicative group Z_p* and q a 160-bit prime that divides (p-1)
and is a qth root of 1 mod p; that is, g^q = 1 mod p. The TA rolls 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
servers using secure means and (p, q, g, v) to all clients not
necessarily using secure means.
The IFF identity scheme is shown in Figure Figure 15. The TA The TA hides IFF parameters and keys in an OpenSSL DSA cuckoo
generates a DSA parameter structure for use as IFF parameters. The structure. The IFF parameters are identical to the DSA parameters,
IFF parameters are identical to the DSA parameters, so the OpenSSL so the OpenSSL library can be used directly. The structure shown in
library DSA parameter generation routine can be used directly. The FigureFigure 15 is written to a file as a DSA private key encoded in
DSA parameter structure shown in Table Figure 16 is written to a file PEM. Unused structure members are set to one.
as a DSA private key encoded in PEM. 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 |
+---------+----------+-------------+-------------+ +---------+----------+-------------+-------------+
| b | priv_key | group key | server | | b | priv_key | group key | server |
+---------+----------+-------------+-------------+ +---------+----------+-------------+-------------+
| v | pub_key | client keys | client | | v | pub_key | client key | client |
+---------+----------+-------------+-------------+ +---------+----------+-------------+-------------+
Figure 16: IFF Identity Scheme Parameters Figure 15: IFF Identity Scheme Structure
Alice challenges Bob to confirm identity using the following protocol Alice challenges Bob to confirm identity using the following protocol
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), computes y = k + br mod q and x = 2. Bob rolls random k (0 < k < q), computes y = k + br mod q and x =
g^k mod p, then sends (y, hash(x)) to Alice. g^k mod p, then sends (y, hash(x)) to Alice.
3. Alice computes z = g^y * v^r mod p and verifies hash(z) = 3. Alice computes z = g^y * v^r mod p and verifies hash(z) equals
hash(x). hash(x).
If the hashes match, Alice knows that Bob has the group key b. If the hashes match, Alice knows that Bob has the group key b.
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. On success the IFF and PRV bits are lit in the server certificate.
status word.
D.4. Guillard-Quisquater (GQ)
The Guillou-Quisquater (GQ) identity scheme is useful when B.4. Guillard-Quisquater (GQ) Identity Scheme
certificates are generated using the NTP software library. These
routines convey the GQ public key in a X.509v3 extension field. The
scheme involves a set of parameters which persist for the life of the
scheme and a private/public identity key, which is refreshed each
time a new certificate is generated. The utility inserts the client
key in an X.509 extension field when the certificate is generated.
The client key is used when computing the response to a challenge.
The TA generates the GQ parameters and keys and distributes them by
secure means to all group members. The scheme is self contained and
independent of new generations of host keys and sign keys and
certificates.
The GQ parameters are generated by OpenSSL routines normally used to The GQ scheme is useful when the server key must be refreshed from
generate RSA keys. By happy coincidence, the mathematical principles time to time without changing the group key. The NTP utility
on which GQ is based are similar to RSA, but only the modulus n is programs include the GQ client key in the X509v3 Subject Key
used in identity calculations. The parameters hide in a RSA cuckoo Identifier extension field. The primary disadvantage of the scheme
structure and use the same members. The values are used in an is that the group key must be protected in both the server and
identity scheme based on RSA cryptography and described in [14] and client. A secondary disadvantage is that when a server key is
[13] p. 300 (with errors). The 512-bit public modulus n=pq, where p refreshed, old extension fields no longer work. The scheme is shown
and q are secret large primes. The TA rolls random group key b (0 < in Figure Figure 16a involves a set of public parameters and group
b < n) and distributes (n, b) to all group members using secure key used to generate private server keys and client keys.
means. The private server key and public client key are constructed
later.
Trusted Trusted
Authority Authority
+------------+ +------------+
| Parameters | | Parameters |
Secure +------------+ Secure Secure +------------+ Secure
+-------------| Group Key |-----------+ +-------------| Group Key |-----------+
| +------------+ | | +------------+ |
\|/ \|/ \|/ \|/
+------------+ Challenge +------------+ +------------+ Challenge +------------+
| Parameters |<------------------------| Parameters | | Parameters |<------------------------| Parameters |
+------------+ +------------+ +------------+ +------------+
| Group Key | | Group Key | | Group Key | | Group Key |
+------------+ Response +------------+ +------------+ Response +------------+
| Server Key |------------------------>| Client Key | | Server Key |------------------------>| Client Key |
+------------+ +------------+ +------------+ +------------+
Server Client Server Client
Figure 17: Schnorr (IFF) Identity Scheme Figure 16: Schnorr (IFF) Identity Scheme
The GQ identity scheme is shown in Figure Figure 17. When generating By happy coincidence, the mathematical principles on which GQ is
new certificates, the server rolls new random private server key u (0 based are similar to RSA. The scheme is a modification of an
< u < n) and public client key its inverse obscured by the group key algorithm described in [13] and [12] p. 300 (with errors). The
v = (u^-1)^b mod n. These values replace the private and public keys parameters are generated by routines in the OpenSSL library, but only
normally generated by the RSA scheme. In addition, the public client the moduli p and q are used. The 512-bit public modulus is n=pq,
key is conveyed in a X.509 certificate extension. The updated GQ where p and q are secret large primes. The TA rolls random large
structure shown in Figure Figure 18 is written as an RSA private key prime b (0 < b < n) and distributes (n, b) to all group servers and
encoded in PEM. Unused structure members are set to one. clients using secure means, since an intruder in possesion of these
values could impersonate a legitimate server. The private server key
and public client key are constructed later.
The TA hides GQ parameters and keys in an OpenSSL RSA cuckoo
structure. The GQ parameters are identical to the RSA parameters, so
the OpenSSL library can be used directly. When generating a
certificate, the 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.
These values replace the private and public keys normally generated
by the RSA scheme. The client key is conveyed in a X.509 certificate
extension. The updated GQ structure shown in Figure Figure 17 is
written as an RSA private key encoded in PEM. Unused structure
members are set to one.
+---------------------------------+-------------+ +---------------------------------+-------------+
| GQ | RSA | Item | Include | | GQ | RSA | Item | Include |
+=========+==========+============+=============+ +=========+==========+============+=============+
| n | n | modulus | all | | n | n | modulus | all |
+---------+----------+------------+-------------+ +---------+----------+------------+-------------+
| b | e | group key | server | | b | e | group key | all |
+---------+----------+------------+-------------+ +---------+----------+------------+-------------+
| u | p | server key | server | | u | p | server key | server |
+---------+----------+------------+-------------+ +---------+----------+------------+-------------+
| v | q | client key | client | | v | q | client key | client |
+---------+----------+------------+-------------+ +---------+----------+------------+-------------+
Figure 18: IFF Identity Scheme Parameters Figure 17: GQ Identity Scheme Structure
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 < n) and sends to Bob. 1. Alice rolls random r (0 < r < n) and sends to Bob.
2. Bob rolls random k (0 < k < n) and computes y = ku^r mod n and x 2. Bob rolls random k (0 < k < n) and computes y = ku^r mod n and x
= k^b mod n, then sends (y, hash(x)) to Alice. = k^b mod n, then sends (y, hash(x)) to Alice.
3. Alice computes z = (v^r)*(y^b) mod n and verifies hash(z) = 3. Alice computes z = (v^r)*(y^b) mod n and verifies hash(z) equals
hash(x). hash(x).
If the hashes match, Alice knows that Bob has the group key b. If the hashes match, Alice knows that Bob has the corresponding
Besides making the response shorter, the hash makes it effectively server key u. Besides making the response shorter, the hash makes it
impossible for an intruder to solve for b by observing a number of effectively impossible for an intruder to solve for u by observing a
these messages. The signed response binds this knowledge to Bob's number of these messages. The signed response binds this knowledge
private key and the public key previously received in his to Bob's private key and the client key previously received in his
certificate. Further evidence is the certificate containing the certificate.
public identity key, since this is also signed with Bob's private
key. On success the IFF and PRV bits are lit in the server status
word.
D.5. Mu-Varadharajan (MV) Identity Scheme
The Mu-Varadharajan (MV) scheme was originally intended to encrypt B.5. Mu-Varadharajan (MV) Identity Scheme
broadcast transmissions to receivers which do not transmit. There is
one encryption key for the broadcaster and a separate decryption key
for each receiver. It operates something like a pay-per-view
satellite broadcasting system where the session key is encrypted by
the broadcaster and the decryption keys are held in a tamper proof
set-top box. We don't use it this way, but read on.
The MV scheme is perhaps the most interesting and flexible of the The MV scheme is perhaps the most interesting and flexible of the
three challenge/response schemes. It can be used when a small number three challenge/response schemes, but is devilishly complicated. It
of servers provide synchronization to a large client population where is most useful when a small number of servers provide synchronization
there might be considerable risk of compromise between and among the to a large client population where there might be considerable risk
servers and clients. The TA generates an intricate cryptosystem of compromise between and among the servers and clients. The client
involving public and private encryption keys, together with a number population can be partitioned into a modest number of subgroups, each
of activation keys and associated private client decryption keys. associated with an individual client key.
The activation keys are used by the TA to activate and revoke
individual client decryption keys without changing the decryption
keys themselves.
The TA provides the server with a private encryption key and public The TA generates an intricate cryptosystem involving encryption and
decryption key. The server adjusts the keys by a nonce for each decryption keys, together with a number of activation keys and
plaintext encryption, so they appear different on each use. The associated client keys. The TA can activate and revoke individual
encrypted ciphertext and adjusted public decryption key are provided client keys without changing the client keys themselves. The TA
in the client message. The client computes the decryption key from provides to the servers an encryption key E and partial decryption
its private decryption key and the public decryption key in the keys g-bar and g-hat which depend on the activated keys. The servers
message. have no additional information and, in particular, cannot masquerade
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
changed if the TA activates or deactivates any client key. The
clients have no further information and, in particular, cannot
masquerade as a server or TA.
In the MV scheme the activation keys are known only to the TA. The The scheme uses an encryption algorithm similar to El Gamal
TA decides which keys to activate and provides to the servers a cryptography and a polynomial formed from the expansion of product
private encryption key E and public decryption keys g-bar and g-hat terms (x-x_1)(x-x_2)(x-x_3)...(x-x_n), as described in [14]. The
which depend on the activated keys. The servers have no additional paper has significant errors and serious omissions. The cryptosystem
information and, in particular, cannot masquerade as a TA. In is constructed so that, for every encrytion key E its iniverse is
addition, the TA provides to each client j individual private (g-bar^x-hat_j)(g-hat^x-bar_j) mod p for every j. This remains true
decryption keys x-bar_j and x-hat_j , which do not need to be changed if both quantities are raised to the power k mod p. The difficulty
if the TA activates or deactivates this key. The clients have no in finding E is equivalent to the descrete log problem.
further information and, in particular, cannot masquerade as a server
or TA.
The MV values hide in a DSA cuckoo structure which uses the same The scheme is shown in Figure Figure 18. The TA generates the
parameters, but generated in a different way. The values are used in parameters, group key, server keys and client keys, one for each
an encryption scheme similar to El Gamal cryptography and a client, all of which must be protected to prevent theft of service.
polynomial formed from the expansion of product terms (x-x_1)*(x- Note that only the TA has the group key, which is not known to either
x_2)*(x-x_3)*...*(x-x_n), as described in [15]. The paper has the servers or clients. In this sense the MV scheme is a zero-
significant errors and serious omissions. knowledge proof.
Trusted Trusted
Authority Authority
+------------+ +------------+
| Parameters | | Parameters |
+------------+ +------------+
| Group Key | | Group Key |
+------------+ +------------+
| Server Key | | Server Key |
Secure +------------+ Secure Secure +------------+ Secure
+-------------| Client Key |-----------+ +-------------| Client Key |-----------+
| +------------+ | | +------------+ |
\|/ \|/ \|/ \|/
+------------+ Challenge +------------+ +------------+ Challenge +------------+
| Parameters |<------------------------| Parameters | | Parameters |<------------------------| Parameters |
+------------+ +------------+ +------------+ +------------+
| Server Key |------------------------>| Client Key | | Server Key |------------------------>| Client Key |
+------------+ Response +------------+ +------------+ Response +------------+
Server Client Server Client
Figure 19: Mu-Varadharajan (MV) Identity Scheme Figure 18: Mu-Varadharajan (MV) Identity Scheme
The MV identity scheme is shown in Figure Figure 19. The TA writes The TA hides MV parameters and keys in OpenSSL DSA cuckoo structures.
the server parameters, private encryption key and public decryption The MV parameters are identical to the DSA parameters, so the OpenSSL
keys for all servers as a DSA private key encoded in PEM, as shown in library can be used directly. The structure shown in Figures below
the Figure Figure 20. are written to files as a DSA private key encoded in PEM. Unused
structure members are set to one. Figure Figure 19 shows the data
structure used by the servers, while Figure Figure 20 shows the
client data 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 | |
+---------+----------+------------+-------------+ +---------+----------+------------+-------------+
| g-bar | priv_key | public | server | | g-bar | priv_key | public | server |
| | | decrypt | | | | | decrypt | |
+---------+----------+------------+-------------+ +---------+----------+------------+-------------+
| g-hat | pub_key | public | server | | g-hat | pub_key | public | server |
| | | decrypt | | | | | decrypt | |
+---------+----------+------------+-------------+ +---------+----------+------------+-------------+
Figure 19: MV Scheme Server Structure
Figure 20: MV Scheme Server Parameters
The TA writes the client parameters and private decryption keys for
each client as a DSA private key encoded in PEM. It is used only by
the designated recipient(s) who pay a suitably outrageous fee for its
use. Unused structure members are set to one, as shown in Table
Figure 21,
+---------------------------------+-------------+ +---------------------------------+-------------+
| MV | DSA | Item | Include | | MV | DSA | Item | Include |
+=========+==========+============+=============+ +=========+==========+============+=============+
| p | p | modulus | all | | p | p | modulus | all |
+---------+----------+------------+-------------+ +---------+----------+------------+-------------+
| x-bar_j | priv_key | public | client | | x-bar_j | priv_key | public | client |
| | | decrypt | | | | | decrypt | |
+---------+----------+------------+-------------+ +---------+----------+------------+-------------+
| x-hat_j | pub_key | public | client | | x-hat_j | pub_key | public | client |
| | | decrypt | | | | | decrypt | |
+---------+----------+------------+-------------+ +---------+----------+------------+-------------+
Figure 21: MV Scheme Client Parameters Figure 20: MV Scheme Client Structure
The devil is in the details. Let q be the product of n distinct
primes s'_j (j = 1...n), where each s'_j, also called an activation
key, has m significant bits. Let prime p = 2q + 1, so that q and
each s'_j divide p-1 and p has M=nm+1 significant bits. Let g be the
generator of the multiplicative group Zp*; that is, gcd(g, p-1) = 1
and g^q = 1 mod p. We do modular arithmetic over Zq and then project
into Zp* as powers of g. Sometimes we have to compute an inverse
b^-1 of random b in Zq, but for that purpose we require gcd(b, q) =
1. We expect M to be in the 500-bit range and n relatively small,
like 30. The TA uses a nasty probabilistic algorithm to generate the
cryptosystem.
1. Generate the m-bit primes s'_j (0 < j < n), which may have to be
replaced later. As a practical matter, it is tough to find more
than 30 distinct primes for M=512 or 60 primes for M=1024. The
latter can take several hundred iterations and several minutes on
a Sun Blade 1000.
2. Compute modulus q = s'_1 * s'_2 * ... * s'_n, then modulus p = 2q
+ 1. If p is composite, the TA replaces one of the primes with a
new distinct prime and tries again. Note that q will hardly be a
secret since p is revealed to servers and clients. However,
factoring q to find the primes should be adequately hard, as this
is the same problem considered hard in RSA. Question: is it as
hard to find n small prime factors totalling M bits as it is to
find two large prime factors totalling M bits? Remember, the bad
guy doesn't know n.
3. Associate with each s'_j an element s_j such that s_j*s'_j = s'_j
mod q. One way to find an s_j is the quotient s_j = (q + s'_j) /
s'_j.
4. Compute the generator g of Z_p using a random roll such that
gcd(g, p-1) = 1 and g^q = 1 mod p. If not, roll again.
Once the cryptosystem parameters have been determined, the TA sets up
a specific instance of the scheme as follows.
1. Roll n random roots x_j (0 < x_j < q) for a polynomial of order
n. While it may not be strictly necessary, Make sure each root
has no factors in common with q.
2. Expand the n product terms (x-x_0)*(x-x_1)*...*(x-x_n) to form n
+ 1 coefficients a_i mod q (0 <= i < n) in powers of x using a
fast method contributed by C. Boncelet.
3. Generate g_i = g^(a_i) mod p for all i and the generator g.
Verify the product g_i^(a_i*(x_j)^i) = 1 mod p for all i, j (0 <=
i < n, 0 <= j < n). Note the a_i*(x_j)^i exponent is computed
mod q, but the g_i is computed mod p. Also note the expression
given in the paper cited is incorrect.
4. Make master encryption key A = product of (g_i)^x_j mod p (0 <= i
< n, 0 <= j < n). Keep it around for awhile, since it is
expensive to compute.
5. Roll private random group key b (0 < b < q), where gcd(b, q) = 1
to guarantee the inverse exists, then compute b^-1 mod q. If b
is changed, all keys must be recomputed.
6. Make private client keys x-bar_j = b^-1 * ((x_1)^n + (x_2)^n +
... + (x_n)^n) mod q (omitting (x_j)^n from the summation) and
x-hat_j = s_j * (x_j)^n mod q for all j. Note that the keys for
the jth client involve only s_j, but not s'_j or s. The TA sends
(p, x-bar_j, x-hat_j) to the jth client(s) using secure means.
7. The activation key is initially q by construction. The TA The devil is in the details, which are beyond the scope of this memo.
revokes client j by dividing q by s'_j. The quotient becomes the The steps in generating the cryptosystem activating the keys and
activation key s. Note we always have to revoke one key; generating the partial decryption keys are in [15] page 170 ff.
otherwise, the plaintext and cryptotext would be identical. The
TA computes E = A^s, g-bar = x-bar^s mod p, g-hat = x-hat^sb mod
p and sends (p, E, g-bar, g-hat to the servers using secure
means.
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' = E^k mod p and public decryption key g-bar' = encryption key E-prime = E^k mod p and partial decryption keys
g-bar^k mod p and g-hat' = g-hat^k mod p. He encrypts x = E' * r g-bar-prime = g-bar^k mod p and g-hat-prime = g-hat^k mod p. He
mod p and sends (hash(x), g-bar', g-hat') to Alice. encrypts x = E-prime * r mod p and sends (x, g-bar-prime, g-hat-
prime) to Alice.
3. Alice computes the session decryption key E^-1 = (g-bar')^x-hat_j
* (g-hat')^x-bar_j mod p, recovers the encryption key E' =
(E^-1)^-1 mod p, encrypts z = E' * r mod p, then verifies that
hash(z) = hash(x).
D.6. Interoperability Issues
A specific combination of authentication scheme (none, symmetric key,
Autokey), digest/signature scheme and identity scheme (PC, TC, IFF,
GQ, MV) is called a cryptotype, although not all combinations are
possible. There may be management configurations where the servers
and clients may not all support the same cryptotypes. A secure NTPv4
subnet can be configured in several ways while keeping in mind the
principles explained in this section. Note however that some
cryptotype combinations may successfully interoperate with each
other, but may not represent good security practice.
The cryptotype of an association is determined at the time of
mobilization, either at configuration time or some time later when a
packet of appropriate cryptotype arrives. When a client, broadcast
or symmetric active association is mobilized at configuration time,
it can be designated non-authentic, authenticated with symmetric key
or authenticated with some Autokey scheme, and subsequently it will
send packets with that cryptotype. When a responding server,
broadcast client or symmetric passive association is mobilized, it is
designated with the same cryptotype as the received packet.
When multiple identity schemes are supported, the parameter exchange
determines which one is used. The request message contains bits
corresponding to the schemes it supports, while the response message
contains bits corresponding to the schemes it supports. The client
matches the server bits with its own and selects a compatible
identity scheme. The server is driven entirely by the client
selection and remains stateless. When multiple selections are
possible, the order from most secure to least is GC, IFF, TC. Note
that PC does not interoperate with any of the others, since they
require the host certificate which a PC server will not reveal.
Following the principle that time is a public value, a server
responds to any client packet that matches its cryptotype
capabilities. Thus, a server receiving a non-authenticated packet
will respond with a non-authenticated packet, while the same server
receiving a packet of a cryptotype it supports will respond with
packets of that cryptotype. However, new broadcast or manycast
client associations or symmetric passive associations will not be
mobilized unless the server supports a cryptotype compatible with the
first packet received. By default, non-authenticated associations
will not be mobilized unless overridden in a decidedly dangerous way.
Some examples may help to reduce confusion. Client Alice has no
specific cryptotype selected. Server Bob supports both symmetric key
and Autokey cryptography. Alice's non-authenticated packets arrive
at Bob, who replies with non-authenticated packets. Cathy has a copy
of Bob's symmetric key file and has selected key ID 4 in packets to
Bob. If Bob verifies the packet with key ID 4, he sends Cathy a reply
with that key. If authentication fails, Bob sends Cathy a thing
called a crypto-NAK, which tells her something broke. She can see
the evidence using the utility programs of the NTP software library.
Symmetric peers Bob and Denise have rolled their own host keys,
certificates and identity parameters and lit the host status bits for
the identity schemes they can support. Upon completion of the
parameter exchange, both parties know the digest/signature scheme and
available identity schemes of the other party. They do not have to
use the same schemes, but each party must use the digest/signature
scheme and one of the identity schemes supported by the other party.
It should be clear from the above that Bob can support all the girls 3. Alice computes the session decryption key E^-1 = (g-bar-prime)^x-
at the same time, as long as he has compatible authentication and hat_j (g-hat-prime)^x-bar_j mod p and verifies that r = E^-1 x.
identification credentials. Now, Bob can act just like the girls in
his own choice of servers; he can run multiple configured
associations with multiple different servers (or the same server,
although that might not be useful). But, wise security policy might
preclude some cryptotype combinations; for instance, running an
identity scheme with one server and no authentication with another
might not be wise.
Appendix E. ASN.1 Encoding Rules Appendix C. ASN.1 Encoding Rules
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 [16]. The particular signature encryption schemes are specified in [16]. The particular
algorithms required for conformance are not specified in this report. algorithms required for conformance are not specified in this memo.
E.1. COOKIE request, IFF response, GQ response, MV response C.1. 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 67, line 11 skipping to change at page 49, line 38
encoded by the i2d_DSAparams() routine in the OpenSSL library. In encoded by the i2d_DSAparams() routine in the OpenSSL library. In
the response, p is the hash of the encrypted challenge value and (q, the response, p is the hash of the encrypted challenge value and (q,
g) is the client portion of the decryption key. g) is the client portion of the decryption key.
DSAparameters ::= SEQUENCE { DSAparameters ::= SEQUENCE {
p ::= INTEGER, p ::= INTEGER,
q ::= INTEGER, q ::= INTEGER,
g ::= INTEGER g ::= INTEGER
} }
E.2. CERT response, SIGN request and response C.2. Certificates
Certificate extension fields are used to convey information used by
the identity schemes. While the semantics of these fields generally
conforms with conventional usage, there are subtle variations. The
fields used by Autokey Version 2 include:
o Basic Constraints. This field defines the basic functions of the
certificate. It contains the string "critical,CA:TRUE", which
means the field must be interpreted and the associated private key
can be used to sign other certificates. While included for
compatibility, Autokey makes no use of this field.
o Key Usage. This field defines the intended use of the public key
contained in the certificate. It contains the string
"digitalSignature,keyCertSign", which means the contained public
key can be used to verify signatures on data and other
certificates. While included for compatibility, Autokey makes no
use of this field.
o Extended Key Usage. This field further refines the intended use
of the public key contained in the certificate and is present only
in self-signed certificates. It contains the string "Private" if
the certificate is designated private or the string "trustRoot" if
it is designated trusted. A private certificate is always
trusted.
o Subject Key Identifier. This field contains the client identity
key used in the GQ identity scheme. It is present only if the GQ
scheme is in use.
The value field contains a X509v3 certificate encoded by the The value field contains a X509v3 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 [11], including the use of X509v3 extension the rules stated in [10], including the use of X509v3 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
skipping to change at page 68, line 4 skipping to change at page 51, line 11
when the certificate was generated. The signature is the object when the certificate was generated. The signature is the object
identifier of the message digest/signature encryption scheme used to identifier of the message digest/signature encryption scheme used to
sign the certificate. It must be identical to the sign the certificate. It must be identical to the
signatureAlgorithm. signatureAlgorithm.
CertificateSerialNumber ::= INTEGER CertificateSerialNumber ::= INTEGER
Validity ::= SEQUENCE { Validity ::= SEQUENCE {
notBefore UTCTime, notBefore UTCTime,
notAfter UTCTime notAfter UTCTime
} }
The notBefore and notAfter define the period of validity as defined The notBefore and notAfter define the period of validity as defined
in Appendix D. in Appendix B.
SubjectPublicKeyInfo ::= SEQUENCE { SubjectPublicKeyInfo ::= SEQUENCE {
algorithm AlgorithmIdentifier, algorithm AlgorithmIdentifier,
subjectPublicKey BIT STRING subjectPublicKey BIT STRING
} }
The AlgorithmIdentifier specifies the encryption algorithm for the The AlgorithmIdentifier specifies the encryption algorithm for the
subject public key. The subjectPublicKey is the public key of the subject public key. The subjectPublicKey is the public key of the
subject. subject.
skipping to change at page 68, line 28 skipping to change at page 51, line 36
extnID OBJECT IDENTIFIER, extnID OBJECT IDENTIFIER,
critical BOOLEAN DEFAULT FALSE, critical BOOLEAN DEFAULT FALSE,
extnValue OCTET STRING extnValue OCTET STRING
} }
Name ::= SEQUENCE { Name ::= SEQUENCE {
OBJECT IDENTIFIER commonName OBJECT IDENTIFIER commonName
PrintableString HostName PrintableString HostName
} }
For all certificates, the subject HostName is the unique DNS name of For trusted host certificates the subject and issuer HostName is the
the host to which the public key belongs. The reference NTP name of the group, while for all other host certificates the
implementation uses the string returned by the Unix gethostname() subject and issuer HostName is the NTP name of the host. In the
routine (trailing NUL removed). For other than self-signed reference implementation if these names are not explicitly specified,
certificates, the issuer HostName is the unique DNS name of the host they default to the string returned by the Unix gethostname() routine
signing the certificate. (trailing NUL removed). For other than self-signed certificates, the
issuer HostName is the unique DNS name of the host signing the
certificate.
Authors' Addresses 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
skipping to change at page 70, line 7 skipping to change at page 53, line 7
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
Full Copyright Statement Full Copyright Statement
Copyright (C) The IETF Trust (2007). Copyright (C) The IETF Trust (2008).
This document is subject to the rights, licenses and restrictions This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors contained in BCP 78, and except as set forth therein, the authors
retain all their rights. retain all their rights.
This document and the information contained herein are provided on an This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
 End of changes. 242 change blocks. 
1814 lines changed or deleted 1054 lines changed or added

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