Ruhr-Uni-Bochum

Decomposing Linear Layers

2022

Conference / Medium

Authors

Sondre Ronjom Gregor Leander Patrick Felke Christof Beierle

Research Hub

Research Hub A: Kryptographie der Zukunft

Research Challenges

RC 1: Cryptography against Mass Surveillance

Abstract

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 ms x ms matrix with entries in a prime field Fp can be represented as an m x m matrix over the extension field Fps . 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 F28 used in the hash function Streebog is a Cauchy matrix.

Tags

Symmetric Cryptography
Cryptography