Algebraic Attacks on Clock-Controlled
Stream Ciphers
by

Sultan Zayid Mohammed Al-Hinai
Bachelor of Science (In Physics) (Strathclyde University- Glasgow -Scotland) – 2000
Master of Science (In Information Security) (Royal Holloway University of London ) – 2002

Thesis submitted in accordance with the regulations for the Degree of
Doctor of Philosophy

Information Security Institute
Faculty of Information Technology
Queensland University of Technology

November 6, 2007



Keywords
Stream Ciphers, Linear Feedback Shift Registers, Non Linear Feedback Shift Registers, Regular Clocking, Irregular Clocking, Clock-Controlled, Algebraic Attacks, Fast Algebraic Attacks.

i


ii


Abstract
Stream ciphers are encryption algorithms used for ensuring the privacy of digital telecommunications.
They have been widely used for encrypting military communications, satellite communications, pay TV

encryption and for voice encryption of both fixed lined and wireless networks. The current multi year
European project eSTREAM, which aims to select stream ciphers suitable for widespread adoptation,
reflects the importance of this area of research.
Stream ciphers consist of a keystream generator and an output function. Keystream generators
produce a sequence that appears to be random, which is combined with the plaintext message using the
output function. Most commonly, the output function is binary addition modulo two. Cryptanalysis of
these ciphers focuses largely on analysis of the keystream generators and of relationships between the
generator and the keystream it produces. Linear feedback shift registers are widely used components
in building keystream generators, as the sequences they produce are well understood.
Many types of attack have been proposed for breaking various LFSR based stream ciphers. A recent
attack type is known as an algebraic attack. Algebraic attacks transform the problem of recovering the
key into a problem of solving multivariate system of equations, which eventually recover the internal
state bits or the key bits. This type of attack has been shown to be effective on a number of regularly
clocked LFSR based stream ciphers. In this thesis, algebraic attacks are extended to a number of well
known stream ciphers where at least one LFSR in the system is irregularly clocked. Applying algebriac
attacks to these ciphers has only been discussed previously in the open literature for LILI-128.
In this thesis, algebraic attacks are first applied to keystream generators using stop-and go clocking.
Four ciphers belonging to this group are investigated: the Beth-Piper stop-and-go generator, the alternating step generator, the Gollmann cascade generator and the eSTREAM candidate: the Pomaranch
cipher. It is shown that algebraic attacks are very effective on the first three of these ciphers. Although
no effective algebraic attack was found for Pomaranch, the algebraic analysis lead to some interesting
findings including weaknesses that may be exploited in future attacks.
Algebraic attacks are then applied to keystream generators using (p, q) clocking. Two well known
examples of such ciphers, the step1/step2 generator and the self decimated generator are investigated.
Algebraic attacks are shown to be very powerful attack in recovering the internal state of these generators.
A more complex clocking mechanism than either stop-and-go or the (p, q) clocking keystream
generators is known as mutual clock control. In mutual clock control generators, the LFSRs control
the clocking of each other. Four well known stream ciphers belonging to this group are investigated
with respect to algebraic attacks: the Bilateral-stop-and-go generator, A5/1 stream cipher, Alpha 1
stream cipher, and the more recent eSTREAM proposal, the MICKEY stream ciphers. Some theoretical
iii



