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.

Additional Metadata
Persistent URL dx.doi.org/10.13154/tosc.v2017.i2.203-227
Journal IACR Transactions on Symmetric Cryptology
Citation
Canteaut, A, Lambooij, E, Neves, S, Rasoolzadeh, S, Sasaki, Y, & Stevens, M.M.J. (2017). Refined Probability of Differential Characteristics Including Dependency Between Multiple Rounds. IACR Transactions on Symmetric Cryptology, 2017(2), 203–227. doi:10.13154/tosc.v2017.i2.203-227