Number of servers needed to detect one falseticker?

[Miroslav Lichvar]

Hi,

I'm wondering about the section 5.3.3 on the ntp support web

http://support.ntp.org/bin/view/Support/SelectingOffsiteNTPServers#Section_5.3.3.

It says and explains that minimum number of servers to detect one
falseticker is four, is that really correct? I understand that four is
better for reliability, but from the algorithm description
(http://www.eecis.udel.edu/~mills/ntp/html/select.html) and my tests
with a simulated falseticker it seems that three is enough.

Also, while running with two servers might be the worst configuration
for ntpd, it still could be prefered over the configuration with only
one server by users who would rather have two sources marked as
falsetickers and know a problem needs to be fixed than unknowingly
follow a bad truechimer.

Is it possible to reword that section?

Thanks,

--
Miroslav Lichvar

[Richard B. Gilbert]

I suppose it's possible to rewrite that segment of the documentation.
It might be easiest for all concerned if you submit a draft with the
changes you think necessary.

The problem with using only two servers is that NTPD has no means of
determining which is more nearly correct when the two differ, as they
inevitably will!

The documentation for NTPD attempts to explain the reasoning behind the
recommendations to use four, five, or seven servers. I think Dave's
book also addresses the subject.

[Miroslav Lichvar]

On Tue, Jan 04, 2011 at 02:35:13PM -0500, Richard B. Gilbert wrote:
> The problem with using only two servers is that NTPD has no means of
> determining which is more nearly correct when the two differ, as
> they inevitably will!

ntpd will pick the one with smaller distance if their intervals
overlap. Otherwise they both will be falsetickers.

--
Miroslav Lichvar

[Miroslav Lichvar]

On Tue, Jan 04, 2011 at 04:12:06PM -0500, Brian Utterback wrote:
> On 01/04/11 13:44, Miroslav Lichvar wrote:
> > It says and explains that minimum number of servers to detect one
> > falseticker is four, is that really correct? I understand that four is
> > better for reliability, but from the algorithm description
> > (http://www.eecis.udel.edu/~mills/ntp/html/select.html) and my tests
> > with a simulated falseticker it seems that three is enough.
> >
>

> Three are often sufficient, but not always. The key issues are which
> is the falseticker and how far apart they are and what the dispersion
> is. A falseticker by definition is one whose offset plus and minus its
> dispersion does not overlap the actual time. So, if two servers only
> overlapped a little bit, right over the actual time, they would both
> be truechimers by definition, but if a falseticker overlapped one of
> them bu a large amount, but fell short of the actual time, it could
> cause NTP to accept the one truechimer and the falseticker and reject
> the other truechimer.

You mean something like this?

|
<-----------> <---->
<--------------->
|

Wouldn't be all three marked as truechimers? If there was a fourth
server it could overlap the leftmost interval and they still would be
all marked as truechimers.

> > Also, while running with two servers might be the worst configuration
> > for ntpd, it still could be prefered over the configuration with only
> > one server by users who would rather have two sources marked as
> > falsetickers and know a problem needs to be fixed than unknowingly
> > follow a bad truechimer.
>

> The problem is that the two servers would never be marked as
> falsetickers at all, since NTP could not eliminate either one of them.
> Both would be accepted as truechimers.

That's not what I see here. Two sources can either overlap or not.
They can be both falseticker or both truechimers (and the one with
smaller distance will be the system peer).

> This can lead to clockhopping,
> where the system time is alternatingly set to each of the servers in
> turn.

I think clockhopping can happen with any number of servers, there just
needs to be two or more similar sources on top of the list sorted by
synchronization distance.

--
Miroslav Lichvar

[David Woolley]

In this case, ntpd will use an average of both of them, when the
confidence intervals overlap; it will not pick just one except for the
purposes of providing downstream error statistics.

[David L. Mills]

Miroslav,

Nowhere in the documentation produced by me is the statement that the
minimum number of servers to reliably find the truechimers is four.
There might have been some confusion in the past, in particular with
reference to Lamport's paper, which describes an algorithm much more
complicated and unsuitable for practical use. In that paper, four
Byzantine generals are necessary to detect a traitor, but only three if
digital signatures are available. The NTP algorithm, derived in part
from Keith Marzullo's dissertation, is not that algorithm.

The NTP algorithm is described on the page you cite. A constructive
proof, elaborated in my book, is simple and based on the intersection
properties of correctness intervals, which are loosely defined as the
interval equal to the roundtrip delay with the center point as the
maximum likelihood estimate of the server offset. If there are two
servers and their correctness intervals overlap, both are truechimers.
If the intervals do not overpap, no decision is possible. If there are
three servers and the intersection of two intervals is nonempty, both
are truechimers and the third is a falseticker. If no two intervals
intersect, no decision is possible.

So, it is incomplete to specify a minimum number of servers. The only
valid statement is on the page "The intersection interval is the
smallest interval containing points from the largest number of
correctness intervals." If the intersection interval contains more than
half the total number of servers; those servers are truechimers and the
others are falsetickers.

Dave

[David L. Mills]

David,

As you might see from the online documentation, much of the tutorial
material has been largely rewritten. Awhile back, some kind soul pointed
out a logical discrepancy in the select algorithm. That was repaired,
the code updated and the documentation refreshed. The pages linked from
"How NTP Works" is offered as a definitive tutorial that might clear the
air on these issues.

Dave

David Woolley wrote:

> _______________________________________________
> questions mailing list
> ques...@lists.ntp.org
> http://lists.ntp.org/listinfo/questions

[David Woolley]

The average user doesn't read such documentation.

The average user, if they believe anything at all, seems to believe that
there is no combining algorithm and the server with the * on the ntpq
peers display is the only one used to discipline the clock. This is why
they get so concerned about exactly which source has the *.

No, I haven't done a survey of users, but you can tell it by what gets
posted on this newsgroup.

Note that I was describing the combining algorithm, rather than the
selection one.

Top posted against my better judgement.

[Terje Mathisen]

David L. Mills wrote:
> Miroslav,
>
> Nowhere in the documentation produced by me is the statement that the
> minimum number of servers to reliably find the truechimers is four.
> There might have been some confusion in the past, in particular with
> reference to Lamport's paper, which describes an algorithm much more
> complicated and unsuitable for practical use. In that paper, four
> Byzantine generals are necessary to detect a traitor, but only three if
> digital signatures are available. The NTP algorithm, derived in part
> from Keith Marzullo's dissertation, is not that algorithm.

I.e. Byzantine generals not only lie, the also lie about _who_ they are,
spoofing messages from other generals. In NTP this would mean a
falsticker which also sends out packets pretending to be responses from
other servers, something which is effectively impossible unless they are
based on the same (broadcast) network and can sniff incoming requests
and/or poison the ARP tables to commandeer the other server's IP address.

Your digital signatures make such lies impossible.

> The NTP algorithm is described on the page you cite. A constructive
> proof, elaborated in my book, is simple and based on the intersection
> properties of correctness intervals, which are loosely defined as the
> interval equal to the roundtrip delay with the center point as the
> maximum likelihood estimate of the server offset. If there are two
> servers and their correctness intervals overlap, both are truechimers.
> If the intervals do not overpap, no decision is possible. If there are
> three servers and the intersection of two intervals is nonempty, both
> are truechimers and the third is a falseticker. If no two intervals
> intersect, no decision is possible.
>
> So, it is incomplete to specify a minimum number of servers. The only
> valid statement is on the page "The intersection interval is the
> smallest interval containing points from the largest number of
> correctness intervals." If the intersection interval contains more than
> half the total number of servers; those servers are truechimers and the
> others are falsetickers.

I think Miroslav showed an ascii art example for when three servers
might not be enough:

Two servers which don't overlap, and a third which overlaps (partly)
both of them:

<----> <----> server A and B
<---> server C

In this particular situation C must be a survivor, but since it overlaps
both A and B with an identical amount, there is no way to determine if
(A^C) or (B^C) is the best interval to pick.

I guess the key here is that this situation is impossible unless at
least one of the servers are lying (falseticker).

You could even extend this to four servers, where server D is identical
to server C, and it would be equally hard to determine if A or B was the
falseticker, right?

Fortunately, NTP timestamps have enough resolution to make the
likelyhood of multiple perfectly positioned confidence intervals
extremely unlikely, and if it does happen in a particular poll cycle,
then NTPD will happily coast on until the next poll. :-)

Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[Miroslav Lichvar]

On Wed, Jan 05, 2011 at 09:23:59AM +0100, Terje Mathisen wrote:
> Two servers which don't overlap, and a third which overlaps (partly)
> both of them:
>
> <----> <----> server A and B
> <---> server C
>
> In this particular situation C must be a survivor, but since it
> overlaps both A and B with an identical amount, there is no way to
> determine if (A^C) or (B^C) is the best interval to pick.

The select algorithm doesn't care how much they overlap. Recent
ntp-dev versions work as described on the select.html web page, so the
intersection interval will be equal to C and all three sources will
pass. Older versions worked also with centers of the intervals and as
the centers of A and B are lying outside the intersection interval, C
would be the only truechimer.

I'd be curious to hear why that approach was dropped.

--
Miroslav Lichvar

[David L. Mills]

Terje,

That's why Autokey uses digital signatures and zero-knowledge identity
proofs.

Dave

[David L. Mills]

MIroslav,

The select algorithm was changed in a very minor way to conform
precisely to the formal assassin quoted in my previous message. It
probably has very little practical significance. After all, the old
algorithm has been going strong for nineteen years.

Dave

[Miroslav Lichvar]

On Wed, Jan 05, 2011 at 10:31:15AM -0500, Brian Utterback wrote:
> Let's equalize a bit to make it a bit more fair:
>
> <c------------> <b------------->
> <a-------------->
>
> So, now, if you were NTP, which would you choose? You are correct in
> your assessment that NTP would accept them all as truechimers. You are
> correct also that adding a fourth still does not guarantee that you
> will throw out the falseticker, but NTP uses intervals at this stage,
> not actual servers, so adding another truechimer will guarantee that
> the interval used will contain the real time.

Not necessarily.

|
<---------> A
| <-----> B
<--------> C
<-------> D
|
<==> X

Here, B is the only server off, but the result X doesn't contain the
actual time.

> > I think clockhopping can happen with any number of servers, there just
> > needs to be two or more similar sources on top of the list sorted by
> > synchronization distance.
> >
>

> With more servers on the list, the clustering and combining algorithms
> will merge them into a single offset and they will not hop. With two
> servers, these algorithms cannot function.

Combining doesn't affect clockhopping, it happens after the system
peer is selected.

> By the way, over time Dr. Mills has added features to try to suppress
> clock hopping as much as possible without compromising the correctness
> proofs. With the latest versions, clock hopping may not be so much of
> a problem. Bu tit is still an issue. Even if you prefer one clock, it
> might be inaccessible for a while and you will hop anyway.

Yes, the maximum anti-clockhopping threshold is a fixed value (1 ms by
default), so it can't work well in all situations. But it can be tuned
with the tos mindist command.

--
Miroslav Lichvar

[David L. Mills]

Terfe,

Read the formal assertion carefully and examine the algorithm on the
Select Algorithm page. The algorithm would return interval C as the
smallest intersection with the largess number of contributors.

Dave

[David L. Mills]

Miroslav,

According to your diagram, the algorithm would determine the
intersection interval as interval a. The midpoints of all three
intervals would be considered truechimers, since each of the intervals
a, b and c, contain points in the intersection interval.

Dave