Subject: [ntpwg] An exploration of the NTS design space

From: Daniel Franke <[email-masked]>
Date: Sun, 19 Jun 2016 22:28:49 -0400

---
note: This email is formatted as Pandoc Markdown
title: An Exploration of the NTS Design Space
author: Daniel Fox Franke
date: June 19, 2016
---

# Background

The IETF's NTP Working Group is seeking to produce a new standard for
public-key authentication of the Network Time Protocol, replacing the
broken and disused Autokey protocol (RFC5906). The effort is dubbed
NTS, for Network Time Security. There is a draft proposal currently in
WG Last Call status:
<https://tools.ietf.org/html/draft-ietf-ntp-network-time-security-14>. Eric
Rescorla reviewed this draft and requested that the committee produce
a design which makes better use of existing standards, specifically
TLS. He recruited me to assist in this design effort.

This essay is the product of my first week of thinking seriously about
the problem. It is not a design document. Rather, it is a sketch of
the whole space of reasonable designs and an exploration of the
necessary consequences of particular high-level design decisions.

# What makes NTP cryptographically exceptional?

Possible designs for NTS can be placed into one of three broad
categories:

* Type I: Those which encapsulate the entire NTP within a DTLS
  channel.

* Type II: Those which piggyback off the (D)TLS handshake for key
  establishment, but perform symmetric authentication in a custom way.

* Type III: Those that are unrelated to TLS (like the
  currently-adopted draft).

The attitude of the typical practicing crypto engineer (myself
included), is that we should not be reinventing the wheel, and that
ceteris paribus we should prefer Type I over Type II and Type II over
Type III. Any decision to move down in this hierarchy needs to be
well-justified.

In this section, I address several features of NTP which make it
cryptographically exceptional: ways in which it violates the TLS
designers' basic assumptions about what application-level requirements
TLS needs to serve. In turn, I examine the extent to which each of
these points justifies moving away from a Type I design.

## Load on NTP servers scales out on unusual axes

NTP scales differently than, e.g., a web server:

1. A single NTP server may have an exceptionally large number of
   clients. For example, consider time.apple.com, the default time
   server for every Mac, with broad geographic regions served by
   clusters of just five servers.

2. Client-server associations may be exceptionally long-lived. They
   are established once when the client boots up, and may stay alive
   for years at a time.

3. The average client, individually, imposes exceptionally little
   load.  By default, after the initial burst, just one pair of
   packets is exchanged every 1024 seconds.

The upshot of this is that it is highly undesirable to require servers
to maintain per-client state throughout the lifetime of an
association. It may nonetheless be acceptable to require servers to
retain per-client state only briefly, say, only during an initial
handshake. Later in this essay I will revisit whether this is actually
true, drawing an affirmative conclusion.

Unauthenticated client/server NTP queries require only a single round
trip. It is desirable that, following initial key establishment, this
property be retained for authenticated queries.

DTLS is a stateful protocol, and out of all the arguments against a
Type I design, I find this one the most persuasive. However, I do not
find it immediately dispositive, because DTLS *can* be coerced into
providing the properties I prescribe here, or at least it will be able
to do once TLS 1.3 is ratified. TLS 1.3 introduces support for "0-RTT
data", permitting clients to resume a previously-negotiated session
and send along some application data all in their first packet.

## NTP is exceptionally sensitive to cipher performance

For most applications, cipher performance merely has to be good enough
that it does not overload the CPU, and the algorithms in common use
today are fast enough to make up a negligible part of most servers'
CPU budget. For the handful use cases where this is not true (such as
CDN proxies), it's usually just a matter of throwing more hardware at
the problem.

NTP is different, because latency matters more than throughput. Even
on a mostly-idle server, a slow cipher still places a burden on
timekeeping precision. Suppose it takes about 1250 CPU cycles to
compute a MAC. That is a latency of about 500ns. If there is no
counterbalancing source of latency on the client side, then this will
add a consistent bias of 250ns to time-offset calculations, which is
more than rounding error if the client is talking to a stratum 1
server over a wired LAN.

This is a good argument in favor of careful ciphersuite selection. It
is a bad argument against using DTLS. The DTLS record layer is already
light and efficient and supports a variety of high-performance
algorithms. No bespoke design is going to make any measurable
improvement in timekeeping performance.

## Merely delaying delivery of NTP packets alters their semantics

