Block Cipher Invariants as Eigenvectors of Correlation Matrices

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.

This work was supported by the Research Council KU Leuven: C16/18/004.

1 Introduction

Block ciphers are an essential primitive for the construction of many cryptosystems. This leads to a natural desire to optimize them with respect to various application-dependent criteria. Examples include low-latency block ciphers such as PRINCE [6] and MANTIS [4], and the low-power design Midori-64 [2]. Biryukov and Perrin [5] give a broad overview of such lightweight primitives.

One requirement is shared by all applications: the block cipher must be secure – at the very least it must approximate a pseudorandom permutation. A common design decision that often helps to reduce latency, energy consumption and other cost measures is the simplification of the key-schedule. This, along with other aspects of lightweight designs, has led to the development of new cryptanalytic tools such as invariant subspaces [17] and nonlinear invariants [22]. These attacks are the subject of this paper.

At CRYPTO 2017, it was shown by Beierle, Canteaut, Leander and Rotella that invariant attacks can often be averted by a careful choice of the round constants [3]. Their work, as well as the earlier work by Todo, Leander and Sasaki on nonlinear invariants [22], invites several questions. This paper will be concerned with three related problems that arise in this context.

• 1. In their future work sections, Todo et al. [22] and Beierle et al. [3] both express the desire to generalize the nonlinear invariant attack. One can argue that a deeper theoretical understanding of block cipher invariants is helpful, if not essential, to achieve this goal.

• 2. One potential generalization is the existence of block cipher invariants which are not invariants under all of the round transformations. It is important to investigate this possibility, because such cases are not covered by the techniques introduced by Beierle et al. for choosing the round constants.

• 3. The previous problem leads to a third question: do such (generalized) invariants only impact the security of the cipher for a specific choice of the round constants? The results in this paper suggest otherwise.

Contribution. The first of the problems listed above is addressed in Sect. 4, where the main contribution is Definition 2 and the discussion following it. It is shown that block cipher invariants have an effective description in terms of eigenvectors of correlation matrices. These matrices were first introduced by Daemen, Govaerts and Vandewalle [8] in the context of linear cryptanalysis [20]. As a side result, more insight into the relation between invariants and linear cryptanalysis is obtained.

Section 5 takes a closer look at the invariants of Midori-64, leading up to an example of an invariant of the type described in the second problem above. It will be shown in Sect. 5.3 that, with minor changes to the round constants, Midori-64 has an invariant which is not invariant under the round function. It applies to $2^{96}$ weak keys. Note that this is a significantly larger class of weak keys compared to previous work, i.e. $2^{32}$ for the invariant subspace attack of Guo et al. and $2^{64}$ for the nonlinear invariant attack of Todo et al. [22]. In fact, it will be demonstrated that the invariant discussed in Sect. 5.3 corresponds to a linear hull with maximal correlation. This observation is of independent interest and will be briefly discussed in Sect. 5.4.

Finally, Sects. 6 and 7 address the third question listed above. That is, two cryptanalytic results are given to demonstrate that block cipher invariants may impact the security of a block cipher regardless of the choice of round constants.

In Sect. 6, a practical attack on 10 rounds of Midori-64 – for any choice of round constants – will be given. The attack applies to $2^{96}$ weak keys and requires roughly $1.25 \cdot 2^{21}$ chosen plaintexts. The computational cost is dominated by $2^{56}$ block cipher calls. Note that the data complexity and especially the computational cost to determine whether a weak key is used, are significantly lower. As discussed by Luykx, Mennink and Paterson [19] in ASIACRYPT 2017, this has a significant impact on the multi-key security of the block cipher.

Section 7 shows that the full key of MANTIS-4 [4] can be recovered given 640 chosen plaintexts. This attack works for all keys provided that a weak tweak is used. The number of weak tweaks is $2^{32}$ (out of $2^{64}$). The computational cost of this attack is dominated by $2^{56}$ block cipher calls.

2 Preliminaries and Related Work

Most of the notation used in this paper is standard, for instance $(\mathbb {F}_2, +, \cdot )$ denotes the field with two elements. Random variables are denoted in boldface.

Many of the results in this work can be compactly described by means of tensor products of real vector spaces. Let $V_1, \ldots , V_n$ be vector spaces over $\mathbb {R}$. Their tensor product is a real vector space $V_1 \otimes \cdots \otimes V_n$. Elements of $V_1 \otimes \cdots \otimes V_n$ will be called tensors. For $V = V_1 = \cdots = V_n$, the tensor product $V_1 \otimes \dots \otimes V_n$ will be denoted by $V^{\otimes n}$. Knowledge of tensor products is not essential to understand this work.

The invariant subspace attack was introduced by Leander, Abdelraheem, AlKhzaimi and Zenner in the context of PRINTcipher [17]. Let $E_k : \mathbb {F}_2^n \rightarrow \mathbb {F}_2^n$ be a block cipher. An affine subspace $a + V$ of $\mathbb {F}_2^n$ such that

$$\begin{aligned} E_k(a + V) = a + V, \end{aligned}$$

(1)

is called an invariant subspace for $E_k$. The keys k for which (1) holds, will be called weak keys. At ASIACRYPT 2016, Todo et al. introduced the nonlinear invariant attack as an extension of this attack [22]. A Boolean function $f : \mathbb {F}_2^n \rightarrow \mathbb {F}_2$ is called a nonlinear invariant for $E_k$ iff there exists a constant $c \in \mathbb {F}_2$ such that for all $x \in \mathbb {F}_2^n$,

$$\begin{aligned} f(x) + f(E_k(x)) = c. \end{aligned}$$

Importantly, the constant c may depend on the key k, but not on x.

The description of block cipher invariants in this paper is based on correlation matrices, which were first introduced by Daemen et al. [8]. The definition of these matrices has been postponed to Sect. 3, as they will be introduced from a novel point of view.

Finally, a brief description of Midori-64 is given here. This information will be used extensively in Sects. 5 and 6. Midori-64 is an iterated block cipher with a block size of 64 bits and a key length of 128 bits [2]. It operates on a 64-bit state, which can be represented as a $4 \times 4$ array of 4-bit cells. The round function consists of the operations SubCell ($\mathfrak {S}$), ShuffleCell (P), MixColumn ($\mathfrak {M}$) and a key addition layer. This structure is shown in Fig. 1.

Fig. 1.

The overall structure and round function of Midori-64.

The SubCell ($\mathfrak S$) mapping applies a 4-bit S-box S to each cell of the state. The fact that the S-box is an involution will be used in Sect. 5. The algebraic normal form of $S(x) = (S_1(x), S_2(x), S_3(x), S_4(x))$ is provided below. These expressions will not be used explicitly, but they can be helpful to verify the calculations in Sects. 6 and 7.

$$\begin{aligned} S_1(x_1, x_2, x_3, x_4)&= x_{1} x_{2} x_{3} + x_{1} x_{3} x_{4} + x_{1} x_{2} + x_{1} x_{3} + x_{3} x_{4} + 1 \\ S_2(x_1, x_2, x_3, x_4)&= x_{1} x_{2} x_{3} + x_{1} x_{3} x_{4} + x_{2} x_{3} x_{4} + x_{1} x_{4} + x_{1} + x_{4} + 1 \\ S_3(x_1, x_2, x_3, x_4)&= x_{1} x_{2} + x_{1} x_{4} + x_{2} x_{4} + x_{2} + x_{4}\\ S_4(x_1, x_2, x_3, x_4)&= x_{1} x_{2} x_{3} + x_{1} x_{3} x_{4} + x_{2} x_{3} x_{4} + x_{1} x_{4} + x_{2} x_{4} + x_{3}. \end{aligned}$$

The permutation ShuffleCell (P) interchanges the cells of the state. It operates on the state as follows:

The MixColumn ($\mathfrak M$) transformation acts on each state column independently by the following matrix over $\mathbb {F}_{2^4}$:

