Abstract:
The theory of linear cryptanalysis is revisited and generalized in light of recent developments in symmetric-key cryptography. Trade-offs in the design of lightweight cryptographic primitives have enabled new attacks such as block cipher invariants, and have renewed the interest in long-standing problems such as the effective use of nonlinear approximations in cryptanalysis. These developments are intrinsically related to linear cryptanalysis in the weak key model. In addition, permutation-based cryptography – which is based on keyless primitives – is gaining traction. In response to these urgent tendencies, the present thesis develops a pervasive generalization of linear cryptanalysis. The proposed “geometric approach” enables a uniform treatment of many variants of the classical linear attack and is suitable for use in the keyless and weak key models of analysis. The new framework additionally facilitates novel extensions to linear cryptanalysis. Furthermore, it is applied to resolve problems related to the use of nonlinear approximations. As a further contribution, the problem of proving security against linear cryptanalysis is revisited in the weak key model.
The full text can be downloaded here.
Source code:
Riemannian optimization for Midori-64. Requires Python 3 and Pymanopt.
Nonlinear approximations in Midori-64. Requires Sage and the file midori_mixcolumn.sobj.
Errata for the printed version:
In the first sentence following Lemma 2.1 on page 12, \(x_{i + 1} = F_i(x_i)\) as opposed to \(x_{i + 1} = F(x_i)\).
In equation (2.3) and the preceding paragraph on page 13, \(u\) and \(v\) should be interchanged. Also, \(v \in \mathbb{F}_2^m\) as opposed to \(v \in \mathbb{F}_2^n\).
In Definition 3.1 (page 28), 3, \(\sigma_d > 0\) should be replaced by \(\sigma_d \ge 0\).
In Theorem 3.3 (page 30), it is preferable to denote the independent variable in the second equation using \(\chi \in \widehat{G}\).
In Defintion 3.5 (page 33), the principal correlations should be defined as the singular values of \(\mathscr{T}^F_{\mathcal U, \mathcal V}\). When \(F\) is a permutation, these are the same as the principal correlations between \(\mathcal{U}\) and \(T^{F}\mathcal{V}\) in the sense of Definition 3.1. However, in general, there is a difference. This difference can be elimiated by using a slightly different definition of `approximation map’.
In the example near the top of page 36, \(|G|\) should be replaced by \(|X|\).
In Corollary 3.2 (page 39), the error term in the nonorthogonal case should be \(V_r^\ast\,E\,V_0\) as opposed to \(E\).
In Definition 3.8 (page 41), \(\mathcal{V} \subseteq T^F \mathcal{V}\) should be \(T^F \mathcal{V} \subseteq \mathcal{V}\) instead.
In the last equation on page 47, several primes are missing (\(k_i\) rather than \(k_i'\)).
On page 48, the first sentence should say \(K_2 \in (\mathbb{F}_2^4 \setminus \mathcal K) \times \mathcal K^3\). Similarly, in the next two paragraphs on that page, \(K_1\) should be replaced by \(K_2\). The same error also appears on page 50 (first sentence of 3.4.3).
On page 52, the last item in the enumeration should be labeled by a dash as the others.
On page 54, the words “one can” are duplicated in “one can split this nonlinear approximation …”.
The reference to Serre’s book Linear Representations of Finite Groups appears twice (as [92] and [93]).