Boomerang uniformity of popular S-box constructions
- PDF / 760,996 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 51 Downloads / 182 Views
Boomerang uniformity of popular S-box constructions Shizhu Tian1,2,3 · Christina Boura3,4
· Léo Perrin3
Received: 4 September 2019 / Revised: 19 June 2020 / Accepted: 28 July 2020 / Published online: 14 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In order to study the resistance of a block cipher against boomerang attacks, a tool called the Boomerang Connectivity Table (BCT) for S-boxes was recently introduced. Very little is known today about the properties of this table especially for bijective S-boxes defined for n variables with n ≡ 0 mod 4. In this work we study the boomerang uniformity of some popular constructions used for building large S-boxes, e.g. for eight variables, from smaller ones. We show that the BCTs of all the studied constructions have abnormally high values in some positions. This remark permits us in some cases to link the boomerang properties of an S-box with other well-known cryptanalytic techniques on such constructions while in other cases it leads to the discovery of new ones. A surprising outcome concerns notably the Feistel and MISTY networks. While these two structures are very similar, their boomerang uniformity can be very different. Indeed, we show that the boomerang uniformity of a Feistel network is always the worst one possible, while for a MISTY construction this quantity depends on its inner building blocks. In the second part, we investigate the boomerang uniformity under EA-equivalence for Gold and the inverse function (as used respectively in MPC-friendly ciphers and the AES) and we prove that the boomerang uniformity is EAinvariant in these cases. Finally, we present an algorithm for inverting a given BCT and provide experimental results on the size of the BCT-equivalence classes for some 4 and 8-bit S-boxes. Keywords BCT · S-box · Feistel · MISTY · Lai-Massey · Gold · 94A60
This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Coding and Cryptography 2019”.
B
Christina Boura [email protected] Shizhu Tian [email protected] Léo Perrin [email protected]
1
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China
2
School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
3
Inria, Paris, France
4
University of Versailles, Versailles, France
123
1960
S. Tian et al.
Mathematics Subject Classification 94A60
1 Introduction To evaluate the security level of a block cipher, cryptanalysts have designed multiple techniques that aim at searching for undesirable patterns. One such technique is the so-called differential cryptanalysis [3] which looks for pairs (a, b) of input and output differences such that E k (x ⊕ a) ⊕ E k (x) = b, where E k is (a round-reduced version of) the studied block cipher. Block ciphers—but also other symmetric primitives such as hash functions for example— are often built using the so-called S-boxes as the source of their non-linearity.
Data Loading...
