Abstract
This thesis presents a new family of cryptanalytic attacks on a class of binary
additive synchronous stream ciphers, the theory of which is based on the properties of 2adic numbers. We refer to this new family of cryptanalytic attacks
as State Transition Attacks (STAs); we identify three variants of this class
of attack, namely Conventional State Transition Attacks (CSTAs), Fast State
Transition Attacks (FSTAs) and Improved State Transition Attacks (ISTAs).
These attack variants give rise to tradeoffs between data, time and memory
complexities. The thesis describes STAs on a class of binary additive synchronous
stream ciphers whose keystream generators use lsequences, which
are generated by binary Feedback with Carry Shift Registers (FCSRs). A new
theory of linearisation intervals for FCSR state update functions is also presented,
and results on correlations between the feedback bit and the Hamming
weights of the main and carry registers of Galois FCSRs are developed. These
theoretical findings are used to cryptanalyse an eSTREAM candidate known
as FFCSRH v2, as well as two variants of this cipher, known as FFCSRH
and FFCSR16. This cryptanalysis yields State Recovery Algorithms (SRAs)
for these ciphers. The cryptanalytic attacks on FFCSRH v2, FFCSRH and
FFCSR16 presented in this thesis are the most efficient attacks known so
far on these ciphers. The thesis also presents a FCSR key recovery algorithm
which works in conjunction with the SRAs in order to recover the effective key
used in these ciphers.
The thesis also presents various techniques, which can be considered as
prerequisite for simulating new attacks on FCSRbased stream ciphers. In
order to describe these techniques, the thesis defines a smallscale variant of
the FFCSRH type keystream generators and names it as Tcipher. The
thesis develops a statistical analysis for the Tcipher and uses it to describe
various aspects of the sequences generated by such ciphers. These include
computing the frequency distribution of linearisation intervals, formulating
and solving systems of equations in these intervals. The thesis further presents
enumeration and pseudocode algorithms for solving systems of equations in
the finite field F2.
additive synchronous stream ciphers, the theory of which is based on the properties of 2adic numbers. We refer to this new family of cryptanalytic attacks
as State Transition Attacks (STAs); we identify three variants of this class
of attack, namely Conventional State Transition Attacks (CSTAs), Fast State
Transition Attacks (FSTAs) and Improved State Transition Attacks (ISTAs).
These attack variants give rise to tradeoffs between data, time and memory
complexities. The thesis describes STAs on a class of binary additive synchronous
stream ciphers whose keystream generators use lsequences, which
are generated by binary Feedback with Carry Shift Registers (FCSRs). A new
theory of linearisation intervals for FCSR state update functions is also presented,
and results on correlations between the feedback bit and the Hamming
weights of the main and carry registers of Galois FCSRs are developed. These
theoretical findings are used to cryptanalyse an eSTREAM candidate known
as FFCSRH v2, as well as two variants of this cipher, known as FFCSRH
and FFCSR16. This cryptanalysis yields State Recovery Algorithms (SRAs)
for these ciphers. The cryptanalytic attacks on FFCSRH v2, FFCSRH and
FFCSR16 presented in this thesis are the most efficient attacks known so
far on these ciphers. The thesis also presents a FCSR key recovery algorithm
which works in conjunction with the SRAs in order to recover the effective key
used in these ciphers.
The thesis also presents various techniques, which can be considered as
prerequisite for simulating new attacks on FCSRbased stream ciphers. In
order to describe these techniques, the thesis defines a smallscale variant of
the FFCSRH type keystream generators and names it as Tcipher. The
thesis develops a statistical analysis for the Tcipher and uses it to describe
various aspects of the sequences generated by such ciphers. These include
computing the frequency distribution of linearisation intervals, formulating
and solving systems of equations in these intervals. The thesis further presents
enumeration and pseudocode algorithms for solving systems of equations in
the finite field F2.
Original language  English 

Qualification  Ph.D. 
Awarding Institution 

Award date  1 Jan 2012 
Publication status  Unpublished  2011 