RFC 5906
Network Time Protocol Version 4: Autokey Specification
RFC 5906: Network Time Protocol Version 4: Autokey Specification 🕰️✨
okay bestie, this is the title block 💖 It's an Informational RFC, so it's published for information and isn't a Standards Track spec. It came out in June 2010 from the IETF (Internet Engineering Task Force) 🌸. The editor is B. Haberman, Ed. from JHU/APL, and D. Mills from U. Delaware is also an author. It has ISSN 2070-1721. The header doesn't list any RFCs it obsoletes or updates, so it stands on its own 🦋
Abstract 🔐
okay so this memo explains Autokey, a security model that lets NTP (Network Time Protocol) servers prove who they are to clients using public key cryptography 🔑 The big idea is that you can't just copy IPsec's schemes, because that would stop servers from being stateless and would seriously mess up how accurate the timekeeping is ⏰ On top of that, PKI schemes assume you always have authenticated time values to check certificate lifetimes, but getting cryptographically verified timestamps means the timekeeping and authentication parts have to talk to each other 💅
This memo covers the Autokey requirements analysis, its design principles, and the protocol spec 📜 It also gives a detailed walkthrough of the protocol's states, events, and transition functions 🧚 A prototype of the Autokey design is implemented, tested, and documented in the NTPv4 software distribution for Unix, Windows, and Virtual Memory System (VMS) operating systems, at http://www.ntp.org 🎀
Status of This Memo 📋
this document is not an Internet Standards Track spec, it's published just for information 🌈
It is a product of the Internet Engineering Task Force (IETF), so it represents the consensus of the IETF community 🫶 It got public review and was approved for publication by the Internet Engineering Steering Group (IESG) ✨ Not every IESG-approved doc is a candidate for any level of Internet Standard, so check Section 2 of RFC 5741 for the details 💜
You can find info about this doc's current status, any errata, and how to give feedback at http://www.rfc-editor.org/info/rfc5906 🦋
Copyright Notice ⚖️
Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved. 🌸
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as they're in effect on the date this document was published. Please read these carefully, because they spell out your rights and restrictions for this doc 🧾 Any Code Components pulled out of this document must include Simplified BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come without warranty as described in the Simplified BSD License 💖
This document may include material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The people who control the copyright in some of that material may not have given the IETF Trust permission to allow modifications outside the IETF Standards Process. Unless you get an adequate license from those copyright holders, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process. The exceptions are formatting it for publication as an RFC or translating it into languages other than English 🌍
Table of Contents 🗺️
1. Introduction ....................................................4
2. NTP Security Model ..............................................4
3. Approach ........................................................7
4. Autokey Cryptography ............................................8
5. Autokey Protocol Overview ......................................12
6. NTP Secure Groups ..............................................14
7. Identity Schemes ...............................................19
8. Timestamps and Filestamps ......................................20
9. Autokey Operations .............................................22
10. Autokey Protocol Messages .....................................23
10.1. No-Operation .............................................26
10.2. Association Message (ASSOC) ..............................26
10.3. Certificate Message (CERT) ...............................26
10.4. Cookie Message (COOKIE) ..................................27
10.5. Autokey Message (AUTO) ...................................27
10.6. Leapseconds Values Message (LEAP) ........................27
10.7. Sign Message (SIGN) ......................................27
10.8. Identity Messages (IFF, GQ, MV) ..........................27
11. Autokey State Machine .........................................28
11.1. Status Word ..............................................28
11.2. Host State Variables .....................................30
11.3. Client State Variables (all modes) .......................33
11.4. Protocol State Transitions ...............................34
11.4.1. Server Dance ......................................34
11.4.2. Broadcast Dance ...................................35
11.4.3. Symmetric Dance ...................................36
11.5. Error Recovery ...........................................37
12. Security Considerations .......................................39
12.1. Protocol Vulnerability ...................................39
12.2. Clogging Vulnerability ...................................40
13. IANA Considerations ...........................................42
13. References ....................................................42
13.1. Normative References .....................................42
13.2. Informative References ...................................43
Appendix A. Timestamps, Filestamps, and Partial Ordering .........45
Appendix B. Identity Schemes .....................................46
Appendix C. Private Certificate (PC) Scheme ......................47
Appendix D. Trusted Certificate (TC) Scheme ......................47
Appendix E. Schnorr (IFF) Identity Scheme ........................48
Appendix F. Guillard-Quisquater (GQ) Identity Scheme .............49
Appendix G. Mu-Varadharajan (MV) Identity Scheme .................51
Appendix H. ASN.1 Encoding Rules .................................54
Appendix I. COOKIE Request, IFF Response, GQ Response, MV
Response .............................................54
Appendix J. Certificates .........................................551. Introduction 🌟
okay so a distributed network service needs stuff that's reliable, available everywhere, and able to survive attacks 🛡️ That protects against both accidental and malicious attacks on the servers and clients, and on the values they swap 💅 Reliability means a client can tell that the packets it got are authentic, meaning they really came from the intended server and weren't made up or changed by an intruder 🕵️♀️ Ubiquity means a client can verify a server's authenticity using only public info 🌍 Survivability means being protected from faulty implementations, improper operation, and possible malicious clogging and replay attacks 💀
This memo describes a cryptographically sound and efficient methodology for use in the Network Time Protocol (NTP) [RFC5905] ⏰ The various key agreement schemes [RFC4306][RFC2412][RFC2522] that have been proposed need per-association state variables, and that clashes with the principles of the remote procedure call (RPC) paradigm, where servers keep no state for what could be a huge client population 🙈 Looking at the PKI model and algorithms, e.g., as implemented in the OpenSSL library, leads to the conclusion that any scheme requiring every NTP packet to carry a PKI digital signature would result in unacceptably poor timekeeping performance 📉 no thank you!!
The Autokey protocol is based on a mix of PKI and a pseudo-random sequence generated by repeated hashes of a cryptographic value that involves both public and private components 🧚 This scheme has been implemented, tested, and deployed on the Internet of today 🚀 A detailed description of the security model, design principles, and implementation is presented in this memo 💜
This informational document describes the NTP extensions for Autokey as implemented in an NTPv4 software distribution available from http://www.ntp.org 🎀 The description is provided to offer a basis for future work and a reference for the software release 🌸 This document also explains the motivation behind the extensions within the protocol ✨
2. NTP Security Model ✨
Okay so NTP security has to be even MORE stringent than most other distributed services, bestie 😭🔥. First, the authentication mechanism and the time synchronization mechanism are literally tangled together 🎀. Reliable time sync needs cryptographic keys that are only valid over designated time intervals, but those intervals can only be enforced when the participating servers and clients are reliably synced to UTC 🕰️. On top of that, the NTP subnet is hierarchical by nature, so time and trust flow from the primary servers at the root, through secondary servers, down to the clients at the leaves 🌳.
A client can claim to be authentic to dependent applications only if every server on the path to the primary servers is bona fide authentic 💅. To hammer this home, this memo swaps "authentic" for "proventic", a brand new adjective for English, derived from "provenance" like the provenance of a painting 🎨. Having already abused the language this far, the suffixes that can be attached to the various derivatives of authentic will be adopted for proventic too 💀. In NTP, each server authenticates the next-lower stratum servers and proventicates (authenticates by induction) the lowest stratum (primary) servers. Serious computer linguists would correctly interpret the proventic relation as the transitive closure of the authentic relation 🤓.
It's important to note that proventic does not necessarily imply the time is correct ⚠️. An NTP client mobilizes a number of concurrent associations with different servers and uses a crafted agreement algorithm to pluck truechimers from the population, possibly including falsetickers 🍓. A particular association is proventic if the server certificate and identity have been verified by the means described in this memo. However, the statement "the client is synchronized to proventic sources" means that the system clock has been set using the time values of one or more proventic associations and according to the NTP mitigation algorithms.
Over the last several years, the IETF has defined and evolved the IPsec infrastructure for privacy protection and source authentication in the Internet 🔐. The infrastructure includes the Encapsulating Security Payload (ESP) [RFC4303] and Authentication Header (AH) [RFC4302] for IPv4 and IPv6. Cryptographic algorithms that use these headers for various purposes include those developed for the PKI, including various message digest, digital signature, and key agreement algorithms. This memo takes no position on which message digest or digital signature algorithm is used. That gets established by a profile for each community of users 🙌.
It will facilitate the discussion in this memo to refer to the reference implementation available at http://www.ntp.org. It includes Autokey as described in this memo and is available to the general public; however, it is not part of the specification itself 🧚. The cryptographic means used by the reference implementation and its user community are based on the OpenSSL cryptographic software library available at http://www.openssl.org, but other libraries with equivalent functionality could be used as well. It is important for distribution and export purposes that the way in which these algorithms are used precludes encryption of any data other than incidental to the construction of digital signatures 🔒.
The fundamental assumption in NTP about the security model is that packets transmitted over the Internet can be intercepted by those other than the intended recipient, remanufactured in various ways, and replayed in whole or part 👀. These packets can cause the client to believe or produce incorrect information, cause protocol operations to fail, interrupt network service, or consume precious network and processor resources 😤.
In the case of NTP, the assumed goal of the intruder is to inject false time values, disrupt the protocol, or clog the network, servers, or clients with spurious packets that exhaust resources and deny service to legitimate applications 🚨. The mission of the algorithms and protocols described in this memo is to detect and discard spurious packets sent by someone other than the intended sender, or sent by the intended sender but modified or replayed by an intruder 🛡️.
There are a number of defense mechanisms already built into the NTP architecture, protocol, and algorithms ✨. The on-wire timestamp exchange scheme is inherently resistant to spoofing, packet-loss, and replay attacks 🙌. The engineered clock filter, selection, and clustering algorithms are designed to defend against evil cliques of Byzantine traitors 😈. While not necessarily designed to defeat determined intruders, these algorithms and accompanying sanity checks have functioned well over the years to deflect improperly operating but presumably friendly scenarios. However, these mechanisms do not securely identify and authenticate servers to clients 💀. Without specific further protection, an intruder can inject any or all of the following attacks:
- An intruder can intercept and archive packets forever, as well as all the public values ever generated and transmitted over the net.
- An intruder can generate packets faster than the server, network, or client can process them, especially if they require expensive cryptographic computations.
- In a wiretap attack, the intruder can intercept, modify, and replay a packet. However, it cannot permanently prevent onward transmission of the original packet; that is, it cannot break the wire, only tell lies and congest it. Except in the unlikely cases considered in Section 12, the modified packet cannot arrive at the victim before the original packet, nor does it have the server private keys or identity parameters.
- In a man-in-the-middle or masquerade attack, the intruder is positioned between the server and client, so it can intercept, modify, and replay a packet and prevent onward transmission of the original packet. Except in unlikely cases considered in Section 12, the middleman does not have the server private keys.
The NTP security model assumes the following possible limitations 🥺:
- The running times for public key algorithms are relatively long and highly variable. In general, the performance of the time synchronization function is badly degraded if these algorithms must be used for every NTP packet.
- In some modes of operation, it is not feasible for a server to retain state variables for every client. It is, however, feasible to regenerate them for a client upon arrival of a packet from that client.
- The lifetime of cryptographic values must be enforced, which requires a reliable system clock. However, the sources that synchronize the system clock must be cryptographically proventicated. This circular interdependence of the timekeeping and proventication functions requires special handling 🌀.
- Client security functions must involve only public values transmitted over the net. Private values must never be disclosed beyond the machine on which they were created, except in the case of a special trusted agent (TA) assigned for this purpose 🔑.
Unlike the Secure Shell (SSH) security model, where the client must be securely authenticated to the server, in NTP the server must be securely authenticated to the client 🔄. In SSH, each different interface address can be bound to a different name, as returned by a reverse-DNS query. In this design, separate public/private key pairs may be required for each interface address with a distinct name. A perceived advantage of this design is that the security compartment can be different for each interface. This allows a firewall, for instance, to require some interfaces to authenticate the client and others not 🧱.
3. Approach 🦋
The Autokey protocol described in this memo is designed to meet the following objectives. In-depth discussions on these objectives are in the web briefings and will not be elaborated in this memo. Note that here, and elsewhere in this memo, mention of broadcast mode means multicast mode as well, with exceptions as noted in the NTP software documentation [RFC5905] 📚.
- It must interoperate with the existing NTP architecture model and protocol design. In particular, it must support the symmetric key scheme described in [RFC1305]. As a practical matter, the reference implementation must use the same internal key management system, including the use of 32-bit key IDs and existing mechanisms to store, activate, and revoke keys 🗝️.
- It must provide for the independent collection of cryptographic values and time values. An NTP packet is accepted for processing only when the required cryptographic values have been obtained and verified and the packet has passed all header sanity checks ✅.
- It must not significantly degrade the potential accuracy of the NTP synchronization algorithms. In particular, it must not make unreasonable demands on the network or host processor and memory resources 💪.
- It must be resistant to cryptographic attacks, specifically those identified in the security model above. In particular, it must be tolerant of operational or implementation variances, such as packet loss or disorder, or suboptimal configurations 🛡️.
- It must build on a widely available suite of cryptographic algorithms, yet be independent of the particular choice. In particular, it must not require data encryption other than that which is incidental to signature and cookie encryption operations 🎀.
- It must function in all the modes supported by NTP, including server, symmetric, and broadcast modes 🌈.
4. Autokey Cryptography ✨
Okay so, Autokey is built on the same PKI algorithms you already know from Secure Shell and SSL 🔐 Like those, it uses message digests to catch packet modification, digital signatures to verify credentials, and public certificates to give you traceable authority. What makes it iconic is how it uses all of that to shut down intruder attacks while keeping the time sync accurate and intact 👑
Autokey, like a lot of remote procedure call (RPC) protocols, leans on message digests for basic authentication 💅 But here's the tea: NTP uses message digests even when Autokey isn't available or configured. Which digest algorithm gets picked depends on the NTP configuration, and Autokey doesn't care. It's totally transparent to it 🫶
The protocol design and the reference implementation both support 128-bit and 160-bit message digest algorithms, and each one comes with a 32-bit key ID ✨ For backwards compatibility with NTPv3, the NTPv4 key ID space is split into two subspaces at a pivot point of 65536 🎀 Symmetric key IDs sit below the pivot and last indefinitely. Autokey key IDs are pseudo-random values equal to or greater than the pivot, and they get expunged immediately after use 💀
Symmetric key and public key cryptography both authenticate the way shown in Figure 1 🦋 The server looks up the key tied to the key ID, then calculates the message digest from the NTP header and extension fields together with the key value. The key ID and digest together form the message authentication code (MAC) that rides along with the message. The client does the exact same computation with its own local copy of the key and compares the result to the digest in the MAC. If they match, the message is assumed authentic 🌸
+------------------+
| NTP Header and |
| Extension Fields |
+------------------+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | Message Authentication Code |
\|/ \|/ + (MAC) +
******************** | +-------------------------+ |
* Compute Hash *<----| Key ID | Message Digest | +
******************** | +-------------------------+ |
| +-+-+-+-+-+-+-|-+-+-+-+-+-+-+-+-+
\|/ \|/
+------------------+ +-------------+
| Message Digest |------>| Compare |
+------------------+ +-------------+
Figure 1: Message AuthenticationAutokey uses specially contrived session keys called autokeys, plus a precomputed pseudo-random sequence of them that gets saved in the autokey list 🧚 The Autokey protocol runs separately for each association, so there can be several autokey sequences going at the same time, all doing their own thing 💜
+-------------+-------------+--------+--------+
| Src Address | Dst Address | Key ID | Cookie |
+-------------+-------------+--------+--------+
Figure 2: NTPv4 AutokeySo an autokey gets computed from those four fields in network byte order, as shown in Figure 2 🍓 The four values get hashed with MD5 to produce the 128-bit autokey value. In the reference implementation, that value is stored along with the key ID in a cache that's used for symmetric keys and autokeys alike. Keys are pulled out of the cache by key ID using hash tables and a fast lookup algorithm ⭐
For IPv4, the Src Address and Dst Address fields hold 32 bits each. For IPv6, they hold 128 bits each. The Key ID and Cookie fields are 32 bits each either way. That means an IPv4 autokey is four 32-bit words, and an IPv6 autokey is ten 32-bit words 🌈 The addresses and key ID are public values you can see right in the packet. The cookie can be a public value or a shared private value, depending on the NTP mode 🙈
The NTP packet format got an upgrade so it can include one or more extension fields tucked between the original NTP header and the MAC 💅 For packets without extension fields, the cookie is a shared private value. For packets with extension fields, the cookie has a default public value of zero, because those packets get validated independently using digital signatures 🫶
Now, there are some situations where using endpoint IP addresses is hard or straight-up impossible 😭 That includes setups with network address translation (NAT) devices, or when addresses change during an association because of mobility constraints. For Autokey, the only restriction is that the address fields visible in the transmitted packet must be the same as the ones used to build the autokey list, and they also have to be the same as the ones visible in the received packet. (Using other means, like Autokey host names (discussed later) or hashes of those names, may be a topic for future study 🔮)
+-----------+-----------+------+------+ +---------+ +-----+------+
|Src Address|Dst Address|Key ID|Cookie|-->| | |Final|Final |
+-----------+-----------+------+------+ | Session | |Index|Key ID|
| | | | | Key ID | +-----+------+
\|/ \|/ \|/ \|/ | List | | |
************************************* +---------+ \|/ \|/
* COMPUTE HASH * *******************
************************************* *COMPUTE SIGNATURE*
| Index n *******************
\|/ |
+--------+ |
| Next | \|/
| Key ID | +-----------+
+--------+ | Signature |
Index n+1 +-----------+
Figure 3: Constructing the Key ListFigure 3 shows how the autokey list and the autokey values get computed 🎀 The key IDs in the autokey list form a sequence that starts with a random 32-bit nonce (the autokey seed), which is greater than or equal to the pivot and serves as the first key ID. The first autokey is computed as described above, using the given cookie and autokey seed, and it gets assigned index 0. The first 32 bits of that result, in network byte order, become the next key ID. The MD5 hash of the autokey is the key value saved in the key cache along with the key ID. The first 32 bits of the key then become the key ID for the next autokey, assigned index 1 ✨
The generation keeps going until the entire list is built 🌸 Sometimes a newly generated key ID turns out to be less than the pivot, or it collides with one that's already been generated (a birthday event). When that happens, which only occurs rarely, the key list gets terminated right at that point 🦋 Each key's lifetime is set to expire one poll interval after its scheduled use. In the reference implementation, the list is terminated when the maximum key lifetime is about one hour. So for poll intervals above one hour, a new key list containing only a single entry gets regenerated for every poll 👑
+------------------+
| NTP Header and |
| Extension Fields |
+------------------+
| |
\|/ \|/ +---------+
**************** +--------+ | Session |
* COMPUTE HASH *<---| Key ID |<---| Key ID |
**************** +--------+ | List |
| | +---------+
\|/ \|/
+-----------------------------------+
| Message Authentication Code (MAC) |
+-----------------------------------+
Figure 4: Transmitting MessagesThe index of the last autokey in the list gets saved along with the key ID for that entry. Together those are called the autokey values 💜 The autokey values are then signed so they can be used later. The list gets used in reverse order, as shown in Figure 4, so the first autokey used is the last one that was generated 🔥
The Autokey protocol includes a message to retrieve the autokey values and verify the signature 💅 That way, subsequent packets can be validated using one or more hashes that eventually match the last key ID (valid) or go past the index (invalid). This is called the autokey test, and it's done for every packet, whether or not it has extension fields 🫶 In the reference implementation, the most recent key ID received is saved so it can be compared with the first 32 bits, in network byte order, of the next following key value. This keeps the number of hash operations down in case a single packet gets lost 🌈
5. Autokey Protocol Overview ✨
okay so the Autokey protocol is basically a bunch of request/response exchanges, and they have to happen in order 💅 every exchange works the same way: the client sends a request message with some data, and the server sends back a response message with its own data 🦋 the requests and responses ride inside extension fields, one per field (more on that later 🎀). an NTP packet can carry one request and one or more responses. here's the lineup 👑
- Parameter exchange. the request has the client's host name and status word, and the response has the server's host name and status word. the status word picks the digest/signature scheme and lists the identity schemes that are supported 🌸
- Certificate exchange. the request has the subject name of a certificate, and the response is a signed certificate with that subject name. if the issuer name isn't the same as the subject name, that cert was signed by a host one step closer to a trusted host, so the client keeps retrieving certs for the issuer name. if it's trusted and self-signed, the trail ends right at the trusted host 💖 if it's nontrusted and self-signed, the host cert hasn't been signed yet, so the trail just loops for a bit 🙈 finishing this exchange lights up the
VALbit (more on that below) ✨ - Identity exchange. ngl this one is a whole vibe 💀 the certificate trail on its own isn't usually enough protection against man-in-the-middle attacks, unless you also have something like the proof-of-possession scheme in [RFC2875], which is expensive and makes servers keep state. Autokey can use one of the challenge/response identity schemes in Appendix B instead 🔥 finishing this exchange lights the
IFFbit 🦋 - Cookie exchange. the request has the server's public key, and the response has the server cookie encrypted with that key. the client uses that value when it builds the key list 🧚 finishing this one lights the
COOKbit 🌈 - Autokey exchange. the request has either no data or the autokey values in symmetric modes. the response has the server's autokey values, and those are what get used to verify the autokey sequence 💜 finishing this lights the
AUTbit ⭐ - Sign exchange. this one only happens once the client has synchronized to a proventic source 🫶 the request has the self-signed client certificate. the server acting as certification authority (CA) reads that cert as an X.509v3 certificate request. it pulls out the subject, issuer, and extension fields, builds a brand-new certificate with those plus its own serial number and expiration time, signs it with its own private key, and sends it back in the response 🍓 the client then uses that signed cert in its own role as a server for its dependent clients. finishing this exchange lights the
SIGNbit 👑 - Leapseconds exchange. also only when the client has synchronized to a proventic source 💅 this one happens when the server has leapseconds values, which the host status word tells you. if so, the client requests them and compares them to its own values, if it has any. if the server's values are newer, the client swaps in the server's values 🎀 the client, acting as a server now, can pass the most recent values along to its dependent clients. in symmetric mode, both peers end up with the newest values, so it's giving teamwork 🌸 finishing this exchange lights the
LPTbit ✨
once the certs and identity have been validated, the later packets get checked with digital signatures and the autokey sequence 🦋 at that point the association is proventic with respect to the downstratum trusted host, but it's not selectable to discipline the system clock yet 🙈 the associations keep collecting time values, and the mitigation algorithms keep doing their thing as usual. when those algorithms have culled the falsetickers and cluster outliers and at least three survivors are left, the system clock has been synchronized to a proventic source 👑🌈
the time values from truechimer sources form a proventic partial ordering, based on the applicable signature timestamps 💜 this raises a really interesting question: how do you tell apart the timestamps from different associations? for example, the timestamp on some Autokey message could be ahead of the system clock by a small amount, and that's totally presumable 🧚 because of that, timestamps aren't compared across different associations, or between associations and the system clock, except in the NTP intersection and clustering algorithms and when checking whether a certificate has expired ⭐ no cap, the timing stuff is delicate 🫶
6. NTP Secure Groups ✨
NTP secure groups are how you make cryptographic compartments and security hierarchies 🏰. A secure group is a bunch of hosts that get dynamically assembled into a forest 🌳, with the roots being the trusted hosts (THs) at the lowest stratum of the group. The THs don't have to be primary (stratum 1) servers, but they often are 👑. A trusted authority (TA), which isn't necessarily a group host, makes the private identity keys for servers and the public identity keys for clients sitting at the leaves of the forest 🍃. The TA hands the server keys to the THs and any other designated servers using secure means, then posts the client keys on a public web site 🌐.
For Autokey purposes, every host in a secure group has the same group name but a different host name, and those host names aren't necessarily related to DNS names 🙈. The group name shows up in the subject and issuer fields of the TH certificates, and the host name goes in those fields for everybody else. So all host certificates are self-signed 💅. When Autokey is running, a client asks its server to sign its certificate and caches the result 💾. Each host builds a certificate trail that might go through intermediate hosts and ends at a TH 🛤️. That means each host along the trail pulls the entire trail from its server(s), then serves that plus its own signed certificates to its clients 🫶.
Secure groups can also be set up as hierarchies, where a TH of one group can be a client of one or more other groups running at a lower stratum 🪜. In one scenario, the THs for groups RED and GREEN stay cryptographically distinct, but both are clients of group BLUE at a lower stratum 💙. In another scenario, the THs for group CYAN are clients of multiple groups, YELLOW and MAGENTA, both operating at a lower stratum ✨. There are lots of other scenarios too, but every one of them must be configured to include only acyclic certificate trails 🔁🚫.
In Figure 5, the Alice group is made up of THs Alice (who is also the TA) and Carol 👩. Dependent servers Brenda and Denise have configured Alice and Carol, respectively, as their time sources. Stratum 3 server Eileen has configured both Brenda and Denise as her time sources 🦋. Public certificates are identified by their subject and signed by their issuer. Also, the server group keys were already installed on Brenda and Denise, and the client group keys were installed on all machines 🔐.
+-------------+ +-------------+ +-------------+
| Alice Group | | Brenda | | Denise |
| Alice | | | | |
| +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ |
Certificate | | Alice | | | | Brenda| | | | Denise| |
+-+-+-+-+-+ | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ |
| Subject | | | Alice*| 1 | | | Alice | 4 | | | Carol | 4 |
+-+-+-+-+-+ | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ |
| Issuer | S | | | | | |
+-+-+-+-+-+ | +=======+ | | +-+-+-+-+ | | +-+-+-+-+ |
| ||Alice|| 3 | | | Alice | | | | Carol | |
Group Key | +=======+ | | +-+-+-+-+ | | +-+-+-+-+ |
+=========+ +-------------+ | | Alice*| 2 | | | Carol*| 2 |
|| Group || S | Alice Group | | +-+-+-+-+ | | +-+-+-+-+ |
+=========+ | Carol | | | | |
| +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ |
S = step | | Carol | | | | Brenda| | | | Denise| |
* = trusted | +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ |
| | Carol*| 1 | | | Brenda| 1 | | | Denise| 1 |
| +-+-+-+-+ | | +-+-+-+-+ | | +-+-+-+-+ |
| | | | | |
| +=======+ | | +=======+ | | +=======+ |
| ||Alice|| 3 | | ||Alice|| 3 | | ||Alice|| 3 |
| +=======+ | | +=======+ | | +=======+ |
+-------------+ +-------------+ +-------------+
Stratum 1 Stratum 2
+---------------------------------------------+
| Eileen |
| |
| +-+-+-+-+ +-+-+-+-+ |
| | Eileen| | Eileen| |
| +-+-+-+-+ +-+-+-+-+ |
| | Brenda| 4 | Carol | 4 |
| +-+-+-+-+ +-+-+-+-+ |
| |
| +-+-+-+-+ +-+-+-+-+ |
| | Alice | | Carol | |
| +-+-+-+-+ +-+-+-+-+ |
| | Alice*| 2 | Carol*| 2 |
| +-+-+-+-+ +-+-+-+-+ |
| |
| +-+-+-+-+ +-+-+-+-+ |
| | Brenda| | Denise| |
| +-+-+-+-+ +-+-+-+-+ |
| | Alice | 2 | Carol | 2 |
| +-+-+-+-+ +-+-+-+-+ |
| |
| +-+-+-+-+ |
| | Eileen| |
| +-+-+-+-+ |
| | Eileen| 1 |
| +-+-+-+-+ |
| |
| +=======+ |
| ||Alice|| 3 |
| +=======+ |
+---------------------------------------------+
Stratum 3Figure 5: NTP Secure Groups
Okay, so the trail-hiking and identity-checking steps go like this 🥾. The step numbers in the descriptions match the step numbers in the figure 🔢.
- The girls kick things off by loading the host key, sign key, self-signed certificate, and group key 🎀. Each client and each server acting as a client starts the Autokey protocol by retrieving the server host name and digest/signature. This happens through the ASSOC exchange, which we cover later 📬.
- They keep loading certificates recursively until they find a self-signed trusted certificate 🔎. Brenda and Denise instantly find trusted certificates for Alice and Carol, respectively, but Eileen gets stuck in a loop 🌀, because neither Brenda nor Denise has their own certificates signed by Alice or Carol. This happens through the CERT exchange, also covered later 💌.
- Brenda and Denise carry on with the selected identity schemes to verify that Alice and Carol have the correct group key that Alice generated earlier 🪪. This uses one of the identity schemes IFF, GQ, or MV, which we'll get to later. If it succeeds, each of them moves on to step 4 🚀.
- Brenda and Denise present their certificates for signature through the SIGN exchange, also covered later ✍️. If that works, either one or both of them can hand these signed certificates to Eileen, who might be looping at step 2 🔁. Eileen can then verify the trail through Brenda or Denise back to the trusted certificates for Alice and Carol 🧩. Once that's done, Eileen can finish the protocol just like Brenda and Denise did 🎉.
For various reasons, a server might want client keys for more than one group, and it's totally a thing 💜. For example, Figure 6 shows three secure groups, Alice, Helen, and Carol, arranged in a hierarchy 🪆. Hosts A, B, C, and D belong to Alice, with A and B as her THs. Hosts R and S belong to Helen, with R as her TH. Hosts X and Y belong to Carol, with X as her TH. Note that the TH for a group is always the lowest stratum, and the hosts of the combined groups form an acyclic graph 📐. Also note that the certificate trail for each group ends on a TH for that group 🎯.
***** ***** @@@@@
Stratum 1 * A * * B * @ R @
***** ***** @@@@@
\ / /
\ / /
***** @@@@@ *********
2 * C * @ S @ * Alice *
***** @@@@@ *********
/ \ /
/ \ / @@@@@@@@@
***** ##### @ Helen @
3 * D * # X # @@@@@@@@@
***** #####
/ \ #########
/ \ # Carol #
##### ##### #########
4 # Y # # Z #
##### #####Figure 6: Hierarchical Overlapping Groups
The whole point of this setup is security separation 🛡️. Servers can't pretend to be clients in other groups, and clients can't pretend to be servers either 🚫. Let's say Alice and Helen belong to national standards laboratories, and their server keys confirm identity between members of each group 🏛️. Carol is a prominent corporation that receives standards products and requires cryptographic authentication 🏢. Maybe under contract, host X, which belongs to Carol, has client keys for both Alice and Helen, plus server keys for Carol 📜. The Autokey protocol runs for each group separately while keeping that security separation intact 🔒. Host X can prove its identity in Carol to clients Y and Z, but it can't prove to anybody that it belongs to Alice or Helen 🙅♀️💖.
7. Identity Schemes ✨
okay bestie, so a digital signature scheme gives you secure server authentication 💅 but it does NOT protect you from masquerade unless you verify the server's identity some other way 🙈. The PKI model makes a server prove who it is with a certificate trail, but a CA still needs independent stuff, like a driver's license, before it signs the server certificate 🪪. Autokey supports this model by default, BUT in a hierarchical ad hoc network, especially with server discovery stuff like NTP manycast, proving identity at each rest stop on the trail has to be an intrinsic capability of Autokey itself 🧚. main character energy, fr fr.
While the identity scheme in [RFC2875] is built on a ubiquitous Diffie-Hellman infrastructure, it's expensive to generate and use compared to the others in Appendix B 😭. In principle, an ordinary public key scheme could be devised for this, but the most stringent Autokey design REQUIRES that every challenge, even if duplicated, results in a different acceptable response 🔥.
7.1. Design Requirements (kinda)
Okay so here's the wishlist for a good identity scheme 🎀:
- The scheme must have a relatively long lifetime, certainly longer than a typical certificate, and have no specific lifetime or expiration date. At the time the scheme is used, the host has not yet synchronized to a proventic source, so the scheme cannot depend on time. 🕰️
- As the scheme can be used many times where the data might be exposed to potential intruders, the data must be either nonces or encrypted nonces. 🔐
- The scheme should allow designated servers to prove identity to designated clients, but not allow clients acting as servers to prove identity to dependent clients. 👑
- To the greatest extent possible, the scheme should represent a zero-knowledge proof; that is, the client should be able to verify that the server has the correct group key, but without knowing the key itself. 🦋
Wait, ngl, the MUST in item 1 and item 2 and the SHOULD in item 3 and item 4 all stay exactly like that in the original, so the vibe is ~chill~ but the rules are not 💀.
There are five schemes now implemented in the NTPv4 reference implementation to prove identity: (1) private certificate (PC), (2) trusted certificate (TC), (3) a modified Schnorr algorithm (IFF aka Identify Friendly or Foe), (4) a modified Guillou-Quisquater (GQ) algorithm, and (5) a modified Mu-Varadharajan (MV) algorithm. Not all of these provide the same level of protection, and one, TC, provides no protection but is included for comparison 🌈. The following is a brief summary description of each; details are given in Appendix B 📚.
The PC scheme involves a private certificate as group key. The certificate is distributed to all other group members by secure means and is never revealed outside the group. In effect, the private certificate is used as a symmetric key. This scheme is used primarily for testing and development and is NOT RECOMMENDED for regular use and is not considered further in this memo 🧪.
All other schemes involve a conventional certificate trail as described in [RFC5280]. This is the default scheme when an identity scheme is not required. While the remaining identity schemes incorporate TC, it is not by itself considered further in this memo 🍓.
The three remaining schemes IFF, GQ, and MV involve a cryptographically strong challenge-response exchange where an intruder cannot deduce the server key, even after repeated observations of multiple exchanges. In addition, the MV scheme is properly described as a zero-knowledge proof, because the client can verify the server has the correct group key without either the server or client knowing its value. These schemes start when the client sends a nonce to the server, which then rolls its own nonce, performs a mathematical operation and sends the results to the client. The client performs another mathematical operation and verifies the results are correct 🫶.
8. Timestamps and Filestamps ⏰
While public key signatures provide strong protection against misrepresentation of source, computing them is expensive 💸. This invites the opportunity for an intruder to clog the client or server by replaying old messages or originating bogus messages. A client receiving such messages might be forced to verify what turns out to be an invalid signature and consume significant processor resources 😩. To foil such attacks, every Autokey message carries a timestamp in the form of the NTP seconds when it was created. If the system clock is synchronized to a proventic source, a signature is produced with a valid (nonzero) timestamp. Otherwise, there is no signature and the timestamp is invalid (zero). The protocol detects and discards extension fields with old or duplicate timestamps, before any values are used or signatures are verified 🛡️.
Signatures are computed only when cryptographic values are created or modified, which is by design not very often. Extension fields carrying these signatures are copied to messages as needed, but the signatures are not recomputed. There are three signature types:
- Cookie signature/timestamp. The cookie is signed when created by the server and sent to the client. 🍪
- Autokey signature/timestamp. The autokey values are signed when the key list is created. 🔑
- Public values signature/timestamp. The public key, certificate, and leapsecond values are signed at the time of generation, which occurs when the system clock is first synchronized to a proventic source, when the values have changed and about once per day after that, even if these values have not changed. 📅
The most recent timestamp received of each type is saved for comparison. Once a signature with a valid timestamp has been received, messages with invalid timestamps or earlier valid timestamps of the same type are discarded before the signature is verified. This is most important in broadcast mode, which could be vulnerable to a clogging attack without this test 📡.
All cryptographic values used by the protocol are time sensitive and are regularly refreshed. In particular, files containing cryptographic values used by signature and encryption algorithms are regenerated from time to time. It is the intent that file regenerations occur without specific advance warning and without requiring prior distribution of the file contents. While cryptographic data files are not specifically signed, every file is associated with a filestamp showing the NTP seconds at the creation epoch 🗂️.
Filestamps and timestamps can be compared in any combination and use the same conventions. It is necessary to compare them from time to time to determine which are earlier or later. Since these quantities have a granularity only to the second, such comparisons are ambiguous if the values are in the same second 🤔.
It is important that filestamps be proventic data; thus, they cannot be produced unless the producer has been synchronized to a proventic source. As such, the filestamps throughout the NTP subnet represent a partial ordering of all creation epochs and serve as means to expunge old data and ensure new data are consistent. As the data are forwarded from server to client, the filestamps are preserved, including those for certificate and leapseconds values. Packets with older filestamps are discarded before spending cycles to verify the signature 🧹.
9. Autokey Operations 🎬
The NTP protocol has three principal modes of operation: client/server, symmetric, and broadcast and each has its own Autokey program, or dance. Autokey choreography is designed to be non-intrusive and to require no additional packets other than for regular NTP operations. The NTP and Autokey protocols operate simultaneously and independently. When the dance is complete, subsequent packets are validated by the autokey sequence and thus considered proventic as well. Autokey assumes NTP clients poll servers at a relatively low rate, such as once per minute or slower. In particular, it assumes that a request sent at one poll opportunity will normally result in a response before the next poll opportunity; however, the protocol is robust against a missed or duplicate response 💃.
The server dance was suggested by Steve Kent over lunch some time ago, but considerably modified since that meal 🥗. The server keeps no state for each client, but uses a fast algorithm and a 32-bit random private value (server seed) to regenerate the cookie upon arrival of a client packet. The cookie is calculated as the first 32 bits of the autokey computed from the client and server addresses, key ID zero, and the server seed as cookie. The cookie is used for the actual autokey calculation by both the client and server and is thus specific to each client separately 🍪✨.
In the server dance, the client uses the cookie and each key ID on the key list in turn to retrieve the autokey and generate the MAC. The server uses the same values to generate the message digest and verifies it matches the MAC. It then generates the MAC for the response using the same values, but with the client and server addresses interchanged. The client generates the message digest and verifies it matches the MAC. In order to deflect old replays, the client verifies that the key ID matches the last one sent. In this dance, the sequential structure of the key list is not exploited, but doing it this way simplifies and regularizes the implementation while making it nearly impossible for an intruder to guess the next key ID 🕵️♀️.
In the broadcast dance, clients normally do not send packets to the server, except when first starting up. At that time, the client runs the server dance to verify the server credentials and calibrate the propagation delay. The dance requires the association ID of the particular server association, since there can be more than one operating in the same server. For this purpose, the server packet includes the association ID in every response message sent and, when sending the first packet after generating a new key list, it sends the autokey values as well. After obtaining and verifying the autokey values, no extension fields are necessary and the client verifies further server packets using the autokey sequence 📻.
The symmetric dance is similar to the server dance and requires only a small amount of state between the arrival of a request and departure of the response. The key list for each direction is generated separately by each peer and used independently, but each is generated with the same cookie. The cookie is conveyed in a way similar to the server dance, except that the cookie is a simple nonce. There exists a possible race condition where each peer sends a cookie request before receiving the cookie response from the other peer. In this case, each peer winds up with two values, one it generated and one the other peer generated. The ambiguity is resolved simply by computing the working cookie as the EXOR of the two values 🤝.
Once the Autokey dance has completed, it is normally dormant. In all except the broadcast dance, packets are normally sent without extension fields, unless the packet is the first one sent after generating a new key list or unless the client has requested the cookie or autokey values. If for some reason the client clock is stepped, rather than slewed, all cryptographic and time values for all associations are purged and the dances in all associations restarted from scratch. This ensures that stale values never propagate beyond a clock step 🧼💖.
10. Autokey Protocol Messages 💌
okay so the Autokey protocol data unit is the extension field 🫶 you can piggyback one or more of them onto an NTP packet. each one is either a request (with optional data) or a response (also with optional data). to avoid deadlocks, a packet can carry any number of responses but only ONE request 🙅♀️ wait, no caps, sorry bestie: only one request can be included. a response gets generated for every request, even if the requestor isn't synced to a proventic source, but most responses only have meaningful data if the responder IS synced to a proventic source ✨ some requests and most responses come with timestamped signatures. the signature covers the entire extension field, including the timestamp and filestamp when they apply. and only if the packet has the right format, length, and message digest do we spend cycles verifying the signature 🧚
there are currently eight Autokey requests and eight matching responses 💅 the NTP packet format is described in [RFC5905], and the extension field format for these messages looks like this:
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|R|E| Code | Field Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Association ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Timestamp |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Filestamp |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Value Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
\ /
/ Value \
\ /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Signature Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
\ /
/ Signature \
\ /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
\ /
/ Padding (if needed) \
\ /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Figure 7: NTPv4 Extension Field Format 🎀
while each extension field is zero-padded to a 4-octet (word) boundary, the entire extension is NOT word-aligned 🙈 the Length field covers the whole extension field, including the Length and Padding fields. the minimum field length is 8 octets, but a maximum field length is still TBD ("remains to be established"). the reference implementation discards any packet with a field length more than 1024 octets 💀
one or more extension fields follow the NTP packet header, and the last one is followed by the MAC. the extension field parser sets a pointer to the first octet beyond the NTP packet header and works out how many octets are left until the end of the packet. if the remaining length is 20 (128-bit digest plus 4-octet key ID) or 22 (160-bit digest plus 4-octet key ID), the leftover data is the MAC and parsing is done ✨ if the remaining length is greater than 22, an extension field is present. if the remaining length is less than 8 or not a multiple of 4, that's a format error and the packet gets discarded. otherwise the parser moves the pointer forward by the extension field length and uses the same rules as above to figure out whether a MAC or another extension field is next 🌸
in Autokey, the 8-bit Field Type field is read as the version number, which is currently 2. for future versions, values 1-7 are reserved for Autokey, and other values may be assigned for other applications 🦋 the 6-bit Code field says which request or response operation it is. there are two flag bits: bit 0 is the Response Flag (R) and bit 1 is the Error Flag (E). the Reserved field isn't used and should be set to 0. the rest of the fields get explained later 🧚
in the most common operations, a client sends a request to a server with an operation code in the Code field, and both the R bit and E bit are dim 💖 the server sends back a response with the same operation code and lights the R bit. the server can also light the E bit if something went wrong. (fun fact: it's not necessarily a protocol error to send an unsolicited response with no matching request 👀) if the R bit is dim, the client puts its client association ID in the Association ID field, and the server returns it so the client can verify it. if the two values don't match, the response is discarded as if it was never sent 🚫 if the R bit is lit, the Association ID field holds the server association ID that was obtained in the initial protocol exchange. if the Association ID doesn't match any mobilized association ID, the request is discarded as if it was never sent 💅
sometimes not every field is there. for requests, until a client has synced to a proventic source, signatures aren't valid. in that case the Timestamp field and the Signature Length field (which gives the length of the Signature) are zero, and the Signature field is absent. some request and error response messages carry no value or signature fields at all, so in those only the first two words (8 octets) are present 🍓
the Timestamp and Filestamp words carry the seconds field of an NTP timestamp. the timestamp sets the signature epoch of the data in the message, and the filestamp sets the generation epoch of the file that ultimately produced the signed data. main character energy 👑
a signature and timestamp are only valid when the signing host is synced to a proventic source; otherwise the timestamp is zero. a cryptographic data file can only be generated if a signature is possible; otherwise the filestamp is zero, EXCEPT in the ASSOC response message, where it holds the server status word 🔥
as in every other TCP/IP protocol design, all data is sent in network byte order 🌈 unless the descriptions below say otherwise, the data being referred to is stored in the Value field. the Value Length field gives the length of the data in the Value field 🫧
10.1. No-Operation
a No-operation request (Code 0) does nothing except return an empty response, which can be used as a crypto-ping 🏓✨
10.2. Association Message (ASSOC)
an Association Message (Code 1) is used in the parameter exchange to get the host name and status word 💜 the request carries the client status word in the Filestamp field and the Autokey host name in the Value field. the response carries the server status word in the Filestamp field and the Autokey host name in the Value field. the Autokey host name is NOT necessarily the DNS host name, so don't mix them up 🙃 a valid response lights the ENAB bit and possibly others in the association status word.
when multiple identity schemes are supported, the host status word decides which ones are available 🎀 in server and symmetric modes, the response status word has bits matching the supported schemes. in all modes, the scheme is picked based on the client identity parameters loaded at startup 🧚
10.3. Certificate Message (CERT)
a Certificate Message (Code 2) is used in the certificate exchange to get a certificate by subject name 📜 the request has the subject name, and the response has the certificate encoded in X.509 format with ASN.1 syntax, as described in Appendix H.
if the subject name in the response doesn't match the issuer name, the exchange keeps going with the issuer name swapped in for the subject name in the request 🔁 it keeps going until a trusted, self-signed certificate turns up and lights the CERT bit in the association status word 🥰
10.4. Cookie Message (COOKIE)
the Cookie Message (Code 3) is used in server and symmetric modes to get the server cookie 🍪 the request contains the host public key encoded with ASN.1 syntax, as described in Appendix H. the response contains the cookie encrypted by the public key from the request. a valid response lights the COOKIE bit in the association status word 💖
10.5. Autokey Message (AUTO)
the Autokey Message (Code 4) is used to get the autokey values 🔑 the request has no value for a client, or the autokey values for a symmetric peer. the response has two 32-bit words: the first is the final key ID, and 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)
the Leapseconds Values Message (Code 5) is used to get the leapseconds values, parsed from the leapseconds table from the National Institute of Standards and Technology (NIST) 🕰️ the request has no values. the response has three 32-bit integers: first the NTP seconds of the latest leap event, then the NTP seconds when the latest NIST table expires, and then the TAI offset following the leap event. a valid response lights the LEAP bit in the association status word 🌟
10.7. Sign Message (SIGN)
the Sign Message (Code 6) asks the server to sign and return a certificate presented in the request ✍️ the request contains the client certificate encoded in X.509 format with ASN.1 syntax, as described in Appendix H. the response contains the client 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)
the Identity Messages (Code 7 (IFF), 8 (GQ), or 9 (MV)) contain the client challenge, usually a 160- or 512-bit nonce 🎲 the response contains the result of the mathematical operation defined in Appendix B. the Response is encoded in ASN.1 syntax, as described in Appendix H. a valid response lights the VRFY bit in the association status word 💅
11. Autokey State Machine 🧠
this section describes the formal model of the Autokey state machine, its state variables, and the state transition functions 🦋
11.1. Status Word ✨
Okay bestie, so the server keeps a host status word 🖥️ and every client keeps its own association status word 🤝. They share the same format and content, shown in Figure 8 💖. The low-order 16 bits track where the Autokey dance is up to 💃, and the high-order 16 bits hold a Numerical Identifier (NID) 🔢. The NID is generated by the OpenSSL library from the OID of one of the message digest/signature encryption schemes defined in [RFC3279] 📜. Here are the NID values for the digest/signature algorithms in RFC 3279, and yes they're all very specific 🥹:
+------------------------+----------------------+-----+
| Algorithm | OID | NID |
+------------------------+----------------------+-----+
| pkcs-1 | 1.2.840.113549.1.1 | 2 |
| md2 | 1.2.840.113549.2.2 | 3 |
| md5 | 1.2.840.113549.2.5 | 4 |
| rsaEncryption | 1.2.840.113549.1.1.1 | 6 |
| md2WithRSAEncryption | 1.2.840.113549.1.1.2 | 7 |
| md5WithRSAEncryption | 1.2.840.113549.1.1.4 | 8 |
| id-sha1 | 1.3.14.3.2.26 | 64 |
| sha-1WithRSAEncryption | 1.2.840.113549.1.1.5 | 65 |
| id-dsa-wth-sha1 | 1.2.840.10040.4.3 | 113 |
| id-dsa | 1.2.840.10040.4.1 | 116 |
+------------------------+----------------------+-----+Bits 24-31 are reserved for server use, and bits 16-23 are reserved for client use 🎀. Inside the host portion, bits 24-27 pick the available identity schemes, and bits 28-31 show the server capabilities 🧚. There are also two extra bits that get implemented separately 🌈.
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Digest / Signature NID | Client | Ident | Host |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Figure 8: Status Word
The host status word rides along in the ASSOC request and response messages 📨. The client copies it into its association status word and then lights up more bits as the dance goes on 💡. Once a bit is lit it basically never goes dark again 🔥, unless there's a general reset and the whole protocol restarts from the very beginning 😭.
Host status bits 🖥️✨
- ENAB (31) is lit if the server implements the Autokey protocol 🔐.
- LVAL (30) is lit if the server has installed leapseconds values, whether they came from the NIST leapseconds file or from another server 🕰️.
- Bits (28-29) are reserved and always dark 🙈.
- Bits 24-27 select which server identity schemes are available 🪪. The specific coding for each scheme isn't decided yet, but the reference implementation (described in Appendix B) includes these schemes:
- none - Trusted Certificate (TC) Scheme (default) 💅.
- PC (27) Private Certificate Scheme 🕵️♀️.
- IFF (26) Schnorr aka Identify-Friendly-or-Foe Scheme 👀.
- GQ (25) Guillard-Quisquater Scheme 🦋.
- MV (24) Mu-Varadharajan Scheme 💜.
- The PC scheme can't be mixed with any other scheme 🚫. Otherwise, the IFF, GQ, and MV bits can be turned on in any combination 🎛️.
Association status bits 🤝✨
- CERT (23): lit when the trusted host certificate and public key are validated 📜.
- VRFY (22): lit when the trusted host identity credentials are confirmed 🪪.
- PROV (21): lit when the server signature is verified using its public key and identity credentials 🔏. This is also called the proventic bit elsewhere in this memo. When it's enabled, signed values in later messages are presumed proventic 💖.
- COOK (20): lit when the cookie is received and validated 🍪. When it's lit, key lists with nonzero cookies get generated. When it's dim, the cookie is zero 🫶.
- AUTO (19): lit when the autokey values are received and validated ✨. When it's lit, clients can validate packets that don't have extension fields, following the autokey sequence 🧩.
- SIGN (18): lit when the host certificate is signed by the server ✍️.
- LEAP (17): lit when the leapseconds values are received and validated 🕰️.
- Bit 16: reserved and always dark 🌙.
There are three more bits, LIST, SYNC, and PEER, that aren't part of the association status word at all 👀. LIST is lit when the key list gets regenerated and dim once the autokey values have been transmitted. This is needed to avoid livelock under some conditions 🙏. SYNC is lit when the client has synchronized to a proventic source, and it never goes dim after that 🔒. PEER is lit when the server has synchronized, as shown in the NTP header, and it never goes dim after that either 🌸.
11.2. Host State Variables 💜
Here's the list of host state variables, and they're all kinda important 🤓.
- Host Name: the name of the host. By default it's the string returned by the Unix gethostname() library function 🏷️. In the reference implementation this is a configurable value ⚙️.
- Host Status Word: this word gets initialized when the host first starts up 🚀. The format is described above 👆.
- Host Key: the RSA public/private key pair used to encrypt and decrypt cookies 🍪. This is also the default sign key 🔑.
- Sign Key: the RSA or Digital Signature Algorithm (DSA) public/private key pair used to encrypt and decrypt signatures when the host key isn't used for that job 🖊️.
- Sign Digest: the message digest algorithm used to compute the message digest before encryption 🧮.
- IFF Parameters: the parameters used in the optional IFF identity scheme described in Appendix B 👀.
- GQ Parameters: the parameters used in the optional GQ identity scheme described in Appendix B 🦋.
- MV Parameters: the parameters used in the optional MV identity scheme described in Appendix B 💜.
- Server Seed: the private value that gets hashed together with the IP addresses and key identifier to build the cookie 🌱.
- CIS: short for Certificate Information Structure 📇. This structure holds certain info fields from an X.509v3 certificate, plus the certificate itself. The extracted fields include the subject and issuer names, the subject public key and message digest algorithm (as pointers), and the beginning and end of the valid period in NTP seconds 🗓️.
The certificate itself is stored as an extension field in network byte order, so it can be copied into the message completely intact 📦. The structure is signed with the sign key and carries the public values timestamp at signature time, plus the filestamp of the original certificate file 🕒. The CIS gets used by the CERT response message and the SIGN request and response messages 💌.
A flags field in the CIS decides the status of the certificate 🚦. It's encoded like this:
TRUST (0x01): the certificate was signed by a trusted issuer. If the certificate is self-signed and has "trustRoot" in the Extended Key Usage field, this bit gets lit when the CIS is built 👑.SIGN (0x02): the certificate signature has been verified. If the certificate is self-signed and verified with its own contained public key, this bit gets lit when the CIS is built ✅.VALID (0x04): the certificate is valid and can be used to verify signatures 💯. This bit gets lit when a trusted certificate has been found on a valid certificate trail 🛤️.PRIV (0x08): the certificate is private and not to be revealed 🤫. If the certificate is self-signed and has "Private" in the Extended Key Usage field, this bit gets lit when the CIS is built 🔒.ERROR (0x80): the certificate is defective and must not be used in any way 💀.
- Certificate List: CIS structures are stored on the certificate list in order of arrival, with the newest CIS placed first 📋. The list starts out with the CIS for the host certificate, which gets read from the host certificate file 📂. More CIS entries get added as certificates come in from servers during the certificate exchange 📨. CIS entries get discarded if newer ones overtake them 🧹.
These values are stored as an extension field structure in network byte order, so they can be copied intact into the message 🧳. They're used to send some Autokey requests and responses 💫. Everything except the Host Name Values structure is signed with the sign key, and they all carry the public values timestamp at signature time ⏱️.
- Host Name Values: used to send ASSOC request and response messages 🤝. It contains the host status word and the host name 🏷️.
- Public Key Values: used to send the COOKIE request message 🍪. It contains the public encryption key used for the COOKIE response message 🔐.
- Leapseconds Values: used to send the LEAP response message 🕰️. It contains the leapseconds values described in the LEAP message description ✨.
11.3. Client State Variables (all modes) 💅
okay bestie, these are the state variables every dance uses in ALL modes 🧚 they're the client's little notebook of everything it's tracking ✨
Association ID: The association ID used in responses. It is assigned when the association is mobilized.Association Status Word: The status word copied from the ASSOC response, subsequently modified by the state machine.Subject Name: The server host name copied from the ASSOC response.Issuer Name: The host name signing the certificate. It is extracted from the current server certificate upon arrival and used to request the next host on the certificate trail. 🫶Server Public Key: The public key used to decrypt signatures. It is extracted from the server host certificate.Server Message Digest: The digest/signature scheme determined in the parameter exchange.Group Key: A set of values used by the identity exchange. It identifies the cryptographic compartment shared by the server and client. 🔐Receive Cookie Values: The cookie returned in a COOKIE response, together with its timestamp and filestamp.Receive Autokey Values: The autokey values returned in an AUTO response, together with its timestamp and filestamp.Send Autokey Values: The autokey values with signature and timestamps.Key List: A sequence of key IDs starting with the autokey seed, each pointing to the next. It is computed, timestamped, and signed at the next poll opportunity when the key list becomes empty. 🌸Current Key Number: The index of the entry on the Key List to be used at the next poll opportunity.
11.4. Protocol State Transitions 🦋
the protocol state machine is very simple but ROBUST 💪 the state is determined by the client status word bits we defined above. the state transitions of the three dances are shown below. the capitalized truth values represent the client status bits. all bits start out dark and get lit up when a specific response message arrives, as detailed above ✨
11.4.1. Server Dance 🎀
the server dance begins when the client sends an ASSOC request to the server. the clock is updated when PREV is lit and the dance ends when LEAP is lit. in this dance the autokey values are not used, so an autokey exchange is not necessary. note that the SIGN and LEAP requests are not issued until the client has synchronized to a proventic source. subsequent packets without extension fields are validated by the autokey sequence. this example and others assume the IFF identity scheme has been selected in the parameter exchange 🔥
1 while (1) {
2 wait_for_next_poll;
3 make_NTP_header;
4 if (response_ready)
5 send_response;
6 if (!ENB) /* parameter exchange */
7 ASSOC_request;
8 else if (!CERT) /* certificate exchange */
9 CERT_request(Host_Name);
10 else if (!IFF) /* identity exchange */
11 IFF_challenge;
12 else if (!COOK) /* cookie exchange */
13 COOKIE_request;
14 else if (!SYNC) /* wait for synchronization */
15 continue;
16 else if (!SIGN) /* sign exchange */
17 SIGN_request(Host_Certificate);
18 else if (!LEAP) /* leapsecond values exchange */
19 LEAP_request;
20 send packet;
21 }Figure 9: Server Dance
if the server refreshes the private seed, the cookie becomes invalid 🙈 the server responds to an invalid cookie with a crypto-NAK message, which makes the client restart the protocol from the very beginning. oof 💀
11.4.2. Broadcast Dance 📡
the broadcast dance is basically the server dance, except the cookie exchange gets swapped out for the autokey values exchange 🔄 the broadcast dance begins when the client receives a broadcast packet including an ASSOC response with the server association ID. this mobilizes a client association so it can proventicate the source and calibrate the propagation delay. the dance ends when the LEAP bit is lit, and after that 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 🧃
in the broadcast dance, extension fields are used with every packet, so the cookie is always zero and no cookie exchange is necessary. as in the server dance, the clock is updated when PREV is lit and the dance ends when LEAP is lit. note that the SIGN and LEAP requests are not issued until the client has synchronized to a proventic source. subsequent packets without extension fields are validated by the autokey sequence ✨
1 while (1) {
2 wait_for_next_poll;
3 make_NTP_header;
4 if (response_ready)
5 send_response;
6 if (!ENB) /* parameters exchange */
7 ASSOC_request;
8 else if (!CERT) /* certificate exchange */
9 CERT_request(Host_Name);
10 else if (!IFF) /* identity exchange */
11 IFF_challenge;
12 else if (!AUT) /* autokey values exchange */
13 AUTO_request;
14 else if (!SYNC) /* wait for synchronization */
15 continue;
16 else if (!SIGN) /* sign exchange */
17 SIGN_request(Host_Certificate);
18 else if (!LEAP) /* leapsecond values exchange */
19 LEAP_request;
20 send NTP_packet;
21 }Figure 10: Broadcast Dance
if a packet is lost and the autokey sequence breaks, 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 it's the latter, the client sends an AUTO request to retrieve 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, no cap 🩰 it begins when the active peer sends an ASSOC request to the passive peer. the passive peer mobilizes an association, and then both peers step a three-way dance where each peer completes a parameter exchange with the other. until one of the peers has synchronized to a proventic source (which could be the other peer) and can sign messages, the other peer loops waiting for a valid timestamp in the ensuing CERT response 🌈
1 while (1) {
2 wait_for_next_poll;
3 make_NTP_header;
4 if (!ENB) /* parameters exchange */
5 ASSOC_request;
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 }Figure 11: Symmetric Dance
once a peer has synchronized to a proventic source, it includes timestamped signatures in its messages. the other peer, which has been stalled waiting for valid timestamps, now mates the dance 💖 it retrieves the now nonzero cookie using a cookie exchange, and then the updated autokey values using an autokey exchange.
as in the broadcast dance, if a packet is lost and the autokey sequence breaks, the peer 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 it's the latter, the client sends an AUTO request to retrieve the autokey values. if the peer receives a crypto-NAK during the dance, or if the association ID changes, the peer restarts the protocol from the beginning. 🫶
11.5. Error Recovery 🚑
okay so the Autokey state machine has a whole toolkit for when things go sideways 😭 like missing files, corrupted data, protocol violations, packets getting lost or showing up out of order, and yes, hostile intruders too 💀. this section is all about how the protocol reacts to reachability and timeout events that come from that kind of mess 🫶
a persistent NTP association gets mobilized by an entry in the configuration file ✨, while an ephemeral association gets mobilized when a broadcast or symmetric active packet shows up with no matching association 🦋. then a general reset reinitializes all association variables back to the initial state they had when first mobilized 🌸. and if the association is ephemeral, it gets demobilized and every resource it grabbed is returned to the system 💅
every NTP association has two variables that keep track of its liveness: the 8-bit reach register and the unreach counter, both defined in [RFC5905] 🧚. at every poll interval, the reach register is shifted left, the low-order bit gets dimmed (so, zero), and the high-order bit gets lost 👋. at the same time, the unreach counter goes up by one. if an arriving packet passes all authentication and sanity checks, the rightmost bit of the reach register gets lit and the unreach counter resets to zero 🔥. if any bit in the reach register is lit, the server is reachable; otherwise, it's unreachable 💀
when the first poll is sent from an association, the reach register and unreach counter both get set to zero 🍓. if the unreach counter hits 16, the poll interval is doubled. and if the association is persistent, it gets demobilized too 🙈. this is lowkey smart because it cuts down the network load for packets that aren't likely to get a response ✨
at each state in the protocol, the client is expecting a particular response from the server 🎀. a request gets included in the NTP packet sent at each poll interval until a valid response comes back or a general reset happens, and in that case the protocol restarts from the beginning 🔄. a general reset also happens for an association when an unrecoverable protocol error occurs 😤. and a general reset happens for all associations when the system clock is first synchronized, when the clock is stepped, or when the server seed is refreshed 🌈
there are special cases designed to respond quickly to broken associations, like when a server restarts or refreshes its keys 🫠. since the client cookie gets invalidated, the server rejects the next client request and returns a crypto-NAK packet 🙅♀️. the crypto-NAK has no MAC, so the problem for the client is figuring out whether it's legit or the result of intruder mischief 🕵️♀️. to reduce the vulnerability in these cases, the crypto-NAK, along with all responses, is only believed if it's the result of a previous packet sent by the client and not a replay, as confirmed by the NTP on-wire protocol 🛡️. ngl, this defense can be easily circumvented by a man-in-the-middle, but it does deflect other kinds of intruder warfare 💅
there are a bunch of situations where some event causes the remaining autokeys on the key list to become invalid 😵💫. when one of these happens, the key list and associated autokeys in the key cache get purged. a new key list, signature, and timestamp are generated when the next NTP message is sent, assuming there is one to send ✨. here's the list of those situations:
- When the cookie value changes for any reason.
- When the poll interval is changed. In this case, the calculated expiration times for the keys become invalid.
- 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 timed out, either of which implies a software bug. 🐛
12. Security Considerations 🔐
okay bestie, this section is where we talk about the most obvious security vulnerabilities in the various Autokey dances 😰. for all of this, the cryptographic algorithms and private values themselves are assumed to be secure. that means a brute force cryptanalytic attack will not reveal the host private key, sign private key, cookie value, identity parameters, server seed, or autokey seed. and an intruder will not be able to predict random generator values. no cap, that's the foundation everything else is built on 👑
12.1. Protocol Vulnerability 🧐
the protocol hasn't been subjected to a formal analysis yet, but a few preliminary assertions can be made 📝. in the client/server and symmetric dances, the underlying NTP on-wire protocol is resistant to lost, duplicate, and bogus packets, even if the clock isn't synchronized. so the protocol isn't vulnerable to a wiretapper attack 🙌. the on-wire protocol is also resistant to replays of both the client request packet and the server reply packet 🔁. a man-in-the-middle attack, even if it could simulate a valid cookie, could not prove identity 🫥.
in the broadcast dance, the client begins with a volley in client/server mode to obtain the autokey values and signature, so it has the same protection as it does in that mode ✨. when it continues in receive-only mode, a wiretapper cannot produce a key list with valid signed autokey values 🚫. if the wiretapper replays an old packet, the client will reject it by the timestamp check 🗑️. the most it can do is manufacture a future packet, which causes clients to repeat the autokey hash operations until they exceed the maximum key number 😩. if this happens, the broadcast client temporarily reverts to client mode to refresh the autokey values 🔄.
by assumption, a man-in-the-middle attacker that intercepts a packet cannot break the wire or delay an intercepted packet ⚠️. if this assumption is removed, the middleman could intercept a broadcast packet and replace the data and message digest without the clients detecting it 😱.
as mentioned previously in this memo, the TC identity scheme is vulnerable to a man-in-the-middle attack where an intruder could create a bogus certificate trail 🚨. to foil this kind of attack, either the PC, IFF, GQ, or MV identity scheme must be used 🛡️.
a client instantiates cryptographic variables only if the server is synchronized to a proventic source 🎯. a server does not sign values or generate cryptographic data files unless it's synchronized to a proventic source 🔏. this raises an interesting issue: how does a client generate proventic cryptographic files before it has ever been synchronized to a proventic source? (who shaves the barber if the barber shaves everybody in town who does not shave himself?) 💈 in principle, this paradox is resolved by assuming the primary (stratum 1) servers are proventicated by external phenomenological means 🌟.
12.2. Clogging Vulnerability 🧱
a self-induced clogging incident cannot happen, since signatures are only computed when the data have changed, and the data don't change very often 🙅♀️. for instance, the autokey values are signed only when the key list is regenerated, which happens about once an hour. meanwhile, the public values are signed only when one of them is updated during a dance or the server seed is refreshed, which happens about once per day ⏰.
there are two clogging vulnerabilities exposed in the protocol design 😬. the first is an encryption attack, where the intruder hopes to clog the victim server with needless cryptographic calculations. the second is a decryption attack, where the intruder attempts to clog the victim client with needless cryptographic calculations. autokey uses public key cryptography, and the algorithms that perform these functions consume significant resources 🥵.
in client/server and peer dances, an encryption hazard exists when a wiretapper replays prior cookie request messages at speed 🏎️. there's no obvious way to deflect such attacks, since the server retains no state between requests 🤷♀️. replays of cookie request or response messages are detected and discarded by the client on-wire protocol 🗑️.
in broadcast mode, a decryption hazard exists when a wiretapper replays autokey response messages at speed 💨. once synchronized to a proventic source, a legitimate extension field with a timestamp the same as or earlier than the most recently received of that type is immediately discarded 🚮. this foils a man-in-the-middle cut-and-paste attack using an earlier response, for example 🙅♀️. a legitimate extension field with a timestamp in the future is unlikely, since that would require predicting the autokey sequence. however, this still causes the client to refresh and verify the autokey values and signature 🔄.
a determined attacker can destabilize the on-wire protocol or an Autokey dance in various ways by replaying old messages before the client or peer has synchronized for the first time 😈. for instance, replaying an old symmetric mode message before the peers have synchronized will prevent the peers from ever synchronizing 🙃. replaying out-of-order Autokey messages in any mode during a dance could prevent the dance from ever completing 🌀. there's nothing new in these kinds of attack, though; a similar vulnerability even exists in TCP 🤓.
13. IANA Consideration ✨
the IANA has added the following entries to the NTP Extensions Field Types registry 📋:
+------------+------------------------------------------+
| Field Type | Meaning |
+------------+------------------------------------------+
| 0x0002 | No-Operation Request |
| 0x8002 | No-Operation Response |
| 0xC002 | No-Operation Error Response |
| 0x0102 | Association Message Request |
| 0x8102 | Association Message Response |
| 0xC102 | Association Message Error Response |
| 0x0202 | Certificate Message Request |
| 0x8202 | Certificate Message Response |
| 0xC202 | Certificate Message Error Response |
| 0x0302 | Cookie Message Request |
| 0x8302 | Cookie Message Response |
| 0xC302 | Cookie Message Error Response |
| 0x0402 | Autokey Message Request |
| 0x8402 | Autokey Message Response |
| 0xC402 | Autokey Message Error Response |
| 0x0502 | Leapseconds Value Message Request |
| 0x8502 | Leapseconds Value Message Response |
| 0xC502 | Leapseconds Value Message Error Response |
| 0x0602 | Sign Message Request |
| 0x8602 | Sign Message Response |
| 0xC602 | Sign Message Error Response |
| 0x0702 | IFF Identity Message Request |
| 0x8702 | IFF Identity Message Response |
| 0xC702 | IFF Identity Message Error Response |
| 0x0802 | GQ Identity Message Request |
| 0x8802 | GQ Identity Message Response |
| 0xC802 | GQ Identity Message Error Response |
| 0x0902 | MV Identity Message Request |
| 0x8902 | MV Identity Message Response |
| 0xC902 | MV Identity Message Error Response |
+------------+------------------------------------------+14. References 📚
14.1. Normative References
[RFC5905] Mills, D., Martin, J., Ed., Burbank, J., and W. Kasch,
"Network Time Protocol Version 4: Protocol and Algorithms
Specification", RFC 5905, June 2010.14.2. Informative References 📚
Okay bestie, these are the background reads 🧚 The original calls them informative, so they're the extra context behind the spec, not the spec itself 💅
[DASBUCH]Mills, D., "Computer Network Time Synchronization - the Network Time Protocol", 2006.[GUILLOU]Guillou, L. and J. Quisquatar, "A "paradoxical" identity-based signature scheme resulting from zero-knowledge", 1990.[MV]Mu, Y. and V. Varadharajan, "Robust and secure broadcasting", 2001.[RFC1305]Mills, D., "Network Time Protocol (Version 3) Specification, Implementation", RFC 1305, March 1992.[RFC2412]Orman, H., "The OAKLEY Key Determination Protocol", RFC 2412, November 1998.[RFC2522]Karn, P. and W. Simpson, "Photuris: Session-Key Management Protocol", RFC 2522, March 1999.[RFC2875]Prafullchandra, H. and J. Schaad, "Diffie-Hellman Proof-of-Possession Algorithms", RFC 2875, July 2000.[RFC3279]Bassham, L., Polk, W., and R. Housley, "Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 3279, April 2002.[RFC4210]Adams, C., Farrell, S., Kause, T., and T. Mononen, "Internet X.509 Public Key Infrastructure Certificate Management Protocol (CMP)", RFC 4210, September 2005.[RFC4302]Kent, S., "IP Authentication Header", RFC 4302, December 2005.[RFC4303]Kent, S., "IP Encapsulating Security Payload (ESP)", RFC 4303, December 2005.[RFC4306]Kaufman, C., "Internet Key Exchange (IKEv2) Protocol", RFC 4306, December 2005.[RFC5280]Cooper, D., Santesson, S., Farrell, S., Boeyen, S., Housley, R., and W. Polk, "Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 5280, May 2008.[SCHNORR]Schnorr, C., "Efficient signature generation for smart cards", 1991.[STINSON]Stinson, D., "Cryptography - Theory and Practice", 1995.
Appendix A. Timestamps, Filestamps, and Partial Ordering ⏰
When the host starts up, it reads the host key and host certificate files, which are required for continued operation 🔐 It also grabs the sign key and leapseconds values, when they're available. While reading these, the host checks the file formats and filestamps for validity 🧐 For instance, all filestamps must be later than the time the UTC timescale was established in 1972, and the certificate filestamp must not be earlier than its associated sign key filestamp. At the time the files are read, the host is not synchronized, so it can't tell whether the filestamps are bogus other than by using these simple checks. It must not produce filestamps or timestamps until synchronized to a proventic source.
In the following bit, A --> B is Lamport's "happens before" relation, which is true if event A happens before event B 🪄 When timestamps are compared to timestamps, the relation is false if A <--> B; that is, false if the events are simultaneous. For timestamps compared to filestamps and filestamps compared to filestamps, the relation is true if A <--> B. Note that the current time plays no part in these assertions except in (6) below; however, the NTP protocol itself ensures a correct partial ordering for all current time values ⏳
The following assertions apply to all relevant responses:
- The client saves the most recent timestamp
T0and filestampF0for the respective signature type. For every received message carrying timestampT1and filestampF1, the message is discarded unlessT0 --> T1andF0 --> F1. The requirement thatT0 --> T1is the primary defense against replays of old messages 🛡️ - For timestamp
Tand filestampF,F --> T; that is, the filestamp must happen before the timestamp. If not, this could be due to a file generation error or a significant error in the system clock time. - For sign key filestamp
S, certificate filestampC, cookie timestampDand autokey timestampA,S --> C --> D --> A; that is, the autokey must be generated after the cookie, the cookie after the certificate, and the certificate after the sign key. Very chronological, very iconic 📅 - For sign key filestamp
Sand certificate filestampCspecifying begin timeBand end timeE,S --> C--> B --> E; that is, the valid period must not be retroactive. No time-travel certs allowed 🙅♀️ - A certificate for subject
Ssigned by issuerIand with filestampC1obsoletes, but does not necessarily invalidate, another certificate with the same subject and issuer but with filestampC0, whereC0 --> C1. - A certificate with begin time
Band end timeEis invalid and cannot be used to verify signatures ift --> BorE --> t, wheretis the current proventic time. Note that the public key previously extracted from the certificate continues to be valid for an indefinite time. This raises the interesting possibility where a truechimer server with expired certificate or a falseticker with valid certificate are not detected until the client has synchronized to a proventic source. Plot twist energy 🎭
Appendix B. Identity Schemes 🪪
There are five identity schemes in the NTPv4 reference implementation: (1) private certificate (PC), (2) trusted certificate (TC), (3) a modified Schnorr algorithm (IFF - Identify Friend or Foe), (4) a modified Guillou-Quisquater (GQ) algorithm, and (5) a modified Mu-Varadharajan (MV) algorithm. Five schemes, zero boring 🌈
The PC scheme is intended for testing and development and not recommended for general use. The TC scheme uses a certificate trail, but not an identity scheme. The IFF, GQ, and MV identity schemes use a cryptographically strong challenge-response exchange where an intruder cannot learn the group key, even after repeated observations of multiple exchanges 🔒 These schemes begin when the client sends a nonce to the server, which then rolls its own nonce, performs a mathematical operation and sends the results to the client. The client performs a second mathematical operation to prove the server has the same group key as the client. Ngl, the nonce ping-pong is so satisfying 🥹
Appendix C. Private Certificate (PC) Scheme 🎀
The PC scheme shown in Figure 12 uses a private certificate as the group key 🗝️
Trusted
Authority
Secure +-------------+ Secure
+--------------| Certificate |-------------+
| +-------------+ |
| |
\|/ \|/
+-------------+ +-------------+
| Certificate | | Certificate |
+-------------+ +-------------+
Server ClientFigure 12: Private Certificate (PC) Identity Scheme
A certificate is designated private when the X.509v3 Extended Key Usage extension field is present and contains "Private". The private certificate is distributed to all other group members by secret means, so in fact becomes a symmetric key 🤫 Private certificates are also trusted, so there is no need for a certificate trail or identity scheme. Main character, no backup needed 👑
Appendix D. Trusted Certificate (TC) Scheme 🌸
All other schemes involve a conventional certificate trail as shown in Figure 13 🔗
Trusted
Host Host Host
+-----------+ +-----------+ +-----------+
+--->| Subject | +--->| Subject | +--->| Subject |
| +-----------+ | +-----------+ | +-----------+
...---+ | Issuer |---+ | Issuer |---+ | Issuer |
+-----------+ +-----------+ +-----------+
| Signature | | Signature | | Signature |
+-----------+ +-----------+ +-----------+Figure 13: Trusted Certificate (TC) Identity Scheme
As described in RFC 4210 [RFC4210], each certificate is signed by an issuer one step closer to the trusted host, which has a self-signed trusted certificate. A certificate is designated trusted when an X.509v3 Extended Key Usage extension field is present and contains "trustRoot". If no identity scheme is specified in the parameter exchange, this is the default scheme 🫶
Appendix E. Schnorr (IFF) Identity Scheme ✨
okay so the IFF scheme is giving "hide the group key and stop stressing about client keys" 🔐 It's super useful when the group key is concealed, because then client keys don't need protecting 💅 The catch (and it's a big one, bestie) is that when the server key gets refreshed, all hosts have to update the client key 😭 Figure 14 shows the setup: a set of public parameters plus a group key with both private and public components. The public component is the client key 🫶
Trusted
Authority
+------------+
| Parameters |
Secure +------------+ Insecure
+-------------| Group Key |-----------+
| +------------+ |
\|/ \|/
+------------+ Challenge +------------+
| Parameters |<------------------------| Parameters |
+------------+ +------------+
| Group Key |------------------------>| Client Key |
+------------+ Response +------------+
Server Client
Figure 14: Schnorr (IFF) Identity SchemeBy happy coincidence, the math behind IFF is similar to DSA 🦋 It's a modification of an algorithm described in [SCHNORR] and [STINSON] (p. 285). The parameters are generated by routines in the OpenSSL library, but only the moduli p, q and generator g actually get used. p is a 512-bit prime, g is a generator of the multiplicative group Z_p*, and q is a 160-bit prime that divides (p-1) and is a qth root of 1 mod p. In other words, g^q = 1 mod p. The TA rolls a private random group key b (0 < b < q), then computes the public client key v = g^(q-b) mod p. The TA distributes (p, q, g, b) to all servers using secure means, and (p, q, g, v) to all clients, not necessarily using secure means.
The TA hides IFF parameters and keys in an OpenSSL DSA cuckoo structure 🧚 The IFF parameters are identical to the DSA parameters, so the OpenSSL library can be used directly. The structure in Figure 15 gets written to a file as a DSA private key encoded in PEM. Unused structure members are set to one.
+----------------------------------+-------------+
| IFF | DSA | Item | Include |
+=========+==========+=============+=============+
| p | p | modulus | all |
+---------+----------+-------------+-------------+
| q | q | modulus | all |
+---------+----------+-------------+-------------+
| g | g | generator | all |
+---------+----------+-------------+-------------+
| b | priv_key | group key | server |
+---------+----------+-------------+-------------+
| v | pub_key | client key | client |
+---------+----------+-------------+-------------+
Figure 15: IFF Identity Scheme StructureAlice challenges Bob to confirm his identity with the following protocol exchange 💖
- Alice rolls random r (
0 < r < q) and sends to Bob. - Bob rolls random k (
0 < k < q), computesy = k + br mod qandx = g^k mod p, then sends(y, hash(x))to Alice. - Alice computes
z = g^y * v^r mod pand verifieshash(z)equalshash(x).
If the hashes match, Alice knows that Bob has the group key b 🎉 Besides making the response shorter, the hash makes it effectively impossible for an intruder to solve for b by observing a number of these messages 🙈 The signed response binds this knowledge to Bob's private key and the public key previously received in his certificate.
Appendix F. Guillard-Quisquater (GQ) Identity Scheme 👑
the GQ scheme is the one for when the server key needs refreshing from time to time without changing the group key 🔄 The NTP utility programs include the GQ client key in the X.509v3 Subject Key Identifier extension field. The big downside is that the group key has to be protected on both the server and the client 😬 A secondary downside is that when a server key gets refreshed, old extension fields stop working. Figure 16 shows the setup: a set of public parameters plus a group key that's used to generate private server keys and client keys.
Trusted
Authority
+------------+
| Parameters |
Secure +------------+ Secure
+-------------| Group Key |-----------+
| +------------+ |
\|/ \|/
+------------+ Challenge +------------+
| Parameters |<------------------------| Parameters |
+------------+ +------------+
| Group Key | | Group Key |
+------------+ Response +------------+
| Server Key |------------------------>| Client Key |
+------------+ +------------+
Server Client
Figure 16: Schnorr (IFF) Identity Schemeheads up, bestie: the caption under this diagram says "Schnorr (IFF)", but this section is about GQ 🙈 That's how the original text reads, so I've kept it exactly as written.
By happy coincidence, the math behind GQ is similar to RSA 🌸 The scheme is a modification of an algorithm described in [GUILLOU] and [STINSON] (p. 300) (with errors). The parameters are generated by routines in the OpenSSL library, but only the moduli p and q get used. The 512-bit public modulus is n=pq, where p and q are secret large primes. The TA rolls random large prime b (0 < b < n) and distributes (n, b) to all group servers and clients using secure means, since an intruder holding these values could impersonate a legitimate server 🚨 The private server key and public client key get constructed later.
The TA hides GQ parameters and keys in an OpenSSL RSA cuckoo structure 🍓 The GQ parameters are identical to the RSA parameters, so the OpenSSL library can be used directly. When generating a certificate, the server rolls random server key u (0 < u < n) and the client key, which is its inverse obscured by the group key: v = (u^-1)^b mod n. These values replace the private and public keys normally generated by the RSA scheme. The client key is conveyed in a X.509 certificate extension. The updated GQ structure in Figure 17 is written as an RSA private key encoded in PEM. Unused structure members are set to one.
+---------------------------------+-------------+
| GQ | RSA | Item | Include |
+=========+==========+============+=============+
| n | n | modulus | all |
+---------+----------+------------+-------------+
| b | e | group key | all |
+---------+----------+------------+-------------+
| u | p | server key | server |
+---------+----------+------------+-------------+
| v | q | client key | client |
+---------+----------+------------+-------------+
Figure 17: GQ Identity Scheme StructureAlice challenges Bob to confirm identity using the following exchange 💅
- Alice rolls random r (
0 < r < n) and sends to Bob. - Bob rolls random k (
0 < k < n) and computesy = ku^r mod nandx = k^b mod n, then sends(y, hash(x))to Alice. - Alice computes
z = (v^r)*(y^b) mod nand verifieshash(z)equalshash(x).
If the hashes match, Alice knows that Bob has the corresponding server key u 🥹 Besides making the response shorter, the hash makes it effectively impossible for an intruder to solve for u by observing a number of these messages. The signed response binds this knowledge to Bob's private key and the client key previously received in his certificate ✨
Appendix G. Mu-Varadharajan (MV) Identity Scheme 🔐✨
okay so the MV scheme is honestly the most interesting and flexible of the three challenge/response schemes 🧠, but it is devilishly complicated 😭. It's most useful when a small number of servers provide synchronization to a huge client population, and there's a real risk that servers and clients could get compromised, either between servers and clients or among the servers themselves 💀. The client population can be split into a modest number of subgroups, and each subgroup is tied to its own client key 🦋.
The TA (Trusted Authority) generates an intricate cryptosystem with encryption and decryption keys, plus a bunch of activation keys and their matching client keys 🎀. The TA can activate and revoke individual client keys without touching the client keys themselves, which is so clean 💅. The TA gives the servers an encryption key E, plus partial decryption keys g-bar and g-hat that depend on which keys are activated. The servers don't get any extra info, so they literally cannot pretend to be the TA 🙅♀️. The TA also gives each client j its own partial decryption keys x-bar_j and x-hat_j. Those don't need to change when the TA activates or deactivates any client key 👑. Clients don't get any further info either, so they can't pretend to be a server or the TA 🫶.
The scheme uses an encryption algorithm that's similar to El Gamal cryptography 🌸. It also uses a polynomial formed by expanding the product terms (x-x_1)(x-x_2)(x-x_3)...(x-x_n), as described in [MV] 📜. Heads up, the paper has significant errors and serious omissions 🙈. The cryptosystem is built 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. That still holds if both quantities get raised to the power k mod p 🔥. Finding E is equivalent to the discrete log problem, so that's the hard part 🧚.
The scheme is shown in Figure 18 🍓. The TA generates the parameters, the group key, the server keys, and the client keys (one for each client). All of these must be protected to prevent theft of service 🚨. Only the TA has the group key, and neither the servers nor the clients know it. In this sense, the MV scheme is a zero-knowledge proof 🌈.
Trusted
Authority
+------------+
| Parameters |
+------------+
| Group Key |
+------------+
| Server Key |
Secure +------------+ Secure
+-------------| Client Key |-----------+
| +------------+ |
\|/ \|/
+------------+ Challenge +------------+
| Parameters |<------------------------| Parameters |
+------------+ +------------+
| Server Key |------------------------>| Client Key |
+------------+ Response +------------+
Server Client
Figure 18: Mu-Varadharajan (MV) Identity SchemeThe TA hides the MV parameters and keys inside OpenSSL DSA cuckoo structures 🥚. The MV parameters are identical to the DSA parameters, so you can use the OpenSSL library directly, which is a huge win 🙌. The structures in the figures below get written to files as an fkey encoded in PEM 📁. Any unused structure members are set to one 1️⃣. Figure 19 shows the data structure the servers use, and Figure 20 shows the client data structure tied to each activation key 💜.
+---------------------------------+-------------+
| MV | DSA | Item | Include |
+=========+==========+============+=============+
| p | p | modulus | all |
+---------+----------+------------+-------------+
| q | q | modulus | server |
+---------+----------+------------+-------------+
| E | g | private | server |
| | | encrypt | |
+---------+----------+------------+-------------+
| g-bar | priv_key | public | server |
| | | decrypt | |
+---------+----------+------------+-------------+
| g-hat | pub_key | public | server |
| | | decrypt | |
+---------+----------+------------+-------------+
Figure 19: MV Scheme Server Structure +---------------------------------+-------------+
| MV | DSA | Item | Include |
+=========+==========+============+=============+
| p | p | modulus | all |
+---------+----------+------------+-------------+
| x-bar_j | priv_key | public | client |
| | | decrypt | |
+---------+----------+------------+-------------+
| x-hat_j | pub_key | public | client |
| | | decrypt | |
+---------+----------+------------+-------------+
Figure 20: MV Scheme Client StructureThe devil is in the details, but those details are beyond the scope of this memo 😤. If you want the steps for generating the cryptosystem, activating the keys, and generating the partial decryption keys, check [DASBUCH] (page 170 ff) 📖.
Okay, here's the challenge/response exchange where Alice challenges Bob to confirm his identity 🕵️♀️💕:
- Alice rolls a random r (0 < r < q) and sends it to Bob.
- Bob rolls a random k (0 < k < q) and computes the session encryption key E-prime =
E^k mod pand the partial decryption keys g-bar-prime =g-bar^k mod pand g-hat-prime =g-hat^k mod p. He encrypts x =E-prime * r mod pand sends (x, g-bar-prime, g-hat-prime) to Alice 🎁. - Alice computes the session decryption key E^-1 =
(g-bar-prime)^x-hat_j (g-hat-prime)^x-bar_j mod pand verifies that r =E^-1 x✅.
Appendix H. ASN.1 Encoding Rules 📦
ngl this part is a bit dry, but it matters 🤓. Certain value fields in request and response messages hold data encoded in ASN.1 distinguished encoding rules (DER) 💌. The BNF grammar for each encoding rule is given below, along with the OpenSSL routine the reference implementation uses for the encoding 🛠️. The object identifiers for the encryption algorithms and the message digest/signature encryption schemes are specified in [RFC3279] 🏷️. The particular algorithms needed for conformance are not specified in this memo 🤷♀️.
Appendix I. COOKIE Request, IFF Response, GQ Response, MV Response 🍪
The value field of the COOKIE request message holds a sequence of two integers, (n, e), encoded by the i2d_RSAPublicKey() routine in the OpenSSL distribution 🔑. In the request, n is the RSA modulus in bits and e is the public exponent 💖.
RSAPublicKey ::= SEQUENCE {
n ::= INTEGER,
e ::= INTEGER
}The IFF and GQ responses each contain a sequence of two integers, (r, s), encoded by the i2d_DSA_SIG() routine in the OpenSSL distribution ✨. In those responses, r is the challenge response and s is the hash of the private value 🦋.
DSAPublicKey ::= SEQUENCE {
r ::= INTEGER,
s ::= INTEGER
}The MV response contains a sequence of three integers, (p, q, g), encoded by the i2d_DSAparams() routine in the OpenSSL library 🌷. In that response, p is the hash of the encrypted challenge value, and (q, g) is the client portion of the decryption key 🫧.
DSAparameters ::= SEQUENCE {
p ::= INTEGER,
q ::= INTEGER,
g ::= INTEGER
}Appendix J. Certificates 🎀
okay bestie, certificates time 🎀 these are the little ID cards Autokey carries around. ngl the extension fields are doing a lot of work here, and they mostly mean what you'd expect, but there are some lowkey sneaky differences ✨ here's what Autokey version 2 uses:
- Basic Constraints. This one says what the certificate is basically for 🎀. It holds the string
critical,CA:TRUE, which means the field must be interpreted, and the private key tied to it can be used to sign other certificates. It's included for compatibility, but Autokey makes no use of it, periodt 💅 - Key Usage. This one spells out what the public key inside is meant for 🔑. It holds
digitalSignature,keyCertSign, which means that key can verify signatures on data and on other certificates. Again, it's only there for compatibility, and Autokey doesn't use it 🙈 - Extended Key Usage. This one refines the public key's purpose even more ✨ and it only shows up in self-signed certificates. It holds
Privateif the certificate is designated private, ortrustRootif it's designated trusted. A private certificate is always trusted, no debate 👑 - Subject Key Identifier. This one carries the client identity key used in the GQ identity scheme 🦋 and it's only present if the GQ scheme is in use.
The value field holds an X.509v3 certificate encoded by the i2d_X509() routine in the OpenSSL distribution. The encoding follows the rules in [RFC5280], including the X.509v3 extension fields 🌸
Here's the overall shape of the certificate:
Certificate ::= SEQUENCE {
tbsCertificate TBSCertificate,
signatureAlgorithm AlgorithmIdentifier,
signatureValue BIT STRING
}The signatureAlgorithm is the object identifier of the message digest/signature encryption scheme used to sign the certificate. The signatureValue is computed by the certificate issuer using this algorithm and the issuer private key 🔐
Next up, the TBSCertificate, which is the bulk of the good stuff 🧚
TBSCertificate ::= SEQUENCE {
version EXPLICIT v3(2),
serialNumber CertificateSerialNumber,
signature AlgorithmIdentifier,
issuer Name,
validity Validity,
subject Name,
subjectPublicKeyInfo SubjectPublicKeyInfo,
extensions EXPLICIT Extensions OPTIONAL
}The serialNumber is an integer guaranteed to be unique for the generating host. The reference implementation uses the NTP seconds from when the certificate was generated ⏰ The signature is the object identifier of the message digest/signature encryption scheme used to sign the certificate. It must be identical to the signatureAlgorithm, so no sneaky mismatches allowed 🙅♀️
CertificateSerialNumber
SET { ::= INTEGER
Validity ::= SEQUENCE {
notBefore UTCTime,
notAfter UTCTime
}
}The notBefore and notAfter define the period of validity as defined in Appendix B 📅
SubjectPublicKeyInfo ::= SEQUENCE {
algorithm AlgorithmIdentifier,
subjectPublicKey BIT STRING
}The AlgorithmIdentifier specifies the encryption algorithm for the subject public key. The subjectPublicKey is the public key of the subject 🫶
Last but not least, the extensions and names:
Extensions ::= SEQUENCE SIZE (1..MAX) OF Extension
Extension ::= SEQUENCE {
extnID OBJECT IDENTIFIER,
critical BOOLEAN DEFAULT FALSE,
extnValue OCTET STRING
}
SET {
Name ::= SEQUENCE {
OBJECT IDENTIFIER commonName
PrintableString HostName
}
}For trusted host certificates, the subject and issuer HostName is the NTP name of the group. For all other host certificates, the subject and issuer HostName is the NTP name of the host 🌈 In the reference implementation, if these names aren't explicitly specified, they default to the string returned by the Unix gethostname() routine, with the trailing NUL removed. For anything other than self-signed certificates, the issuer HostName is the unique DNS name of the host signing the certificate 🌸
⚠️ Heads up on revocation: the Autokey protocol itself has no provisions to revoke certificates. So the reference implementation is purposely restarted about once a week, which leads to the certificate being regenerated and the Autokey protocol restarting. This restart isn't enforced by the Autokey protocol itself, but rather for NTP functionality reasons 😭
Each group host operates with only one certificate at a time and constructs a trail by induction 🔗 Since the group configuration must form an acyclic graph, with roots at the trusted hosts, it doesn't matter which of the possibly several signed certificates gets used. The reference implementation chooses a single certificate and operates with only that certificate until the protocol is restarted 💖
Authors' Addresses 🦋
Brian Haberman (editor) The Johns Hopkins University Applied Physics Laboratory 11100 Johns Hopkins Road Laurel, MD 20723-6099 US
Phone: +1 443 778 1319 EMail: brian@innovationslab.net
Dr. David L. Mills University of Delaware Newark, DE 19716 US
Phone: +1 302 831 8247 EMail: mills@udel.edu
📦 where this page comes from
- ietf: rfc5906 2010-06
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms