  Malware authors often use cryptographic tools such as XOR encryption and
block ciphers like AES to obfuscate part of the malware to evade detection. Use
of cryptography may give the impression that these obfuscation techniques have
some provable guarantees of success. In this paper, we take a closer look at
the use of cryptographic tools to obfuscate malware. We first find that most
techniques are easy to defeat (in principle), since the decryption algorithm
and the key is shipped within the program. In order to clearly define an
obfuscation technique's potential to evade detection we propose a principled
definition of malware obfuscation, and then categorize instances of malware
obfuscation that use cryptographic tools into those which evade detection and
those which are detectable. We find that schemes that are hard to de-obfuscate
necessarily rely on a construct based on environmental keying. We also show
that cryptographic notions of obfuscation, e.g., indistinghuishability and
virtual black box obfuscation, may not guarantee evasion detection under our
model. However, they can be used in conjunction with environmental keying to
produce hard to de-obfuscate version of programs.
