[Ntp] DTLS Lite Security for the Network Time Protocol.

[Harlan Stenn <[e-mail]>]

More from Dave Mills:

DTLS Lite Security for the Network Time Protocol (NTP)
David L. Mills
Harlan Stenn
30 July, 2018

Abstract

This document explores the security architecture and protocols for the
network time protocol NTP. It proposes a set of engineering principles
based on RFC5905, along with a redesign of the Autokey security scheme
described in RFC5906.

The proposed security scheme is based on the Datagram Transport Layer
Security (DTLS)and called DTLS Lite. DTLS Lite is simple yet resistant
to protocol errors and key replacement. It involves various agreement
and signature algorithms leading to a secure means for protecting NTP
from wiretap and middleman attacks.

DTLS Lite has several advantages over Autokey, including:

o a compact and efficient design using elements from the existing code base,

o a signature trail that avoids a certificate cache. this is called the
provenance scheme, as in the provenance of a painting.

o a hash scheme that works for all packets, including handshake packets, and

o a unified design for all NTP modes, including symmetric, client/server
and broadcast modes.

1. Introduction

Recent internet drafts have described a proposed security architecture
and protocol NTS, together with its application to NTP. This model,
while technically sound, is a significant departure from the current NTP
model described in RFC5905. This document describes how and why these
differences occur and proposes a modified design that might mitigate
these differences while reducing complexity and overhead.

One of the most important issues during the two decades of NTP security
development has been to design the security means as an integrated
system. This involves careful consideration of protocol design, security
means and error recovery. Everything depends on everything else, and a
tiny change may have unintended consequences.

In addition, the Autokey public key security scheme described in RFC5906
was designed and implemented over twenty years ago. Time and Moore's law
have caught up to it. Back then, it took over one second to calculate a
public key signature. Today, it takes only a millisecond or two.

This document outlines a proposed replacement for Autokey. The scheme is
based on the Diffie-Hellman agreement algorithm, which results in an
economical implementation and low running time. This document suggests a
variant of this algorithm popularly known as the Station to Station
Protocol, which provides cryptographic authentication of the source.

Due to its similarity to the proposed NTS model based on DTLS, the new
protocol is called DTLS Lite. However, the new protocol is greatly
simplified and free from complicated key computations, as well as
unecessary protocol functions.

DTLS Lite has several advantages over DTLS. Among these are the following:

o DTLS Lite is inherently symmetric. For symmetric peers A and B,the
handshake protocol initiated by A has the same results as when initiated
by B,

o prestored and/or agreed hash keys are used for all packets, including
handshake exchanges,

o improved accuracy due to the absence of extension fields in other than
handshake exchanges,

o multiple, overlapping security grouts can be supported, eaach
identified by a private group key,

o in interleave mode DTLS Lite can be used to compensate for the device
delay, avoiding itinerant messages and messy UDP checksum compensation,

o the certificate trail or provenance is automatically verified without
the use of certificate caches and

o broadcast mode does not require a two-way path between server and
client, since athentication is based on public key cryptography.

The principal goal in the DTLS Lite design is to maximize
synchronization accuracy, rather than conform to a particular public
protocol model. If the latter is desired, NTP security can be achieved
using a straightforward implementation of DTLS.

Autokey in its present form is an optional feature of the reference
implementation. In fact,the significant proposed changes in this
document are to the public key layer. The other protocol layers in the
design, including the format, private key and on-wire layers, are
substantially unchanged.

The DTLS Lite handshake protocol is a sequence of exchanges parasitic on
the on-wire layer. Handshake messages are transmitted in NTP extension
fields. Extensin fields are not ordinarily used once the handshake
protocol has terminated. However, extension fields can be defined for
special functions unrelated to the handshake protocol.

This document discusses engineering issues important to the DTLS  Lite
security design. It does not discuss packet formats, current and
proposed NTP extension field formats, other than for illustration. It
does not discuss cryptographic keys or certificate generation.

2. Protocol Basics

For the purposes of this document, a protocol data unit (PDU) is an NTP
extension field, sometimes called a message. One or more messages can be
appended to an NTP packet header. Each message consists of a function
octet, modifier octet, two-octet data length, and followed by the data
itself, zero padded to a four- octet boundary.

NTP packets are transmitted at poll intervals according to the NTP
on-wire protocol.  Since the extension fields piggyback on these
packets, the security protocol is constrained to these intervals.

2.1 Message Size

It is convenient to restrict the maximum message size to some reasonable
value in the order of 512 bits or 64 octets.  This is the maximum size
of a public key, signature, parameter vector or encrypted cookie. A
certificate is twice this size, including a public key and its signature.

Only two exchanges in the protocol described here have more than one
message, the rest have only one. The maximum total packet size,
including the NTP header plus all messages must be less than the MTU of
1500 octets. Extra long certificates in the order of 5000 octets must be
used only in certificate authorities external to the NTP network. This
avoids fragmentation an its evil consequences.

2.2 Message Structure

Ordinarily, the function octet for both the requests and associated
response messages is the same,except for a response indicator bit. The
response indicator bit is set to zero for a request message and to one
for the associated response message. The remaining seven bits encode the
Autokey version number and message type. The version number for the
proposed DTLS Lite protocol is 3. This is independent of the NTP version
number, currently 4.

Multiple messages can be split over multiple NTP packets as necessary,
due to packet length restrictions. Multiple responses can be associated
with a single request. If a timeout occurs before receiving a response
to a previous request, the request is sent again with new state
variables in the next NTP packet. A response without a previous matching
request is discarded. If a request is received before the response to a
previous request, the result is a protocol error.

Once the protocol handshake has concluded, messages other than the
message authentication code MAC appended to each packet are not normally
used. The MAC uses a shared hash key. The hash key is used to
authenticate each packet using a selected hash algorithm.

2.3 Message Exchanges


An exchange is a volley consisting of a single request message to a host
followed by one or more response messages from that host. In general,
each exchange performs a single function independent of other exchanges.

3. Backward Compatibility

It is important that the current cryptographic keys model and the NTP
modes, including client/server, symmetric, broadcast/multicast/manycast
and interleave modes, be preserved. The existing symmetric key design,
including the keys file, message authentication code (MAC) format and
selection of hash algorithm,should also be retained. It is not necessary
to preserve the current Autokey scheme itself, although some elements of
this scheme remain in this proposal.

