### Block Cipher Invariants as Eigenvectors of Correlation Matrices (Full Version)

Tim Beyne

##### Abstract

A new approach to invariant subspaces and nonlinear invariants is developed. This results in both theoretical insights and practical attacks on block ciphers. It is shown that, with minor modifications to some of the round constants, Midori-64 has a nonlinear invariant with $2^{96}$ corresponding weak keys. Furthermore, this invariant corresponds to a linear hull with maximal correlation. By combining the new invariant with integral cryptanalysis, a practical key-recovery attack on 10 rounds of unmodified Midori-64 is obtained. The attack works for $2^{96}$ weak keys and irrespective of the choice of round constants. The data complexity is $1.25 \cdot 2^{21}$ chosen plaintexts and the computational cost is dominated by $2^{56}$ block cipher calls. Finally, it is shown that similar techniques lead to a practical key-recovery attack on MANTIS-4. The full key is recovered using 640 chosen plaintexts and the attack requires about $2^{56}$ block cipher calls. Finally, it is shown that similar techniques lead to a practical key-recovery attack on Mantis-4. The full key is recovered using roughly $350$ chosen plaintexts and the attack requires about $2^{56}$ block cipher calls. Furthermore, given less than $350$ additional chosen ciphertexts under a related tweak, $2^{18}$ block cipher calls suffice to recover the full key.

Available format(s)
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2018
Keywords
invariant subspace attacknonlinear invariant attacklinear cryptanalysisintegral crypanalysiscorrelation matricesMidori-64MANTIS
Contact author(s)
tim beyne @ student kuleuven be
History
2019-11-18: revised
See all versions
Short URL
https://ia.cr/2018/763

CC BY

BibTeX

@misc{cryptoeprint:2018/763,
author = {Tim Beyne},
title = {Block Cipher Invariants as Eigenvectors of Correlation Matrices (Full Version)},
howpublished = {Cryptology ePrint Archive, Paper 2018/763},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/763}},
url = {https://eprint.iacr.org/2018/763}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.