Balanced Encoding of Near-Zero Correlation for an AES Implementation

Power consumption of a circuit can be exploited to recover the secret key of a cryptographic algorithm. This technique is known as power analysis, one of the well-known techniques of side-channel analysis. Many software countermeasures against power analysis present a time-space trade-off. Masking and shuffling come at cost of the execution time and the extreme use of run-time random number generators. Internally encoded implementations of block ciphers, on the other hand, require large memory space to store a set of lookup tables. While the internal encoding is widely used in white-box cryptography, it has a serious drawback. It cannot protect the secret key against power analysis. In this paper, we propose a secure internal encoding method of an AES implementation. Provided that the five inner rounds are left unprotected because these are not subject to power analysis, the lookup tables are approximately 232KB in size and the number of operation including XORs and table lookups are about 1,000 in total. This is about half the table size required by the white-box AES implementation, which is vulnerable to power analysis, and is about three times the amount of operations required by the straightforward AES implementation.


Introduction
In the gray-box model, software cryptographic implementations executed in untrusted environments can be attacked by exploiting side-channel information such as timing or power consumption. Such information is highly likely to expose a secret key, so an attacker can recover it from non-protected implementations without the effort of reverse engineering. Among many leakage sources of sidechannel information, the correlation to key-dependent intermediate values has been exploited by various attacks. For example, power analysis including Differential Power Analysis (DPA) [13] and Correlation Power Analysis (CPA) [8] analyzes the correlation between the power consumption of the target computation and the corresponding hypothetical values. The attacker queries the software implementation of a cryptographic primitive with arbitrary inputs and collects power traces through physical interaction with an oscilloscope. For every pair of the input and the subkey candidate to the target cryptographic function such as SubBytes, the attacker computes the hypothetical value. The correct candidate produces the correct hypothetical values which are strongly correlated to a particular point in the power traces because the power consumption is proportional (or inversely proportional) to the data processed in the circuit. Here, DPA divides the power traces into sets based on the hypothetical values and gets the average traces of each set. If the subkey candidate is correct, a differential trace then shows a noticeable peak at the points related to the target function. In the case of CPA, the subkey is simply guessed by calculating a correlation between hypotheses and each point in the traces.
The number of power traces required for successful power analysis depends primarily on the power model and electronic noise. A power model such as a bit model or a hamming weight model determines how to express the power consumption of the target function. On the other hand, electronic noise is partly generated in power measurement and is partly generated due to constant components such as leakage current and transistor switching [19]. Generally speaking, as the noise increases, the number of power traces required for key recovery increases. Recently, several studies [7,16,22] have defined another threat model of computational analysis, in which an attacker can access a source code or an executable of the target primitive. In this threat model, a computational trace can be collected by observing the computations in memory without electronic noise. Hence, the key-dependent intermediate values or the memory addresses pertaining to read and write access are clearly revealed.
Computational analysis was originally adapted by Differential Computation Analysis (DCA) [7], a non-invasive attack extracting the secret keys from a wide range of different white-box implementations [9,10] without having to perform a detailed reverse engineering of the target implementation. From the attacker's perspective, the noise-free computational traces have also contributed to DCAvariant attacks such as Zero difference enumeration [2], collision attacks, mutual information analysis [21], and bucketing attacks [27]. From the cryptographic engineer's perspective, on the other hand, the noise-free traces can be used to evaluate the protection of secret keys against power analysis with the reduced number of traces compared to classical power analysis and without an expensive oscilloscope.
The common software countermeasures reducing the problematic correlation are masking and operation shuffling. The basic idea of masking is to split every sensitive variable s into d + 1 shares s 0 , . . . s d such that s 0 • s 1 • . . . • s d = s, where a group operation • is the XOR ⊕ in most cases or is sometimes the modular addition. Here, any subset of less than d + 1 shares or leakage signals should be statistically independent of s. This is achieved by picking up the masks s 1 , . . . , s d uniformly at random and by setting the masked variable s 0 such that s 0 = s • s 1 • . . . • s d . Then d is called the masking order. Because the attack cost of higher-order DPA exploiting d + 1 leakages grows exponentially with the masking order [19], higher-order masking schemes can secure block-cipher implementations.
The disadvantage of higher-order masking is that it is not efficient when recomputing a new S-box S which blinds the input and the output with random masks. A second-order masked AES implementation takes more than 20 times the execution time compared to the first-order implementation [23]. Since the first-order masking can be broken by the second-order DPA with reasonable efforts, a practical approach for industrial practitioners is often to combine it with shuffling [12].
Shuffling randomizes the sequence of independent operations for each execution of encryption. This spreads the leakage point of a key-sensitive variable over t different points. Provided that the sequence is shuffled uniformly at random, then the signal-to-noise ratio of the instantaneous leakage on the sensitive variable is reduced by a factor of t. Shuffling is easy to implement and less costly than higher-order masking especially when applied to the S-box. However, the combination of first-order masking and shuffling is not sufficiently secure against advanced power analysis [25,26].
It is noteworthy that the higher-order DCA [5] is reminiscent of higher-order DPA attacks. This attack was developed to recover the secret key from the masked and shuffled implementation by using computational traces. In addition, an algebraic DCA attack [4] has been proposed to break the linear masking on the white-box implementation independently of the masking orders in the white-box setting. In order to resist both computational and algebraic attacks, a white-box masking scheme that combines linear and nonlinear components has been proposed [24]. However, this masking technique is a hardware-based countermeasure that is largely dependent on a run-time random number generator. In general, masking schemes are costly in terms of run time and often lead to the joint leakage. Although a masking technique can be customized into the precomputation tables of the white-box instances [15,16], it is also costly in terms of memory requirements.
In light of this, there is a clear need for a software-based and non-masking countermeasure against power analysis in the gray-box setting. By doing so, the software implementation of a block cipher in the low-cost device such as ID cards can effectively protect the secret key within limited resources. To achieve this goal, we revisit the internal encoding for the table-based AES implementation. The internal encoding was originally used in white-box cryptography to enhance the table diversity and ambiguity [9,10]. However, the high correlation that still remains in the encoded intermediate values is the main cause of the vulnerabilities of white-box cryptography to gray-box attacks [7,22]. This vulnerability has raised the need for balanced encoding methods.
In this paper, we primarily focus on finding the balanced encoding method. Above all, we customize an 8-bit linear transformation in such a way to eliminate the problematic correlation. Here we note that our linear transformation is designed to use not only nonsingular but also singular matrices. This improves on the table diversity and ambiguity. Because the linear transformation is unable to conceal zeros per se, the nonlinear transformation is partly used to hide zeros. When an AES algorithm is implemented by using our encoding method, the key can be protected from power analysis. The proposed AES implementation requires approximately 232KB of memory space for lookup tables and 1,000 operations including XORs and table lookups. Importantly, it is not dependent on masking techniques and run-time random sources in the device.
The rest of the paper is organized as follows: Section 2 explains the basic concepts of power analysis and the existing method of the internal encoding. In Section 3, we propose our encoding method. In Section 4, we introduce our AES implementation protected by the balanced encoding and analyze its performance and cost. Section 5 shows the experimental results on calculating the correlation between the lookup values and the hypothetical values. Section 6 summarizes this paper.