It is important to retain the capability to reconfigure the NTP subnet
in response to link or host failures. In certain configurations this
might create some kind of vulnerability to hostile attacks. Creative
defenses against such attacks are discussed later in this report.

3.1 Infrastructure

The fundamental principle in the NTP engineering design is that no
explicit infrastructure other than the base network is assumed. This
means that neither DNS nor PKI certificate management infrastructure is
available. In particular, private/public keys and certificates must be
generated by the host that uses them. Since certificates cannot be
authenticated by outside means, there is a possibility of a middleman
attack where the attacker injects its certificate on the trail leading
to the certificate authority.

In the original Autokey design there were optional means to verify the
certificate trail using the identity exchange. This exchange is no
longer needed, since key zero, and the timestamp tests, described below,
perform a similar function.

4. Diversity

In the current NTP architecture, the time and security operations
proceed independently for each association, as described below. Security
for each associations is managed separately. each association is
assigned aN INDIVIDUAL group hash key, while the server or client host
has a separate GROUP hash key.

an association has valid time when the dispersion has fallen below the
threshold. The security is valid when the first signature is verified.
An association is valid when both the time and security are valid.

The associations are selected by the clock filter, Byzantine agreement,
intersection and clustering algorithms. It does not seem feasible to
"loosely synchronize" the system clock with this design, since only
after these algorithms have completed is the system clock eligible to be
synchronized.

5. Two-Way Issues

In broadcast mode, a two-way path between the broadcast server and
client is necessary to compute the round-trip delay. However, in some
supported configurations a return path is not available so the
round-trip delay cannot be computed and must be estimated. It is not
then possible to retrieve any server data other than the broadcast
packet itself. The reference implementation supports both a one-way and
two-way design using an optional client server exchange to compute the
round-trip delay followed by one-way broadcast packets.

6. Access Control

The current reference implementation includes access controls based on
IP address filtering and rate management parameters. Additional access
controls are suggested in this report. There is no need for additional
access control function in the cryptographic algorithms. Other public
key schemes may wish to use an access exchange providing a session key
for the duration of the handshake protocol, although the on-wire
protocol layer provides a similar function.

Rate management issues are a critical consideration in the security
protocol design. For example, a busy NIST server processes over 3000 NTP
packets per second. As learned from experience, the primary component of
CPU cycles is the per-packet overhead, some thousands of instructions
per packet. This overhead is substantially independent of packet length
or number of extension fields.

The current reference implementation limits the minimum packet headway
and minimum average headway to configured values. Clients that violate
these limits are denied service. For example, at NIST, a significant
minority of clients routinely violate the minimum headway requirement of
two seconds and so are discarded. An optional Kiss o' Death (KoD) is
available to quench compliant clients.

The rate management parameters apply both to the NTP packet flows, as
well as the security function. As this function often involves multiple
packets, this may result in excessive acquisition times. The means
described below provide a way to minimize the number of packets to
complete the security function.

7. NTP Secure Network Engineering Principles

An NTP secure network consists of an acyclic, directed graph organized
as a tree with nodes descending from the root node. The nodes correspond
to the NTP hosts and the edges correspond to the network paths between
them. The network paths include one or more physical links,
interconnected by routers and firewalls. Note that the network topology
can change from time to time due to host or network path failures.

The NTP network can contain one or more trees, where each tree is
assigned to a secure group. Each group host is considered trusted, while
those hosts outside the group are considered potential traitors. A
number of groups can be arranged as a forest, where an edge of one group
can terminate on a host of a different group. The groups  of the forest
usually have different root servers as trust anchors. Each trust anchor
and its descendents is associated with a private group hash key, which
is used for handshake exchanges.

For the purposes of network security, each host can communicate directly
only with its immediate upstream and downstream hosts. A host can
operate as a client or server or both at the same time. Each host
includes a set of public/private keys and one or more certificates.

NTP group security  is based on two functions, a cryptographic hash
algorithm used to verify packet integrty, and a recursive provenance
function used to verify the certificate trail. Each signed certificate
confirms authenticity of its public key. Public/private keys and host
certificates are generated individually by each host.

The goal of the security scheme is to authenticate each server to the
next downstream client using one or more certificates.  The provenance
scheme evolves as follows: in the basis step, the certificate authority
host is designated proventic by some means external to the network. For
instance, an external certificate authority can sign the NTP root
certificate. In the induction step, each client in the network
separately requests its immediate ascending server to sign its
certificate. If the signature is valid and the server is designated
proventic, the client is also designated proventic. If the server is not
proventic, the request is ignored and the client request is repeated
after timeout.

In this fashion, eventually all host certificates are signed and
designated proventic. Thus, proventicity flows in steps from the
certificate authority to each downstream host in the network.

Once generated, certificates have a specific assigned lifetime. Some
time before expiration of the lifetime, a new certificate must be
generated with a new lifetime. This does not affect the authenticity or
other parameters of the current certificate. On the other hand, a new
set of public/private keys require the certificate to be regenerated and
its public key to be re-signed by the server. The scheme to do this is
straightforward, but intricate, as described below.

A host is considered provisionally authentic when the shared hash key
signatures have been verified. The host is considered fully proventic
when its certificate has been signed by the next ascending host on the
trail to the certificate authority.

The provenance trail is thus constructed step by step as each signature
is constructed or verified. Each step involves a signature exchange, as
described later. Assuming the host time to be correct, the provenance
trail needs to be verified only once.

Note that this model does not construct the certificate trail in each
client host. In former designs, this was achieved using a persistent
cache which had to be updated on a regular basis. However, both the
current and proposed models are vulnerable to middleman attack. The
original solution for this problem was the Schnorr (IFF) identity scheme
described in RFC5906. The provenance scheme proposed in this document
replaces the IFF scheme while performing the same function. However, a
spoofed server or client packet cannot be distinguished from a valid
packet other than by IP address filtering.

8. Layered Model

The security model in the generic reference implementation RFC5905 can
be summarized as a four-layer model, described below. In the intended
model the handshake protocol messages hitchhike on the NTP packet
headers as transmitted. Note also that the packet poll interval during
the handshake can be reduced consistent with the rate limits.

Of the four layers, the format and on-wire layers are used where
security is not necessary. The format, private key and on-wire layers
are used with symmetric key cryptography and the keys file and keys
generated by the handshake protocol. Except for minor tweaks, these
three layers are implemented in the current reference implementation.
These layers plus the public key layer  described in this document are
used with public key cryptography.