The destination timestamp $t_4$, i.e., the time-of-receipt of an NTP
response according to the client's clock, is semantically an important
part of the message. For obvious reasons, it is impossible to
cryptographically protect this field through any conventional means.
Furthermore, there is no widely-accepted framework for formal analysis
of cryptographic protocols which includes any notion of time rich
enough to meet NTP's demands.

I don't think this point is particularly relevant to any of the design
trade-offs we're considering. In every design under consideration (and
the legacy designs as well), it is possible for an on-path attacker,
by delaying packets, to skew time synchronization by up to 500ms: one
half of the MAXDIST constant. I consider any attempts to improve on
this bound to be out-of-scope, and would have no idea how to do it.

## Checking validity dates on cryptographic attestations poses a
chicken-egg problem

If NTP clients cannot initially count on having sane system clocks,
then they cannot, for example, verify that X.509 certificates have not
expired.

This, too, I consider out-of-scope. What, if any, leeway NTP clients
should allow when checking these validity periods should be treated as
a policy decision, based on the human judgement of the system
administrator and informed by a priori knowledge such as the state and
reliability of the system's RTC and CMOS battery, or the compilation
date of the NTP binary. For a more principled approach, see
<http://arxiv.org/pdf/1503.08768v2.pdf>, but if this sort of thing is
implemented, it can and should be independent of NTP.

## NTP has a broadcast mode

I strongly dislike broadcast mode. I don't think there's any network
in the world whose topology justifies using it, and I think that it
should be removed from the next revision of NTP.

Securing broadcast mode is at the very least a thorny problem, and I
am not yet convinced that there is any practical solution. There's a
TESLA-based proposal in Appendix C of the current draft. It's rather
complex, but I think that complexity is essential: nothing simpler can
possibly work. Even so, it doesn't work very well, failing to produce
good bounds on how much an adversary can skew the clock: an on-path
can delay packets for up to the entire disclosure duration.

My opinion on the matter is that it's just not worth the
effort. Whatever is ratified with regard to broadcast mode, I am
personally unlikely to ever implement it and almost certain never to
deploy it in production. If others are motivated to continue working
on the problem, I don't want to interfere with them. However, I also
don't want to allow considerations surrounding broadcast mode to add
complexity to rest of the design. Right now, they don't: sections of
the current design related to broadcast mode are neatly orthogonal to
all the rest. I want to ensure that future work retains this property.

If broadcast support is kept as an orthogonal concern, then we also
don't have to allow the debate over its design to interfere with the
progress of the rest of the standard. To facilitate this, I think it
would be a good idea to migrate broadcast-related content into a
separate document, possibly with an intended status of Experimental.

# Type I designs

Type I designs must run on a different port than plaintext NTP,
because otherwise there is no clean way to distinguish whether a given
packet is an NTP packet or a DTLS packet. Even if this could somehow
be accomplished, such as by using an NTP extension field to negotiate
a transition to DTLS, running DTLS on the NTP port is likely to
confuse firewalls and other middleboxes, and it increases the
likelihood of implementation mistakes that lead to downgrade attacks.
This particular approach would also require the server to keep state
in order to remember what clients have negotiated DTLS support with
it.

In order to satisfy the previously-laid-out requirements for
statelessness and round-trip minimization, DTLS 1.3 and its 0-RTT data
feature are necessary.

The resulting design is inevitably something very similar to the
following.

When a client contacts a server for the first time, it sends a
ClientHello message with an ALPN extension containing either
"ntp-persistent/1" or "ntp-fastxmit/1". In the fastxmit version, the
client pledges that it will use this session only for client/server
mode, sending mode 3 packets and getting back mode 4 packets. The
persistent version may be used for any mode except broadcast.

The reason for separating these cases is that the server has differing
requirements regarding statefulness and replay protection. In
client/server mode, only the client needs any replay protection; the
server does not. In other modes, both sides need replay protection.
Also, however, in other modes the server can have greater tolerance
for statefulness: although a server may have millions of clients, it
is not going to have millions of symmetric peers, or millions of
ntpq/ntpdc sessions.

Servers probably should not accept ntp-persistent handshakes from the
general public; they should restrict access by demanding client
certificates and/or enforcing IP ACLs.

In the standard DTLS countermeasure against DDoS amplification, if the
ClientHello did not include a cookie then the server replies with a
HelloVerifyRequest and the client resends the ClientHello with the
cookie included. The server does not need to hold any per-client state
during this round trip.