Preliminaries
In this section, we first introduce the well-known techniques of power analysis, which is still one of the most prevalent ways for extracting secret keys from IC cards. Using oscilloscopes in power analysis requires a large number of power traces because the key-dependent information in the trace is not clear due to the measurement noise. However, given the source code or executable of the target cipher, collecting computational traces from memory is more practical than collecting power traces. It is important to notice that if the key is not extracted from noise-free computational traces, it can be determined that the key is secure against power analysis. To demonstrate the security of the proposed AES implementation, we conduct experiments using computational traces in Section 5. Therefore, we explain methods used to measure correlation in the experiments. Lastly, we briefly demonstrate the key leakage caused by the problematic correlation in the existing method of internal encoding adapted to white-box cryptography.

Power Analysis
Power analysis is a non-invasive attack to extract the key from low-cost devices such as IC cards. In the gray-box model of power analysis, an attacker can select a plaintext and access the ciphertext. The attacker can also collect timing or power consumption information related to the encryption operation. However, it is not possible to access the internal resources of the computing environment to observe or manipulate memory. Power consumption of IC cards is proportional (or inversely proportional) to the Hamming weight (HW) of data processed in the circuit [19]. Suppose that an attacker knows a correct subkey of the AES algorithm. For a target operation like SubBytes, power consumption of a circuit is then strongly correlated to the attacker's hypothetical value at a point of power traces. The following explains two fundamental techniques of power analysis, Differential power analysis (DPA) and Correlation power analysis (CPA).
DPA is a statistical method for analyzing power consumption. A selection function D(b, C, k * ) is defined to compute a key-sensitive variable b, where C is a ciphertext and k * is a subkey candidate. If k * is a wrong key candidate, D will evaluate b correctly with a 1/2 probability. DPA records N power traces V 1..N [1.
.κ] consisting of κ points. Then the differential trace ∆ D [j], where j ∈ [1, κ], is generated by computing the difference between the average of traces for D(·) = 1 and D(·) = 0 as follows: , a sample point in the trace. That point indicates power consumption of computing b. For this reason, a correct subkey will result in a noticeable peak in the differential trace, but it is unlikely that the wrong key candidate will produce a spike.
CPA improves on DPA by taking advantage of leakage models such as the HW. For K different key candidates, let h n,k * be the hypothetical value for the power estimation, where n ∈ [1, N ], and k * [0, K). A correlation between hypothetical values and power traces can be obtained by the estimator r as follows [19]: where h * k and V [j] are the sample means of h * k and V [j], respectively. Like in the case of DPA, a correct subkey makes a noticeable spike in the correlation plot.
As mentioned previously, each point of a power trace is also affected by electronic noise of power measurement as well as constant components such as leakage currents and transistor switching. The noise has a significant impact on the number of power traces needed to recover the key. However, it is not necessary to collect power traces if the source code or execution binary is available. In this threat model, Differential computation analysis (DCA) [7] collects noise-free computational traces consisting of read-write data or memory addresses accessed by the software. Since the collected information has no noise, the computational traces make CPA successful with fewer traces. In order to collect computational traces during the encryption, dynamic binary instrumentation (DBI) tools including Pin [18] and Valgrind [20] can be adapted.
Walsh transform can also quantify a correlation using only simple XOR and addition if the intermediate values or computational traces can be collected [22]. To evaluate the security of software cryptographic implementations, the Walsh transform can be inserted in the source code to calculate the correlation without having to use DBI tools. By doing so, scanning every sample point of the traces is not necessary. Compared to Pearson correlation coefficients, the Walsh transform consists of lightweight operations and shows the correlation as a natural number. Definition 1. Let x = x 1 , . . ., x n , ω = ω 1 , . . ., ω n be elements of {0, 1} n and x·ω = x 1 ω 1 ⊕. . .⊕x n ω n . Let f (x) be a Boolean function of n variables. Then the Walsh transform of the function f (x) is a real valued function over {0, 1} n that can be defined as

