**New Attacks on FCSR-based Stream Ciphers.** / Ali, Arshad.

Research output: Thesis › Doctoral Thesis

Unpublished

**New Attacks on FCSR-based Stream Ciphers.** / Ali, Arshad.

Research output: Thesis › Doctoral Thesis

Ali, A 2011, 'New Attacks on FCSR-based Stream Ciphers', Ph.D., Royal Holloway, University of London.

Ali A. New Attacks on FCSR-based Stream Ciphers. 2011. 248 p.

@phdthesis{d5a31c4d920f4a2cbbce6ac446851abb,

title = "New Attacks on FCSR-based Stream Ciphers",

abstract = "This thesis presents a new family of cryptanalytic attacks on a class of binaryadditive synchronous stream ciphers, the theory of which is based on the properties of 2-adic numbers. We refer to this new family of cryptanalytic attacksas State Transition Attacks (STAs); we identify three variants of this classof attack, namely Conventional State Transition Attacks (CSTAs), Fast StateTransition Attacks (FSTAs) and Improved State Transition Attacks (ISTAs).These attack variants give rise to trade-offs between data, time and memorycomplexities. The thesis describes STAs on a class of binary additive synchronousstream ciphers whose keystream generators use l-sequences, whichare generated by binary Feedback with Carry Shift Registers (FCSRs). A newtheory of linearisation intervals for FCSR state update functions is also presented,and results on correlations between the feedback bit and the Hammingweights of the main and carry registers of Galois FCSRs are developed. Thesetheoretical findings are used to cryptanalyse an eSTREAM candidate knownas F-FCSR-H v2, as well as two variants of this cipher, known as F-FCSR-Hand F-FCSR-16. This cryptanalysis yields State Recovery Algorithms (SRAs)for these ciphers. The cryptanalytic attacks on F-FCSR-H v2, F-FCSR-H andF-FCSR-16 presented in this thesis are the most efficient attacks known sofar on these ciphers. The thesis also presents a FCSR key recovery algorithmwhich works in conjunction with the SRAs in order to recover the effective keyused in these ciphers.The thesis also presents various techniques, which can be considered aspre-requisite for simulating new attacks on FCSR-based stream ciphers. Inorder to describe these techniques, the thesis defines a small-scale variant ofthe F-FCSR-H type keystream generators and names it as T-cipher. Thethesis develops a statistical analysis for the T-cipher and uses it to describevarious aspects of the sequences generated by such ciphers. These includecomputing the frequency distribution of linearisation intervals, formulatingand solving systems of equations in these intervals. The thesis further presentsenumeration and pseudocode algorithms for solving systems of equations inthe finite field F2.",

author = "Arshad Ali",

year = "2011",

language = "English",

school = "Royal Holloway, University of London",

}

TY - THES

T1 - New Attacks on FCSR-based Stream Ciphers

AU - Ali, Arshad

PY - 2011

Y1 - 2011

N2 - This thesis presents a new family of cryptanalytic attacks on a class of binaryadditive synchronous stream ciphers, the theory of which is based on the properties of 2-adic numbers. We refer to this new family of cryptanalytic attacksas State Transition Attacks (STAs); we identify three variants of this classof attack, namely Conventional State Transition Attacks (CSTAs), Fast StateTransition Attacks (FSTAs) and Improved State Transition Attacks (ISTAs).These attack variants give rise to trade-offs between data, time and memorycomplexities. The thesis describes STAs on a class of binary additive synchronousstream ciphers whose keystream generators use l-sequences, whichare generated by binary Feedback with Carry Shift Registers (FCSRs). A newtheory of linearisation intervals for FCSR state update functions is also presented,and results on correlations between the feedback bit and the Hammingweights of the main and carry registers of Galois FCSRs are developed. Thesetheoretical findings are used to cryptanalyse an eSTREAM candidate knownas F-FCSR-H v2, as well as two variants of this cipher, known as F-FCSR-Hand F-FCSR-16. This cryptanalysis yields State Recovery Algorithms (SRAs)for these ciphers. The cryptanalytic attacks on F-FCSR-H v2, F-FCSR-H andF-FCSR-16 presented in this thesis are the most efficient attacks known sofar on these ciphers. The thesis also presents a FCSR key recovery algorithmwhich works in conjunction with the SRAs in order to recover the effective keyused in these ciphers.The thesis also presents various techniques, which can be considered aspre-requisite for simulating new attacks on FCSR-based stream ciphers. Inorder to describe these techniques, the thesis defines a small-scale variant ofthe F-FCSR-H type keystream generators and names it as T-cipher. Thethesis develops a statistical analysis for the T-cipher and uses it to describevarious aspects of the sequences generated by such ciphers. These includecomputing the frequency distribution of linearisation intervals, formulatingand solving systems of equations in these intervals. The thesis further presentsenumeration and pseudocode algorithms for solving systems of equations inthe finite field F2.

AB - This thesis presents a new family of cryptanalytic attacks on a class of binaryadditive synchronous stream ciphers, the theory of which is based on the properties of 2-adic numbers. We refer to this new family of cryptanalytic attacksas State Transition Attacks (STAs); we identify three variants of this classof attack, namely Conventional State Transition Attacks (CSTAs), Fast StateTransition Attacks (FSTAs) and Improved State Transition Attacks (ISTAs).These attack variants give rise to trade-offs between data, time and memorycomplexities. The thesis describes STAs on a class of binary additive synchronousstream ciphers whose keystream generators use l-sequences, whichare generated by binary Feedback with Carry Shift Registers (FCSRs). A newtheory of linearisation intervals for FCSR state update functions is also presented,and results on correlations between the feedback bit and the Hammingweights of the main and carry registers of Galois FCSRs are developed. Thesetheoretical findings are used to cryptanalyse an eSTREAM candidate knownas F-FCSR-H v2, as well as two variants of this cipher, known as F-FCSR-Hand F-FCSR-16. This cryptanalysis yields State Recovery Algorithms (SRAs)for these ciphers. The cryptanalytic attacks on F-FCSR-H v2, F-FCSR-H andF-FCSR-16 presented in this thesis are the most efficient attacks known sofar on these ciphers. The thesis also presents a FCSR key recovery algorithmwhich works in conjunction with the SRAs in order to recover the effective keyused in these ciphers.The thesis also presents various techniques, which can be considered aspre-requisite for simulating new attacks on FCSR-based stream ciphers. Inorder to describe these techniques, the thesis defines a small-scale variant ofthe F-FCSR-H type keystream generators and names it as T-cipher. Thethesis develops a statistical analysis for the T-cipher and uses it to describevarious aspects of the sequences generated by such ciphers. These includecomputing the frequency distribution of linearisation intervals, formulatingand solving systems of equations in these intervals. The thesis further presentsenumeration and pseudocode algorithms for solving systems of equations inthe finite field F2.

M3 - Doctoral Thesis

ER -