Analysis-Resistant Malware

Traditionally, techniques for computing on encrypted data have been proposed with privacy preserving applications in mind. Several current cryptosystems support a homomorphic operation, allowing simple computations to be performed using encrypted values. This is sufficient to realize several useful applications, including schemes for electronic voting [16, 12, 17] and single server private information retrieval (PIR) [19, 9]. In this paper, we introduce an alternative application for these techniques in an unexpected setting: malware. We point out the counterintuitive possibility of malware which renders some aspects of its behavior provably resistant to forensic analysis, even with full control over the malware code, its input, and its execution environment. While methods for general purpose computation on encrypted data have not yet been realized, we explore the potential use of current techniques. Specifically, we consider in depth the possibility of malware which employs private information retrieval techniques to find and retrieve specific pieces of sensitive information from compromised hosts while hiding its search criteria. Through an evaluation of the goals of attackers and the constraints under which they operate, we determine that PIR techniques are an attractive technology to malware authors with the potential to increase the threat of targeted espionage. We go on to demonstrate the present feasibility of PIR-based malware through a series of experiments with a full implementation of a recent private stream searching scheme. Through the example of PIR-based malware, we highlight the more general possibilities of computing on encrypted data in a malicious setting.