Paper 2020/500

Weak Linear Layers in Word-Oriented Partial SPN and HADES-Like Schemes

Lorenzo Grassi and Christian Rechberger and Markus Schofnegger

Abstract

Designing cryptographic permutations and ciphers using a substitution permutation network (SPN) approach where the nonlinear part does not cover the full state has recently gained attention due to favourable implementation characteristics in various scenarios. For these word-oriented partial SPN schemes with a fixed linear layer, our goal is to better understand linear layer construction. In this paper we derive conditions which allow either to set up or to prevent attacks based on infinitely long truncated differentials with probability 1. Our analysis is rather broad as in contrast to earlier independent work on this problem, we consider (1) trails that are invariant and trails that are not, and (2) trails with and without active S-boxes. In both cases (namely, active and inactive S-boxes), we are able to provide rigorous sufficient and necessary conditions that prevent the analyzed attacks. On the practical side, we present a tool which is able to determine whether a given linear layer is vulnerable based on these results. Besides P-SPN schemes, our observations may also have a crucial impact on the very recent Hades design strategy, which mixes rounds with full S-box layers and rounds with partial S-box layers.

Note: This is a major update. With respect to the previous version of the paper, we solved many of the open problems left for future research. In particular, this includes the following additions. (1) We are now able to present *sufficient and necessary* conditions which guarantee that no infinitely long subspace trails (either invariant or iterative, both with inactive and active S-boxes) exist. (2) We present new tools that can determine if a given matrix is vulnerable. These tests take only a few seconds on an ordinary computer. (3) Together with our new observations, this allows to find secure matrices for every choice of t (the number of words), s (the number of S-boxes per round), and n or ceil(log_2(p)) (the size of a word in bits for binary fields or prime fields, respectively). (4) Finally, we present new examples and new theoretical results.