The fourth layer consists of the handshake protocol or dance, which
establishes the cryptographic hash keys used beyond the dance. The hash
keys are replaced only if the dance is successful. The state variables
used in the dance are discarded once the dance has completed, or in case
of error. The result is the shared hash key used for all subsequent packets.

8.1 Format Layer

When an NTP packet arrives, the first layer verifies the packet format.
In particular, the UDP checksum and packet length, packet header and
extension field lengths. The extension fields are checked but not
processed at this time.

The format scan results in a pointer just before the message
authentication code (MAC). This designates the upper limit of the hash
computation.

The beginning of the MAC is determined in two ways. If the last  block
in the sequence of messages is less than or equal to 24 octets, the
pointer is set at the beginnning of the last block. If the operation
code in a message designates a MAC message, the pointer is set at the
beginning of the MAC message. This provides both flexibility and
backwards compatibility, as well as the opportunity to add
unauthenticated messages beyond the MAC message.

In case of format error, the packet is discarded with no further action.
If successful, processing continues in the second layer.

8.2. Private Key Layer

The second layer verifies packet data content using keyed hash
functions. This layer functions in a way similar to the DTLS record
protocol. In the NTP generic security model, NTP packets are considered
public values so they are not encrypted. However, it is vital that the
packet be undamaged in transit and the packet order be preserved.
Although the NTP protocol is quite resistant to packet loss,
retransmissions of lost packets are not generally useful, except for
handshake packets.

Packet data integrity is protected by a message authentication code
(MAC), which is used for all packets, including handshake packets. The
MAC is ordinarily constructed and verified using a secret hash key
shared by the participants. The hash key is assumed private and
unpredictable for each association separately.

As an optional feature,an HMAC version of MD5 or SHA1 can be used as the
hash function. This further obscures the hash operations using a second
run of the hash function. Ordinarily, in the first run the shared hash
key is prepended to the packet data and the result processed by the hash
function.  In the second run the shared hash key is prepended to the
result of the first run.  The output of the HMAC is computed as the
result of this run. This makes each hash computation statistically
different, further compromising a brute force attack.

A legacy MAC consists of a 4 octet key identifier (ID) field followed by
the computed hash value with length 16 or 20 octets. Hash keys are
identified by key number in the range 1-254, inclusive. The key number
ordinarily identifies an entry in the keys file by the first octet of
the key ID field in the MAC. Alternately, a hash of arbitrary length can
be implemented using an extension field. In this case, the length octets
in the key ID field will be nonzero and the modifier octet used as the
key number, with number 255 reserved for the shared hash key.

The hash is computed from the beginning of the packet to the beginning
of the MAC. Ordinarily, the MAC is the last extension field in the
packet, but additional extension fields beyond the MAC are possible,
though not included in the hash computation.

If a shared hash key is not available, such as during the handshake
itself, an implicit hash key zero, also called the group key, is
assumed. The value of hash key zero is by default the empty string. This
string can be redefined as necessary. The design intent is to validate
the packet contents using this string, but not necessarily to avoid
spoofed packets, which are caught by the on wire protocol.

The default empty group key is interpreted as a keyless hash, function,
in effect, a checksum.  Otherwise, the nonempty string designates a
group hash key common to all hosts of the group.

By rule, if a packet request uses key zero, the packet response also
uses key zero. Usually, the IBURST flag is used to minimize the time to
complete the handshake.

Note that any agreed upon symmetric key in the ntp.key file could be
used to fulfill the role of key zero. This option could be eused to form
a secure group while preventing access from outside the group.

By specification, a secure server can work with or without a MAC.
Without a MAC the packet is unconditionally accepted; with a MAC a
packet is accepted only if verified by secure means. A configuration bit
can be used to discard packets without a MAC.

If the MAC is verified and the packet is accepted by the on-wire layer,
the packet is processed by the fourth public key layer. In case the MAC
is not verified and the packet is accepted by the on-wire layer, the
packet is discarded and a crypto-NAK message returned to the sender. If
both the MAC and on-wire test fail, the packet is discarded without
further processing.

The crypto-NAK consists of a 4-octet extension field containing an
optional error code. A crypto-NAK packet is always sent with key zero.
It must be verified by the format, private key and on-wire layers. The
crypto-NAK ordinarily results in a new handshake and shared hash key, as
described below. Otherwise, the packet is discarded without further
processing.

If the hash size is too large, it can compromise timing accuracy; if too
small, it can compromise security. A natural choice is 160 bits or 20
octets, as in the current reference implementation. An attractive
strategy is the use of elliptic curve versions of the agreement and
signature algorithms. Using these algorithms,a 160 bit hash size is
equivalent to a 1024 bit hash size using the traditional algorithms.

It is not generally useful to provide larger hash sizes. For example,
the SHA160 hash algorithm produces a 20-octet truncated version of
SHA256. Other hash algorithms can be truncated as well.

In the reference implementation, the hash algorithm can be specified for
each key number in the keys file. In principle, key zero can be assigned
in the keys file as well, providing an independent choice of hash algorithm.

The OpenSSL library includes just about every hash algorithm likely to
be imagined. While historically ambiguous, the International Trade in
Arms Regulations (ITAR) prohibits export of the OpenSSL library, so only
the MD5 hash algorithm is included in the reference distribution.
Alternatively, the OpenSSL library can be imported from foreign or
domestic sources, although the resulting product may not be exported
from the US.

8.3 On-Wire Protocol Layer

The third layer verifies protocol operations consistent with the on-wire
protocol. The protocol discards bogus and duplicate packets as well as
minimizes disruptions due to protocol restarts and dropped packets. The
operations are controlled by two timestamps: the transmit timestamp
saved in the client state variables and the origin timestamp in the
server packet header. The comparison of these two timestamps is called
the loopback test. The transmit timestamp functions as a nonce to verify
that the response corresponds to the original request. The transmit
timestamp also serves to discard replays of the most recent packet. Upon
failure of either test, the packet is discarded with no further action.

In order to reduce roundoff errors and improve security, the low order
nonsignificant bits of the timestamp are replaced by a random bit
string. With typical clock hardware, the size of the random string is at
least 20 bits.

