Paper 2020/500

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

Lorenzo Grassi, Christian Rechberger, and Markus Schofnegger

Abstract

Designing cryptographic permutations and block ciphers using a substitution-permutation 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.

Note: This is a major update. In particular, we formulate the necessary and sufficient conditions in a different way, partially using the primary decomposition theorem. We also add new results regarding certain classes of matrices.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in FSE 2022
Keywords
Partial SPNLinear LayerInvariant SubspaceSubspace TrailHADES
Contact author(s)
l grassi @ science ru nl
markus schofnegger @ iaik tugraz at
History
2021-05-28: last of 6 revisions
2020-04-30: received
See all versions
Short URL
https://ia.cr/2020/500
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/500,
      author = {Lorenzo Grassi and Christian Rechberger and Markus Schofnegger},
      title = {Proving Resistance Against Infinitely Long Subspace Trails: How to Choose the Linear Layer},
      howpublished = {Cryptology ePrint Archive, Paper 2020/500},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/500}},
      url = {https://eprint.iacr.org/2020/500}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.