SoK: Design-Level Backdoors in Block Ciphers Constructions, Detection, and Key Recovery
:12
Abstract
A block cipher is trusted once it resists every published attack and its S-boxes pass the standard tests. A design-level backdoor turns this trust against its users. Its designer hides a structure that only they can exploit, and that the usual tests miss. Four such backdoors have been published, by Rijmen and Preneel, Paterson, Bannier and Filiol, and Peyrin and Wang. Each paper shows what the hidden structure gives its designer. Everyone else needs answers to two other questions. Does the structure also weaken the cipher against ordinary cryptanalysis? Can an evaluator who holds only the specification find it? Neither has been answered for all four designs, so an S-box that passes the usual tests is trusted by default. In this paper we answer both questions. We place the four designs in one taxonomy and in Beyne's correlation-matrix framework. We give an algorithm that recovers a partition trapdoor from the S-box tables, and prove that it never reports a false one and, below an explicit cap, never misses one. We show that inversion and affine equivalence preserve a trapdoor, while extended affine and CCZ equivalence can erase it. We then attack KG-DES (Paterson's S-boxes in DES), BEA-1 and LowMC-M. The answer to the first question depends on the rest of the cipher. In KG-DES the trapdoor makes ordinary attacks far stronger. The best $16$-round differential characteristic has probability $2^{-21.23}$, against $2^{-61.97}$ for DES, and a two-stage attack recovers the $56$-bit key in minutes. In BEA-1 the trapdoor opens no useful trail. However, for every key both ciphers act as an exact smaller cipher on the cosets, and fall to known-plaintext distinguishers from about $2^{16.5}$ and $2^{20.5}$ texts. An independent MILP model confirms every optimum it can prove, and shows that single characteristics put the KG-DES boomerang at $2^{-36.79}$ when it returns with probability $1$. The answer to the second question depends on where the backdoor sits. Our algorithm finds Paterson's trapdoor and BEA-1's four in the S-boxes that carry them. Rijmen and Preneel's trapdoor needs unbalanced S-boxes, which linear algebra exposes. LowMC-M's MALICIOUS backdoor sits in the linear layers instead. With an ideal XOF a backdoored instance is distributed as an honest one, so no test of the primitive finds it. Its holder recovered the key from $35$ to $409$ queries in seven full-size measurements. A deterministic trapdoor in the S-boxes therefore leaves a trace that a sound algorithm finds. A trapdoor in unexplained linear layers leaves none, and only constants derived verifiably from a public seed rule it out. We recommend both as routine checks. Probabilistic trapdoors and trapdoors in only some S-boxes remain open.