International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Differential Trail Search in Cryptographic Primitives with Big-Circle Chi:: Application to Subterranean

Authors:
Alireza Mehrdad , Radboud University, Nijmegen, The Netherlands
Silvia Mella , Radboud University, Nijmegen, The Netherlands
Lorenzo Grassi , Radboud University, Nijmegen, The Netherlands
Joan Daemen , Radboud University, Nijmegen, The Netherlands
Download:
DOI: 10.46586/tosc.v2022.i2.253-288
URL: https://tosc.iacr.org/index.php/ToSC/article/view/9721
Search ePrint
Search Google
Abstract: Proving upper bounds for the expected differential probability (DP) of differential trails is a standard requirement when proposing a new symmetric primitive. In the case of cryptographic primitives with a bit-oriented round function, such as Keccak, Xoodoo and Subterranean, computer assistance is required in order to prove strong upper bounds on the probability of differential trails. The techniques described in the literature make use of the fact that the non-linear step of the round function is an S-box layer. In the case of Keccak and Xoodoo, the S-boxes are instances of the chi mapping operating on l-bit circles with l equal to 5 and 3 respectively. In that case the differential propagation properties of the non-linear layer can be evaluated efficiently by the use of pre-computed difference distribution tables.Subterranean 2.0 is a recently proposed cipher suite that has exceptionally good energy-efficiency when implemented in hardware (ASIC and FPGA). The non-linear step of its round function is also based on the chi mapping, but operating on an l = 257-bit circle, comprising all the state bits. This making the brute-force approach proposed and used for Keccak and Xoodoo infeasible to apply. Difference propagation through the chi mapping from input to output can be treated using linear algebra thanks to the fact that chi has algebraic degree 2. However, difference propagation from output to input is problematic for big-circle chi. In this paper, we tackle this problem, and present new techniques for the analysis of difference propagation for big-circle chi.We implemented these techniques in a dedicated program to perform differential trail search in Subterranean. Thanks to this, we confirm the maximum DP of 3-round trails found by the designers, we determine the maximum DP of 4-round trails and we improve the upper bounds for the DP of trails over 5, 6, 7 and 8 rounds.
BibTeX
@article{tosc-2022-32086,
  title={Differential Trail Search in Cryptographic Primitives with Big-Circle Chi:: Application to Subterranean},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universit├Ąt Bochum},
  volume={2022, Issue 2},
  pages={253-288},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/9721},
  doi={10.46586/tosc.v2022.i2.253-288},
  author={Alireza Mehrdad and Silvia Mella and Lorenzo Grassi and Joan Daemen},
  year=2022
}