PaperlayerView exact revision on arXiv

Source-linked AI summary

Detecting Sybil Attacks using Proofs of Work and Location in VANETs

Mohamed Baza, Mahmoud Nabil, Niclas Bewermeier, Kemal Fidan, Mohamed Mahmoud, Mohamed Abdallah

arXiv:1904.05845v1cs.CR

TL;DR

Sybil attacks exploit anonymous pseudonyms to create fake vehicle identities, posing risks to traffic and safety applications. This paper combines location trajectories from multiple RSUs with proof of work and graph-based detection; it reports high detection with low false negatives and acceptable overhead.

  • Problem

    Anonymous pseudonyms can be abused to create fake vehicle identities, including false congestion reports and biased safety-application results.

    Source: §I · p. 1

  • Method

    The scheme chains time-stamped RSU location tags into anonymous trajectories, uses threshold signatures and proof of work to limit forged trajectories, and applies graph-based matching to reported events.

    Source: §I · p. 2, E. Detecting Sybil Attacks · p. 6

  • Results

    The authors report high Sybil detection with low false negative rate and acceptable communication and computation overhead, and greater efficiency than Footprint.

    Source: §I · p. 2, §IX · p. 14

  • Takeaways & Limitations

    Proof of work limits—but does not eliminate—the chance that malicious vehicles obtain multiple trajectories, so graph-based heuristics provide a second defense layer.

    Source: E. Detecting Sybil Attacks · p. 6

Abstract

from arXiv · show

In this paper, we propose a Sybil attack detection scheme using proofs of work and location. The idea is that each road side unit (RSU) issues a signed time-stamped tag as a proof for the vehicle's anonymous location. Proofs sent from multiple consecutive RSUs is used to create vehicle trajectory which is used as vehicle anonymous identity. Also, one RSU is not able to issue trajectories for vehicles, rather the contributions of several RSUs are needed. By this way, attackers need to compromise an infeasible number of RSUs to create fake trajectories. Moreover, upon receiving the proof of location from an RSU, the vehicle should solve a computational puzzle by running proof of work (PoW) algorithm. So, it should provide a valid solution (proof of work) to the next RSU before it can obtain a proof of location. Using the PoW can prevent the vehicles from creating multiple trajectories in case of low-dense RSUs. Then, during any reported event, e.g., road congestion, the event manager uses a matching technique to identify the trajectories sent from Sybil vehicles. The scheme depends on the fact that the Sybil trajectories are bounded physically to one vehicle; therefore, their trajectories should overlap. Extensive experiments and simulations demonstrate that our scheme achieves high detection rate to Sybil attacks with low false negative and acceptable communication and computation overhead.

I. INTRODUCTION

Sybil attacks exploit anonymous pseudonyms to create fake vehicle identities, threatening traffic and safety applications; prior identity, position, and trajectory approaches have limitations. The proposed scheme combines RSU-issued location proofs, threshold signatures, and proof of work, and the paper reports better efficiency than Footprint.

I. INTRODUCTION

  • Existing identity-registration approaches can be undermined by stolen or colluded identities, GPS-based position checks can fail in mobile VANETs, and trajectory schemes face RSU-compromise and sparse-deployment risks.The cited Footprint approach can allow unlimited valid trajectories after one RSU is compromised, while sparse rural RSUs can enable trajectories that appear to belong to different vehicles.Source: §I · pp. 1–2
  • Chronologically chained time-stamped tags from consecutive RSUs form an anonymous vehicle trajectory, while threshold signatures require contributions from multiple RSUs.The event manager uses heuristics to build a connected graph of suspected Sybil nodes and applies a maximum-clique algorithm to detect them.Source: §I · p. 2
  • Threshold signatures make fake trajectories require compromising an infeasible number of RSUs.The scheme distributes signature generation so no single RSU can create a complete trajectory proof.Source: §I · p. 2
  • Proof of work limits malicious vehicles’ ability to create multiple forged trajectories and is intended to reduce Sybil detection time.The authors analyze PoW probabilistically and develop a model for adjusting parameters, including travel time between consecutive RSUs.Source: §I · p. 2
  • The proposed scheme detects and defends against VANET Sybil attacks more efficiently than Footprint.The paper also reports experimental analysis of proof-of-work parameters and further simulations and practical experiments.Source: §I · p. 2

