by Martin Burkhart and Xenofontas Dimitropoulos
At ETH Zurich, we have developed the SEPIA library, which makes secure multiparty computation practical for many participants and large input data volumes. This paves the way for novel approaches in collaborative network security.
We currently have a fundamental imbalance in cybersecurity. While attackers are acting in an increasingly global and coordinated fashion, eg by using botnets, their counterparts trying to manage and defend networks are limited to examining local information. Collaboration across network boundaries would substantially strengthen network defense by enabling collaborative intrusion and anomaly detection.
Unfortunately, privacy concerns largely prevent collaboration in multi-domain cyberdefense. Data protection legislation makes data sharing illegal in certain cases, especially if personally identifying information (PII) is involved. Even if it were legal, sharing sensitive network internals might actually reduce security if the data should fall into the wrong hands. To address these privacy concerns, a large number of data anonymization techniques and tools have been developed. However, these anonymization techniques are generally not lossless. Therefore, organizations face a delicate privacy-utility tradeoff. While stronger sanitization improves data privacy it also severely impairs data utility.
As an alternative to simplistic data anonymization techniques, we started the SEPIA project [1, 2] at ETH Zurich a few years ago. SEPIA aims at providing practical secure multiparty computation (MPC) tools for collaborative network security. MPC is a cryptographic framework that allows running computations on data distributed among multiple parties, while provably preserving data privacy without relying on a trusted third party. In theory, any computable function on a distributed data set is also securely computable using MPC techniques. Unlike anonymization, MPC gives information-theoretic guarantees for input data privacy. A well-known example of MPC is the Millionaire’s Problem: Two millionaires want to know which of them is richer without revealing their fortunes to each other. Using MPC, the millionaires can compute the answer to their question, without learning anything else.
Although MPC has been studied substantially for almost 30 years, building solutions that are practical in terms of computation and communication cost is still a major challenge, especially if input data are voluminous as in our scenarios. Therefore, we developed new MPC operations for processing high volume data in near real-time. The prevalent paradigm for designing MPC protocols is to minimize the number of synchronization rounds. However, the resulting protocols tend to be inefficient for large numbers of parallel operations, requiring hours or even days to compute simple functions. By optimizing the design of basic operations, we managed to significantly reduce the CPU time and bandwidth consumption of parallel MPC operations. SEPIA's operations are between 35 and several hundred times faster than those of comparable MPC frameworks.
SEPIA provides a layer of basic MPC operations for addition, multiplication, and different types of comparisons that can be used through an API to build more advanced composite protocols. On top of the basic operations, it provides a layer of composite protocols designed for network security and monitoring applications that require the aggregation of events and statistics from multiple domains. For example, the top-k composite protocol aggregates lists of key-value pairs from multiple parties and reveals only the keys with the k largest aggregate values. It can be used to implement an efficient IDS alert correlation mechanism to support multi-party collaboration, for instance in the fight against botnets, without requiring a trusted third party. So far SEPIA has implementations of ten such composite protocols including protocols for private set operations and distributed network anomaly detection.
Figure 1: Visibility of the Skype 2007 anomaly in counts of Netflow records across six networks. Collaborative protocols aid in identifying root causes by combining local views into a bigger picture.
To learn how SEPIA can be useful in practice, we applied it to trafﬁc data from 17 customer networks of the Swiss NREN (SWITCH) collected during the global Skype outage in August 2007. Figure 1 shows the Netflow count across six networks and the aggregate count as computed by SEPIA at the bottom (ALL). The Skype anomaly is clearly visible in the middle. By comparing their local view of the anomaly with the aggregate view, the organizations can quickly decide whether the scope is local or distributed. Also, they can assess how much the local network is affected compared to others and sometimes even proﬁt from early warnings (eg organization 6 was hit one day later than the others). Due to their privacy-awareness, MPC protocols allow the correlation of additional sensitive features, such as the top ports, IP addresses, or IDS alerts during normal and anomalous periods. Such aggregate information beyond the limited local view enables operators to quickly get the big picture of what is going on and act accordingly.
These results are indeed promising and we believe that MPC will play an important role in the future of collaborative network security. SEPIA is already being used by other researchers, for example for practical PIR in electronic commerce . In addition, the Swiss Commission for Technology and Innovation and IBM Research are funding an on-going project that aims at integrating SEPIA with a network monitoring commercial system from IBM thereby enabling privacy-preserving multi-domain flow analysis, which could lead to one of the first commercial products that use MPC.
 M. Burkhart and X. Dimitropoulos. Privacy-Preserving Distributed Network Troubleshooting - Bridging the Gap between Theory and Practice. ACM Transactions on Information and System Security (TISSEC), 14(4), Dec. 2011. R. Henry, F. Olumofin, and I. Goldberg. Practical PIR for electronic commerce. ACM CCS, 2011.
Tel: +41 44 632 70 04