results with regards to the complexity of algebraic attacks on these ciphers are presented. The algebraic
analysis of these ciphers showed that generally, it is hard to generate the system of equations required
for an algebraic attack on these ciphers. As the algebraic attack could not be applied directly on these
ciphers, a different approach was used, namely guessing some bits of the internal state, in order to
reduce the degree of the equations. Finally, an algebraic attack on Alpha 1 that requires only 128 bits
of keystream to recover the 128 internal state bits is presented.
An essential process associated with stream cipher proposals is key initialization. Many recently
proposed stream ciphers use an algorithm to initialize the large internal state with a smaller key and
possibly publicly known initialization vectors. The effect of key initialization on the performance of
algebraic attacks is also investigated in this thesis. The relationships between the two have not been
investigated before in the open literature. The investigation is conducted on Trivium and Grain-128,
two eSTREAM ciphers. It is shown that the key initialization process has an effect on the success
of algebraic attacks, unlike other conventional attacks. In particular, the key initialization process
allows an attacker to firstly generate a small number of equations of low degree and then perform an
algebraic attack using multiple keystreams. The effect of the number of iterations performed during key
initialization is investigated. It is shown that both the number of iterations and the maximum number
of initialization vectors to be used with one key should be carefully chosen. Some experimental results
on Trivium and Grain-128 are then presented.
Finally, the security with respect to algebraic attacks of the well known LILI family of stream ciphers, including the unbroken LILI-II, is investigated. These are irregularly clock- controlled nonlinear
filtered generators. While the structure is defined for the LILI family, a particular paramater choice
defines a specific instance. Two well known such instances are LILI-128 and LILI-II. The security of
these and other instances is investigated to identify which instances are vulnerable to algebraic attacks.
The feasibility of recovering the key bits using algebraic attacks is then investigated for both LILI128 and LILI-II. Algebraic attacks which recover the internal state with less effort than exhaustive key
search are possible for LILI-128 but not for LILI-II. Given the internal state at some point in time, the
feasibility of recovering the key bits is also investigated, showing that the parameters used in the key
initialization process, if poorly chosen, can lead to a key recovery using algebraic attacks.

iv



Contents
Front Matter
Keywords . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i
i

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

iii
v

List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii
Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv
Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv
Previously Published Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix
1

2

Introduction
1.1 Overview of Stream Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
2


1.1.1
1.1.2

Measuring the Security Provided by Stream Ciphers . . . . . . . . . . . . . .
The One Time Pad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
2

1.1.3

Keystream Generators for Stream Ciphers . . . . . . . . . . . . . . . . . . . .

3

1.1.4
1.1.5

Background on LFSR Based Stream Ciphers . . . . . . . . . . . . . . . . . .
Clock-Controlled Generators . . . . . . . . . . . . . . . . . . . . . . . . . . .

4
4

1.2
1.3

Introduction to Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Algebraic Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


7
8

1.4
1.5

Key Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Aims and Objectives of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8
10

1.6
1.7

Contributions and Achievements . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Outline of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10
10

Overview of Algebraic Attacks on LFSR based Stream Ciphers
2.1 Framework for Algebraic Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13
14

2.1.1


2.1.2
2.1.3

Equation Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Linearly Updated Internal States . . . . . . . . . . . . . . . . . . . . . . . . .

15
15

Nonlinearly Updated Internal States

. . . . . . . . . . . . . . . . . . . . . .

18

Reducing the Degree of the Equations . . . . . . . . . . . . . . . . . . . . . .
Methods for Solving Nonlinear Equations . . . . . . . . . . . . . . . . . . . .

19
24

Linearization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

v


Gr¨obner Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


27

Other Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

Fast Algebraic Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Precomputation Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31
31

2.2.2 Realtime Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32
35

Keystream Generators using Stop-and-Go Clocking
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37
37

3.2
3.3

Equation Generation for Stop-and-Go Generators . . . . . . . . . . . . . . . . . . . .
Beth-Piper Stop-and-Go Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . .


38
39

3.3.1
3.3.2

Description of the Basic Beth-Piper Stop-and-Go Generator . . . . . . . . . .
Algebraic Attack of the Basic Beth-Piper Stop-and-Go Generator . . . . . . .

39
39

3.3.3
3.3.4

The Strengthened Beth-Piper Stop-and-Go Generator . . . . . . . . . . . . .
Algebraic Attack on the Strengthened Beth-Piper Stop-and-Go Generator . . .

41
41

3.3.5

Reducing the Degree of the Equations . . . . . . . . . . . . . . . . . . . . . .
Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41
42

3.3.6


Comparison with Previous Cryptanalysis . . . . . . . . . . . . . . . . . . . .

43

3.3.7 Fast Algebraic Attack on Strengthened Beth-Piper Stop-and-Go Generator . .
Alternating Step Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46
47

3.4.1
3.4.2

Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Algebraic Attack on the Alternating Step Generator . . . . . . . . . . . . . . .

47
47

3.4.3
3.4.4

Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Comparison with Previous Cryptanalysis . . . . . . . . . . . . . . . . . . . .

