A Quasidifferential Analysis of the Wrong-Key Randomization Hypothesis

The Wrong-Key Randomization (WKR) hypothesis governs data-complexity estimates in differential cryptanalysis: wrong-key guesses are assumed to behave as a random permutation would. Exact computation of fixed-key differential probabilities was, until recently, infeasible. We use quasidifferential trails to compute the exact wrong-key distribution for the key-recovery map Gk,k' = Fk'-1 o Fk in PRESENT-like SPNs. A mask-first reformulation exposes a Walsh-Hadamard structure; restricting the transform to the low-dimensional support, together with SMT-guided trail enumeration, reduces the cost: for a 16-bit toy cipher, from 280 to 213; for PRESENT, from 2192 to 230; and for GIFT-64, from 2192 to 232. For the toy cipher, PRESENT and GIFT-64, the computed distribution is a structured mixture: a large zero-probability class coexists with bottleneck classes orders of magnitude above the random-permutation mean, and nothing lies between them. Such a distribution is not unimodal, so no Poisson or binomial law fits it for any parameter and the hypothesis is formally false for all three targets. For PRESENT, however, we show that this deviation does not affect the security of Wang's 14-round differential attack. We cast the computed distribution as a structured composite hypothesis, the differential counterpart of the random-permutation/composite-hypothesis model used for wrong keys in linear cryptanalysis, and show that the shape of the wrong-key distribution, not merely its mean, governs how many wrong keys survive the key-recovery filter. For PRESENT with Wang's distinguisher, the structural signal is carried only by the right pairs, whose weight is too small for the deviation to surface; the hypothesis remains a safe heuristic in this case despite being formally false. Our SMT-based enumeration tool is publicly available.