Skip to main content
Back to timeline
arXivSource publication:

A repeated-token prompt collapses KV-cache shuffling: one calibration recovers token multisets from any request, hitting 100% across 11 models

Synopsis

KV-cache obfuscation defenses rest their security on a fresh random permutation per block, but an attacker who submits a prompt of repeated tokens makes that permutation act as the identity on the data matrix, collapsing the observable states from the permutation-group order to roughly the block length. From the rank-one differences among those states, the attacker solves for an equivalent demixer without the defender's secret parameters, and it transfers across requests within the same secret epoch. On KV-Cloak, a single calibration yields 100% token-multiset recovery over 3,000 real WildChat prompts, eleven models and thirteen configurations, including caches from a live vLLM engine.

Source-provided article image: When Shuffling Fails: Token Recovery from Obfuscated KV Caches
arXiv

Interpretation

The random permutation in KV-cache obfuscation defenses can be cancelled by an input the attacker chooses, so the token content carried in a cache block becomes recoverable. Such defenses previously treated the freshly sampled per-block row permutation as the main barrier, on the grounds that the permutation group is far too large to brute-force. On KV-Cloak, a repeated-token probe makes every KV head form exactly as many distinguishable state clusters as the block length, with a separation ratio above 1,324.6 in every head.

The attacker solves an equivalent demixer from the rank-one differences among these states, then matches the recovered rows to tokens with a public-model token dictionary. The demixer needs only one calibration on the attacker's own probe blocks, after which it applies passively to other requests' cache blocks under the same secret epoch. Across 3,000 WildChat prompts, eleven models from 0.5B to 32B parameters and thirteen configurations, token-multiset recovery is 116,571,072/116,571,072, or 100%, including caches produced during live vLLM inference.

The recovered token multiset supports further privacy consequences: language-model reordering restores semantic content, and closed-set matching pinpoints a specific sensitive value. The multiset itself carries no within-block order, so order must be inferred separately, whereas sensitive-value identification does not need it. On a 602-prompt subset, beam-search reordering reaches a mean sentence-embedding cosine of 0.947; on 100 synthetic sensitive-value cases, expected top-1 accuracy is 97.5%, with top-5 and top-10 both at 100%.

Perspective

The demonstration is limited to first-layer Value blocks of the official KV-Cloak implementation, and the attack requires the probe and the target to share one secret epoch, meaning the same row transform, column transform and marker. Evaluation uses English WildChat conversations, mostly 16-token blocks with additional 8- and 32-token blocks, and FP32 inference on a single A100. VeilKV's correctness and tamper rejection are verified in the tested software and vLLM 0.8.5.post1 versions.

Sensitive-value identification is measured in a closed-set setting with a known request template and 100 same-type candidates, which is not unconstrained credential recovery. The algebraic output gives no within-block positions, so order relies on a language-model prior, and only 1 of 602 prompts is fully correctly ordered. VeilKV's protection time is markedly higher than unfused KV-Cloak, and production deployment would additionally need hardware-backed key isolation and an anti-rollback epoch ledger.