Stream ciphers

Stream Ciphers
	Preface
	Contents
	List of Figures
	List of Tables
	List of Algorithms
Chapter 1: Introduction to Stream Ciphers
	1.1 History I: Antique Ciphers
	1.2 Lessons from History: The Classification of Ciphers
	1.3 History II: The Golden Age of Stream Ciphers
	1.4 Lessons from the Enigma
	1.5 History III: Towards Modern Cryptography
	1.6 When to Use Stream Ciphers?
	1.7 Outline of the Book
Part I: Shift Register-Based Stream Ciphers
	Chapter 2: Linear Feedback Shift Registers
		2.1 Basic Definitions
		2.2 Algebraic Description of LFSR Sequences
			2.2.1 Generating Functions
			2.2.2 Feedback Polynomials Without Multiple Roots
			2.2.3 Feedback Polynomials with Multiple Roots
			2.2.4 LFSR Sequences as Cyclic Linear Codes
		2.3 Properties of m-Sequences
			2.3.1 Golomb's Axioms
			2.3.2 Sequences with Two Level Auto-Correlation
			2.3.3 Cross-Correlation of m-Sequences
		2.4 Linear Complexity
			2.4.1 Definition and Basic Properties
			2.4.2 The Berlekamp-Massey Algorithm
			2.4.3 Asymptotic Fast Computation of Linear Complexity
			2.4.4 Linear Complexity of Random Sequences
		2.5 The Linear Complexity Profile of Pseudo-random Sequences
			2.5.1 Basic Properties
			2.5.2 Continued Fractions
			2.5.3 Classification of Sequences with a Perfect Linear Complexity Profile
		2.6 Implementation of LFSRs
			2.6.1 Hardware Realization of LFSRs
			2.6.2 Software Realization of LFSRs
				2.6.2.1 Bit-Oriented Implementation
				2.6.2.2 Word-Oriented Implementation
	Chapter 3: Non-linear Combinations of LFSRs
		3.1 De Bruijn Sequences
		3.2 A Simple Example of a Non-linear Combination of LFSRs
		3.3 Different Attack Classes
			3.3.1 Time-Memory Trade-off Attacks
			3.3.2 Algebraic Attacks
			3.3.3 Correlation Attacks
		3.4 Non-linear Combinations of Several LFSR Sequences
			3.4.1 The Product of Two LFSRs
			3.4.2 General Combinations
		3.5 Non-linear Filters
		3.6 Correlation Immune Functions
			3.6.1 Definition and Alternative Characterizations
			3.6.2 Siegenthaler's Inequality
			3.6.3 Asymptotic Enumeration of Correlation Immune Functions
	Chapter 4: Correlation Attacks
		4.1 CJS-Attacks
			4.1.1 The Basic Version
			4.1.2 Using Relations of Different Size
			4.1.3 How to Search Relations
			4.1.4 Extended Relation Classes
			4.1.5 Twice Step Decoding
			4.1.6 Evaluation of the Relations
				4.1.6.1 Simple Counting
				4.1.6.2 Fourier Transformation
		4.2 Attacks Based on Convolutional Codes
			4.2.1 Introduction to Convolutional Codes
			4.2.2 Decoding Convolutional Codes
				4.2.2.1 Viterbi Decoding
				4.2.2.2 Sequential Decoding
			4.2.3 Application to Cryptography
				4.2.3.1 A Fast Correlation Attack Based on Viterbi's Algorithm
				4.2.3.2 A Fast Correlation Attack Based on Sequential Decoding
		4.3 Attacking LFSRs with Sparse Feedback Polynomials
	Chapter 5: BDD-Based Attacks
		5.1 Binary Decision Diagrams
			5.1.1 Ordered BDDs
			5.1.2 Free BDDs
		5.2 An Example of a BDD-Based Attack
			5.2.1 The Cipher E0
			5.2.2 Attacking E0
	Chapter 6: Algebraic Attacks
		6.1 Tools for Solving Non-linear Equations
			6.1.1 Gröbner Bases
				6.1.1.1 Ordering on Monomials
				6.1.1.2 Monomial Ideals and the Hilbert Basis Theorem
				6.1.1.3 Gröbner Bases and Buchberger's Algorithm
				6.1.1.4 The Gröbner Walk
			6.1.2 Linearization
				6.1.2.1 Ordinary Linearization
				6.1.2.2 Relinearization
				6.1.2.3 The XL-Algorithm
				6.1.2.4 The XL-Algorithm and Gröbner Bases
		6.2 Pre-processing Techniques for Algebraic Attacks
			6.2.1 Reducing the Degree
			6.2.2 Dealing with Combiners with Memory
		6.3 Real World Examples
			6.3.1 LILI-128
			6.3.2 E0
	Chapter 7: Irregular Clocked Shift Registers
		7.1 The Stop-and-Go Generator and the Step-Once-Twice Generator
		7.2 The Alternating Step Generator
		7.3 The Shrinking Generator
			7.3.1 Description of the Cipher
			7.3.2 Linear Complexity of the Shrinking Generator
			7.3.3 Correlation Attacks Against the Shrinking Generator
		7.4 Side Channel Attacks
