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\equiv 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 EA-invariant 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.
Similar content being viewed by others
References
Albrecht M.R., Grassi L., Rechberger C., Roy A., Tiessen T.: MiMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity. In: J.H. Cheon, T. Takagi (eds.) ASIACRYPT 2016, Part I, LNCS, vol. 10031, pp. 191–219. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_7
Banik S., Bogdanov A., Isobe T., Shibutani K., Hiwatari H., Akishita T., Regazzoni, .: Midori: A block cipher for low energy. In: T. Iwata, J.H. Cheon (eds.) ASIACRYPT 2015, Part II, LNCS, vol. 9453, pp. 411–436. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48800-3_17
Biham E., Shamir A.: Differential cryptanalysis of DES-like cryptosystems. J. Cryptol. 4(1), 3–72 (1991). https://doi.org/10.1007/BF00630563.
Biryukov A., Leurent G., Perrin L.: Cryptanalysis of Feistel networks with secret round functions. In: O. Dunkelman, L. Keliher (eds.) SAC 2015, LNCS, vol. 9566, pp. 102–121. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-319-31301-6_6
Biryukov A., Perrin L.: On reverse-engineering S-boxes with hidden design criteria or structure. In: R. Gennaro, M.J.B. Robshaw (eds.) CRYPTO 2015, Part I, LNCS, vol. 9215, pp. 116–140. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_6
Bluher A.W.: On x\({}^{\text{ q+1 }}\)+ax+b. Finite Fields Their Appl. 10(3), 285–305 (2004). https://doi.org/10.1016/j.ffa.2003.08.004.
Bonnetain X., Perrin L., Tian S.: Anomalies and Vector Space Search: Tools for S-Box Reverse-Engineering. Cryptology ePrint Archive, Report 2019/528 (2019). https://eprint.iacr.org/2019/528
Boura C., Canteaut A.: On the boomerang uniformity of cryptographic sboxes. IACR Trans. Symm. Cryptol. 2018(3), 290–310 (2018). https://doi.org/10.13154/tosc.v2018.i3.290-310.
Boura C., Canteaut A., Jean J., Suder V.: Two notions of differential equivalence on Sboxes. Des. Codes Cryptogr. 87(2–3), 185–202 (2019). https://doi.org/10.1007/s10623-018-0496-z.
Canteaut A., Duval S., Leurent G.: Construction of lightweight S-boxes using Feistel and MISTY structures. In: O. Dunkelman, L. Keliher (eds.) SAC 2015, LNCS, vol. 9566, pp. 373–393. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-319-31301-6_22
Cid C., Huang T., Peyrin T., Sasaki Y., Song L.: Boomerang connectivity table: a new cryptanalysis tool. In: J.B. Nielsen, V. Rijmen (eds.) EUROCRYPT 2018, Part II, LNCS, vol. 10821, pp. 683–714. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-319-78375-8_22
De Canniére C.: Analysis and Design of Symmetric Encryption Algorithms. PhD thesis, Katholieke Universiteit Leuven (2007)
Dunkelman O., Huang S.: Reconstructing an S-box from its difference distribution table. IACR Trans. Symmetric Cryptol. 2019(2), 193–217 (2019). https://doi.org/10.13154/tosc.v2019.i2.193-217.
ETSI/Sage: Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3. Document 4 : Design and Evaluation Report. Technical report, ETSI/Sage (2011). http://www.gsma.com/aboutus/wp-content/uploads/2014/12/EEA3_EIA3_Design_Evaluation_v2_0.pdf
Grosso V., Leurent G., Standaert F.X., Varici K.: LS-designs: Bitslice encryption for efficient masked software implementations. In: C. Cid, C. Rechberger (eds.) FSE 2014, LNCS, vol. 8540, pp. 18–37. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46706-0_2
Grosso V., Leurent G., Standaert F.X., Varici K., Anthony Journault F.D., Gaspar L., Kerckhof S.: SCREAM & iSCREAM Side-Channel Resistant Authenticated Encryption with Masking. Candidate for the CAESAR Competition. See also http://perso.uclouvain.be/fstandae/SCREAM/ (2014)
Karpman P., Grégoire B.: The LITTLUN S-box and the FLY block cipher. In: Lightweight Cryptography Workshop 2016, October 17–18 (informal proceedings). National Institute of Standards and Technology (2016)
Li K., Qu L., Sun B., Li C.: New results about the boomerang uniformity of permutation polynomials. Cryptology ePrint Archive, Report 2019/079 (2019). https://eprint.iacr.org/2019/079
Li Y., Wang M.: On EA-equivalence of certain permutations to power mappings. Des. Codes Cryptogr. 58(3), 259–269 (2011). https://doi.org/10.1007/s10623-010-9406-8.
Li Y., Wang M.: Permutation polynomials EA-equivalent to the inverse function over GF (2\({}^{\text{ n }}\)). Cryptogr. Commun. 3(3), 175–186 (2011). https://doi.org/10.1007/s12095-011-0045-3.
Matsui M.: New block encryption algorithm MISTY. In: E. Biham (ed.) FSE’97, LNCS, vol. 1267, pp. 54–68. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052334
Mesnager S., Tang C., Xiong M.: On the boomerang uniformity of (quadratic) permutations over f\({}_{\text{2 }{}^{\text{ n }}}\). CoRR (2019). arXiv:1903.00501
Perrin L.: Cryptanalysis, Reverse-Engineering and Design of Symmetric Cryptographic Algorithms. Ph.D. thesis, University of Luxembourg (2017). http://orbilu.uni.lu/handle/10993/31195
Vaudenay S., Junod P.: Device and method for encrypting and decrypting a block of data. United States Patent (20040247117), see also “Fox, a New Family of Block Ciphers” http://crypto.junod.info/sac04a.pdf (2004)
Wagner D.: The boomerang attack. In: L.R. Knudsen (ed.) FSE’99, LNCS, vol. 1636, pp. 156–170. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48519-8_12
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Coding and Cryptography 2019”.
A Proof of Proposition 6
A Proof of Proposition 6
We prove here the bounds provided in Proposition 6 for the two types of unbalanced MISTY network depicted in Fig. 5. We start by the network on the left.
Proof
Suppose that \(m<n\) and define the function
where \(F_1\) and \(F_3\) are permutations over \(\mathbb {F}_2^n\) and \(F_2\) is a permutation over \(\mathbb {F}_2^m\). This function is displayed at the left of Fig. 9. We denote the values of (x, y, z) after i rounds for both cases as \((\ell _i,m_i,r_i)\).
Begin with \((l_0,m_0,r_0)=(x,y,z)\in \mathbb {F}_2^{m}\times \mathbb {F}_2^{m}\times \mathbb {F}_2^{n-m}\). Then
Consider \(b=(b_1,b_2,b_3)\) with \(b_1=b_2\ne 0\) and \(b_3=0\), with \(b_1\) and \(b_2\) being m-bit values and \(b_3\) being an \((n-m)\)-bit value. By starting with \((l_3+b_1,m_3+b_1,r_3)\), we get
That is, for \(b=(b_1,b_1,0)\) with \(b_1\ne 0\in \mathbb {F}_2^m\),
Then, for \(a=(a_1,0,0),b=(b_1,b_1,0)\in \mathbb {F}_2^{m}\times \mathbb {F}_2^{m}\times \mathbb {F}_2^{n-m}\),
By definition, we deduce that \(\beta _S(a,b)=2^n\beta _{F_2}(a_1,b_1)\). Indeed, since for any \(x\in T\) where
we have \(F^{-1}_2(F_2(x+a_1)+b_1)=F^{-1}_2(F_2(x)+b_1)+a_1\), Eq. (15) becomes
Now, by choosing \(a_1,b_1\) such that \(\beta _{F_2}(a_1,b_1)=\beta _{F_2}\), it follows that \(\beta _S\ge 2^n\beta _{F_2} \). \(\square \)
Lemma 2
If \(F_1\) is an affine permutation then the unbalanced MISTY network on the left of Fig. 5 has the worst possible BCT.
Proof
Since \(F_1\) is affine, we can simplify the function \(S_b(x,y,z)\) as
By chosing \(a=(0,a_2,a_3)\in \mathbb {F}_2^{m}\times \mathbb {F}_2^{m}\times \mathbb {F}_2^{n-m}\) with \(a_2,a_3 \ne 0\), we get
which holds for any \((x,y,z)\in \mathbb {F}_2^{m}\times \mathbb {F}_2^{m}\times \mathbb {F}_2^{n-m}\). Therefore, \(\beta _S=2^{n+m}\).\(\square \)
We provide now the proof for the network depicted on the right of Fig. 5. The proof for this case is very similar to the previous one and we only provide it here for the sake of completeness.
Proof
Suppose that \(m<n\) and define the function
when \(F_1\) and \(F_3\) are permutations over \(\mathbb {F}_2^m\) and \(F_2\) is a permutation over \(\mathbb {F}_2^n\). This function is displayed on the rightside of Fig. 9. We denote the values of (x, y, z) after i rounds for both cases as \((\ell _i,m_i,r_i)\).
Begin with \((l_0,m_0,r_0)=(x,y,z)\in \mathbb {F}_2^{n-m}\times \mathbb {F}_2^{m}\times \mathbb {F}_2^{m}\). Then,
Consider \(b=(b_1,b_2,b_3)\) with \(b_1= 0\) and \(b_2 = b_3 \ne 0\), with \(b_1\) being an \((n-m)\)-bit value and \(b_2,b_3\) being m-bit values. Then, by beginning with \((l_3,m_3+b_2,r_3+b_2)\) we get
That is, for \(b=(0,b_2,b_2)\) with \(b_2\ne 0\in \mathbb {F}_2^m\),
Then, for \(a=(0,a_2,0)\), \(b=(0,b_2,b_2)\in \mathbb {F}_2^{n-m}\times \mathbb {F}_2^{m}\times \mathbb {F}_2^{m} \) with \(a_2, b_2 \ne 0\) we have
By definition, we deduce that \(\beta _S(a,b)=2^m\beta _{F_2}(0||a_2,0||b_2)\). Indeed, since for any \(x||y\in T\) where
\(F^{-1}_2\left( F_2(x||y+a_2)+(0||b_2)\right) =F^{-1}_2\left( F_2(x||y)+(0||b_2)\right) +0||a_2\), Eq. (16) becomes
Now, we choose \(a_2,b_2\) such that \(\beta _{F_2}(0||a_2,0||b_2)=\beta _{F_2|_{\mathbb {F}_2^m}}\). It follows that \(\beta _S\ge 2^m\beta _{F_2|_{\mathbb {F}_2^m}} \). \(\square \)
From the above lower bound, we may come up with the idea of constructing an S-box with boomerang uniformity equal to 4 by setting \(m=1\) and by choosing \(F_2\) to be an APN permutation. However, in this case, \(F_{1}\) would have to be an affine permutation as the only 1-bit permutations are \(x \mapsto x\) and \(x \mapsto x\oplus 1\). Lemma 2 can be adapted to this situation and yields the same conclusion: the boomerang uniformity of such a 3-round MISTY network is maximal. Hence, this approach cannot work.
Rights and permissions
About this article
Cite this article
Tian, S., Boura, C. & Perrin, L. Boomerang uniformity of popular S-box constructions. Des. Codes Cryptogr. 88, 1959–1989 (2020). https://doi.org/10.1007/s10623-020-00785-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-020-00785-0