The transmit timestamp might not be considered sufficiently random as a
nonce. However, the timestamps are always increasing, even if by a small
amount, and the timestamps are never predictable.

A collision event occurs when two different packets hash to the same
value. However, an attempt to construct an artificial collision requires
the packet to have correct format and pass the timestamp tests.
Therefore, in this proposal, transmit timestamps are considered valid
nonces. If necessary, an extension field can be defined for an alternate
nonce, although this is not reccomended.

An important function of the on-wire layer is collection of packet
timestamps, both input and output. There are three kinds of timestamps,
in order of increasing accuracy: softstamps, drivestamps and hardstamps.
These are determined by reading the system clock at specified protocol
events. Softstamps are determined when a packet is removed from the
input queue and when a packet is added to the output queue. Drivestamps
are determined at the time of the device interrupt at the end of the
packet. They are used by the reference implementation and in particular
the interleave protocol. Hardstamps are determined at specific events
determined by specialized interface hardware. They are not used in the
current reference implementation.

Drivestamps are the main determinant of timekeeping accuracy. They must
be collected at the device layer and passed upwards in the input packet
buffer or at the end of the output operation. This can complicate the
security protocol, especially if using a prepackaged security
implementation. For the best accuracy timestamps are not used for
handshake packets.

For the best accuracy, the length of all NTP packets should be nearly
the same. Also, the network delay on the client path and server path
should be nearly the same. For example, on a 100 MB/s link each octet
consumes ABOUT 80 ns, so the delay of a 256-bit message is about 10
microseconds. A network path where client packets go by satellite and
server packets go by landline, the delay difference is some 270 ms.

8.4 Public Key Layer

The fourth layer constructs and authenticates the shared hash key and
provenance trail to the certificate authority host. This layer functions
in a manner similar to the DTLS handshake protocol but is greatly
simplified in DTLS Lite. The basic protocol dance begins with a
parameter exchange followed by a cookie exchange and signature
exchange,as required.

The main function of the handshake is to develop and validate a
provisional hash key used by the client and server. Once the handshake
has completed, operation continues exactly as in the private key layer.
However, the actual shared key is updated only if the handshake
completes without error. Each invocation of the handshake is completely
separate; it starts with empty state variables and terminates by erasing
them again.

It is important to minimize the number of exchanges in order to minimize
the latency to acquire the time and authenticate the server. Ordinarily,
the time is acquired within six NTP rounds of two seconds each. The
authentication dance is piggybacked on these rounds. In DTLS Lite the
authenticity can be confirmed within four rounds or less.

The parameter exchange includes two messages, the host certificate
message followed by the selected algorithms message. The cookie exchange
develops and verifies the shared hash key and signature. The parameter
and cookie exchanges are sent with hash key zero. The signature exchange
constructs or verifies the public key signature on the host certificate.
The agreed hash key developed during the cookie exchange is used for the
signature exchange, and subsequent NTP packets.

The certificate authority host is designated either by a self-signed
certificate or by an identifier in the x509v3 extension field. Host
certificates are exchanged using the parameter exchange, with new
certificates replacing old ones with the same subject and issuer names.
Note that the certificate authority host can be either the root server
host in the network or an external certificate authority host connected
by an appropriate communication means.

By default, the subject name on the host certificate is the string
returned by the Unix gethostbyname library routine. The subject name on
the certificate authority is interpreted as the group name associated
with the particular trail and is useful in the identity exchange or
equivalent scheme.

The provenance trail is constructed step by step for each association,
with the issuer name replacing the subject name at each step. Note that
each step involves a single signature,so does not construct the entire
trail.

Once the provenance trail has been verified, it is not necessary to do
it again, unless a certificate is revoked or reaches advanced age. Note
that each association might have different issuer and subject names.

As part of the initialization process, a self-signed host certificate is
generated for each association. If the host certificate has not been
signed by the server for each association, the host certificate is
provided to each association server for signature. This is called the
signature exchange and needs to be done only once for each association.
Note that the next downstream host has the choice of signed
certificates, but they are all equivalent.

Once the provenance trail signatures have been verified, the host
certificate is considered authentic. If a certificate has been changed
on the provenance trail, the scheme to update the trail could be
tedious, as described below. Note that there are no provisions in the
security scheme to revoke a certificate, so this must be done by
external means.

In the following, the host certificate belongs to the host containing
the public/private keys, while a server certificate belongs to each
client association separately. Once the cookie exchange has completed,
the shared hash key can be used for authentication of all subsequent
packets.

For this purpose, the cookie exchange is split into two subexchanges:

o the agreement subexchange, which develops the shared hash key and

o the verify subexchange, which authenticates the shared hash key.

Each of these subexchanges consists of a request message followed by a
response message in the usual format. If any of these subexchanges
fail,the dance is terminated and all state variables are erased.

In symmetric mode the agreement subexchange uses the classic
Diffie-Hellman algorithm. In client/server mode the hash key is a
cookie,as described below. In the parameter and cookie exchanges, the
exchange uses key zero, as described above. The verify subexchange uses
the public key signature of the shared hash key in both the request and
response messages. If the signatures are not correct, the handshake
dance is restarted with fresh state variables.

The association is considered provisionally authentic following the
cookie exchange. The provenance trail is augmented in the signature
exchange. If successful, the provenance trail is extended by one step;
if not, the association tries again after timeout.

The sequence of messages in the handshake dance can best be managed by
appropriate state transition tables. These dances are similar, but not
identical, to the ones used for similar purposes in the RFC5906 Autokey
implementation and the NTS proposals.

A subtle difference between this proposal and the NTS proposals is how
to interpret the parameter exchange messages. The intent is that each
peer/client has a private vector of components, while each peer/server
has a private vector of similar components. The parameter exchange
appends the vector of one participant to the vector of the other
participant. Then, the working vector is derived in each participant by
the same algorithm. The result applies to both symmetric and
client/server modes, although the results are not saved in server mode.
Typical components include selected hash and encryption algorithms.

An optional feature is to verify the subject name on the received
certificate. The name is valid if it matches an entry on a private list
of host names in the NTP network.  The list must be constructed in advance.

The choice of handshake dance is determined by the NTP mode:
client/server, symmetric and broadcast. The above sequence of exchanges
is identical for client/server and symmetric modes, as well as optional
broadcast delay measurement,if used. Note that the signature scheme is
defined on each certificate. Otherwise, the agreement, hash, signature
and encryption algorithm identifiers default as in the parameter exchange.

