Paper 2019/097

Linearly equivalent S-boxes and the Division Property

Patrick Derbez, Pierre-Alain Fouque, and 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.

Note: Revision on April 16th 2019 : More details about the S-box criteria.