Algebraic Methods in Block Cipher Cryptanalysis

This thesis is a contribution to the field of algebraic cryptanalysis. Specifically the following topics have been studied: We construct and analyze Feistel and SLN ciphers that have a sound design strategy against linear and differential cryptanalysis. The encryption process for these cipher can be described by very simple polynomial equations. For a block and key size of 128 bits, we present ciphers for which practical Gröbner Basis Attacks can recover the full cipher key for up to 12 rounds requiring only a minimal number of plaintext/ciphertext pairs. We show how Gröbner bases for a subset of these ciphers can be constructed with negligible computational effort. This reduces the key-recovery problem to a Gröbner basis conversion problem. By bounding the running time of a Gröbner basis conversion algorithm, FGLM, we demonstrate the existence of block ciphers resistant against differential and linear cryptanalysis but vulnerable against Gröbner basis attacks. A paper on this subject has been published in the "Proceedings of The Cryptographers' Track at the RSA Conference 2006 (CT-RSA 2006)". We demonstrate an efficient method for computing a Gröbner basis of a zero-dimensional ideal describing the key-recovery problem from a single plaintext/ciphertext pair for the full AES-128. This Gröbner basis is relative to a degree-lexicographical order. We investigate whether the existence of this Gröbner basis has any security implications for the AES. This result has been published in the "Revised Selected Papers of the Fast Software Encryption Workshop 2006 (FSE 2006)". SMS4 is a 128-bit block cipher used in the WAPI standard for providing data confidentiality in wireless networks. For this cipher we explain how to construct a extension field embedding similar to BES, and demonstrate the fragility of the cipher design by giving variants that exhibit 2^{64} weak keys. These results have been published in the "Proceedings of Information Security and Privacy, 12th Australasian Conference (ACISP 2007)''. Cryptomeria is a 64-bit block cipher with a 56-bit key used in the CPRM / CPPM standard for content protection on DVD Audio discs, Video DVD-Rs and SD cards. The design of this cipher is public, the S-Box - which is application-specific - is treated as a trade secret which needs to be licensed from the 4C Entity, Inc. We show how for Cryptomeria and similarly structured ciphers the S-Box can be recovered in a chosen-key setting by a combination of differential and algebraic methods. This attack has been practically validated against reduced round versions of Cryptomeria. This is unpublished work. We look into Gröbner bases algorithms which use linear algebra methods. Because these algorithms are extremely memory-hungry, we have developed strategies for implementing the reduced row-echelon computation efficiently on distributed memory systems. We give an algorithm to efficiently tackle this problem in the dense case and discuss the sparse case. A extended abstract on this subject has been submitted to and accepted at "The First International Conference on Symbolic Computation and Cryptography (SCC 2008)"