High Correlation in the Existing Encoding Method
So far, the internal encoding consisting of linear and nonlinear transformations has been applied to white-box cryptographic implementations for block ciphers in order to obfuscate key-dependent intermediate values. Unfortunately, the current encoding method cannot hide the keys completely from power analysis [1,14]. First, the linear combinations of intermediate values are highly correlated with the intermediate values due to the key-dependent distribution. For example, suppose that an 8-bit linear transformation is applied to 3 · x, where x is the SubBytes output. Then the linear combination of the first to fifth bits of 3 · x is always correlated to the first bit of x. Second, the two 4-bit concatenated nonlinear transformations show a limited confusion effect on 8-bit values.
Let f i (·) denote the encoding on the MixColumns multiplication in the first round of a white-box implementation of an AES-128 algorithm (WB-AES) [9]. To be specific, the MixColumns multiplication is performed between the SubBytes output and the first column of MixColumn matrix. Given the SubBytes output x, f i∈[0,31] (x) is an encoded 32-bit value of MixColumns multiplication. Fig. 1 illustrates the Walsh transform with ω = 8. Although the correct subkey has W f i = 0 at 30 bits out of 32 bits, the 6th and the 7th bits of f (·) are highly correlated to the 4th LSB of x. Their Walsh transform scores are 128. In contrary, the average of |W f i | of the wrong key candidates was 13.07 (max = 52 and s.d = 9.44). This gives us that the subkey can be recovered by power analysis with an overwhelming probability.
Previously, the classical and customized masking techniques have been proposed to solve this problem of the internal encoding [5,15,16] masking is however expensive in terms of computational costs and is not secure against higher-order DPA attacks. On the other hand, the customized masking requires tens of megabytes for lookup tables, which cannot be stored in a low-cost device. To address this problem, we propose a non-masking encoding method that takes up less memory space for an AES-128 algorithm.