48
49

3.4.5

3.4.6

Modified Alternating Step Generator . . . . . . . . . . . . . . . . . . . . . . .
Alternative Algebraic Attacks on the Alternating Step Generator . . . . . . . .

51
51

Cascade Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Gollmann Cascade Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52
53

3.6.1
3.6.2

Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Algebraic Attack on the Gollmann Cascade Generator . . . . . . . . . . . . .

53
53

3.6.3

Recovering the Initial State . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54
56


3.6.4

Comparison with Previous Cryptanalysis . . . . . . . . . . . . . . . . . . . .

56

3.6.5
3.6.6

An Alternative Algebraic Attack . . . . . . . . . . . . . . . . . . . . . . . . . 58
Clock-Controlled Cascade Generator with Output Bits Taken from All Registers 59

2.2

2.3
3

3.4

3.5
3.6

3.7

3.8

Pomaranch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7.1 Pomaranch Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


60
60

3.7.2

Algebraic Analysis of Pomaranch . . . . . . . . . . . . . . . . . . . . . . . .
Overcoming the Problem of the Degree Accumulation . . . . . . . . . . . . .

62
63

Algebraic Analysis of the Filter Function . . . . . . . . . . . . . . . . . . . .
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65
65

vi


4

Keystream Generators using (p, q) Clocking

67

4.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


67

4.2

Step1/Step2 Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68
68

4.2.2
4.2.3

Algebraic Attack on the Step1/Step2 Generator . . . . . . . . . . . . . . . . .
Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68
69

4.2.4
4.2.5

Comparison with Previous Cryptanalysis . . . . . . . . . . . . . . . . . . . .
Alternative Algebraic Attack on the Step1/Step2 Generator . . . . . . . . . . .

70
72

Self-Decimated Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


73
73

4.3.2
4.3.3

Algebraic Attack on the Self-Decimated Generator . . . . . . . . . . . . . . .
Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

73
74

4.3.4 Strengthening the (p, q) Self-Decimated Generator . . . . . . . . . . . . . . .
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

75
75

Keystream Generators using Mutual Clock Control
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

77
77

5.2

Equation Generation for Mutually Clock-Controlled Keystream Generators . . . . . .

78


5.3

The Bilateral Stop-and-Go Generator . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.1 Description of the Bilateral Stop and Go Generator . . . . . . . . . . . . . . .

81
81

5.3.2

Algebraic Analysis of the Bilateral Stop and Go Generator . . . . . . . . . . .
Reducing the Overall Degree of the Equations . . . . . . . . . . . . . . . . . .

81
82

A5/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.1 Description of A5/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83
84

5.4.2

Algebraic Analysis of A5/1 . . . . . . . . . . . . . . . . . . . . . . . . . . .
Reducing the Overall Degree of the Equations . . . . . . . . . . . . . . . . . .

84
85


Alpha 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.1 Description of Alpha 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86
87

5.5.2
5.5.3

Algebraic Attacks on Alpha 1 . . . . . . . . . . . . . . . . . . . . . . . . . .
Reducing the Overall Degree of the Equations . . . . . . . . . . . . . . . . . .

88
88

5.5.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
MICKEY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

89
90

5.6.1

Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

90

5.6.2
5.6.3


Algebraic Analysis of MICKEY-80 v1 . . . . . . . . . . . . . . . . . . . . . .
Algebraic Analysis of MICKEY-80 v2 . . . . . . . . . . . . . . . . . . . . . .

91
92

5.7

5.6.4 Algebraic Analysis of MICKEY-128 v2 . . . . . . . . . . . . . . . . . . . . .
An Alternative Algebraic Attack on Mutually Clock Control Stream Ciphers . . . . . .

93
94

5.8

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

96

4.3

4.4
5

5.4

5.5


5.6

6

Initialization and Algebraic Attacks

97

6.1
6.2

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Algebraic Attacks using Multiple Keystreams . . . . . . . . . . . . . . . . . . . . . .

97
98

6.2.1

99

Facilitating the Linearization Approach . . . . . . . . . . . . . . . . . . . . .

vii


6.2.2
6.3

Overview of Key Initialization Process of eSTREAM Ciphers . . . . . . . . . . . . . 101


