SoK: Design-Level Backdoors in Block Ciphers Constructions, Detection, and Key Recovery

What it is

A preprint by Shah Fahd (ePrint 2026/2582, received 21 October 2026) that studies the four published design-level block cipher backdoors: Rijmen and Preneel, Paterson, Bannier and Filiol, and Peyrin and Wang. It asks two questions the original papers left open. Does the trapdoor also weaken the cipher against ordinary cryptanalysis? Can an evaluator who holds only the specification find it? The paper places the designs in one taxonomy and in Beyne's correlation-matrix framework.

How it works

The detection algorithm recovers a partition trapdoor from the S-box tables. The paper proves it never reports a false trapdoor and, below an explicit cap, never misses one. Inversion and affine equivalence preserve a trapdoor. Extended affine and CCZ equivalence can erase it, so an equivalent S-box may hide what the algorithm would otherwise find.

The attacks show the effect depends on the rest of the cipher:

• KG-DES (Paterson's S-boxes in DES): the best 16-round differential characteristic has probability 2^-21.23, against 2^-61.97 for DES. A two-stage attack recovers the 56-bit key in minutes. Single characteristics put the boomerang at 2^-36.79 when it returns with probability 1.
• BEA-1: the trapdoor opens no useful trail. For every key, though, BEA-1 and KG-DES act as an exact smaller cipher on the cosets. Known-plaintext distinguishers need about 2^16.5 texts (KG-DES) and 2^20.5 texts (BEA-1), in that order of the ciphers as listed in the abstract.
• LowMC-M: the MALICIOUS backdoor sits in the linear layers. With an ideal XOF, a backdoored instance is distributed as an honest one. Its holder recovered the key from 35 to 409 queries in seven full-size measurements.

An independent MILP model confirms every optimum it can prove.

Preconditions / Affected

Detection by the algorithm applies to deterministic trapdoors in S-boxes. It finds Paterson's trapdoor and BEA-1's four trapdoors in the S-boxes that carry them. Rijmen and Preneel's trapdoor needs unbalanced S-boxes, which linear algebra exposes. A trapdoor in unexplained linear layers, as in LowMC-M, leaves nothing for any test of the primitive to find.

What to do

The paper recommends two routine checks for anyone evaluating a cipher:

1. Run the partition-trapdoor recovery on the S-box tables, and treat equivalence-class changes (extended affine, CCZ) as a way a trapdoor could be hidden.
2. Require that linear-layer and other constants be derived verifiably from a public seed. The paper says this is the only way to rule out a linear-layer trapdoor.

The page gives no code, repository or commands.

Caveats

Probabilistic trapdoors and trapdoors in only some S-boxes remain open. The soundness guarantee of "never misses" holds only below the explicit cap. The work is a preprint with no peer review noted.