Proposed Encoding
Before going into depth on our balanced encoding, let's start by explaining the imbalances in the existing 8-bit linear transformation of a white-box AES implementation. For x ∈ GF(2 8 ), let S (x) denote the SubBytes output multiplied by ∈ {1, 2, 3}, the elements in the MixColumns matrix. Here, S (x, y) refers to the y-th bit of S (x), where y ∈ [1,8] (the MSB is the first bit). The following matrix S is defined as An asterisk often refers to either a row or a column. For example, S i, * refers to the i-th row, and S * ,j refers to the j-th column of S . If M i,j is an 8 × 8 binary invertible matrix, an 8-bit linear transformation with S is given by R = M ·S . Each row in R i, * is then computed by the XOR operations between the selected rows in S ; if M i,j = 1, S j, * is XORed to compute R i, * By Definition 2, for random integers i, i ∈ [1,8] and , ∈ [1,3], the balanced linear transformation must satisfy the Walsh transform as follows: In other words, this implies HW(R i, * ⊕ S i , * ) = 128. As pointed out in [14], the key-dependent distribution of S , however, leads to HW(R i, * ⊕ S i , * ) = 0, which results in the Walsh transform value 256, with an overwhelming probability. Table 1 lists V and W, the row index of S and the sets of the row indexes of S , respectively, producing the Walsh transform value of 256 for each pair of ( , ). The first row of the table means that if = , the Walsh transform value would be 256 only if the j-th row from S and S was selected, where j ∈ [1,8]. For ( , ) = (2, 1), for example, suppose that R 2 contains a row computed by a linear combination of the 7-and 8-th rows of S 2 . This row is then identical to the 8th bit of S 1 . In other words, this linear transformation is unable to protect R 2 from an attacker calculating a correlation using the 8th bit of S 1 .
Considering AddRoundKey performed before SubBytes, a subkey k will be added to the input x of S(·). Here, it is easy to know that S(x ⊕ k) can by expressed by a permutation of columns in S and S . Thus, the same row indexes listed in Table 1 will lead to the same results even after k is added to x.

Basic Idea
Overall, our encoding protects a byte using a customized 8-bit linear transformation and a simple nibble encoding. To be balanced, the linear transformation must generate a matrix M that does not contain the row indexes listed in Table 1. Previously, the linear transformation has adapted only invertible matrices to guarantee its inverse transformation. However, using only binary invertible matrices, after excluding those row indexes, reduces the table diversity. To solve this problem, our linear transformation is designed to adapt singular matrices as well as nonsingular ones. It is noteworthy that this proposed linear transformation is capable of decoding, i.e., inverse transformation, even though both singular and nonsingular matrices are utilized. The following explains the proposed 8-bit linear transformation consisting of 4-bit transformations. In addition, the 4-bit nonlinear transformations, often called the nibble encoding, are partly used to hide the value of 0.
Notation. For 8-bit binary vectors X, Y, Z, the superscripts H and L represent their upper 4 bits and lower 4 bits, respectively. Thus, X = X H ||X L . The encoding is denoted by E, consisting of the linear and nonlinear transformations, denoted by L and N , respectively. By abuse of notation, N H denotes the nibble encoding for the upper 4 bits whereas N L denotes for the lower 4 bits of the input. The subscripts to N are used to indicate different nibble encodings. The decoding is denoted by D. Let denote two sets of 4 × 4 binary matrices by F  and G, which are chosen under the certain conditions explained in the following. f $ ← − F means a random sampling from F. Idx (v) is defined to be a function:

Balanced Linear Transformation
Suppose f and g are the elements randomly chosen from F and G, respectively. For an 8-bit vector X = X H ||X L , the proposed linear transformation Z = L(X, f, g) is defined as follows: where · implies multiplication. This can be represented by M · X, using an 8×8 matrix M defined as follows: During the computation of L, if M * ,i =1, the i-th row of X is to be XORed. The balance can be achieved by using binary vectors f i, * that are not listed in Table 1, where i ∈ [1,4]. Let B F i denote the blacklist, i.e., the set of binary vectors that must not appear to the i-th row of f ∈ F. There exist 27,000 Table 1. Our exhaustive search found that a total of 1,098,661,500 (> 2 30 ) pairs of (g, f ) satisfies In other words, our linear transformation guarantees the table diversity consisting of more than 2 30 pairs of (g, f ) producing the Walsh transform value of 0. For each f , the average numbers of row vectors at g 1, * , g 2, * , g 3, * , and g 4, * are approximately 14, 13.6, 14.2, and 14.6, respectively.
For four 8-bit values X 1 , X 2 , X 3 , and X 4 , let Y and Z stand for the followings: Then, the inverse of the linear transformation is accomplished by Y = L −1 (Z, f, g): Then, it is easy to see that S can be considered a permutation of columns in S . Without loss of generality, R = M · S. If Equation 1 is true, then It also implies that HW(R i, * ⊕ S i , * ) = 128. This gives us that the protection of L on MixColumns does not produce intermediate values which are highly correlated to the correct hypothetical value of it.

Nibble Encoding for Hiding Zeros
Because of the balance provided by L, all intermediate values have no problematic correlation to the correct hypothetical values before applying nibble encodings. For this reason, the use of nibble encoding is restricted to hide the value of 0, which cannot be hidden by multiplication. Simply speaking, each nibble encoding swaps the value 0 with e ∈ [0, 0xF ], whereas the other values remains the same. The focus is on finding a candidate e, keeping the balance in the encoding. Fig. 2 shows graphical representation of two nibble encodings applied to R . In the upper and lower 4 bits, every four-bit chunk from 0 to 0xF appears exactly 16 times because of the balance by L. Let denote two candidates to be swapped in the upper and the lower four bits by e H and e L , respectively. In other words, the upper (resp. the lower) nibble encoding performs 16 swaps between 0 and e H (resp. e L ). Let J H 0 be a set of column indices with the upper four bits of R equal to zero, and let J H e be a set of column indices with the upper four bits equal to e as follows: For the upper 4-bit nibble encoding N H , a candidate e H must satisfy the following conditions to provide the first-order balanced encoding: Here, it is worthy noting that the balance must be investigated for all ∈ {1,2,3} since a single matrix M will be used to protect S 1 , S 2 , and S 3 (see Section 4). Similarly, we define J L 0 ={j|R 5,j ||R 6,j ||R 7,j ||R 8,j = 0} J L e ={j |R 5,j ||R 6,j ||R 7,j ||R 8,j = e} For the lower 4-bit nibble encoding N L , a candidate e L must satisfy the following conditions: A more graphical way of representing the implication is illustrated in Fig. 3. 0 can be swapped with e H if the HW of every column in J H 0 and J H e are the same for each row of S . Also, e L can be found in the same manner using column indices belonging to J L 0 and J L e . By using 100 different pairs of (f, g), R ∈{1,2,3} was constructed and was then encoded by a pair of nibble encodings. We found that an average of 12

Protected AES-128
From now on, we describe a secure design of AES with a 128-bit key protected by our balanced encoding. Overall, this is inspired by a white-box cryptographic implementation of AES [9], which is mainly composed of a series of internally encoded lookup tables. Our focus is, however, on protecting against DPA-like attacks which take advantage of correlation to the key-dependent intermediate values.
In other words, the rest of gray-and white-box attacks such as cryptanalysis and fault injection are not taken into account. Thus, the proposed structure is not as heavyweight as a white-box implementation.

Threat Model
We clarify the threat model as follows. Above all, an attacker has no access to the internal computing resource in the device. This non-invasive attacker can obtain the input and output of encryption and can collect power traces. When conducting power analysis, the target hypothetical values against the table-based implementation of AES are one of the followings. First, the most common hypothetical value is the output of MixColumns multiplication. More specifically, it is the result of multiplication of the SubBytes output with one of the three coefficients in the MixColumns matrix. Second, the partial or three XOR operations between four bytes from MixColumns multiplication can be attacked. Here we note that the three XORs compute a subbyte of the round output.
Ironically, the low correlation provided by the proposed encoding increases the probability that the lowest-ranked key is the correct key as a result of power analysis. To solve this problem, we explain a method of deliberately raising the ranking of correct subkeys in the power analysis results.