A. Network Model

  • The network model includes roadside units, vehicles with onboard units and GPS receivers, a trusted authority, and an event manager.RSUs communicate with nearby vehicles and with each other; the event manager detects Sybil trajectories after receiving reported events.Source: A. Network Model · p. 2

B. Adversary and Threat Model

The threat model treats vehicles as untrusted and allows RSU compromise and pseudonym-sharing collusion, while preserving driver anonymity is a design goal. The preliminaries introduce secret sharing as the basis for threshold access.

B. Adversary and Threat Model

  • Vehicles may launch Sybil attacks and collude by sharing pseudonyms, while compromised RSUs and an honest-but-curious event manager are also in scope.The trusted authority is fully trusted; the event manager should not learn drivers’ actual identities.Source: B. Adversary and Threat Model · p. 2

C. Design Goals

  • The design goals are RSU-compromise resistance, short detection time, location privacy, and unlinkability across messages and locations.The paper motivates unlinkability by the risk that visited locations or linked messages could expose driver identity or location information.Source: C. Design Goals · p. 3

III. PRELIMINARIES

  • The preliminaries provide background on secret sharing and threshold signatures used by the scheme.The notation is listed in Table I.Source: §III · p. 3, Table I · p. 3

A. Secret Sharing

  • In a (t, n)-threshold secret-sharing scheme, at least t participants can recover the shared secret, while fewer than t cannot.Shares are assigned to participants, and a qualifying set can reconstruct the secret using Lagrange interpolation.Source: A. Secret Sharing · p. 3

B. Threshold signatures

Threshold signatures distribute signing power among participants rather than assigning it to one signer. The paper adopts a scheme whose shares can be combined into a publicly verifiable signature.

B. Threshold signatures

  • A (t, n)-threshold signature lets at least t participants combine partial signatures into a valid signature verifiable with a unique public key.Each participant signs using a secret-key share, rather than holding the sole signing key.Source: B. Threshold signatures · p. 3
  • The adopted threshold-signature scheme is based on Gap Diffie-Hellman groups and is described as anonymous, secure, and low overhead.Its signing uses hash computations and modular exponentiation, verification uses two pairing operations, and reconstruction multiplies signature shares.Source: B. Threshold signatures · pp. 3–4
  • Each participant computes a signature share on message m, and at least t participants’ shares are combined into a standard signature.The scheme description identifies G as a Gap Diffie-Hellman group and H as a public one-way, collision-resistant hash function.Source: B. Threshold signatures · p. 4

IV. PROPOSED SCHEME

Vehicles build anonymous trajectories from consecutive, time-stamped location proofs issued by RSUs. Threshold signatures and a travel-time-calibrated proof-of-work puzzle constrain trajectory creation.

A. Overview

  • Each vehicle combines consecutive, time-stamped RSU location tags into a trajectory used as its anonymous identity.The tags are chained chronologically as the vehicle moves between RSUs.Source: A. Overview · p. 4

B. System Initialization

  • The TA provisions RSUs in a group with shares for a (t, n) threshold signature and gives vehicles certified temporary public keys for anonymous authentication.Here, n is the number of RSUs in the group.Source: B. System Initialization · p. 4

C. Exchanged Messages

  • After receiving an RSU proof, a vehicle solves a seeded PoW puzzle and submits its solution with a new temporary key to the next RSU.The next RSU verifies vehicle ownership and the puzzle before contributing a signature share.Source: C. Exchanged Messages · pp. 4–5
  • The puzzle requires finding a nonce that makes the hash fall below a target, with lower targets requiring more solving time.The target is adjusted according to expected travel time between RSUs.Source: C. Exchanged Messages · p. 5
  • With t = 3, R3 combines signature shares into a standard signature that proves the vehicle appeared at R1.The resulting message also includes location information for the RSUs encountered so far.Source: C. Exchanged Messages · pp. 4, 6

D. Creating Trajectories and Reporting Events

The scheme uses chained RSU proofs as anonymous vehicle trajectories and submits them with reported events. The event manager applies physical-travel heuristics and graph-based grouping to identify trajectories from Sybil nodes.

D. Creating Trajectories and Reporting Events