6.4

Trivium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.4.1 Facilitating the Linearization Approach on Trivium . . . . . . . . . . . . . . . 103
6.4.2
6.4.3

6.5

6.6
7

Degree Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Observation on Trivium Initialization . . . . . . . . . . . . . . . . . . . . . . 105

Grain-128 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.5.1 Facilitating the Linearization Approach . . . . . . . . . . . . . . . . . . . . . 106
6.5.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

Algebraic Analysis of the LILI Keystream Generators
111
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7.2

7.3


Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
7.2.1 LILI-128 Keystream Generator . . . . . . . . . . . . . . . . . . . . . . . . . 113
7.2.2 LILI-II Keystream Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Algebraic Analysis of the LILI Family of Stream Ciphers . . . . . . . . . . . . . . . . 113
7.3.1

7.4

Attack 1 : Guessing the Controlling Register . . . . . . . . . . . . . . . . . . 114

7.3.2 Attack 2 : Keystream Decimation . . . . . . . . . . . . . . . . . . . . . . . . 115
Algebraic Analysis of the LILI-II Stream Cipher . . . . . . . . . . . . . . . . . . . . . 117
7.4.1
7.4.2

Algebraic Representation for the LILI Family of Stream Ciphers . . . . . . . . 117
Algebraic Attacks on LILI-II . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
Standard Algebraic Attacks of Section 7.3.1 . . . . . . . . . . . . . . . . . . . 118
Standard Algebraic Attacks of Section 7.3.2 . . . . . . . . . . . . . . . . . . . 118

7.5

7.4.3 Fast Algebraic Attacks on LILI-II . . . . . . . . . . . . . . . . . . . . . . . . 118
Initialization and Algebraic Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
7.5.1
7.5.2

8

Direct Recovery of Key Bits . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

Recovering the Key Bits Given the Internal State Bits . . . . . . . . . . . . . . 121

7.6

Investigating the Resistance of Other Instances of the LILI Family Ciphers to Algebraic
Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

7.7

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

Conclusion and Future Research
8.1

8.2

127

Review of Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
8.1.1
8.1.2

Chapter 3: Keystream Generators using Stop-and-Go Clocking . . . . . . . . . 128
Chapter 4: Keystream Generators using (p, q) Clocking . . . . . . . . . . . . . 129

8.1.3
8.1.4

Chapter 5: Keystream Generators using Mutual Clock Control . . . . . . . . . 129
Chapter 6: Initialization and Algebraic Attacks . . . . . . . . . . . . . . . . . 130


8.1.5 Chapter 7: Algebraic Analysis of the LILI Keystream Generators . . . . . . . 130
Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

A Algebraic Relations in Pomaranch

133

B Algebraic Normal Form of LILI-II Boolean function

137

viii


Bibliography

141

ix


x


List of Figures
1.1
1.2

Binary additive stream cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Basic Clock-Controlled Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3
5

1.3
1.4

The Step1/Step2 Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Mutually clock-controlled stream ciphers . . . . . . . . . . . . . . . . . . . . . . . .

5
6

1.5

Clock-controlled nonlinear filter generators . . . . . . . . . . . . . . . . . . . . . . .

6

2.1

Algebraic attacks algorithm

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.2
2.3


Algorithm for finding low degree multiples . . . . . . . . . . . . . . . . . . . . . . .
Algorithm for the linearization approach . . . . . . . . . . . . . . . . . . . . . . . .

21
25

2.4
2.5

Algorithm for the F4 approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Algorithm for the XL approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28
30

2.6
2.7

Precomputation step algorithm due to [60] . . . . . . . . . . . . . . . . . . . . . . .
Algorithm for precomputation and realtime phases of the fast algebraic attack based on

32

LFSR based keystream generators . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

3.1


The Beth-Piper Stop-and-Go Generator - Basic Version . . . . . . . . . . . . . . . . .

39

3.2

Algorithm for algebraic attack for recovering the state of the Basic Beth-Piper Stop-

3.3

and-Go Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
The Beth-Piper Stop-and-Go Generator - Strengthened Version . . . . . . . . . . . . .

40
41

Algorithm for algebraic attack for recovering the state of the strengthened Beth-Piper
stop-and-go generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

