Cryptology ePrint Archive: Report 2017/478

Refined Probability of Differential Characteristics Including Dependency Between Multiple Rounds

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

Abstract: 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.

Category / Keywords: differential cryptanalysis, independent S-box, fixed key, unkeyed construction, exact probability, RoadRunneR, Minalpher

Original Publication (in the same form): IACR-TOSC ISSUE 2-2017

Date: received 29 May 2017, last revised 29 May 2017

Contact author: sasaki yu at 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

Available format(s): PDF | BibTeX Citation

Version: 20170529:164823 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]