$$\begin{aligned} M = \begin{pmatrix} 0 &{} 1 &{} 1 &{} 1 \\ 1 &{} 0 &{} 1 &{} 1 \\ 1 &{} 1 &{} 0 &{} 1 \\ 1 &{} 1 &{} 1 &{} 0 \end{pmatrix}. \end{aligned}$$

That is, each cell of a column of the state is replaced by the exclusive or of the other elements in the same column. Finally, the round key in round i is alternatingly taken to be $K_0 + \gamma _i$ or $K_1 + \gamma _i$, where $\gamma _i$ is a round constant. Importantly, round constants are only added to the least significant (rightmost) bit of each cell, i.e. $\gamma _i \in \{0, 1\}^{16}$.

The tweakable block cipher MANTIS [4] is quite similar to Midori-64, having nearly the same round function. Details will be given in Sect. 7.

3 Correlation Matrices

The cryptanalysis of symmetric-key primitives is generally based on properties of the plaintext that are reflected by the corresponding ciphertext. To every such property, one could associate a set of values satisfying it. A convenient way to work with sets of plaintexts, or more generally multisets, is to associate a probability space with the set of block cipher inputs. Let $\varvec{x}$ be a random variable on $\mathbb {F}_2^n$ with probability mass function $p_{\varvec{x}}$. The Fourier transform $\widehat{p}_{\varvec{x}}$ of $p_{\varvec{x}}$ is defined by

$$\begin{aligned} \widehat{p}_{\varvec{x}}(\chi _u) = \sum _{x \in \mathbb {F}_2^n} p_{\varvec{x}}(x)\chi _u(x), \end{aligned}$$

where $\chi _u : x \mapsto (-1)^{u^T x}$ is a character of $\mathbb {F}_2^n$. That is, the function $p_{\varvec{x}}$ is expressed in the character basis of the algebra $\mathbb {C}[\mathbb {F}_2^n]$ of functions $\mathbb {F}_2^n \rightarrow \mathbb {C}$. Since the character group of $\mathbb {F}_2^n$ is isomorphic to $\mathbb {F}_2^n$, we may consider $\widehat{p}_{\varvec{x}}$ to be a function on $\mathbb {F}_2^n$ instead. That is,

$$\begin{aligned} \widehat{p}_{\varvec{x}}(u) = \mathbf {E}\left[ (-1)^{u^T\varvec{x}}\right] , \end{aligned}$$

where $\mathbf {E}\left[ \;\cdot \;\right]$ denotes the expected value. Additional information regarding the use of characters and, more generally, representations in the context of probability theory can be found in the references [7, 10].

Example 1

The Fourier transform of the uniform distribution on $\mathbb {F}_2^n$ is zero everywhere except at $u = 0$, i.e. it has coordinates $(1, 0, \ldots , 0)^T$. Let $p(x) = 0$ for all $x \ne c$ and $p(c) = 1$, then $\widehat{p}(u) = (-1)^{u^Tc}$. To stress that $\widehat{p}$ is a vector, we will regularly use the notation $\widehat{p}_u = \widehat{p}(u)$.    $\triangleright$

The following result is essential to the discussion of the invariants of Midori-64 in Sect. 5. Note that here, and further on, the vector spaces $\mathbb {F}_2^{mn}$ and $(\mathbb {F}_2^n)^m$ are treated as essentially the same. Recall that the symbol “$\otimes$” denotes the tensor product, which in this case coincides with the Kronecker product.

Theorem 1

(Independence). Let $\varvec{x}_1, \ldots , \varvec{x}_m$ be independent random variables on $\mathbb {F}_2^n$. The Fourier transform of the joint probability mass function of $\varvec{x}_1, \ldots , \varvec{x}_m$ is given by

$$\begin{aligned} \widehat{p}_{\varvec{x}_1, \ldots , \varvec{x}_m} = \bigotimes _{i = 1}^m \widehat{p}_{\varvec{x}_i}, \end{aligned}$$

where $\widehat{p}_{\varvec{x}_i}$ is the Fourier transform of the probability mass function of $\varvec{x}_i$.

Proof

By the independence of $\varvec{x}_1, \ldots , \varvec{x}_m$, we have

$$\begin{aligned} \widehat{p}_{\varvec{x}_1, \ldots , \varvec{x}_m}(u_1, \ldots , u_m) = \mathbf {E}\left[ (-1)^{\sum _{i=1}^m u_i^T\varvec{x}_i}\right] = \prod _{i = 1}^m \mathbf {E}\left[ (-1)^{u_i^T\varvec{x}_i}\right] . \end{aligned}$$

   $\square$

In fact, Theorem 1 generalizes to arbitrary functions $f : (\mathbb {F}_2^n)^m \rightarrow \mathbb {C}$ such that $f(x_1, \dots x_m) = \prod _{i = 1}^m f_i(x_i)$ with $f_i \in \mathbb {C}[\mathbb {F}_2^n]$.

The reader who is familiar with tensors may find it intuitive to consider $\widehat{p}_{\varvec{x}_1, \ldots , \varvec{x}_m}$ in Theorem 1 to be a simple (i.e. rank one) tensor in $[\mathbb {R}^{2^n}]^{\otimes m}$. This fact is not essential to the remainder of the paper.

The discussion so far has been limited to probability distributions. The remainder of this section deals with transformations of these distributions. The relation between the probability distribution of $\varvec{x}$ and $F(\varvec{x})$ is in general given by a transition matrix. When represented in the basis of characters, such a matrix may be called a correlation matrix (not to be confused with a matrix of second moments).

Definition 1

(Correlation matrix over $\mathbb {F}_2^n$). Let $F : \mathbb {F}_2^n \rightarrow \mathbb {F}_2^m$ be a vectorial Boolean function. The correlation matrix $C^F \in \mathbb {R}^{2^m \times 2^n}$ of F is the representation of the transition matrix of F with respect to the character basis of $\mathbb {C}[\mathbb {F}_2^n]$ and $\mathbb {C}[\mathbb {F}_2^m]$.

Theorem 2

Let $F : \mathbb {F}_2^n \rightarrow \mathbb {F}_2^m$ be a vectorial Boolean function with correlation matrix $C^F$. Let $\varvec{x}$ be a random variable on $\mathbb {F}_2^n$ with probability mass function $p_{\varvec{x}}$, then

$$\begin{aligned} \widehat{p}_{F(\varvec{x})} = C^F \widehat{p}_{\varvec{x}}. \end{aligned}$$

Proof

This result is essentially a restatement of Definition 1.   $\square$

It is instructive to consider the coordinates of $C^F$. By the Fourier inversion formula, we have

$$\begin{aligned} p_{\varvec{x}}(x) = \frac{1}{2^n} \sum _{u \in \mathbb {F}_2^n} (-1)^{u^T x}\, \widehat{p}_{\varvec{x}}(u). \end{aligned}$$

By substituting the above into the definition of $\widehat{p}_{F(\varvec{x})}$, and from Theorem 2, one obtains

$$\begin{aligned} \widehat{p}_{F(\varvec{x})}(u) = \sum _{v \in \mathbb {F}_2^n}\left[ \frac{1}{2^n}\sum _{x \in \mathbb {F}_2^n} (-1)^{u^T F(x) + v^T x}\right] \widehat{p}_{\varvec{x}}(v) = \sum _{v \in \mathbb {F}_2^n} C^F_{u, v}\; \widehat{p}_{\varvec{x}}(v). \end{aligned}$$

Since this holds for all functions $\widehat{p}_{\varvec{x}}$, the coordinates of $C^F$ are

$$\begin{aligned} C^F_{u, v} = \frac{1}{2^n} \sum _{x \in \mathbb {F}_2^n} (-1)^{u^T F(x) + v^T x}. \end{aligned}$$

(2)

