Terrorist-fraud resistant distance-bounding protocol with malicious verifier

[dbosk]

We must solve the terrorist-fraud resistance for the distance-bounding protocol. The problem is this: the protesters have no incentive to follow the protocol of performing the distance-bounding protocol, they have incentives to be dishonest. Thus they cannot be assumed honest verifiers. The only possible honest party is the trusted journalist Jane.

Terrorist-fraud resistance is based on the assumption that Alice will not forward the data to Bob if Bob could later impersonate Alice arbitrarily. We need that Bob must be able to impersonate Alice as a participant of e.g. a counter-protest. If it's only bound to the protest that Alice supports, she will not mind. And this will eventually lead to the protesters boosting their participation count.

[dbosk]

Trusted journalist Jane will witness, this is the only way for Alice and Bob to get valid proofs. Thus they must perform the protocol with her. Bob will try to get a witness signature for Alice (too).

Bob performs the protocol with Eve as a witness. If the witness get the ability to impersonate, Eve will include Alice and Bob in her own counter-protest too.

We sort of need an asymmetric computation in the distance-bounding protocol. Alice must provide Bob with something that allows Bob to impersonate Alice forever, specifically in any counter-protests. However, the witness (Eve) should not be able to impersonate the prover later.

[dbosk]

There is a paper Multi-Hop Distance Estimation: How Far are You?, maybe it will be useful for Jane.

[dbosk]

We need three simultaneous properties:

• privacy
• terrorist-fraud resistance
• malicious-verifier secure

[dbosk]

The Multi-Hop Distance-Bounding paper assumes an honest verifier.

[dbosk]

Conjecture: A distance-bounding protocol cannot be malicious-verifier secure and terrorist-fraud resistant at the same time.

Definition: A distance-bounding protocol is malicious-verifier secure if a verifier cannot impersonate a prover after any honest interaction by the prover. (I.e. the prover naïvely follows the protocol.)

The idea: The prover P wants to prove that P' is close to V (i.e. P and P' commits terrorist-fraud). V initializes the challenge with P who forwards it to P'. P' gives all the correct responses to P for use during the distance-bounding phase. Since V cannot impersonate P' after the interaction, then neither can P --- which violates the terrorist-fraud resistance assumption.

The only way I can see to fix this is to make each challenge in the quick phase directly depend on the private key of P', in which case the terrorist-fraud resistance assumption is not violated. However, that would move a heavy computation from the initialisation phase to the distance-bounding phase, can that be made to work? (There's a reason there is an initialization phase.)

[dbosk]

Boureanu, Vaudenay: "Challenges in Distance Bounding", IEEE S&P Magazine 2015.

A good introduction to distance-bounding protocols. Introduces the three main properties: distance fraud (DF), mafia fraud (Man-In-the-Middle, MIM), terrorist fraud (TF). Mentions distance hijacking, where a malicious prover uses an honest prover against an honest verifier and hijacks the distance-bounding phase (the quick phase).

It highlights problems of actually implementing these protocols. I got the impression that there are no functioning implementations of these protocols in mid-2015. The analog-digital converters add too much latency, so it must sort of be done in hardware. Is this true, can distance bounding be done using a smartphone nowadays?

It focuses entirely on honest verifiers.

[dbosk]

Agnès Brelurut, David Gerault, Pascal Lafourcade: Survey of Distance Bounding Protocols and Threats.

Only honest verifiers. Describes the traditional properties:

• Distance fraud (DF)
• Mafia fraud (MF) or man-in-the-middle (MIM) or relay attacks
• Terrorist fraud (TF)
• Impersonation fraud (IF): an adversary tries to impersonate the prover to the verifier, e.g. to blame someone else.
• Distance hijacking (DH)

They also mention the three formal definitions of BMV:

• Distance fraud (DF): which includes both classical distance fraud and distance hijacking.
• Man-in-the-middle (MiM): includes both mafia fraud and impersonation fraud.
• Collusion fraud (CF): this extends the notion of terrorist fraud.

They show that:

• CF => TF => DF => DH
• MiM => MF and MiM => IF

And analyses 42 protocols from 1993 to 2015 and presents success probabilities for attacks on each.

[dbosk]

My to-read list:

• (Sound) Proof of proximity of knowledge
• Practical and provably secure distance bounding
• Subtle kinks in distance bounding: an analysis of prominent protocols
• Terrorism in distance bounding: modelling terrorist-fraud resistance

[dbosk]

• Ahmad Ahmadi and Reihaneh Safavi-Naini: Distance-bounding Identification
• Ahmad Ahmadi, Reihaneh Safavi-Naini: Privacy-Preserving Distance-Bounding Proof-of-Knowledge

[dbosk]

Brands, Chaum: Distance-bounding protocols

They confirm my idea of turning the Schnorr protocol into a distance-bounding protocol. They focus on mafia fraud (MF) and distance fraud (DF), I must look into how it is with impersonation fraud (IF) and distance hijacking (DH). I.e. to see if they provide DF and MIM in the BMV-sense. A DB protocol based on Schnorr should inherit malicious-verifier (impersonation) resistance.

Since Schnorr is the foundation of all zero-knowledge proofs of knowledge (ZKPoK) protocols, we can do a distance-bounding ZKPoK (DBZKPoK). I must look into whether anyone has done this before.

[dbosk]

Maybe GDB: Group Distance Bounding Protocols can be useful, we have to look into it though.

[dbosk]

Privacy-Preserving Distance-Bounding Proof-of-Knowledge seems to do what we want. I have to read it though.

[dbosk]

Authentication goal:

• Prove knowledge of $k_p$.
• Malicious verifier (bilateral authentication)
• Terrorist fraud if possible.

Proximity goal:

• Prove $k_p$ is close.
• Prevent relay attacks (Mafia fraud).
• Prevent distance fraud.

Revocation?

[sgambs]

To add to the related work and compare with our solution UrbanCount: Mobile Crowd Counting in Urban Environments

[dbosk]

Nice! Maybe Sonja can ask Gunnar for a copy of the paper.

On Wed 07 Feb 2018 00:18:31 GMT, sgambs wrote:

To add to the related work and compare with our solution UrbanCount: Mobile Crowd Counting in Urban Environments

[dbosk]

I still don't think that we can have both terrorist-fraud resistance and impersonating-verifier resistance, I think they are mutually exclusive.

72 adds a protocol which provides privacy, impersonating-verifier resistance and the usual distance-fraud resistance, Mafia-fraud resistance and distance hijacking resistance.

[dbosk]

Our DB Schnorr construction is probably terrorist-fraud resistant.

We must commit to one random value $r$ by sending $g^r$ to the witness. The witness will reply by two challenges, $c_0, c_1$. The dishonest prover will compute $s_0 = r + c_0 x$ and $s_1 = r + c_1 x$ and give to the "terrorist prover".

Thus the secret $x$ can be inferred from $s_0, s_1$ together, but not from only $s_b$ ($b\in {0, 1}). Thus, the witness cannot infer $k$ since she never learns both $s_0, s_1$, but the terrorist can. This is exactly the situation created when proving it's a proof of knowledge: the extractor rewinds the prover and gives him a second challenge, then the secret can be extracted from the two responses.

[dbosk]

Maybe we can use the Distance-Bounding Protocols: Verification without Time and Location paper (i.e. Tamarin) to verify the protocol.

[dbosk]

This is now done.