Re: [Ntp] NTPv5 Loop Detection without Stratum

[Paul Gear <[e-mail]>]

On 23/8/22 20:32, Miroslav Lichvar wrote:
> On Tue, Aug 23, 2022 at 12:21:19PM +0200, Heiko Gerstung wrote:
>> One way of avoiding/detecting loops:
>> - upon startup, an NTPv5 instance creates a random 64bit ID
>> - we add a loop detection EF that can include n IDs (or we use n EFs)
>> - a stratum one server, when ask for his "sync trace", responds with only his ID
>> - a stratum two server would add its own ID to the ID of its upstream server, responding with a sync trace of two IDs
>> - a stratum 1+n server would respond with the sync trace of its upstream source(s) plus its own ID
>> - if you use more than one upstream source, you can respond with a list of all IDs from the sync trace of all your upstream sources (removing duplicates)
>> - by checking if your own ID is in the sync trace of your upstream source(s), you can find out if there is a loop
> That was the original idea before Daniel Franke suggested to use a
> bloom filter instead of a simple list. This makes the amount of
> exchanged data constant and it can contain a very large number of
> reference IDs before collisions can be expected.


I'm far from an expert on bloom filters, but they can have false 
positives, which would result in a source which was not part of a 
client's upstreams being erroneously flagged as being so.  Would this 
not require a trace (like what Heiko has described above) to detect?

In some cases, false positives would be inconsequential (e.g. when the 
client is using a well-served zone in the public pool and can easily ask 
for another source), but in private networks where the number of sources 
may be more limited discarding an upstream source may be more problematic.

Are these concerns warranted?  Some (all?) bloom filter implementations 
allow one to tune the desired false positive level; could we set that 
level low enough that it wouldn't be significant?

The fixed size of a bloom filter makes it simple to avoid traffic 
amplification, but with a trace this would be trickier, because if it 
required more than one UDP packet to transfer it would require holding 
state on the server, opening the server to resource exhaustion attacks also.

Regards,
Paul