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 $\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.\\

Note: EDP lower bound part corrected.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Maiorana-McFarland structurelinear hullPotentialExpected differential probabilitySimonSimeck
Contact author(s)
chenhao @ fudan edu cn
haochen @ jnu edu cn
History
2022-01-29: last of 3 revisions
2021-12-31: received
See all versions
Short URL
https://ia.cr/2021/1703
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1703,
      author = {Hao Chen},
      title = {The Maiorana-McFarland structure based cryptanalysis of Simon},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1703},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1703}},
      url = {https://eprint.iacr.org/2021/1703}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.