Part II: Some Special Ciphers
	Chapter 8: The Security of Mobile Phones (GSM)
		8.1 The GSM Protocol
		8.2 A5/2
			8.2.1 Description of A5/2
			8.2.2 An Instance of a Ciphertext-Only Attack
			8.2.3 Other Attacks Against A5/2
		8.3 A5/1
			8.3.1 Description of A5/1
			8.3.2 Time-Memory Trade-off Attacks
			8.3.3 Correlation Attacks
	Chapter 9: RC4 and Related Ciphers
		9.1 Description of RC4
		9.2 Application of RC4 in WLAN Security
			9.2.1 The WEP Protocol
			9.2.2 The WPA Protocol
			9.2.3 A Weakness Common to Both Protocols
		9.3 Analysis of the RC4 Key Scheduling
			9.3.1 The Most Likely and Least Likely RC4 Permutation
			9.3.2 Discarding the First RC4 Bytes
		9.4 Chosen IV Attacks
			9.4.1 Initialization Vector Precedes the Main Key
			9.4.2 Variants of the Attack
			9.4.3 Initialization Vector Follows the Main Key
		9.5 Attacks Based on Golic's Correlation
			9.5.1 Initialization Vector Follows the Main Key
			9.5.2 Initialization Vector Precedes the Main Key
			9.5.3 Attacking RC4 with the First n Bytes Discarded
			9.5.4 A Ciphertext-Only Attack
		9.6 State Recovering Attacks
		9.7 Other Attacks on RC4
			9.7.1 Digraph Probabilities
			9.7.2 Fortuitous States
		9.8 RC4 Variants
			9.8.1 An RC4 Variant for 32-Bit Processors
			9.8.2 RC4A
			9.8.3 Modifications to Avoid Known Attacks
	Chapter 10: The eStream Project
		10.1 Trivium
		10.2 Rabbit
		10.3 Mosquito and Moustique
	Chapter 11: The Blum-Blum-Shub Generator and Related Ciphers
		11.1 Cryptographically Secure Pseudo-random Generators
		11.2 The Blum-Blum-Shub Generator
		11.3 Implementation Aspects
		11.4 Extracting Several Bits per Step
		11.5 The RSA Generator and the Power Generator
		11.6 Generators Based on Other Hard Problems
		11.7 Unconditionally Secure Pseudo-random Sequences
Part III: Mathematical Background
	Chapter 12: Computational Aspects
		12.1 Bit Tricks
			12.1.1 Infinite 2-adic Expansions
			12.1.2 Sideway Addition
			12.1.3 Sideway Addition for Arrays
		12.2 Binary Decision Diagrams, Implementation Aspects
			12.2.1 Memory Management
				12.2.1.1 Nodes with Reference Counter
				12.2.1.2 An RPN Calculator for BDDs
			12.2.2 Implementation of the Basic Operations
			12.2.3 Implementation of Reordering Algorithms
				12.2.3.1 Jumping up
				12.2.3.2 Sifting down
			12.2.4 Emulating a BDD Base
		12.3 The O-Notation
		12.4 The Complexity Classes P and NP
		12.5 Fast Linear Algebra
			12.5.1 Matrix Multiplication
				12.5.1.1 Simple Algorithms
				12.5.1.2 Strassen's Algorithm
				12.5.1.3 Pan's Algorithm
				12.5.1.4 Binary Matrices
			12.5.2 Other Matrix Operations
			12.5.3 Wiedmann's Algorithm and Black Box Linear Algebra
	Chapter 13: Number Theory
		13.1 Basic Results
		13.2 The Group (Z/nZ)x
		13.3 The Prime Number Theorem and Its Consequences
		13.4 Zsigmondy's Theorem
		13.5 Quadratic Residues
		13.6 Lattice Reduction
	Chapter 14: Finite Fields
		14.1 Basic Properties
		14.2 Irreducible Polynomials
		14.3 Primitive Polynomials
		14.4 Trinomials
		14.5 The Algebraic Normal Form
	Chapter 15: Statistics
		15.1 Measure Theory
		15.2 Simple Tests
			15.2.1 The Variation Distance
			15.2.2 The Test Problem
			15.2.3 Optimal Tests
			15.2.4 Bayesian Statistics
		15.3 Sequential Tests
			15.3.1 Introduction to Sequential Analysis
			15.3.2 Martingales
			15.3.3 Wald's Sequential Likelihood Ratio Test
			15.3.4 Brownian Motion
			15.3.5 The Functional Central Limit Theorem
	Chapter 16: Combinatorics
		16.1 Asymptotic Calculations
		16.2 Permutations
		16.3 Trees
Part IV: Exercises with Solutions
	Chapter 17: Exercises
		17.1 Proposals for Programming Projects
	Chapter 18: Solutions
Part V: Programs
	Chapter 19: An Overview of the Programs
	Chapter 20: Literate Programming
		20.1 Introduction to Literate Programming
		20.2 Pweb Design Goals
		20.3 Pweb Manual
			20.3.1 Structure of a WEB-Document
			20.3.2 Text Sections
			20.3.3 Code Sections and Modules
			20.3.4 Macros
			20.3.5 Special Variable Names
			20.3.6 Include Files
			20.3.7 Conditional Compilation
			20.3.8 More pweb Commands
			20.3.9 Compatibility Features
			20.3.10 Common Errors
			20.3.11 Editing pweb Documents
			20.3.12 Extending pweb
Notations
References
Index