This establishes the equivalence of Definition 1 and the definition due to Daemen et al. [8], which originates in the notion of correlation between Boolean functions. Note that (2) coincides with the Walsh-Hadamard transformation of F, but since the result of this transformation is not typically interpreted as a linear operator, we will avoid this term.

To conclude this section, a few useful properties of correlation matrices will be listed. These results can also be found (some in a slightly different form) in [8]. In Theorem 5, $\delta$ denotes the Kronecker delta function.

Theorem 3

(Composition). Let $F : \mathbb {F}_2^l \rightarrow \mathbb {F}_2^m$ and $G : \mathbb {F}_2^m \rightarrow \mathbb {F}_2^n$, then $C^{G \circ F} = C^G C^F$.

Theorem 4

(Orthogonality). Let $F : \mathbb {F}_2^n \rightarrow \mathbb {F}_2^n$. If F is a bijection, then its correlation matrix $C^F$ is orthogonal.

Theorem 5

(Linear maps). Let $L : \mathbb {F}_2^n \rightarrow \mathbb {F}_2^m$ be a linear map, then $C^L_{u, v} = \delta (v + L^Tu)$. Furthermore, if L is bijective, $C^L$ is a permutation matrix.

Theorem 6

(Boxed maps). Let $F : \mathbb {F}_2^{sn} \rightarrow \mathbb {F}_2^{sm}$ be a vectorial Boolean function such that there exist functions $F_i : \mathbb {F}_2^n \rightarrow \mathbb {F}_2^m$, $i = 1, \ldots , s$ with the property that $F = (F_1, \ldots , F_s)$. Then

$$\begin{aligned} C^F = \bigotimes _{i = 1}^s C^{F_i}. \end{aligned}$$

In light of Theorem 1, the property expressed by Theorem 6 is intuitively clear: a function satisfying the conditions of Theorem 6 preserves the independence of its inputs.

Example 2

Let $C^K$ denote the correlation matrix corresponding to the function $x \mapsto x + K$ with $x, K \in \mathbb {F}_2^2$. Let $K = (\kappa _1, \kappa _2)$. By Theorem 6, $C^K = C^{\kappa _1} \otimes C^{\kappa _2}$. It follows that $C^K$ is given by

$$\begin{aligned} C^K = \begin{pmatrix} 1 &{} 0 \\ 0 &{} (-1)^{\kappa _1} \end{pmatrix} \otimes \begin{pmatrix} 1 &{} 0 \\ 0 &{} (-1)^{\kappa _2} \end{pmatrix} = \begin{pmatrix} 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} (-1)^{\kappa _1} &{} 0 &{} 0 \\ 0 &{} 0 &{} (-1)^{\kappa _2} &{} 0 \\ 0 &{} 0 &{} 0 &{} (-1)^{\kappa _1 + \kappa _2} \end{pmatrix}. \end{aligned}$$

The fact that the correlation matrix of a constant addition is diagonal will be essential to motivate our definition of block cipher invariants in Sect. 4.    $\triangleright$

4 Block Cipher Invariants

The invariant subspace attack is based on the existence of an affine space which is mapped to itself by a block cipher. A nonlinear invariant is a set which is encrypted to itself or its complement. The purpose of this section is to define what it means for a “cryptanalytic property” to be invariant under a block cipher, and then to show that this definition includes the nonlinear invariant and invariant subspace attacks as special cases.

Let $F : \mathbb {F}_2^n \rightarrow \mathbb {F}_2^n$ be an arbitrary function – in particular, F need not be bijective. With invariant subspace attacks in mind, it is reasonable to ask which probability distributions are invariant under F. This is equivalent to determining all multisets which are mapped to themselves by F. The solutions to this problem are precisely the eigenvectors of the transition matrix of F which are also probability distributions. The main issue with this formulation is that, even for a simple function such as the addition of a constant, computing the eigenvectors of the transition matrix is not as trivial as one might hope.

To simplify matters, we will make a change of basis to the character basis of $\mathbb {C}[\mathbb {F}_2^n]$, which was introduced in Sect. 3. That is, we consider the eigenvectors of correlation matrices instead of transition matrices. This has the important advantage that the correlation matrix of a constant addition is a diagonal matrix. This is helpful, because the columns of a diagonal matrix also form a basis of eigenvectors.

One final simplification can be made before stating Definition 2: there is no good reason to consider only probability distributions – one can simply allow all eigenvectors. It will be shown in Sect. 4.1 that nonlinear invariants are examples of eigenvectors that are not Fourier transformations of probability distributions.

Definition 2

(Block cipher invariant). A vector $v \in \mathbb {C}^{2^n}$ is an invariant for a block cipher $E_k : \mathbb {F}_2^n \rightarrow \mathbb {F}_2^n$ iff it is an eigenvector of the correlation matrix $C^{E_k}$. If v is a multiple of $(1, 0, \ldots , 0)^T$, it will be called a trivial invariant.

This paper is only concerned with eigenvectors which correspond to real eigenvalues, i.e. $\pm 1$ due to Theorem 4. More generally, one could also have eigenvalues which are complex roots of unity. This will be discussed briefly in Sect. 8, which covers future work.

Not all vectors satisfying Definition 2 can be used in cryptanalysis. A sufficient condition for an invariant to be useful is that it depends only on part of the key, and that it comes with an efficient way of testing whether it holds for a given set of plaintext/ciphertext pairs. Section 4.1 shows that the latter requirement is usually not a problem.

Finally, note that some work related to Definition 2 can be found in the literature. Abdelraheem et al. [1] have observed that invariant subspaces correspond to eigenvectors of a submatrix of $C^{E_k}$. This can be seen to be a special case of Definition 2. Dravie et al. [12] give several results related to the spectrum of correlation matrices (not in the context of invariant attacks).

4.1 Nonlinear Invariants

The goal of this section is to establish the relation between Definition 2 and nonlinear invariants. Theorem 7 provides a general result to this end, but the simpler Corollary 1 is sufficient to obtain the desired relation. For the following results, the notation $e_0 = (1, 0, \ldots , 0)^T$ will be used.

Theorem 7

(Nonlinear invariant). Let $E_k : \mathbb {F}_2^n \rightarrow \mathbb {F}_2^n$ be a block cipher with correlation matrix $C^{E_k}$ and $f : \mathbb {F}_2^n \rightarrow \mathbb {F}_2$ a Boolean function with correlation matrix $(e_0~v)^T$. If v is an eigenvector of $C^{E_k}$ with eigenvalue $\lambda = \pm 1$, then for any random variable $\varvec{x}$ on $\mathbb {F}_2^n$, it holds that

$$\begin{aligned} \Pr {\left[ f(E_k(\varvec{x})) = 0\right] } - \frac{1}{2} = \lambda \left( \Pr {\left[ f(\varvec{x}) = 0\right] } - \frac{1}{2}\right) . \end{aligned}$$

(3)

Conversely, suppose (3) holds for a set of random variables $\varvec{x}_1, \ldots , \varvec{x}_m$ with probability distributions $p_{\varvec{x}_1}, \ldots , p_{\varvec{x}_m}$ such that $\mathrm {Span}\,\{p_{\varvec{x}_1}, \ldots , p_{\varvec{x}_m}\} = \mathbb {R}^{2^n}$. Then v is an eigenvector of $C^{E_k}$ with eigenvalue $\lambda$.

Proof

By the orthogonality of $C^{E_k}$, it holds that $\left[ C^{E_k} v\right] ^T \left[ C^{E_k} w\right] = v^T w$. Since $C^{E_k}v = \lambda v$ with $\lambda = \pm 1$, it follows that $\lambda v^T\left[ C^{E_k} w\right] = v^T w$ and hence $v^T\left[ C^{E_k} w\right] = \lambda v^T w$.

