TY - JOUR
AU - Beierle, Christof
AU - Felke, Patrick
AU - Leander, Gregor
AU - RÃ¸njom, Sondre
PY - 2022/12/07
Y2 - 2023/02/07
TI - Decomposing Linear Layers
JF - IACR Transactions on Symmetric Cryptology
JA - ToSC
VL - 2022
IS - 4
SE - Articles
DO - 10.46586/tosc.v2022.i4.243-265
UR - https://tosc.iacr.org/index.php/ToSC/article/view/9978
SP - 243-265
AB - <p>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 substitutionpermutation network (SPN), covering the case in which the specification of the linear layer is obfuscated by applying secret linear transformations to the S-boxes. We first present algorithms to decide whether an <em>ms </em>x <em>ms</em> matrix with entries in a prime field F<sub><em>p</em></sub> can be represented as an <em>m x m</em> matrix over the extension field F<sub><em>p</em></sub><em><sup>s</sup></em> . 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 x 8 MDS matrix over F<sub><em>2<sup>8</sup></em></sub> used in the hash function Streebog is a Cauchy matrix.</p>
ER -