Refined Probability of Differential Characteristics Including Dependency Between Multiple Rounds

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

IACR Transactions on Symmetric Cryptology - Issue 2-2017


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 RR. 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.

[pdf] [DOI]

tags: differential_cryptanalysis, Minalpher, RoadRunneR, symmetric_key_cryptanalysis