Algebraic properties of the operations used in block cipher idea

Thesis Type: Doctorate

Institution Of The Thesis: Orta Doğu Teknik Üniversitesi, Institute of Applied Mathematics, Turkey

Approval Date: 2007




In this thesis we obtain several interesting algebraic properties of the operations used in the block cipher IDEA which are important for cryptographic analyzes. We view each of these operations as a function from $\mathbb Z_{2}^n \times \mathbb Z_{2}^n \to \mathbb Z_{2}^n$. By fixing one of variables $v(z)=\mathbf Z$ in $\mathbb Z_{2}^n \times \mathbb Z_{2}^n$, we define functions $\mathbf {f}_z$ and $\mathbf {g}_z$ from $\mathbb Z_{2}^n$ to $\mathbb Z_{2}^n$ for the addition $\BIGboxplus$ and the multiplication $\BIGodot$ operations, respectively. We first show that the nonlinearity of $\mathbf {g}_z$ remains the same under some transformations of $z$. We give an upper bound for the nonlinearity of $\mathbf {g}_{2^k}$, where $2\leq k < n-1$. We list all linear relations which make the nonlinearity of $\mathbf {f}_z$ and $\mathbf {g}_z$ zero and furthermore, we present all linear relations for $\mathbf {g}_z$ having a high probability. We use these linear relations to derive many more linear relations for 1-round IDEA. We also devise also a new algorithm to find a set of new linear relations for 1-round IDEA based on known linear relations. Moreover, we extend the largest known linear class of weak keys with cardinality $2^{23}$ to two classes with cardinality $2^{24}$ and $2^{27}$. Finally, we obtain several interesting properties of the set $ \{ ({\mathbf X},{\mathbf X} \BIGoplus {\mathbf A}) \in \mathbb Z_2^n \times \mathbb Z_2^n \,I\, (\mathbf {X}\BJoin {\mathbf Z})\BIGoplus( ({\mathbf X} \BIGoplus {\mathbf A} ) \BJoin \mathbf {Z} ) = {\mathbf B} \}$ for varying ${\mathbf A}, {\mathbf B}$ and ${\mathbf Z}$ in $\mathbb Z_2^n$, where $\BJoin \in \{ \BIGodot,\BIGboxplus \}$. By using some of these properties, we present impossible differentials for 1-round IDEA and Pseudo-Hadamard Transform.