Design
The following describes a rearrangement of AES-128 by which a series of lookup tables is generated. By shifting the initial AddRoundKey into the first round and by applying ShiftRows to the round key (except the final round key), AES-128 can be described concisely as follows: state ← plaintext for r = 1 · · · 9 ShiftRows(state) AddRoundKey(state,k r−1 ) SubBytes(state) MixColumns(state) ShiftRows(state) AddRoundKey (state,k 9 ) SubBytes(state) AddRoundKey(state, k 10 ) ciphertext ← state, where k r is a 4 × 4 matrix of the r-th round key, andk r is the result of applying ShiftRows to k r . By doing so, AddRoundKey can combine with SubBytes before multiplying each column of the MixColumns matrix for the first -ninth rounds.
Let T-boxes be an 8×8 lookup table defined as where j is the column index of the vector. The next step is to make a composition U • T , say U T , mapping each subbyte of the plaintext to the MixColumns multiplication. Because the first key-dependent intermediate value, after running encryption, is exposed by looking up the U T table, its output must be encoded. Let denote them by In order to apply L on the four bytes of a column vector above, four sets of (f, g) are required; therefore each round uses 16 sets in total. The subscripts j,k are used to index a set pertaining to L, where j is a column index and k ∈ {1, 2, 3, 4}. y i,k is then encoded by L j,k (y i,k , f j,k , g j,k ). The structure of lookup tables precomputing the operations up to the MixColumns multiplication are simply depicted in Fig. 4. Note that the second round begins with the decoding of the first round output whereas the first round does not have to decode the plaintext. Through out this paper, we assume that the nibble encoding (blank squares in Fig. 4) is always applied to every boundary of lookup tables.   can be placed in a 4×4×4 array. The next step is to combine the encoded results of MixColumns multiplication into the round output by conducting XOR operations. Since the nibble encoding swaps zeros with unknown values, every XOR operation depicted by ⊕ in Fig. 5 must be performed by looking up the XOR tables, denoted by T x . An instance of T x is generated by using three nibble encodings to decode two 4-bit inputs and to encode a 4-bit output. Due to the distributive property of multiplication over XOR, L does not have to be decoded in this process. The final round does not involve MixColumns, and thus T 10 is not composed with U . Because its outputs make a ciphertext, T 10 does not encode the output. Let Q 0 denote the set of tables above, protected by the proposed encoding. As previously pointed out, we need another set of lookup tables, say Q 1 , so that the correct key does not show the lowest correlation as a result of power analysis. Here, Q 1 is simply generated by flipping the input and output bits of Q 0 . By doing so, Q 1 can also provide the balanced encoding on the encryption of a plaintext. In order to effectively protect the key from power analysis, the balance must be broken to some extent. So, a plaintext is encrypted by using Q 0 with probability α and by using Q 1 with probability 1 − α. Let {b 1 , b 2 · · · b n } be a sequence of binary numbers where b i = 0 or 1 such that If a random number generator is available in the device, each encryption begins by picking up i ∈ [1, n] at random and encrypts a plaintext using Q bi . If α = 1/2, a binary number, say b, may be simply generated to choose Q b . In this case, this is the only operation that the encryption depends on the run-time random number generator. Otherwise, based on the fact that power analysis uses uniformlydistributed plaintexts, i can be derived from plaintexts. For example, if n is unknown and less than 256, an XOR sum of every subbyte of the plaintext (mod n) can be used to choose i. By doing so, the encryption becomes independent of run-time random sources.

Costs
From the 1st to 2nd rounds, the size and the number of lookups of the table are only half compared to a white-box AES implementation [9]. This is because we do not protect the intermediate values by a 32-bit linear transformation which is replaced with four 8-bit transformations. Only the first and the last two MixColumns are protected against the non-invasive power analysis, and thus the proposed encoding is applied to those five outer rounds. During the encryption operation, one byte must pass through two MixColumns to be affected by all the bits in the key. For the inner rounds (from the 3rd to the 7th rounds) a straightforward AES implementation is adapted. Table 3 shows the table size of the number of lookups for the outer rounds. Here, the additional memory consumption including the S-box and the rest of round keys required for the inner-round operations is negligible and therefore gives approximately 116KB of the table size. Because the size of Q 0 and Q 1 are the same, the total size is about 232KB. In addition, approximately 400 operations including lookups and XORs are required for the inner rounds and thus about 1,000 operations are needed in total. Simply put, the additional cost for applying the proposed encoding is mainly imposed by the lookup tables of the protected rounds. From the practical point of view, each execution of encryption does not need to generate random numbers and a new set of masked tables.