3.5
3.6

The Alternating Step Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
The Gollmann Cascade Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47
53


3.7
3.8

Algorithm for algebraic attack for recovering the state of the Gollmann cascade generator 55
Pomaranch Version 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

4.1
4.2

The Step1/Step2 Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
The Self-Decimated Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68
73

5.1
5.2

The Bilateral-stop-and-go-generator . . . . . . . . . . . . . . . . . . . . . . . . . . .
A5/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81
84

5.3

Alpha 1 stream cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

87


5.4

The MICKEY family of stream ciphers . . . . . . . . . . . . . . . . . . . . . . . . .

90

6.1

Algorithm for facilitating the linearization approach using multiple keystreams . . . . 100

3.4

xi


6.2

Algorithm for obtaining low degree equations or for reducing the overall degree of the
equations using multiple keystreams . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

6.3
6.4

Keystream generation and initialization processes of Trivium . . . . . . . . . . . . . . 103
The Grain family of stream cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

7.1
7.2

The LILI family of keystream generators. . . . . . . . . . . . . . . . . . . . . . . . . 112

Algorithm for algebraic attack based on guessing the controlling register . . . . . . . . 114

7.3

Algorithm for precomputation and realtime phases of the algebraic attack based on
keystream decimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

xii


List of Tables
2.1

LFSR internal state values in terms of initial state values . . . . . . . . . . . . . . . .

16

3.1

Attack Times for Beth-Piper Stop-and-Go Generator . . . . . . . . . . . . . . . . . .

43

3.2

Comparing algebraic attack and the linear syndrome attack on the strengthened BethPiper stop-and-go . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

3.3

3.4

Algebraic attack times on Alternating Step Generator . . . . . . . . . . . . . . . . . .
Best known attacks on the Alternating Step Generator . . . . . . . . . . . . . . . . . .

48
50

3.5
3.6

Recovering the internal state bits of a Gollmann cascade with K = 4 . . . . . . . . . .
Best known attacks on Gollmann cascade generator . . . . . . . . . . . . . . . . . . .

56
57

4.1
4.2

Algebraic attack times for step1/step2 generator . . . . . . . . . . . . . . . . . . . . .
Best known attacks on Step1/Step2 Generator . . . . . . . . . . . . . . . . . . . . . .

69
71

4.3
4.4

Algebraic attack on the Self-Decimated Generator . . . . . . . . . . . . . . . . . . . .

Algebraic attack times for Self-Decimated Generator . . . . . . . . . . . . . . . . . .

74
75

5.1

Description of clocking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

5.2
5.3

Low degree multiples for the output function for the Bilateral Stop and Go Generator .
Standard algebraic attacks on A5/1 with the guessing approach . . . . . . . . . . . . .

83
86

5.4
5.5

Standard algebraic attacks on Alpha 1 with the guessing approach . . . . . . . . . . .
Best known attacks on the Alpha 1 stream cipher . . . . . . . . . . . . . . . . . . . .

89
89

5.6


Data obtained for the alternative algebraic attack . . . . . . . . . . . . . . . . . . . .

96

6.1

Number of IV needed for an algebraic attack for various given numbers of outputs and

6.2

degrees of the equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Experimental results for Trivium :X = 288 iterations and Y = 21. . . . . . . . . . . . 104

6.3
6.4

Experimental results for Trivium :X = 335 iterations and Y = 21 . . . . . . . . . . . 104
Experimental results for Grain-128: X = 64 and Y = 12 . . . . . . . . . . . . . . . . 108

6.5
6.6

Experimental results for Grain-128: X = 82 and Y = 12 . . . . . . . . . . . . . . . . 108
Experimental results for Grain-128: X = 94 and Y = 12 . . . . . . . . . . . . . . . . 109

7.1
7.2

Parameters for two specific generators from the LILI family . . . . . . . . . . . . . . 112

Summary of the algebraic attacks of Sections 7.3.1 and 7.3.2 on both LILI-128 and
LILI-II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

7.3
7.4

Attack of Section 7.3.1 using fast algebraic attacks on both LILI-128 and LILI-II . . . 119
Attack of Section 7.3.2 using fast algebraic attacks on both LILI-128 and LILI-II . . . 119
xiii


