Half-Moon Cookie: Private, Similarity-Based Blocklisting with TOCTOU-Attack Resilience
About
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. 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, enabling independent choice of methods to compute them privately and efficiently. Still, this computation 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 show how Half-Moon Cookie can be instantiated for similarity-based malware detection, to block malicious executables without revealing client inputs or disclosing the blocklist.