A Table-based White-box AES Implementation With Non-linear Obfuscation

White-box cryptography is in fact a set of techniques for equivalent transformation, which converts conventional cryptographic algorithms into functionally equivalent alternatives which guarantee solid security under untrusted execution environments, i.e. white-box attack context. Its existence emanates from the pressing demand to design and implement strong cryptographic algorithms that are able to be deployed in white-box context. In such an environment, the attacker is presumed to be in possession of the hardware/software of the cryptographic algorithms, and furthermore have full access to its software implementation and full control over its execution platform.White-box cryptography aims at constructing software implementation behaving as“black box” even executed in white-box environment, making a white-box attacker impossible to gain additional advantages over a black-box attacker.Starting from 2002, as Chow et al. proposed the first white-box implementation for AES, lots of researchers have dedicated themselves into this field, presenting plenty of creative ideas as well as innovative approaches. However, most of their contributions, especially for those popular algorithm such as AES, are proved to be insecure.Therefore, the design of secure white-box implementations, which is not only challenging but promising, remains to be solved.This paper describes in detail a new table-based white-box AES implementation, which obtains a sound resistance against the BGE attack and De Mulder et al.’s cryptanalysis against Xiao-Lai scheme. The new scheme exploits larger key-dependent lookup tables nTMC – 16- to 32-bit mappings – to implement the composition of AddRoundKey,SubBytes and MixColumns. Each such table integrates two bytes of the round keys and is blended with random mixing bijections.Apart of the tables nTMC, 8- to 128-bit key-independent tables TSR are designed to implement the ShiftRows operation and cooperate with nTMC via a sophisticated three-dimensional binding form. The outputs of TSR are merged via the network of tables TXOR and TXOR3. Moreover, random non-linear encodings are applied to all types of tables for better obfuscation.We then analyse the performance of the new scheme and white-box security against different types of attack and measure two security metrics: the white-box diversity and ambiguity. From the perspective of performance, the new scheme consumes 28444 kB memory for each encryption/decryption procedure, with 7776 table lookups. While from the aspect of security, we get solid results from the calculation of both security metrics. We also believe that the new scheme can withstand the BGE attack due to the lack of the essential property: the unique linear dependency between the output pair(yi, yj). We further illustrate that the scheme can also resist the cryptanalysis of De Mulder et al. since(i) the non-linear encodings are introduced to every table to prevent from the application of “linear” equivalence algorithm and(ii) the well-defined binding method between nTMC and TSR is irreducible and enlarges the size of solution set from 28 to 224, resulting in the complexity of at least 264, which is satisfactory for applications.