by Joppe W. Bos and Wil Michiels (NXP)
Secure software implementations in the ‘white-box attack model’ (where the user can be the adversary) are being used to secure smart devices. At NXP we have created a new technique for security assessment which allows one to efficiently extract the secret key from all publicly available white-box implementations. This highlights the risk of using such solutions for certain use-cases in practice.
Owing to the widespread use of ‘smart’ devices, which allow users to access a large variety of ubiquitous services, these platforms have become a valuable target to compromise. There are various ways to protect cryptographic secret key material, which might be used to secure your mobile payment transactions, decrypt streaming media content, or protect your fare during transit. Solutions range from using unprotected software implementations to tamper-resistant hardware implementations. In order to support as many devices as possible, there has been a trend in the last couple of years towards using secure cryptographic software implementations.
Note, however, that in many realistic scenarios the user of the device might be the adversary. In the streaming content scenario, for instance, a user might want to give a friend access to his or her subscribed content. This adversary controls the platform where the software is being executed and this allows one to perform static analysis on the software, inspect and alter the memory used, and even alter intermediate results during execution. This security model is referred to as the white-box model, and a software implementation of a cryptographic algorithm which is secure in this model is called a white-box implementation. This model was introduced in . The idea is to use look-up tables rather than individual computational steps to implement the cryptographic algorithm. The usage of a fixed secret key is embedded in these tables that are filled with pseudo-random data.
A well-known attack on hardware implementations is to collect power traces: a collection of power measurements over time when executing the cryptographic implementation given known input. The statistical behaviour of a power trace might correlate to, and hence reveal information about, the secret key material used (see ). In order to assess the security of white-box implementations we applied this side-channel information paradigm to the software implementation setting. To collect information we have used freely available dynamic binary instrumentation tools. In such tools additional analysis code is added to the original code of the client program at run-time in order to aid memory debugging, memory leak detection, and profiling. This allows one to monitor, modify and insert instructions in a binary executable. We have developed plugins for these tools which can collect software traces: a trace which records the read and write accesses made to memory. These software traces are used to deduce information about the secret embedded in the look-up tables of a white-box implementation in the same way as this is done with power traces for hardware in differential power analysis techniques. This means that we correlate key guesses with the measurements in the software traces. We named this approach ‘differential computation analysis’ (DCA).
Figure 1: An example of a software trace where the enlarged part of the right shows the usage of the AES algorithm. Source: NXP.
We have demonstrated in  that DCA can be used to efficiently extract the secret key from all publicly available white-box implementations. In contrast to the current cryptanalytic methods to attack white-box implementations, this technique does not require any knowledge about the implementation strategy used, can be mounted without much technical cryptographic knowledge in an automated way, and extract the key significantly faster. We have created a tool which can visualize the traces (accesses to memory). Figure 1 shows an example of a software execution trace of a white-box implementation of the advanced encryption standard (AES). The virtual address space is represented on the x-axis while the y-axis is a temporal axis going from top to bottom. The entire execution is on the left while the enlarged part on the right shows 9 times 4 rows of instructions indicating the usage of AES: AES is a ten round block cipher where the last round differs slightly from the first nine. Once the target cryptographic cipher has been discovered with the help of this visualization tool, the embedded secret key can be extracted without any technical knowledge by collecting software traces and performing the statistical analysis in an automated fashion using our publicly available tools.
Although we could extract the secret keys from all publicly available white-box challenges we did not investigate the strength of commercially available white-box products since no company, as far as we are aware, has made a challenge publicly available. Unfortunately the well-studied countermeasures from the cryptographic hardware community do not directly apply since they rely on using randomly generated masks. In our security model an adversary can simply disable the entropy of the system rendering the random number generator mute. With this work we have highlighted the risks of relying on pure software implementation for certain use-cases and hope this security assessment will eventually increase the overall level of security for the end-users.
 S. Chow, P. A. Eisen, H. Johnson, P. C. van Oorschot: “White-box cryptography and an AES implementation”, in SAC 2002, LNCS vol. 2595, pp. 250-270, Springer.
 P. C. Kocher, J. Jaffe, B. Jun: “Differential power analysis”, in CRYPTO'99, LNCS vol. 1666, pp. 388-397, Springer.
 J. W. Bos, C. Hubain, W. Michiels, P. Teuwen: “Differential Computation Analysis: Hiding your White-Box Designs is Not Enough”, Cryptology ePrint Archive, Report 2015/260, IACR, 2015. Source code: https://github.com/SideChannelMarvels.
Joppe W. Bos
NXP Semiconductors, Belgium