A subtle complication is how to validate the lifetime of the
certificates along the trail to the certificate authority. The lifetime
of the subject certificate intersected with the lifetime of the issuer
certificate might or might not be empty. However, the lifetime of the
server certificate must contain the current valid time.

The orthodox way is to wait until the association time is valid, then
compare the valid time with the certificate lifetime. A discrepancy
results in a protocol restart. Note that a new regenerated certificate
might require a new generation of its issuer. The implications may be
tedious.

The dances involve a balance between formal authentication and duration
of the protocol. For instance, the cookie exchange confirms that the
hash key is valid, but does not necessarily confirm that the provenance
trail is valid. A successful signature of the host or server certificate
confirms that the certificate is valid. There is an interval between
validation of the shared hash key and validation of the certificate
trail but the time information may or may not be correct.

In the following dances, the only use of public key cryptography is to
verify signatures. Compromise of the private key does not affect the
shared hash key. Note that each restart of the dance results in a new
shared hash key unrelated to previous shared hash keys. In this
sense,the DTLS Lite handshake protocol has perfect forward secrecy. This
means that a disclosed private key cannot be used to authenticate past
or future packets beyond the lifetime of the publid/private signature
keys. In addition, old keys cannot be used for new signatures and new
keys cannot be used for old signatures.

8.4.1 Symmetric Mode

The goal of this dance is to install identical shared hash keys in both
peers. The design reflects the requirement of strict symmetry; that is,
peer A appears to peer B the same way that peer B appears to  peer A. In
addition, the key agreement does not reveal any public values or public
key encryptions that might be used in a spoof attack.

The dance can be started by either peer. Peers Alice and Bob use large
prime p as modulus and primitive root g as generator. A small value for
g, typically 2, is often used. A typical prime p is either 251 bits for
32 octet signatures or 509 bits for 64 octet signatures. The g and p
values must be shared in all symmetric hosts.

In the agreement phase, Alice sends her public DH key to Bob in an
extension field of a request message. Bob constructs his public DH key
and sends it to Alice in an extension field of a response message. Both
Alice and Bob then construct the shared hash key for use later.

In the VERIFY phase, Alice sends her signature of the shared hash key to
Bob. Bob verifies the signature, then sends his signature of the shared
hash key to Alice. Alice verifies his signature. Failure to validate
either signature results in a crypto-NAK and protocol restart.

The shared key constructed by Alice and Bob is used as the hash key in
subsequent PACKETS. The public and private DH keys are expunged after
use; they are used only once.

8.4.2 Client/Server Mode

The goal in this dance is to install a server cookie used in the client
as the hash key. The server is stateless and the protocol has perfect
forward security. The design reflects the requirement that no public
values are revealed, or public key encryptions which can result in a
spoof attack.

The dance is started by the client. The cookie can be regenerated by the
server upon arrival of a client packet. The cookie exchange is similar
to the cookie exchange proposed in the NTS documents, except that the
proposed cookie exchange is protected by key zero and the on-wire
protocol layer.

In the agreement phase, client Alice sends her public DH key to server
Bob. Bob then sends his public DH key to Alice. Both Alice and Bob
construct the shared key as described above. Alice and Bob use the
shared key as the encryption key for the cookie.

The cookie is the hash of the client IP addresses concatenated with a
server secret key using the selected hash algorithm. The server secret
key is a random number regenerated about once per day.

Bob encrypts the cookie using the shared key and sends it in the same
packet as his DH public key. The verify exchamge uses the same
signatures as in the symmetric mode. As an optional embellishment, if
the server has the public certificate of the client, this authenticates
the client to the server as well.

8.4.3 Broadcast Mode

The original Autokey protocol was based on the assumption that the
cryptographic algorithms were very slow and vulnerable to a flooding
attack. In fact, the Diffie-Hellman agreement took over 10 seconds on a
Sun IPC. As current machines and algorithms are much faster, it is
convenient for the server to compute the signature of the NTP header in
an extension field and for the client to verify the signature using the
public key on the server certificate. The server certificate must be
installed beforehand in each client. This is not a trivial requirement;
the certificate trail must be constructed separately.

When two or more broadcast client associations are in the same host, it
is convenient to include the certificate subject name in an extension
field of the broadcast packet. This selects the server certificate and
thus the correct signature key.

A common problem in this and other broadcast schemes is vulnerability to
copies of old messages, perhaps very old ones. The proposed solution is
to use the transmit timestamp as a sequence number and ordering
function. An old duplicate is recognized by a transmit timestamp older
than the most recent transmit timestamp. Once the first packet is
received, the broadcast client ignores all broadcast packets with an
earlier transmit timestamp. This design works even if the broadcast
server is restarted. If a broadcast client is restarted, there might be
some spurious old duplicates before the first new message. If the most
recent transmit timestamp is preserved between restarts, these old
duplicates are suppressed.

8.5 Dynamic Associations

In most NTP modes, the associations are mobilized in advance. Two
association modes, broadcast client and symmetric passive, are mobilized
dynamically when a client packet is received. In principal, this
constitues a flooding hazard where the intruder sends bogus packets
designed to mobilize multiple associations at high rates.

The defense against this hazard is to mobilize an association only if
the initiating packet has been securely authenticated. In the case of a
broadcast server or symmetric active packet which matches an existing
association, the packet is processed in the normal way, as described
above. In the case of a packet not matching an existing association, the
packet is accepted and the association mobilized only if correctly
authenticated; otherwise, the packet is discarded without further
processing.

In case of a broadcast server packet, it is prudent to avoid the
signature overhead if the certificate subject name does not match the
subject name on any known certificate. In case of a symmetric active
packet, the packet is authentic only if the MAC with key zero is valid
and the packet contains a parameter request message.

8.6 Interleave Mode

Improved timing accuracy can be achieved using interleave mode with
symmetric or broadcast modes. In this scheme a devstamp is captured near
the end of the packet before the hash and related cryptographic
computations. This devstamp replaces the transmit timestamp field in the
next following packet.

This feature can be used with an FPGA to capture a hardstamp upon
passage of the SOF symbol in the ethernet frame. The FPGA can be used to
capture a hardstamp in the receive packet as well. This scheme avoids
tinkering with the UDP checksum and in fact results in a time precision
comparable to IEEE 1588 PTP.

