When shuffling fails: recovering tokens from obfuscated KV caches
When Shuffling Fails: Token Recovery from Obfuscated KV Caches
Translation in progress — untranslated text is omitted.
Quick read
Based on the paper PDF (AI-generated); refer to the original
Researchers from Huazhong University of Science and Technology and other institutions propose in a paper the Repeat-to-Reveal attack, which breaks obfuscation defenses such as KV-Cloak that protect KV caches with secret transforms plus random permutations, achieving 100% token multiset recovery on 11 models, 13 configurations and 3,000 WildChat prompts, including caches produced by a running vLLM engine. The attack exploits input symmetry: repeated-token prompts make entire blocks of Value rows identical, defeating the random permutation and collapsing the effective state space from b! to b; a single calibration then allows passive recovery of subsequent cache blocks across requests within the same secret period, and language-model ranking restores the text, reaching a semantic similarity of 0.947 with the original source. In synthetic tests, the attack identified sensitive values such as passwords and card numbers from 100 candidates with a 97.5% expected top-1 accuracy; the same collapse mechanism was also validated on the sequence permutation defense of Thomas et al. and on PermLLM.
- LLM serving systems store and share KV cache blocks, exposing token-level representations. One class of defenses (shuffled obfuscation) protects the cache with a secret linear transformation plus random permutation, claiming that the b! permutation group size provides security; the authors argue this argument is flawed.
- The authors point out that input symmetry collapses b! into b distinguishable states, and propose the Repeat-to-Reveal attack: use repeated-token probes to calibrate an equivalent demixer, then recover the token multiset via matching against the public model dictionary, and rank with LM beam search; they also propose the V EIL KV authenticated encryption defense.
- On KV-Cloak, token multiset recovery Rbag reaches 100% across 11 models, 13 configurations, and 3,000 WildChat prompts (GPU); LM ordering Scos is 0.947; Acc@1 on 100 synthetic sensitive-value cases is 97.5%; the mechanism is confirmed on two other defenses of the same kind.
- The authors state that the attack requires the probe and target to share the same secret configuration (S, M, a), and did not measure how often real deployments satisfy this condition; targets are English WildChat prompts, first-layer Value blocks; the sensitive-value experiment is a closed-set setting; V EIL KV's latency overhead is non-negligible, and production deployment also requires hardware key isolation and anti-rollback.
The paper points out that KV cache obfuscation defenses relying on permutation randomness have their effective state space collapse under attacker-chosen inputs; teams deploying private inference protections can use this to test security arguments.