Subject: Re: [Ntp] Antw: [EXT] Handling synchronization loops

From: Miroslav Lichvar <[email-masked]>
Date: Tue, 1 Mar 2022 15:40:56 +0100

On Thu, Feb 24, 2022 at 09:24:42PM -0800, Hal Murray wrote:
> Suppose we start with a running system and each server has a full graph of its 
> upstream servers.  What would a new server need to know to join?  If using one 
> of the new server links would make a loop, how do we decide if the new server 
> should drop that link or some link in the established system should be 
> dropped?  A variation on that is a link coming back up.  Or maybe that's all 
> we need.  A new server is just a bunch of links coming up.

To keep it simple, I think the server which would close the loop
should avoid doing that. Maybe there could be some negotiation, but
I'd rather not go there if not necessary.

> Do we need to avoid all loops?  Assume that a server derives the target time 
> with some weighting of its upstream servers.  If a loop would contribute less 
> than X%, is that good enough?  What is a reasonable value of X?

That depends on the implementation and configuration. I'd prefer to
avoid all loops.

> Do we also want to investigate other weak links?  For example depending on a 
> single stratum 1 server.  I expect the logic for that will also catch cases 
> where everything funnels through a single server at other levels.

With both the bloom filter and the graph, I think there should be a
way to lower the weights of sources that share too many sources, e.g.
using the Hamming distance.

> Should we keep track of NTS vs unauthenticated links?  But authenticated 
> doesn't actually tell us anything about the quality of a clock.  We can 
> probably figure out if the time is good using NTP.  By "quality", I'm 
> interested in the reliability of the people running the server.

That could be just a single bit indicating the server has only
authenticated sources or an authenticated source trusted over
unauthenticated sources.

> How much trouble could a bad guy generate by pretending to be a server and 
> asking to break all sorts of important links because they will cause a loop?

Good question. An attacker could prevent synchronization several
layers below if the reference ID is known. Is this more powerful than
what is already possible by setting a high stratum close to 16?

> Miroslav: You had good graphs with a simple loop.  Can you make another one 
> with a longer loop?

Sure, here is a nice example with 4 ntpd clients configured in a loop.
Each one is polling a remote stratum-1 server and one neighbour:
A->B->C->D->A

https://fedorapeople.org/~mlichvar/ntpresponse/sync-loop.png

You can see how the response is moving in the loop and it gets back at
the right time to amplify the ringing, causing it to completely fall
apart.

-- 
Miroslav Lichvar

---

From: Miroslav Lichvar <[email-masked]>
Date: Thu, 3 Mar 2022 17:29:22 +0100

On Wed, Feb 16, 2022 at 03:29:30PM +0100, Miroslav Lichvar wrote:
> I think we might need to specify for how long should clients wait
> before selecting a server that was in a loop again. This could be a
> random number based on their polling interval, stratum, and the number
> of polls it takes to exchange the whole filter. There could also be a
> requirement for servers to delay removing reference IDs from their
> filters.

I spent some time testing this in simulations.

Let's consider the example with four local clients configured to poll
one another in a loop at a constant polling interval of 64s.

With the NTPv4 refid a loop is formed and it is not detected:

00:00:00              A      B      C      D      A
00:05:22              A      B   -> C      D   -> A
00:05:23              A      B   -> C   -> D   -> A
00:05:24              A   -> B   -> C   -> D   -> A

With the proposed extension field using Bloom filter and clients not
selecting the source only if they would close the loop it doesn't
reliably get to a stable state. It can look like this (the dot
indicates a detected loop):

00:00:00              A      B      C      D      A
00:04:19              A      B      C   -> D      A
00:05:23              A   -> B   -> C   -> D      A
00:06:27              A   -> B   -> C   -> D   -> A
00:07:32              A   -> B     .C   -> D   ->.A
00:08:36              A   ->.B     .C   -> D     .A
00:08:37              A     .B     .C   -> D      A
00:09:41              A      B     .C   -> D   -> A
00:09:42              A   -> B      C   -> D   -> A
00:10:46              A   -> B   -> C   -> D   -> A
00:11:52              A   -> B   ->.C   -> D   -> A
00:12:55              A   ->.B     .C   -> D   -> A
...
01:51:04              A      B   -> C   -> D   -> A
01:52:00              A   -> B   -> C   -> D   -> A
01:52:02              A   -> B   ->.C   -> D   -> A
01:52:08              A   -> B     .C   -> D   -> A
01:54:10              A   ->.B     .C   -> D   -> A
01:55:14              A     .B     .C   -> D   -> A
01:55:15              A      B     .C   -> D   -> A
01:55:17              A      B      C   -> D   -> A
01:55:23              A      B   -> C   -> D   -> A
01:56:19              A   -> B   -> C   -> D   -> A
01:56:21              A   -> B   ->.C   -> D   -> A
01:56:28              A   -> B     .C   -> D   -> A
01:58:29              A   ->.B     .C   -> D   -> A
01:59:32              A     .B     .C   -> D   -> A
01:59:33              A      B     .C   -> D   -> A
01:59:36              A      B      C   -> D   -> A
...

Adding a random delay to the selection of a source which previously
indicated a loop seems to help, but it still takes some time before it
settles down. Here is an example:

00:00:00              A      B      C      D      A
00:05:23              A   -> B      C      D      A
00:05:24              A   -> B   -> C   -> D   -> A
00:06:29              A   -> B   -> C   -> D   ->.A
00:07:33              A   -> B   -> C   ->.D     .A
00:07:34              A   -> B   -> C     .D      A
00:08:36              A   -> B   ->.C     .D      A
00:08:37              A   -> B     .C      D      A
00:08:38              A   -> B     .C      D   -> A
00:08:39              A   -> B     .C   -> D   -> A
00:09:40              A   -> B      C   -> D   -> A
00:09:42              A   -> B   -> C   -> D   -> A
00:10:44              A   -> B   -> C   -> D      A
00:10:47              A   -> B   -> C   ->.D      A
00:10:48              A   -> B   -> C     .D      A
00:11:49              A   -> B   ->.C     .D      A
00:11:51              A   -> B     .C      D      A
00:12:53              A   -> B      C      D      A
00:12:56              A   -> B   -> C      D      A
00:14:02              A   -> B   -> C      D   -> A
00:15:08              A   -> B   -> C   -> D   -> A
00:16:07              A   -> B   -> C   -> D   ->.A
00:16:10              A   -> B   -> C   ->.D   ->.A
00:16:11              A   -> B   -> C   ->.D     .A
00:16:12              A   -> B   -> C     .D     .A
00:17:11              A   -> B   -> C     .D      A
00:17:15              A   -> B   -> C     .D   -> A
00:19:24              A   -> B   -> C      D   -> A
00:20:28              A   -> B   -> C     .D   -> A

Basically, we need all except one source in the configured loop to
select and stick to it.

I tried also delaying the distribution of the Bloom filter as it would
be if it was transmitted in parts. It didn't seem to make a difference
wrt the time it takes to settle down.

There is a possibility for the client to measure the delay of the loop
using a secondary reference ID which could be added to the filter at
any time. Would that help?

Any thoughts?

-- 
Miroslav Lichvar