Linear structures in blockciphers

From MaRDI portal





A blockcipher is a mapping \(F\colon \mathbb{F}^m_2\times \mathbb{F}^k_2\to \mathbb{F}^m_2\) (where \(\mathbb{F}^m_2\) and \(\mathbb{F}^k_2\) are called the message space and key space, respectively), such that for every \(\underbar{k}\) in \(\mathbb{F}^k_2\), the mapping \(F_{\underline{k}}(\cdot,\underline{k})\colon \mathbb{F}^m_2\to \mathbb{F}^m_2\) is one-to-one. A well-known example of a blockcipher is the Data Encryption Standard (DES) with message space \(\mathbb{F}_2^{64}\) and key space \(\mathbb{F}_2^{56}\). A blockcipher \(F\) can be used as a conventional cryptosystem only if it can not be broken by a fast known- or chosen plaintext attack, that means that for every plaintext \(\underbar{p}\) and corresponding ciphertext \(\underbar{c}\), it should be infeasible to solve the unknown key \(\underbar{k}\) from \(F\((\underbar{p},\underbar{k})=\underline{c}\), even if \(\underbar{p}\) is chosen in a special way. In the paper, the notion of a linear structure in a blockcipher is introduced. A blockcipher has a linear structure if there are subsets \(P\), \(K\) and \(C\) of plaintext bits, key bits and ciphertext bits of this blockcipher, respectively, with the following property: either for each plaintext and each key, a simultaneous change of all plaintext bits in \(P\) and key bits in \(K\) leaves the exclusive-or sum of the ciphertext bits in \(C\) unchanged; or for each plaintext and key, simultaneously changing all plaintext bits in \(P\) and all key bits in \(K\) causes a change of the exclusive-or sum of the ciphertext bits in \(C\). The class of linear structures includes, among other things, the complementation property of DES and structures previously introduced by \textit{J. A. Reeds} and \textit{J. L. Manferdelli} [Lect. Notes Comput. Sci. 196, 377--389 (1985; Zbl 1359.94620)] and \textit{D. Chaum} and the author [Crypto 1985, Lect. Notes Comput. Sci. 218, 199--211 (1986; Zbl 0592.94009)]. It is proved that for blockciphers with linear structures there exists known- and chosen plaintext attacks faster than the trivial attack of trying all keys. Further, linear structures in product ciphers (these are compositions of easily breakable blockciphers, so-called rounds) are investigated. A method is described to construct linear structures in the whole product cipher from linear structures in the separate rounds; linear structures in the product cipher that can be constructed in this way are called recursive over its rounds. It is proved that the product cipher DES has no other recursive linear structure than its complementation property. [For the entire collection see Zbl 0635.00022.]




Cited in
(40)








This page was built for publication: Linear structures in blockciphers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3809719)