Mehreen Afzal (#309)
Topic of his/her doctorate.
Algebraic Cryptanalysis of Stream Ciphers with Non-linear Update
Year of completion
Stream ciphers are quite well known for providing security in comunication. Due to their efficient
implementation they have received attention of many cipher designers in previous years. Many
new designs have been proposed and extensively analyzed in the form of NESSIE and eSTREAM
projects. In general a new proposed design has to ensure, at least, that it is resistant to the existing
attacks. Algebraic attack is now quite a familiar threat for stream ciphers. Therefore, to make
out the design components, that can strengthen a cipher, against algebraic cryptanalysis must
also be of interest to stream cipher designers. Algebraic cryptanalysis, in its general form, aims at
recovering the internal secret state bits of the registers of the cipher by solving non-linear algebraic
equations. That is why it is considered, not to be applicable on stream ciphers, where registers
are updated non-linearly. Since, in this case, degree of algebraic equations, which relate internal
states with key-stream bits, increase with each clock. However, different designs with nonlinear
update may offer disparate levels of resistance.
In this thesis, we analyze some structures of stream ciphers with non-linear update and identify the
level of resistance their design shows against the recovery of secret internal states. Our objective
is to analyze and compare the design of the key generating mechanism and not the cipher along
with its initialization mechanism. Thus, we concentrate on the key generating part and compare
the ciphers on the basis that how many of their internal state bits can be recovered by solving nonlinear
algebraic equations, using guess and determine approach. Caused by a rise in the degree of equations with each clock, some of the internal state bits have to be guessed to recover the
remaining. Our analysis reveals, that due to some thoughtful guessing, more internal state bits
can be recovered which are not possible otherwise. However, some structures are resistent to give
secret state bits by solving algebraic equations, even after guessing large number of bits. Aim of
this thesis is to identify such structures.
Ciphers considered for this work are A5/1, A5/2, Trivium, Grain and Mickey. Significance of
this work also lies in the fact that we have analyzed those ciphers which have been selected
for the final portfolio of completed eSTREAM project. Based on our analysis, we also propose
some modifications in the design of Grain-v1 to strengthen it against intial state recovery attack,
without any increase in the secret state bits. Some modifications in the design of Trivium are also
suggested therefore, the same structure can be used with larger key bit space.
mehreenafzal00 (at) hotmail.com