Half-Moon Cookie: Private, Similarity-Based Blocklisting with TOCTOU-Attack Resilience

1. Problem Statement

The paper addresses two critical challenges in modern cybersecurity blocklisting:

1. Privacy vs. Utility: Conventional blocklisting requires either a public blocklist (leaking sensitive threat intelligence) or clients to reveal their queries to a server (leaking user data). This is particularly problematic for proprietary blocklists (e.g., specific malware signatures) and sensitive client inputs (e.g., proprietary executables or private emails).
2. TOCTOU Vulnerabilities: Checking an artifact against a blocklist immediately before use is often too computationally expensive for the "critical path" of execution. Moving the check to an earlier time (e.g., by the sender) introduces Time-of-Check vs. Time-of-Use (TOCTOU) vulnerabilities, where an attacker can swap a benign file for a malicious one after the check but before use.

Existing solutions for private blocklisting often rely on exact matching (ineffective for polymorphic malware) or require expensive cryptographic protocols (like garbled circuits) for every single check, making them impractical for large-scale deployment.

2. Methodology: The Half-Moon Framework

The authors propose Half-Moon Cookie (Half Moon), a three-party protocol involving a Sending Client ($C_{snd}$), a Receiving Client ($C_{rcv}$), and a Server ($S$). The system separates the blocklist check into two distinct phases to balance privacy, security, and performance.

A. Core Concept: Two-Phase Checking

1. Explicit Check (Sender-Side):

   • $C_{snd}$ submits an artifact $w$ to $S$.
   • $S$ holds a proprietary blocklist $U_{blk}$ (represented as a set of embeddings $L$ in a metric space).
   • The protocol checks if $w$ is "close" (within a distance threshold $T$) to any item in $L$ using fuzzy hashing (similarity-based matching).
   • Privacy: $S$ learns nothing about $w$; $C_{snd}$ learns nothing about $L$.
   • Outcome: If $w$ is clean, $S$ generates a hiding and binding token ($\gamma$) and stores it in an allowlist. $C_{snd}$ receives a nonce and the token parameters.

2. Implicit Check (Receiver-Side):

   • $C_{rcv}$ receives $w$ from $C_{snd}$.
   • Instead of re-running the expensive similarity check against the full blocklist, $C_{rcv}$ performs a lightweight verification against the allowlist using the token provided by $C_{snd}$.
   • TOCTOU Resilience: If the blocklist is updated, the allowlist is cleared, forcing a new explicit check. This minimizes the window for TOCTOU attacks.

B. Cryptographic Primitives & Optimizations

To achieve efficiency and security, the framework utilizes several advanced techniques:

• Metric Embedding: The blocklist is embedded into a metric space (specifically Hamming distance) using fuzzy hashing (e.g., TLSH).
• Reusable Garbled Circuits (RGC):
  • The "Embed-and-Map" phase (hashing the file) is computationally heavy. The authors use CRGC (Reusable Garbled Circuits) to decouple the circuit size from the input file size.
  • The circuit is split into reusable segments (handling linear operations like scanning the file) and non-reusable segments (handling the final check). This reduces communication and computation costs by orders of magnitude compared to monolithic garbled circuits.
• One-Time Pairwise Unpredictable Permutation:
  • To prevent a malicious sender from forging inputs, the system applies a permutation $P$ to the embedded hash.
  • This ensures that even if a malicious sender tries to submit a different file $w'$ that matches a previous token, they cannot predict the permutation output without the server's secret key.
• Symmetric Uncommon Roots (SUR) Metric:
  • To perform the distance check privately without revealing the vectors, the authors use a polynomial-based metric (SUR) derived from the Noisy Polynomial Addition (Fnpa) functionality. This allows the server to check if the Hamming distance is within the threshold without learning the actual hash values.
• Hiding and Binding Tokens:
  • The token $\gamma$ is constructed as $\gamma = f(w) + s \times H(w, f(w), k_f, m)$.
  • Hiding: The random mask $s$ and random oracle $H$ ensure $S$ cannot learn $w$ from $\gamma$.
  • Binding: The structure ensures a malicious $C_{snd}$ cannot find a different $w'$ that produces the same $\gamma$ (collision resistance).

3. Key Contributions

1. Formal Definition of Half-Moon: A new cryptographic primitive that supports both an explicit privacy-preserving similarity check and an efficient implicit confirmation check.
2. Efficient Similarity-Based Blocklisting: A framework that supports approximate matching (fuzzy hashing) while keeping both the blocklist and the client input private.
3. TOCTOU Resilience: A design pattern where the sender performs the heavy check, and the receiver performs a lightweight allowlist verification, effectively mitigating race conditions without sacrificing privacy.
4. Scalable Implementation:
   • Integration of Reusable Garbled Circuits to handle large file inputs (e.g., executables) efficiently.
   • Use of Fuzzy PSI (Private Set Intersection) techniques adapted for Hamming distance without data distribution assumptions.
5. Security Proofs: Formal proofs demonstrating security against:
   • Malicious Senders ($T_1$): Cannot forge tokens for blocked items or learn the blocklist.
   • Honest-but-Curious Servers ($T_2$): Cannot learn the client's input if the item is not blocked.

4. Experimental Results

The authors implemented Half-Moon in C++ and evaluated it on malware detection scenarios (using the Ember dataset and Enron email attachments).

• Performance Gains (Explicit Check):
  • Using Reusable Garbled Circuits (RGC) reduced communication volume by >2 orders of magnitude and response time by >1 order of magnitude compared to monolithic garbled circuits.
  • For a 5kB executable, response time dropped from ~1000s (monolithic) to ~4.8s (RGC) with TLSH.
• Throughput:
  • The system scales well with blocklist size ($|L|$). While larger blocklists increase latency slightly, the system saturates at high concurrency (e.g., ~250 concurrent requests for a 10kB file).
  • The cost is largely independent of the input file size due to the RGC optimization.
• Implicit Check Efficiency:
  • The implicit check is extremely fast (0.19s) and low bandwidth (7.2 KB), compared to fuzzy PSI baselines (e.g., Chakraborti et al. [29] took 160s).
  • It is independent of blocklist size, making it ideal for receivers.
• Hash Function Selection:
  • TLSH was found to be the most efficient hash function for this framework, outperforming ssdeep and sdhash in total response time.

5. Significance

The Half-Moon Cookie framework represents a significant advancement in privacy-preserving security infrastructure:

• Practicality: It bridges the gap between theoretical privacy protocols (which are often too slow) and real-world security needs (which require speed and scalability).
• Malware Defense: It enables effective detection of polymorphic malware (via similarity hashing) without exposing proprietary threat intelligence or user data.
• System Design: It offers a novel architectural solution to the TOCTOU problem by shifting the computational burden to the sender while maintaining strong security guarantees for the receiver.
• Broader Applicability: While demonstrated on malware, the framework is applicable to any scenario requiring private similarity checks, such as CSAM detection, spam filtering, or credential breach checks.

In summary, Half-Moon Cookie provides a robust, efficient, and privacy-preserving mechanism for verifying artifacts against proprietary blocklists, solving the trade-off between security, privacy, and performance that has hindered previous solutions.