Improved Differential-Linear Analysis for the Speck Family

Add-Rotate-XOR (ARX) constructions build symmetric ciphers from modular addition, word-wise rotations, and XOR. Carry propagation in modular addition makes differential-linear (DL) cryptanalysis inherently bit-oriented. Focusing on hourglass(-like) DL distinguishers for the Speck family, we derive simple alignment relations between Speck’s rotation parameters and carry-related bit positions in modular addition. These relations predict systematic preferences for sparse intermediate differences and masks, and experiments on several Speck variants corroborate these patterns. Based on these relations, we develop a fast search approach that uses SMT (Satisfiability Modulo Theories) optimization to obtain optimal outer differential and linear trails under boundary constraints and a CUDA batch evaluator to estimate middle-round differential-linear approximation (DLA) correlations with a top-<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> filtering strategy. Applying this method to the Speck family, we improve the best-known DL distinguishers for 12-round Speck64 and 16-round Speck96, increasing the estimated overall correlation |<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">bp</i>ϵ<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>| by factors up to 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1.22</sup> (from 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">−22.29</sup> to 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">−21.07</sup>) and 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4.13</sup> (from 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">−48.32</sup> to 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">−44.19</sup>), respectively. Compared to the best-known distinguishers, this reduces the required chosen-plaintext pairs by factors of about 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2.44</sup> and 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">8.26</sup>, respectively. We further give an effective 14-round Speck64 distinguisher, extending the previously best-known effective result by one round.