Welcome to the resource topic for 2019/097
Title:
Linearly equivalent S-boxes and the Division Property
Authors: Patrick Derbez, Pierre-Alain Fouque, Baptiste Lambin
Abstract:Division property is a new cryptanalysis method introduced by Todo at Eurocrypt’15 that proves to be very efficient on block ciphers and stream ciphers. It can be viewed as a generalization or a more precise version of integral cryptanalysis, that allows to take into account bit properties. However, it is very cumbersome to study the propagation of a given division property through the layers of a block cipher. Fortunately, computer-aided techniques can be used to this end and many new results have been found. Nonetheless, we claim that the previous techniques do not consider the full search space. Indeed, we show that even if the previous techniques fail to find a distinguisher based on the division property over a given function E, we can find a distinguisher over a linearly equivalent function, i.e. over L_{out} \circ E \circ L_{in} with L_{out} and L_{in} being linear mappings, and such distinguisher is still relevant. We first show that the representation of the block cipher heavily influences the propagation of the division property, and exploiting this, we give an algorithm to efficiently search for such linear mappings L_{out} and L_{in}. As a result, we are able to exhibit a new distinguisher over 10 rounds of RECTANGLE, while the previous best known distinguisher was over 9 rounds. Our algorithm also allows us to rule out such distinguisher over strictly more than 9 rounds of PRESENT, which is the highest known number of rounds on which we can build an integral distinguisher. Finally, we also give some insight about the construction of an S-box to strengthen a block cipher against our technique. We first prove that if an S-box satisfies a certain criteria, then using this S-box is optimal in term of resistance against classical division property. According to this, we exhibit some stronger variants of RECTANGLE and PRESENT, on which the maximum number of rounds we can distinguish is 2 rounds lower than the original, thus more secure against division property.
ePrint: https://eprint.iacr.org/2019/097
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .