Half-Moon Cookie: Private, Similarity-Based Blocklisting with TOCTOU-Attack Resilience
This work addresses the need for privacy-preserving blocklisting in security applications, enabling clients to verify items against sensitive blocklists without disclosure, while also mitigating time-of-check-to-time-of-use vulnerabilities.
Half-Moon Cookie introduces a private blocklisting framework that allows clients to check items against a proprietary blocklist without revealing queries or the blocklist, supporting similarity-based checks and efficient verification to prevent TOCTOU attacks. The design separates embedding from the blocklist check, achieving performance that scales with the sum rather than product of costs, and is demonstrated for malware detection.
Blocklisting is a common technique for preventing the use of known malicious content. However, conventional blocklisting infrastructures require either the blocklist to be public or clients to reveal their queries to the blocklist server. In this work, we introduce a private blocklisting framework, Half-Moon Cookie, by which a client can check an item against a proprietary blocklist held by a server, to determine whether the item is close to any blocklist element in a metric space. Critically, our design separates the embedding step from the blocklist check, so that performance degrades with their sum and not their product. Still, this check might be too costly to perform on the critical path of using the item, and so our design also supports a very efficient check that an item previously passed the blocklist check. In doing so, we support applications where one client can perform the blocklist check on the item before sending it, and recipients can more efficiently confirm the previous result before using the item, thereby avoiding TOCTOU attacks. We demonstrate how Half-Moon Cookie can be instantiated for similarity-based malware detection, enabling effective identification of malicious executables without revealing client inputs or disclosing the underlying blocklist.