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.