Paper 2018/095

Towards Fully Automated Analysis of Whiteboxes: Perfect Dimensionality Reduction for Perfect Leakage

Cees-Bart Breunesse, Ilya Kizhvatov, Ruben Muijrers, and Albert Spruyt

Abstract

Differential computation analysis (DCA) is a technique recently introduced by Bos et al. and Sanfelix et al. for key recovery from whitebox implementations of symmetric ciphers. It consists in applying the differential power analysis approach to software execution traces that are obtained by tracing the memory accesses of a whitebox application. While being very effective, DCA relies on analyst intuition to be efficient. In particular, memory range selection is needed to prevent software execution traces from becoming prohibitively long. Moreover, analyst failure to specify the relevant range lets the vulnerable whitebox implementation be evaluated as secure. We present a novel approach for dimensionality reduction of software execution traces, that takes a significant part of analyst intuition out of the loop. The approach exploits the lack of measurement noise in the traces and selects only the samples that are relevant for the key recovery. Our experiments with the published whitebox implementations show that the length of software execution traces can be automatically reduced to a few dozens of bits. This results in an attack speedup of several orders of magnitude, which in turn facilitates the use of more computationally intensive DCA flavours such as multiple leakage targets proposed by Klemsa. Our approach simplifies the methodology for whitebox analysis down to the tracing of a large default memory range, letting our dimensionality reduction techniques extract the relevant points for DCA, and run the attack on multiple leakage targets, excluding analyst errors and saving analysis time. It also provides quick insights in case of whitebox implementations with additional protection layers such as encodings, and can be used to identify the range for fault injection in differential fault analysis. We make our techniques available to the community as a part of a free/libre open-source side channel analysis toolkit. We believe they are a step forward for fully automated whitebox analysis tools.