Short description of the course
Stream ciphers are an important class of secret-key encryption schemes, i.e., schemes that use the same key for both encryption and decryption. They encrypt individual bits of a plaintext one at a time using the so-called keystream which results from a pseudorandom generator initialized from the shared secret key.
Stream ciphers are more appropriate in applications where buffering is limited or where characters must be processed as they arrive. Further, they are less prone to error propagation which makes them advantageous when transmission errors are highly probable. Therefore, stream ciphers are ubiquitous in wireless communications, e.g. A5/1 used in GSM phones, RC4 used in Wi-Fi, or E0 used in Bluetooth.
In this course, we study the design principles of stream ciphers, and get a close look at the summation generator E0 used in Bluetooth. We also tackle the important attacks to which stream ciphers are vulnerable, and discuss the main countermeasures one should implement to counter such attacks.
Organization (lectures, assignments, practice labs, etc.) and plan
The course has three types of class sessions: Lectures (1.5 h), recitations (1.5h) and tutorials (3h).
Lectures serve to introduce new concepts. Recitations elaborate more on the theory and work through new examples with the participation of students. Finally, tutorials are intended to test the students’ comprehension through exercises and problems that cover the course material, and that are assigned on a daily basis. The students in the tutorials are encouraged to work in groups, especially on the programming assignments.
Prerequisites
The course is self-contained. However, fast understanding of basic number theory is needed. For instance, the course “Cryptography” offered in the BCS 2022 program is helpful.
Also, some programming experience (in any language) is needed to do the programming assignments.
Grading policy
The grading formula that will be used to determine the grade is:
The final exam (which takes place on Friday) accounts for 50% of the final grade
The programming assignments account for the remaining 50%
The PhD students are further expected to read and present a research paper, and potentially implement some algorithms relevant to stream ciphers.
Overview of Stream Ciphers. (Lecture)
Theoretical Background. (Lecture ; Recitation 1 ; Recitation 2 ; Tutorial)
Linear Feedback Shift Registers. (Lecture ; Recitation ; Tutorial)
Design and Analysis of Stream Ciphers. (Lecture ; Recitation)
Application: The Summation Generator (Lecture ; Recitation ; Tutorial)
Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. (Chapter 2, Chapter 6). Available at https://cacr.uwaterloo.ca/hac/
Modern Computer Algebra by Joachim von zur Gathen and Jürgen Gerhard. (Chapter 3, Chapter 5-Section 9, Chapter 12-Section 3)
Algorithmic Cryptanalysis by Antoine Joux. (Chapter 12)
Correlation Immunity and the Summation Generator by Rainer A. Rueppel. CRYPTO '85: Advances in Cryptology 1985. Pages 260–272
Correlation-immunity of nonlinear combining functions for cryptographic applications by Thomas Siegenthaler. IEEE Trans. Inf. Theory 30(5): 776-780 (1984)