MSAG: Cracking WeChat's Location Privacy Through Missequence State Analysis

TL;DR

Despite WeChat's efforts to mask user locations through distance rounding and systematic noise, researchers have uncovered a new vulnerability. By shifting the focus from reported distances to the relative order of users in the "People Nearby" list, the proposed MSAG method can pinpoint a user within 50 meters, rendering traditional obfuscation strategies ineffective.

The "People Nearby" Privacy Paradox

WeChat's "People Nearby" feature is a double-edged sword. While it facilitates social discovery, it provides a playground for "stalking" through trilateration. To counter this, WeChat implemented several defense mechanisms:

• Distance Banding: Reporting distances in 100m or 1km increments.
• Systematic Noise: Intentionally reporting a 260m distance as 400m.
• Relative Hiding: Only showing distance, not coordinates.

Existing attacks like RRABG or HNBG try to "guess" the real distance from these noisy reports. However, as the noise increases, these methods fail. The authors of this paper realized that while the distance numbers are fake, the order in which users appear still carries high-fidelity spatial information.

Methodology: The Power of Relative Order

The core insight of MSAG is the Hybrid Distance Range (H). In a perfect system, if User A is 100m away and User B is 101m away, User A always appears first. In WeChat, the injected noise might put User B first—this is a Missequence State.

1. Determining the "Stable" Threshold (H)

Through 100,000 statistical tests using mock locations, the authors found that if the distance between two users is large enough (greater than H ≈ 29.6m), WeChat's noise can no longer swap their positions. This H value is the "key" to the attack.

2. The Reference Probe (RP) Attack

Instead of guessing where the target is, the attacker places a controlled account (Reference Probe) near the target.

• Binary Search: The attacker moves the RP until it is adjacent to the target in the "People Nearby" list.
• Sequence Checking: By micro-adjusting the RP's position, the attacker finds the exact point where the RP and the target "flicker" in order.
• Delimiting the Ring: Once the missequence is found, the target's distance is constrained to $d_{pr}\pm H$.

Experimental Battleground: SOTA Comparison

The researchers conducted a massive 15-month study in Beijing/Zhengzhou. They compared MSAG against three major baselines:

1. RRABG: Relation between reported and actual distance.
2. HNBG: Heuristic number theory approach.
3. ETBG: Enhanced trilateration (Grindr-style attack).

Key Performance Metrics

• Precision: MSAG achieved an average error of 44.1m.
• Reliability: 72% of its errors were under 60m, whereas ETBG (which assumes a perfect order) failed miserably on WeChat due to the systematic noise.
• Complexity: MSAG remains efficient at $O(\log N)$, making it practical for real-time tracking.

Critical Insight: Why Does This Work?

Traditional defenses focus on the magnitude of the error (making the distance number wrong). MSAG succeeds because it exploits the topology of the list. Since WeChat wants to provide a usable service, it must keep the list "mostly" sorted. That "mostly" is exactly where the privacy leak lives.

Handling Anomalies

The paper also introduces sophisticated strategies for trilateration when circles don't perfectly intersect (a common issue with noisy data). They provide geometric solutions for four specific "abnormal" cases, ensuring a result is always generated even when data is inconsistent.

Conclusion & Future Outlook

MSAG proves that distance obfuscation is not a silver bullet. For LBSN developers (like those at Tencent), the takeaways are clear:

• Limit Query Frequency: Restricting how many times an account can "refresh" nearby users slows down the binary search.
• Bigger Sequence Shuffling: Injecting more randomness into the order of users, not just the reported distance.
• Identity Verification: Detecting virtual/mock locations remains the best front-line defense.

For the academic community, this work opens a new door: the analysis of Missequence States as a general tool for probing black-box social discovery algorithms.