Improved Leakage Abuse Attacks in Searchable Symmetric Encryption with eBPF Monitoring

This paper demonstrates that leveraging eBPF-based system-level monitoring reveals new leakage patterns in Searchable Symmetric Encryption (SSE) that extend beyond traditional threat models, thereby enabling more powerful leakage abuse attacks and highlighting the critical need to address system-level exposures in SSE defenses.

The Gist

Here is an explanation of the paper, translated into everyday language with some creative analogies.

The Big Picture: The "Locked Box" Illusion

Imagine you have a very secure, high-tech locked box (this is your encrypted data) that you send to a mysterious warehouse (the Cloud Server). You want the warehouse to find specific items inside the box for you without ever opening the box or seeing what's inside.

To do this, you use a special magic key (Searchable Symmetric Encryption, or SSE). You give the warehouse a token that says, "Find all items tagged 'Invoice'." The warehouse uses the token, finds the right items, and hands them back to you.

The Problem: The warehouse is "honest but curious." It won't steal your data, but it loves to watch what you do. It knows:

• How often you ask for "Invoices."
• How many items you get back each time.
• That you asked for "Invoices" three times today.

Researchers have known for a while that if the warehouse watches these patterns, it can guess what you are searching for. This is called a Leakage Abuse Attack.

The Twist: The "Ghost in the Machine"

This paper asks a scary new question: What if the warehouse doesn't just watch the boxes, but also watches the workers moving them?

