| Ivica Nikolic |  |
 |
Date de l'exposé : 18 novembre 2011
Automatic search of related-key differential characteristics: Applicationsto AES and DES
The differential attack is one of the most widely used approaches in cryptanalysis of block ciphers and hash functions. It was used in the attacks on the two encryption standards DES and AES. To launch this attack, the cryptanalyst has to find a differential - an input difference for the cipher that propagates to output difference with a probability higher than in a pseudo-random permutation. The input difference can be only in the plaintext (single-key differential attack) or in both the plaintext and the key (related-key differential attack). The differential can be seen as a collection of differential characteristics - round-by-round differences that lead from the input difference to the output difference. The task of finding single-key differential characteristics usually is the most difficult part of the attack since these characteristics in most of the cases are found manually - an effort that requires days of inspecting the internal structure of the cipher. Moreover, the search of related-key characteristics is always by hand. We present algorithms for automatic search of related-key characteristics by efficiently eliminating the requirement for the full search of the brute-force space of characteristics. The elimination is achieved by counting the number of active S-boxes in each round of the cipher. In the cases of byte-oriented ciphers, a special internal representation of the ciphers additionally reduces the search complexity by reducing the branching. Our approach is applied to several block ciphers including DES and AES. We also show relation between the search problem and the problem of finding a path with minimal weight in a graph.
