International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at) iacr.org.

Details

Mehreen Afzal (#309)
Name Mehreen Afzal
Topic of his/her doctorate. Algebraic Cryptanalysis of Stream Ciphers with Non-linear Update
Category secret-key cryptography
Ph.D. Supervisor(s) Ashraf Masood
Year of completion 2010
Abstract 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.
E-Mail Address mehreenafzal00 (at) hotmail.com
Last Change 2011-04-11 08:58:49
To provide an update on this entry, please click .

Contact: phds (at) iacr.org

[ IACR home page ] [ IACR PhDs page ] © IACR