TICTOC J. Alvarez-Hamelin, Ed.
Internet-Draft D. Samaniego
Updates: none (if approved) A. Ortega
Intended status: Standards Track Universidad de Buenos Aires
Expires: September 1, 2018 February 28, 2018
Synchronizing Internet Clocks (sic)
draft-alavarez-hamelin-tictoc-sic-00
Abstract
This memo introduces a new secure method to synchronize difference
clocks on the Internet, assuring smoothness (i.e., frequency
stability) and robustness to man-in-the-middle attacks. This type of
synchronization is useful for some kind of measurements, like
traffic, load, or relative time measurements. The "sic" proposal is
highly accurate, with an MTIE (Maximum Time Interval Error) less than
25 microseconds by a minute for the 90% of the cases, and it is based
on a regular packets exchange.
Requirements Language
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 [RFC2119].
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 September 1, 2018.
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 1]
Internet-Draft (sic) February 2018
Copyright Notice
Copyright (c) 2018 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(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. Overview of sic protocol . . . . . . . . . . . . . . . . . . 3
3. The formal definition of sic protocol . . . . . . . . . . . . 7
3.1. Algorithm description . . . . . . . . . . . . . . . . . . 7
3.2. Protocol definitions . . . . . . . . . . . . . . . . . . 12
3.3. Protocol packet specification . . . . . . . . . . . . . . 14
3.4. How to use sic . . . . . . . . . . . . . . . . . . . . . 15
4. Implementation of sic protocol . . . . . . . . . . . . . . . 16
4.1. Evaluation . . . . . . . . . . . . . . . . . . . . . . . 16
5. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . 17
6. Security Considerations . . . . . . . . . . . . . . . . . . . 18
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 18
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 18
9.1. Normative References . . . . . . . . . . . . . . . . . . 18
9.2. Informative References . . . . . . . . . . . . . . . . . 18
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 19
1. Introduction
There are different types of clock synchronization on the Internet.
NTP [RFC5905] remains one of the most popular because a potential
user does not need any extra hardware, and it is practically a
standard in most of the operating systems distributions. Its working
principle relays on time servers having some kind of precise clock
source, like atomic clocks or GPS based. For most of the needs, NTP
provides an accurate synchronization. Moreover, NTP recently
incorporates some strategies oriented to avoid man-in-the-middle
(MitM) attacks. It has a potential accuracy of tens of milliseconds.
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 2]
Internet-Draft (sic) February 2018
When accuracy and stability are needed, others proposal arise, e.g.,
the PTP [RFC8173] clock. This mechanism was also defined as the IEEE
Std. 1588-2008, and incorporates some hardware to provide a highly
accurate clock. The main problem with this approach is that you need
extra (and somehow expensive too) equipment in each point requiring
to perform measurements. In the same way, the GPS (Global Position
System) is a non-expensive solution, but you continue to need to
provide every point of measurement with a GPS unit and also provide
it with a sky clear view for working.
Another proposal is the TSClocks [ToN2008], which take advantage of
the internal computers' clock. This work has been shown a very
interesting solution because it is not expensive and can be used in
any computer connected to the Internet. This solution was proposed
in the beginning at LAN (Local Area Network) level, and then it has
been extended to other situations. In [ToN2008] authors report an
error en the difference clock about half of hundred of microseconds
for a WAN connection with 40ms of RTT (Round Trip Time).
Our design is close to TSClocks but it takes advantage of statistics
to perform better. Because measurements are done on the Internet,
route changes are frequent, so we include its detection. Finally,
our implementation also contemplates the protection to MitM attacks,
including the signature of measurements in each packet. It also has
no constraints on the quality of the server's clock and the distance
of both ends (as the TSClocks has).
2. Overview of sic protocol
Synchronizing Internet Clocks is a protocol-oriented to provide
difference clocks in two endpoints connected to the Internet. While
absolute clocks try to know the exact difference between them,
difference clocks are useful when you measure time variation (e.g.,
traffic, load, etc.). The model of typical time-measurement is shown
in Figure 1.
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 3]
Internet-Draft (sic) February 2018
XXXXXXXX XXXXXXXX
XXXXXX XXX X
XX XXX
+----+----------+XX XXXX
| XX XX
| X Iternet XX
| XX XXX
+--+------+ XXXXXX XX+---------+------+
| | X XX |
| Client | XX XXX |
| | XX XXX XXXXX XX +---+----+
| | XXX XXXXXXX XXXXXX | |
+---------+ | Server |
| |
| |
+--------+
Figure 1: The clock synchronization of sic.--
In this model, sic performs measurements with packets in the way
shown in Figure 2.
t2 t3
Server +---------------@-------*----------------------------->
/ \_ C_s [s]
/ \_
/ \_
/ \_
/ \_
/ \_
/ \_
/ \_
/ \_
/ \_
/ \_ C_c [s]
Client +---*------------------------------------------@------>
t1 t4
Figure 2: Time line of packets.--
This representation shows a time line for each side (client and
server), and the diagonal lines depict a packet traversing some
physical space (wires, routers, and switches). As it is shown, the
packet travel times are not identical, because routes and traffic en
each case differs. The difference between the client clock C_c and
the server clock C_s can be modeled as:
C_c = Cs + phi ,
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 4]
Internet-Draft (sic) February 2018
phi(t) = C_c(t) - C_s(t) , (1)
where phi is the difference. When there is no traffic (i.e., RTT is
constant) and routes are equal, the difference between clocks can be
computed as:
phi[c->s] = t1 - ( t2 - RTT/2 ) , (2)
phi[c<-s] = t4 - ( t3 + RTT/2 ) , (3)
and phi[c->s] = phi[c<-s]. The general equation for the RTT is:
RTT = ( t2 - t1 ) + ( t4 - t3 ) . (4)
Computing Equations 2 and 3 for the this simplified case yields on
phi = RTT. Notice that routes are not symmetrical in most of the
cases; therefore it is not possible to determine the absolute clocks'
difference.
The sic protocol is based on the statistics and traffic behavior. It
is observed the RTT between two endpoints follows a heavy-tailed
distribution, where alpha-stable distribution shows as one possible
model [traffic-stable]. This distribution can be characterized by
four parameters: the localization "delta," the stretching "gamma,"
the tail "alpha," and the symmetry "beta," [alfa-estables] .The
location parameter is highly related to the mode of the distribution:
delta > 0. The stretching is related to the dispersion: gamma > 0.
The symmetry, -1 <= beta <= 1, indicates if the distribution is skew
to the right (the tail decays to the left) for positive values or the
other direction for negatives ones. Finally, the tail alpha, defined
in (0,2], indicates if the distribution is Gaussian one when alpha=2,
a power law without variance for alpha <2, and also without statistic
mean for alpha<1. The alpha-stable distribution is the
generalization of the Central Limit Theorem for any distribution
(i.e., it includes the cases without variance or mean).
Therefore, sic performs periodic measurements to infer the difference
of two clocks in the Internet taking advantage of the empiric
observations. The proposal periodicity is 1 second, and we estimate
the parameters of the simple skew model:
phi(t) = K + F * t , (5)
where phi(t) = C_c - C_s, K is a constant representing the absolute
difference of time of client clock C_c and server clock C_s, and f is
the rate parameter. As sic is a difference clock, we only estimate
the frequency parameter "F."
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 5]
Internet-Draft (sic) February 2018
Notice the "K" parameter cannot be estimated using just endpoints
measurements. Considering the following asymmetry definition:
t[c->s]
A = 1 - --------- , (6)
t[c<-s]
where t[c->s] is the minimum time for the client to the server. The
maximum of Equation 6 is A=1, which is unlucky, and this establishes
the hard bound for the error of K as min(RTT). In our experiments,
it was always less than min(RTT)/2.
Another problem with most of the synchronization protocols is the
estimation of minimum RTT, whose estimation depends upon the time-
window where is done. Figure 3 shows the error on the minimum RTT
estimation when a window of 10 minutes is used. That is, we computed
the minimum RTT over a week (mRTTw), we calculated the minimum RTT on
windows of 10 minutes (mRTT10m), and the error is mRTT10m - mRTTw.
This case occurs in an experiment where the minimum latency between
probes was of 9431 microseconds during one week, i.e., mRTTw=9431
microseconds. Notice that mRTT10m varies a lot, and their values can
be more than 450 microseconds above the minimum RTT in a week. This
error is a consequence of the statistical behavior of the RTT which
can be model by the alfa-stable distribution.
Error of the min(RTT)
[micro-seconds]
500 +------|-------|------|------|------|-------|------|------+
| + + + O + + + + |
| * |
400 |-+ ** O +-|
| * * O O ** O O |
| O * * ** * ** ** ** |
300 |-+ * O*O * O O* * O*O * * O O *-|
| O* O O * * * O * * * *|
| O * O ** * * O * * * O** O|
200 |-* * * * * O * O * O*O * O +-|
|** O O * ** * * * * O |
|O * *** O * * * |
100 |-+ O O O * O +-|
| ** |
| ** |
0 |-+ + + O + + + + + +-|
+------|-------|------|------|------|-------|------|------+
0 50 100 150 200 250 300 350 400
time [minutes]
Figure 3: Min RTT error, estimated every 10 minutes along 7 hours.--
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 6]
Internet-Draft (sic) February 2018
Then, the sic protocol estimates phi(t) of Equation 5 using
statistics on the measurements, taking advantage of the inherent
properties of RTT, i.e., the heavy tail distribution and its alfa-
stable distribution model. The way of operation is sending packets
periodically, compute an estimation of phi(t), and provide a
corrected local clock with:
t_c = t_l + phi(t_l) , (7)
where t_c is the corrected time and t_l the local clock time (notice
that is according to Equation 1).
The sic protocol also detects the change of route for their packets
by seeking a nonnegligible difference between the minimum RTT of the
actual and past round. In next section, we provide different
mechanisms to implement this service.
3. The formal definition of sic protocol
In this section we present the sic's algorithm (see Section 3.1), we
introduce the definitions of their parameters, and finally, we
provide the packet format.
The sic protocol MUST sign the packets with the deterministic
Elliptic Curve Digital Signature Algorithm (ECDSA) specified in the
[RFC6979], to make it resistant to MitM attacks. In order to avoid
delays when a packet is signed, sic sign them in a deferred fashion.
That is, in each packet carries the signarue of the previous packet
(see algorigthms in Figure 6 and Figure 5 ).
3.1. Algorithm description
We provide the formal description of sic that implementations MUST
respect. The sic protocol runs on an infinite loop that can be
identified with tree states: NOSYNC, PRESYNC, and SYNC. These states
are triggered by the variables errsync, presync, and synck.
Lines 1 to 4 in Figure 4 init the data structures needed and set the
algorithm the NOSYNC. It initiates on the NOSYNC state, filling a
measurement window with the phi's estimation of Equation 2 (line 8).
Notice that it can also be used Equation 3, or an average of both,
but in our experiments, it worked better use just one way to make the
estimations. The possible explanation is that measurements are
affected by the same type of traffic.
The median of the measurement window is also computed in line 9,
while lines 10-12 are used to verify if there is a path change in the
measurements. When an appreciable difference is detected (bonded by
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 7]
Internet-Draft (sic) February 2018
errRTT) in line 13, the "else" clause is executed and the systems re-
initiates the cycle (see lines 17-22). Notice that line 13 verifies
if the absolute value of the minimum RTTs is lower than a percentage
of minimum over the complete RTT window.
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 8]
Internet-Draft (sic) February 2018
=======================================================================
| sic algorithm |
=======================================================================
1 Wmedian <-0, Wm <-0, WRTT <-0, actual_m <-0, actual_c <-0
2 presync <- INT_MAX - P, epochsync <- INT_MAX - P, n_to <-0
3 synck <- false, errsync <- epoch, set(0, 0, NOSYNC), e_prev<-epoch
4 send_sic_packet(SERVER_IP, TIMEOUT)
5 for each timer(RUNNING_TIME) == 0
6 | (epoch, t1, t2, t3, t4, to) <- send_sic_p(SERVER_IP,TIMEOUT)
7 | if (to == false) then
8 | | Wm <- t1 - t2 + (t2 - t1 + t4 - t3)/2
9 | | Wmedian <- median(Wm)
10 | | WRTT <- t4 - t1 size(W)
11 | | RTTf <- min(WRTT[size(WRTT)/2,size(WRTT)])
12 | | RTTl <- min(WRTT[0,size(WRTT)/2])
13 | | if ((|RTTf - RTTl| <= errRTT * min(WRTT)) then
14 | | | if (epoch >= presynck + P)) then
15 | | | | presynck <- true
16 | | | end if
17 | | else
18 | | | synck <- false, Wmedian <- 0
19 | | | Wm <- 0, errsync <- epoch, n_to <- 0
20 | | | epoch_sync <- INT_MAX - P, pre_sync <- INT_MAX - P
21 | | | set(0, 0, NOSYNC)
22 | | end if
23 | | if ((synck == true) && (epoch >= epochsync + P)) then
24 | | | (m, c) <- linear_fit(Wmedian)
25 | | | actual_c <- c
26 | | | actual_m <- (1-alpha) * m + alpha * actual_m
27 | | | epochsync <- epoch, n_to <- 0
28 | | | set(actual_m, actual_c, SYNC)
29 | | else
30 | | | if (epoch == errsync + MEDIAN_MAX_SIZE) then
31 | | | | presync <- epoch
32 | | | end if
33 | | | if (epoch >= presync + P) then
34 | | | | (actual_m, actual_c) <- linear_fit(Wmedian)
35 | | | | synck <- true , epoch_sync <- epoch
36 | | | | set(actual_m, actual_c, PRESYNC)
37 | | | end if
38 | | end if
39 | else
40 | | to <- false
41 | end if
42 end for
=======================================================================
Figure 4: Formal description of sic.--
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 9]
Internet-Draft (sic) February 2018
Several conditions should be verified To pass form NOSYNC to PRESYNC.
First, the "else" condition of line 29 should occur, and also the
elapsed time between errsync and actual epoch should be
MEDIAN_MAX_SIZE (30-32). Therefore, when it also P time is passed
form presync, the condition on line 33 is true, and the system
arrives at PRESYNC, providing an initial estimation of phi.
Then, if there is no route change, the condition in line 14 will be
true when the time was increased in another P period. Then, the
system is in SYNC state, and it provides the estimation of phi(t) in
line 28. Notice that every P time the estimation of phi(t) is
computed unless a change of route occurs (lines 13 and 17-22).
The function in line 6: (epoch, t1, t2, t3, t4, to) <-
send_sic_packet(SERVER_IP, TIMEOUT), has an special treatment. It
sends the packets specified in SectionSection 3.3, which have
signatures. To avoid the time that is needed to compute de
signature, we implemented a policy to send the signature of the
previous packet, and if an error is detected, we can stop the
synchronization just one loop ahead.
Figure 5 illustrates how the client side MUST implement the function
send_sic_p (server, TIMEOUT). This function computes the timestamp
t1 in line 1, build and send the UDP packet in lines 2-3. Then, if
there is no timeout, it calculates the t4 timestamp (line 5), and if
there is not lost packets verify the signature of the previous one in
lines 8-18. Notice if that signature is not valid with the received
certificate, then the systems change to NOSYNC state immediately in
line 11, and it also does the same if the limit of time without
receiving packets MAX_to is reached. Finally, it stores the received
packet into a global variable prev_rcv_pck to use in the next packet
(line 18). Notice that n_to, the lost packets, is a global variable,
as well as the epoch of the previous packet: e_prev.
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 10]
Internet-Draft (sic) February 2018
=======================================================================
| function: send_sic_p(server, TIMEOUT) |
=======================================================================
1 t1 <- get_timestamp()
2 sic_P <- sic_pck(t1, 0, 0, prev_sig)
3 (to, rcv_sic_pck) <- send(sic_P,UDP_PORT, SERVER_IP, TIMEOUT)
4 if (to == false) then
5 | t4 <- get_timestamp()
6 | epoch <- trunc_to_seconds(t1)
7 | prev_sig <- get_signature(sic_P)
8 | if (epoch - e_prev <= RUNNING_TIME) then
9 | | if (n_to < MAX_to) then
10 | | | if (verify(prev_rcv_pck,rcv_sic.CERT) == false) then
11 | | | | set(0, 0, NOSYNC)
12 | | | else
13 | | | | n_to <- 0, e_prev <- epoch
14 | | | end if
15 | | else
16 | | | set(0, 0, NOSYNC)
17 | | end if
18 | end if
19 | prev_rcv_pck <- rcv_sic_pck
20 | t2 <- rcv_sic_pck.t2
21 | t3 <- rcv_sic_pck.t3
22 else
23 | n_to <- n_to + 1
24 end if
25 return (epoch, t1, t2, t3, t4, to)
=======================================================================
Figure 5: The send_sic_p function.--
The server sic algorithm is presented in Figure 6. It uses
prev_sic_P{}, which is a structure to store the received previous
signatures, indexed by the IP client addresses (CLIENT_add contains
its IP and UDP port); and the same for prev_sig{} with the previously
sent signatures. Line 6 verifies either signature is null because it
is the first packet, or it is a valid signature. In both cases, the
algorithm process the packet computing t3, building up the sic
packet, sending it and computing its signature (stored to send in the
next reply) in lines 7-11. Next, the actual packet is stored in the
prev_sic_P{} structure, line 13.
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 11]
Internet-Draft (sic) February 2018
=======================================================================
| Server sic algorihm |
=======================================================================
1 prev_sic_P{} <- null, prev_sig{} <-- null
2 while (RUNNING == true) then
3 | if (receive() == true) then
4 | | t2 <- get_timestamp()
5 | | prev_sig <- get_signature(prev_sic_P{receive().CLIENT_add})
6 | | if (prev_sig == null) ||
| | (verify(prev_sig, CLIENT_add.CERT) == true) then
7 [ | | t3 <- get_timestamp()
8 | | | sic_P<-sic_pack(t1, t2, 3, prev_sig)
9 | | | send(sic_P, CLIENT_add.UDP, CLIENT_add.IP, TIMEOUT)
10 | | | prev_sig <- get_signature(sic_P)
11 | | | prev_sig{receive().CLIENT_add} <- prev_sig
12 | | end if
13 | | prev_sic_P{receive().CLIENT_add} <- receive().sic_pack
14 | end if
15 end while
=======================================================================
Figure 6: Algorith sic for the Server.--
3.2. Protocol definitions
We provide a formal definition of each used constants and variables;
the RECOMMENDED values are displayed in parentheses at the end of the
description. These constant and variables MUST be represented in a
sic implementation. All the types MUST be respected, and they are
expressed in "C" programming language running on a 64-bit processor.
a. Constants used for the sic algorithm (Figure 4)
1. RUNNING_TIME: is the period between sic packets are sent (1
second).
2. MEDIAN_MAX_SIZE: is the window size used to compute the
median of the measurements (600).
3. P: is the period between phi's estimation (60).
4. alpha: is a float in the [0,1], the coefficient of the
autoregressive estimation of the slope of phi(t) (0.05).
5. TIMEOUT: is the maximum time in seconds that a sic packet
reply is expected (0.8 seconds).
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 12]
Internet-Draft (sic) February 2018
6. SERVER_IP: is the IP address of the server (@IP in version 4
or 6).
7. errRTT: is a float that bounds the maximum difference to
detect a route change (0.2).
8. MAX_to: is an integer representing the maximum number of
packet lost (P/10).
9. CERT: is a public certificate of the other end, it is used
to verify signs of the packets.
10. UDP_PORT: is an integer with the port UDP where the service
is running on the server. (4444)
11. SERVER_IP: is the IP address of the server.
12. CLIENT_IP: is the IP address of the client.
b. States used for the sic algorithm (Figure 4)
1. NOSYNC: a boolean indicates that it is not possible to
correct the local time.
2. PRESYNC: a boolean indicates that sic is almost (P
RUNNING_TIME) seconds from the synchronization.
3. SYNC: a boolean indicates that sic is synchronized.
c. Variables used for the sic algorithms (Figure 4, Figure 5 and
Figure 6)
1. errsync: is an integer with the UNIX timestamp epoch of the
initial NOSYNC cycle. It is used to complete the window or
measurements (Wm) to compute their medians.
2. presync: is an integer with the UNIX timestamp epoch of the
initial PRESYNC cycle. It is used to wait until (P
RUNNING_TIME) seconds to the linear fit of phi(t).
3. synck: is an integer with the UNIX timestamp epoch of the
initial SYNC cycle. Every P RUNNING_TIME) seconds the
phi(t) function is estimated.
4. epochsync: is an integer with the last UNIX timestamp epoch
of synchronization. It is used to compute a new estimation
of phi(t), every (P RUNNING_TIME) seconds.
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 13]
Internet-Draft (sic) February 2018
5. epoch: is an integer with UNIX timestamp in seconds. It
carries the initial epoch of each sic measurement packet.
6. t1, t2, t3, t4: are long long integers to store the t UNIX
timestamps in microseconds.
7. actual_m : is a double with the slope for the phi(t)
estimation.
8. actual_c: is a double with the intercept for the phi(t)
estimation.
9. Wm: is an array of long long integers of MEDIAN_MAX_SIZE.
It stores the instantaneous estimates of phi(t).
10. Wmedian: is an array of long long integers of P size. It
saves the computed medians of Wm every RUNNING_TIME.
11. WRTT: is an array of long long integers of (2 P) size. It
stores the calculated RTT of last measurements.
12. RTTl: is a long long integer with the minimum of last P
RTTs. It is used to detect changes on the route from the
client to the server.
13. RTTf: is a long long integer with the minimum of previous P
RTTs. It is used to detect changes on the route from the
client to the server.
14. n_to: is an integer representing the number of lost packets
in the actual synchronization window P.
15. e_prev: is an integer with the UNIX timestamp epoch of the
last valid packet.
16. prev_rcv_pck: is a sic packet structure, the previous
received one.
3.3. Protocol packet specification
The sic protocol send packets with timestamps with the format of UNIX
timestamps in microseconds. Regarding Figure 2, the client takes a
timestamp t1 just before to send the packet. When server receives
the packet, immediately computes t2, and just before to send it
computes t3. When the client receives the packet, it calculates t4.
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 14]
Internet-Draft (sic) February 2018
Now, even if the server does not need the t1 because the proposed
protocol synchronizes a client with the server clock, this
information could be useful for the server in the future.
The packets are shown in Figure 7. They MUST be sent as UDP data,
and it MUST have five fields. The first tree corresponds to t1
(client), t2 (server), and t3 (server); the last one is the signature
of the previous message of the sender (client o server) with its
private key. The timestamps t1, t2, and t3 MUST be the UNIX
timestamp in microseconds represented with a long long integer of
64-bit C language.
The client and server certificates SHOULD be valid and signed ones
(only for experimentation user MAY use autogenerated ones).
f1 f2 f3 f4
+----------------------------------------+
| t1_c | 0 | 0 | Sig_c n-1 |
+----------------------------------------+
Client --> Server
f1 f2 f3 f4
+----------------------------------------+
| t1_c | t2_s | t3_s | Sig_s n-1 |
+----------------------------------------+
Server --> Client
Figure 7: Packet format for the sic protocol.--
3.4. How to use sic
To use the sic algorithm is needed a Server and one Client at least.
The Server can support multiple clients, and its maximum is a topic
of further study. The Server clock is considered the master one, and
all clients synchronize with it. Server side runs sic as a server in
a UDP_PORT number, as the algorithm Figure 6 specifies.
Client sic runs the algorithm Figure 4 and also SHOULD provide the
corrected time as
t = actual_c + actual_m * timestamp (8)
Figure 8
Different ways of doing this task are possible:
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 15]
Internet-Draft (sic) February 2018
Providing a client capable of reading the variables actual_m and
actual_c in shared memory and producing the result of Equation 8.
Providing a service in a UDP port answering the correcter
timestamp queries with Equation 8.
Other solution.
4. Implementation of sic protocol
In this section we present the prove of the sic concept through some
test that we already performed, and the current implementation of sic
in C language. Our implementation is publicly available
[sic-implementation]. Currently, it is under developping state to
include the signature of packets.
@@@@ We started with a version to test sic without the MitM
protection; soon we will finish with the secured version.
This protocol implements protection against MitM attacks. The
identity of endpoints is guarantee by signed certificates using the
deterministic Elliptic Curve Digital Signature Algorithm (ECDSA)
specified in the [RFC6979]. Server and Client should use signed and
valid ECDSA certificates to asure their identy, and each side has is
resposible to verify the public certificate of the other side before
to run the algorithm in Figure 4.
4.1. Evaluation
To verify the sic proposal, we tested it using three hosts with GPS
units. The first two were located at Buenos Aires, and the third at
Los Angeles. We slighted modified the algorithm in Figure 4 to
trigger each measurement using the PPS (pulse per second) signal
provided by the GPS unit. Then, recording the client and server
clocks with the PPS signal, we can determine the real phi function of
Equation 1, within the GPS error (it is several orders of magnitude
smaller than the sic protocol).
We use MTIE defined as follows (see [ToIM1996]):
MTIE = max [phi(t')] - min [phi (t)] , (9)
for every t' and t in the interval [t,t+s]; and we chose s=60
seconds. We selected two cases of study, one national and other
international. In Figure 9 we show the result of the MTIE (Maximum
Time Interval Error), evaluated in 60 seconds intervale, for the
experiment Buenos Aires-Buenos Aires (RTT of 40 ms) and Buenos Aires-
Los Angeles (RTT of 274 ms). The percentile 97.5 corresponds to 30
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 16]
Internet-Draft (sic) February 2018
microseconds for the Buenos Aires case, and 42 microseconds for the
Los Angeles case. We display the quartiles in Figure 10 . These
measurements were performed during a week in each case.
CDF
+--|-------|-------|-----|-------|----------|------|------+
1 |-+ + + + #########*#*#*#*#*#*#*#*#******|
| ##### ******* |
| #### **** |
0.8 |-+ ## *** +-|
| ### ** |
| ## *** |
0.6 |-+ ## ** +-|
| ## ** |
| ## ** |
0.4 |-+ ## ** +-|
| ## ** |
| ## ** |
0.2 |-+ ## *** +-|
| #### *** Buenos Aires ####### |
| #### *** Los Angeles ******* |
0 |##******* + + + + + + + +-|
+--|-------|-------|-----|-------|-----|----|------|------+
7 10 15 20 30 40 50 70 100
[micro-seconds]
Figure 9: Cumulative distribution function of the MTIE (60s).--
|Buenos Aires (40ms) | Los Angeles (273ms) |
====+====================+=====================+
Q3 | 14.69 | 19.29 |
----+--------------------+---------------------+
Q2 | 11.60 | 14.93 |
----+--------------------+---------------------+
Q1 | 9.41 | 12.26 |
Figure 10: Table with MTIE quartiles for two RTT cases.--
5. Conclusions
This document presents the sic algorithm to synchronize host clocks
using the Internet and resistant to MitM attacks. It also shows the
complete specification, implementation, and experiments results that
support it working principle. In particular, sic has demonstrated
stability on the clock rate less than 1ppm for most of the cases.
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 17]
Internet-Draft (sic) February 2018
6. Security Considerations
This protocol implements protection against MitM attacks. The
identity of endpoints is guarantee by signed valid certificates.
7. IANA Considerations
This memo makes no requests of IANA.
8. Acknowledgements
The authors thank to Ethan Katz-Bassett, Zahaib Akhtar, the USC and
CAIDA for lodging the testbed of sic.
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>.
[RFC6979] Pornin, T., "Deterministic Usage of the Digital Signature
Algorithm (DSA) and Elliptic Curve Digital Signature
Algorithm (ECDSA)", RFC 6979, DOI 10.17487/RFC6979, August
2013, <https://www.rfc-editor.org/info/rfc6979>.
[RFC8173] Shankarkumar, V., Montini, L., Frost, T., and G. Dowd,
"Precision Time Protocol Version 2 (PTPv2) Management
Information Base", RFC 8173, DOI 10.17487/RFC8173, June
2017, <https://www.rfc-editor.org/info/rfc8173>.
9.2. Informative References
[alfa-estables]
Uchaikin, V. and V. Zolotarev, "Chance and stability:
stable distributions and their applications.", Walter de
Gruyter. (Book), 1999.
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 18]
Internet-Draft (sic) February 2018
[sic-implementation]
Samariego, E., Ortega, A., and J. Alvarez-Hamelin,
"Synchronizing Internet Clocks",
https://github.com/CoNexDat/SIC, February 2018.
[ToIM1996]
Bregni, S., "Measurement of maximum time interval error
for telecommunications clock stability characterization",
Bregni S. Measurement of maximum time interval error for
telecommunicIEEE transactions on instrumentation and
measurement. 45(5):900-906, October 1996.
[ToN2008] Veitch, D., Ridoux, J., and S. Korada, "Robust
synchronization of absolute and difference clocks over
networks.", IEEE.ACM Transactions on Networking (TON)
17.2 (2009): 417-430, 2009.
[traffic-stable]
Carisimo, E., Grynberg, S., and J. Alvarez-Hamelin,
"Influence of traffic in stochastic behavior of latency.",
7th PhD School on Traffic Monitoring and Analysis (TMA),
Ireland, Dublin,, June 2017.
Authors' Addresses
Jose Ignacio Alvarez-Hamelin (editor)
Universidad de Buenos Aires
Av. Paseo Colon 850
Buenos Aires C1063ACV
Argentina
Phone: +54 11 5285-0716
Email: ihameli@cnet.fi.uba.ar
URI: http://cnet.fi.uba.ar/ignacio.alvarez-hamelin/
David Samaniego
Universidad de Buenos Aires
Av. Paseo Colon 850
Buenos Aires C1063ACV
Argentina
Phone: +54 11 5285-0716
Email: dsamanie@fi.uba.ar
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 19]
Internet-Draft (sic) February 2018
Alfredo A. Ortega
Universidad de Buenos Aires
Av. Paseo Colon 850
Buenos Aires C1063ACV
Argentina
Phone: +54 11 5285-0716
Email: ortegaalfredo@gmail.com
Alvarez-Hamelin, et al. Expires September 1, 2018 [Page 20]