Experimental Results
Our experiments can be divided into two parts. First, we demonstrate the balanced encoding using only Q 0 . To that end, the UT outputs and the round outputs were analyzed. We measured how much they correlate with the correct hypothetical values through the Walsh transforms and the DCA attacks. Second, we show that there is an increase in the correlation coefficients when using either Q 0 or Q 1 with a 1/2 probability. As mentioned before, it has the same effect as the increase in encoding imbalance. By doing so, the correct subkey does not lead to the lowest correlation.

Analysis of the UT Outputs
To demonstrate the effect of the balanced encoding on the UT outputs, we provide the following experimental results. First, the correlation of the UT outputs to the hypothetical values was investigated in the first round. Specifically, the hypothetical values guess the results of MixColumns multiplication, i.e., the Sub-Bytes outputs multiplied by 1, 2, or 3. In the following, we take a close look at U T 1 0,0 , a slice of the UT table mapping the first subbyte of a plaintext to the MixColumns multiplication in the first round. The Walsh transforms W t is defined: Here, W t tells us how much the lookup values of U T 1 0,0 and the hypothetical SubBytes output multiplied by ∈ {1, 2, 3} are correlated. For every single bit of the correct hypothetical values, all of the Walsh transforms give 0 as a result of the balanced encoding as shown in Fig. 10 -Fig. 12 in Appendix A. Fig. 6 shows a small part of the results obtained by the hypothetical values -the first bit of the SubBytes output multiplied by 1, 2, and 3. This balanced encoding has an influence on the result of DCA attacks using the hypothetical SubBytes output. In order to illustrate it, 10,000 computational traces of encryption using 10,000 random plaintexts were collected by using Valgrind. Table 4 shows the DCA result based on the SubBytes output. All correct subkeys ranked the lowest out of eight attacks at least once. Table 5 compares the highest correlation coefficient from all key candidates and the coefficient from the correct key. When the computational traces are composed of only the UT outputs, the DCA results and the corresponding correlation coefficients are shown in Table 10 and Table 11 in Appendix B, respectively. This shows the proposed encoding addresses the correlation problem caused by the existing encoding method. These two experiments were carried out to show there is no problematic correlation between the encoded lookup values and the correct values of S ∈{1,2,3} . Table 4: DCA ranking on the AES encryption using only Q 0 when conducting mono-bit CPA on the SubBytes output with 10,000 computational traces.``````T   166 0.163 0.164 0.159 0.155 0.170 0.154 0.155 0.156 0.166 0.165 0.160 0.170 0.160 0.156 0.158 With α = 1/2, the probability that a plaintext is encrypted with Q 0 or Q 1 is the same. The next experiments are almost the same with the previous ones, except that Q 0 and Q 1 were selected with a 1/2 probability for each encryption.
In other words, the Walsh transforms were calculated by using the UT lookup values from Q 0 and Q 1 . All of the results are provided in Fig. 14 -Fig. 16 in Appendix A, and Fig. 7 shows one of them. The hypothetical value was, like in the case of the previous experiments, the first bit of the SubBytes output multiplied by 1, 2, and 3. There was an increase in the encoding imbalance by which the correct subkey does not lead to the lowest correlation to the correct hypothetical values. The encoding imbalance shown in the results of the Walsh transforms above improves the protection of keys against DCA attacks searching for either the highest-or lowest-ranking subkey candidate. While the correct subkeys are in the lowest rank in Table 4, those are not in the highest or lowest ranks as shown in Table 6 when a plaintext was encrypted by looking up Q 0 or Q 1 with a 1/2 probability. Compared to Table 5, the gap between correlation coefficients computed by the correct and wrong subkeys are reduced as shown in Table 7.

