Cryptology ePrint Archive: Report 2021/1703

The Maiorana-McFarland structure based cryptanalysis of Simon

Hao Chen

Abstract: In this paper we propose the linear hull construction for block ciphers with quadratic Maiorana-McFarland structure round functions. The search for linear trails with high squared correlations from our Maiorana-McFarland structure based constructive linear cryptanalysis is linear algebraic. Hence from this linear algebraic essence, the space of all linear trails has the structure such that good linear hulls can be constructed. We apply our method to construct better linear hulls for the Simon and Simeck block cipher family. Then for the Simon2n and its variants, we prove the lower bound $\frac{1}{2^n}$ on the potential of the linear hull with the fixed input and output masks at arbitrary long rounds, under independent assumptions. We argue that for Simon2n the potential of the realistic linear hull of the Simon2n with the linear key-schedule should be bigger than $\frac{1}{2^{2n}}$.\\

On the other hand we prove that the expected differential probability (EDP) is at least $\frac{1}{2^n}$ under the independence assumptions. It is argued that the lower bound of EDP of Simon2n of realistic differential trails is bigger than $\frac{1}{2^{2n}}$. It seems that at least theoretically the Simon2n is insecure for the key-recovery attack based on our new constructed linear hulls and key-recovery attack based on our constructed differential trails.\\

Category / Keywords: secret-key cryptography / Maiorana-McFarland structure, linear hull, Potential, Expected differential probability, Simon, Simeck

Date: received 30 Dec 2021, last revised 21 Jan 2022

Contact author: chenhao at fudan edu cn, haochen at jnu edu cn

Available format(s): PDF | BibTeX Citation

Note: EDP lower bound part corrected.

Short URL: ia.cr/2021/1703

[ Cryptology ePrint archive ]