7.5

Summary of requirements for the algebraic attacks of Sections 7.3.1 and 7.3.2 . . . . . 122

7.6

Results of attack of Section 7.3.1

7.7
7.8

Results of attack of Section 7.3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
Results of attack of Section 7.3.1 using fast algebraic attacks . . . . . . . . . . . . . . 123

7.9

Results of attack of Section 7.3.2 using fast algebraic attacks . . . . . . . . . . . . . . 124

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 122


Notation
The keystream generators examined in this thesis are based on shift registers. Capital letters are used
to denote registers and subscript to refer to a specific stage of a register, so A i refers to the ith stage of
register A. To indicate the contents of the register at a specific time instance we use the superscript t.
The lengths (in bits) of these registers are denoted l, m, n, r etc. The i th bit of register A at time t is
denoted by Ati and so the output bit is Atl . The keystream is denoted z, so z t is used to denote the output
from the entire system at time t. M denotes the number of monomials occurring in a given system of
equations and d the degree of the equations.

xiv


Declaration
The work contained in this thesis has not been previously submitted for a degree or diploma at any
higher education institution. To the best of my knowledge and belief, the thesis contains no material
previously published or written by another person except where due reference is made.

Signed: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Date: . . . . . . . . . . . . . . . . . . . . . . . . .

xv


xvi


Previously Published Material
The following papers have been published or presented, and contain material based on the content of
this thesis.
• [1] Sultan Zayid Al-Hinai, Lynn Batten, Bernard Colbert and Kenneth Wong. Algebraic attacks

on clock-controlled stream ciphers. In L. M. Batten and R. Safavi-Naini, editors, Proceedings of
Information Security and Privacy - 11th Australasian Conference, ACISP 2006, volume 4058 of
Lecture Notes in Computer Science, pages 1–16. Springer-Verlag, 2006.
• [2] Kenneth Wong, Bernard Colbert, Lynn Batten and Sultan Zayid Al-Hinai. Algebraic attacks
on clock-controlled cascade ciphers. In Rana Barua, Tanja Lange, editors, Proceedings of the 7th
International Conference on Cryptology in India, INDOCRYPT - 2006, volume of Lecture Notes
in Computer Science, pages 32–47 . Springer-Verlag, 2006.
• [3] Sultan Zayid Al-Hinai, Ed Dawson, Matt Henricksen and Leonie Simpson. On the Security
of the LILI Family of Stream Ciphers Against Algebraic Attacks. In J. Pieprzyk and H. Ghodosi
and E. Dawson, editors, Proceedings of Information Security and Privacy - 12th Australasian
Conference, ACISP 2007, volume 4586 of Lecture Notes in Computer Science, pages 11–28.
Springer-Verlag, 2007.

xvii


xviii


Acknowledgements
In the name of Allah, the most gracious, the most merciful. Alhamdulliah without your blessing Allah I
could not have finished this thesis. First of all I wish to thank all my supervisors Professor Ed Dawson,
Dr Leonie Simpson and Dr Matt Henricksen. Professor Dawson is a very knowledgeable and caring
person, he is always there when needed. Professor Dawson provided with the guidance, encouragement
and enthusiastic support over the course of this work.
Dr Simpson is very patient and provided me a lot of encouragement, support and guidance so that
I could finish the thesis. In addition, thanks to Dr Henricksen who I came to know more closely in
my last two years of my PhD for the useful discussion and moral support. To my former principal
supervisor, Dr Bill Millan, thank you.
To my wife and children your sacrifices are great, and without your support this thesis would not

