The need for software security in untrusted environments is ever increasing. White-box cryptography aims to ensure the security of cryptographic algorithms when the attacker has full access to their implementations. However, there is no secure white-box implementation of standard block ciphers such as DES and AES known to date: All published techniques have been practically broken. In this paper, we revisit white-box cryptography and propose a family of white-box secure block ciphers SPACE with several novel features. The design of SPACE is such that the key-extraction security in the white box reduces to the well-studied problem of key recovery for block ciphers (AES in our example) in the standard black-box setting. Moreover, to mitigate code lifting, we introduce the notion of space hardness. It measures the difficulty of compressing the white-box implementation of a cipher, and quantifies security against code lifting by the amount of code that needs to be extracted from the implementation by a white-box attacker to maintain its functionality. SPACE includes several variants with different white-box code sizes. Therefore, it is applicable to a wide range of environments and use cases. One of the variants called N-SPACE can be implemented with different code sizes while keeping the cipher itself unchanged. SPACE offers a high level of space hardness: It is difficult to find a compact but still functional representation of SPACE given its white-box implementation. This property has several useful consequences for applications. First, it gets more challenging for a DRM attacker (e.g. in a pay TV setting) to scale a code-lifting attack and to distribute the break. Moreover, this paves the way for mass-surveillance resistant cryptography: If a large proportion of users dedicates a significant part of their computers' storage (e.g. HDD) to white-box SPACE implementations, it will be much more complex or even infeasible for governmental agencies to deal with the keys of all users simultaneously due to the limited storage available, forcing them to focus on targeted attacks instead. This consequence is especially important given Snowden's revelations on the extent of the mass surveillance practice by NSA and GCHQ. Finally, the usage of SPACE ciphers can mitigate the damage of having malware in security-critical systems such as networks processing top-secret data: As those are typically insulated from the Internet, the capacity of the communication channel from inside to outside the system is often limited, making it infeasible for Trojans to transmit the necessary key material.
