[Security Research] Stalking via Number Theory: Breaking WeChat's Location Privacy

TL;DR

Researchers have uncovered a critical privacy flaw in Location-Based Social Networks (LBSNs) like WeChat. Despite these apps "blurring" your location into 100m distance bands, a new attack leveraging number theory can pinpoint a user's exact location within 60 meters—effectively "visual distance." The study introduces a Two-Dimensional (2-D) Algorithm that overcomes existing obfuscation and proposes k-anonymity as a robust defense.

Background: The Illusion of Distance Obfuscation

When you use "People Nearby" on WeChat, the app doesn't say "Bob is at [lat, long]." Instead, it says "Bob is 800m away." This is a security feature called Location Obfuscation. By rounding the actual distance $d$ into a band $W_d$, the service aims to prevent trilateration (the math used by GPS to find you).

The research team, however, asked a dangerous question: Can we reverse this rounding if we have enough data points?

The Pain Point: The "Edge" Case Problem

Previous attempts at this attack (FundALG) often failed when users were near specific rounding thresholds. If a user moves from 99m to 101m, the reported distance jumps from 100m to 200m. This creates "abnormal errors" where the predicted location could be hundreds of meters off. The authors' primary insight was that these errors aren't random—they are a function of the mathematical rounding logic.

Methodology: The 2-D Heuristic Approach

The attack uses an Android emulator (BlueStacks) to place "virtual probes" (fake GPS accounts) in a grid around a target city.

1. The Core Math

The algorithm uses the Extended Euclidean Algorithm to find coefficients that satisfy the distance equations. By placing probes at intervals $x$, they create a system of linear congruences that reveals the true distance $D$.

2. Solving the 2D Plane

The authors improved the basic attack by partitioning the target area. If a target is detected in a "danger zone" (where rounding errors are likely), the algorithm dynamically moves the positioning probes to a "safe zone" to recalibrate.

Fig 1: The FundALG logic using intersecting probe lines to narrow down user coordinates.

Experiments: Real-World Stalking

The team tested their 2-D algorithm against real WeChat accounts in a 1km x 1km area.

• Accuracy: 84% of simulation errors were under 60 meters.
• Reliability: The 2-D refinement reduced massive outliers (errors >100m) from 25% to just 10%.
• Efficiency: Despite the complexity, the attack runs in $O(N)$ time. Using parallel probes, a target can be "locked on" in seconds.

Fig 2: CDF showing the drastic improvement in accuracy between the fundamental and 2-D algorithms.

The Solution: K-Anonymity

To fix this, the authors suggest k-anonymity. Instead of reporting the user's distance, the server should report the distance of a "cloak user"—a randomly selected dummy location within a small radius $r$ of the actual user.

Does it work? Yes. In simulations, this defense increased the attacker's error by 15.7 times. Most predicted locations were pushed beyond 100 meters, making it impossible to identify which house or building a user is actually in.

Final Insights

This paper serves as a wake-up call for LBSN developers. Simple mathematical rounding is a "glass house" of security—easily shattered by anyone with a basic understanding of number theory. For developers, the takeaway is clear: obfuscation must be probabilistic (like k-anonymity or differential privacy), not just deterministic rounding.

Limitations

The current attack relies on the target's location remaining relatively static during the probing phase. Rapidly moving targets would require a significantly higher density of probes to track in real-time.