The Wrong Key Randomization Hypothesis: A Quasidifferential Analysis

Abstract

We revisit key-recovery differential attacks without assuming wrong-key randomization (WKR). Recent work has investigated key dependencies in differential characteristics from complementary perspectives (propagating key-schedule constraints through trails, and computing fixed-key probabilities via quasidifferentials), yet the full distribution of wrong-key probabilities for the key-recovery map remained out of reach. Building on the quasidifferential framework of Beyne and Rijmen, we present a method that computes these probabilities for PRESENT-like SPNs, combining SMT-guided enumeration of quasidifferential trails with a sparse Walsh-Hadamard transform to keep the computation tractable. The resulting distribution of wrong-key hit rates is a finite mixture with large zero-probability classes and others well above 2^{-n}. We take these computed probabilities into a hypothesis-testing model to obtain data-complexity estimates without WKR. Validation on a 16-bit toy cipher and on PRESENT demonstrates that fixed-key structure can both help and hurt key recovery, by magnitudes reaching 100x in certain regimes.

Biography

Ricardo is a PhD student in the Symmetric Cryptography group at Ruhr Universität Bochum, supervised by Prof. Gregor Leander. His research focuses on key dependency in differential cryptanalysis and key recovery, using automated methods such as SAT/SMT solving and integer programming. He also has a secondary interest in explainability (XAI) and Boolean function analysis. He holds an undergraduate degree in mathematics and a master's in computer science from Pontificia Universidad Católica de Chile, where he worked on computational complexity, logic, and automata theory under the supervision of Prof.