The interleave receiver uses a two-stage delay line.  The delay line
saves the current received packet followed by the previous received
packet.  The transmit softstamp for the current packet is replaced by
the transmit devstamp for the previous packet.

9. Error Recovery

This section summarizes a number of anticipated attacks on the clients
and servers in the protocol. For each attack a set of  defenses is
suggested and evaluated.

The most obvious form of attack is simply to hack the servers and set
the system clock to evil values.  There is no need to attack the
protocol or dances that might develop.

9.1 Brute Force Attacks

As in all cryptographic algorithms, the secret keys can be compromised
with possibly gigantic computing resources. One of the first things a
suspicious cryptographer looks at is the size of the bit strings used in
the cryptographic scheme.

A brute force attack on the shared hash key might not work in all cases.
Consider the number k of spurious keys that correctly decrypt a
ciphertext of n symbols. The number k generally decreases as n
increases. The number of symbols n where k decreases to one is called
the unicity distance. This statistic is generally more or less than 50
symbols for English. If the packet length is less than the unicity
distance, this means that a key that correctly decrypts a ciphertext x
may not correctly decrypt a ciphertext other than x.

As mentioned previously in this document, cryptographic keys must be
refreshed from time to time.  For symmetric mode peers, this can be done
using the handshake dance every day or two, but this applies only to a
single association.  For client/server mode the server private key can
be a new random value; this applies to all associations.  This is done
typically once per day.  For public key signatures, this requires
generation of new public/private keys and associated certificates.  The
computational complexity required suggests doing this once per week.


9.2 Cryptographic Errors

The usual response to a hash or signature failure in symmetric and
server modes is to send a crypto-NAK and discard the packet. In
addition, the sender clears its state variables and starts a timer. The
crypto-NAK is not used in client or broadcast modes.

If the crypto-NAK results from a hash failure, only the cookie exchange
is necessary. If the crypto-NAK results from a signature failure, the
protocol is restarted.

All messages, including the crypto-NAK, are validated by the tests of
the on-wire protocol. In addition, all messages after the cookie
exchange are protected by the agreed hash key and hash algorithm.

9.3 Old Duplicates

Old duplicates are suppressed in various ways, even if not
authenticated. The transmit timestamp test suppresses replays of the
last transmitted packet.  The loopback test suppresses replays of old
messages, both in symmetric and client/server modes. In broadcast
interleave mode a duplicate or missing packet can be detected using the
difference between the softstamp and drivestamp, as recorded in the NTP
header.

To see this, consider a replay of an old packet from peer A to peer B in
symmetric mode. Assume that the old replay arrives at peer B after the
last legitimate packet from peer A and before the next transmitted
packet from peer B. The loopback test for peer B operates as for peer A
to discard the old replay.

9.4 General Considerations

There is a wide spectrum of possible hostile probes on the NTP
implementation itself. One of these is simply to amputate the
cryptographic data from a transmitted packet. An immature implementation
might assume that the NTP design permits both secure and insecure
operations to be sanctioned. Such an error invites a middleman to
significantly alter the receive and transmit timestamps on the insecure
NTP packet, resulting in any of the actions described below.

In symmetric mode each restart results in a different shared hash key.
In client/server mode, the shared hash key is changed only when the
server secret value is changed or when the optional hmac is updated. The
restart then delays a time interval randomized over the poll interval,
then sends a parameter exchange and continues the dance.

This design provides correct recovery in case of public key changes and
server secret key updates. While this scheme invites a terrorist to
disrupt the protocol by injecting a bogus parameter exchange in the
middle of ordinary operations, the choice of key zero protects the
protocol from foreign networks without knowledge of the key zero value.
The result might not be considered a vulnerability, but in any case
represents a denial of service attack.

Even if the cryptographic defenses are breached, packets containing
protocol errors are suppressed. For instance, servers send only response
messages, never request messages. Clients send only request messages,
never response messages. servers attacked by bogus ip return addresses,
can result in one of two outcomes. If the recipient client is not an NTP
client, the recipient disregards the packet. If the recipient client is
a legitimate NTP client, the packet is discarded as not the result of a
previous  request.

9.5 Protocol Sequence

The random delay at protocol restart is designed to minimize collisions
in symmetric mode. A simple algorithm is used in order to avoid packet
overlaps, in the reference implementation to slew the packets of one
peer to be transmitted near the midpoint of the other peer~Rs poll interval.

In symmetric mode the first peer to timeout after restart sends a
parameter request and continues as required. A peer receiving a
parameter request before timeout resets the timeout greater than the
poll interval, then sends a parameter response as required. This avoids
races where both peers attempt to start  the dance at the same time.

The cryptographic strength depends on the size of the hash and the hash
algorithm. If the sizes are equal, the strength of the agreed key and
table key are the same.

While it is cryptographically hard to masquerade as a valid peer, client
or server, a clever middleman can simply change a packet to
intentionally cause a crypto-NAK and eventually a protocol restart. Done
often enough, the result represents a denial of service opportunity.

9.6 Dance Moves

The protocol dance is protected in part by the on-wire protocol layer
and by hash key zero. The parameter request includes the subject name on
the host certificate; the parameter response includes the subject name
on the server certificate. These names can be verified by the client
association.

The parameter exchange reveals the server certificate used to validate
the cookie exchange. The state transition tables verify correct sequence
of request and response messages. In summary, a hostile intruder cannot
toss fake values with effect on the state of the recipient.

Attacks on the public keys are detected by the hash key signatures, key
zero, and the on-wire layer; packets with loopback or duplicate errors
are ignored. Thus, the most likely result of a middleman invasion is a
restart, rather than a false agreement.

A significant disruption is likely when a new public/private key and
certificate are generated in the middle of the certificate trail. This
requires recomputing the new certificate signature in the immediate
upstream host and the immediate downstream hosts.

In broadcast mode, the most popular attack is to repeat old valid
messages. Ordinarily, these are suppressed by the transmit timestamp as
described above. However, protocol restarts and lost packets might
result in misordered messages. The enlightened response is to run a
timeout upon receiving a valid message and terminate it upon receiving a
message with a later timestamp. Note that a terrorist cannot construct a
valid message, as it cannot construct a valid signature.

9.7 Distributed Denial of Service (DDoS) Attacks

