Paper 2026/2746

Differential Cryptanalysis of SPEEDY: Revised Security Evaluation and Improved Key Recovery Attack

Abstract

The resistance of a block cipher against differential cryptanalysis (DC) is a fundamental criterion for evaluating its security. SPEEDY is a family of low-latency SPS-type block ciphers designed by Leander et al. The designers presented two evaluations of SPEEDY against DC: the first restricted 1-bit-to-1-bit differential propagations through the S-box and used the higher-order branch numbers to estimate the maximum expected differential probability (EDP) of differential trails; the second imposed a structural restriction and assumed that all 1-bit-to-1-bit propagations through an active S-box are possible to estimate the minimum number of active S-boxes. Zhang later exhibited a counterexample to the designers' first evaluation and introduced the notion of partition branch number, relaxing some of the propagation restrictions to allow multi-bit-to-1-bit transitions on some S-box layers and refining the evaluation. However, these evaluations consider only restricted spaces of differential characteristics and therefore inaccurately estimate the security of SPEEDY against DC, which means that the resistance of SPEEDY against DC remains unclear so far. To address this problem, we propose an efficient search method based on search patterns. Unlike previous evaluations, our method imposes no a priori structural restrictions on the allowed differential characteristics; it uses computational pruning to keep the search tractable and performs a conservative security evaluation of the pruned region, thereby providing an accurate evaluation over the global space. At the framework level, we decompose an r-round differential characteristic into an (r-1)-round core trail and an r-round extended trail. By extending a core trail independently at both ends, the two additional S-box layers are handled by two separate models, each containing only one S-box layer and solvable efficiently. At the implementation level, we further introduce a short-round reuse via hash-map concatenation technique, which concatenates short-round core trails to construct longer-round core trails, thereby avoiding expensive long-round MILP models. For 4 rounds, we narrow the minimum number of active S-boxes from the previously reported 35 to [33,34] and find a characteristic with 34 active S-boxes outside the previous search spaces. We also obtain the highest-probability differential characteristics known to date for 2 to 5 rounds. In particular, the 2-, 3-, and 4-round characteristics disprove the designers' branch-number-based security claims. Furthermore, using the quasidifferential framework, we evaluate the found characteristics and obtain several 5-round distinguishers outperforming those used in existing key recovery attacks in terms of EDP. Finally, we optimize the probabilistic extension parameters used in a previous key recovery attack, which yields the best known key recovery attack on SPEEDY-7-192, with data complexity $2^{173.48}$ and time complexity $2^{173.69}$ encryptions.