The server replies to the ClientHello with the usual ServerHello /
Certificate / CertificateVerify / Finished messages, also including a
CertificateRequest message if the server is using client certificates
to enforce access control. Even in the fastxmit case, the server
*does* need to hold state while it is waiting for the client to reply
to these messages. However, it may use very aggressive timeouts.  NTP
is already designed to intentionally fail if the round-trip latency
between two endpoints is greater than a second, so the server may
purge its handshake-related state if it does not get a reply within
that second.

The client replies with a Finished message, preceded by Certificate
and CertificateVerify messages if required. In the persistent case,
the client may follow the Finished message with application data. In
the fastxmit case, the server will not expect application data during
this handshake. Instead, it will reply to the Finished message with a
NewSessionTicket message, and then immediately purge the session
state.

On fastxmit resumption, the client sends a ClientHello, containing:

* The DTLS cookie that the server previously gave it
* The session ticket that the server previously gave it
* A pre_shared_key extension
* An early_data extension (0-RTT data) containing a mode 3 NTP packet

The server replies with ServerHello and Finished messages, followed by
a mode 4 NTP packet as application data. It then discards the nascent
session without waiting for the client to respond with a Finished
message.

There is a privacy problem with this design. The TLS 1.3 draft advises
that clients SHOULD NOT reuse session tickets across multiple
connections, because this allows a passive adversary to correlate the
two connections as coming from the same client, even if the client has
moved networks in the interim. To avoid reuse, the server is supposed
send the client a fresh session ticket for later use. However, the
current TLS 1.3 draft specifies that the server may not send a
NewSessionTicket message until after it has received a Finished
message from the client. Complying with this requirement would add a
second round trip to every time query, which I think is
unacceptable. However, I think the requirement can be relaxed: on PSK
handshakes, it should be safe for the server to false-start the
NewSessionTicket message. I can raise this issue with the TLSWG if
needed.

# Type II designs

A Type II design should run the handshake on a port other than UDP
123.  If that port is used only for the handshake and for nothing
else, then it may be a TCP port and use normal TLS rather than
DTLS. Multiplexing the handshake directly onto the NTP port creates
the same ambiguity problems as it does in Type I
designs. Encapsulating a DTLS handshake inside an NTP extension field
is theoretically possible but poorly advised, for two reasons. First,
it is likely source of bugs wherein implementations mishandle the
other contents of the NTP packet while the handshake is still in
progress. Second, it interacts badly with rate limiting. It is best
for the server to finish the handshake as quickly as possible, to
minimize the amount of time that it has to retain state. If clients
won't send (or servers won't accept) more than one packet per $N$
seconds, that increases memory pressure on the server by at least a
factor of $N$, and more like $10N$ or $20N$ in practice. The problem
gets multiplicitatively worse if bundles of DTLS messages have to be
split across multiple packets to prevent fragmentation.

Type II designs do not need to rely on TLS 1.3; 1.2 will do just fine.
The initial handshake in a Type II design looks just like it does in
the Type I design, but no application data (early or otherwise) is
ever exchanged; as soon as both parties have sent their Finished
messages and the client has gotten a session ticket, they can hang up.

The two parties can then follow RFC5705 to export key material from
the TLS handshake for use on the NTP port. Three keys should be
extracted: two MAC keys (one for each direction), and one privacy key
whose purpose I'll explain in a moment.

After the handshake, clients query the server on the normal NTP port,
including an extension field which contains a MAC tag, a nonce, and
the session ticket provided during the handshake. The extension field
in the server's response contains a MAC tag, the nonce provided by the
client, and a fresh session ticket encrypted with the privacy key.
The client decrypts the session ticket and sends it back (in
plaintext) after the next polling interval. This handling of session
tickets solves the privacy problem posed by the Type I design.

The simple nonce scheme described here only provides the client with
any replay protection. This is sufficient for fastxmit, but for modes
where both sides need replay protection, something more is required. I
do not want to carry forward the legacy authentication system's
reliance on origin timestamps as a replay protection mechanism: this
is bad design and a layering violation.  A well-designed
authentication layer's security guarantees should be generic, i.e.,
agnostic to the form of the application data they're
carrying. Furthermore, in some modes inspection of origin timestamps
is inadequate: see
e.g. <http://support.ntp.org/bin/view/Main/NtpBug2947>
(CVE-2015-8140).

Designing a satisfactory approach to mutual replay-protection should
be reasonably straightforward, but I haven't taken the time to do so,
because I like the design in the next section better, and it avoids
the need for it.