Of the threat scenarios, a DDoS attack is the most disruptive. The
reference implementation includes a most recently used (MRU) list used
by the rate management function. Each entry includes the client IP
address, process time of arrival and related information. The list is
ordered by decreasing process time of arrival with duplicate IP
addresses suppressed. The process time is implemented by a counter which
increments once per second, independently of the NTP system clock.

For each arriving packet, the MRU list is searched for an entry matching
the IP address. If found, the headway is determined as the time
difference between the matching entry and the arriving packet.  If the
headway is less than the minimum, the packet is discarded without
further processing. If accepted, the entry is unlinked and the packet
time and IP address linked first on the list.

The processing rate is the total number of entries on the MRU list
divided by the total elapsed process time. This can be used in a scheme
to discard packets as the rate increases above a threshold. Note that a
DDoS attack cannot be differentiated from an overflow of legitamate
traffic. of the MRU list is when the number of distinct IP entries
exceeds the MRU maximum size. This can be used in a scheme to drop
packets in the same way as headway violations. There might be other
schemes using the overflow as well.

9.8 Amplification Attacks

In the DTLS lite protocol described in this document, an amplification
hazard is when a small request message results in a large response
message.  This is avoided in the NTS proposal by including a dummy
placeholder in the request, so that the response has the same length as
the request.  This is considered a waste of network resources and is
unnecessary in the protocol proposed here.

In DTLS Lite, there are no instances of significant differences between
the lengths of request and response packets, except for the cookie
response message in client/server mode, as described previously.  This
is not considered an amplification attack, since the bogus recipient
cannot further amplify that message.

9.9 Data Minimization

A hazard has been identified when an interceptor can learn something
about client location using leaked NTP header values. A proposed
solution is to set all client header fields to zero, except the transmit
timestamp field, which is set to a nonce. However, this prevents
calculation of the client offset and delay, which is the intent of the
protocol. This is an unnecessary procedure and is not recommended. If
this procedure is indeed necessary, the client packet can be formatted
as in SNTP or UDP/TIME.

9.10 Broadcast Hazards

The NTP reference implementation includes a number of broadcast modes,
including IPv4/IPv6 broadcast, multicast and manycast modes. These modes
pose a significant hazard when a terrorist attempts to clog the
broadcast client with a stream of broadcast messages with fake ip source
addresses and at extreme rate. These hazards can be deflected by the
layered model above, or by access controls and rate management.

Manycast mode, which might be useful to the pool community, poses a
unique hazard. The manycast client begins by broadcasting a client
request message. Potential servers reply with a unicast server response
message. The  manycast client then selects the manycast server based on
server parameters, such as server stratum. The selected manycast client
proceeds as in client/server mode with the selected server. these
messages and subsequent packets proceed as in the  client/server mode.

Subsequent traffic is protected as in the layered model. While this
scheme  protects using the layered constraints, a middleman can overload
the manycast servers with a flood of manycast client packets. Potential
pool clients can use this mode,but are advised to use carefully tailored
access controls.

There are additional scenarios where an attacker can overload the
servers or clients with multiple associations. These include a flood of
fake broadcast server or symmetric active probes using bogus source ip
addresses. These packets might result in a broadcast client or symmetric
passive peer to allocate and initialilze a bogus passive association.
The result can be a failed initialzation consuming substantial victim
resources.

9.11 Configuration Support

Note that the original library program used to generate keys and
certificate applications continues to work with the proposed scheme. A
significant challenge is to minimize the complexity of the configuration
effort.

10. Hacker Opportunities

Consider when a server update has passed all forms of cryptographic and
protocol defenses. A critical question is when the server time is
intentionally disrupted in order to destabilize the client clock. There
are several mutually exclusive hacker opportunities described below.

In a stop attack, the server simply stops operating. The result is that
the client clock continues at its intrinsic time and frequency. If the
frequency is far from nominal, the client clock error will grow without
bound.

In a panic attack, the server clock offset is greater than the panic
threshold, usually 900 seconds. In this scenario the client clock is
stepped to some large offset greater than the panic threshold. If it is
the first update, the client clock is stepped to the apparent time and
operation continues with this time. This is often the case at client
startup with no real time clock hardware. If it is not the first update,
the client stops the NTP program with a log entry and operator warning.
If this happens, the inexperienced operator simply restarts the program
and the evil step occurs anyway. This can destabilize the client
applications in massive ways.

In a step attack, the client clock is stepped less than the panic
threshold, but greater than the step threshold, usually 128
milliseconds. The server continues in this way for the stepout
threshold, usually 900 seconds. After this, the next update will step
the client clock by the server update. The clever terrorist can repeat
this with different offsets, causing the client clock to oscillate wildly.

In a swish attack, the server uses offsets less than the step threshold
but adds or subtracts increasing offsets. The clock eventually reaches
and holds at the maximum frequency, currently 500 parts per million, or
about 43 seconds per day.

11. Implementation Suggestions

Judging from development experience, tinkering with protocol design can
be tedious. The dances interact with the timeout and rate management
functions, while exchanges may either timeout or result in error.

Current and useful features of the reference implementation may be lost
in a new implementation. The effective approach may be to eviscerate the
current Autokey provisions in the reference implementation and replace
with the above design.

This may not be as difficult as it seems. The first step is to remove
all extension field references to association ID, timestamps and
filestamps. Note that the progression of exchanges is not changed. The
next step is to implement the cookie and DH agreement algorithms as
described above. The final step is to remove all references to the SKEY
scheme and replace with the signature scheme as described.

12. Alternative Models

As an aside, ASN.1 encoding of extension fields is probably not a good
idea. However, ASN.1 is appropriate for parameter data. All other
extension fields use only opaque octet strings. Even ASN.1 encoded data,
such as certificates, are transmitted as flat opaque bit strings.

TLS/TCP, DTLS/UDP or combinations of these might be a good alternate
approach. The motivation for this approach is to use existing public
security schemes to authenticate NTP packets. This approach requires a
public software protocol stack or library. Besides forming an additional
target for hostile attack, the time and resources required may be
burdensome.

12.1 TLS/TCP

The TCP protocol design is at odds with the NTP datagram and rate
management principles. The TCP model requires the client and server to
maintain persistant protocol state, which requires state variables to be
preserved during at least the handshake dance. In client/server mode the
TCP connection must be mobilized each time the shared hash key is
updated and in case of error. In addition, TCP requires a format layer
that identifies packet boundaries. Effective design requires window and
retransmission strategies, use of the push bit and slow-start features
of the TCP protocol.

