CryptographcAutomated Identification of Cryptographic Primitives in Binary Programs
Felix Gr¨bert1 , Carsten Willems2 , and Thorsten Holz1 o
2 1 Horst G¨rtz Institute for IT-Security, Ruhr-University Bochum o Laboratory for Dependable Distributed Systems, University of Mannheim

Abstract. Identifying that a given binary program implements a specific cryptographic algorithm and finding out more information about the cryptographic code is an important problem. Proprietary programs and especially malicious software (so called malware) often use cryptography and we want to learn more about the context, e.g., which algorithms and keys are used by the program. This helps an analyst to quickly understand what a given binary program does and eases analysis. In this paper, we present several methods to identify cryptographic primitives (e.g., entire algorithms or only keys) within a given binary program in an automated way. We perform fine-grained dynamic binary analysis and use the collected information as input for several heuristics that characterize specific, unique aspects of cryptographic code. Our evaluation shows that these methods improve the state-of-the-art approaches in this area and that we can successfully extract cryptographic keys from a given malware binary. Keywords: Binary Analysis, Malware Analysis, Cryptography

1

Introduction

Analyzing a given binary program is a difficult and cumbersome task: an analyst typically needs to understand the assembly code and interpret it to draw meaningful conclusions from it. An attacker can hamper the analysis attempts in many ways and take advantage of different code obfuscation techniques [10, 15]. A powerful way to complicate analysis is cryptovirology [23], i.e., using cryptography in a program such that specific activities are disguised. The following list provides a few recent examples of real-world malware which use cryptography in one form or another: – Wang et al. analyzed a sample of Agobot, which uses SSL to establish an encrypted IRC connection to a specific server [20]. – Caballero et al. showed that MegaD, a malware family communicating over TCP port 443, uses a custom encryption protocol to evade network-level analysis [2]. – Werner and Leder analyzed Conficker and found that this malware uses the OpenSSL implementation of SHA-1 and a reference implementation of MD6.

2

F. Gr¨bert et al. o

Interestingly, the attackers also later patched the MD6 implementation in a malware update to fix a buffer overflow in the MD6 reference implementation [7]. Furthermore, Porras et al. found that the malware authors use RSA with 1024 bits for signature verification [16], in newer versions the attackers even use RSA with a 4096 bit key. – Werner and Leder also analyzed the Waledac malware [21]. About 1,000 of the 4,000 functions used by Waledac have been borrowed from OpenSSL. Furthermore, AES in CBC Mode with an IV of zero is used. The self-signed RSA client certificates are used in a key exchange protocol. – Stewart analyzed the algorithms used by the Storm Worm malware [17]. For the peer-to-peer and fast-flux communication, the malware uses a static XOR algorithm for subnode authentication and a RSA key with 56 bits [5]. An analyst needs to manually identify the cryptographic algorithms and their usage to understand the malicious actions, which is typically time-consuming. If this task can be automated, a faster analysis of malware is possible, thus enabling security teams to respond quickly to emerging Internet threats. In this paper, we study the problem of identifying the type of cryptographic primitives used by a given binary program. If a standardized cryptographic primitive such as AES, DES, or RC4 is used, we want to identify the algorithm, verify the instance of the primitive, and extract the parameters used during this invocation. This problem has been studied in the past, for example by Wang et al., who introduced a heuristic based on changes in the code structure