[Paper Review] Relocate-Vote Using Sparsity Information to Exploit Ciphertext Side-Channels

This is a paper review for Relocate-Vote Using Sparsity Information to Exploit Ciphertext Side-Channels (USENIX’25)(https://aasthakm.github.io/files/sec25-relocatevote.pdf)

I’ve been looking for similar papers about attacking the AMD SEV-SNP by doing a ciphertext side channel attack.

And this paper is a current and relevant one.

Introduction/Background

What is a ciphertext side channel attack?

The ciphertext side channel attack is a type of side channel attack. Since a confidential computing environment encrypts memory, the result of reading the pages is ciphertext (encrypted data).

And by making a dictionary between plaintext and ciphertext, the attacker can recover pairs of plaintext-to-ciphertext.

The characteristics of AMD SEV-SNP

AMD SEV-SNP, one of the pioneering techniques for confidential computing, is implementing memory encryption via AES XEX encryption mode.

This mode uses a tweak value to perform an XOR operation with the plaintext, and these tweak values are derived from an address where the data will be stored.

Because of this, the encrypted data stored in a specific address results in determinism.

Attack method

Understanding the nature of the encryption mode the AMD SEV-SNP uses, we can get a critical insight into an attack surface. If we put known data at the known address, the ciphertext is predictable.

Also, the paper suggests another important observation that the frequency of ciphertext can give an attacker hints about the operations the victim is doing. It matters because if the same plaintext (like 0 ) is common across many pages, its ciphertext will show up more frequently than others. By looking at ciphertext frequency distributions, the attacker can deduce which ciphertext corresponds to which common plaintext value, without ever seeing the plaintext directly.

In this paper, we introduce a novel Relocate-Vote primitive that exploits ciphertext frequency distributions to learn the ciphertexts of prevalent values in a CVM page frame.

And what matters here is that all relocations must land in the same frame so the tweak (sPA) stays constant. This ensures that the same plaintext block always produces the same ciphertext during sampling.

Our attacks consist of two phases: an offline phase conducted before the victim CVM’s execution and an online phase that takes place during the victim CVM’s execution. In the offline phase, we assume the attacker knows the victim applications running inside the CVM and analyzes their behavior to understand how sparsity manifests in the applications. Through this, the attacker learns how to decode the pattern of prevalent and non-prevalent values to extract sensitive information from the application.

In the online phase, the attacker first learns the ciphertexts of prevalent values in the CVM using Relocate-Vote, then monitors CVM’s execution through controlled-channel attacks to locate pages containing secret information and finally recovers the encoded secrets by decoding the distribution of prevalent and non-prevalent values. To highlight the core idea of the attack and simplify implementation, our current attack prototype uses only a single target page frame during the online phase. Upon receiving a page fault via the controlled channel, the attacker immediately relocates the fauling page to this target frame, thereby revealing the collision status of each encrypted block on the faulting page.

Sparse LLM leakage via ReLU Activation

ReLU’s “Sparsity” (lots of zeros) is what leaks — the attacker can distinguish which memory blocks are all prevalent values (zeros) vs. which contains nonzeros, revealing patterns linked to the secret input tokens.

ReLU generates input-dependent patterns of interleaving zero and positive values and can reveal information about the processed tokens.

The attacker cannot see the exact hidden states (real activation values). Instead, they use their Relocate-Vote primitive to learn which memory blocks are all zeros vs. contain some non-zero values. Because encryption operates in 16 B blocks, they can’t pinpoint which neuron inside that block is active — only that at least one is.

Personal input

1. Interestingly, they recover the input prompts for LLM (LLaMA.cpp)
2. Relocating is a definite good option when there’s no repetitive access to the same address.