Internet DRAFT - draft-schiff-ntp-chronos
draft-schiff-ntp-chronos
Network Working Group N. R.Schiff
Internet-Draft D. Dolev
Intended status: Informational Hebrew University of Jerusalem
Expires: March 5, 2020 T. Mizrahi
Huawei Network.IO Innovation Lab
M. Schapira
Hebrew University of Jerusalem
September 2, 2019
A Secure Selection and Filtering Mechanism for the Network Time Protocol
Version 4
draft-schiff-ntp-chronos-03
Abstract
The Network Time Protocol version 4 (NTPv4) defines the peer process,
the clock filter algorithm, the system process and the clock
description algorithm. The clock filter algorithm and the system
process, as defined in RFC 5905, are the mechanism according to which
an NTP client chooses the NTP servers it synchronized with. This
document specifies an alternative set of client mechanisms, named
Chronos, that is backward compatible with NTPv4, and offers an
improved level of security against time shifting attacks.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on March 5, 2020.
Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved.
R.Schiff, et al. Expires March 5, 2020 [Page 1]
Internet-Draft NTP Extention with Chronos September 2019
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Conventions Used in This Document . . . . . . . . . . . . . . 3
2.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3
2.2. Terms and Abbreviations . . . . . . . . . . . . . . . . . 3
2.3. Notations . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Extension for NTP Selection Process . . . . . . . . . . . . . 4
3.1. Peer calibration Process . . . . . . . . . . . . . . . . 4
3.2. Chronos Selection Process . . . . . . . . . . . . . . . . 4
4. Chronos Pseudocode . . . . . . . . . . . . . . . . . . . . . 5
5. Precision Vs. Security . . . . . . . . . . . . . . . . . . . 5
6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 6
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 6
8. Security Considerations . . . . . . . . . . . . . . . . . . . 6
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 7
9.1. Normative References . . . . . . . . . . . . . . . . . . 7
9.2. Informative References . . . . . . . . . . . . . . . . . 7
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 8
1. Introduction
According to RFC 5905 [RFC5905], the NTP servers used for updating
the client's time are chosen by the clock filter algorithm and the
system process. However, this method may be vulnerable to time
shifting attacks, in which the attacker's goal is to shift the local
time of an NTP client. Time shifting attacks on NTP are possible
even if all NTP communications are encrypted and authenticated. This
document introduces an improved system process with a secure
algorithm called Chronos. Chronos is backwards compatible with
NTPv4, as an NTP client that runs Chronos is interoperable with
[RFC5905]-compatible NTPv4 servers.
Chronos achieves accurate synchronization even in the presence of
powerful attackers who are in direct control of a large number of NTP
servers. Chronos leverages ideas from distributed computing
literature on clock synchronization in the presence of adversarial
(Byzantine) behaviour.
R.Schiff, et al. Expires March 5, 2020 [Page 2]
Internet-Draft NTP Extention with Chronos September 2019
A Chronos client iteratively "crowdsources" time queries across
multiple NTP servers and applies a provably secure algorithm for
eliminating "suspicious" responses and averaging over the remaining
responses. Chronos is carefully engineered to minimize communication
overhead so as to avoid overloading NTP servers. Chronos' security
was evaluated both theoretically and experimentally with a prototype
implementation. The experimental results indicate that in order to
implement a successful time-shifting attack on a Chronos client by
over 100ms from the UTC, even a powerful man-in-the-middle attacker
requires over 20 years of effort in expectation. The full paper is
in [Chronos_paper].
Chronos differs from the current NTPv4 in two aspects. First, the
Chronos client relies on a large number of NTP servers, from which
only few are chosen at random in order to avoid overloading the
servers. Second, the selection algorithm uses an approximate
agreement technique to remove outliers, thus limiting the attacker's
ability to contaminate the chosen time samples. These Chronos client
mechanisms have provable security guarantees against man-in-the-
middle attackers and attackers who are capable of compromising a
large number of NTP servers.
2. Conventions Used in This Document
2.1. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
2.2. Terms and Abbreviations
NTPv4 Network Time Protocol version 4 [RFC5905].
Selection process Clock filter algorithm and system process
[RFC5905].
2.3. Notations
R.Schiff, et al. Expires March 5, 2020 [Page 3]
Internet-Draft NTP Extention with Chronos September 2019
Describing Chronos algorithm, the following notation are used.
+---------+---------------------------------------------------------+
| Notaion | Meaning |
+---------+---------------------------------------------------------+
| w | An upper bound on the distance from the local time at |
| | any NTP server with an accurate clock ("truechimer" as |
| | in [RFC5905]) |
| Cest | the client's estimate for the time that passed since |
| | its last synchronization to the server pool (sec) |
| ERR | (2W*Cest)/1000 |
| K | panic trigger |
| tc | the current time, as indicated by the client's local |
| | clock [sec] |
+---------+---------------------------------------------------------+
Table 1: Chronos Notations
3. Extension for NTP Selection Process
A client that runs Chronos does not implement the functionality
described in Sections 10 and 11 in [RFC5905]. Instead, the client
implements the behavior described in this section and the next one.
3.1. Peer calibration Process
The peer calibration process gathers a server pool of hundreds of
servers. Each NTP client conducts the peer process as in Section 9
in [RFC5905], on an hourly basis for 24 consecutive hours and
generates the union of all received IP addresses. Importantly, this
is executed in the background once in a long time (e.g., every few
weeks/months).
3.2. Chronos Selection Process
The Chronos selection process samples the server pool and removes
outliers (replaces the clock filter algorithm and the system process
as in [RFC5905]). First, a subset on the order of tens of the
servers in the server pool is selected at random. Then, out of the
tens of collected samples, the third lowest-value samples and third
highest value samples are discarded.
Given the remaining samples, Chronos checks two conditions:
o The maximal distance between every two time samples does not
exceed 2w.
R.Schiff, et al. Expires March 5, 2020 [Page 4]
Internet-Draft NTP Extention with Chronos September 2019
o The average value of the remaining samples is at a distance of at
most ERR+2w from the client's local clock.
(where w,ERR are described in Table 1).
In the event that both of these conditions are satisfied, the average
of the remaining samples is the "final offset". Otherwise, a few
tens of the servers from the pool are sampled again, in the exact
same manner. This re-sampling process continues until the two
conditions are finally satisfied or the number of times the servers
are re-sampled exceeds a "Panic Trigger" (K in Table 1), in which
case, Chronos enters a "Panic Mode".
In panic mode a Chronos client queries all the servers in the server
pool, orders the collected time samples from lowest to highest and
eliminates the bottom third and the top third of the samples. The
client then averages over the remaining samples, which become the new
"final offset".
As in [RFC5905], the final offset is passed to the clock discipline
algorithm to steer the system clock to the correct time.
4. Chronos Pseudocode
The Chronos pseudocode Time Sampling Scheme is the following:
counter := 0
While counter < K do
S := sample(m) //gather sample from tens randomly chosen servers
T := bi-side-trim(S,1/3) //trim third lowest and highest values
if (max(T) -min(T) <= 2w) and (|avg(T)-tc| < ERR + 2w) Then
return avg(t)
end
counter ++;
end
// panic mode;
S := sample(n);
T := bi-sided-trim(S,n/3) //trim bottom and top thrids;
return avg(T)
5. Precision Vs. Security
Chronos client changes the list of the sampled servers more
frequently than NTPv4 [Chronos_paper], without using NTPv4 filters.
This enables Chronos to be provably more secure than NTPv4 [RFC5905]
but might adversely affect its precision and accuracy. Therefore we
R.Schiff, et al. Expires March 5, 2020 [Page 5]
Internet-Draft NTP Extention with Chronos September 2019
add the following smoothing mechanism: Chronos returns the offset
with minimal absolute value unless its distance from the average
offset is larger than a predefined value. Another approach we
considered was to use the same set of servers as in the previous
sample, unless the difference between the current offset and the new
offset is larger than a predefined value.
In our experiments we observed that with the smoothing mechanism,
Chornos and NTP are similar in terms of precision and accuracy when
there is no attack.
6. Acknowledgements
The authors would like to thank Miroslav Lichvar, Yaakov.J.Stein and
Karen O'Donoghue for contributions to this document and helpful
discussions and comments.
7. IANA Considerations
This memo includes no request to IANA.
8. Security Considerations
As explained above, a Chronos client repeatedly gathers time samples
from small subsets of a large pool of NTP servers. The following
form of a man-in-the-middle (MitM) Byzantine attacker is considered:
a MitM attacker is assumed to control a subset of the servers in the
pool of available servers and is capable of determining precisely the
values of the time samples gathered by the Chronos client from these
NTP servers. The threat model thus encompasses a broad spectrum of
MitM attackers ranging from fairly weak (yet dangerous) MitM
attackers only capable of delaying and dropping packets to extremely
powerful MitM attackers who are in control of authenticated NTP
servers. MitM attackers captured by this framework might be, for
example, (1) in direct control of a fraction of the NTP servers
(e.g., by exploiting a software vulnerability), (2) an ISP (or other
Autonomous-System-level attacker) on the default BGP paths from the
NTP client to a fraction of the available servers, (3) a nation state
with authority over the owners of NTP servers in its jurisdiction, or
(4) an attacker capable of hijacking (e.g., through DNS cache
poisoning or BGP prefix hijacking) traffic to some of the available
NTP servers. The details of the specific attack scenario are
abstracted by reasoning about MitM attackers in terms of the fraction
of servers with respect to which the attacker has MitM capabilities.
Analytical results (in [Chronos_paper]) indicate that in order to
succeed in shifting time at a Chronos client by even a small time
R.Schiff, et al. Expires March 5, 2020 [Page 6]
Internet-Draft NTP Extention with Chronos September 2019
shift (e.g., 100ms), even a powerful man-in-the-middle attacker
requires many years of effort (e.g., over 20 years in expectation).
It should be noted that Chronos provides resilience to MitM attacks
that cannot be achieved by cryptographic authentication protocols.
However, adding an authentication and crypto-based security layer to
the Chronos layer is important for achieving high security guarantees
and detection of various spoofing and modification attacks.
Further details about the Chronos security considerations and
guarantees are discussed in [Chronos_paper].
9. References
9.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC5905] Mills, D., Martin, J., Ed., Burbank, J., and W. Kasch,
"Network Time Protocol Version 4: Protocol and Algorithms
Specification", RFC 5905, DOI 10.17487/RFC5905, June 2010,
<https://www.rfc-editor.org/info/rfc5905>.
9.2. Informative References
[Chronos_paper]
Deutsch, O., Schiff, N., Dolev, D., and M. Schapira,
"Preventing (Network) Time Travel with Chronos", 2018,
<http://wp.internetsociety.org/ndss/wp-
content/uploads/sites/25/2018/02/
ndss2018_02A-2_Deutsch_paper.pdf>.
[RFC2629] Rose, M., "Writing I-Ds and RFCs using XML", RFC 2629,
DOI 10.17487/RFC2629, June 1999,
<https://www.rfc-editor.org/info/rfc2629>.
[RFC3552] Rescorla, E. and B. Korver, "Guidelines for Writing RFC
Text on Security Considerations", BCP 72, RFC 3552,
DOI 10.17487/RFC3552, July 2003,
<https://www.rfc-editor.org/info/rfc3552>.
[RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an
IANA Considerations Section in RFCs", RFC 5226,
DOI 10.17487/RFC5226, May 2008,
<https://www.rfc-editor.org/info/rfc5226>.
R.Schiff, et al. Expires March 5, 2020 [Page 7]
Internet-Draft NTP Extention with Chronos September 2019
[roughtime]
Patton, C., "Roughtime: Securing Time with Digital
Signatures", 2018,
<https://blog.cloudflare.com/roughtime/>.
Authors' Addresses
Neta Rozen Schiff
Hebrew University of Jerusalem
Jerusalem
Israel
Phone: +972 2 549 4599
Email: neta.r.schiff@gmail.com
Danny Dolev
Hebrew University of Jerusalem
Jerusalem
Israel
Phone: +972 2 549 4588
Email: danny.dolev@mail.huji.ac.il
Tal Mizrahi
Huawei Network.IO Innovation Lab
Israel
Email: tal.mizrahi.phd@gmail.com
Michael Schapira
Hebrew University of Jerusalem
Jerusalem
Israel
Phone: +972 2 549 4570
Email: schapiram@huji.ac.il
R.Schiff, et al. Expires March 5, 2020 [Page 8]