While TCP provides reliable delivery, fragmentation and flow control,
retransmissions of handshake packets render NTP timestamps essentially
useless. A large multi-segment packet invites an interceptor to delete a
segment, requiring the transmitter to retransmit the entire packet. This
suggests use of the cryptographic hash function above to protect TCP data.

Among other things, the TCP retransmission algorithm would be greatly
destabilized by a large poll interval. It might be best to isolate the
handshake rounds as a separate TCP protocol. In this design the
handshake dance concludes with the shared hash key and then disappears.
In this way the TCP handshake packets are completely isolated from
NTP/UDP packets but are beyond the reach of rate management. However,
this design requires both client and server to manage TCP connections
and mobilize associations on demand.

The TCP model requires both server and client to maintain large memory
areas for buffering and control state, which is not practical in a
stateless server architecture. It also requires copying handshake
packets to internal buffers and then copying data from these buffers to
handshake messages. The overhead in these actions would overwhelm a
processor faced with a swarm of 3000 NTP packets per second.

Finally, the TLS/TCP protocol overhead requires up to seven control
packets in addition to the dance packets, while obeying the rate
constraints. The result of a bogus and middleman attacks on the TCP
protocol itself is unclear. The conclusion is that any security model
based on TCP is inappropriate for direct use by NTP.

12.2 DTLS/UDP

DTLS/UDP at first glance seems a much better security protocol for NTP
than TLS/TCP due to its intrinsic structure based on datagram
principles. The NTS protocol requires the NTP header and extension
fields to be embedded in the DTLS/UDP record protocol, which requires
copying, as in TLS/TCP. This results in considerable overhead and loss
of timestamp accuracy.

The DTLS handshake protocol is not well protected, but the key zero
scheme could resolve this problem. However, the record protocol could be
avoided if the I/O buffer contains the complete NTP packet header, PDUs,
and MAC. This is an example of the "touch only once" principle, which is
adopted in the above proposal as well.

A showstopper problem is that DTLS/UDP is implemented differently in
symmetric and client/server modes. There are then three protocol designs
for the hash function; one each for symmetric mode, client/server mode
and the original symmetric key mode. This document is carefully crafted
to include all three designs in the same protocol. In principal, the
only difference between these modes is in the agreement phase of the
cookie exchange, but this is not supported in the NTS proposals.

For the best accuracy, the on-wire timestamps should be implemented as
close as possible to the end of packet hardware interrupt. The reference
implementation does this by an intricate scheme involving the Unix
interrupt queue and recording the timestamp in the input packet buffer.
In the DTLS/UDP model, the buffer is then passed to the DTLS/UDP record
protocol, which might not preserve the timestamp. This would be possible
only with considerable modifications to the DTLS/UDP public software
distribution.

To continue support for the non-authenticated protocol and the
authenticated keys file model, the NTP/UDP port must be 123 as required
for historic operations. Therefore, a DTLS/UDP or TCP security protocol
must be supported on a different port. This raises a significant problem
when synchronizing between the two ports.

The use of TCP on a port other than 123 can support segmentation and
reassembly for the handshake protocol. The real killer in a DTLS/UDP
design is what to do about fragmentation and reassembly.

Apparently, the current security infrastructure requires certificates of
over 5000 octets, which requires multiple fragments not greater than the
1500-octet MTU. This results in unacceptable loss of timekeeping
accuracy. The most effective solution is to require certificates to be
less than the MTU of 1500 octets. It is not clear why such large packets
are required but the simple observation is that certificates for NTP
security need not be as robust as needed for web browsing.

In summary, a model such as the above, where TCP is used for handshake
operations and UDP is used for NTP support, is a useful alternate to
piggybacked messages. In principle, the actual handshake exchanges can
be based on the DTLS Lite or official TLS models.

13. Parting Shots

With respect to the NTP model in RFC5905, the proposed protocol in the
NTS in NTP documents seems at odds. The NTS scheme uses different models
for client/server and symmetric modes, as symmetric mode does indeed
have server state and the client/server mode does not.

The proposed NTS broadcast scheme requires a two-way message path, which
is not a requirement in the NTP model. While the proposed NTS scheme
could be a configuration option, the proposed scheme in this document is
a necessity for the one-way configuration.

On the other hand, the proposed NTS scheme seems wholly appropriate for
an application such as the IP/TIME or SNTP protocol, where there is no
on-wire protocol layer. With NTP, this layer avoids the need for
explicit nonce and session keys.

There are some warts in the reference implementation and proposed public
key schemes. There might be ways to validate the certificate trail other
than proposed in this document.

As in all cryptographic schemes, provisions must be made to refresh the
key material. As suggested above, the secret key of the server should be
refreshed about once per day. For more disruption due to certificate
updates, the present design does this by shutting down and then
restarting all associations once per week. More sophisticated schemes
might be devised.

Rare collisions would be expected in symmetric mode. This would happen
when both peers start the protocol at the same time. This can be avoided
using a random delay at association startup, as described previously in
this document.

The most objectionable issue about the proposed NTS for NTP document is
its astonishing complexity. There are up to five keys for each
association, premaster, master, client, server and session keys. In this
document only one shared key is required. There is no need for two keys
in client/server mode. There is no need to export keys, unless the
intent is to provide recovery of keys for forensic purposes.

The DTLS/UDP handshake exposes an astonishing panoply of apparently
useless options. Provisions to renegotiate keys aare superfluous, since
the protocol can simply be restarted.

Provisions for protocol version rollback are not necessary; in NTP
philosophy a new protocol version is backwards compatible with previous
versions. The notion of session key is foreign to NTP. In particular,
the NTP session lives forever.

The proposed protocol handshake in the NTS document is expensive, and
time consuming at best. It requires an extra extension field in
client/server mode. It can result in unstable operation and excessive
handshake times compared to the protocol proposed in this document.

The most interesting issue is why the DTLS for the NTP document is
necessary in the first place. A straightforward mapping of NTP packets
to DTLS record protocol would suffice. There is nothing in the NTS for
NTP document on specific functions for time management. This might
require additions to the DTLS options mechanism, but would degrade clock
synchronization accuracy.

-- 
Harlan Stenn <[e-mail]>
http://networktimefoundation.org - be a member!