International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Block ciphers sensitive to Groebner Basis Attacks

Authors:
Johannes Buchmann
Andrei Pychkine
Ralf-Philipp Weinmann
Download:
URL: http://eprint.iacr.org/2005/200
Search ePrint
Search Google
Abstract: We construct and analyze Feistel and SPN ciphers that have a sound design strategy against linear and differential attacks but for which the encryption process can be described by very simple polynomial equations. For a block and key size of 128 bits, we present ciphers for which practical Groebner basis attacks can recover the full cipher key requiring only a minimal number of plaintext/ciphertext pairs. We show how Groebner bases for a subset of these ciphers can be constructed with neglegible computational effort. This reduces the key recovery problem to a Groebner basis conversion problem. By bounding the running time of a Groebner basis conversion algorithm, FGLM, we demonstrate the existence of block ciphers resistant against differential and linear cryptanalysis but vulnerable against Groebner basis attacks.
BibTeX
@misc{eprint-2005-12536,
  title={Block ciphers sensitive to Groebner Basis Attacks},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / cryptanalysis, block ciphers, algebraic attacks, Groebner bases},
  url={http://eprint.iacr.org/2005/200},
  note={ weinmann@cdc.informatik.tu-darmstadt.de 12961 received 27 Jun 2005},
  author={Johannes Buchmann and Andrei Pychkine and Ralf-Philipp Weinmann},
  year=2005
}