Type II designs need a means of determining what algorithms to use for
MACing the NTP packets and encrypting the session tickets. The
simplest approach is to settle on a single choice, and achieve cipher
agility by versioning in the ALPN field. I think this will be
satisfactory, but if I am overruled on this then the alternative is
either to negotiate algorithms via an application-layer protocol over
the TLS channel, or to define a new TLS extension and do the
negotiation in the ClientHello / ServerHello messages.

# Hybrid Type I / Type II

This idea is my favorite: use the Type II design for client/server
mode, and Type I for everything else. So, start by doing a DTLS
handshake. If the ALPN field is "ntp-fastxmit/1", then hang up after
the Finished messages are exchanged and proceed with the Type II
protocol over the NTP port.  If the ALPN field is "ntp-persistent/1",
keep the session open and exchange NTP packets as application data
encapsulated within the DTLS channel.  I think this solves everything:
no excess state, no need for TLS 1.3, no kludges with 0-RTT data and
aborted handshakes, no tracking, and replay protection everywhere it's
needed.

# Type III

In light of all the above, I don't think it's necessary to consider
any Type III designs. However, I will remark here on one notable merit
of the currently-adopted proposal, which is that it allows the server
to avoid maintaining state at any point during the handshake. However,
the state requirements of the Type I and Type II designs above are
already sufficiently modest that I don't think any further
optimization is warranted. Suppose an NTP server has one hundred
million clients, that the clients are restarted at an average
frequency of once per ten thousand seconds, and that all clients have
a round-trip latency of an entire second. The server will therefore
have an average of ten thousand handshakes in flight at a given
time. So, even this implausibly busy server with these particularly
obnoxious clients can maintain all its per-client state in just a few
megabytes of memory.
_______________________________________________
ntpwg mailing list
[email-masked]
http://lists.ntp.org/listinfo/ntpwg

---

From: Hal Murray <[email-masked]>
Date: Tue, 21 Jun 2016 21:12:13 -0700

I like it.  Thanks.

[email-masked] said:
> The upshot of this is that it is highly undesirable to require servers to
> maintain per-client state throughout the lifetime of an association.

I think it's worth exploring that area.  Modern servers have lots of memory.  
How much state does an association need?  Handwave.  If it's 100 bytes, then 
we get 10 million clients per gigabyte.  10 million clients at 1000 second 
polling interval is 10000 packets per second which is the ballpark of what 
current ntpd can do with a single CPU (without encryption).

> NTP is different, because latency matters more than throughput. Even on a
> mostly-idle server, a slow cipher still places a burden on timekeeping
> precision. Suppose it takes about 1250 CPU cycles to compute a MAC. That is
> a latency of about 500ns. ...

I don't think that area is going to be a problem.  Modern OSes grab a time 
stamp when a packet arrives.  The transmit side is a bit tricky since the 
send-time goes in the packet and we need that before we can do the crypto.  I 
think we can work around that by measuring the time to do the crypto at 
startup and bumping the send-time to compensate.  Or setup the time longer in 
the future and queue the packet until that time.

I agree that we need to think carefully about how much CPU a crypto algorithm 
uses.

> ## Checking validity dates on cryptographic attestations poses a chicken-egg
> problem 

> If NTP clients cannot initially count on having sane system clocks, then
> they cannot, for example, verify that X.509 certificates have not expired.

> This, too, I consider out-of-scope. What, if any, leeway NTP clients should
> allow when checking these validity periods should be treated as a policy
> decision, based on the human judgement of the system administrator and
> informed by a priori knowledge such as the state and ...

I think we need to carefully consider how to get started.  I'd be happy to 
push this part off to another document as long as there is a big (huge?) 
disclaimer in the first document and/or we have some ideas about how to solve 
the problem.

A good test case is a spare board that has been on the shelf for 10 years.  I 
think that's a reasonable time for telco gear.  Military is probably longer.

Does the API for the certificate library have a flag to say 
don't-check-expiration?

It's probably worth mentioning that NTP already has the concept of broken 
servers (falsetickers).  I think we can leverage that to cover broken 
algorithms and/or leaked keys and maybe some software bugs.

---------

It may be time to encourage ISPs (and web server farms...) to provide NTP 
servers for their customers.  It's tangled up with trust as well as load 
spreading.

Authentication is worthless unless you trust the party you are 
authenticating.  I think that leaves the pool out of the authenticated area.

-- 
These are my opinions.  I hate spam.