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.