Paper 2019/172

Correlation of Quadratic Boolean Functions: Cryptanalysis of All Versions of Full MORUS

Danping Shi, Siwei Sun, Yu Sasaki, Chaoyun Li, and Lei Hu


We show that the correlation of any quadratic Boolean function can be read out from its so-called disjoint quadratic form. We further propose a polynomial-time algorithm that can transform an arbitrary quadratic Boolean function into its disjoint quadratic form. With this algorithm, the exact correlation of quadratic Boolean functions can be computed efficiently. We apply this method to analyze the linear trails of MORUS (one of the seven finalists of the CAESAR competition), which are found with the help of a generic model for linear trails of MORUS-like key-stream generators. In our model, any tool for finding linear trails of block ciphers can be used to search for trails of MORUS-like key-stream generators. As a result, a set of trails with correlation $2^{-38}$ is identified for all versions of full MORUS, while the correlations of previously published best trails for MORUS-640 and MORUS-1280 are $2^{-73}$ and $2^{-76}$ respectively (ASIACRYPT 2018). This significantly improves the complexity of the attack on MORUS-1280-256 from $2^{152}$ to $2^{76}$. These new trails also lead to the first distinguishing and message-recovery attacks on MORUS-640-128 and MORUS-1280-128 with surprisingly low complexities around $2^{76}$. Moreover, we observe that the condition for exploiting these trails in an attack can be more relaxed than previously thought, which shows that the new trails are superior to previously published ones in terms of both correlation and the number of ciphertext blocks involved.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2019
Quadratic Boolean functionDisjoint quadratic formCorrelation attackCAESAR competitionMORUSMILP
Contact author(s)
shidanping @ iie ac cn
sunsiwei @ iie ac cn
sasaki yu @ lab ntt co jp
chaoyun li @ esat kuleuven be
hulei @ iie ac cn
2019-06-24: last of 3 revisions
2019-02-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Danping Shi and Siwei Sun and Yu Sasaki and Chaoyun Li and Lei Hu},
      title = {Correlation of Quadratic Boolean Functions: Cryptanalysis of All Versions of Full MORUS},
      howpublished = {Cryptology ePrint Archive, Paper 2019/172},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.