Re: [Ntp] An NTPv5 design sketch

Great Daniel.

I’d like to add that we also need to consider the topic of 
metrological traceability.
Technically the control fields as described in „Guidelines for 
Defining Packet Timestamps“ might be applied to transport the 
necessary information to enable traceability.

Dieter

On 12 Apr 2020, at 18:19, Daniel Franke wrote:

> Rendered version:
> https://gist.github.com/dfoxfranke/4ca0443b6ff6e0473578cf3827b9ea7f
>
> # Overview
>
> ΤΗ ΚΑΛΛΙΣΤΗΙ!
>
> This is a sketch of a proposed NTPv5 design (by no means a complete
> spec, but hopefully good enough to make the concepts clear). It's a
> fairly ambitious step forward from previous versions, almost but not
> quite a green field design.  I say "almost" because it retains a
> couple limited backward-compatibility constraints:
>
> 1. It must be possible to cleanly multiplex NTPv5 with NTPv4 (and
>    earlier) on the same port. Basically the just means keeping the
>    version field in the same place.
>
> 2. It must be possible to discipline your clock from a mix of NTPv5
>    and NTPv4 sources.
>
> That said, the reader should still find much that is familiar. We've
> learned a lot in the nearly 35 years that NTP has been in operation,
> but plenty of those lessons have been about what works and not just
> about what doesn't!
>
> This design includes *all the goodies* — just about everything from
> the [trac 
> wishlist](https://trac.ietf.org/trac/ntp/wiki/NtpVersionFourIssues)
> is addressed here. Some highlights follow:
>
> * The packet structure has been completely reworked, aside from
>   retaining the version field as previously mentioned.
>
> * Network Time Security is a mandatory and integral part of the
>   protocol. NTS-related fields are a part of the base packet rather
>   than extension. All information that can be encrypted, is, and
>   clients do not send any information servers beyond what is strictly
>   necessary for the server to construct a response.
>
> * All communication in NTPv5 is unicast between a stateful client and
>   a stateless server. Behavior analagous to symmetric mode of NTPv4 is
>   implemented in NTPv5 by two endpoints each functioning as a client
>   of the other. The broadcast mode has been eliminated.
>
> * NTPv4's interleaved timestamp functionality is replaced by a
>   distinct "follow-up" message, similar to the eponymous functionality
>   in PTP.
>
> * NTPv4's "refid" mechanism, intended to detect one-degree timing
>   loops, is replaced by a new mechanism based on Bloom filters that
>   works out to arbitrary degree.
>
> * Timestamps are now based on the TAI timescale, and time packets
>   carry a UTC-TAI offset and more detailed information about recent or
>   upcoming leap seconds.
>
> * I adopt PTP's 80-bit timestamp format.
>
> * Time packets carry both an absolute clock (subject to step
>   adjustments) and a (stable) difference clock.
>
> * Time packets carry an unencrypted and unauthenticated correction
>   field intended for manipulation by middleboxes. The function of this
>   field is analogous to PTP's concept of transparent clocks.  We
>   define a value for the Router Alert IP option to signal to
>   middleboxes that this behavior is desired.
>
> * Methods for selecting among time sources, filtering noise, nd
>   disclipining the local clock are not discussed in this sketch, and I
>   propose that they no longer be a normative part of the standard. We
>   specify only as much as is necessary to define protocol semantics
>   and to ensure global stability among heterogenous implementations.
>
> # Additions to NTS-KE
>
> NTS-KE works the same way for NTPv5 as it does for NTPv4. We allocate
> a new NTS Next Protocol ID to represent NTPv5 and define new NTS-KE
> record types "New Cookie For NTPv5", "NTPv5 Server Negotiation", and
> "NTPv5 Port Negotiation" whose structure and semantics are identical
> to their NTPv4 counterparts.
>
> We add one additional NTS-KE record, "Request Address-Bound NTPv5
> Cookies", whose body is empty and whose critical bit is unset. When
> the client includes this record in an NTS-KE request, it is asking
> that the cookies that the server returns be cryptographically bound to
> the client's network address, such that the NTP server will reject
> them as invalid if the client sends them from any other
> address. Normally such a restriction is undesirable, because it
> interacts poorly with mobile clients and certain NATs and therefore
> would lead to a less reliable protocol.  However, it makes possible
> certain features which would otherwise be unsafe.
>
> Most of NTPv5 is designed to prevent DDoS amplification: response are
> never larger than the request they are responding to. However, the
> "follow-up" feature is an exception to this, since the server sends
> back two packets in response to a single packet from the
> client. Address-bound cookies prevent this from being abused due to
> the difficulty of obtaining a cookie bound to a spoofed
> address. Servers will be mandated to send follow-up messages only to
> clients which present address-bound cookies, and clients will be
> advised to request address-bound cookies if and only if they plan to
> utilize the follow-up message feature.
>
> # Preliminaries on packet structure
>
> Throughout this document I'll be using the TLS presentation language
> to describe packet structure; see RFC 8446, section 3. Of the two
> array styles specified there (triangular brackets for arrays preceded
> by their length, square brackets for ones that are not), I use use
> only the [] style, and the corresponding length field is always
> explicit elsewhere in the message.
>
> To be friendly to hardware implementations, all variable-length fields
> are padded out to a multiple of 4 octets; the length field gives the
> *unpadded* length which is then rounded up to the next multiple of
> four to obtain length inclusive of padding. We'll use the following
> type to conveniently represent an opaque field that has padding at the
> end of it:
>
> ```
> struct {
>   opaque data[4];
> } padded;
> ```
>
> Furthermore, all 1, 2, and 4-octet fields are generally arranged so as
> to be self-aligned, and longer fields are arranged to have 4-octet
> alignment. Timestamps, which follow the format of PTPv2, are slight
> exception to this:
>
> ```
> struct {
>   int48 seconds; // SI seconds, has a range of about ±4.46 million 
> years
>   uint32 nanoseconds; // SI nanoseconds, ranging [0..999999999]
>   uint16 fracs; // 1/65536ths of a nanosecond
> } Timestamp;
> ```
>
> Although they partly follow the rule by being 12 octets long and
> aligned to 4 octets everywhere they occur, the `uint32 nanoseconds`
> has odd alignment.
>
> In any case, the padding rules are exactly what is specified in this
> grammar; there is no implicit additional padding.
>
> # Top-level packet structure
>
> Every NTPv5 packet has the same top-level format: two fixed octet 
> giving
> the version number, a two octet packet type, and then a type-dependent
> body.
>
> ```
> enum {
>   request(0),
>   response(1),
>   request_with_correction(2),
>   response_with_correction(3),
>   nts_nak(4),
>   (65535)
> } PacketType;
>
> struct {
>   /* Keep this octet fixed like this for all future versions. NTPv6
>      and beyond should continue with VN=5 here, and give their actual
>      version in the next octet. */
>   uint8 legacy_li_vn_mode = 0xe8; // LI = 3 (unsync), VN = 5, Mode = 0
>
>   /* Version field gets a whole octet from now on rather than just 3 
> bits */
>   uint8 version = 5;
>
>   PacketType packet_type;
>
>   select(Packet.packet_type) {
>     case request:                  NtsData;
>     case response:                 NtsData;
>     case request_with_correction:  NtsDataWithCorrection;
>     case response_with_correction: NtsDataWithCorrection;
>     case crypto_nak:               NtsNak;
>   } body;
> } Packet;
>
> struct {
>   uint8 cookie_length; //Always zero in response packets
>   uint8 nonce_length;
>   uint16 ciphertext_length;
>   opaque unique_identifier[32];
>   padded cookie[pad(cookie_length)]; //Always zero-length in response 
> packets
>   padded nonce[min(16,pad(cookie_length))]; //Padded up to a minimum 
> 16 octets
>   padded ciphertext[pad(ciphertext_length)];
> } NtsData;
>
> struct {
>   Correction correction;
>   NtsData nts_data;
> } NtsDataWithCorrection;
>
> struct {
>   opaque unique_identifier[32];
> } NtsNak;
>
> ```
>
> The `Packet` structure is a cryptographic envelope: except for the
> `Correction` structure (fully defined later) which is intentionally
> manipulable by middleboxes, it exposes only as much information as is
> needed for the receiver to locate, authenticate, and decrypt the
> ciphertext.
>
> If you are already familiar with NTS for NTPv4, then the meaning of
> the fields of `NtsData` should be self-explanatory. While they are now
> syntactically part of the base packet rather than being scattered
> across NTS extension fields, they have basically the same semantics as
> those corresponding extensions. There is only a slight difference in
> how the associated data for RFC 5116 is constructed. In NTPv4, the
> Associated Data is whatever appears on the wire from the start of the
> packet to the start of the NTS Authenticator and Encrypted Extensions
> Fields extension field. In NTPv5, the associated data is exactly the
> following structure:
>
> ```
> struct {
>   uint8 legacy_li_vn_mode = 0xe8;
>   uint8 version = 5;
>   PacketType packet_type;
>   uint8 cookie_length;
>   uint8 nonce_length;
>   uint16 ciphertext_length;
>   opaque unique_identifier[32];
>   padded cookie[pad(cookie_length)];
> } NtsAd;
> ```
>
> The `NtsAd` structure is a pseudo-type which never crosses the wire as
> such, but is formed by cpying the corresponding fields out of `Packet`
> and `NtsData`. Authenticating some of these fields is redundant but
> helps guard against certain implementation mistakes.
>
> Decrypting the ciphertext gives a structure of type `NtsPlaintext`:
>
> ```
> enum {
>   time_request(0),
>   time_response(1),
>   followup_response(2),
>   source_request(3),
>   source_response(4),
>   (65535)
> } MessageType;
>
> struct {
>   MessageType msg_type;
>   uint8 cookie_len;
>   uint8 num_cookies;
>   /* num_cookies cookies, each with an unpadded length of cookie_len, 
> and
>      padding added to the end of each individual cookie. */
>   padded cookies[num_cookies * pad(cookie_len)];
>   select (NtsPlaintext.msg_type) {
>     case time_request:          TimeRequest;
>     case time_response:         TimeResponse;
>     case source_request:        SourceRequest;
>     case source_response:       SourceResponse;
>     case followup_response:     FollowupResponse;
>   } body;
> } NtsPlaintext;
> ```
>
> Here we have a bit more machinery for NTS cookies, and a message type
> and corresponding body where all the information actually related to
> time synchroniziation lives. In request packets, the `cookies` field
> contains placeholders, and in response packets it contains fresh
> cookies being provided to the client. Again, while I have made the
> syntactic change of moving these from extension fields to the base
> packet, the semantics are the same as they are in NTPv4.
>
> # Time messages
>
> Unless extensions are present, the body of a time request has only
> one bit of any interest; the rest is just anti-amplification padding.
> When bit 2 of the `flags` octet is set, the client is requesting that
> the server send a follow-up packet to provide a drivestamp.
>
> ```
> struct {
>   uint8 flags; /* bit 2: set = follow-up requested
>                   bit 0-1, 3-7: unused, MUST be clear */
>   opaque anti_amplification_padding[103];
>   Extension extensions[]; // Each extension is self-delimiting, and 
> we're at
>                           // the end of the extension list when we're 
> at the
>                           // end of the structure
> } TimeRequest;
> ```
>
> Now finally we reach the meat: the `TimeResponse` structure where all
> the core time synchronization information lives. Inline comments
> briefly describe each field and then I'll circle back to highlight
> some details.
>
> ```
> struct {
>   uint8 flags; /* bit 0: set = synchronized, clear = unsynchronized
>                   bit 1: set = leap insertion, clear = leap deletion
>                   bit 2: set = expect follow-up
>                   bit 3-7: unused, MUST be clear */
>
>   /* Same meaning as in NTPv4 */
>   int8 precision;
>
>   /* Please don't send me an average of more than one packet per
>      2**throttle seconds once you've stabilized */
>   int8 throttle;
>
>   /* Please don't send me more than one packet over any
>      2**burst_throttle second interval */
>   int8 burst_throttle;
>
>   /* Randomly-generated value that identifies this server */
>   opaque source_id[16];
>
>   /* Incremented whenever we change upstream sources or whenever one
>     of our upstream sources changes its own source_seqno. */
>   uint32 source_seqno;
>
>   /* These have no specified epoch; they get set arbitrarily on
>      startup and never step. They may receive frequency discipline but
>      never offset discipline (c.f. RAD clocks). */
>   Timestamp recv;
>   Timestamp xmit;
>
>   /* Add this amount to convert the recv and xmit timestamps to a TAI
>      timestamp (relative to midnight 1970-01-01 TAI). This estimate
>      gets an immediate step adjustment any time we receive a new data
>      point. */
>   Timestamp tai_loc_offset;
>
>   /* Error estimates for tai_loc_offset (replaces root
>      delay/dispersion) */
>   Timestamp max_error;
>   Timestamp rms_error;
>
>   /* The TAI time of the last-announced leap event, which might be
>      past or future. Flag bit 1 says whether it's an insertion or
>      deletion */
>   Timestamp leap_event;
>
>   /* UTC-TAI offset after the completion of the above event */
>   int32 utc_tai_offset;
>
>   /* Counts the number of leap events that have ever historically
>      occurred */
>   uint32 leap_seqno;
>
>   Extension extensions[]; // Each extension is self-delimiting, and 
> we're at
>                           // the end of the extension list when we're 
> at the
>                           // end of the structure
> } TimeResponse;
> ```
>
> The `recv` and `xmit` timestamps are captured at the same point as
> they are in NTPv4 (the recv timestamp the moment the request is
> received, the xmit timestamp as nearly as possible to the moment the
> response is sent). However, these timestamps don't have a defined
> epoch so they don't actually tell you the time as such: they're just
> timers that advance by one second per second of real time — 
> difference
> clocks as opposed to absolute clocks. To get an absolute timestamp, 
> you
> have to add `tai_loc_offset` to them.
>
> `tai_loc_offset` represents the server's best available estimate of
> the offset between its local monotonic clock (what it samples when it
> captures `recv` and `xmit` timestamps) and TAI. It's allowed to jump
> around every time the server gets a new data point that improves its
> estimate. So you can't rely on `xmit + tai_loc_offset` to be at all
> stable; it can even move backward. In any computation that assumes
> stable monotonic progression, just use `recv` and `xmit` by 
> themselves.
>
> While `recv` and `xmit` are guaranteed to never receive step 
> adjustments,
> there is no guarantee about any higher derivatives. For example if a 
> server
> thinks its clock is 5ppm slow, it can immediately speed it up by 5ppm; 
> it
> does not have to gradually accelerate.
>
> If the `source_id` field has changed from one time response to
> another, then `recv` and `xmit` timestamps from before the change are
> no longer comparable to the one after. The server may have rebooted
> and lost its clock.
>
> Since we've adopted PTPv2's timestamp format, we also adopt their
> epoch of January 1, 1970 TAI rather than the NTPv4 epoch of 1900.
>
> `max_error` gives a maximum error bound on `tai_loc_offset`, and
> `rms_error` gives the square root of the expected squared error.
>
> We don't specify what kind of estimator `tai_loc_offset` is, e.g. a
> minimum-mean-squared-error estimate versus a maximum likelihood
> estimate, and we don't require that the estimator be unbiased.
> However, since `rms_error` is based on mean-squared error, using any
> estimator other than a MMSE estimator requires reporting a larger
> `rms_error` than one otherwise might be able to.
>
> The `leap_event` and `utc_tai_offset` fields along with the `leap
> insertion/deletion` flag bit are used in converting from TAI to UTC
> and notifying of upcoming or recent leap events. `leap_event` gives
> the TAI timestamp as of the conclusion of the most recently-announced
> leap second event, which might be in the future or might be in the
> past. `utc_tai_offset` gives the UTC-TAI offset as of the conclusion
> of that event, and the flag bit tells whether the leap event is/was an
> insertion or a deletion.
>
> The `throttle` and `burst_throttle` fields replace KoD RATE messages.
> Rather than the server sending KoDs to clients that query it too
> frequently (which burdens the server with maintaining a table to keep
> track of this), it simply communicates its policy on what query rate
> is acceptable and clients are expected to follow it.
>
> The `source_seqno` field is part of NTPv5's loop-detection scheme. Its
> meaning and purpose will be explained in a later section.
>
> Extensions have the same type-length-value format that they do in 
> NTPv4:
>
> ```
> struct {
>   uint16 type;
>   uint16 len;
>   padded body[pad(len)];
> } Extension;
> ```
>
> But, as throughout NTPv5, the length field gives the unpadded length
> rather than the padded one. Unlike in NTPv4, NTPv5 extension bodies
> have no minimum length since we're free of the syntactic ambiguities
> that force RFC 7822 to require one.
>
> This design defines no extension fields. Extension fields are only one
> of two ways that NTPv5 can be extended; new message types can be
> defined as well. Generally, extension fields should be preferred only
> when the information they carry is somehow coupled to the time data in
> the same packet (such as, to pick a silly example, adding additional
> bits of precision to a timestamp). Otherwise it is probably better to
> define a new message type instead.
>
> # Follow-up messages
>
> When the client sets flag bit 2 in a `TimeRequest` and the server sets
> bit 2 in its `TimeResponse`, it should be immediately followed by a
> `FollowupResponse` which provides a corrected `xmit` stamp. The 
> corrected
> stamp can be based on a drivestamp from the emitting NIC and therefore
> more accurate than the original.
>
> ```
> struct {
>   Timestamp corrected_xmit;
> } FollowupResponse;
> ```
>
> # Source messages and loop detection
>
> NTPv5 uses a loop-detection mechanism based on Bloom filters that
> works for a large number of sources out to arbitrary degree. At
> startup, each server randomly assigns itself a 128-bit `source_id`.
> It then sends each of its upstream sources a `SourceRequest` message 
> —
> just a bunch of padding, no meaningful fields.
>
> ```
> struct {
>   opaque anti_amplification_padding[532];
> } SourceRequest;
> ```
>
> It gets back a `SourceResponse` from each one.
>
> ```
> struct {
>   opaque source_id[16];
>   uint32 source_seqno;
>   opaque bloom_filter[512];
> } SourceResponse;
> ```
>
> Each source has populated a Bloom filter based on its own sources
> further upstream. Our newly-online server now builds a Bloom filter of
> its own. First, it takes the union (bitwise OR) of all the filters
> from upstream. Then it inserts the `source_id`s of its immediate
> upstream stources into the filter. Since source IDs are already
> uniformly random, the hash functions we employ can be very simple.
> Split the 128-bit `source_id` into ten 12-bit values `h_0`, `h_1`, 
> …,
> `h_9`, discarding the last 8 bits. Then for each `i`, set the `h_i`'th
> bit in the filter.
>
> Once the new server has computed its filter and finished
> synchronizing, it comes online with a `source_seqno` of 0. It then
> watches the `source_seqno`s in the time responses from its
> sources. Whenever one of them changes, it sends a new `SourceRequest`
> to that server, recomputes its filter, and increments its own
> `source_seqno`. However, if the new filter that comes back includes
> our own `source_id`, this indicates a probable timing loop and we
> should drop that source.
>
> The use of Bloom filters means that timing loops will always be
> detected but there will be occasional false positives. With the filter
> size chosen, we can scale to a few hundred transitive upstream sources
> before the probability of a false positive becomes non-negligible,
> which should be sufficient.
>
> Endpoints that act only as clients and not as servers don't have to
> bother doing any of this since they can't possibly be involved in
> timing loops.
>
> # Correction fields
>
> The `Correction` structure is deliberately not encrypted or
> authenticated, and is intended for maniplation by middleboxes. It is
> similar in function to PTP's transparent clocks.
>
> Packets which contain correction fields must also include a Router
> Alert IP option (RFC 2113 & 2711) in order to signal to middleboxes
> that they want them modified. Middleboxes must rely strictly on this
> option (and not merely on something looking like a syntactically-valid
> NTPv5 packet going over the NTP port) to detect that they are handling
> NTPv5 traffic and that such modifications are desired.
>
>
> ```
> struct Correction {
>   Timestamp correction;
>   uint32 path_crc;
> };
> ```
>
> `correction` is initially 0 when time requests initiate from the
> client. Compliant middleboxes increment it by the amount of time that
> the request spends queued. The receiving NTP server copies the
> correction field it receives into the response. Middleboxes on the
> return path decrement the response's correction field by the amount of
> time that the response spends queued.
>
> `path_crc` is initially 0 when time requests initiate from the
> client. Compliant middleboxes self-assign an identifier at random and
> add their identifier to the CRC (where "add" here means the CRC group
> operation). The receiving NTP server copies the `path_crc` field it
> receives into the response. Middleboxes on the return path subtract
> their self-assigned identifier from the `path_crc`. The client 
> receiving
> the response verifies that the `path_crc` is 0. If not, there is a
> routing asymmetry and the correction should be discarded.
>
> Correction fields can, obviously, be maliciously altered by a MitM in
> order to cause the client to obtain a bogus time estimate. Clients
> which pay attention to correction fields must set a limit on the
> largest correction they will accept. A correction whose absolute value
> is in excess of one half the measured RTT is definitely bogus and
> should always be rejected, but clients may choose to set bounds
> tighter than this.
>
> _______________________________________________
> ntp mailing list
> ntp@ietf.org
> https://www.ietf.org/mailman/listinfo/ntp