Paper 2025/1553

Understanding Unexpected Fixed-Key Differential Behaviours: How to Avoid Major Weaknesses in Lightweight Designs (Extended Version)

Merlin Fruchon, Direction Générale de l'Armement, French Institute for Research in Computer Science and Automation

Abstract

Many design strategies and differential attacks rely on the so-called hypothesis of stochastic equivalence, which states that the differential behaviour of a cipher for any fixed key can be approximated by its average behaviour over all keys. However, this assumption is known to be invalid in general. For instance, all two-round differential characteristics of AES are plateau, meaning that their probabilities highly depend on the key. While such discrepancies were traditionally expected to occur only for a small number of rounds, several counter-examples have been exhibited recently thanks to the quasi-differential framework. This paper aims to show why the divergence between fixed-key and average behaviour can be even more pronounced and is definitely harder to anticipate when analyzing differentials, rather than individual characteristics, which is the quantity actually relevant in differential cryptanalysis. Indeed, when a differential aggregates many characteristics that do not satisfy the hypothesis of stochastic equivalence, several scenarios may arise: the sets of weak keys may be identical across all characteristics, resulting in a strong clustering effect, or entirely disjoint, eliminating any such effect. Focusing on (truncated) differentials that include plateau characteristics, we demonstrate how this mechanism explains the unexpected differential behaviour observed in Midori64 and Scream over an arbitrary number of rounds, as recently reported by Baudrin et al. We also clarify how this situation differs from invariant subspaces, except in a few specific cases. Furthermore, we identify the properties of the Sbox that give rise to this weakness and all vulnerable Sboxes among the optimal 4-bit functions.