Crypto Talk at 27C3: Automatic Identification of Cryptographic Primitives in Software, Day1, 16:00, Saal 3

Many applications, including closed source applications like malware or DRM-enabled multimedia players (you might consider them as malware too) use cryptography. When analyzing these applications, a first step is the identification and localization of the cryptographic building blocks (cryptographic primitives, for example AES, DES, RSA…) in the applications. When these blocks have been localized, the input and output of the cryptographic primitives and the key management can be observed and the application can be analyzed further. Fortunately, many cryptographic algorithms use special constants or have a typical fingerprint  and there are only a few different public implementations of the algorithm. This allows us to automate this first, Felix Gröbert will show us how:

Using dynamic binary instrumentation, we record instructions of a program during runtime and create a fine-grained trace. We implement a trace analysis tool, which also provides methods to reconstruct high-level information from a trace, for example control flow graphs or loops, to detect cryptographic algorithms and their parameters.

Trace driven/dynamic analysis has some advantages of static analysis:

• Because the program is analyzed at runtime, it is immediately known which parts of the code are used at which time, so that they might be correlated with runtime decryption of the code or with network communication.
• Inputs and outputs of the primitives as well as the keys are recorded, even if the originate from a remote server or botnet. This allows us to immediately distinguish between long term keys and session keys, if multiple executions of the same program can be recorded.
• This is also highly interesting if private keys are included in an obfuscated binary, for example private RSA keys.
• Dead or unused code is automatically excluded, so that one can proceed with the main parts of the code first.
• If additional code is loaded from a server, it is included in the analysis. This would be hard to impossible using static analysis.

Of course, trace driven analysis has it disadvantages, for example if a malware needs to communicate with a command-and-control server, which has already been taken down or behaves differently on different systems or at different times.__

Personally, I am interested in this talk because it might make ease up the analysis of closed source applications using cryptography. Even if the application, the DRM scheme, or the cryptographic primitive has no special weaknesses or bugs, just he recording of every input and output of all cryptographic building blocks in the application might be sufficient to extract a DRM free version of DRM protected digital content. Please also note that even if an application uses only well analyzed cryptographic primitives as AES and RSA, it might still be insecure, if these primitives are used in the wrong way.

See the talk at Day 1, 16:00, Saal 3!

Author: Erik Tews