Title: New techniques and improved complexity analysis of impossible differential attacks
Abstract: Impossible differential cryptanalysis is a powerful attack against block ciphers introduced independently by Knudsen and Biham et al. The idea of these attacks is to exploit differentials that have zero probability to occur in order to eliminate some key candidates. In this talk we introduce new techniques and correct complexity analyses for impossible differential cryptanalysis. To begin with, we show how the key schedule of a cipher impacts an impossible differential attack and we provide a new formula for the time complexity analysis that takes this parameter into account. Further, we show, for the first time, that the technique of multiple differentials can be applied to impossible differential attacks. Then, we demonstrate how this technique can be combined in practice with multiple impossible differentials or with the so-called state-test technique. Implementation of the above techniques will be briefly discussed and applications on ciphers including AES-128, CRYPTON-128, ARIA-128, CLEFIA-128, Camellia-256 and LBlock will be shown. This is joint work with Virginie Lallemand, Maria Naya-Plasencia and Valentin Suder.