Protecting White-Box AES with Dual Ciphers - Information Security and Cryptology-ICISC 2010 - page 279

et al. [11]. In [6], Bringer et al. showed how to improve the security of the trace-
able block cipher by adding some perturbations in its description. The perturba-
tion idea was exploited by the same authors to improve the white-box AES im-
plementation [7]. Indeed, Bringer et al. added perturbations to the global rounds
of AES in order to make its algebraic structure inaccessible. In this instance, the
constants of SubBytes operation are made non-standard and unknown to the

adversary.
In this paper, we propose to build upon Chow et al. ideas to create a version
of white-box AES that better resists to the Billet et al. attack. Our approach
changes the algebraic structure in each round of AES in addition to the mixing
bijections. The use of different algebraic structure for the same instance of an
iterative block cipher was already proposed in [3]. The intrinsic structure of
the block cipher used in [3] is however based on Matsumoto-Imai multivariate
scheme [13] that is different from that of AES. We propose a different method
that works with the AES building block structure and that improves the security
of the white-box implementation. Our modification concerns all the operations
that involve constants within one round (i.e. and

key schedule operations). Moreover, all the elements of a state as well as the
round subkeys are transformed in order to fit the modified structure in each
round.
Our solution relies on using the dual ciphers [2,15,5] and raises the complexity
of Billet et al. attack from 2 30 to 2 91 . The structure changes make the original
cipher more intricate for the adversary such that he has to repeat the attack of
Billet et al. for all possible combinations of dual ciphers. Although raising the
attack complexity to 2 91 operations does not provide theoretical security for a
128-bit AES decryption key, it is useful from a practical perspective. In addition
to providing the white-box AES with a protection against practical attacks, our
design implementation is comparable in time and space requirements to that of
Chow et al.
The rest of this paper is organized as follows. Section 2 describes the white-
box AES implementation proposed by Chow et al. In Section 3 we review the
Billet et al. attack as well as the generic attack proposed by Michiels et al. In
Section 4 our improvements to the white-box implementation are detailed, and
in Section 5 we propose an enhanced implementation that is better resistant
against the attacks. Finally, we conclude in Section 6.

,

InvSubBytes InvMixColumns

2 AES White-Box Implementation

For most cryptographic applications, a program is supplied with an AES decryp-
tion algorithm together with a decryption key. As the decryption key must be
kept secret and inaccessible to the user, the AES decryption algorithm (which
is different from the encryption algorithm) has, in some cases, to be white-box
implemented. This is for example the case when the application is expected to
runonanopenplatform.Inothercases,onemaywantthewhite-boximplemen-
tation to be backward compatible with a legacy implementation (non white-box)