Cryptology ePrint Archive: Report 2020/500

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

Lorenzo Grassi and Christian Rechberger and Markus Schofnegger

Abstract: When designing a classical substitution-permutation network (SPN) permutation, every non-trivial choice of the S-box and of the affine layer provides security after a finite number of rounds. However, this is not necessarily the case for partial SPN (P-SPN) ciphers: Since the nonlinear part does not cover the full state, there may exist highly non-trivial choices of linear layers which, for example, do not provide security against statistical attacks.

Quite surprisingly, this direction has hardly been considered in the literature. For example, LowMC uses different linear layers in each round in order to avoid the problem, but this solution is quite expensive, both computationally and memory-wise. Zorro, another construction with an incomplete nonlinear layer, simply reuses the AES matrix, but this introduces weaknesses.

Working from an attacker's perspective and focusing on P-SPN ciphers, in this paper we present conditions which allow to set up attacks based on infinitely long subspace trails -- even when using highly non-trivial linear layers. We analyze both the case in which the trail is invariant and the case in which is not invariant (yet still an infinite number of rounds can be covered). In this paper, we consider two scenarios, namely active and inactive S-boxes. For the first case, we finally provide a tool which is able to determine whether a given linear layer matrix is vulnerable against infinitely long invariant subspace trails based on our observations.

Finally, we point out that besides P-SPN ciphers, our results may also have a crucial impact on the Hades design strategy recently presented at Eurocrypt 2020, which mixes rounds with full S-box layers and rounds with partial S-box layers in order to guarantee security and achieve good performance in the target applications.

Category / Keywords: secret-key cryptography / Partial SPN, Linear Layer, Invariant Subspace, Subspace Trail, HADES

Date: received 29 Apr 2020, last revised 4 May 2020

Contact author: l grassi at cs ru nl

Available format(s): PDF | BibTeX Citation

Version: 20200504:172606 (All versions of this report)

Short URL: ia.cr/2020/500


[ Cryptology ePrint archive ]