Paper 2006/168

How Fast can be Algebraic Attacks on Block Ciphers ?

Nicolas T. Courtois

Abstract

In this paper we give a specification of a new block cipher that can be called the Courtois Toy Cipher (CTC). It is quite simple, and yet very much like any other known block cipher. If the parameters are large enough, it should evidently be secure against all known attack methods. However, we are not proposing a new method for encrypting sensitive data, but rather a research tool that should allow us (and other researchers) to experiment with algebraic attacks on block ciphers and obtain interesting results using a PC with reasonable quantity of RAM. For this reason the S-box of this cipher has only 3-bits, which is quite small. Ciphers with very small S-boxes are believed quite secure, for example the Serpent S-box has only 4 bits, and in DES all the S-boxes have 4 output bits. The AES S-box is not quite as small but can be described (in many ways) by a very small systems of equations with only a few monomials (and this fact can also be exploited in algebraic cryptanalysis). We believe that results on algebraic cryptanalysis of this cipher will have very deep implications for the security of ciphers in general.

Note: Work in progress. To summarize the main results: it is the first time in the history, that a block cipher with no special algebraic structure and with a (very) large number of S-boxes is being broken in practice by an algebraic attack.

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
algebraic cryptanalysisAESSerpent
Contact author(s)
courtois @ minrank org
History
2006-05-18: revised
2006-05-16: received
See all versions
Short URL
https://ia.cr/2006/168
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/168,
      author = {Nicolas T.  Courtois},
      title = {How Fast can be Algebraic Attacks on Block Ciphers ?},
      howpublished = {Cryptology ePrint Archive, Paper 2006/168},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/168}},
      url = {https://eprint.iacr.org/2006/168}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.