Secrecy Preserving Signatures

Project Background

Signature-based packet filtering plays a key role in detecting intrusions and related attacks for networks accessible to the public Internet. By analyzing packets for pre-determined suspicious patterns, a system of this type can alert network operators to undesired behavior and perhaps even trigger a response.
There are many other approaches to network intrusion detection—for example, studying the statistical behavior of network traffic, or monitoring the behavior of the network hosts themselves, searching for the markers of malicious code—but packet filtering is one of the most widely used. The open source filtering software Snort, for example, has over 400,000 registered users,[1] and it is just one of numerous tools that provide similar services.
The rules used for packet filtering can be as simple as a list of banned IP addresses, but with the rise of bot nets, and other compromised machine attacks, deep packet inspection is often necessary. This technique looks for patterns in the packet payload, using, typically, regular expressions to describe the problematic strings sought by a given filtering rule.
Effective filtering rules—sometimes called signatures—are valuable and can represent a serious investment of resources. Where such resources have been invested, it is to the benefit of the Internet community for the signatures to be widely deployed and used—reducing the ability of attackers to go unnoticed. On the other hand, distributing these signatures to third parties, which would be necessary for their scalable deployment, is not desirable for the organizations that invested so much in their creation.
For a security company, for example, its signature corpus might be one its most important intellectual property assets. It cannot simply make them available to any interested network operator. Similarly, for a government agency, their signatures might be literally classified—making it illegal for them to be made public.
Project Description
This tension between the need to deploy filters widely, and the need to protect the information contained in the filers, motivates a key question:
How can the organizations that generate signatures for network attack detection share this information with the network operators that need to perform filtering, without revealing too many details of the signatures?
This research project seeks answers to this question.
In more detail, in this project, we will focus on the more difficult (and more useful) component of packet filtering: deep packet inspection. We will seek new cryptographic/security techniques that allow obfuscated versions of signatures to be distributed in such a way that recreating the original signatures is impossible (at least, with respect to standard cryptographic hardness assumptions).
Furthermore, we will seek solutions that complicate offline dictionary attacks. In this context, a dictionary attack refers to the attacker strategy of rapidly running a large corpus of carefully selected packets through the filter—treating the logic as a black box—observing which packets trigger an alert and which do not, ultimately allowing it to reconstruct key pieces of the underlying signatures. 
If the filtering happens on a single machine, such attacks are unavoidable in the case where the machine is compromised. With this in mind, in this project we will seek solutions that distribute the filtering responsibility among multiple machines that must cooperate in some way to complete the alert decision. The goal is to require the compromise of multiple machines before an offline dictionary attack is possible. If it is possible to geographically isolate these machines, this constraint increases the challenge posed to an attacker. At the same time, the amount and complexity of the communication between these machines must be minimized to avoid too much of a performance degradation.
(One such efficient strategy, for example, might have the primary filtering machine generate an obfuscated alert code that it then passes on to another machine that can un-obfuscate it and register a real alert if necessary. The original machine, therefore, does not know which packets actually generate alerts. Also, these obfuscated alerts can be potentially batched and sent off at regular intervals, avoiding the need for the original machine to perform online communication for each packet as it arrives.)
Project Goals
This project is theoretical in nature. We will start by formally describing the problem and threat model, and then seek fundamental limits of what is and is not possible. Once the landscape of possibility is defined, we will seek a collection of algorithms with provable performance and security guarantees.
Privacy-preserving deep packet inspection is, to the best of our knowledge, a new topic in security. As with many such topics, the first step towards its successful realization in practice is understanding its theoretical foundations. This project takes this step.
Schedule of Major Steps

Exploratory research on relevant security systems, cryptographic primitives, and solutions for simpler filtering tasks (i.e., IP matching).
Formalization of network and threat models.
Development of lower bounds on what is and is not possible under our assumptions.
New algorithms for distributed deep packet filtering with provable performance and safety guarantees.