Cryptology ePrint Archive: Report 2018/763

Block Cipher Invariants as Eigenvectors of Correlation Matrices

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.

Category / Keywords: secret-key cryptography / invariant subspace attack, nonlinear invariant attack, linear cryptanalysis, integral crypanalysis, correlation matrices, Midori-64, MANTIS

Original Publication (in the same form): IACR-ASIACRYPT-2018

Date: received 20 Aug 2018

Contact author: tim beyne at student kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20180820:182322 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]