For any $\varvec{x}$, choose w as the Fourier transform of the probability mass function of $\varvec{x}$. Since $v^T\left[ C^{E_k}w\right] = \lambda v^Tw$, the correlations of $f(\varvec{x})$ and $f(E_k(\varvec{x}))$ are equal if $\lambda =1$ and opposite if $\lambda = -1$. To show the converse, extract a basis $\{w_1, \ldots , w_{2^n}\}$ for $\mathbb {R}^{2^n}$ from the vectors $\widehat{p}_{\varvec{x}_1}, \ldots , \widehat{p}_{\varvec{x}_m}$. From $v^T[C^{E_k}w_i] = \lambda v^Tw_i$, $i = 1, \ldots , 2^n$ it follows that $v^T C^{E_k} = \lambda v^T$. The result follows from the orthogonality of $C^{E_k}$.   $\square$

Theorem 7 has the following corollary, which gives the precise relation between the eigenvectors of $C^{E_k}$ and the nonlinear invariants of $E_k$ as defined by Todo, Leander and Sasaki [22].

Corollary 1

Let $E_k : \mathbb {F}_2^n \rightarrow \mathbb {F}_2^n$ be a block cipher with correlation matrix $C^{E_k}$ and $f : \mathbb {F}_2^n \rightarrow \mathbb {F}_2$ a Boolean function with correlation matrix $(e_0~v)^T$. v is an eigenvector of $C^{E_k}$ with eigenvalue $(-1)^c$, $c \in \mathbb {F}_2$ if and only if for all $x \in \mathbb {F}_2^n$, it holds that

$$\begin{aligned} f(x) + f(E_k(x)) = c. \end{aligned}$$

Proof

For any x, apply Theorem 7 to a random variable $\varvec{x}$ with probability distribution concentrated on x. For the converse, it suffices to note that the Fourier transforms of these probability distributions form a basis for $\mathbb {R}^{2^n}$.   $\square$

Finally, the following is a simple result that is useful to obtain the nonlinear invariant corresponding to an eigenvector v. Note that $\varvec{1}_{S}$ denotes the indicator function of a set S.

Theorem 8

Let S be any subset of $\mathbb {F}_2^n$ and let $p_1, p_2$ be functions¹ defined by $p_1(x) = 2^{-n}\varvec{1}_{S}$ and $p_2(x) = 2^{-n}\varvec{1}_{\mathbb {F}_2^n \setminus S}$ respectively. If $v \in \mathbb {F}_2^{n}$ is the difference of the Fourier transforms of $p_1$ and $p_2$, i.e., $v = \widehat{p}_2 - \widehat{p}_1$ then $\varvec{1}_{S}$ has correlation matrix $(e_0~v)^T$.

Proof

The (scaled) Walsh-Hadamard transform of $\varvec{1}_{S}$ is given by

$$\begin{aligned} \frac{1}{2^n}\sum _{x \in \mathbb {F}_2^n} (-1)^{\varvec{1}_{S}(x) + u^T x} = \frac{1}{2^n}\left[ \sum _{x \not \in S} (-1)^{u^T x} - \sum _{x \in S} (-1)^{u^T x}\right] = \widehat{p}_2(u) - \widehat{p}_1(u). \end{aligned}$$

   $\square$

Example 3

Consider the function $F : (x_1, x_2) \mapsto (x_2, x_1)$. It has correlation matrix

$$\begin{aligned} C^F = \begin{pmatrix} 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 &{} 0 \\ 0 &{} 1 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 1. \end{pmatrix}. \end{aligned}$$

The vector $2^{-1}\,(1, 1, 1, -1)^T = 2^{-2}\,[(3, 1, 1, -1)^T - \,(1, -1, -1, 1)^T]$ is an eigenvector of $C^F$. The corresponding nonlinear invariant is $f(x_1, x_2) = x_1x_2$.   $\triangleright$

4.2 Computing Invariants

In general, it is nontrivial to compute the invariants of a block cipher. This is in part due to large block sizes, and in part due to the key-dependence of the invariants. To avoid dependencies on the key, one could attempt to find invariants for parts of the block cipher that do not involve the key. The influence of the key addition can easily be checked afterwards. In fact, when working in the character basis, it only depends on the nonzero pattern of the invariant.

The problem is then reduced to computing the invariants of an unkeyed permutation $F : \mathbb {F}_2^n \rightarrow \mathbb {F}_2^n$. With Definition 2 in mind, one might consider using a standard numerical procedure to compute the eigenvectors of $C^F$. This is not a particularly efficient approach: the computational cost is $\mathcal {O}(2^{3n})$, which is of the same order as the ANF-based algorithm proposed by Todo et al. [22] to find nonlinear invariants.

In fact, due to the structure of the matrix $C^F$, its eigendecomposition can be computed using at most $\mathcal {O}(n 2^{2n})$ operations. The following algorithm generalizes the cycle structure approach which is mentioned by Todo et al. [22] as “potentially applicable”. One computes the cycle-decomposition of F. Then, for each cycle $(x_0, \dots , x_{l-1})$ and for each $0 \le j < l$, let $v^{(j)}$ be the Fourier transform of the uniform distribution on the singleton $\{x_j\}$. Let $\zeta = e^{2\pi \sqrt{-1}/l}$. For every $0 \le k < l$, one obtains an eigenvector² $w = \sum _{j = 0}^{l - 1} \zeta ^{-kj} v^{(j)}$ corresponding to the eigenvalue $\zeta ^k$:

$$\begin{aligned} C^Fw = \sum _{j = 0}^{l - 1} \zeta ^{-kj} C^F v^{(j)} = \sum _{j = 0}^{l - 1} \zeta ^{-k(j-1)} v^{(j)} = \zeta ^k w. \end{aligned}$$

This method obtains a complete eigenvector basis, since the sum of all cycle lengths is $2^n$.

Unfortunately, even the algorithm above is impractical for $n = 64$. To obtain invariants, it is thus necessary to exploit structural properties of the block cipher. Here, Definition 2 will be of use by facilitating a convenient description of invariants. Theorem 9 in Sect. 5 provides an example in the context of Midori-64.

The main structural property that has been exploited in previous work such as [15, 17, 22] is the existence of non-trivial simultaneous invariants for the linear layer and the nonlinear layer of a block cipher. In the first part of Sect. 5, this approach is briefly revisited from the point of view of Definition 2. Then, more general (i.e. not requiring simultaneous eigenvectors) invariants will be discussed. Note that the discussion in Sect. 5 will be tailored to the block cipher Midori-64.

5 Invariants for Midori-64

In this section, the invariants of Midori-64 are discussed in the correlation matrix framework. As an example, in Sect. 5.2 we recover the invariant subspace attack of Guo et al. [15] and the nonlinear invariant from Todo et al. [22]. Then, in Sect. 5.3, a more general invariant will be obtained. This invariant will be used in Sects. 6 and 7 to obtain practical attacks on (round reduced) Midori-64 and MANTIS.

Before proceeding with the computation of the invariants, it is necessary to analyze the structure of Midori-64 in more detail. Section 5.1 provides the necessary preliminaries.

5.1 State Representation and Round Transformations

In its most general form, the Fourier-domain representation of the Midori-64 state is a vector $v \in \mathbb {C}^{2^{64}}$. Recall from Sect. 2 that it is convenient to represent the Midori-64 state as a $4 \times 4$ array of 4-bit cells. For this reason, we will denote coordinate $u = (u_1, \ldots , u_{16})$ with $u_i \in \mathbb {F}_2^4$ of v by $v_u = v_{u_1, \ldots , u_{16}}$. This notation reflects the fact that we can think of v as a tensor of order 16, i.e. $v \in [\mathbb {C}^{2^4}]^{\otimes 16}$.

From Fig. 1, and by using Theorem 3, the correlation matrix of the Midori-64 round function is given by

$$\begin{aligned} C^{R_i} = C^{\kappa _i + \gamma _i}C^{\mathfrak M}C^PC^{\mathfrak S}, \end{aligned}$$

