Cryptanalysis of a partially known cellular automata cryptosystem

Cellular automata provide simple discrete deterministic mathematical models for physical, biological, and computational systems. Despite their simple construction, cellular automata are shown to be capable of complicated behavior and to generate complex and random patterns. There have been constant efforts to exploit cellular automata for cryptography since the very beginning of the research on cellular automata. Unfortunately, most of the previous cryptosystems based on cellular automata are either insecure or inefficient. In ICICS' 02, Sen et al. made a new effort in cellular automata cryptosystems (CACs) design, where the affine cellular automata are combined with nonaffine transformations. It is claimed that the weakness in some of the previous CACs due to the affine property is removed. In this paper, we show that the new CAC is still insecure. It can be broken by a chosen-plaintext attack. The attack is very efficient, requiring only hundreds of chosen plaintexts and a small computation amount. We also consider the possibility of modifying the new CAC. Our results show, however, that it is not easy to secure the scheme by minor modifications.