Refined Probability of Differential Characteristics Including Dependency Between Multiple Rounds


  • Anne Canteaut Inria, Paris, France
  • Eran Lambooij Eindhoven University of Technology, Eindhoven, The Netherlands
  • Samuel Neves Centre for Informatics and Systems of the University of Coimbra (CISUC), Department of Informatics Engineering, University of Coimbra, Coimbra, Portugal
  • Shahram Rasoolzadeh Ruhr-Universität Bochum, Bochum, Germany
  • Yu Sasaki NTT Secure Platform Laboratories, Tokyo, Japan
  • Marc Stevens Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands



differential cryptanalysis, independent S-box, fixed key, unkeyed construction, exact probability, RoadRunneR, Minalpher


The current paper studies the probability of differential characteristics for an unkeyed (or with a fixed key) construction. Most notably, it focuses on the gap between two probabilities of differential characteristics: probability with independent S-box assumption, pind, and exact probability, pexact. It turns out that pexact is larger than pind in Feistel network with some S-box based inner function. The mechanism of this gap is then theoretically analyzed. The gap is derived from interaction of S-boxes in three rounds, and the gap depends on the size and choice of the S-box. In particular the gap can never be zero when the S-box is bigger than six bits. To demonstrate the power of this improvement, a related-key differential characteristic is proposed against a lightweight block cipher RoadRunneR. For the 128-bit key version, pind of 2−48 is improved to pexact of 2−43. For the 80-bit key version, pind of 2−68 is improved to pexact of 2−62. The analysis is further extended to SPN with an almost-MDS binary matrix in the core primitive of the authenticated encryption scheme Minalpher: pind of 2−128 is improved to pexact of 2−96, which allows to extend the attack by two rounds.



How to Cite

Canteaut, A., Lambooij, E., Neves, S., Rasoolzadeh, S., Sasaki, Y., & Stevens, M. (2017). Refined Probability of Differential Characteristics Including Dependency Between Multiple Rounds. IACR Transactions on Symmetric Cryptology, 2017(2), 203–227.