E. Detecting Sybil Attacks

  • PoW limits, but does not eliminate, multiple trajectories, so trajectory heuristics and graph-based analysis provide a second defense layer.The two heuristics bound travel time between consecutive RSUs and the number of RSUs traversed within a period.Source: E. Detecting Sybil Attacks · p. 6
  • The exclusion test flags trajectory pairs as suspicious unless they show distinct RSUs within a check window or exceed the trajectory-length limit when combined.The test uses RSU overlap and the check-window and trajectory-length constraints.Source: E. Detecting Sybil Attacks · p. 6
  • The manager builds a graph whose edges mark negative exclusion tests, then repeatedly removes maximum cliques so a malicious vehicle is represented once.The paper uses the MCS maximum-clique algorithm for this step.Source: E. Detecting Sybil Attacks · p. 6

V. SELECTION OF POW TARGETS

The section experimentally derives PoW target values for different vehicle traverse times and uses them to construct a lookup table for RSU verification. Longer traverse times correspond to lower expected target values.

A. Experimental Results

  • The experiment ran PoW 1,000 times at each of four traverse times: 10, 30, 90, and 130 seconds.Raspberry Pi 3 devices simulated vehicles; the resulting target values were grouped into ranges to estimate their probabilities.Source: A. Experimental Results · p. 7
  • The authors used target-value probability mass functions to derive cumulative distributions for the different traverse times.The CDF gives the probability that a computed target T is less than a threshold t.Source: A. Experimental Results · p. 7, Figure 6 · p. 7, Figure 5 · p. 7
  • At 130 seconds, the probability of computing a target below T = 2239 is 0.98.The lookup-table estimates also show lower expected target values as traverse time increases.Source: A. Experimental Results · pp. 7–8
  • The expected target values at different traverse times and target success rates form a lookup table loaded onto each RSU for PoW verification.A 95% target success rate means 95% of vehicles can compute the specified target.Source: Figure 7 · p. 7, A. Experimental Results · p. 8

B. Mathematical Model

The authors model the probability of solving PoW puzzles during travel between RSUs, then compare the model with experimental results. They use the model to generate target lookup-table values from hash rate and traverse time.

B. Mathematical Model

  • The model maps vehicle hash attempts during a traverse to draws from a finite hash space, with successful hashes representing PoW solutions below the target.The hypergeometric model gives the probability of k successes in n draws from a pool of size N containing K successful outcomes.Source: B. Mathematical Model · p. 8
  • For a 90-second traverse, the model uses n = 3.5 × 10^6 hashes and target values of 16.73×10^70 and 6.34×10^70 for 99% and 85% target success rates, respectively.The hash-space size is N = 2^256, the SHA-256 output space.Source: B. Mathematical Model · p. 8
  • The experimental results match the approximated hypergeometric distribution, which can also generate the target lookup table from hash rate and traverse time.The model uses a Poisson approximation because direct computation of the hypergeometric PMF is difficult for the large values involved.Source: B. Mathematical Model · p. 8

C. Importance of using PoW

The section evaluates how PoW affects the probabilities that honest vehicles create one trajectory and malicious vehicles create multiple trajectories. Lower target values and longer trajectories reduce the malicious success probability, while overly low targets can also hinder honest vehicles.

C. Importance of using PoW

  • The authors define one-trajectory success for an honest vehicle and multiple-trajectory success for a malicious vehicle using the probability model in Eq. 6.The former uses i = 1; the latter uses i > 1, representing multiple PoW solutions required at each RSU.Source: C. Importance of using PoW · p. 9
  • The probability of creating multiple trajectories decreases significantly as trajectory length increases, reducing the success of Sybil attacks by making multiple trajectories difficult to create.The evaluated cases include two, three, and four trajectories, with lengths up to 10 RSUs.Source: C. Importance of using PoW · p. 9
  • Lowering the target value reduces the probability of creating multiple trajectories, but setting it too low can prevent honest vehicles from creating a valid trajectory with high probability.The target should balance honest trajectory completion against the chance of malicious vehicles creating many trajectories.Source: C. Importance of using PoW · p. 9

VI. SECURITY AND EVALUATION ANALYSIS

The evaluation simulates honest and malicious vehicle trajectories on a Nashville road map, then compares Sybil-detection performance with Footprint using repeated runs and three classification metrics.

A. Sybil Attack Detection

1) Simulation Design:

  • About 160 simulated vehicles follow random routes on a Nashville map, with 10% designated malicious and each malicious vehicle assigned 1–10 forged trajectories.Routes use 10–15-RSU subtrajectories, random start times within five seconds, and 10–130 seconds of travel between RSUs.Source: 1) Simulation Design · p. 9