have been completed.
My mother, brothers, sisters and family many thanks. Special thanks go to my mother who always
provided advice when needed and always prayed for me to complete this thesis. I cannot forget my
mother in law who gave us a great help with the children during the write up phase of the thesis.
To the Omani government that provided the scholarship and gave me this opportunity to complete
my PhD degree, many thanks also. I also would like to thank the support of Said Faraj Al-Rabia, Dr
Hamed Al-Rawahi, and Yahya Al-Rawahi.
To all of my friends in Oman and in Brisbane especially Yusof Banihamad, Saleh, Riza, Housain
and all ISI staff and students your help and friendship have made study in Brisbane very enjoyable.
I also would like to thank Dr Hovard Molland who visited our institute during the final year of PhD
course, with whom I had useful discussions. I thank him for his initial advice and help in using the
Magma mathematical software as a useful tool for my research.
I wish to acknowledge the efforts of co-researchers, who worked with me on certain areas of this
thesis. They are: Professor Lynn Batten, Dr Bernard Colbert and Kenneth Wong who worked with me
on most of Chapters 3 and 4 except for Sections 3.3.7, 3.4.6, 3.6.6 and 4.2.5. Professor Lynn Batten
and Dr Bernard Colbert also worked with me on parts of Chapter 5.

xix


xx


Chapter 1

Introduction

Stream ciphers have been widely used for providing data confidentiality for real time applications
such as mobile telephony (as in the Global System for Mobile Communications (GSM) networks),
satellite communications, pay-TV, secure online transactions and sensitive military communications.

For these telecommunication applications, information needs to be encrypted and decrypted at high
speed. For example decryption of high resolution streaming video data needs to occur in real time. In
addition, these telecommunication applications often require the use of encryption algorithms with low
implementation footprint (gates/memory), and which are cost effective. Stream ciphers can be designed
to provide both security and meet these speed and efficiency requirements. In many telecommunication
applications, error propagation can occur. There is a need for encryption algorithms that have limited
or no error propagation. Stream ciphers can be designed to overcome the error propagation problems.
Various methods have been proposed for analysing and attacking stream ciphers. Some of the
proposed methods are generic and can be applied to any stream cipher regardless of the structure. Other
methods are more specialized and structure dependent. Generally, the aim of an attack is to recover the
internal state at some point in time, or recover the secret key bits. One specialized structure dependent
attack method is known as algebraic attacks.
Algebraic attacks are new methods for attacking and analyzing stream ciphers. They have drawn
much attention from the cryptographic community. Although the effectiveness of these attacks on block
ciphers has been questioned by members of the cryptographic community, many stream ciphers have
been broken by algebraic attacks. This thesis investigates the security of a number of well known stream
ciphers against algebraic attacks, and shows that certain stream ciphers are vulnerable to algebraic
attacks.
In this chapter, the major concepts and terms used in defining the topic are explained. This includes
stream ciphers, keystream generators, and types of attacks on stream ciphers, including algebraic attacks. Secondly, an overview of the thesis is outlined, highlighting the main results.

1


2

Chapter 1. Introduction

1.1 Overview of Stream Ciphers
Stream ciphers have been widely used for providing data confidentiality for real time applications

as they have the potential to provide fast efficient encryption and decryption. Good introductions to
modern stream ciphers and associated analysis are provided by Rueppel [170] and Menezes [150].
This section outlines the principle behind the design of modern stream ciphers and their components.

1.1.1 Measuring the Security Provided by Stream Ciphers
Taking an information theoretic approach, Shannon [178] classified ciphers according to the security
provided as follows:
Definition 1.1 Unconditionally secure: A cipher is unconditionally secure or information theoretic
secure if the attacker is unable to determine the plaintext with any probability greater than randomly
guessing given unlimited ciphertext, time and computational power.
Definition 1.2 Computationally secure: a cipher is computationally secure if an attacker is unable to
determine the plaintext given the ciphertext and polynomial computing resources.

1.1.2 The One Time Pad
The one-time pad is an encryption algorithm that combines a secret key and a message to generate
the ciphertext. The key, plaintext message and the ciphertext are all of equal length. The one timepad is the only known unconditionally secure cipher. A one time-pad is regarded as perfectly secure
and unbreakable if the secret key is a uniformly random stream, the lengths of the secret key and the
plaintext are the same and the key is never reused for a second encryption.
The Vernam cipher is a binary one-time pad [189]. The plaintext message, the secret key and the
ciphertext are all binary streams. That is, the plaintext message characters, the secret key characters and
the ciphertext characters are binary digits (bits). Only the sender and receiver know the key. Vernam
introduced simple encryption and decryption functions. The encryption operation is the bitwise modulo
2 addition of the plaintext with the key. Similarly, the decryption operation is the bitwise modulo 2
addition of the ciphertext with the keystream. This operation is also known as XOR, and in this thesis
denoted by ⊕. The XOR function is defined a follows 1 ⊕ 0 = 1, 1 ⊕ 1 = 0, 0 ⊕ 1 = 1 and 0 ⊕ 0 = 0.