Even if the boxes are locked and the labels are scrambled, the workers (the computer's operating system) still have to walk to specific shelves to grab the boxes. They have to open specific doors. They have to carry specific heavy crates.

The researchers discovered a tool called eBPF. Think of eBPF as a super-powered security camera that can be installed inside the warehouse's walls. It doesn't need to break the locks; it just watches the workers' footsteps in real-time.

The New Attack: "The Footprint Tracker"

Here is how the new attack works, step-by-step:

1. The Old Way (Frequency Matching):

   • Analogy: The warehouse manager counts how many boxes come out. "Ah, you asked for 'Invoice' and got 5 boxes. You asked for 'Contract' and got 2 boxes."
   • The Flaw: Sometimes, "Invoice" and "Budget" both result in 5 boxes. The manager gets confused and can't tell which one you actually wanted.

2. The New Way (eBPF Monitoring):

   • Analogy: The manager puts on the super-camera (eBPF). Now, instead of just counting boxes, the manager sees exactly which shelves the workers walked to.
   • Even though the boxes are locked, the shelf numbers (file names) are visible.
   • The manager thinks: "You asked for a token. The workers went to Shelf 101, Shelf 205, and Shelf 300. I know from my secret list that those shelves contain 'Invoices'."

The "Aha!" Moment

The researchers tested this in a lab using a dataset of real emails (the Enron dataset).

• The Old Attack: Got about 78% of the search terms right. It got stuck when two different words had the same number of results.
• The New Attack (with eBPF): Got 100% of the search terms right.

Why? Because even if two words have the same number of results, they almost never access the exact same specific files. The "footprints" (file access patterns) were unique enough to solve the puzzle.

The Takeaway: The "Back Door" in the Wall

The scary part of this paper isn't that the encryption is broken. The math is still perfect. The problem is that real-world computers leak information in ways the math doesn't account for.

• The Theory: "As long as the data is encrypted, we are safe."
• The Reality: "As long as the computer has to physically touch the files to read them, the operating system leaves a trail."

It's like having a vault that is mathematically unbreakable, but the guard leaves a trail of footprints in the dust that leads straight to the treasure.

What Should We Do?

The authors suggest that future security designs need to stop looking only at the "math" and start looking at the "machinery."

• Current Defenses: Hiding how many results you get (padding).
• Needed Defenses: Hiding which files are touched. This might require technologies like ORAM (Oblivious RAM), which is like making the workers shuffle around the warehouse, pick up random boxes, and drop them back down just to confuse the camera, so no one can tell which shelf was actually visited.

In short: If you are storing encrypted data in the cloud, you can't just trust the encryption. You have to worry about the "footprints" the server leaves behind while doing its job.

Technical Summary

Here is a detailed technical summary of the paper "Improved Leakage Abuse Attacks in Searchable Symmetric Encryption with eBPF Monitoring" by Chinecherem Dimobi.

1. Problem Statement

Searchable Symmetric Encryption (SSE) allows users to search encrypted data on untrusted cloud servers without revealing the content of the data or the queries. However, SSE schemes are known to leak metadata, such as access patterns (which documents are returned) and search patterns (query frequency).

• The Gap: While recent defenses (e.g., padding, volume hiding) have mitigated traditional Leakage-Abuse Attacks (like the Frequency Matching Attack), these defenses primarily focus on cryptographic and index-level leakages.
• The Core Issue: Existing threat models often ignore system-level leakages. Specifically, they assume that if the data is encrypted, the underlying operating system behavior (e.g., which specific files are opened and read by the kernel) remains opaque.
• The Question: Can an attacker with access to the Cloud Service Provider's (CSP) system kernel (via tools like eBPF) observe low-level file access patterns to bypass current SSE defenses and recover plaintext queries with higher accuracy?

2. Methodology

The authors propose a passive attack model where the adversary (the CSP) uses eBPF (Extended Berkeley Packet Filter) to monitor system calls in real-time during SSE operations.

A. Threat Model

• Adversary: An "honest-but-curious" CSP that follows protocols correctly but actively monitors system behavior.
• Capabilities:
  • Full visibility into encrypted operations (tokens, indexes, ciphertext).
  • System-level monitoring: Ability to use eBPF to trace kernel events (e.g., openat, read syscalls) to see exactly which ciphertext files are accessed.
  • Auxiliary Knowledge: Partial knowledge of the plaintext dataset (e.g., keyword frequencies and document distributions from a public source like the Enron dataset).
• Assumptions: The encryption itself is secure; the attacker cannot break the cryptography but can exploit implementation-level side channels.

B. The New Leakage Vector: $L_{fileAccess}$

The paper defines a new leakage pattern, $L_{fileAccess}$, which reveals the exact set of ciphertext filenames accessed for a specific search token ($t_w$).

• Mechanism: When a CSP processes a query, it must retrieve specific encrypted files from storage. In many implementations, these files retain their original filenames (or a direct mapping to them) at the filesystem level.
• Observation: By attaching eBPF probes to kernel system calls, the attacker logs the sequence of files opened for each query.

C. Enhanced Frequency Matching Attack (eFMA)

The authors extend the classic Frequency Matching Attack (FMA) into eFMA:

1. Baseline FMA: Matches query tokens to keywords based on result size (number of documents returned) and query frequency. This fails when multiple keywords have identical result sizes and frequencies.
2. eFMA Enhancement:
   • The attacker observes the exact set of filenames accessed ($F_e$) for a query token.
   • The attacker compares $F_e$ against the known plaintext file sets ($F_p$) derived from their auxiliary knowledge.
   • Resolution: If $F_e$ matches $F_p$ exactly, the attacker can uniquely identify the keyword, even if the frequency and result size are ambiguous.

3. Key Contributions

1. Identification of $L_{fileAccess}$: The paper formally defines a new leakage vector based on system-level file access patterns, which is distinct from traditional index-level leakage.
2. Demonstration of eFMA: The authors demonstrate that combining eBPF monitoring with standard leakage abuse techniques creates a significantly more powerful attack vector.
3. Bridging Theory and Reality: The work highlights a critical disconnect between theoretical SSE security models (which assume only index leakage) and real-world deployment vulnerabilities (where the OS kernel leaks file access details).
4. Practical Attack Implementation: The authors successfully implemented the attack using bpftrace (an eBPF tool) on a Dockerized environment, proving the feasibility of the attack without modifying the underlying SSE code.

4. Experimental Results

• Setup:
  • Scheme: DK-Nguyen DSSE (Dynamic SSE with forward privacy).
  • Dataset: 100 emails from the Enron dataset.
  • Tool: bpftrace for monitoring openat and read syscalls.
• Metrics: Query Recovery Accuracy (mapping encrypted tokens to plaintext keywords).
• Findings:
  • Baseline FMA: Achieved 77.8% accuracy. It failed to distinguish between keywords that shared the same frequency and result size (e.g., tokens T12, T13, T17, T18).
  • Enhanced eFMA: Achieved 100% accuracy.
  • Analysis: The eBPF monitoring allowed the attacker to distinguish between tokens with identical frequencies by observing that they accessed different sets of files. For example, two keywords might both return 12 documents, but the specific identities of those 12 files were unique to each keyword.

5. Significance and Implications

• Vulnerability of "Secure" Schemes: Even formally secure SSE schemes (like those with forward privacy) are vulnerable if the underlying system implementation does not obfuscate file access patterns.
• Limitations of Current Defenses: Padding and volume hiding are insufficient because they do not hide which specific files are being accessed, only how many.
• Need for New Threat Models: Future SSE security definitions must explicitly include system-level leakages (file access, syscall sequences, timing) rather than focusing solely on cryptographic leakage.
• Future Directions: The paper suggests that defenses like Oblivious RAM (ORAM) or file name obfuscation are necessary to mitigate these attacks, as standard SSE is no longer sufficient against an adversary with kernel-level visibility.

Conclusion

This research proves that system-level monitoring via eBPF creates a powerful side channel that can completely break the anonymity of SSE queries in realistic deployments. By observing which encrypted files are accessed, an attacker can resolve ambiguities that traditional frequency-based attacks cannot, achieving perfect query recovery in the tested scenario. This necessitates a paradigm shift in SSE design to account for the "noisy" reality of operating system interactions.