On the Foundations of White-Box Cryptography

In the white-box attack scenario, we consider an adversary who gets access to the implementation code of a cryptographic algorithm with an embedded secret key. Additionally, the adversary is assumed to be in control of the execution environment of the implementation. White-box cryptography aims to maintain an implementation secure, even in the presence of such a strong adversary. In this thesis, we study the foundations of white-box cryptography, clarifying its security goals, studying its feasibility and studying the effectiveness of popular attacks on real life implementations. Towards this goal, we consider the use case of white-box cryptography for mobile payment applications and compare it with its more traditional use case in digital rights management. We start by studying security definitions previously suggested and explain why the properties captured by these definitions do not align with the security we wish to achieve for white-box crypto in the context of mobile payment applications. We then propose new security notions, focusing on confidentiality and integrity as basic security goals and hardware-binding as a means to mitigate code-lifting attacks. Following this line, we present security notions for a hardware-bound white-box key derivation function (WKDF), for hardware-binding for white-box encryption, and for a hardware-bound white-box payment scheme. We present feasibility results for our WKDF based on the assumption of puncturable pseudorandom functions (PPRF) and indistinguishability obfuscation. Our construction consists of a PPRF which we use for deriving keys and bind it to a pseudorandom function-like functionality which is used for verifying if the program is running on the intended device. Via obfuscation, we hide the secret keys used for key derivation and for verification and bind these two functionalities together. Based on our WKDF, we construct a mobile payment scheme, whose security is derived from the WKDF. Additionally, we construct an incompressible white-box encryption scheme based on the standard assumption of one-way permutations. Finally, we study the susceptibility of white-box implementations w.r.t. gray-box attacks, i.e. key extraction attacks adopted from side-channel analysis of hardware implementations. We focus on the differential computation analysis (DCA), which performs a statistical analysis on execution traces of white-box designs. We study the effectiveness of this attack and show that popular white-box design frameworks are too weak to protect against DCA. Our studies lead us to an improvement and generalization of this attack. We conclude this thesis by conducting a qualitative analysis on candidate implementations submitted to the 2017 WhiBox CTF Challenge. Our results highlight the importance of achieving resistance against gray-box attacks, as well as the importance of achieving the notion of hardware-binding in order to reduce adversarial capabilities in the real world.