Although it is fast and secure, the one-time pad has significant key management problems. The
requirements for uncondition security (that the key is a truly random sequence the same length as the
message and may not be reused) result in significant issues with respect to the random generation of
the key, the secure distribution of the key and finally the secure elimination of the key. In spite of this,

many countries still use the one-time pad for very sensitive military information. For example, a onetime pad is used for the hot line between the United States and Russia where the security requirement
justifies the cost. For most applications, a less expensive and more practical scheme is required.
Stream ciphers solve some of the problems of key management (the major disadvantage of the one

time pad) by taking a short key, and possibly also a publicly known initialization vector (IV ), as input
to a keystream generator, and expand it into a long keystream. Stream ciphers aim to emulate a onetime pad by producing a keystream that appears unpredictable and random, although it is completely
deterministic. Given the algorithm for keystream generation and the initial state of a generator then the


1.1. Overview of Stream Ciphers

3

same keystream will be produced each time. Although many modern stream ciphers try to adapt the
idea of the one-time pad, none of these pseudorandom generators are unconditionally secure. Instead,
they aim to be computationally secure. The aim is to produce a cipher for which an attacker, given
reasonable resources and time, cannot recover the plaintext. A naive attack is to try every possible key.
A stream cipher is known as secure if breaking it requires more computing power than exhaustive key
search attack.

1.1.3 Keystream Generators for Stream Ciphers
Definition 1.3 Stream Cipher : An encryption algorithm which divides the plaintext into successive
characters and encrypts each character under a time varying function of the key [170].
For the last three decades, most of the proposed stream ciphers were based on one-bit characteristics. However, many recently proposed stream ciphers are based on characters consisting of a group
of bits called words. Common word sizes are 8, 16, 32, or 64 bits. Most bit-based stream ciphers are
fast in hardware but less efficient in software. Word based stream ciphers are intended to achieve adequate security, high speed and efficiency when implemented in software as well as hardware. Bit-based
stream ciphers are widely used, and have been well studied and analyzed. The properties of sequences
produced by ciphers based on bit-based linear feedback shift registers (LFSRs) in particular are well
known. The ciphers examined in this thesis are all bit-based.
Modern stream ciphers are divided into two classes: synchronous and self-synchronous stream

ciphers. A synchronous stream cipher is a cipher in which the keystream is generated as a function of
the key, and possibly an IV , and is produced independently from the ciphertext. In contrast, in selfsynchronizing stream ciphers, the keystream is generated as a function of the key, and possibly an IV ,
and a fixed number of ciphertext characters. All of the ciphers examined in this thesis are synchronous
stream ciphers.
Binary additive stream ciphers are the most common form of stream cipher. In binary additive
stream ciphers, the output function is the bitwise modulo two addition (XOR). Figure 1.1 illustrates
the encryption and decryption operations using a binary additive synchronous stream cipher. Let p t , z t
and ct denote the plaintext, keystream and ciphertext bits, respectively, at time, for some t ≥ 0. Under
encryption, the tth bit in the ciphertext stream is formed as ct = z t ⊕pt , where ⊕ is the output function.

For decryption, the plaintext bitstream is recovered by adding, bitwise modulo 2, the keystream to the
ciphertext bitstream. The tth bit in the plaintext stream is given by pt = z t ⊕ ct . The stream ciphers
examined in this thesis are assumed to be binary additive stream ciphers.

Secret Key ✲
Initialization Vector ✲

Pseudorandom

Pseudorandom

Keystream

Keystream

Generator

Generator

zt


Sender

pt

❄
✓✏
✲ +
✲
✒✑ct

zt

Channel

ct

✛ Secret Key
✛ Initialization Vector

❄
✓✏
✲ +
✲ Receiver
✒✑pt

Figure 1.1: Binary additive stream cipher