Algebraic Cryptanalysis of Kahkeshan Block Cipher

Algebraic cryptanalysis is a general attack in which a cryptosystem is broken by solving a system of multivariate equations over a finite field (e.g. GF (2)) that describes the whole cryptosystem. In this paper we investigate the resistance of Kahkeshan block cipher against algebraic cryptanalysis. One of the most effective algorithms used for applying algebraic attacks on block ciphers is XSL algorithm. Our results of applying this algorithm to realize the attack on 8-round and 10-round Kahkeshan indicate a significant decrease in the complexity of the attack by the factor 2119 in comparison with the complexity of differential attack on 8-round Kahkeshan; and by the factor 271 as compared with that of boomerang attack on 10-round Kahkeshan, which have already been reported in the open literatures.

Keywords:

Kahkeshan block cipher , S-box , Algebraic Cryptanalysis , XSL algorithm