Side-Channel Attack on Substitution Blocks

We describe a side-channel attack on a substitution block, which is usually implemented as a table lookup operation. In particular, we have investigated smartcard implementations. The attack is based on the identifying equal intermediate results from power measurements while the actual values of these intermediates remain unknown. A powerful attack on substitution blocks can be mounted if the same table is used in multiple iterations and if cross-iteration comparisons are possible. Adversaries can use the method as a part of reverse engineering tools on secret algorithms. In addition to the described method, other methods have to be employed to completely restore the algorithm and its accompanying secret key. We have successfully used the method in a demonstration attack on a secret authentication and session-key generation algorithm implemented on SIM cards in GSM networks. The findings provide guidance for designing smartcard solutions that are secure against this kind of attack.