@article{Canteaut_Lambooij_Neves_Rasoolzadeh_Sasaki_Stevens_2017, title={Refined Probability of Differential Characteristics Including Dependency Between Multiple Rounds}, volume={2017}, url={https://tosc.iacr.org/index.php/ToSC/article/view/644}, DOI={10.13154/tosc.v2017.i2.203-227}, abstractNote={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, <em>p</em><sub>ind</sub>, and exact probability, <em>p</em><sub>exact</sub>. It turns out that pexact is larger than <em>p</em><sub>ind</sub> 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, <em>p</em><sub>ind</sub> of 2<sup>−48</sup> is improved to <em>p</em><sub>exact</sub> of 2<sup>−43</sup>. For the 80-bit key version, <em>p</em><sub>ind</sub> of 2<sup>−68</sup> is improved to <em>p</em><sub>exact</sub> of 2<sup>−62</sup>. The analysis is further extended to SPN with an almost-MDS binary matrix in the core primitive of the authenticated encryption scheme Minalpher: <em>p</em><sub>ind</sub> of 2<sup>−128</sup> is improved to <em>p</em><sub>exact</sub> of 2<sup>−96</sup>, which allows to extend the attack by two rounds.}, number={2}, journal={IACR Transactions on Symmetric Cryptology}, author={Canteaut, Anne and Lambooij, Eran and Neves, Samuel and Rasoolzadeh, Shahram and Sasaki, Yu and Stevens, Marc}, year={2017}, month={Jun.}, pages={203–227} }