where $\kappa _i = K_0$ when i is odd and $K_1$ when i is even. Recall that $C^{\kappa _i + \gamma _i}$ is a diagonal matrix. It follows from Theorem 6 that $C^{\mathfrak S} = [C^S]^{\otimes 16}$ and $C^{\mathfrak M} = [C^M]^{\otimes 4}$. The matrix $C^S \in \mathbb {R}^{16 \times 16}$ is a symmetric orthogonal matrix and $C^M \in \mathbb {R}^{2^{16} \times 2^{16}}$ is a symmetric permutation matrix. Specifically, we have $C^M_{u, v} = \delta (u + Mv)$ by Theorem 5. Finally, $C^P$ is a permutation matrix such that $C^P v_{u_1, \ldots , u_{16}} = v_{u_{\pi ^{-1}(1)}, \ldots , u_{\pi ^{-1}(16)}}$ with $\pi$ the ShuffleCell permutation.³

It is convenient to look only for invariants with independent cells in the sense of Theorem 1 – but the reader should be reminded that the invariants need not be Fourier transforms of probability distributions. That is, we will assume that there exist vectors $v^{(1)}, \ldots , v^{(16)}$ such that

$$\begin{aligned} v_{u_1, \ldots , u_{16}} = \prod _{i = 1}^{16} v^{(i)}_{u_i}. \end{aligned}$$

(4)

Equivalently, $v = \otimes _{i = 1}^{16} v^{(i)}$. Of course, this assumption imposes a serious restriction. However, assuming (4) greatly simplifies the theory and is sufficiently general to recover the invariant attacks of Guo et al. [15] and Todo et al. [22]. Furthermore, more general assumptions are not necessary to obtain the invariant that will be presented in Sect. 5.3.

The invariants considered in Sect. 5.2 will be required to be invariant under $\mathfrak S$, $\mathfrak M$ and P. Consider the last requirement, i.e. v is an eigenvector of $C^P$. Recall that $C^P$ is a permutation matrix such that

$$\begin{aligned} C^P \bigotimes _{i = 1}^{16} v^{(i)} = \bigotimes _{i = 1}^{16} v^{(\pi ^{-1}(i))}. \end{aligned}$$

If v is symmetric, that is, $v^{(1)} = \cdots = v^{(16)} = \widetilde{v}$, then $\otimes _{i = 1}^{16} v^{(i)} = {\widetilde{v}}^{\otimes 16}$ is clearly invariant under $C^P$. It turns out that for the purpose of this paper, it suffices to consider only invariants v such that there exists some $\widetilde{v} \in \mathbb {C}^{16}$ such that

$$\begin{aligned} v_{u_1, \ldots , u_{16}} = \prod _{i = 1}^{16} \widetilde{v}_{u_i}. \end{aligned}$$

(5)

That is, $v = {\widetilde{v}}^{\otimes 16}$ and v will be called symmetric, in line with standard terminology for such tensors. Note that assumption (5), is less restrictive than (4). Indeed, for any realistic choice of round constants, an asymmetric invariant tends to lead to conflicting requirements on the key after a sufficient number of rounds. Slightly more general invariants can be obtained by requiring that $v^{(i)}$ is constant on the cycles of $\pi$.

Computing an eigenvector basis for $C^\mathfrak {S}$ is not difficult. In the remainder of this section, the eigenvectors of $C^\mathfrak {M}$ satisfying (4) and (5) will be listed. In particular, it is not necessary to compute these eigenvectors numerically. We begin with the straightforward result in Lemma 1. The main result is stated in Theorem 9.

Lemma 1

If $v^{\otimes 4}$ is a real eigenvector of $C^M$, then there exists a scalar $\alpha \in \mathbb {R}_0$ such that all coordinates of v in the standard basis are equal to 0 or $\pm \alpha$.

Proof

The condition that $v^{\otimes 4}$ is an eigenvector of $C^M$ is equivalent to

$$\begin{aligned} v^{\otimes 4}_{u_1, u_2, u_3, u_4} = \lambda v_{M(u_1, u_2, u_3, u_4)^T}^{\otimes 4}. \end{aligned}$$

Hence, we have for all $u_1, \dots , u_4 \in \mathbb {F}_2^4$ that

$$\begin{aligned} \prod _{i = 1}^4 v_{u_i} = \lambda \prod _{i = 1}^4 v_{\Sigma _{j \ne i} u_j}. \end{aligned}$$

(6)

Note that no vector of the form $v^{\otimes 4}$ can correspond to $\lambda = -1$, since it follows from (6) that $v_u^4 = \lambda v_u^4$. Suppose that at least one coordinate of v is nonzero, i.e. $v_u = \alpha$ for some u. By (6), this implies $\alpha v_{u'}^3 = \alpha ^3 v_{u'}$ for any $u' \in \mathbb {F}_2^4$. Consequently, $v_{u'} \in \{0, \pm \alpha \}$.   $\square$

Theorem 9

If $v^{\otimes 4}$ is a real eigenvector of $C^M$, then $\mathcal {A} = \{u~|~v_u \ne 0\}$ is an affine subspace of $\mathbb {F}_2^4$ and there exists a scalar $\alpha \in \mathbb {R}_0$ such that $v_u = \pm \alpha$ for all $u \in \mathcal {A}$. The converse is also true in the following cases:

• For $\dim {\mathcal {A}} = 0$, $\dim {\mathcal {A}} = 1$ and $\dim {\mathcal {A}} = 2$.

• For $\dim {\mathcal {A}} = 3$, provided that the number of negative coordinates of v is even.

The condition for $\dim {\mathcal {A}} = 3$ is also necessary.

Proof

Suppose $v^{\otimes 4}$ is a real eigenvector of $C^M$. Let $a, u, u' \in \mathbb {F}_2^4$ such that $v_a \ne 0$, $v_{a + u} \ne 0$ and $v_{a + u'} \ne 0$. By (6), we have

