Skip to main content

Synchronizing Internet Clocks (sic)
draft-alavarez-hamelin-tictoc-sic-00

The information below is for an old version of the document.
Document Type
This is an older version of an Internet-Draft whose latest revision state is "Expired".
Authors José Ignacio Alvarez-Hamelin , David Samaniego , Alfredo A. Ortega
Last updated 2018-02-28
RFC stream (None)
Formats
Stream Stream state (No stream defined)
Consensus boilerplate Unknown
RFC Editor Note (None)
IESG IESG state I-D Exists
Telechat date (None)
Responsible AD (None)
Send notices to (None)
draft-alavarez-hamelin-tictoc-sic-00
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]