Improved cryptanalysis of an AES implementation
Ludo Tolhuizen · 2012
In [1], Chow et al. provide an implementation of AES as a series oflookups in key-dependenttables. The tables depend not only on a key,but also on randomly chosen permutations ofthe set of 8-bits bytes.The idea is that many pairs of keys and permutations may give riseto the same table, thus obfuscating the key. The cryptanalysis of Billet et al. [2] shows how to reconstruct the used byte permutations.The most time consuming part of their method deals with finding theused byte permutationup to an affine mapping; it has a time-complexity of at most 2^24, thus essentially cracking the given AES implementation. In this paper, we provide a variation on this part of the attack, reducing the time complexity even further, viz. to at most 2^14.