Paper 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. 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 $$ under the independence assumptions. It is argued that the lower bound of EDP of Simon2n of realistic differential trails is bigger than $$. 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.

Note: EDP lower bound part corrected.