Time-Memory Trade-Offs for Side-Channel Resistant Implementations of Block Ciphers

Currently, the most efficient first-order masked implementations use the classical randomized table countermeasure, which induces a penalty factor of around 2-3 in execution time compared to an unmasked implementation. However, an S-box with n-bit input and m-bit output requires 2(n)m bit memory; for example, AES requires 256 bytes of RAM. Conversely, generic S-box computation method due to Rivain-Prouff requires almost no memory, but the penalty factor to achieve first-order resistance is roughly 30-35. Therefore, we suggest studying time-memory trade-offs for block-cipher implementations based on an adaptation of a table compression technique proposed by IBM. We use the similar approach to study time-memory trade-offs for second-order masked implementations as well. We show that for the case of AES, reasonably efficient implementations can be obtained with just 40 bytes of RAM in both the cases and hence they can be used in highly memory constrained devices.