2) Considered key metrics:

  • The evaluation measures false-positive rate, false-negative rate, and detection rate, with detection rate defined as the fraction of Sybil trajectories correctly identified.The metrics are used to compare the proposed scheme with Footprint, averaging 30 simulation runs for each configuration.Source: 2) Considered key metrics · p. 10

3) Impact of the check window size:

The simulations examine how check-window size and trajectory-length limits affect detection compared with Footprint; the proposed scheme improves detection outcomes under the reported settings.

3) Impact of the check window size:

  • The false-negative rate fell and detection rate rose by up to 50% relative to Footprint as check-window size varied, while false-positive rates remained the same.The check window ranged from 2 to 50 seconds with a 15-RSU trajectory limit; increasing the window lowered FPR but raised FNR in both schemes.Source: 3) Impact of the check window size · p. 10

4) Impact of the trajectory length limit:

  • The proposed scheme outperformed Footprint as the trajectory-length limit varied from 2 to 24 RSUs with a 17-second check window.Figure 12 compares FPR, FNR, and DR across trajectory-length limits; the supplied prose gives no specific magnitude for this comparison.Source: 4) Impact of the trajectory length limit · p. 10, Figure 12 · p. 11
  • The reported detection-time comparison says the proposed scheme reduced FPR by around 15% and increased DR by up to 40% relative to Footprint.The figure text attributes the detection improvements to PoW making it harder to compute forged trajectories simultaneously.Source: Figure 13 · p. 11

5) Detection time overhead of eliminating Sybil nodes:

PoW limits forged trajectories and reduces the event manager’s clique-search burden; the security analysis also describes protections against RSU compromise, replay, and location inference.

5) Detection time overhead of eliminating Sybil nodes:

  • When malicious vehicles could generate 28 forged trajectories, Footprint required about 26 seconds for detection, while the proposed scheme detected them in milliseconds.The authors connect the reduced clique-algorithm workload to PoW limiting the number of successful forged trajectories.Source: 5) Detection time overhead of… · p. 11

B. Security/Privacy Analysis

  • Threshold signatures require contributions from at least t RSUs, so one compromised RSU cannot issue a proof of location by itself.The authors state this mitigates RSU-compromise attacks.Source: B. Security/Privacy Analysis · pp. 11–12
  • Message verification and temporary private keys are described as defenses against replay, while PoW limits forged trajectories and associated denial-of-service attacks.The analysis also says anonymous threshold signatures and changing temporary location tags protect location privacy; PoW avoids requiring a specific RSU configuration for overlapping coverage.Source: B. Security/Privacy Analysis · p. 12

VII. COMPUTATION AND COMMUNICATION OVERHEAD

  • The overhead implementation used Python Charm and Raspberry Pi 3 devices with a 1.2 GHz processor and 1 GB RAM.The evaluation used a 160-bit MNT159 curve for bilinear pairing to estimate the BLS signature operations.Source: §VII · p. 12

1) Computation overhead:

The paper reports computation and communication costs for issuing location proofs, reviews prior Sybil-detection approaches, and concludes that its scheme detects attacks with acceptable overhead.

1) Computation overhead:

  • An RSU’s proof-of-location issuance cost is 6.66·t ms, comprising 0.39·t ms for signing and 6.27·t ms for verification, versus about 9.01 ms for Footprint.Source: 1) Computation overhead · p. 12

2) Communication overhead:

  • Message size is approximated as 24·l + 20·t bytes in the proposed scheme and 24·l + 372 bytes in Footprint, so both grow as a trajectory encounters more RSUs.The paper suggests choosing short-period events to limit message size and retain temporary linkability of location tags.Source: 2) Communication overhead · p. 12

VIII. RELATED WORK

  • Related work spans identity-registration, physical-position-verification, and trajectory-based methods, with cited approaches facing privacy, deployment, or robustness constraints.The discussion specifically notes Footprint’s vulnerability to RSU compromise, multiple trajectories, and overlapping RSU coverage.Source: §VIII · pp. 12–13

IX. CONCLUSION

  • The conclusion describes anonymous trajectories as consecutive proofs of location from multiple RSUs, with threshold signatures and PoW addressing RSU compromise and forged trajectories.The authors report high detection rates, low false-negative rates, and acceptable communication and computation overhead.Source: §IX · pp. 13–14
Loading 1904.05845v1…