Linearly equivalent S-boxes and the division property
- PDF / 542,139 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 112 Downloads / 165 Views
Linearly equivalent S-boxes and the division property Baptiste Lambin1,2
· Patrick Derbez1 · Pierre-Alain Fouque1
Received: 24 February 2020 / Revised: 4 June 2020 / Accepted: 6 June 2020 © The Author(s) 2020
Abstract Division property is a cryptanalysis method that proves to be very efficient on block ciphers. Computer-aided techniques such as MILP have been widely and successfully used to study various cryptanalysis techniques, and it especially led to many new results for the division property. Nonetheless, we claim that the previous techniques do not consider the full search space. We show that even if the previous techniques fail to find a distinguisher based on the division property over a given function, we can potentially find a relevant distinguisher over a linearly equivalent function. We 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. As a result, we exhibit a new distinguisher over 10 rounds of RECTANGLE, while the previous best was over 9 rounds, and rule out such a distinguisher over more than 9 rounds of PRESENT. We also give some insight about the construction of an S-box to strengthen a block cipher against our technique. We prove that using an S-box satisfying a certain criterion is optimal in term of resistance against classical division property. Accordingly, we exhibit stronger variants of RECTANGLE and PRESENT, improving the resistance against division property based distinguishers by 2 rounds. Keywords Cryptanalysis · Division Property · RECTANGLE Mathematics Subject Classification 94A60
Communicated by P. Charpin. Baptiste Lambin was supported by the Direction Générale de l’Armement (Pôle de Recherche CYBER). Patrick Derbez was supported by the French Agence Nationale de la Recherche through the CryptAudit Project under Contract ANR-17-CE39-0003. Pierre-Alain Fouque was supported by the French Agence Nationale de la Recherche through the BRUTUS Project under Contract ANR-14-CE28-0015.
B
Baptiste Lambin [email protected] Patrick Derbez [email protected] Pierre-Alain Fouque [email protected]
1
Univ Rennes, CNRS, IRISA, Rennes, France
2
Present Address: Horst Görtz Institute for IT-Security, Ruhr-Universität Bochum, Bochum, Germany
123
B. Lambin et al.
1 Introduction Division property is a distinguishing property which was first presented by Todo at Eurocrypt’15 [15]. This cryptanalysis technique quickly became a hot topic in the community, especially since it led to the first theoretical attack against full MISTY1 [14]. This property can be seen as a generalization of integral and higher-order differential distinguishers. At Crypto’16, Boura et al. [4] provided a simpler formulation of the division property, especially for the construction of the division trails of S-boxes. Recently, division property was used to improve cube attacks and allowed to improve the best known results against several
Data Loading...
