| 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
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.
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].
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.
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.
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.
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).
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.
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.--
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 ,
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).
phi(t) = K + F * t , (5)
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:
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.”
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.--
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.
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 ).
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 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.
======================================================================= | 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.--
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.
======================================================================= | 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.--
=======================================================================
| 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.--
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.
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.
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.--
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.
t = actual_c + actual_m * timestamp (8)
Figure 8
Client sic runs the algorithm Figure 4 and also SHOULD provide the corrected time as
Different ways of doing this task are possible:
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.
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).
MTIE = max [phi(t')] - min [phi (t)] , (9)
We use MTIE defined as follows (see [ToIM1996]):
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 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.--
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.
This protocol implements protection against MitM attacks. The identity of endpoints is guarantee by signed valid certificates.
This memo makes no requests of IANA.
The authors thank to Ethan Katz-Bassett, Zahaib Akhtar, the USC and CAIDA for lodging the testbed of sic.
| [RFC2119] | Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997. |
| [RFC5905] | Mills, D., Martin, J., Burbank, J. and W. Kasch, "Network Time Protocol Version 4: Protocol and Algorithms Specification", RFC 5905, DOI 10.17487/RFC5905, June 2010. |
| [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. |
| [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. |
| [alfa-estables] | Uchaikin, V. and V. Zolotarev, "Chance and stability: stable distributions and their applications.", Walter de Gruyter. (Book), 1999. |
| [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. |