Analysis of the Round Outputs
The encoded round output of the first round was analyzed so that the balance in the encoding applied to the round output can be investigated. Let p1 and p2   denote the first two byte of the plaintexts. When the remaining 14 bytes are fixed to 0, the first byte of the first round output can be expressed as follows.
where c is a constant. For simplicity, represents the encoding applied to δ. Then, the first subbyte of the first round output protected by the proposed encoding can be written by • δ(p1, p2). If we assume that the attacker knowsk 0 0,0 , the corresponding hypothetical value is given by where k * is the key candidates. Let the subscripts i and i denote the i-and i -th bits, respectively. For a fixed p1 and the correct key candidate, by Equation (2), we expect Thus, the Walsh transform W γ is defined: To see the effect of the balance in the encoded round output, we calculated W γ for all i, i ∈ [1,8]. As a result, the correct subkey always produced zeros on the Walsh transforms as illustrated in Fig. 13 in Appendix A, and Fig. 8 shows one of the results in the case of i = 1. Only the correct subkey (0x55) scores 0 for all i ∈ [1,8]. We also collected 10,000 computational traces while performing encryption using plaintexts consisting of the first two random bytes (p1, p2) followed by the 14 zeros. Assuming that the first subkeyk 0 0,0 is known, we mounted a customized DCA attack to recover the second subkeyk 0 1,0 . Table 8 shows the result. It is noteworthy that the DCA ranking of the correct subkey is relatively high compared to Table 4 because there is a decrease in the correlation coefficients computed by each of all key candidates. For this reason, the round output protected by the proposed encoding is not an attractive attack target for power analysis. The Walsh transforms and the DCA results with respect to the round outputs obtained by looking up Q 0 and Q 1 with a 1/2 probability are provided in Fig. 9 and Table 9, respectively. There is no noticeable point of key leakage. These experimental results give us the following. The proposed encoding has the effect of extremely lowering the problematic correlation to the correct hypothetical intermediate value. However, due to this fact, a variant of power analysis can find the subkeys that lead to the lowest correlation on the UT output. If a plaintext is encrypted by either Q 0 and Q 1 with a 1/2 probability, it is possible to counteract the variant of power analysis in advance.   operations quickly. In this paper, we improved on the internal encoding of the table-based AES implementation in such a way to protect the key hidden in the tables from power analysis as well as simple memory observation. Since our proposed encoding is perfectly balanced, power analysis attackers may guess the key which leads to the lowest correlation to the correct hypothetical values. To solve this problem, we suggested to generate the complement of the balanced tables and use it to encrypt a plaintext with a 1/2 probability. Meanwhile, our scheme requires only 232KB in the memory space and 1,000 operations including XORs and lookups. It is also noteworthy that it does not rely on run-time random number generators.
As future work, we remark that it seems possible to combine our implementation with countermeasures of fault attacks [3,6,11]. In particular, our table-based implementation is easy to combine with a table redundancy method for protecting fault attacks [17]. By doing so, we can defend against power analysis and fault attacks at the same time with only a few hundred kilobytes of memory space. Since a table redundancy method is also not dependent on a run-time random source, a combination of both techniques seem to be reasonable for lowcost devices. Note, however, that the proposed implementation is secure under the gray-box model. In other words, the key would lead to the lowest correlation if a white-box attacker could manipulate the execution flow so that either table of Q 0 or Q 1 is always selected.

A The experimental results of the Walsh Transforms
All of the Walsh transform results explained in Section 5 are provided. First, Fig. 10 -Fig. 12 show W t1 -W t3 , respectively, using only Q 0 . Next, Fig. 13 depicts W γ . Every Walsh transform with respect to the correct subkeys and Q 0 results in the value of 0. In contrary, Fig. 14 -Fig. 16 illustrate W t1 -W t3 , respectively, with an increase in the encoding imbalance when using Q 0 and Q 1 . Fig. 17 also demonstrate it with respect to W γ .
B The experimental results of the DCA attacks on the UT outputs Table 4 and Table 5 in Section 5 show the results of DCA using the computational traces that contain every computation in the encryption. For this reason, the DCA ranking of the correct subkey was not always the lowest. To show the effectiveness of our balanced encoding in more detail, we would like to provide DCA results using the 10,000 computational traces consisting of only the UT output values. This will help us understand more accurately how the Walsh transform score 0 for the UT output appears in the correlation coefficients. As shown in Table 10, all correct subkeys were ranked lowest in all cases as a result of the DCA attacks. In this regard, it can be seen that the correlation coefficients calculated by the correct subkeys shown in Table 11 is much lower than the coefficients provided in Table 5.