Paper 2017/478

Refined Probability of Differential Characteristics Including Dependency Between Multiple Rounds

Anne Canteaut, Eran Lambooij, Samuel Neves, Shahram Rasoolzadeh, Yu Sasaki, and Marc Stevens


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, $p_{ind}$, and exact probability, $p_{exact}$. It turns out that $p_{exact}$ is larger than $p_{ind}$ 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, $p_{ind}$ of $2^{-48}$ is improved to $p_{exact}$ of $2^{-43}$. For the 80-bit key version, $p_{ind}$ of $2^{-68}$ is improved to $p_{exact}$ 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: $p_{ind}$ of $2^{-128}$ is improved to $p_{exact}$ of $2^{-96}$, which allows to extend the attack by two rounds.

Available format(s)
Publication info
Published by the IACR in TOSC 2017 ISSUE 2
differential cryptanalysisindependent S-boxfixed keyunkeyed constructionexact probabilityRoadRunneRMinalpher
Contact author(s)
sasaki yu @ lab ntt co jp
sneves @ dei uc pt
anne canteaut @ inria fr
e lambooij @ student tue nl
marc stevens @ cwi nl
Rasoolzadeh shahram @ gmail com
2017-05-29: received
Short URL
Creative Commons Attribution


      author = {Anne Canteaut and Eran Lambooij and Samuel Neves and Shahram Rasoolzadeh and Yu Sasaki and Marc Stevens},
      title = {Refined Probability of Differential Characteristics Including Dependency Between Multiple Rounds},
      howpublished = {Cryptology ePrint Archive, Paper 2017/478},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.