Malware analysis systems are one of the best weapons in the arsenal of cybersecurity companies and researchers. An integral part of such systems is a sandbox providing an instru-mented and isolated environment to run unknown artifacts and observe their behavior to identify potentially malicious actions. In order to avoid detection, attackers have developed numerous techniques to make analysis harder. One class of anti-analysis attacks is based on the observation that it is not only the sandbox that monitors the behavior of the runningprogram; the program itself can also monitor its surrounding environment to detect the presence of a sandbox and try to evade it. This is usually achieved by looking for artifacts sug-gesting that the execution environment is a sandbox, such as specific memory patterns, behavioral traits of certain CPUinstructions (known as red pills), or parallel running processes of known Virtual Machine (VM) vendors. To mitigate this threat, sophisticated sandboxes remove or spoof these signals, thus making it harder for a malware sample to detect the emulated environment. In this paper we devise a new evasion strategy based on Proof-of-Work (PoW) algorithms that show an asymptotic behavior, in terms of computational cost, when they run on some class of hardware platform. To this end such algorithms can be used to effectively detect virtualized environments (e.g., malware sandbox analysis). To prove the validity of this intuition, we design and implementScrambleSuit: a tool that is able to automatically implement such detection strategies and embed a test evasion program into an arbitrary malware sample. Evaluation results show that the proposed detection technique can evade the most popular public sandboxes.