$$\begin{aligned} v_{a + u + u'}^2 v_{a + u'} v_{a + u} = v_a^2\, v_{a + u} v_{a + u'} \ne 0. \end{aligned}$$

Hence, $v_{a + u + u'} \ne 0$. It follows that $\mathcal {A}$ is an affine space. Lemma 1 completes the argument.

To show the converse, first consider the case $\dim \mathcal {A} \in \{0, 1, 2\}$. It suffices to demonstrate that if $u_1, \ldots , u_4 \in \mathcal {A}$, then $\prod _{i = 1}^4 v_{u_i} = \prod _{i = 1}^4 v_{\Sigma _{j \ne i} u_j}$. Note that $\{u_1, \dots , u_4\}$ and $\{\Sigma _{i \ne 1} u_i, \dots , \Sigma _{i \ne 4} u_i\}$ generate the same affine space. Since the dimension of this space is at most two, it contains at most four elements. Hence, both products contain the same factors.

For $\dim \mathcal A = 3$, the previous argument no longer applies when $u_1, \dots , u_4$ are linearly independent. In this case the left and right hand side of $\prod _{i = 1}^4 v_{u_i} = \prod _{i = 1}^4 v_{\Sigma _{j \ne i} u_j}$ involve different variables. Hence, since $\mathcal {A}$ contains eight elements, the products of these elements must be positive.   $\square$

The only symmetric rank one invariants which are not covered by Theorem 9 are those containing only nonzero entries. It would be possible to extend the result to cover this case as well, but this would have little practical value since such eigenvectors can never lead to a significant class of weak keys. This will become clear in Sect. 5.2.

5.2 Simultaneous Eigenvectors

As discussed in Sect. 4.2, it is not possible to find the eigenvectors of $C^{E_k}$ directly and to subsequently identify those vectors that depend only on a limited portion of the key. A more realistic approach is to find joint eigenvectors for all of the transformations in the round function. This corresponds to the strategy that is commonly used, and it is the strategy that will be applied in this section.

The problem considered in this section is thus to find vectors $v \in \mathbb {R}^{2^{64}}$ such that $[C^S]^{\otimes 16} v = \lambda v$ and $[C^M]^{\otimes 4} v = \mu v$ with $\lambda , \mu \in \{-1, 1\}$. Furthermore, v must be an eigenvector of $C^P$, but if v is symmetric, we need not separately consider this requirement. For each of these vectors v, we additionally require that they are eigenvectors of $C^{K + \gamma _i}$ for $i = 1, \ldots , 16$. In general, this is not possible without making some assumptions on the key K.

If $\{v_1, \ldots , v_{16}\}$ is a basis of eigenvectors of $C^S$, then the set of all vectors of the form $\otimes _{i = 1}^{16} v_{\ell _i}$ with $\ell _i \in \{1, \ldots , 16\}$ is a basis of eigenvectors of $[C^S]^{\otimes 16}$. Suppose that $E_{+1}^S$ is the eigenspace of $C^S$ corresponding to eigenvalue 1, and $E_{-1}^S$ likewise for eigenvalue $-1$. Any useful invariant must be an eigenvector of the diagonal matrices $C^{\kappa _i + \gamma _i}$ as well. That is, the invariants must be an element of one of the vector spaces listed in Table 1.

Table 1. Bases for the intersection of the eigenspaces of $C^S$ and $C^{\gamma _i}$.

The vectors $v^{\otimes 4}$ should additionally be eigenvectors of $C^M$. A necessary condition to this end is given by Theorem 9 (in fact, Lemma 1 is sufficient here). Using this result, only four nontrivial invariants of the form $v^{\otimes 16}$ remain. These are listed in Table 2. The first of these invariants satisfies the conditions of Theorem 8. It corresponds to the nonlinear invariant discovered by Todo, Leander and Sasaki [22].

Table 2. Invariants for Midori-64. Note that the last invariant is simply the nonlinear invariant corresponding to the second invariant (which is an invariant subspace).

Note that the weak-key class corresponding to a given invariant (the second column in Table 2), is readily determined from the vector v. For instance, consider the vector $C^\kappa v$, with $\kappa = (\kappa _1, \dots , \kappa _4)^T \in \mathbb {F}_2^4$ a single nibble of the round key:

$$\begin{aligned} v&= (0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, -1, 0, 0, 0, 1)^T, \\ C^\kappa v&= (-1)^{\kappa _3 + \kappa _4}(0, 0, 0, 1, 0, 0, 0, (-1)^{\kappa _2}, 0, 0, 0, (-1)^{1+\kappa _1}, 0, 0, 0, (-1)^{\kappa _1 + \kappa _2})^T. \end{aligned}$$

Hence, v is invariant under $C^\kappa$ provided that $\kappa _1 = \kappa _2 = 0$. Note that v is also invariant under the addition of the round constants – which has the same effect as modifying $\kappa _4$.

An alternative approach to finding invariants starts from the eigenvectors of $C^M$. Theorem 9 makes this method efficient. This will be the starting point to obtain more general invariants in Sect. 5.3.

5.3 Nonlinear Invariant for “Almost Midori-64”

In the previous section, a few eigenvectors of $C^{R_i}$ were obtained by intersecting the eigenspaces of $C^{\mathfrak M}$, $C^{\mathfrak S}$ and $C^{K + \gamma _i}$. In general the eigenvectors of $C^{R_i}$ are not eigenvectors of $C^{\mathfrak M}$ or $C^{\mathfrak S}$. Furthermore, the eigenvectors of $C^{E_k}$ need not be eigenvectors of the round functions $C^{R_i}$. In order to find all invariants, then, it would be necessary to solve the eigenvalue problem of Definition 2 directly. As discussed before, tackling this problem is out of the scope of this paper, but a slightly more general type of invariant for Midori-64 is presented in this section.

Figure 2 shows the general idea: it may be possible to find a vector $u^{\otimes 16}$ which is mapped to a vector $v^{\otimes 16}$ by $C^{R_i}$, such that $C^{R_{i+1}}v^{\otimes 16} = u^{\otimes 16}$. Such a vector $u^{\otimes 16}$ would be an eigenvector of $C^{R_{i+1}}C^{R_i}$, but not of $C^{R_i}$.

Fig. 2.

If $u \ne v$, this figure depicts an invariant for two rounds which is not invariant under one round.

To find such an invariant, it suffices to obtain vectors u and $v = C^Su$ such that $C^Mu^{\otimes 4} = u^{\otimes 4}$ and $C^Mv^{\otimes 4} = v^{\otimes 4}$. Theorem 9 provides a complete list of possible choices for u and v. This approach is formalized in Algorithm 1. This algorithm requires a negligible amount of time, as the inner loop is only executed 5216 times – once for each symmetric rank one invariant of $C^\mathfrak {M}$. Note that it also returns invariants of the conventional type.

A list of invariants produced by Algorithm 1 is given in Appendix A. The most interesting pair of vectors u, v is given by

$$\begin{aligned} u&= (0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)^T \\ v&= (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1/2, -1/2, 0, 0, 1/2, -1/2)^T. \end{aligned}$$

Clearly, u is invariant under the addition of any constant. For v, it holds that

$$\begin{aligned} C^{\kappa } v = (-1)^{\kappa _1 + \kappa _3}/2\cdot (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, (-1)^{1+\kappa _4}, 0, 0, (-1)^{\kappa _2}, (-1)^{1+\kappa _2+\kappa _4})^T, \end{aligned}$$

which is a multiple of v provided that $\kappa _2 = \kappa _4 = 0$. For the usual choice of round constants of Midori-64, v is not invariant under the addition of the constants. However, had the round constants been chosen as $\gamma _i \in \{\texttt {0}, \texttt {2}, \texttt {8}, \texttt {A}\}^{16}$ rather than $\gamma _i \in \{0, 1\}^{16}$, the attack would apply. Moreover, such a restriction only applies to half of the rounds – the round constants of other rounds may be chosen arbitrarily.

The restriction $\kappa _2 = \kappa _4 = 0$ (which applies to $K_0$ or $K_1$, but not both) corresponds to a class of $2^{96}$ weak keys. By Theorem 8, v corresponds to the following nonlinear invariant:

$$\begin{aligned} f(x_1, \ldots , x_{64}) = \sum _{i = 1}^{16} \left[ x_{4i}x_{4i-2} + x_{4i} + x_{4i-1} + x_{4i-3}\right] \end{aligned}$$

(7)

That is, there exists a constant $c \in \mathbb {F}_2$ such that $f(E_k(x)) + f(x) = c$ for all x and for any even number of rounds. By Theorem 8, u corresponds to the following “nonlinear” invariant:

$$\begin{aligned} g(x_1, \ldots , x_{64}) = \sum _{i = 1}^{16} \left[ x_{4i} + x_{4i-2}\right] . \end{aligned}$$

(8)

Hence, for an even number of rounds, $g(E_k(x)) + g(x)$ is constant. Note that if the number of rounds is odd, the value $f(E_k(x)) + g(x)$ is constant instead. Appendix B provides test code for this property.

5.4 Trail Clustering in Midori-64

It is worthwhile to take a closer look at the invariant g given by (8) in Sect. 5.3. Since g is a linear function, it corresponds to a linear hull with correlation $\pm 1$ (where the sign depends on the key). Considering the fact that Midori-64 has been designed with resistance to linear cryptanalysis in mind, this is remarkable.

Remark 1

The correlation of any trail in “almost Midori-64” is (much) smaller than $2^{-32}$, yet there is a linear hull with correlation $\pm 1$ for $2^{96}$ keys.

The correlation of a linear hull is equal to the sum of the correlations of all trails within the hull. It is well-established that, in theory, this sum could become large even if all terms are small. Such ideas go back to Nyberg [21]. Daemen and Rijmen [9] refer to this effect as trail clustering.

Remark 1 demonstrates an extreme case of trail clustering: the absolute correlation of the hull is not just large, it is maximal. This appears to be the first real-world observation of such behavior.

6 Practical Attack on 10 Rounds of Midori-64

The purpose of this section is to demonstrate that the invariant for “almost Midori-64” can be used even when the round constants are not modified. In fact, the attack in this section is valid for any choice of round constants.

Specifically, it will be shown that 10 rounds of Midori-64 are subject to a key-recovery attack that requires $1.25 \cdot 2^{21}$ chosen plaintexts and has a computational cost of $2^{56}$ block cipher calls. The downside of this attack is that it is limited to $2^{96}$ out of $2^{128}$ keys. Note that Midori-64 has been analyzed in several prior works. Lin and Wu [18] demonstrate meet-in-the-middle attacks on 10, 11 and 12 rounds of Midori-64. Chen and Wang [23] give a 10 round impossible differential cryptanalysis. The downside of those attacks is that they can not be executed in practice. Table 3 provides an overview of attacks on Midori-64.

Table 3. Overview of key-recovery attacks on Midori-64. Time is measured by the number of encryption operations. Memory is expressed in number of bytes.

The attack presented below is based on the observation that integral properties [16] and invariants can often be combined. However, since we allow arbitrary round constants in this section, the invariant can only be used once. In this regard the nonlinear invariant that was introduced in Sect. 5.3 has an important advantage: with one assumption on the key, it covers two rounds.

6.1 Nonlinear Property for 6 Rounds of Midori-64

This section shows that the two-round nonlinear invariant for Midori-64 can be extended to a six round nonlinear property. When a key which does not belong to the weak key class is added to the state, the vector corresponding to a nonlinear invariant will be mapped to another vector which only depends (up to a scale factor) on key bits that are already “known”, i.e. that had to be fixed to obtain the invariant in the first place. This holds in both the forward and backward direction, leading to a 6-round nonlinear property. This is illustrated in Fig. 3.

Fig. 3.

Nonlinear property over six rounds of Midori-64. The notation “$\simeq$” is used to indicate equality in the second and fourth bits of every nibble of each of its arguments.

The functions $h_1$ and $h_2$ in Fig. 3 depend on the choice of the round constants. Specifically, $h_1$ depends on $P^{-1}(\mathfrak {M}(\gamma _5 + \gamma _7))$ and $h_2$ depends on $\gamma _7 + \gamma _9$. For the purposes of this paper, a detailed description of $h_1$ is not necessary. For $h_2$, it holds that

$$\begin{aligned} h_2(x_1, \ldots , x_{64}) = \sum _{i = 1}^{16} f(S(x_{4i - 3}, x_{4i - 2}, x_{4i - 1}, x_{4i}) + \gamma _{7, i} + \gamma _{9, i}). \end{aligned}$$

In general, $h_j$ can be written in the form

$$\begin{aligned} h_j(x_1, \ldots , x_{64}) = \sum _{i = 1}^{16} h^{(\beta _{j, 2i}, \beta _{j, 2i+1})}(x_{4i}, x_{4i+1}, x_{4i+2}, x_{4i+3}), \end{aligned}$$

(9)

where $\beta _j \in \mathbb {F}_2^{32}$ is a constant depending on the round constants. In particular, $\beta _2$ consists of the second and fourth bits of every nibble of $\gamma _7 + \gamma _9$. For the default choice of round constants of Midori-64, $\beta _{j, 2i} = 0$. Hence, only two different Boolean functions can occur as terms in (9):

$$\begin{aligned} h^{(00)}(x_1, x_2, x_3, x_4)&= x_2 + x_4 \\ h^{(01)}(x_1, x_2, x_3, x_4)&= x_2 x_3 x_4 + x_1 x_3 x_4 + x_1 x_2 x_3 + x_1 x_4 + x_1 + x_2. \end{aligned}$$

Since the functions $h_1$ and $h_2$ are balanced on every cell of the state, it holds that $\sum _{x \in S} h_i(x) = 0$ with S a set of state values such that every cell takes all values exactly once. This makes it possible to combine integral cryptanalysis with the 6-round nonlinear property described above.

6.2 Integral Property for 4 Rounds of Midori-64

An integral attack on Midori-64 that is suitable for our purposes will now be given. The following notation will be used: cells taking all values an equal number of times are denoted using the label “A”, constant cells will be labeled by “C”. Subscripts are used to denote groups of values which jointly satisfy the “A” property. Note that cells can be part of several groups, e.g. a cell marked “$A_{i, j}$” is contained in groups i and j. The Midori-64 designers discuss the existence of a 3.5 round integral distinguisher. In fact, one can see that a 4-round integral property⁴ exists. Note that the property is nearly identical to the Rijndael distinguisher discussed by Knudsen and Wagner [16], the difference being that the property works better than expected for Midori-64.

Fig. 4.

First two rounds of the integral property for four rounds of Midori-64.

Fig. 5.

Last two rounds of the integral property for four rounds of Midori-64.

The integral property is based on a set of chosen ciphertexts such that the diagonal cells take all possible values exactly once and all other cells are constant. After one round, the same property then holds for the first column whereas all other cells are constant. This is shown in Fig. 4.

The effect of the remaining rounds is shown in Fig. 5. Figure 5 shows that, before the last application of $\mathfrak {M}$, any four distinct cells in a column jointly satisfy the “A” property. This implies that all cells can be labeled “A” after four rounds.

The derivation in Fig. 5 starts by forming appropriate groups of cells which are independent before the third round. Four (sometimes overlapping) groups of such cells are indicated using “$A_i$”, $i = 0, \dots , 3$ in Fig. 5. The maps $\mathfrak {S}$ and P preserve the groups. Furthermore, one can see that four new groups can be obtained after the application of $\mathfrak {M}$. These groups can be chosen in such a way that they are aligned in different columns of the state after P has been applied. The four round property then follows.

6.3 Combination of the Nonlinear and Integral Properties

The final attack can now be described. Figure 6 provides an overview. Let $\mathcal {I}$ denote a set of plaintext/ciphertext pairs with the structure required by the integral property from Fig. 4. Then, due to the nonlinear property from Fig. 3, the following holds:

$$\begin{aligned} \sum _{(P, C) \in \mathcal {I}} h_2(C + K_0 + K_1) = \sum _{(P, C) \in \mathcal {I}} h_1((R_4 \circ \cdots \circ R_1)(P + K_0 + K_1)) = 0. \end{aligned}$$

Hence, every set $\mathcal {I}$ defines a low-degree nonlinear polynomial equation in (part of) $K_0 + K_1$. Given enough such equations, one observes that a Gröbner basis for the ideal generated by these polynomials can be efficiently (within a second on a regular computer) computed. Although computing Gröbner bases is hard in general, it is easy in this case due to the fact that key bits from different cells are never multiplied together.

Note that only those key bits which are involved in $h_2$ in a nonlinear way can be recovered by solving the system of polynomial equations. That is, the number of key bits recovered is four times the number of nonlinear terms in (9). For the default Midori-64 round constants, 40 key bits can be recovered. This requires $40 \cdot 2^{16} = 1.25 \cdot 2^{21}$ chosen plaintexts.

The remaining 24 bits of $K_0 + K_1$ can be guessed, along with the 32 unknown bits in $K_0$. This requires $2^{56}$ block cipher calls. Note that this additional work is only necessary after it has been established that a weak key is used. Hence, an attacker in the multi-key setting has a very efficient method to identify potential targets.

Fig. 6.

Overview of the attack on 10 rounds of Midori-64.

7 Practical Attack on MANTIS-4

This section presents an attack on the block cipher MANTIS [4], which is closely related to Midori-64. Dobraunig, Eichlseder, Kales and Mendel give a practical attack against MANTIS-5 in the chosen tweak setting [11]. This attack has been extended to six rounds by Eichlseder and Kales [13]. The attack presented in this section is limited to MANTIS-4, but the assumptions about the capabilities of the attacker are different. The attacker is not allowed to choose the tweak, but it is assumed that a weak tweak is used. It will be shown that for every choice of the key, there are $2^{32}$ (out of $2^{64}$) weak tweaks. When a weak tweak is used, the full key can be recovered from (on average) 640 chosen plaintexts and with a computational cost of approximately $2^{56}$ block cipher calls.

Figure 7 illustrates the overall structure of MANTIS-4. Unlike in Midori-64, the round key $K_1$ is the same in all rounds. Additional whitening keys $K_0$ and $K_0^\prime = (K_0 \ggg 1) + (K_0 \gg 63)$ are added before the first round and after the last round. The round function is nearly identical to the Midori-64 round function, the difference being that the round keys and constants are added before rather than after the application of $\mathfrak {M}$. Hence, the 2-round nonlinear invariant for Midori-64 also applies to MANTIS-4. Note that the values of the round constants $\mathrm {RC}_1, \ldots , \mathrm {RC}_4$ are not essential to the attack described here.

Structurally, MANTIS differs from Midori-64 in two major aspects: it takes an additional tweak as an input, and it is a reflection cipher. In every round, the tweak is permuted cellwise by a permutation $\sigma$. In all other aspects, the tweak is treated in the same way as the round key $K_1$. The reflection property will make it be possible to extend the 6-round nonlinear property of Midori-64 to eight rounds. The presence of a tweak allows mounting a weak tweak rather than a weak key attack, which corresponds to a significantly weaker adversarial model.

Fig. 7.

Overview of MANTIS-4.

An overview of the attack is shown in Fig. 8. As in the attack on Midori-64 from Sect. 6, a few initial rounds are covered by an integral property. Since the nonlinear property extends over eight rounds for MANTIS, it suffices to use a weaker integral property. Figure 9 shows the property that will be used. It requires 16 chosen plaintexts.

Fig. 8.

Nonlinear property over eight rounds of MANTIS-4. The notation “$\simeq$” is used to indicate equality in the second and fourth bits of every nibble of each of its arguments.

Fig. 9.

Integral property for two rounds of MANTIS.

The nonlinear property is similar to the property that was discussed in Sect. 6, but slightly more complicated. Specifically, due to the tweak-key schedule, the functions $h_1$ and $h_2$ can depend on the tweak. As for Midori-64, $h_1$ and $h_2$ can be written in the form

$$\begin{aligned} h_j(x_1, \dots , x_{64}) = \sum _{i = 1}^{16} h^{(\beta _{j, 2i}, \beta _{j, 2i+1})}(x_{4i}, x_{4i+1}, x_{4i+2}, x_{4i+3}), \end{aligned}$$

(10)

where $\beta _j = (\beta _{j, 1}, \dots , \beta _{j, 32}) \in \mathbb {F}_2^{32}$ is a constant that possibly depends on the tweak and the functions $h^{(\beta _{j, 2i}, \beta _{j, 2i+1})}$ are given by

$$\begin{aligned} h^{(00)}(x_1, x_2, x_3, x_4)&= x_1 + x_2 \\ h^{(11)}(x_1, x_2, x_3, x_4)&= x_1 x_3 + x_2 + x_3 + x_4 \\ h^{(01)}(x_1, x_2, x_3, x_4)&= x_1 x_2 x_3 + x_1 x_2 x_4 + x_2 x_3 x_4 + x_1 x_4 + x_3 + x_4 \\ h^{(10)}(x_1, x_2, x_3, x_4)&= x_1 x_2 x_3 + x_1 x_2 x_4 + x_2 x_3 x_4 + x_1 x_4 + x_1 x_3 + x_1 + x_2 + x_3. \end{aligned}$$

Note that all of these functions are balanced. The constant $\beta _1$ consists of the second and fourth bits of every nibble of $\alpha$. For convenience, this will be denoted by $\beta _1 \simeq \alpha$. For $\beta _2$, we have $\beta _2 \simeq \mathrm {RC}_1 + \alpha + K_1 + \sigma (T)$. This implies that

$$\begin{aligned} \beta _2 \simeq \mathrm {RC}_1 + \mathrm {RC}_3 + \sigma (T) + \sigma ^3(T). \end{aligned}$$

Let $\mathcal {I}$ denote a set of plaintext/ciphertext pairs such that the plaintexts have the structure required by the integral property, then

$$\begin{aligned} \sum _{(P, C) \in \mathcal {I}} h_2(C + K_0^\prime + K_1 + T + \alpha ) = \sum _{(P, C) \in \mathcal {I}} h_1(R_1(R_2(P + K_0 + K_1 + T))) = 0. \end{aligned}$$

Hence, each set $\mathcal {I}$ corresponds to a low-degree polynomial equation in (part of) the key. As in Sect. 6, a Gröbner basis for the ideal generated by these polynomials can be efficiently computed.

As in the attack on Midori-64, only those key bits which are involved in $h_2$ in a nonlinear way can be recovered by solving the system of polynomial equations. For simplicity, assume that the functions $h^{(00)}$, $h^{(01)}$, $h^{(10)}$ and $h^{(11)}$ all occur as terms in (10) in the same proportion. Then the expected number of key bits that can be recovered by solving the system of polynomial equations is equal to 40.⁵ For obtaining 40 key bits, it was observed that 40 equations are sufficient. This requires $2^4 \cdot 40 = 640$ chosen plaintexts.

The remaining bits of the whitening key $K_0^\prime + K_1$ (24 bits on average) can then be guessed, along with the 32 unknown bits of $K_1$. For each such guess, it is possible to compute $K_0^\prime$ (since $K_0^\prime + K_1$ is already known) and hence $K_0$. No additional plaintext/ciphertext pairs are necessary to carry out this process. Hence, the work required for the entire key-recovery attack is then roughly $2^{56}$ block cipher calls.

8 Future Work

Returning to Definition 2, one potentially interesting direction for future work is the use of complex eigenvalues. The corresponding eigenvectors are related to real invariants of $[C^{E_k}]^l$ with l the order of the corresponding eigenvalue. If l is not too large, then such invariants might lead to additional attacks.

Another topic that deserves more attention is the development of practical methods to compute an eigenvector basis for the correlation matrix of the entire round function. Even if this does not lead to new attacks, it could be a tool for designers to demonstrate security with respect to attacks based on invariants.

Yet another direction for future work is to improve and extend the attack on 10 rounds of Midori-64 from Sect. 6 and the attack on MANTIS-4 from Sect. 7.

9 Conclusion

The three problems mentioned in the introduction have been addressed. In Sect. 4, a new theory of block cipher invariants was developed. Beside providing the foundation for the remainder of the paper, Definition 2 provides insight and uncovers several directions for future research. Section 5 provides a detailed analysis of invariants in Midori-64, leading to a new class of $2^{96}$ weak keys when minor modifications to the round constants are made. It was shown that this invariant is equivalent to a linear hull with maximal correlation. Finally, Sects. 6 and 7 illustrate the importance of invariants, even when round constants initially seem to limit their applicability. Two practical attacks were described: (1) a key-recovery attack on 10-round Midori-64 for $2^{96}$ weak keys, requiring $1.25 \cdot 2^{21}$ chosen plaintexts (2) a key-recovery attack on MANTIS-4 with an average data complexity of 640 chosen plaintexts.

Appendices

A List of Invariants Produced by Algorithm 1

See Table 4.

Table 4. Invariants for two rounds of (modified) Midori-64, as obtained using Algorithm 1. Only invariants with at least $2^{64}$ weak keys are listed. Note that these invariants are not valid for all choices of the round constants. The label “type I” refers to invariants with $u = v$, whereas “type II” indicates that $u \ne v$. Note that not all of these invariants are linearly independent.

B Test Code for Nonlinear Invariant from Sect. 5.3

The following code was tested using Sage 8.1.