International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Proving Resistance Against Infinitely Long Subspace Trails: How to Choose the Linear Layer

Authors:
Lorenzo Grassi , Digital Security Group, Radboud University, Nijmegen, Netherlands
Christian Rechberger , Institute of Applied Information Processing and Communications (IAIK), Graz University of Technology, Graz, Austria
Markus Schofnegger , Institute of Applied Information Processing and Communications (IAIK), Graz University of Technology, Graz, Austria
Download:
DOI: 10.46586/tosc.v2021.i2.314-352
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8913
Search ePrint
Search Google
Abstract: Designing cryptographic permutations and block ciphers using a substitutionpermutation network (SPN) approach where the nonlinear part does not cover the entire state has recently gained attention due to favorable implementation characteristics in various scenarios.For word-oriented partial SPN (P-SPN) schemes with a fixed linear layer, our goal is to better understand how the details of the linear layer affect the security of the construction. In this paper, we derive conditions that allow us to either set up or prevent attacks based on infinitely long truncated differentials with probability 1. Our analysis is rather broad compared to earlier independent work on this problem since we consider (1) both invariant and non-invariant/iterative trails, and (2) trails with and without active S-boxes.For these cases, we provide rigorous sufficient and necessary conditions for the matrix that defines the linear layer to prevent the analyzed attacks. On the practical side, we present a tool that can determine whether a given linear layer is vulnerable based on these results. Furthermore, we propose a sufficient condition for the linear layer that, if satisfied, ensures that no infinitely long truncated differential exists. This condition is related to the degree and the irreducibility of the minimal polynomial of the matrix that defines the linear layer. Besides P-SPN schemes, our observations may also have a crucial impact on the Hades design strategy, which mixes rounds with full S-box layers and rounds with partial S-box layers.
Video from TOSC 2021
BibTeX
@article{tosc-2021-31088,
  title={Proving Resistance Against Infinitely Long Subspace Trails: How to Choose the Linear Layer},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2021, Issue 2},
  pages={314-352},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8913},
  doi={10.46586/tosc.v2021.i2.314-352},
  author={Lorenzo Grassi and Christian Rechberger and Markus Schofnegger},
  year=2021
}