Contemporary Mathematics

Volume XXX, 2008

Cellular Automata in Stream Ciphers

Amparo F´uster-Sabater

Abstract. A wide family of nonlinear sequence generators, the so-called clock-

controlled shrinking generators, has been analyzed and identiﬁed with a subset

of linear cellular automata. The algorithm that converts the given generator

into a linear model based on automata is very simple and can be applied in a

range of practical interest. Due to the linearity of these automata as well as

the characteristics of this class of generators, a cryptanalytic approach can be

proposed. Linear cellular structures easily model keystream generators with

application in stream cipher cryptography.

1. Introduction

Cellular Automata (CA) are particular forms of ﬁnite state machines that can

be investigated by the usual analytic techniques ([10], [17], [19], [25]). CA have

been used in application areas so diﬀerent as physical system simulation, biologi-

cal process, species evolution, socio-economical models or test pattern generation.

They are deﬁned as arrays of identical cells in an n-dimensional space and char-

acterized by diﬀerent parameters [26]: the cellular geometry, the neighborhood

speciﬁcation, the number of contents per cell and the transition rule to compute

the successor state. Their simple, modular and cascable structure makes them very

attractive for VLSI implementations.

On the other hand, Linear Feedback Shift Registers (LFSRs) [11] are linear

structures currently used in the generation of pseudorandom sequences. The in-

herent simplicity of LFSRs, their ease of implementation and the good statistical

properties of their output sequences turn them into natural building blocks for the

design of pseudorandom sequence generators with applications in spread-spectrum

communications, circuit testing, error-correcting codes, numerical simulations or

cryptography.

In recent years, one-dimensional CA have been proposed as an alternative to

LFSRs ([2], [3], [19], [26]) in the sense that every sequence generated by a LFSR can

1991 Mathematics Subject Classiﬁcation. Primary 40B05, 40C05; Secondary 68R01.

Key words and phrases. Cellular automata, clock-controlled generators, sequence reconstruc-

tion, cryptography.

Work supported by Ministerio de Educaci´ on y Ciencia (Spain) Projects SEG2004-02418 and

SEG2004-04352-C04-03.

2008 American Mathematical Society

1

Contemporary Mathematics

Volume 477 , 2009

cc 2009 American Mathematical Society

1

http://dx.doi.org/10.1090/conm/477/09301

Volume XXX, 2008

Cellular Automata in Stream Ciphers

Amparo F´uster-Sabater

Abstract. A wide family of nonlinear sequence generators, the so-called clock-

controlled shrinking generators, has been analyzed and identiﬁed with a subset

of linear cellular automata. The algorithm that converts the given generator

into a linear model based on automata is very simple and can be applied in a

range of practical interest. Due to the linearity of these automata as well as

the characteristics of this class of generators, a cryptanalytic approach can be

proposed. Linear cellular structures easily model keystream generators with

application in stream cipher cryptography.

1. Introduction

Cellular Automata (CA) are particular forms of ﬁnite state machines that can

be investigated by the usual analytic techniques ([10], [17], [19], [25]). CA have

been used in application areas so diﬀerent as physical system simulation, biologi-

cal process, species evolution, socio-economical models or test pattern generation.

They are deﬁned as arrays of identical cells in an n-dimensional space and char-

acterized by diﬀerent parameters [26]: the cellular geometry, the neighborhood

speciﬁcation, the number of contents per cell and the transition rule to compute

the successor state. Their simple, modular and cascable structure makes them very

attractive for VLSI implementations.

On the other hand, Linear Feedback Shift Registers (LFSRs) [11] are linear

structures currently used in the generation of pseudorandom sequences. The in-

herent simplicity of LFSRs, their ease of implementation and the good statistical

properties of their output sequences turn them into natural building blocks for the

design of pseudorandom sequence generators with applications in spread-spectrum

communications, circuit testing, error-correcting codes, numerical simulations or

cryptography.

In recent years, one-dimensional CA have been proposed as an alternative to

LFSRs ([2], [3], [19], [26]) in the sense that every sequence generated by a LFSR can

1991 Mathematics Subject Classiﬁcation. Primary 40B05, 40C05; Secondary 68R01.

Key words and phrases. Cellular automata, clock-controlled generators, sequence reconstruc-

tion, cryptography.

Work supported by Ministerio de Educaci´ on y Ciencia (Spain) Projects SEG2004-02418 and

SEG2004-04352-C04-03.

2008 American Mathematical Society

1

Contemporary Mathematics

Volume 477 , 2009

cc 2009 American Mathematical Society

1

http://dx.doi.org/10.1090/conm/477/09301