[ntp:questions] Number of servers needed to detect one falseticker?

David L. Mills mills at udel.edu
Wed Jan 5 15:04:47 UTC 2011


Terje,

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

Dave

Terje Mathisen wrote:

> 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





More information about the questions mailing list