zone anchor collusion attack allows beacon to falsely claim a PoL

[brenzi]

After studying your latest version (Draft 0.4) of the technical whitepaper I can't see how you mitigate the following attack:

zone anchors and one beacon collude to produce a false proof-of-location

assumptions

• all colluding zone anchors are following the protocol for time sync
• the set of colluding zone anchors are densely distributed around location A with no fair zone anchors within plausible range of A
• the fraudulent beacon is in location B (which is not within the range of the zone anchors) but pretends to be in location A

attack scenario 1) the beacon sends a presence claim to its colluding zone anchors. As the protocol demands, this includes percieved location A, a payment and a nonce 2) the colluding zone anchors each calculate their virtual TDOA according to virtual location A and write the signed claim to the zone log. 3) the validators have no reason to distrust the zone log and will validate the proof-of-location

the fraudulent beacon now successfully gets a proof-of-location for location A although being located at B.

How can you mitigate this attack?

[brenzi]

in a telegram discussion, @ryan-foamspace insisted that in my diagram, location 'A' would only be covered by one zone (made up by the minimum four ZA's). Therefore his countermeasure would be to distrust the claim because the zone was isolated (confirmed by only one zone). However I'm still convinced that this attack also works if location A is covered by many zones - as long as they collude.

Here's another scenario where the attack works just the same, but with many more ZA's colluding. It doesn't matter how the zones are made up between the available zone anchors. Here location 'A' is covered by several zones. I've sketched two possible zones covering 'A'. No matter who is staking with whom to make up a zone, it just takes collusion of all the red ZA's for this attack to work and not being noticed by anyone

red are the colluding ZA, green are the fair ZA (extending to infinity in all directions). the dashed red line is the tranceiver range for the beacon (equal to the range of any ZA in ths scenario)

[AFDudley]

Your description in 2 is insufficient to generate a valid presence claim. Presence claims require:

1. A timestamped message from one ZA
2. A timestamped signed message from a mobile beacon.
3. A ZA of the same zone signing and timestamping the message from 2.

If we fix your "attack" above and the MB is not in the zone, that means iby definiton messages are being relayed, the relay can't run faster than the speed of light, so the attack will be obvious by checking the timestamps.

[brenzi]

@AFDudley The Whitepaper PoL is based on single-signal TDOA. This means the beacon sends out a timestamped message and the ZA's will timestamp received packets. The two timestamps are written to the zone log. An external observer can now (re-)calculate the TDOA for each ZA. BUT: it has to rely on time synchronized ZA. What I'm stating in the attack is what I called 'virtual TDOA'. This means that the colluding ZA's are perfectly time-synchronized but they write fake timestamps to the received packet. If you know location A it's trivial to generate fake timestamps that look like the colluding beacon would be at location A to any outsiders like the validators. Speed of light is only a variable in that formula, no constraint on the feasibility of the attack.

[AFDudley]

I worked on the white paper and we discussed this attack for many hours. I haven't read which draft is published, so these answers may not be in the published draft.

The red circles on your first diagram are wrong then, that zone would be faulted.

Your second diagram is an example of an isolated zone, there are several problems with this.

(Sorry, this is going to come out kinda funny and I'll edit my answer based on any confusion you have.)

Valdiators will see this zone is logically discontiguous from the other zones. So, the ZAs won't get any rewards from running their zone, rewards can only be spent on the network between contiguous zones. (Hopefully, once I explain this you'll see an actual attack and we can discuss the mitigations.) There are three ways that zones can be contiguous:

1. The zone can share ZAs with other contiguous zones, this means the same ZA is bonded to multiple zones.

2. A set of contiguous ZAs can opt to sign the correctly timestamped messages from discontiguous ZAs.

3. Mobile beacons can claim rewards by "walking back" claims from discontiguous ZAs. (These claims could also be "beamed" back, at some point this will explained further.)

If we only have 1 and 2 a Zone can't claim to be at a location in range of an existing ZA and lie about it's position, it's difficult to overstate how important this is. 3 allows for zones that are disconnected to be weakly connected together by mobile beacons. Exactly how walk backs work is TBD, but we can imagine the MB rewards are escrowed and only unlocked after some number of confirmations from other MBs or slowly released if the formerly discontiguous zone becomes and remains contiguous over time.

Also worth mentioning here, there are a number of simple and accurate ways we can weigh the histories of MBs and determine if we should believe they are real devices. We can also challenge MBs to prove themselves, etc etc. (In correctly configured Zones, we should expect there to be an internet connection and a validator within a reasonable distance, the union of these expectations can be incentivized, I'm sure that's not in the current paper.)

It's also important remember individuals can travel to where Zones claim to be and verify them directly.

[AFDudley]

There is a broader issue with your the treatment of time and signal generation in your second diagram, which I believe also represents a physical impossibility very similar to your first.

The MB in your example is a phantom, which is fine, we should expect phantom MBs, millions of them in fact, mitigating this is surely not in the paper so it's fair for you to assume them.

But in your second diagram, why would anyone believe the Bad Zone is valid? It isn't sharing a clock with what should be contiguous zones, which means the zone is faulted.

[brenzi]

I can only know, what is public and that's draft V0.4 of the whitepaper. Yet even the additional information you're stating doesn't mitigate this attack. But I think there are misunderstandings:

The red circles on your first diagram are wrong then, that zone would be faulted.

In the first diagram, the circles represent transciever ranges of individual ZA's. What's wrong about them? I see that in my first diagram there's not enough density of ZA's to reach contiguous zones. I get this. But that doesn't disqualify my argument, as the second diagram is supposed to show.

Your second diagram is an example of an isolated zone, there are several problems with this.

I've just sketched three zones there, two of which are overlapping. As there is a high density of ZA's I thought it was clear that means that in this diagram there are only contiguous zones. Or do you assume them being side by side? Let my try a third diagram: Here I assume that each zone is made up of four ZA's but as the circle indicates, the range of transcievers is much larger, so more ZA's could participate in all of these zones what would make the zones overlap (but that's not easily visualized in a sketch...). Now please explain to me what would be suspicious about this setup.

But in your second diagram, why would anyone believe the Bad Zone is valid? It isn't sharing a clock > with what should be contiguous zones, which means the zone is faulted.

Why would anyone suspect? Of course all ZA's are sharing a clock, your're neglecting my assumptions. All ZA's behave excactly along the protocol - with one exception: In the case of the attack claim the red ones don't write their true receive timestamp to the data packet sent out by the fraudulent beacon. Of course, that beacon doesn't even send ANYTHING out over LoRa. It sends the claim privately to all colluding ZA's who behave as if that packet was received on the LoRa physical Layer and add their (fake) timestamp according to the beacons timestamp plus the TOF from the fake location A to themselves.

Do we have a common understanding of the attack now?

[AFDudley]

In the case of the attack claim the red ones don't write their true receive timestamp to the data packet sent out by the fraudulent beacon.

This doesn't work. Either they never broadcast the message, so the other ZAs that should see skewed messages won't OR the malicious ZAs will desync their clocks from the honest ones, which will be trivial to detect.

(Since you don't actually reply to all my comments at once, I will only reply to one of your comments at a time.)

[brenzi]

Not sure if I get you right. But at least I think now we're talking about the interesting bit.

Either they never broadcast the message, so the other ZAs that should see skewed messages won't OR the malicious ZAs will desync their clocks from the honest ones, which will be trivial to detect.

Of course the ZA's sign the presence claims from the beacon and broadcast them to the zone log. What keeps them from faking a timestamp by a few ms? The zone log is a blockchain - no hard timestamping features there so how do you intend to detect the timestamp is fake?

One doesn't need to desync system clocks to fake a timestamp.

[brenzi]

Have you thought about performing all the BFT time sync, timestamping and signing stuff within a trusted execution environment (TEE) on the ZA? If there is a practical way to do that together with secure boot and deterministic builds, I'd be with you

[AFDudley]

Wherever the paper describes this, it needs to be more clear, because I finally understand what you mean and it's very different from what I meant.

There are a lot of different points to clear up, but the gist of it is you're right, what you've specified should not be a valid presence claim. It's probably not clear from the document why it isn't.

I will come back to this later and do a proper write-up.

Another answer is, the MB must sync its clock in the zone and a third party would only trust a set of multiple zone-MB sync messages as evidence a MB was at a place.

EDIT: section 5.2 of draft 0.4 does NOT describe a BFT method for an r to prove their location to a third party.

Section 11 of draft 0.4 is not clear about some key points:

1. The specification of the zone log is incomplete.

2. Presence claims are composable.

3. A single message of the form: ZA_signed(timestamp, MB_signed(timestamp, ZA_signed(timestamp-nonce))) Results in a single valid presence claim, but is insufficient to provide proof of anything to a third party that should not have received the initial ZA_signed(timestamp-nonce)

4. There is little effort put in to the existing document to explain how evidence gains support as it moves from local to global consensus.

[AFDudley]

A TEE won't be required, I'm more worried about getting signing fast enough.

[brenzi]

Thanks @AFDudley for these comments. Looking forward to getting more details in the next whitepaper draft.