Paper 2005/200

Block ciphers sensitive to Groebner Basis Attacks

Johannes Buchmann, Andrei Pychkine, and Ralf-Philipp Weinmann

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
cryptanalysisblock ciphersalgebraic attacksGroebner bases
Contact author(s)
weinmann @ cdc informatik tu-darmstadt de
History
2005-06-29: received
Short URL
https://ia.cr/2005/200
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/200,
      author = {Johannes Buchmann and Andrei Pychkine and Ralf-Philipp Weinmann},
      title = {Block ciphers sensitive to Groebner Basis Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2005/200},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/200}},
      url = {https://eprint.iacr.org/2005/200}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.