Paper 2022/1159

Decomposing Linear Layers

Christof Beierle, Faculty of Computer Science, Ruhr University Bochum, Bochum, Germany
Patrick Felke, University of Applied Sciences Emden-Leer, Emden, Germany
Gregor Leander, Faculty of Computer Science, Ruhr University Bochum, Bochum, Germany
Sondre Rønjom, Nasjonal Sikkerhetsmyndighet (NSM), Oslo, Norway, University of Bergen, Bergen, Norway

There are many recent results on reverse-engineering (potentially hidden) structure in cryptographic S-boxes. The problem of recovering structure in the other main building block of symmetric cryptographic primitives, namely, the linear layer, has not been paid that much attention so far. To fill this gap, in this work, we develop a systematic approach to decomposing structure in the linear layer of a substitution-permutation network (SPN), covering the case in which the specification of the linear layer is obfuscated from applying secret linear transformations to the S-boxes. We first present algorithms to decide whether an $ms \times ms$ matrix with entries in a prime field $\mathbb{F}_p$ can be represented as an $m \times m$ matrix over the extension field $\mathbb{F}_{p^s}$. We then study the case of recovering structure in MDS matrices by investigating whether a given MDS matrix follows a Cauchy construction. As an application, for the first time, we show that the $8 \times 8$ MDS matrix over $\mathbb{F}_{2^8}$ used in the hash function Streebog is a Cauchy matrix.

Available format(s)
Secret-key cryptography
Publication info
finite field matrix substitution-permutation network MDS Cauchy
Contact author(s)
christof beierle @ rub de
patrick felke @ hs-emden-leer de
gregor leander @ rub de
sondre ronjom @ uib no
2022-09-06: approved
2022-09-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Christof Beierle and Patrick Felke and Gregor Leander and Sondre Rønjom},
      title = {Decomposing Linear Layers},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1159},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.