draft-ietf-ntp-autokey-01.txt   draft-ietf-ntp-autokey-02.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 February 25, 2008
Expires: August 28, 2008 Expires: September 2, 2008
Network Time Protocol Version 4 Autokey Specification Network Time Protocol Version 4 Autokey Specification
draft-ietf-ntp-autokey-01 draft-ietf-ntp-autokey-02
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 August 28, 2008. This Internet-Draft will expire on September 2, 2008.
Copyright Notice
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
skipping to change at page 2, line 40 skipping to change at page 2, line 37
10.3. Certificate Message (CERT) . . . . . . . . . . . . . . . 24 10.3. Certificate Message (CERT) . . . . . . . . . . . . . . . 24
10.4. Cookie Message (COOKIE) . . . . . . . . . . . . . . . . . 24 10.4. Cookie Message (COOKIE) . . . . . . . . . . . . . . . . . 24
10.5. Autokey Message (AUTO) . . . . . . . . . . . . . . . . . 24 10.5. Autokey Message (AUTO) . . . . . . . . . . . . . . . . . 24
10.6. Leapseconds Values Message (LEAP) . . . . . . . . . . . . 25 10.6. Leapseconds Values Message (LEAP) . . . . . . . . . . . . 25
10.7. Sign Message (SIGN) . . . . . . . . . . . . . . . . . . . 25 10.7. Sign Message (SIGN) . . . . . . . . . . . . . . . . . . . 25
10.8. Identity Messages (IFF, GQ, MV) . . . . . . . . . . . . . 25 10.8. Identity Messages (IFF, GQ, MV) . . . . . . . . . . . . . 25
11. Autokey State Machine . . . . . . . . . . . . . . . . . . . . 25 11. Autokey State Machine . . . . . . . . . . . . . . . . . . . . 25
11.1. Status Word . . . . . . . . . . . . . . . . . . . . . . . 25 11.1. Status Word . . . . . . . . . . . . . . . . . . . . . . . 25
11.2. Host State Variables . . . . . . . . . . . . . . . . . . 27 11.2. Host State Variables . . . . . . . . . . . . . . . . . . 27
11.3. Client State Variables (all modes) . . . . . . . . . . . 29 11.3. Client State Variables (all modes) . . . . . . . . . . . 29
11.4. Server State Variables (broadcast and symmetric modes) . 30 11.4. Protocol State Transitions . . . . . . . . . . . . . . . 30
11.5. Protocol State Transitions . . . . . . . . . . . . . . . 30 11.4.1. Server Dance . . . . . . . . . . . . . . . . . . . . 30
11.5.1. Server Dance . . . . . . . . . . . . . . . . . . . . 30 11.4.2. Broadcast Dance . . . . . . . . . . . . . . . . . . . 31
11.5.2. Broadcast Dance . . . . . . . . . . . . . . . . . . . 31 11.4.3. Symmetric Dance . . . . . . . . . . . . . . . . . . . 32
11.5.3. Symmetric Dance . . . . . . . . . . . . . . . . . . . 32 11.5. Error Recovery . . . . . . . . . . . . . . . . . . . . . 33
11.6. Error Recovery . . . . . . . . . . . . . . . . . . . . . 34 11.6. Security Considerations . . . . . . . . . . . . . . . . . 35
11.7. Security Considerations . . . . . . . . . . . . . . . . . 36 11.7. Protocol Vulnerability . . . . . . . . . . . . . . . . . 35
11.8. Protocol Vulnerability . . . . . . . . . . . . . . . . . 36 11.8. Clogging Vulnerability . . . . . . . . . . . . . . . . . 36
11.9. Clogging Vulnerability . . . . . . . . . . . . . . . . . 37 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 37
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 38 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 37
13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 38 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 37
14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 38 14.1. Normative References . . . . . . . . . . . . . . . . . . 37
14.1. Normative References . . . . . . . . . . . . . . . . . . 38 14.2. Informative References . . . . . . . . . . . . . . . . . 37
14.2. Informative References . . . . . . . . . . . . . . . . . 38 Appendix A. Timestamps, Filestamps and Partial Ordering . . . . . 38
Appendix A. Timestamps, Filestamps and Partial Ordering . . . . . 39 Appendix B. Identity Schemes . . . . . . . . . . . . . . . . . . 39
Appendix B. Identity Schemes . . . . . . . . . . . . . . . . . . 40 Appendix C. Private Certificate (PC) Scheme . . . . . . . . . . . 40
B.1. Private Certificate (PC) Scheme . . . . . . . . . . . . . 41 Appendix D. Trusted Certificate (TC) Scheme . . . . . . . . . . . 40
B.2. Trusted Certificate (TC) Scheme . . . . . . . . . . . . . 41 Appendix E. Schnorr (IFF) Identity Scheme . . . . . . . . . . . . 41
B.3. Schnorr (IFF) Identity Scheme . . . . . . . . . . . . . . 42 Appendix F. Guillard-Quisquater (GQ) Identity Scheme . . . . . . 43
B.4. Guillard-Quisquater (GQ) Identity Scheme . . . . . . . . 44 Appendix G. Mu-Varadharajan (MV) Identity Scheme . . . . . . . . 45
B.5. Mu-Varadharajan (MV) Identity Scheme . . . . . . . . . . 46 Appendix H. ASN.1 Encoding Rules . . . . . . . . . . . . . . . . 47
Appendix C. ASN.1 Encoding Rules . . . . . . . . . . . . . . . . 48 H.1. COOKIE request, IFF response, GQ response, MV response . 48
C.1. COOKIE request, IFF response, GQ response, MV response . 49 H.2. Certificates . . . . . . . . . . . . . . . . . . . . . . 48
C.2. Certificates . . . . . . . . . . . . . . . . . . . . . . 49 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 50
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 51 Intellectual Property and Copyright Statements . . . . . . . . . . 52
Intellectual Property and Copyright Statements . . . . . . . . . . 53
1. Introduction 1. Introduction
A distributed network service requires reliable, ubiquitous and A distributed network service requires reliable, ubiquitous and
survivable provisions to prevent accidental or malicious attacks on survivable provisions to prevent accidental or malicious attacks on
the servers and clients in the network or the values they exchange. the servers and clients in the network or the values they exchange.
Reliability requires that clients can determine that received packets Reliability requires that clients can determine that received packets
are authentic; that is, were ctually sent by the intended server and are authentic; that is, were actually sent by the intended server and
not manufactured or modified by an intruder. Ubiquity requires that not manufactured or modified by an intruder. Ubiquity requires that
a client can verify the authenticity of a server using only public a client can verify the authenticity of a server using only public
information. Survivability requires protection from faulty information. Survivability requires protection from faulty
implementations, improper operation and possibly malicious clogging implementations, improper operation and possibly malicious clogging
and replay attacks. and replay attacks.
This memo describes a cryptographically sound and efficient This memo describes a cryptographically sound and efficient
methodology for use in the Network Time Protocol (NTP) [1]. The methodology for use in the Network Time Protocol (NTP)
various key agreement schemes [2][3][4] proposed require per- [I-D.ietf-ntp-ntpv4-proto]. The various key agreement schemes
association state variables, which contradicts the principles of the [RFC2408][RFC2412][RFC2522] proposed require per-association state
remote procedure call (RPC) paradigm in which servers keep no state variables, which contradicts the principles of the remote procedure
for a possibly large client population. An evaluation of the PKI call (RPC) paradigm in which servers keep no state for a possibly
model and algorithms as implemented in the OpenSSL library leads to large client population. An evaluation of the PKI model and
the conclusion that any scheme requiring every NTP packet to carry a algorithms as implemented in the OpenSSL library leads to the
PKI digital signature would result in unacceptably poor timekeeping conclusion that any scheme requiring every NTP packet to carry a PKI
digital signature would result in unacceptably poor timekeeping
performance. performance.
The Autokey protocol is based on a combination of PKI and a pseudo- The Autokey protocol is based on a combination of PKI and a pseudo-
random sequence generated by repeated hashes of a cryptographic value random sequence generated by repeated hashes of a cryptographic value
involving both public and private components. This scheme has been involving both public and private components. This scheme has been
implemented, tested and deployed in the Internet of today. A implemented, tested and deployed in the Internet of today. A
detailed description of the security model, design principles and detailed description of the security model, design principles and
implementation is presented in this memo. implementation is presented in this memo.
2. NTP Security Model 2. NTP Security Model
NTP security requirements are even more stringent than most other NTP security requirements are even more stringent than most other
distributed services. First, the operation of the authentication distributed services. First, the operation of the authentication
mechanism and the time synchronization mechanism are inextricably mechanism and the time synchronization mechanism are inextricably
intertwined. Reliable time synchronization requires cryptographic intertwined. Reliable time synchronization requires cryptographic
keys which are valid only over esignated time intervals; but, time keys which are valid only over a designated time intervals; but, time
intervals can be enforced only when participating servers and clients intervals can be enforced only when participating servers and clients
are reliably synchronized to UTC. In addition, the NTP subnet is are reliably synchronized to UTC. In addition, the NTP subnet is
hierarchical by nature, so time and trust flow from the primary hierarchical by nature, so time and trust flow from the primary
servers at the root through secondary servers to the clients at the servers at the root through secondary servers to the clients at the
leaves. leaves.
A client can claim authentic to dependent applications only if all A client can claim authentic to dependent applications only if all
servers on the path to the primary servers are bone-fide authentic. servers on the path to the primary servers are bone-fide authentic.
In order to emphasize this requirement, in this memo the notion of In order to emphasize this requirement, in this memo the notion of
"authentic" is replaced by "proventic", a noun new to English and "authentic" is replaced by "proventic", 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
derivatives of authentic will be adopted for proventic as well. In derivatives of authentic will be adopted for proventic as well. In
NTP each server authenticates the next lower stratum servers and NTP each server authenticates the next lower stratum servers and
proventicates (authenticates by induction) the lowest stratum proventicates (authenticates by induction) the lowest stratum
(primary) servers. Serious computer linguists would correctly (primary) servers. Serious computer linguists would correctly
interpret the proventic relation as the transitive closure of the interpret the proventic relation as the transitive closure of the
authentic relation. authentic relation.
skipping to change at page 5, line 28 skipping to change at page 5, line 30
possibly including falsetickers. A particular association is possibly including falsetickers. A particular association is
proventic if the server certificate and identity have been verified proventic if the server certificate and identity have been verified
by the means described in this memo. However, the statement "the by the means described in this memo. However, the statement "the
client is synchronized to proventic sources" means that the system client is synchronized to proventic sources" means that the system
clock has been set using the time values of one or more proventic clock has been set using the time values of one or more proventic
associations and according to the NTP mitigation algorithms. associations and according to the NTP mitigation algorithms.
Over the last several years the IETF has defined and evolved the Over the last several years the IETF has defined and evolved the
IPSEC infrastructure for privacy protection and source authentication IPSEC infrastructure for privacy protection and source authentication
in the Internet. The infrastructure includes the Encapsulating in the Internet. The infrastructure includes the Encapsulating
Security Payload (ESP) [5] and Authentication Header (AH) [6] for Security Payload (ESP) [RFC2406] and Authentication Header (AH)
IPv4 and IPv6. Cryptographic algorithms that use these headers for [RFC2402] for IPv4 and IPv6. Cryptographic algorithms that use these
various purposes include those developed for the PKI, including MD5 headers for various purposes include those developed for the PKI,
message digests, RSA digital signatures and several variations of including MD5 message digests, RSA digital signatures and several
Diffie-Hellman key agreements. The fundamental assumption in the variations of Diffie-Hellman key agreements. The fundamental
security model is that packets transmitted over the Internet can be assumption in the security model is that packets transmitted over the
intercepted by other than the intended recipient, remanufactured in Internet can be intercepted by other than the intended recipient,
various ways and replayed in whole or part. These packets can cause remanufactured in various ways and replayed in whole or part. These
the client to believe or produce incorrect information, cause packets can cause the client to believe or produce incorrect
protocol operations to fail, interrupt network service or consume information, cause protocol operations to fail, interrupt network
precious network and processor resources. service or consume 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 memo is to detect and discard and protocols described in this memo is to detect and discard
spurious packets sent by other than the intended sender or sent by spurious packets sent by 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,
skipping to change at page 6, line 31 skipping to change at page 6, line 32
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 11.7, the modified packet cannot arrive at considered in Section 11.6, 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 11.7, the packet. Except in unlikely cases considered in Section 11.6, the
middleman does not have the server private keys. middleman does not have the server private keys.
The NTP security model assumes the following possible limitations. The NTP security model assumes the following possible limitations.
1. The running times for public key algorithms are relatively long 1. The running times for public key algorithms are relatively long
and highly variable. In general, the performance of the time and highly variable. In general, the performance of the time
synchronization function is badly degraded if these algorithms synchronization function is badly degraded if these algorithms
must be used for every NTP packet. must be used for every NTP packet.
2. In some modes of operation it is not feasible for a server to 2. In some modes of operation it is not feasible for a server to
skipping to change at page 7, line 38 skipping to change at page 7, line 39
The Autokey protocol described in this memo is designed to meet the The Autokey protocol described in this memo is designed to meet the
following objectives. In-depth discussions on these objectives is in following objectives. In-depth discussions on these objectives is in
the web briefings and will not be elaborated in this memo. Note that the web briefings and will not be elaborated in this memo. Note that
here and elsewhere in this memo mention of broadcast mode means here and elsewhere in this memo mention of broadcast mode means
multicast mode as well, with exceptions as noted in the NTP software multicast mode as well, with exceptions as noted in the NTP software
documentation. documentation.
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 [7]. As a practical matter, the key scheme described in [RFC1305]. As a practical matter, the
reference implementation must use the same internal key reference implementation must use the same internal key
management system, including the use of 32-bit key IDs and management system, including the use of 32-bit key IDs and
existing mechanisms to store, activate and revoke keys. existing mechanisms to store, activate and revoke keys.
2. It must provide for the independent collection of cryptographic 2. It must provide for the independent collection of cryptographic
values and time values. A NTP packet is accepted for processing values and time values. A NTP packet is accepted for processing
only when the required cryptographic values have been obtained only when the required cryptographic values have been obtained
and verified and the packet has passed all header sanity checks. and verified and the packet has passed all header sanity checks.
3. It must not significantly degrade the potential accuracy of the 3. It must not significantly degrade the potential accuracy of the
NTP synchronization algorithms. In particular, it must not make NTP synchronization algorithms. In particular, it must not make
unreasonable demands on the network or host processor and memory unreasonable demands on the network or host processor and memory
resources. resources.
4. It must be resistant to cryptographic attacks, specifically those 4. It must be resistant to cryptographic attacks, specifically those
identified in the security model above. In particular, it must identified in the security model above. In particular, it must
be tolerant of operational or implementation variances, such as be tolerant of operational or implementation variances, such as
packet loss or misorder, or suboptimal configurations. packet loss or disorder, or suboptimal configurations.
5. It must build on a widely available suite of cryptographic 5. It must build on a widely available suite of cryptographic
algorithms, yet be independent of the particular choice. In algorithms, yet be independent of the particular choice. In
particular, it must not require data encryption other than particular, it must not require data encryption other than
incidental to signature and cookie encryption operations. incidental to signature and cookie encryption operations.
6. It must function in all the modes supported by NTP, including 6. It must function in all the modes supported by NTP, including
server, symmetric and broadcast modes. server, symmetric and broadcast modes.
4. Autokey Cryptography 4. Autokey Cryptography
skipping to change at page 10, line 36 skipping to change at page 10, line 36
| 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 Figure 3 shows how the autokey list and autokey values are Figure 3 shows how the autokey list and autokey values are computed.
computed. The key IDs used in the autokey list consists of a The key IDs used in the autokey list consists of a sequence starting
sequence starting with a random 32-bit nonce (autokey seed) equal to with a random 32-bit nonce (autokey seed) equal to or greater than
or greater than the pivot as the first key ID. The first autokey is the pivot as the first key ID. The first autokey is computed as
computed as above using the given cookie and autokey seed and above using the given cookie and autokey seed and assigned index 0.
assigned index 0. The first 32 bits of the result in network byte The first 32 bits of the result in network byte order become the next
order become the next THe MD5 hash of the autokey is the key value The MD5 hash of the autokey is the key value saved in the key cache
saved in the key cache along with the key ID. The first 32 bits of along with the key ID. The first 32 bits of the key become the key
the key become the key ID for the next autokey assigned index 1. ID for the next autokey assigned index 1.
Operations continue to generate the entire list. It may happen that Operations continue to generate the entire list. It may happen that
a newly generated key ID is less than the pivot or collides with a newly generated key ID is less than the pivot or collides with
another one already generated (birthday event). When this happens, another one already generated (birthday event). When this happens,
which occurs only rarely, the key list is terminated at that point. which occurs only rarely, the key list is terminated at that point.
The lifetime of each key is set to expire one poll interval after its The lifetime of each key is set to expire one poll interval after its
scheduled use. In the reference implementation, the list is scheduled use. In the reference implementation, the list is
terminated when the maximum key lifetime is about one hour, so for terminated when the maximum key lifetime is about one hour, so for
poll intervals above one hour a new key list containing only a single poll intervals above one hour a new key list containing only a single
entry is regenerated for every poll. entry is regenerated for every poll.
skipping to change at page 12, line 17 skipping to change at page 12, line 17
For Autokey purposes all hosts belonging to a secure group have the For Autokey purposes all hosts belonging to a secure group have the
same group name but different host names, not necessarily related to same group name but different host names, not necessarily related to
the DNS names. The group name is used in the subject and issuer the DNS names. The group name is used in the subject and issuer
fields of the TH certificates; the host name is used in these fields fields of the TH certificates; the host name is used in these fields
for other hosts. Thus, all host certificates are self-signed. for other hosts. Thus, all host certificates are self-signed.
During the Autokey protocol a client requests the server to sign its During the Autokey protocol a client requests the server to sign its
certificate and caches the result. A certificate trail is certificate and caches the result. A certificate trail is
constructed by each host, possibly via intermediate hosts and ending constructed by each host, possibly via intermediate hosts and ending
at a TH. Thus, each host along the trail retrieves the entire trail 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 from its server(s) and provides this plus its own signed certificates
to its clients. to its clients.
Secure groups can be configured as hierarchies where a TH of one Secure groups can be configured as hierarchies where a TH of one
group can be a client of one or more other groups operating at a group can be a client of one or more other groups operating at a
lower stratum. In one scenario, groups RED and GREEN can be lower stratum. In one scenario, groups RED and GREEN can be
cryptographically distinct, but both be clients of group BLUE cryptographically distinct, but both be clients of group BLUE
operating at a lower stratum. In another scenario, group CYAN can be operating at a lower stratum. In another scenario, group CYAN can be
a client of multiple groups YELLOW and MAGENTA, both operating at a a client of multiple groups YELLOW and MAGENTA, both operating at a
lower stratum. There are many other scenarios, but all must be lower stratum. There are many other scenarios, but all must be
configured to include only acyclic certificate trails. configured to include only acyclic certificate trails.
skipping to change at page 15, line 51 skipping to change at page 15, line 51
A digital signature scheme provides secure server authentication, but A digital signature scheme provides secure server authentication, but
it does not provide protection against masquerade, unless the server it does not provide protection against masquerade, unless the server
identity is verified by other means. The PKI model requires a server identity is verified by other means. The PKI model requires a server
to prove identity to the client by a certificate trail, but to prove identity to the client by a certificate trail, but
independent means such as a drivers license are required for a CA to independent means such as a drivers license are required for a CA to
sign the server certificate. While Autokey supports this model by sign the server certificate. While Autokey supports this model by
default, in a hierarchical ad-hoc network, especially with server default, in a hierarchical ad-hoc network, especially with server
discovery schemes like NTP Manycast, proving identity at each rest discovery schemes like NTP Manycast, proving identity at each rest
stop on the trail must be an intrinsic capability of Autokey itself. stop on the trail must be an intrinsic capability of Autokey itself.
While the identity scheme described in [8] is based on a ubiquitous While the identity scheme described in [RFC2875] is based on a
Diffie-Hellman infrastructure, it is expensive to generate and use ubiquitous Diffie-Hellman infrastructure, it is expensive to generate
when compared to others described in Appendix B. In principle, an and use when compared to others described in Appendix B. In
ordinary public key scheme could be devised for this purpose, but the principle, an ordinary public key scheme could be devised for this
most stringent Autokey design requires that every challenge, even if purpose, but the most stringent Autokey design requires that every
duplicated, results in a different acceptable response. challenge, even if duplicated, results in a different acceptable
response.
There are five schemes now implemented in the NTPv4 reference There are five schemes now implemented in the NTPv4 reference
implementation to prove identity: (1) private certificate (PC), (2) implementation to prove identity: (1) private certificate (PC), (2)
trusted certificate (TC), (3) a modified Schnorr algorithm (IFF aka trusted certificate (TC), (3) a modified Schnorr algorithm (IFF aka
Identify Friendly or Foe), (4) a modified Guillou-Quisquater Identify Friendly or Foe), (4) a modified Guillou-Quisquater
algorithm (GQ), and (5) a modified Mu-Varadharajan algorithm (MV). algorithm (GQ), and (5) a modified Mu-Varadharajan algorithm (MV).
Following is a summary description of each; details are given in Following is a summary description of each; details are given in
Appendix B. Appendix B.
The PC scheme involves a private certificate as group key. The The PC scheme involves a private certificate as group key. The
certificate is distributed to all other group members by secure means certificate is distributed to all other group members by secure means
and is never revealed outside the group. In effect, the private and is never revealed outside the group. In effect, the private
certificate is used as a symmetric key. This scheme is used certificate is used as a symmetric key. This scheme is used
primarily for testing and development and is not recommended for primarily for testing and development and is not recommended for
regular use and is not considered further in this memo. regular use and is not considered further in this memo.
All other schemes involve a conventional certificate trail as All other schemes involve a conventional certificate trail as
described in RFC 2510 [9]. This is the default scheme when an described in RFC 2510 [RFC2510]. This is the default scheme when an
identity scheme is not specified. While the remaining identity identity scheme is not specified. While the remaining identity
schemes incorporate TC, it is not by itself considered further in schemes incorporate TC, it is not by itself considered further in
this memo. this memo.
The three remaining schemes IFF, GQ and MV involve a The three remaining schemes IFF, GQ and MV involve a
cryptographically strong challenge-response exchange where an cryptographically strong challenge-response exchange where an
intruder cannot deduce the server key, even after repeated intruder cannot deduce the server key, even after repeated
observations of multiple exchanges. In addition, the MV scheme is observations of multiple exchanges. In addition, the MV scheme is
properly described as a zero-knowledge proof, because the client can properly described as a zero-knowledge proof, because the client can
verify the server has the correct group key without either the server verify the server has the correct group key without either the server
skipping to change at page 17, line 4 skipping to change at page 17, line 5
results are correct. results are correct.
7. Timestamps and Filestamps 7. Timestamps and Filestamps
While public key signatures provide strong protection against While public key signatures provide strong protection against
misrepresentation of source, computing them is expensive. This misrepresentation of source, computing them is expensive. This
invites the opportunity for an intruder to clog the client or server invites the opportunity for an intruder to clog the client or server
by replaying old messages or originating bogus messages. A client by replaying old messages or originating bogus messages. A client
receiving such messages might be forced to verify what turns out to receiving such messages might be forced to verify what turns out to
be an invalid signature and consume significant processor resources. be an invalid signature and consume significant processor resources.
In order to foil such attacks, every Autokey message carries a In order to foil such attacks, every Autokey message carries a
timestamp in the form of the NTP seconds when it was. If the system timestamp in the form of the NTP seconds when it was. If the system
clock is synchronized to a proventic source, a signature is produced clock is synchronized to a proventic source, a signature is produced
with valid (nonzero) timestamp. Otherwise, there is no signature and with valid (nonzero) timestamp. Otherwise, there is no signature and
the timestamp is invalid (zero). The protocol detects and discards the timestamp is invalid (zero). The protocol detects and discards
extension fields with old or duplicate timestamps, before any values extension fields with old or duplicate timestamps, before any values
are used or signatures are verified. are used or signatures are verified.
Signatures are computed only when cryptgraphic values are created or Signatures are computed only when cryptographic values are created or
modified, which is by design not very ofter. Extension fields modified, which is by design not very often. Extension fields
carrying these signatures are copied to messages as needed, but the carrying these signatures are copied to messages as needed, but the
signarutres are not recomputed. There are three signature tyupes: signatures are not recomputed. There are three signature types:
1. Cookie signature/timestamp. The cookie is signed when created by 1. Cookie signature/timestamp. The cookie is signed when created by
the server and sent to the cliente. the server and sent to the client.
2. Autokey signature/timestamp. The autokey values are signed when 2. Autokey signature/timestamp. The autokey values are signed when
the key list is created. the key list is created.
3. Public values signature/timestamp. The public key, certificate 3. Public values signature/timestamp. The public key, certificate
and leapsecond values are signed at the time of generation, which and leapsecond values are signed at the time of generation, which
occurs when the system clock is first synchronized to a proventic occurs when the system clock is first synchronized to a proventic
source, when the values have changed and about once per day after source, when the values have changed and about once per day after
that, even if these values have not changed. that, even if these values have not changed.
skipping to change at page 18, line 20 skipping to change at page 18, line 20
forwarded from server to client, the filestamps are preserved, forwarded from server to client, the filestamps are preserved,
including those for certificate and leapseconds values. Packets with including those for certificate and leapseconds values. Packets with
older filestamps are discarded before spending cycles to verify the older filestamps are discarded before spending cycles to verify the
signature. signature.
8. Autokey Protocol Overview 8. Autokey Protocol Overview
The Autokey protocol includes a number of request/response exchanges The Autokey protocol includes a number of request/response exchanges
that must be completed in order. In each exchange a client sends a that must be completed in order. In each exchange a client sends a
request message with data and expects a server response message with request message with data and expects a server response message with
data. Requests and responses are containined in extension fields, data. Requests and responses are contained in extension fields, one
one request or response in each field, as described later. An NTP request or response in each field, as described later. An NTP packet
packet can contain one request message and one or more response can contain one request message and one or more response messages.
messages. Following is a list of these messages. Following is a list of these messages.
o Parameter exchange. The request includes the client host name; o Parameter exchange. The request includes the client host name and
the response one contains the server host name and status word. status word; the response includes the server host name and status
The status word specifies the digest/signature scheme it will use word. The status word specifies the digest/signature scheme to
and the identity schemes it supports. use and the identity schemes supported.
o Certificate exchange. The request includes the subject name of a o Certificate exchange. The request includes the subject name of a
certificate; the response consists of a signed certificate with certificate; the response consists of a signed certificate with
that subject name. If the the issuer name is not the same as the that subject name. If the issuer name is not the same as the
subject name, it has been signed by a host one step closer to a subject name, it has been signed by a host one step closer to a
trusted host and certificate retrieval continues for the issuer trusted host, so certificate retrieval continues for the issuer
name. If it is trusted and self-signed, the trail concludes at name. If it is trusted and self-signed, the trail concludes at
the trusted host. If nontrusted and self-signed, the host the trusted host. If nontrusted and self-signed, the host
certificate has not yet been signed, so the trail temporarily certificate has not yet been signed, so the trail temporarily
loops. Completion of this exchange lights the VAL bit as loops. Completion of this exchange lights the VAL bit as
described below. described below.
o Indentity exchange. The certificate trail is generally not o Identity exchange. The certificate trail is generally not
considered sufficient protection against middleman attacks unless considered sufficient protection against middleman attacks unless
additional protection such as described inor proof-of-possession additional protection such as the proof-of-possession scheme
scheme in [8] is available, but this is expensive and requires described in [RFC2875] is available, but this is expensive and
servers to retain state. Autokey can use one of the challenge/ requires servers to retain state. Autokey can use one of the
response identity schemes described in Appendix B. Completion of challenge/response identity schemes described in Appendix B.
this exchange lights the IFF bit as described below. Completion of this exchange lights the IFF bit as described below.
o Cookie exchange. The request includes the public key of the o Cookie exchange. The request includes the public key of the. The
client. THe response includes the server cookie encrypted with response includes the server cookie encrypted with this key. The
thise key. The client uses this value when constructing the key client uses this value when constructing the key list. Completion
list. Completion of this exchange lights the CKY bit as described of this exchange lights the COOK bit as described below.
below.
o Autokey exchange. The request includes either no data or the o Autokey exchange. The request includes either no data or the
autokey values of the peer in symmetric modes. The response autokey values in symmetric modes. The response includes the
includes the autiokey values of the server or peer. These values autokey values of the server. These values are used to verify the
are used to verify the autokey sequence. Completion of this autokey sequence. Completion of this exchange lights the AUT bit
exchange lights the AUT bit as described below. as described below.
o Sign exchange. This exchange is executed only when the client has o Sign exchange. This exchange is executed only when the client has
synchronized to a proventic source. The request includes the synchronized to a proventic source. The request includes the
self-signed client certificate. The server acting as CA self-signed client certificate. The server acting as CA
interprets the certificate as a X.509v3 certificate request. It interprets the certificate as a X.509v3 certificate request. It
extracts the subject, issuer, and extension fields, builds a new extracts the subject, issuer, and extension fields, builds a new
certificate with these data along with its own serial number and certificate with these data along with its own serial number and
expiration time, then signs it using its own public key and expiration time, then signs it using its own public key and
includes it in the response. The client uses the signed includes it in the response. The client uses the signed
certificate in its own role as server for dependent clients. certificate in its own role as server for dependent clients.
Completion of this exchange lights the SGN bit as described below. Completion of this exchange lights the SIGN bit as described
below.
o Leapseconds exchange. This exchange is executed only when the o Leapseconds exchange. This exchange is executed only when the
client has synchronized to a proventic source. This exchange client has synchronized to a proventic source. This exchange
occurs when the server has the leapseconds values, as indicated in occurs when the server has the leapseconds values, as indicated in
the host status word. If so, the client requests the values and the host status word. If so, the client requests the values and
compares them with its own values, if available. If the server compares them with its own values, if available. If the server
values are newer than the client values, the client replaces its values are newer than the client values, the client replaces its
own with the server values. The client, acting as server, can now own with the server values. The client, acting as server, can now
provide the most recent values to its dependent clients. In provide the most recent values to its dependent clients. In
symmetric mode, this results in both peers having the newest symmetric mode, this results in both peers having the newest
values. Completion of this exchange lights the LPT bit as values. Completion of this exchange lights the LPT bit as
described below. described below.
Once the certificates and identity have been validated, subsequent Once the certificates and identity have been validated, subsequent
packets are validated by digital signatures and autokey sequences. packets are validated by digital signatures and the autokey sequence.
The association is now proventic with respect to the downstratum The association is now proventic with respect to the downstratum
trusted host, but in not yet selectable to discipline the system trusted host, but is not yet selectable to discipline the system
clock. The associations accumulate time values and the mitigation clock. The associations accumulate time values and the mitigation
algorithms continue in the usual way. When these algorithms have algorithms continue in the usual way. When these algorithms have
culled the falsetickers and cluster outlyers and at least three culled the falsetickers and cluster outlyers and at least three
survivors remain, the system clock has been synchronized to a survivors remain, the system clock has been synchronized to a
proventic sourc. proventic source.
The time values for truechimer sources form a proventic partial The time values for truechimer sources form a proventic partial
ordering relative to the applicable signature timestamps. This ordering relative to the applicable signature timestamps. This
raises the interesting issue of how to mitigate between the raises the interesting issue of how to 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.
9. Autokey Operations 9. Autokey Operations
The NTP protocol has three principal modes of operation: client/ The NTP protocol has three principal modes of operation: client/
server, symmetric and broadast and each has its own Autokey program, server, symmetric and broadcast and each has its own Autokey program,
or dance. Autokey choreography is designed to be nonintrusive and to or dance. Autokey choreography is designed to be nonintrusive and to
require no additional packets other than for regular NTP operations. require no additional packets other than for regular NTP operations.
The NTP and Autokey protocols operate simultaneously and The NTP and Autokey protocols operate simultaneously and
independently. When the dance is complete, subsequent packets are independently. When the dance is complete, subsequent packets are
validated by the autokey sequence and thus considered proventic as validated by the autokey sequence and thus considered proventic as
well. Autokey assumes NTP clients poll servers at a relatively low well. Autokey assumes NTP clients poll servers at a relatively low
rate, such as once per minute or slower. In particular, it is rate, such as once per minute or slower. In particular, it assumes
assumed that a request sent at one poll opportunity will normally that a request sent at one poll opportunity will normally result in a
result in a response before the next poll opportunity; however the response before the next poll opportunity; however the protocol is
protocol is robust against a missed or duplicate response. robust against a missed or duplicate response.
The server dance was suggested by Steve Kent over lunch some time The server dance was suggested by Steve Kent over lunch some time
ago, but considerably modified since that meal. The server keeps no ago, but considerably modified since that meal. The server keeps no
state for each client, but uses a fast algorithm and a 32-bit random state for each client, but uses a fast algorithm and a 32-bit random
private value (server seed) to regenerate the cookie upon arrival of private value (server seed) to regenerate the cookie upon arrival of
a client packet. The cookie is calculated as the first 32 bits of a client packet. The cookie is calculated as the first 32 bits of
the autokey computed from the client and server addresses, key ID the autokey computed from the client and server addresses, key ID
zero and the server seed as cookie. The cookie is used for the zero and the server seed as cookie. The cookie is used for the
actual autokey calculation by both the client and server and is thus actual autokey calculation by both the client and server and is thus
specific to each client separately. specific to each client separately.
skipping to change at page 21, line 19 skipping to change at page 21, line 19
verifies further server packets using the autokey sequence. verifies further server packets using the autokey sequence.
The symmetric dance is similar to the server dance and requires only The symmetric dance is similar to the server dance and requires only
a small amount of state between the arrival of a request and a small amount of state between the arrival of a request and
departure of the response. The key list for each direction is departure of the response. The key list for each direction is
generated separately by each peer and used independently, but each is generated separately by each peer and used independently, but each is
generated with the same cookie. The cookie is conveyed in a way generated with the same cookie. The cookie is conveyed in a way
similar to the server dance, except that the cookie is a simple similar to the server dance, except that the cookie is a simple
nonce. There exists a possible race condition where each peer sends nonce. There exists a possible race condition where each peer sends
a cookie request before receiving the cookie response from the other a cookie request before receiving the cookie response from the other
peer. In this case, each peer winds up with two values, one it peer. In this case each peer winds up with two values, one it
generated and one the other peer generated. The ambiguity is generated and one the other peer generated. The ambiguity is
resolved simply by computing the working cookie as the EXOR of the resolved simply by computing the working cookie as the EXOR of the
two values. two values.
Once the autokey dance has completed, it is normally dormant. In all Once the autokey dance has completed, it is normally dormant. In all
except the broadcast dance, packets are normally sent without except the broadcast dance, packets are normally sent without
extension fields, unless the packet is the first one sent after extension fields, unless the packet is the first one sent after
generating a new key list or unless the client has requested the generating a new key list or unless the client has requested the
cookie or autokey values. If for some reason the client clock is cookie or autokey values. If for some reason the client clock is
stepped, rather than slewed, all cryptographic and time values for stepped, rather than slewed, all cryptographic and time values for
skipping to change at page 21, line 50 skipping to change at page 21, line 50
included in a packet, but only one request. A response is generated included in a packet, but only one request. A response is generated
for every request, even if the requestor is not synchronized to a for every request, even if the requestor is not synchronized to a
proventic source, but most contain meaningful data only if the proventic source, but most contain meaningful data only if the
responder is synchronized to a proventic source. Some requests and responder is synchronized to a proventic source. Some requests and
most responses carry timestamped signatures. The signature covers most responses carry timestamped signatures. The signature covers
the entire extension field, including the timestamp and filestamp, the entire extension field, including the timestamp and filestamp,
where applicable. Only if the packet passes all extension field where applicable. Only if the packet passes all extension field
tests are cycles spent to verify the signature. tests are cycles spent to verify the signature.
There are currently eight Autokey requests and eight corresponding There are currently eight Autokey requests and eight corresponding
responses. The NTP packet format is described in [1] and the responses. The NTP packet format is described in
extension field format used for these messages is illustrated in [I-D.ietf-ntp-ntpv4-proto] and the extension field format used for
Figure 7. these messages is illustrated in Figure 7.
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 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 | | Field Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Association ID | | Association ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Timestamp | | Timestamp |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Filestamp | | Filestamp |
skipping to change at page 22, line 43 skipping to change at page 22, line 44
Figure 7: NTPv4 Extension Field Format Figure 7: NTPv4 Extension Field Format
Each extension field is zero-padded to a 4 octet boundary. The Each extension field is zero-padded to a 4 octet boundary. The
Length field covers the entire extension field, including the Length Length field covers the entire extension field, including the Length
and Padding fields. While the minimum field length is 8 octets, a and Padding fields. While the minimum field length is 8 octets, a
maximum field length remains to be established. The reference maximum field length remains to be established. The reference
implementation discards any packet with a field length more than 1024 implementation discards any packet with a field length more than 1024
octets. octets.
If an extension field is present, the parser examines the Length The extension field parser initializes a pointer to the first octet
field. If the length is less than 4 or not a multiple of 4, a format beyond the NTP header fields and calculates the number of octets
error has occurred and the packet is discarded; otherwise, the parser remaining in the packet. If this value is 20 the remaining data are
increments the pointer by the length value. The parser now uses the the MAC and parsing is complete. If greater than 20 an extension
same rules as above to determine whether a MAC is present and/or field is present. 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 lengthuses uses
the same rules as above to determine whether a MAC is present or
another extension field. another extension field.
The 8-bit Code field specifies the request or response operation, The 8-bit Code field specifies the request or response operation,
while the 4-bit Version Number (VN) field is 2 for the current 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 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 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 presently unused and should be set to 0. The remaining fields will
be described later. be described later.
In the most common protocol operations, a client sends a request to a In the most common protocol operations, a client sends a request to a
skipping to change at page 23, line 27 skipping to change at page 23, line 30
server as a handle for subsequent exchanges. If for some reason 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 association ID value in a request does not match the association ID
of any mobilized association, the server returns the request with of any mobilized association, the server returns the request with
both the R and E bits lit. Note that it is not necessarily a both the R and E bits lit. Note that it is not necessarily a
protocol error to send an unsolicited response with no matching protocol error to send an unsolicited response with no matching
request. request.
In some cases not all fields may be present. For requests, until a In some cases not all fields may be present. For requests, until a
client has synchronized to a proventic source, signatures are not client has synchronized to a proventic source, signatures are not
valid. In such cases the Timestamp and Signature Length fields are 0 valid. In such cases the Timestamp and Signature Length fields are 0
and the Signature field is empty. Responses are generated only when and the Signature field is empty. Some request and error response
the responder has synchronized to a proventic source; otherwise, an
error response message is sent. Some request and error response
messages carry no value or signature fields, so in these messages messages carry no value or signature fields, so in these messages
only the first two words are present. only the first two words are present.
The Timestamp and Filestamp words carry the seconds field of an NTP The Timestamp and Filestamp words carry the seconds field of an NTP
timestamp. The Timestamp field establishes the signature epoch of timestamp. The timestamp establishes the signature epoch of the data
the data field in the message, while the filestamp establishes the field in the message, while the filestamp establishes the generation
generation epoch of the file that ultimately produced the data that epoch of the file that ultimately produced the data that is signed.
is signed. A signature and timestamp are valid only when the signing A signature and timestamp are valid only when the signing host is
host is synchronized to a proventic source; otherwise, the timestamp synchronized to a proventic source; otherwise, the timestamp is zero.
is zero. A cryptographic data file can only be generated if a A cryptographic data file can only be generated if a signature is
signature is possible; otherwise, the filestamp is zero, except in possible; otherwise, the filestamp is zero, except in the ASSOC
the ASSOC response message, where it contains the server status word. response message, where it contains the server status word.
Unless specified otherwise in the descriptions to follow, the data As in all other TIP/IP protocol designs, all data are sent in network
referred to are stored in the Value field. byte order. Unless specified otherwise in the descriptions to
follow, the data referred to are stored in the Value field.
10.1. No-Operation 10.1. No-Operation
A No-operation request (Field Type = 0) does nothing except return an A No-operation request (Field Type 0) does nothing except return an
empty response which can be used as a crypto-ping. empty response which can be used as a crypto-ping.
10.2. Association Message (ASSOC) 10.2. Association Message (ASSOC)
An Association Message (Field Type = 1) is used in the parameter An Association Message (Field Type 1) is used in the parameter
exchange to obtain the host name and status word. The request exchange to obtain the host name and status word. The request
contains the client status word in the Filestamp field and the host contains the client status word in the Filestamp field and the
name in the Value field. The response contains the server status Autokey host name in the Value field. The response contains the
word in the Filestamp field and the host name in the Value field. By server status word in the Filestamp field and the Autokey host name
default the host name is the string returned by the Unix in the Value field. The Autokey host name is not necessarily the DNS
gethostname() library function. While minimum and maximum host name host name. A valid response lights the ENAB bit and possibly others
lengths remain to be established, the reference implementation uses in the association status word.
the values 4 and 256, respectively.
When multiple identity schemes are supported, the status words When multiple identity schemes are supported, the host status word
determine which one is used. The request message contains bits determine which ones are available. In server and symmetric modes
corresponding to the schemes the client supports, while the response the response status word contains bits corresponding to the supported
message contains bits corresponding to the schemes the server schemes. In all modes the scheme is selected based on the client
supports. The server and client do an AND operation on the status identity parameters which are loaded at startup.
words to select compatible identity schemes. If multiple schemes
result, the bits are ranked from right to left.
10.3. Certificate Message (CERT) 10.3. Certificate Message (CERT)
A Certificate Message (Field Type = 2) is used in the certificate A Certificate Message (Field Type 2) is used in the certificate
exchange to obtain a certificate by name. The request contains the exchange to obtain a certificate by subject name. The request
subject name; the response contains the certificate encoded in X.509 contains the subject name; the response contains the certificate
format with ASN.1 syntax as described in Appendix C. encoded in X.509 format with ASN.1 syntax as described in Appendix H.
If the subject name in the response does not match the issuer name, If the subject name in the response does not match the issuer name,
the exchange continues with the issuer name replacing the subject the exchange continues with the issuer name replacing the subject
name in the request. The exchange continues until a trusted, self- name in the request. The exchange continues until a trusted, self-
signed certificate is found. signed certificate is found and lights the CERT bit in the
association status word.
10.4. Cookie Message (COOKIE) 10.4. Cookie Message (COOKIE)
The Cookie Message (Field Type = 3) is used in server and symmetric The Cookie Message (Field Type 3) is used in server and symmetric
modes to obtain the server cookie. The request contains the host modes to obtain the server cookie. The request contains the host
public key encoded with ASN.1 syntax as described in Appendix C. The public key encoded with ASN.1 syntax as described in Appendix H. The
response contains the cookie encrypted by the public key in the response contains the cookie encrypted by the public key in the
request. request. A valid response lights the COOKIE bit in the associaton
status word.
10.5. Autokey Message (AUTO) 10.5. Autokey Message (AUTO)
The Autokey Message (Field Type = 4) is used to obtain the autokey The Autokey Message (Field Type 4) is used to obtain the autokey
values. The request contains no value. The response contains two values. The request contains no value for a client or the autokey
32-bit words in network byte order. The first word is the final key values for a symmetric peer. The response contains two 32-bit words,
ID, while the second is the index of the final key ID. the first is the final key ID, while the second is the index of the
final key ID. A valid response lights the AUTO bit in the
association status word.
10.6. Leapseconds Values Message (LEAP) 10.6. Leapseconds Values Message (LEAP)
The Leapseconds Values Message (Field Type = 5) is used to obtain the The Leapseconds Values Message (Field Type 5) is used to obtain the
leapseconds values as parsed from the leapseconds table from NIST. leapseconds values as parsed from the leapseconds table from NIST.
The request and response messages have the same format, except that The request contains no values. The response contains three 32-bit
the R bit is set to 0 in the request and set to 1 in the response. integers: first the NTP seconds of the latest leap event followed by
Both the request and response contains three 32-bit integers, the NTP the NTP seconds when the latest NIST table expires and then the TAI
seconds of the latest leap event followed by the NTP seconds when the offset following the leap event. A valid response lights the LEAP
latest NIST table expires and then the TAI offset following the leap bit in the association status word.
event.
10.7. Sign Message (SIGN) 10.7. Sign Message (SIGN)
The Sign Message (Field Type = 6) requests the server to sign and The Sign Message (Field Type 6) requests the server to sign and
return a certificate presented in the request. The request contains return a certificate presented in the request. The request contains
the client certificate encoded in X.509 format with ASN.1 syntax as the client certificate encoded in X.509 format with ASN.1 syntax as
described in Appendix C. The response contains the client described in Appendix H. The response contains the client
certificate signed by the server private key. certificate signed by the server private key. A valid response
lights the SIGN bit in the association status word.
10.8. Identity Messages (IFF, GQ, MV) 10.8. Identity Messages (IFF, GQ, MV)
The Identity Messages (Field Type = 7 (IFF), 8 (GQ), or 9 (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 contains the client challenge, usually a 160- or 512-bit nonce. The
response contains the result of the mathematical operation defined in response contains the result of the mathematical operation defined in
Appendix B. The Response is encoded in ASN.1 syntax as described in Appendix B. The Response is encoded in ASN.1 syntax as described in
Appendix C. Appendix H. A valid responselights the VRFY bit in the association
status word.
11. Autokey State Machine 11. Autokey State Machine
This section describes the formal model of the Autokey state machine, This section describes the formal model of the Autokey state machine,
its state variables and the state transition functions. its state variables and the state transition functions.
11.1. Status Word 11.1. Status Word
Each server and client operating also as a server implements a host The server implements a host status word, while each client
status word, while each client implements an association status word implements an association status word. These words have the format
for each server. Both words have the format and content shown in and content shown in Figure 8. The low order 16 bits of the status
Figure 8. The low order 16 bits of the status word define the state word define the state of the Autokey dance, while the high order 16
of the Autokey protocol, while the high order 16 bits specify the bits specify the message digest/signature encryption scheme as
message digest/signature encryption scheme as encoded in the OpenSSL encoded in the OpenSSL library. Bits 24-31 are reserved for server
library. Bits 24-31 of the status word are reserved for server use, use, while bits 16-23 are reserved for client use. In the host
while bits 16-23 are reserved for client association use. In the portion bits 24-27 specify the available identity schemes, while bits
host portion bits 24-27 specify the available identity schemes, while 28-31 specify the server capabilities. There are two additional bits
bits 28-31 specify the server capabilities. There are two additional 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 bits as the dance proceeds. Once enabled,
enabled, these bits never come dark unless a general reset occurs and these bits ordinarily never come dark unless a general reset occurs
the protocol is restarted from the beginning. The status bits are and the protocol is restarted from the beginning.
defined as follows:
o ENB (31) - Lit if the server implements the Autokey protocol The host status bits are defined as follows:
o LPF (30) - Lit if the server has loaded leapseconds values o ENAB (31) Lit if the server implements the Autokey protocol.
o IDN (24-27) - These four bits select which identity scheme is in o LVAL (30) Lit if the server has installed leapseconds values,
use. While specific coding for various schemes is yet to be either from the NIST leapseconds file or from another server.
determined, the schemes available in the reference implementation
and described in Appendix B include the following:
* 0x0 Trusted Certificate (TC) Scheme (default) o Bits (28-29) are reserved - always dark.
* 0x1 Private Certificate (PC) Scheme o Bits 24-27 select which server identity schemes are available.
While specific coding for various schemes is yet to be determined,
the schemes available in the reference implementation and
described in Appendix B include the following:
* 0x2 Schnorr aka Identify-Friendly-or-Foe (IFF) Scheme * none - Trusted Certificate (TC) Scheme (default).
* 0x4 Guillard-Quisquater (GC) Scheme * PC (27) Private Certificate Scheme.
* 0x8 Mu-Varadharajan (MV) Scheme * IFF (26) Schnorr aka Identify-Friendly-or-Foe Scheme.
The PC scheme is exclusive of any other scheme. Otherwise, the IFF, * GQ (25) Guillard-Quisquater Scheme.
GQ and MV bits can be enabled in any combination.
* MV (24) Mu-Varadharajan Scheme.
o The PC scheme is exclusive of any other scheme. Otherwise, the
IFF, GQ and MV bits can be enabled in any combination.
The association status bits are defined as follows: The association status bits are defined as follows:
o VAL (0x0100) - Lit when the server certificate and public key are o CERT (23) Lit when the trusted host certificate and public key are
validated. validated.
o IFF (0x0200) - Lit when the server identity credentials are o VRFY (22) Lit when the trusted host identity credentials are
confirmed. confirmed.
o PRV (0x0400) - Lit when the server signature is verified using the o PROV (21) Lit when the server signature is verified using its
public key and identity credentials. Also called the proventic public key and identity credentials. Also called the proventic
bit elsewhere in this memo. When enabled, signed values in bit elsewhere in this memo. When enabled, signed values in
subsequent messages are presumed proventic. subsequent messages are presumed proventic.
o CKY (0x0800) - Lit when the cookie is received and validated. o COOK (20) Lit when the cookie is received and validated. When
When enabled, key lists with nonzero cookies can be generated. lit, key lists with nonzero cookies are generated; when dim, the
cookie is zero.
o AUT (0x1000) - Lit when the autokey values are received and o AUTO (19) Lit when the autokey values are received and validated.
validated. When enabled, clients can validate packets without When lit, clients can validate packets without extension fields
extension fields according to the autokey sequence. according to the autokey sequence.
o SGN (0x2000) - Lit when the host certificate is signed by the o SIGN (18) Lit when the host certificate is signed by the server.
server.
o LPT (0x4000) - Lit when the leapseconds values are received and o LEAP (17) Lit when the leapseconds values are received and
validated. validated.
There are four additional status bits LST and SYN not included in the o Bit 16 is reserved - always dark.
status word. LST is a client propertie, while SYN is a host
property. LST is lit when the key list is regenerated and signed and There are three additional bits: LIST, SYNC and PEER not included in
DIM when the autokey values have been transmitted. This is necessary the association status word. LIST is lit when the key list is
to avoid livelock under some conditions. SYN is lit when the client regenerated and dim when the autokey values have been transmitted.
has synchronized to a proventic source and never dim after that. This is necessary to avoid livelock under some conditions. SYNC is
lit when the client has synchronized to a proventic source and never
dim after that. PEER is lit when the server has synchronized, as
indicated in the NTP header, and never dim after that.
11.2. Host State Variables 11.2. Host State Variables
Following is a list of state variables used by the server protocol. Following is a list of host state variables.
o Host Name - The name of the host, by default the string returned Host Name - The name of the host, by default the string returned by
by the Unix gethostname() library function. the Unix gethostname() library function. In the reference
implementation this is a configurable value.
o Host Status Word - This word is initialized when the host first Host Status Word - This word is initialized when the host first
starts up. The format is described above. starts up. The format is described above.
o Host Key - The RSA public/private key pair used to encrypt/decrypt 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/ 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 Sign Digest - The message digest algorithm used to compute the
signature before encryption. message digest before encryption.
o IFF Parameters - The parameters used in the optional IFF identity IFF Parameters - The parameters used in the optional IFF identity
scheme described in Appendix B. scheme described in Appendix B.
o GQ Parameters - The parameters used in the optional GQ identity GQ Parameters - The parameters used in the optional GQ identity
scheme described in Appendix B. scheme described in Appendix B.
o MV Parameters - The parameters used in the optional MV identity MV Parameters - The parameters used in the optional MV identity
scheme described in Appendix B. scheme described in Appendix B.
o Server Seed - The private value hashed with the IP addresses to Server Seed - The private value hashed with the IP addresses and key
construct the cookie. identifier to construct the cookie.
o Certificate Information Structure (CIS) - Certificates are used to
construct certificate information structures (CIS) which are
stored on the certificate cache. The structure includes certain
information fields from an X.509v3 certificate, together with the
certificate itself encoded in ASN.1 syntax. Each structure
carries the public value timestamp and the filestamp of the
certificate file where it was generated. Elsewhere in this memo
the CIS will not be distinguished from the certificate unless
noted otherwise. A flags field in the CIS determines the status
of the certificate. The field is encoded as follows:
* TRST (0x01) - The certificate has been signed by a trusted Certificate Information Structure (CIS) - This structure includes
issuer. If the certificate is self-signed and contains certain information fields from an X.509v3 certificate, together with
"trustRoot" in the Extended Key Usage field, this bit is lit the certificate itself. The fields extracted include the subject and
when the CIS is constructed issuer names, subject public key and message digest algorithm
(pointers), and the beginning and end of the valid period in NTP
seconds.
* SIGN (0x02) - The certificate signature has been verified. If The certificate itself is stored as an extension field in network
the certificate is self-signed and verified using the contained byte order so it can be copied intact to the message. The structure
public key, this bit is lit when the CIS is constructed. is signed using the sign key and carries the public values timestamp
at signature time and the filestamp of the original certificate file.
The structure is used by the CERT response message and SIGN request
and response messages.
* VALD (0x04) - The certificate is valid and can be used to A flags field in the CIS determines the status of the certificate.
verify signatures. This bit is lit when a trusted certificate The field is encoded as follows:
has been found on a valid certificate trail.
* PRIV (0x08) - The certificate is private and not to be o TRUST (0x01) - The certificate has been signed by a trusted
revealed. If the certificate is self-signed and contains issuer. If the certificate is self-signed and contains
"Private" in the Extended Key Usage field, this bit is lit when "trustRoot" in the Extended Key Usage field, this bit is lit when
the CIS is constructed. the CIS is constructed.
* ERRR (0x80) - The certificate is defective and not to be used o SIGN (0x02) - The certificate signature has been verified. If the
in any way. certificate is self-signed and verified using the contained public
key, this bit is lit when the CIS is constructed.
o Certificate List - CIS structures are stored on the certificate o VALID (0x04) - The certificate is valid and can be used to verify
list in order of arrival, with the most recently received CIS signatures. This bit is lit when a trusted certificate has been
placed first on the list. The list is initialized with the CIS found on a valid certificate trail.
for the host certificate, which is read from the certificate file.
Additional CIS entries are pushed on the list as certificates are
obtained from the servers during the certificate exchange. CIS
entries are discarded if overtaken by newer ones or expire due to
old age.
o Host Certificate - The self-signed X.509v3 certificate for the o PRIV (0x08) - The certificate is private and not to be revealed.
host. The subject and issuer fields consist of the host name, If the certificate is self-signed and contains "Private" in the
while the message digest/signature encryption scheme consists of Extended Key Usage field, this bit is lit when the CIS is
the sign key and message digest defined above. Optional constructed.
information used in the identity schemes is carried in X.509v3
extension fields compatible with [10].
o Public Key Values - The public encryption key for the COOKIE o ERROR (0x80) - The certificate is defective and not to be used in
request, which consists of the public value of the host key. It any way.
carries the public values timestamp and the filestamp of the host
key file.
o Leapseconds Values. The leapseconds values parsed from the NIST Certificate List - CIS structures are stored on the certificate list
leapseconds file. It carries the public values timestamp and the in order of arrival, with the most recently received CIS placed first
filestamp of the leapseconds values. on the list. The list is initialized with the CIS for the host
certificate, which is read from the host certificate file.
Additional CIS entries are added to the list as certificates are
obtained from the servers during the certificate exchange. CIS
entries are discarded if overtaken by newer ones.
11.3. Client State Variables (all modes) The following values are stored as an extension field structure in
network byte order so they can be copied intact to the message. They
are used to send some Autokey requests and responses. All but the
Host Name Values structure are signed using the sign key and all
carry the public values timestamp at signature time.
Following is a list of state variables used by the client association Host Name Values. This is used to send ASSOC request and response
protocol in all modes. messages. It contains the host status word and host name.
o Association ID - The association ID used in responses. It is Public Key Values - This is used to send the COOKIE request message.
assigned when the association is mobilized It contains the public encryption key used for the COOKIE response
message.
o Server Association ID - The server association ID used in Leapseconds Values. This is used to send the LEAP response message.
requests. It is copied from the first nonzero association ID In contains the leapseconds values in the LEAP message description.
field in a response
o Server Subject Name - The server host name determined in the 11.3. Client State Variables (all modes)
parameter exchange
o Server Issuer Name - The host name signing the certificate. It is Following is a list of state variables used by the various dances in
extracted from the current server certificate upon arrival and all modes.
used to request the next item on the certificate trail
o Association Status Word - The host status word of the server Association ID - The association ID used in responses. It is
determined in the parameter exchange assigned when the association is mobilized.
o Server Public Key - The public key used to decrypt signatures. It Association Status Word - The status word copied from the ASSOC
is extracted from the first certificate received, which by design response; subsequently modified by the state machine.
is the server host certificate
o Server Message Digest - The digest/signature scheme determined in Subject Name - The server host name copied from the ASSOC respones.
the parameter exchange
o Identification Challenge - A 512-bit nonce used in the Issuer Name - The host name signing the certificate. It is extracted
identification exchange from the current server certificate upon arrival and used to request
o Group Key - A set of values used by the identification exchange. the next host on the certificate trail.
It identifies the cryptographic compartment shared by the server
and client
o Receive Cookie Values - The cookie returned in a COOKIE response, Server Public Key - The public key used to decrypt signatures. It is
together with its timestamp and filestamp extracted from the server host certificate.
o Receive Autokey Values - The autokey values returned in an AUTO Server Message Digest - The digest/signature scheme determined in the
response, together with its timestamp and filestamp parameter exchange.
11.4. Server State Variables (broadcast and symmetric modes) Group Key - A set of values used by the identity exchange. It
identifies the cryptographic compartment shared by the server and
client.
Following is a list of server state variables used in broadcast and Receive Cookie Values - The cookie returned in a COOKIE response,
symmetric modes. together with its timestamp and filestamp
o Send Cookie Values - The cookie encryption values, signature and Receive Autokey Values - The autokey values returned in an AUTO
timestamps response, together with its timestamp and filestamp.
o Send Autokey Values - The autokey values, signature and timestamps Send Autokey Values - The autokey values with signature and
timestamps.
o Key List - A sequence of key IDs starting with the autokey seed Key List - A sequence of key IDs starting with the autokey seed and
and each pointing to the next. It is computed, timestamped and each pointing to the next. It is computed, timestamped and signed at
signed at the next poll opportunity when the key list becomes 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 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.
11.5. Protocol State Transitions 11.4. Protocol State Transitions
The protocol state machine is very simple but robust. The state is The protocol state machine is very simple but robust. The state is
determined by the server status bits defined above. The state determined by the client status word bits defined above. The state
transitions of the three dances are shown below. The capitalized transitions of the three dances are shown below. The capitalized
truth values represent the server status bits. All server bits are truth values represent the client status bits. All bits are
initialized dark and are lit upon the arrival of a specific response initialized dark and are lit upon the arrival of a specific response
message, as detailed above. message as detailed above.
11.5.1. Server Dance 11.4.1. Server Dance
The server dance begins when the client sends an ASSOC request to the The server dance begins when the client sends an ASSOC request to the
server. It ends when the first signature is verified and PRV is lit. server. The clock is updated when PREV is lit and the dance ends
Subsequent packets received without extension fields are validated by when LEAP is lit. In this dance the autokey values are not used, so
the autokey sequence. An optional LEAP exchange updates the an autokey exchange is not necessary. Note that the SIGN and LEAP
leapseconds values. Note the order of the identity exchanges and requests are not issued until the client has synchronized to a
that only the first one will be used if multiple schemes are proventic source. Subsequent packets without extension fields are
available. Note also that the SIGN and LEAP requests are not issued validated by the autokey sequence. This example and others assumes
until the client has synchronized to a proventic source. the IFF identity scheme has been selected in the parameter exchange..
while (1) { 1 while (1) {
wait_for_next_poll; 2 wait_for_next_poll;
make_NTP_header; 3 make_NTP_header;
if (response_ready) 4 if (response_ready)
send_response; 5 send_response;
if (!ENB) 6 if (!ENB) /* parameter exchange */
/ * parameters exchange */ 7 ASSOC_request;
ASSOC_request; 8 else if (!CERT) /* certificate exchange */
else if (!VAL) 9 CERT_request(Host_Name);
/* certificate exchange */ 10 else if (!IFF) /* identity exchange */
CERT_request(Host_Name); 11 IFF_challenge;
else if (IDN & GQ && !IFF) 12 else if (!COOK) /* cookie exchange */
/* GQ identity exchange */ 13 COOKIE_request;
GQ_challenge; 14 else if (!SYNC) /* wait for synchronization */
else if (IDN & IFF && !IFF) 15 continue;
/* IFF identity exchange */ 16 else if (!SIGN) /* sign exchange */
IFF_challenge; 17 SIGN_request(Host_Certificate);
else if (!IFF) 18 else if (!LEAP) /* leapsecond values exchange */
/* TC identity exchange */ 19 LEAP_request;
CERT_request(Issuer_Name); 20 send packet;
else if (!CKY) 21 }
/* cookie exchange */
COOKIE_request;
else if (SYN && !SIG)
/* signe exchange */
SIGN_request(Host_Certificate);
else if (SYN && LPF & !LPT)
/* leapseconds exchange */
LEAP_request;
} Figure 9: Server Dance
When the PC identity scheme is in use, the ASSOC response sets VAL, If the server refreshes the private seed, the cookie becomes invalid.
IFF, and SIG to 1; the COOKIE response sets CKY and AUT to 1; and the The server responds to an invalid cookie with a crypto_NAK message,
first valid signature sets PRV to 1. which causes the client to restart the protocol from the beginning.
11.5.2. Broadcast Dance 11.4.2. Broadcast Dance
The only difference between the broadcast and server dances is the The broadcast dance is similar to the server dance with the cookie
inclusion of an autokey values exchange following the cookie exchange replaced by the autokey values exchange. The broadcast
exchange. The broadcast dance begins when the client receives the dance begins when the client receives a broadcast packet including an
first broadcast packet, which includes an ASSOC response with ASSOC response with the server association ID. This mobilizes a
association ID. The broadcast client uses the association ID to client ssociation in order to proventicate the source and calibrate
initiate a server dance in order to calibrate the propagation delay. the propagation delay. The dance ends when the LEAP bit is lit,
after which the client sends no further packets. Normally, the
broadcast server includes an ASSOC response in each transmitted
packet. However, when the server generates a new key list, it
includes an AUTO response instead.
The dance ends when the first signature is verified and PRV is lit. In the broadcast dance extension fields are used with every packet,
Subsequent packets received without extension fields are validated by so the cookie is always zero and no cookie exchange is necessary. As
the autokey sequence. An optional LEAP exchange updates the in the server dance, the clock is updated when PREV is lit and the
leapseconds values. When the server generates a new key list, the dance ends when LEAP is lit. Note that the SIGN and LEAP requests
server replaces the ASSOC response with an AUTO response in the first are not issued until the client has synchronized to a proventic
packet sent. source. Subsequent packets without extension fields are validated by
the autokey sequence.
while (1) { 1 while (1) {
wait_for_next_poll; 2 wait_for_next_poll;
make_NTP_header; 3 make_NTP_header;
if (response_ready) 4 if (response_ready)
send_response; 5 send_response;
if (!ENB) 6 if (!ENB) /* parameters exchange */
/* parameters exchange */ 7 ASSOC_request;
ASSOC_request; 8 else if (!CERT) /* certificate exchange */
else if (!VAL) 9 CERT_request(Host_Name);
/* certificate exchange */ 10 else if (!IFF) /* identity exchange */
CERT_request(Host_Name); 11 IFF_challenge;
else if (IDN & GQ && !IFF) 12 else if (!AUT) /* autokey values exchange */
/* GQ identity exchange */ 13 AUTO_request;
GQ_challenge; 14 else if (!SYNC) /* wait for synchronization */
else if (IDN & IFF && !IFF) 15 continue;
/* IFF identity exchange */ 16 else if (!SIGN) /* sign exchange */
IFF_challenge; 17 SIGN_request(Host_Certificate);
else if (!IFF) 18 else if (!LEAP) /* leapsecond values exchange */
/* TC identity exchange */ 19 LEAP_request;
CERT_request(Issuer_Name); 20 send NTP_packet;
else if (!CKY) 21 }
/* cookie exchange */
COOKIE_request;
else if (!AUT)
/* autokey values exchange */
AUTO_request;
else if (SYN &&! SIG)
/* sign exchange */
SIGN_request(Host_Certificate);
else if (SYN && LPF & !LPT)
/* leapseconds exchange */
LEAP_request;
}
When the PC identity scheme is in use, the ASSOC response lights VAL, Figure 10: Server Dance
IFF, and SIG; the COOKIE response lights CKY and AUT; and the first
valid signature lights PRV.
11.5.3. Symmetric Dance If a packet is lost and the autokey sequence is broken, the client
hashes the current autokey until either it matches the previous
autokey or the number of hashes exceeds the count given in the
autokey values. If the latter, the client sends an AUTO request to
retrive the autokey values. If the client receives a crypto-NAK
during the dance, or if the association ID changes, the client
restarts the protocol from the beginning.
11.4.3. Symmetric Dance
The symmetric dance is intricately choreographed. It begins when the The symmetric dance is intricately choreographed. It begins when the
active peer sends an ASSOC request to the passive peer. The passive active peer sends an ASSOC request to the passive peer. The passive
peer mobilizes an association and both peers step the same dance from peer mobilizes an association and both peers step a three-way dance
the beginning. Until the active peer is synchronized to a proventic where each peer completes a parameter exchange with the other. Until
source (which could be the passive peer) and can sign messages, the one of the peers has synchronized to a proventic source (which could
passive peer loops waiting for the timestamp in the ASSOC response to be the other peer) and can sign messages, the other peer loops
light up. Until then, the active peer dances the server steps, but waiting for a valid timestamp in the ensuing CERT response.
skips the sign, cookie and leapseconds exchanges.
while (1) {
wait_for_next_poll;
make_NTP_header;
if (!ENB)
/* parameters exchange */
ASSOC_request;
else if (!VAL)
/* certificate exchange */
CERT_request(Host_Name);
else if (IDN & GQ && !IFF)
/* GQ identity exchange */
GQ_challenge;
else if (IDN & IFF && !IFF)
/* IFF identity exchange */
IFF_challenge;
else if (!IFF)
/* TC identity exchange */
CERT_request(Issuer_Name);
else if (SYN && !SIG)
/* sign exchange */
SIGN_request(Host_Certificate);
else if (SYN && !CKY)
/* cookie exchange */
COOKIE_request;
else if (!LST)
/* autokey values response */
AUTO_response;
else if (!AUT)
/* autokey values exchange */
AUTO_request;
else if (SYN && LPF & !LPT)
/* leapseconds exchange */
LEAP_request;
}
When the PC identity scheme is in use, the ASSOC response lights VAL,
IFF, and SIG; the COOKIE response lights CKY and AUT; and the first
valid signature lights PRV.
Once the active peer has synchronized to a proventic source, it 1 while (1) {
includes timestamped signatures with its messages. The first thing 2 wait_for_next_poll;
it does after lighting timestamps is dance the sign exchange so that 3 make_NTP_header;
the passive peer can survive the default identity exchange, if 4 if (!ENB) /* parameters exchange */
necessary. This is pretty weird, since the passive peer will find 5 ASSOC_request;
the active certificate signed by its own public key. 6 else if (!CERT) /* certificate exchange */
7 CERT_request(Host_Name);
8 else if (!IFF) /* identity exchange */
9 IFF_challenge;
10 else if (!COOK && PEER) /* cookie exchange */
11 COOKIE_request);
12 else if (!AUTO) /* autokey values exchange */
13 AUTO_request;
14 else if (LIST) /* autokey values response */
15 AUTO_response;
16 else if (!SYNC) /* wait for synchronization */
17 continue;
18 else if (!SIGN) /* sign exchange */
19 SIGN_request;
20 else if (!LEAP) /* leapsecond values exchange */
21 LEAP_request;
22 send NTP_packet;
23 }
The passive peer, which has been stalled waiting for the active Figure 11: Symmetric Dance
timestamps to light up, now mates the dance. The initial value of
the cookie is zero. If a COOKIE response has not been received by
either peer, the next message sent is a COOKIE request. The
recipient rolls a random cookie, lights CKY and returns the encrypted
cookie. The recipient decrypts the cookie and lights CKY. It is not
a protocol error if both peers happen to send a COOKIE request at the
same time. In this case both peers will have two values, one
generated by itself and the other received from the other peer. In
such cases the working cookie is constructed as the EXOR of the two
values.
At the next packet transmission opportunity, either peer generates a Once a peer has synchronized to a proventic source, it includes
new key list and sets LST to 1; however, there may already be an AUTO timestamped signatures in its messages. The other peer, which has
request queued for transmission and the rules say no more than one been stalled waiting for valid timestamps, now mates the dance. It
request in a packet. When available, either peer sends an AUTO retrives the now nonzero cookie using a a cookie exchange and then
response and dims LST. The recipient initializes the autokey values the updated autokey values using an autokey exchange.
and lights LST and AUT. Subsequent packets received without
extension fields are validated by the autokey sequence.
The above description assumes the active peer synchronizes to the As in the broadcasst dance, if a packet is lost and the autokey
passive peer, which itself is synchronized to some other source, such sequence broken, the peer hashes the current autokey until either it
as a radio clock or another NTP server. In this case, the active matches the previous autokey or the number of hashes exceeds tha
peer is operating at a stratum level one greater than the passive count given in the autokey values. If the latter, the client sends
peer and so the passive peer will not synchronize to it unless it an AUTO request to retrive the autokey values. If the peer receives
loses its own sources and the active peer itself has another source. a crypto-NAK during the dance, or if the association ID changes, the
peer restarts the protocol from the beginning.
11.6. Error Recovery 11.5. Error Recovery
The Autokey protocol state machine includes provisions for various The Autokey protocol state machine includes provisions for various
kinds of error conditions that can arise due to missing files, kinds of error conditions that can arise due to missing files,
corrupted data, protocol violations and packet loss or misorder, not corrupted data, protocol violations and packet loss or misorder, not
to mention hostile intrusion. This section describes how the to mention hostile intrusion. This section describes how the
protocol responds to reachability and timeout events which can occur protocol responds to reachability and timeout events which can occur
due to such errors. due to such errors.
A persistent NTP association is mobilized by an entry in the A persistent NTP association is mobilized by an entry in the
configuration file, while an ephemeral association is mobilized upon configuration file, while an ephemeral association is mobilized upon
the arrival of a broadcast, manycast or symmetric active packet with the arrival of a broadcast or symmetric active packet with no
no matching association. Subsequently, a general reset reinitializes matching association. Subsequently, a general reset reinitializes
all association variables to the initial state when first mobilized. all association variables to the initial state when first mobilized.
In addition, if the association is ephemeral, the association is In addition, if the association is ephemeral, the association is
demobilized and all resources acquired are returned to the system. demobilized and all resources acquired are returned to the system.
Every NTP association has two variables which maintain the liveness Every NTP association has two variables which maintain the liveness
state of the protocol, the 8-bit reachability register defined in [7] state of the protocol, the 8-bit reach register and the unreach
and the watchdog timer, which is new in NTPv4. At every poll counter defined in [I-D.ietf-ntp-ntpv4-proto]. At every poll
interval the reachability register is shifted left, the low order bit interval the reach register is shifted left, the low order bit is
is dimmed and the high order bit is lost. At the same time the dimmed and the high order bit is lost. At the same time the unreach
watchdog counter is incremented by one. If an arriving packet passes counter is incremented by one. If an arriving packet passes all
all authentication and sanity checks, the rightmost bit of the authentication and sanity checks, the rightmost bit of the reach
reachability register is lit and the watchdog counter is set to zero. register is lit and the unreach counter is set to zero. If any bit
If any bit in the reachability register is lit, the server is in the reach register is lit, the server is reachable, otherwise it
reachable, otherwise it is unreachable. is unreachable.
When the first poll is sent from an association, the reachability When the first poll is sent from an association, the reach register
register and watchdog counter are zero. If the watchdog counter and unreach counter are set to zero. If the the unreach counter
reaches 16 before the server becomes reachable, a general reset reaches 16, the poll interval is doubled. In addition, if
occurs. This resets the protocol and clears any acquired resources association is persistent, it is demobilized. This reduces the
before trying again. If the server was once reachable and then network load for packets that are unlikely to elicit a response.
becomes unreachable, a general reset occurs. In addition, if the
watchdog counter reaches 16 and the association is persistent, the
poll interval is doubled. This reduces the network load for packets
that are unlikely to elicit a response.
At each state in the protocol the client expects a particular 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.
skipping to change at page 36, line 7 skipping to change at page 35, line 11
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.
2. When a client switches from client mode to broadcast client mode. 2. When the poll interval is changed. In this case the calculated
There is no further need for the key list, since the client will
not transmit again.
3. When the poll interval is changed. In this case the calculated
expiration times for the keys become invalid. expiration times for the keys become invalid.
4. If a problem is detected when an entry is fetched from the key 3. If a problem is detected when an entry is fetched from the key
list. This could happen if the key was marked non-trusted or list. This could happen if the key was marked non-trusted or
timed out, either of which implies a software bug. timed out, either of which implies a software bug.
11.7. Security Considerations 11.6. Security Considerations
This section discusses the most obvious security vulnerabilities in This section discusses the most obvious security vulnerabilities in
the various Autokey dances. In the following discussion the the various Autokey dances. In the following discussion the
cryptographic algorithms and private values themselves are assumed cryptographic algorithms and private values themselves are assumed
secure; that is, a brute force cryptanalytic attack will not reveal secure; that is, a brute force cryptanalytic attack will not reveal
the host private key, sign private key, cookie value, identity the host private key, sign private key, cookie value, identity
parameters, server seed or autokey seed. In addition, an intruder parameters, server seed or autokey seed. In addition, an intruder
will not be able to predict random generator values. will not be able to predict random generator values.
11.8. Protocol Vulnerability 11.7. Protocol Vulnerability
While the protocol has not been subjected to a formal analysis, a few While the protocol has not been subjected to a formal analysis, a few
preliminary assertions can be made. In the client/server and preliminary assertions can be made. In the client/server and
symmetric dances the underlying NTP on-wire protocol is resistant to symmetric dances the underlying NTP on-wire protocol is resistant to
lost, duplicate and bogus packets, even if the clock is not lost, duplicate and bogus packets, even if the clock is not
synchronized, so the protocol is not vulnerable to a wiretapper synchronized, so the protocol is not vulnerable to a wiretapper
attack. A middleman attack, even if it could simulate a valid attack. A middleman attack, even if it could simulate a valid
cookie, could not present a valid signature. cookie, could not present a valid signature.
In the broadcast dance the client begins with a volley in client/ In the broadcast dance the client begins with a volley in client/
server mode to obtain the autokey values and signature, so has the server mode to obtain the autokey values and signature, so has the
same protection as in that mode. When continuing in receive-only same protection as in that mode. When continuing in receive-only
mode, a wiretapper cannot produce a key list with valid signed mode, a wiretapper cannot produce a key list with valid signed
autokey values. The most it can do is replay an old packet causing autokey values. If it replays an old packet, the client will reject
clients to repeat the autokey hash operations until exceeding the it by the timestamp check. The most it can do is manufacture a
maximum key number. future packet causing clients to repeat the autokey hash operations
until exceeding the maximum key number. If this happens the
broadcast client tempoerarily revers to client mode to refresh the
autokey values.
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.
11.9. Clogging Vulnerability 11.8. Clogging Vulnerability
A self-induced clogging incident cannot happen, since signatures are A self-induced clogging incident cannot happen, since signatures are
computed only when the data have changed and the data do not change computed only when the data have changed and the data do not change
very often. For instance, the autokey values are signed only when very often. For instance, the autokey values are signed only when
the key list is regenerated, which happens about once an hour, while the key list is regenerated, which happens about once an hour, while
the public values are signed only when one of them is updated during the public values are signed only when one of them is updated during
a dance or the server seed is refreshed, which happens about once per a dance or the server seed is refreshed, which happens about once per
day. day.
There are two clogging vulnerabilities exposed in the protocol There are two clogging vulnerabilities exposed in the protocol
design: an encryption attack where the intruder hopes to clog the design: an encryption attack where the intruder hopes to clog the
victim server with needless cryptographic calculations, and a victim server with needless cryptographic calculations, and a
decryption attack where the intruder attempts to clog the victim decryption attack where the intruder attempts to clog the victim
client with needless cryptographic calculations. Autokey uses public client with needless cryptographic calculations. Autokey uses public
key cryptography and the algorithms that perform these functions key cryptography and the algorithms that perform these functions
consume significant resources. consume significant resources.
In client/server and peer dances an encryption hazard exists when a In client/server and peer dances an encryption hazard exists when a
wiretapper replays prior cookie request messages at speed. There is wiretapper replays prior cookie request messages at speed. There is
no obvious way to deflect such attacks, as the server retains no no obvious way to deflect such attacks, as the server retains no
state between requests. Replays of cookie response messages are state between requests. Replays of cookie request or response
detected and discarded by the NTP on-wire protocol. messages are detected and discarded by the client on-wire protocol.
In broadcast mode a client a decription hazard exists when a In broadcast mode a client a decryption hazard exists when a
wiretapper replays autokey response messages at speed. Once wiretapper replays autokey response messages at speed. Once
synchronized to a proventic source, a legitimate extension field with synchronized to a proventic source, a legitimate extension field with
timestamp the same as or earlier than the most recently received of timestamp the same as or earlier than the most recently received of
that type is immediately discarded. This foils a middleman cut-and- that type is immediately discarded. This foils a middleman cut-and-
paste attack using an earlier response, for example. A legitimate paste attack using an earlier response, for example. A legitimate
extension field with timestamp in the future is unlikely, as that extension field with timestamp in the future is unlikely, as that
would require predicting the autokey sequence. In either case the would require predicting the autokey sequence. However, this causes
extension field is discarded before expensive signature computations. the client to refresh and verify the autokey values and signature.
This defense is most useful in symmetric mode, but a useful
redundancy in other modes.
An interesting adventure is when an intruder replays a recent packet A determined middleman can modify a recent packet with an intentional
with an intentional bit error. A stateless server will return a bit error. A stateless server will return a crypto-NAK message which
crypto-NAK message which will be discarded by the NTP on-wire will cause the client to perform a general reset. The middleman can
protocol. However, a legitimate crypto-NAK is sent if the server has do other things as well and have nothing to do with Autokey.
just refreshed the server seed. In this case the the client performs
a general reset and restarts the protocol as expected.
12. IANA Considerations 12. IANA Considerations
Any IANA registries needed? Any IANA registries needed?
13. Acknowledgements 13. Acknowledgements
... ...
14. References 14. References
14.1. Normative References 14.1. Normative References
[1] Burbank, J., "Network Time Protocol Version 4 Protocol And [I-D.ietf-ntp-ntpv4-proto]
Algorithms Specification", draft-ietf-ntp-ntpv4-proto-08 (work Burbank, J., "Network Time Protocol Version 4 Protocol And
in progress), November 2007. Algorithms Specification", draft-ietf-ntp-ntpv4-proto-09
(work in progress), February 2008.
14.2. Informative References 14.2. Informative References
[2] Maughan, D., Schneider, M., and M. Schertler, "Internet [DASBUCH] Mills, D., ""Compouter Network Time Synchronization - the
Security Association and Key Management Protocol (ISAKMP)", Network Time Protocol"", 2006.
RFC 2408, November 1998.
[3] Orman, H., "The OAKLEY Key Determination Protocol", RFC 2412, [GUILLOU] Guillou, L. and J. Quisquatar, "A "paradoxical" identity-
November 1998. based signature scheme resulting from zero-knowledge",
1990.
[4] Karn, P. and W. Simpson, "Photuris: Session-Key Management [MV] Mu, Y. and V. Varadharajan, "Robust and secure
Protocol", RFC 2522, March 1999. broadcasting", 2001.
[5] Kent, S. and R. Atkinson, "IP Encapsulating Security Payload [RFC1305] Mills, D., "Network Time Protocol (Version 3)
(ESP)", RFC 2406, November 1998. Specification, Implementation", RFC 1305, March 1992.
[6] Kent, S. and R. Atkinson, "IP Authentication Header", RFC 2402, [RFC2402] Kent, S. and R. Atkinson, "IP Authentication Header",
November 1998. RFC 2402, November 1998.
[7] Mills, D., "Network Time Protocol (Version 3) Specification, [RFC2406] Kent, S. and R. Atkinson, "IP Encapsulating Security
Implementation", RFC 1305, March 1992. Payload (ESP)", RFC 2406, November 1998.
[8] Prafullchandra, H. and J. Schaad, "Diffie-Hellman Proof-of- [RFC2408] Maughan, D., Schneider, M., and M. Schertler, "Internet
Possession Algorithms", RFC 2875, July 2000. Security Association and Key Management Protocol
(ISAKMP)", RFC 2408, November 1998.
[9] Adams, C. and S. Farrell, "Internet X.509 Public Key [RFC2412] Orman, H., "The OAKLEY Key Determination Protocol",
Infrastructure Certificate Management Protocols", RFC 2510, RFC 2412, November 1998.
March 1999.
[10] Housley, R., Polk, W., Ford, W., and D. Solo, "Internet X.509 [RFC2510] Adams, C. and S. Farrell, "Internet X.509 Public Key
Public Key Infrastructure Certificate and Certificate Infrastructure Certificate Management Protocols",
Revocation List (CRL) Profile", RFC 3280, April 2002. RFC 2510, March 1999.
[11] Schnorr, C., "Efficient signature generation for smart cards", [RFC2522] Karn, P. and W. Simpson, "Photuris: Session-Key Management
1991. Protocol", RFC 2522, March 1999.
[12] Stinson, D., "Cryptography - Theory and Practice", 1995. [RFC2875] Prafullchandra, H. and J. Schaad, "Diffie-Hellman Proof-
of-Possession Algorithms", RFC 2875, July 2000.
[13] Guillou, L. and J. Quisquatar, "A "paradoxical" identity-based [RFC3279] Bassham, L., Polk, W., and R. Housley, "Algorithms and
signature scheme resulting from zero-knowledge", 1990. Identifiers for the Internet X.509 Public Key
Infrastructure Certificate and Certificate Revocation List
(CRL) Profile", RFC 3279, April 2002.
[14] Mu, Y. and V. Varadharajan, "Robust and secure broadcasting", [RFC3280] Housley, R., Polk, W., Ford, W., and D. Solo, "Internet
2001. X.509 Public Key Infrastructure Certificate and
Certificate Revocation List (CRL) Profile", RFC 3280,
April 2002.
[15] Mills, D., ""Compouter Network Time Synchronization - the [SCHNORR] Schnorr, C., "Efficient signature generation for smart
Network Time Protocol"", 2006. cards", 1991.
[16] Bassham, L., Polk, W., and R. Housley, "Algorithms and [STINSON] Stinson, D., "Cryptography - Theory and Practice", 1995.
Identifiers for the Internet X.509 Public Key Infrastructure
Certificate and Certificate Revocation List (CRL) Profile",
RFC 3279, April 2002.
Appendix A. Timestamps, Filestamps and Partial Ordering Appendix A. Timestamps, Filestamps and Partial Ordering
When the host starts, it reads the host key and host certificate When the host starts, it reads the host key and host certificate
files, which are required for continued operation. It also reads the files, which are required for continued operation. It also reads the
sign key and leapseconds values, when available. When reading these sign key and leapseconds values, when available. When reading these
files the host checks the file formats and filestamps for validity; files the host checks the file formats and filestamps for validity;
for instance, all filestamps must be later than the time the UTC for instance, all filestamps must be later than the time the UTC
timescale was established in 1972 and the certificate filestamp must timescale was established in 1972 and the certificate filestamp must
not be earlier than its associated sign key filestamp. At the time not be earlier than its associated sign key filestamp. At the time
the files are read the host is not synchronized, so it cannot the files are read the host is not synchronized, so it cannot
determine whether the filestamps are bogus other than these simple determine whether the filestamps are bogus other than these simple
checks. It must not produce filestamps or timestamps until checks. It must not produce filestamps or timestamps until
sunchronized to a proventic source. synchronized to a proventic source.
In the following the relation A --> B is Lamport's "happens before" In the following the relation A --> B is Lamport's "happens before"
relation, which is true if event A happens before event B. When relation, which is true if event A happens before event B. When
timestamps are compared to timestamps, the relation is false if A timestamps are compared to timestamps, the relation is false if A
<--> B; that is, false if the events are simultaneous. For <--> B; that is, false if the events are simultaneous. For
timestamps compared to filestamps and filestamps compared to timestamps compared to filestamps and filestamps compared to
filestamps, the relation is true if A <--> B. Note that the current filestamps, the relation is true if A <--> B. Note that the current
time plays no part in these assertions except in (6) below; however, time plays no part in these assertions except in (6) below; however,
the NTP protocol itself insures a correct partial ordering for all the NTP protocol itself insures a correct partial ordering for all
current time values. current time values.
skipping to change at page 41, line 10 skipping to change at page 40, line 12
recommended for general use. The TC scheme uses a certificate trail, recommended for general use. The TC scheme uses a certificate trail,
but not an identity scheme. The IFF, GQ and MV identity schemes use but not an identity scheme. The IFF, GQ and MV identity schemes use
a cryptographically strong challenge-response exchange where an a cryptographically strong challenge-response exchange where an
intruder cannot learn the group key, even after repeated observations intruder cannot learn the group key, even after repeated observations
of multiple exchanges. These schemes begin when the client sends a of multiple exchanges. These schemes begin when the client sends a
nonce to the server, which then rolls its own nonce, performs a nonce to the server, which then rolls its own nonce, performs a
mathematical operation and sends the results to the client. The mathematical operation and sends the results to the client. The
client performs a second mathematical operation to prove the server client performs a second mathematical operation to prove the server
has the same group key as the client. has the same group key as the client.
B.1. Private Certificate (PC) Scheme Appendix C. Private Certificate (PC) Scheme
The PC scheme shown in Figure Figure 12 uses a private certificate as The PC scheme shown in Figure Figure 12 uses a private certificate as
the group key. the group key.
Trusted Trusted
Authority Authority
Secure +-------------+ Secure Secure +-------------+ Secure
+--------------| Certificate |-------------+ +--------------| Certificate |-------------+
| +-------------+ | | +-------------+ |
| | | |
skipping to change at page 41, line 36 skipping to change at page 40, line 38
Figure 12: Private Certificate (PC) Identity Scheme Figure 12: Private Certificate (PC) Identity Scheme
A certificate is designated private when the X509v3 Extended Key A certificate is designated private when the X509v3 Extended Key
Usage extension field is present and contains "Private". The private Usage extension field is present and contains "Private". The private
certificate is distributed to all other group members by secret certificate is distributed to all other group members by secret
means, so in fact becomes a symmetric key. Private certificates are means, so in fact becomes a symmetric key. Private certificates are
also trusted, so there is no need for a certificate trail or identity also trusted, so there is no need for a certificate trail or identity
scheme. scheme.
B.2. Trusted Certificate (TC) Scheme Appendix D. Trusted Certificate (TC) Scheme
All other schemes involve a conventional certificate trail as shown All other schemes involve a conventional certificate trail as shown
in Figure Figure 13. in Figure Figure 13.
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 13: Trusted Certificate (TC) Identity Scheme Figure 13: Trusted Certificate (TC) Identity Scheme
As described in RFC-2510 [9], each certificate is signed by an issuer As described in RFC-2510 [RFC2510], each certificate is signed by an
one step closer to the trusted host, which has a self-signed trusted issuer one step closer to the trusted host, which has a self-signed
certificate. A certificate is designated trusted when an X509v3 trusted certificate. A certificate is designated trusted when an
Extended Key Usage extension field is present and contains X509v3 Extended Key Usage extension field is present and contains
"trustRoot". If no identity scheme is specified in the parameter "trustRoot". If no identity scheme is specified in the parameter
exchange, this is the default scheme. exchange, this is the default scheme.
B.3. Schnorr (IFF) Identity Scheme Appendix E. Schnorr (IFF) Identity Scheme
The IFF scheme is useful when the group key is concealed, so that The IFF scheme is useful when the group key is concealed, so that
client keys need not be protected. The primary disacvantage is that client keys need not be protected. The primary disadvantage is that
when the server key is refreshed all hosts must update the client when the server key is refreshed all hosts must update the client
key. The scheme shown in Figure Figure 14 involves a set of public key. The scheme shown in Figure Figure 14 involves a set of public
parameters and a group key including both private and public parameters and a group key including both private and public
components. The public component is the client key. components. The public component is the client key.
Trusted Trusted
Authority Authority
+------------+ +------------+
| Parameters | | Parameters |
Secure +------------+ Insecure Secure +------------+ Insecure
skipping to change at page 43, line 6 skipping to change at page 42, line 6
+------------+ Challenge +------------+ +------------+ Challenge +------------+
| Parameters |<------------------------| Parameters | | Parameters |<------------------------| Parameters |
+------------+ +------------+ +------------+ +------------+
| Group Key |------------------------>| Client Key | | Group Key |------------------------>| Client Key |
+------------+ Response +------------+ +------------+ Response +------------+
Server Client Server Client
Figure 14: Schnorr (IFF) Identity Scheme Figure 14: Schnorr (IFF) Identity Scheme
By happy coincidence, the mathematical principles on which IFF is By happy coincidence, the mathematical principles on which IFF is
based are similar to DSA. The scheme is a modification an algorithm based are similar to DSA. The scheme is a modification an algorithm
described in [11] and [12] p. 285. The parameters are generated by described in [SCHNORR] and [STINSON] p. 285. The parameters are
routines in the OpenSSL library, but only the moduli p, q and generated by routines in the OpenSSL library, but only the moduli p,
generator g are used. The p is a 512-bit prime, g a generator of the q and generator g are used. The p is a 512-bit prime, g a generator
multiplicative group Z_p* and q a 160-bit prime that divides (p-1) of the multiplicative group Z_p* and q a 160-bit prime that divides
and is a qth root of 1 mod p; that is, g^q = 1 mod p. The TA rolls a (p-1) and is a qth root of 1 mod p; that is, g^q = 1 mod p. The TA
private random group key b (0 < b < q), then computes public client rolls a private random group key b (0 < b < q), then computes public
key v = g^(q-b) mod p. The TA distributes (p, q, g, b) to all client key v = g^(q-b) mod p. The TA distributes (p, q, g, b) to all
servers using secure means and (p, q, g, v) to all clients not servers using secure means and (p, q, g, v) to all clients not
necessarily using secure means. necessarily using secure means.
The TA hides IFF parameters and keys in an OpenSSL DSA cuckoo The TA hides IFF parameters and keys in an OpenSSL DSA cuckoo
structure. The IFF parameters are identical to the DSA parameters, structure. The IFF parameters are identical to the DSA parameters,
so the OpenSSL library can be used directly. The structure shown in so the OpenSSL library can be used directly. The structure shown in
FigureFigure 15 is written to a file as a DSA private key encoded in FigureFigure 15 is written to a file as a DSA private key encoded in
PEM. Unused structure members are set to one. PEM. Unused structure members are set to one.
+----------------------------------+-------------+ +----------------------------------+-------------+
skipping to change at page 44, line 11 skipping to change at page 43, line 11
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. certificate.
B.4. Guillard-Quisquater (GQ) Identity Scheme Appendix F. Guillard-Quisquater (GQ) Identity Scheme
The GQ scheme is useful when the server key must be refreshed from The GQ scheme is useful when the server key must be refreshed from
time to time without changing the group key. The NTP utility time to time without changing the group key. The NTP utility
programs include the GQ client key in the X509v3 Subject Key programs include the GQ client key in the X509v3 Subject Key
Identifier extension field. The primary disadvantage of the scheme Identifier extension field. The primary disadvantage of the scheme
is that the group key must be protected in both the server and is that the group key must be protected in both the server and
client. A secondary disadvantage is that when a server key is client. A secondary disadvantage is that when a server key is
refreshed, old extension fields no longer work. The scheme is shown refreshed, old extension fields no longer work. The scheme is shown
in Figure Figure 16a involves a set of public parameters and group in Figure Figure 16a involves a set of public parameters and group
key used to generate private server keys and client keys. key used to generate private server keys and client keys.
skipping to change at page 44, line 44 skipping to change at page 43, line 44
| Group Key | | Group Key | | Group Key | | Group Key |
+------------+ Response +------------+ +------------+ Response +------------+
| Server Key |------------------------>| Client Key | | Server Key |------------------------>| Client Key |
+------------+ +------------+ +------------+ +------------+
Server Client Server Client
Figure 16: Schnorr (IFF) Identity Scheme Figure 16: Schnorr (IFF) Identity Scheme
By happy coincidence, the mathematical principles on which GQ is By happy coincidence, the mathematical principles on which GQ is
based are similar to RSA. The scheme is a modification of an based are similar to RSA. The scheme is a modification of an
algorithm described in [13] and [12] p. 300 (with errors). The algorithm described in [GUILLOU] and [STINSON] p. 300 (with errors).
parameters are generated by routines in the OpenSSL library, but only The parameters are generated by routines in the OpenSSL library, but
the moduli p and q are used. The 512-bit public modulus is n=pq, only the moduli p and q are used. The 512-bit public modulus is
where p and q are secret large primes. The TA rolls random large n=pq, where p and q are secret large primes. The TA rolls random
prime b (0 < b < n) and distributes (n, b) to all group servers and large prime b (0 < b < n) and distributes (n, b) to all group servers
clients using secure means, since an intruder in possesion of these and clients using secure means, since an intruder in possession of
values could impersonate a legitimate server. The private server key these values could impersonate a legitimate server. The private
and public client key are constructed later. server key and public client key are constructed later.
The TA hides GQ parameters and keys in an OpenSSL RSA cuckoo The TA hides GQ parameters and keys in an OpenSSL RSA cuckoo
structure. The GQ parameters are identical to the RSA parameters, so structure. The GQ parameters are identical to the RSA parameters, so
the OpenSSL library can be used directly. When generating a the OpenSSL library can be used directly. When generating a
certificate, the server rolls random server key u (0 < u < n) and certificate, the server rolls random server key u (0 < u < n) and
client key its inverse obscured by the group key v = (u^-1)^b mod n. client key its inverse obscured by the group key v = (u^-1)^b mod n.
These values replace the private and public keys normally generated These values replace the private and public keys normally generated
by the RSA scheme. The client key is conveyed in a X.509 certificate by the RSA scheme. The client key is conveyed in a X.509 certificate
extension. The updated GQ structure shown in Figure Figure 17 is extension. The updated GQ structure shown in Figure Figure 17 is
written as an RSA private key encoded in PEM. Unused structure written as an RSA private key encoded in PEM. Unused structure
skipping to change at page 46, line 5 skipping to change at page 45, line 5
3. Alice computes z = (v^r)*(y^b) mod n and verifies hash(z) equals 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 corresponding If the hashes match, Alice knows that Bob has the corresponding
server key u. Besides making the response shorter, the hash makes it server key u. Besides making the response shorter, the hash makes it
effectively impossible for an intruder to solve for u by observing a effectively impossible for an intruder to solve for u by observing a
number of these messages. The signed response binds this knowledge number of these messages. The signed response binds this knowledge
to Bob's private key and the client key previously received in his to Bob's private key and the client key previously received in his
certificate. certificate.
B.5. Mu-Varadharajan (MV) Identity Scheme Appendix G. Mu-Varadharajan (MV) Identity Scheme
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, but is devilishly complicated. It three challenge/response schemes, but is devilishly complicated. It
is most useful when a small number of servers provide synchronization is most useful when a small number of servers provide synchronization
to a large client population where there might be considerable risk to a large client population where there might be considerable risk
of compromise between and among the servers and clients. The client of compromise between and among the servers and clients. The client
population can be partitioned into a modest number of subgroups, each population can be partitioned into a modest number of subgroups, each
associated with an individual client key. associated with an individual client key.
The TA generates an intricate cryptosystem involving encryption and The TA generates an intricate cryptosystem involving encryption and
skipping to change at page 46, line 30 skipping to change at page 45, line 30
keys g-bar and g-hat which depend on the activated keys. The servers keys g-bar and g-hat which depend on the activated keys. The servers
have no additional information and, in particular, cannot masquerade have no additional information and, in particular, cannot masquerade
as a TA. In addition, the TA provides to each client j individual as a TA. In addition, the TA provides to each client j individual
partial decryption keys x-bar_j and x-hat_j, which do not need to be partial decryption keys x-bar_j and x-hat_j, which do not need to be
changed if the TA activates or deactivates any client key. The changed if the TA activates or deactivates any client key. The
clients have no further information and, in particular, cannot clients have no further information and, in particular, cannot
masquerade as a server or TA. masquerade as a server or TA.
The scheme uses an encryption algorithm similar to El Gamal The scheme uses an encryption algorithm similar to El Gamal
cryptography and a polynomial formed from the expansion of product cryptography and a polynomial formed from the expansion of product
terms (x-x_1)(x-x_2)(x-x_3)...(x-x_n), as described in [14]. The terms (x-x_1)(x-x_2)(x-x_3)...(x-x_n), as described in [MV]. The
paper has significant errors and serious omissions. The cryptosystem paper has significant errors and serious omissions. The cryptosystem
is constructed so that, for every encrytion key E its iniverse is is constructed so that, for every encryption key E its inverse is
(g-bar^x-hat_j)(g-hat^x-bar_j) mod p for every j. This remains true (g-bar^x-hat_j)(g-hat^x-bar_j) mod p for every j. This remains true
if both quantities are raised to the power k mod p. The difficulty if both quantities are raised to the power k mod p. The difficulty
in finding E is equivalent to the descrete log problem. in finding E is equivalent to the descrete log problem.
The scheme is shown in Figure Figure 18. The TA generates the The scheme is shown in Figure Figure 18. The TA generates the
parameters, group key, server keys and client keys, one for each parameters, group key, server keys and client keys, one for each
client, all of which must be protected to prevent theft of service. client, all of which must be protected to prevent theft of service.
Note that only the TA has the group key, which is not known to either Note that only the TA has the group key, which is not known to either
the servers or clients. In this sense the MV scheme is a zero- the servers or clients. In this sense the MV scheme is a zero-
knowledge proof. knowledge proof.
skipping to change at page 48, line 22 skipping to change at page 47, line 22
| | | decrypt | | | | | decrypt | |
+---------+----------+------------+-------------+ +---------+----------+------------+-------------+
| x-hat_j | pub_key | public | client | | x-hat_j | pub_key | public | client |
| | | decrypt | | | | | decrypt | |
+---------+----------+------------+-------------+ +---------+----------+------------+-------------+
Figure 20: MV Scheme Client Structure Figure 20: MV Scheme Client Structure
The devil is in the details, which are beyond the scope of this memo. The devil is in the details, which are beyond the scope of this memo.
The steps in generating the cryptosystem activating the keys and The steps in generating the cryptosystem activating the keys and
generating the partial decryption keys are in [15] page 170 ff. generating the partial decryption keys are in [DASBUCH] page 170 ff.
Alice challenges Bob to confirm identity using the following Alice challenges Bob to confirm identity using the following
exchange. exchange.
1. Alice rolls random r (0 < r < q) and sends to Bob. 1. Alice rolls random r (0 < r < q) and sends to Bob.
2. Bob rolls random k (0 < k < q) and computes the session 2. Bob rolls random k (0 < k < q) and computes the session
encryption key E-prime = E^k mod p and partial decryption keys encryption key E-prime = E^k mod p and partial decryption keys
g-bar-prime = g-bar^k mod p and g-hat-prime = g-hat^k mod p. He g-bar-prime = g-bar^k mod p and g-hat-prime = g-hat^k mod p. He
encrypts x = E-prime * r mod p and sends (x, g-bar-prime, g-hat- encrypts x = E-prime * r mod p and sends (x, g-bar-prime, g-hat-
prime) to Alice. prime) to Alice.
3. Alice computes the session decryption key E^-1 = (g-bar-prime)^x- 3. Alice computes the session decryption key E^-1 = (g-bar-prime)^x-
hat_j (g-hat-prime)^x-bar_j mod p and verifies that r = E^-1 x. hat_j (g-hat-prime)^x-bar_j mod p and verifies that r = E^-1 x.
Appendix C. ASN.1 Encoding Rules Appendix H. 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 [RFC3279]. The
algorithms required for conformance are not specified in this memo. particular algorithms required for conformance are not specified in
this memo.
C.1. COOKIE request, IFF response, GQ response, MV response H.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 49, line 38 skipping to change at page 48, 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
} }
C.2. Certificates H.2. Certificates
Certificate extension fields are used to convey information used by Certificate extension fields are used to convey information used by
the identity schemes. While the semantics of these fields generally the identity schemes. While the semantics of these fields generally
conforms with conventional usage, there are subtle variations. The conforms with conventional usage, there are subtle variations. The
fields used by Autokey Version 2 include: fields used by Autokey Version 2 include:
o Basic Constraints. This field defines the basic functions of the o Basic Constraints. This field defines the basic functions of the
certificate. It contains the string "critical,CA:TRUE", which certificate. It contains the string "critical,CA:TRUE", which
means the field must be interpreted and the associated private key means the field must be interpreted and the associated private key
can be used to sign other certificates. While included for can be used to sign other certificates. While included for
skipping to change at page 50, line 22 skipping to change at page 49, line 22
the certificate is designated private or the string "trustRoot" if the certificate is designated private or the string "trustRoot" if
it is designated trusted. A private certificate is always it is designated trusted. A private certificate is always
trusted. trusted.
o Subject Key Identifier. This field contains the client identity o Subject Key Identifier. This field contains the client identity
key used in the GQ identity scheme. It is present only if the GQ key used in the GQ identity scheme. It is present only if the GQ
scheme is in use. scheme is in use.
The value field contains a X509v3 certificate encoded by the The value field contains 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 [10], including the use of X509v3 extension the rules stated in [RFC3280], 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 53, line 44 skipping to change at line 2340
attempt made to obtain a general license or permission for the use of attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr. http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at this standard. Please address the information to the IETF at
ietf-ipr@ietf.org. ietf-ipr@ietf.org.
Acknowledgment
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
 End of changes. 182 change blocks. 
611 lines changed or deleted 560 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/