Cheap wireless tags — RFID labels, tire-pressure sensors, Bluetooth beacons — cannot afford real cryptography, so their anti-tracking protection is built from the few operations that fit a tiny silicon budget: bitwise XOR, rotations, and shift registers. The result is a long history of one-off breaks. Tire sensors broadcast a static 32-bit identifier that anyone with a software-defined radio can log from 40 meters away Security and Privacy Vulnerabilities of In-Car Wireless Networks: A Tire Pressure Monitoring System Case Study, and static MAC addresses have allowed hotspot eavesdroppers to trace users for two decades A Methodological Assessment of Location Privacy Risks in Wireless Hotspot Networks. When designers rotate identifiers instead, the lightweight math underneath keeps collapsing: an adversary who XORs a chosen value into a tag's response can re-identify the tag in later sessions because XOR is linear Vulnerability analysis of lightweight secure search protocols for low-cost RFID systems, and Pandaka's linear key schedule turns key recovery into Gaussian elimination Evaluation and Cryptanalysis of the Pandaka Lightweight Cipher. Every one of these breaks was found by hand, protocol by protocol, by experts who happened to look.
This proposal borrows a tool from a field with the opposite problem. In control theory, linearity is the resource that makes prediction cheap: Willems' fundamental lemma says that for a linear system, any behavior the system can exhibit is a linear combination of windows of one sufficiently rich recorded trace, which is why data-driven controllers can skip system identification entirely Data-Driven Model Predictive Control with Stability and Robustness Guarantees, Regularized and Distributionally Robust Data-Enabled Predictive Control. Those authors are candid that the lemma dies on nonlinear plants. We propose to run the lemma backwards, as an attack oracle. A tag protocol is conditionally linear exactly when the adversary can make the tag's own responses betray that linearity — the same regime cryptanalysts keep surfacing by hand, from chosen initialization vectors that suppress carry propagation in ARX ciphers Chosen IV Cryptanalysis on Reduced Round ChaCha and Salsa to XOR operations that dissolve into integer matrix multiplication under restricted inputs Cryptanalysis of LASH. If we can detect that regime automatically, with a query budget an eavesdropper actually has, we get three things at once: an automated vulnerability finder, a quantitative security margin, and a working tracking attack whenever the margin hits zero.
Core Claim
Treat a tag protocol as a black box that maps a public challenge (a nonce, a reader query, an injected value) and hidden internal state to an emitted message. The adversary records input–output traces under challenges it chooses, builds a Hankel matrix — a matrix whose columns are all length-$L$ sliding windows of that recorded trace — and asks whether a freshly queried response can be written as a combination of the recorded ones:
$$\rho(\mathcal{U}) \;=\; \min_{\alpha} \big\lVert H_L(\mathcal{D})\,\alpha - \bar{y} \big\rVert_2$$
Here $\mathcal{D}$ is the recorded trace, $\bar{y}$ is a new probe response drawn from a chosen input subspace $\mathcal{U}$, and $\alpha$ is the vector of combining weights. If the chosen inputs are rich enough to span the space of length-$L$ behaviors (persistently exciting, in the control-theory phrase), then a near-zero residual is not a heuristic signal but a certificate: by Willems' lemma the protocol acts affinely on $\mathcal{U}$, and the fitted $\alpha$ is an exact predictor of future tag responses that the adversary can use to re-link randomized sessions or forge replies. The superposition margin $\mu$ is the smallest residual the adversary can drive to within a fixed query budget, minimized over its choice of input subspace. A protocol with $\mu \approx 0$ on some adversary-reachable subspace is trackable by linear algebra; a protocol with $\mu$ bounded away from zero forces the attacker to model nonlinearity. This inverts the standard roles of the two literatures: control theory treats superposition as the property that enables guarantees A Tour of Reinforcement Learning: The View from Continuous Control, and cryptanalysis treats it as the property that destroys them; we use the control-theoretic characterization of linearity as the security test itself.
Research Program
The first workstream builds the oracle. Chosen-input subspaces are the crux: global linearity is easy to test, but the dangerous regimes are conditional — carry-free additions, restricted input sets that absorb XOR into matrix form Cryptanalysis of LASH, rotational regimes where ARX designs become linear modulo $2^n-1$ Rotational Cryptanalysis of ARX, and bit positions where nonlinear feedback functions admit linear approximations, as in HC-128 Some Observations on HC-128. We will develop a search over structured input families — bit-masked challenges, offset injections in the style of the Lv et al. attack, chosen-IV patterns in the style of Maitra — that minimizes $\rho$ per unit of query budget, and characterize the sample complexity of detection as a function of Hankel depth $L$ and state size.
The second workstream makes the margin meaningful. Coulson et al. proved that regularizing the Hankel combining weights is equivalent to robustness against distributional shift over a Wasserstein ball Regularized and Distributionally Robust Data-Enabled Predictive Control; we reinterpret their robustness guarantee as an attacker's error bound, so $\mu$ measures how far a linear predictor is from being certifiably exact. Where the residual is small but nonzero, we bound how much it can shrink under local approximation using sector-style constraints on the nonlinear layers, the technique Yin et al. used to bound activations when certifying neural controllers Imitation Learning with Stability and Safety Guarantees. The output is the curve Yarom et al. explicitly left open: how many gates of nonlinearity a designer must buy to buy how much margin Evaluation and Cryptanalysis of the Pandaka Lightweight Cipher.
The third workstream turns the oracle into a tracking attack under mobility, the regime where existing trackers fail. Gagnon et al. showed RSSI fingerprinting re-identifies randomized BLE devices at up to 99% accuracy when everything is static, but below 50% once targets move, because the physical channel is a nonlinear, time-varying process they treat only as an empirical nuisance RSSI-Based Fingerprinting of Bluetooth Low Energy Devices. A digital-layer linear predictor does not depend on the channel at all; when it succeeds, re-linking should be mobility-invariant. Where physical evidence is still wanted — for instance, distinguishing a genuine tag from a clone using motion feasibility — we fuse the digital re-link with learned nonlinear motion models in the spirit of ABC-LMPC's ensemble dynamics and sampling-based prediction ABC-LMPC: Safe Sample-Based Learning MPC for Stochastic Nonlinear Dynamical Systems with Adjustable Boundary Conditions, upgrading the fixed-graph, bounded-velocity travel-time reasoning of ACD ACD: An Adaptable Approach for RFID Cloning Attack Detection.
Baselines
The naive reference point is "the randomization works": an eavesdropper with no attack re-links sessions at chance rate, $1$ over the tag population. Any real attack must beat this, and the point of the study is to measure how far above chance each method sits.
The strongest existing competitor on the digital layer is bespoke expert cryptanalysis, and we will reimplement the published attacks on the same protocol builds we test against. For Pandaka, that is the Known-Indicators Attack of Yarom et al., which recovers base keys with $2^{55}$ guesses from about 170 bits of known plaintext for Pandaka(16,6), and whose CRC leakage drops a ciphertext-only attack on Pandaka(32,6) from $2^{192}$ to roughly $2^{72}$ Evaluation and Cryptanalysis of the Pandaka Lightweight Cipher. For the Kulseng protocols, it is the XOR-manipulation attack of Lv et al. that re-identifies tags across sessions and desynchronizes readers Vulnerability analysis of lightweight secure search protocols for low-cost RFID systems. The file reports no re-link rate or detection sample complexity for that attack, so we state plainly: no reported result found on Lacuna for a quantitative tracking rate on the Kulseng protocols; we will generate one ourselves. The fair-comparison rule is that our oracle gets the same total query budget (bits of known plaintext, number of tag sessions) and the same compute as the re-implemented hand attacks, but no source code or algebraic description of the protocol — only black-box query access. Beating the baseline means recovering an equally strong attack (comparable guessed-key complexity and plaintext budget on Pandaka; the same re-link and desynchronization effect on Kulseng) from queries alone.
On the physical layer, the strongest competitor is the RSSI histogram classifier of Gagnon et al., which reached up to 99% re-identification among 30 static devices and fell below 50% in dynamic settings RSSI-Based Fingerprinting of Bluetooth Low Energy Devices. Their Inria dataset is not public, so we re-collect matched static and dynamic traces with the same histogram resolution they found best (10–15 bins) and report their published figures as the reference numbers.
Two ablations isolate the key ingredient. The first replaces the chosen-input subspace search with passive sampling of whatever challenges the reader happens to send; if the oracle still finds the linear regimes, the adaptive search is unnecessary, and the proposal's central mechanism is wrong. The second replaces the Hankel span test with a plain global linear regression of responses on challenges, run with the same budget; this separates conditional-linearity detection from trivial global linearity.
Why not just…?
Why not just fit a linear regression to the input–output data? For a globally linear design like Pandaka's key schedule, a regression would find the vulnerability just as well, and we concede that up front; the ablation exists to quantify exactly this. The reason to invoke the Hankel machinery is conditional linearity, where the affine behavior holds only on a chosen subspace — carry-suppressed additions Chosen IV Cryptanalysis on Reduced Round ChaCha and Salsa, restricted input sets in LASH Cryptanalysis of LASH — and a global regression dilutes that signal across the nonlinear complement. The decisive experiment is the reduced-round ChaCha test below: if a plain regression finds the chosen-IV regime as cheaply as the subspace search does, the subspace search adds nothing and should be dropped.
Why not just run bespoke cryptanalysis on each new protocol? That is the status quo that produced every break cited above, and an expert with the source can in principle exceed any fixed query budget — a real threat we take seriously. But it is slow, expert-bound, and has repeatedly missed subtle cross-group correlations that designers also missed, as Wagner showed for the Yi-Lam hash Cryptanalysis of the Yi-Lam Hash. A black-box oracle that any evaluation lab can run against a compiled protocol, before deployment, closes the gap between "an expert looked at it" and "it was checked." The decisive check is agreement: the oracle must reproduce the known-vulnerable results and stay silent on known-strong ones.
Why not just fix the problem with standard nonlinear primitives, or defend with better fingerprinting? On the defense side, both Lv et al. and Yarom et al. recommend nonlinear functions but acknowledge the gate-count cost that motivated the weak designs in the first place Evaluation and Cryptanalysis of the Pandaka Lightweight Cipher; the margin curve is precisely the tool for spending that budget rationally, and even strong ARX primitives retain conditional linear regimes under chosen inputs Chosen IV Cryptanalysis on Reduced Round ChaCha and Salsa, so a cheap test remains useful after the upgrade. On fingerprinting, learned channel classifiers are environment-dependent and collapse under motion, below 50% in Gagnon et al.'s own dynamic experiments RSSI-Based Fingerprinting of Bluetooth Low Energy Devices, and they offer no exactness guarantee; the zero-residual certificate, backed by persistence of excitation, is the qualitative difference. Honest caveat: physical-layer randomization defenses such as randomized modulation Securing RFIDs by Randomizing the Modulation and Channel attack a different leakage channel and would remain necessary alongside anything we propose.
Proposed Experiments and Decisive Checks
The first experiment is ground-truth rediscovery. We reimplement the Kulseng Basic and Synchronisation protocols and Pandaka(16,6) and (32,6) from their published descriptions, give the oracle black-box query access, and measure detection sample complexity and the strength of the recovered attack. Success means matching the hand attacks' outcomes — $2^{55}$-guess key recovery from roughly 170 bits of plaintext on Pandaka(16,6), and the CRC-driven ciphertext-only drop toward $2^{72}$ on Pandaka(32,6) Evaluation and Cryptanalysis of the Pandaka Lightweight Cipher — without source access, at comparable budget.
The second experiment tests sensitivity to conditional, not global, linearity. We build a tag pseudonym generator on reduced-round ChaCha and let the oracle search chosen-IV-style input families. The known ground truth is that chosen IVs suppress carries and let differential biases survive into round 7, improving the published attack complexity from $2^{248}$ to $2^{238.94}$ Chosen IV Cryptanalysis on Reduced Round ChaCha and Salsa; the oracle should flag exactly those input regimes with depressed residuals, while full 20-round ChaCha should keep the margin bounded away from zero at any practical budget — the essential false-positive check.
The third experiment measures tracking under mobility. We run a population of emulated tags with rotating pseudonyms through static and dynamic scenarios, comparing our digital re-link, the Gagnon-style RSSI classifier, an ACD-style spatiotemporal feasibility tracker (whose published figures — 98.7% average accuracy, 96% recall, and 3.273 seconds of online delay on a 10,000-tag, 400,000-point stream ACD: An Adaptable Approach for RFID Cloning Attack Detection — set the scalability bar), and the fusion. The hypothesis is that digital re-linking is mobility-invariant while RSSI-based tracking degrades from the 99% static reference toward the sub-50% dynamic regime its authors reported.
The fourth experiment produces the designer-facing margin curve: sweep the nonlinearity budget (S-box layers, rounds, nonlinear state updates) in a synthetic protocol family and plot $\mu$ and attacker success against gate count. If the curve is flat where theory says nonlinearity should bite, the margin is not measuring what we claim, and the proposal's second workstream needs rethinking rather than repair.
References
- Security and Privacy Vulnerabilities of In-Car Wireless Networks: A Tire Pressure Monitoring System Case Study
- A Methodological Assessment of Location Privacy Risks in Wireless Hotspot Networks
- Vulnerability analysis of lightweight secure search protocols for low-cost RFID systems
- Evaluation and Cryptanalysis of the Pandaka Lightweight Cipher
- Data-Driven Model Predictive Control with Stability and Robustness Guarantees
- Regularized and Distributionally Robust Data-Enabled Predictive Control
- Chosen IV Cryptanalysis on Reduced Round ChaCha and Salsa
- Cryptanalysis of LASH
- A Tour of Reinforcement Learning: The View from Continuous Control
- Rotational Cryptanalysis of ARX
- Some Observations on HC-128
- Imitation Learning With Stability and Safety Guarantees
- RSSI-Based Fingerprinting of Bluetooth Low Energy Devices
- ABC-LMPC: Safe Sample-Based Learning MPC for Stochastic Nonlinear Dynamical Systems with Adjustable Boundary Conditions
- ACD: An Adaptable Approach for RFID Cloning Attack Detection
- Cryptanalysis of the Yi-Lam Hash
- Securing RFIDs by Randomizing the Modulation and Channel