Online malware scanners are one of the best weapons in the arsenal of cybersecurity companies and researchers. A fundamental part of such systems is the sandbox that provides an instrumented and isolated environment (virtualized or emulated) for any user to upload and run unknown artifacts and identify potentially malicious behaviors. The provided API and the wealth of information in the reports produced by these services have also helped attackers test the efficacy of numerous techniques to make malware hard to detect. The most common technique used by malware for evading the analysis system is to monitor the execution environment, detect the presence of any debugging artifacts, and hide its malicious behavior if needed. This is usually achieved by looking for signals suggesting that the execution environment does not belong to a native machine, such as specific memory patterns or behavioral traits of certain CPU instructions. In this paper, we show how an attacker can evade detection on such analysis services by incorporating a Proof-of-Work (PoW) algorithm into a malware sample. Specifically, we leverage the asymptotic behavior of the computational cost of PoW algorithms when they run on some classes of hardware platforms to effectively detect a non bare-metal environment of the malware sandbox analyzer. To prove the validity of this intuition, we design and implement Scramblesuit, a framework to automatically (i) implement sandbox detection strategies, and (ii) embed a test evasion program into an arbitrary malware sample. We perform a comprehensive evaluation of Scramblesuit across a wide range of: 1) COTS architectures (ARM, Apple M1, i9, i7 and Xeon), 2) malware families, and 3) online sandboxes (JoeSandbox, Sysinternals, C2AE, Zenbox, Dr.Web VX Cube, Tencent HABO, YOMI Hunter). Our empirical evaluation shows that a PoW-based evasion technique is hard to fingerprint, and reduces existing malware detection rate by a factor of 10. The only plausible counter-measure to Scramblesuit is to rely on bare-metal online malware scanners, which is unrealistic given they currently handle millions of daily submissions.