Algebraic Cryptanalysis (eBook)

EAE lgebraic Cryptanalysis 2
Preface 5
Why this Book was Written 6
Advice for Graduate Students 7
Dedication 8
Acknowledgements 9
If you Find Any Errors. . . 13
Contents 14
List of Tables 24
List of Figures 25
List of Algorithms 26
List of Abrreviations 27
Introduction: How to Use this Book 28
Part One 28
Part Two 29
Part Three 31
Appendices 32
Suggested Chapter Ordering 33
Theorem Numbering 33
Cryptanalysis 34
The Block Cipher Keeloq and Algebraic Attacks 35
Notational Convention 35
2.1 What is Algebraic Cryptanalysis? 36
2.1.1 The CSP Model 36
2.2 The Keeloq Specification 36
2.3 Modeling the Non-linear Function 37
2.3.1 I/O Relations and the NLF 38
2.4 Describing the Shift-Registers 38
2.4.1 Disposing of the Secret Key Shift-Register 39
2.4.2 Disposing of the Plaintext Shift-Register 39
Change of Indexing 39
2.5 The Polynomial System of Equations 39
2.6 Variable and Equation Count 40
2.7 Dropping the Degree to Quadratic 40
2.8 Fixing or Guessing Bits in Advance 41
2.9 The Failure of a Frontal Assault 42
The Fixed-Point Attack 43
3.1 Overview 43
3.1.1 Notational Conventions 43
3.1.2 The Two-Function Representation 43
3.1.3 Acquiring an f (8)k -oracle 44
3.2 The Consequences of Fixed Points 44
3.3 How to Find Fixed Points 45
3.4 How far must we search? 46
3.4.1 With Analytic Combinatorics 47
3.4.2 Without Analytic Combinatorics 49
3.5 Comparison to Brute Force 49
3.6 Summary 50
3.7 Other Notes 51
3.7.1 A Note about Keeloq’s Utilization 51
3.7.2 RPA vs KPA vs CPA 52
3.8 Wagner’s Attack 52
3.8.1 Later Work on Keeloq 53
Iterated Permutations 55
4.1 Applications to Cryptography 55
4.2 Background 56
4.2.1 Combinatorial Classes 56
4.2.2 Ordinary and Exponential Generating Functions 56
4.2.3 Operations on OGFs 57
4.2.3.1 Simple Sum 57
4.2.3.2 Cartesian Product 57
4.2.3.3 Sum with Non-Empty Intersection 58
4.2.3.4 Semiring of Combinatorial Classes 58
4.2.3.5 Sequences of Objects 59
4.2.3.6 Other Operations 60
4.2.4 Examples 60
4.2.4.1 Permutations in General 60
4.2.4.2 The Non-Negative Integers 60
4.2.4.3 Partitions into Boxes 61
4.2.4.4 Cycles 61
4.2.4.5 Morse Code 62
4.2.4.6 Zig-Zag Arrangement 62
4.2.5 Operations on EGFs 62
4.2.5.1 The Labelled Product 62
4.2.5.2 Random Permutations 64
4.2.5.3 Asymptotic Probabilities 64
4.2.6 Notation and Definitions 65
4.3 Strong and Weak Cycle Structure Theorems 66
4.3.1 Expected Values 67
4.4 Corollaries 69
4.4.1 On Cycles in Iterated Permutations 71
4.4.1.1 An Example 71
4.4.2 Limited Cycle Counts 72
4.4.3 Monomial Counting 73
4.5 Of Pure Mathematical Interest 73
4.5.1 The Sigma Divisor Function 74
4.5.2 The Zeta Function and Ap´ery’s Constant 74
4.5.3 Greatest Common Divisors and Cycle Length 75
4.6 Highly Iterated Ciphers 75
4.6.1 Distinguishing Iterated Ciphers 76
4.6.1.1 Repeating the Attack 77
4.6.1.2 A General Maxim: 78
4.6.2 A Key Recovery Attack 78
Stream Ciphers 81
5.1 The Stream Ciphers Bivium and Trivium 81
5.1.1 Background 81
5.1.1.1 What is a Stream Cipher? 81
5.1.1.2 What was eSTREAM? 82
5.1.1.3 What is Trivium? 84
5.1.1.4 Secret Key versus Initial State 85
5.1.1.5 Initialization Stage in Trivium 86
5.1.1.6 Two Types of Attack 86
5.1.1.7 What is Bivium? 87
5.1.2 Bivium as Equations 87
5.1.2.1 Features of these Equations 90
5.1.3 An Excellent Trick 90
5.1.4 Bivium-A 91
5.1.5 A Notational Issue 91
5.1.6 For Further Reading 91
5.2 The Stream Cipher QUAD 92
5.2.1 How QUAD Works 92
5.2.2 Proof of Security 93
5.2.2.1 Computationally Indistinguishable 93
5.2.2.2 The Objective 94
5.2.2.3 The Underlying Hard Problem: A Pre-Image Finder 94
5.2.2.4 Outline of a Proof 95
5.2.2.5 Exploratory Example 96
5.2.3 The Yang-Chen-Bernstein-Chen Attack against QUAD 98
5.2.3.1 The Combination of Wiedemann and XL-II 98
5.2.3.2 The Attack Itself 100
5.2.4 Extending to GF(16) 101
5.2.4.1 An Exercise 101
5.2.4.2 The Solution: Direct Version 101
5.2.4.3 Another look at Fix-XL 102
5.2.5 For Further Reading 103
5.3 Conclusions for QUAD 104
Linear Systems Mod 2 105
Some Basic Facts about Linear Algebra overGF(2) 106
6.1 Sources 106
6.2 Boolean Matrices vs GF(2) Matrices 106
6.2.1 Implementing with the Integers 107
6.3 Why is GF(2) Different? 107
6.3.1 There are Self-Orthogonal Vectors 107
6.3.2 Something that Fails 108
6.3.3 The Probability a Random Square Matrix Singular orInvertible 109
6.4 Null Space from the RREF 110
6.5 The Number of Solutions to a Linear System 111
The Complexity of GF(2)-Matrix Operations 114
7.1 The Cost Model 114
7.1.1 A Word on Architecture and Cross-Over 115
7.1.2 Is the Model Trivial? 116
7.1.3 Counting Field Operations 116
7.1.4 Success and Failure 117
7.2 Notational Conventions 117
7.3 To Invert or to Solve? 118
7.4 Data Structure Choices 119
7.4.1 Dense Form: An Array with Swaps 119
7.4.2 Permutation Matrices 119
7.5 Analysis of Classical Techniques with our Model 121
7.5.1 Na¨ ve Matrix Multiplication 121
7.5.2 Matrix Addition 121
7.5.3 Dense Gaussian Elimination 121
7.5.4 Back-Solving a Triangulated Linear System 123
7.6 Strassen’s Algorithms 124
7.6.1 Strassen’s Algorithm for Matrix Multiplication 125
7.6.2 Misunderstanding Strassen’s Matrix Inversion Formula 126
7.7 The Unsuitability of Strassen’s Algorithm for Inversion 126
7.7.1 Strassen’s Approach to Matrix Inversion 127
7.7.2 Bunch and Hopcroft’s Solution 128
7.7.3 Ibara, Moran, and Hui’s Solution 128
On the Exponent of Certain Matrix Operations 131
8.1 Very Low Exponents 131
8.2 The Equicomplexity Theorems 132
8.2.1 Starting Point 133
8.2.2 Proofs 133
8.3 Determinants and Matrix Inverses 142
8.3.1 Background 142
8.3.2 The Baur-Strassen-Morgenstern Theorem 144
8.3.2.1 The Computational Model 145
8.3.2.2 Theorem and Proof 145
Superfluous Operations: 146
Useful Operations: 146
Notation 147
Case 1: Sum of Two Distinct Variables 147
Case 2: Sum of a Variable with Itself 147
Case 3: Sum of a Variable and a Constant 148
Case 4: Sum of a Constant and a Variable 148
Case 5: Difference of Two Distinct Variables 148
Case 6: Deducting a Constant from a Variable 149
Case 7: Deducting a Variable from a Constant 149
Case 8: Product of Two Distinct Variables 149
Case 9: Product of a Variable with Itself 150
Case 10: Product of a Constant and a Variable 150
Case 11: Product of a Variable and a Constant 151
Case 12: Quotient of Two Distinct Variables 151
Case 13: A Constant Divided by a Variable 151
Case 14: A Variable Divided by a Constant 152
The Base Case 152
Considering s and h also 153
8.3.2.3 A Running Example 153
8.3.2.4 Dividing by Zero 155
8.3.2.5 Impossibility of the Hessian 155
8.3.3 Consequences for the Determinant and Inverse 156
The Method of Four Russians 157
9.0.4 The Fair Coin Assumption 158
9.1 Origins and PreviousWork 158
9.1.1 Strassen’s Algorithm 159
9.2 Rapid Subspace Enumeration 159
9.3 The Four Russians Matrix Multiplication Algorithm 161
9.3.1 Role of the Gray Code 161
9.3.2 Transposing the Matrix Product 162
9.3.3 Improvements 162
9.3.4 A Quick Computation 163
9.3.5 M4RM Experiments Performed by SAGE Staff 163
9.3.6 Multiple Gray-Code Tables and Cache Management 165
9.4 The Four Russians Matrix Inversion Algorithm 165
9.4.1 Stage 1: 165
9.4.2 Stage 2: 166
9.4.3 Stage 3: 166
9.4.4 A Curious Note on Stage 1 of M4RI 167
9.4.5 Triangulation or Inversion? 169
9.5 Exact Analysis of Complexity 169
9.5.1 An Alternative Computation 170
9.5.2 Full Elimination, not Triangular 171
9.5.3 The Rank of 3k Rows, or Why k+e is not Enough 172
9.5.4 Using Bulk Logical Operations 173
9.6 Experimental and Numerical Results 173
9.7 M4RI Experiments Performed by SAGE Staff 175
9.7.1 Determination of k 175
9.7.2 The Transpose Experiment 175
9.8 PairingWith Strassen’s Algorithm for Matrix Multiplication 175
9.8.1 Pairing M4RI with Strassen 176
9.9 Higher Values of q 176
9.9.1 Building the Gray Code over GF(q) 176
9.9.2 Other Modifications 177
9.9.3 Running Time 177
9.9.4 Implementation 178
The Quadratic Sieve 183
10.1 Motivation 183
10.1.1 A View of RSA from 60,000 feet 184
10.1.2 Two Facts from Number Theory 185
10.1.3 Reconstructing the Private Key from the Public Key 185
10.2 Trial Division 187
10.2.1 Other Ideas 189
10.2.1.1 Classification by Difficulty 189
10.2.1.2 Easy Factorization 190
10.2.1.3 Testing Divisibility with GCDs 190
10.2.2 Sieve of Eratosthenes 191
10.2.2.1 Smooth Version 192
An Interesting Trick 192
10.3 Theoretical Foundations 193
10.4 The Na ve Sieve 194
10.4.1 An Extended Example 195
10.5 The Gödel Vectors 195
10.5.1 Benefits of the Notation 196
10.5.2 Unlimited-Dimension Vectors 197
10.5.3 The Master Stratagem 197
10.5.4 Historical Interlude 197
10.5.5 Review of Null Spaces 198
10.5.6 Constructing a Vector in the Even-Space 199
10.6 The Linear Sieve Algorithm 200
10.6.1 Matrix Dimensions in the Linear & Quadratic Sieve
10.6.2 The Running Time 202
10.7 The Example, Revisited 202
10.8 Rapidly Generating Smooth Squares 204
Quadratic Residues 205
10.8.1 New Strategy 205
10.9 Further Reading 207
10.10 Historical Notes 207
Polynomial Systems and Satisfiability 208
Strategies for Polynomial Systems 209
11.1 Why Solve Polynomial Systems of Equations over FiniteFields? 209
11.2 Universal Maps 211
11.3 Polynomials over GF(2) 213
11.3.1 Exponents: x2 = x 213
11.3.2 Equivalent versus Identical Polynomials 213
11.3.3 Coefficients 214
11.3.4 Linear Combinations 214
11.4 Degree Reduction Techniques 214
11.4.1 An Easy but Hard-to-State Condition 215
11.4.2 An Algorithm that meets this Condition 216
11.4.3 Interpretation 217
11.4.4 Summary 218
11.4.5 Detour: Asymptotics of the “Choose” Function 218
11.4.6 Complexity Calculation 219
11.4.7 Efficiency Note 220
11.4.8 The Greedy Degree-Dropper Algorithm 220
11.4.9 Counter-Example for Linear Systems 221
11.5 NP-Completeness of MP 221
One Last Interesting Thought 224
11.6 Measures of Difficulty in MQ 225
11.6.1 The Role of Over-Definition 225
11.6.2 Ultra-Sparse Quadratic Systems 225
An Interesting Observation 226
11.6.3 Other Views of Sparsity 227
Connection To Linear Sparsity 227
Memory Usage 227
SAT Solvers 227
11.6.4 Structure 227
11.7 The Role of Guessing a Few Variables 228
11.7.1 Measuring Infeasible Running Times 228
11.7.2 Fix-XL 229
Algorithms for Solving Polynomial Systems 230
12.1 A Philosophical Point on Complexity Theory 230
12.2 Gröbner Bases Algorithms 231
12.2.1 Double-Exponential Running Time 231
12.2.2 Remarks about Gröbner Bases 231
12.3 Linearization 232
12.4 The XL Algorithm 234
12.4.1 Complexity Analysis 236
12.4.2 Sufficiently Many Equations 237
12.4.3 Jumping Two Degrees 237
12.4.4 Fix-XL 238
12.5 ElimLin 240
12.5.1 Why is this useful? 241
12.5.2 How to use ElimLin 242
12.5.3 On the Sub-Space of Linear Equations in the Span of aQuadratic System of Equations 244
12.5.4 The Weight of the Basis 245
12.5.5 One Last Trick for GF(2)-only 246
12.5.6 Notes on the Sufficient Rank Condition 247
Amplification 247
A View from the Point-of-View of Randomness 248
12.6 Comparisons between XL and F4 248
12.7 SAT-Solvers 249
12.8 System Fragmentation 249
12.8.1 Separability 250
12.8.2 Gaussian Elimination is Not Enough 251
12.8.3 Depth First Search 251
12.8.4 Nearly Separable Systems 252
12.8.5 Removing Multiple vertices 253
12.8.6 Relation to Menger’s Theorem 253
12.8.7 Balance in Vertex Cuts 254
12.8.7.1 Infinite Fields and Large Finite Fields 254
12.8.8 Applicability 254
12.9 Resultants 255
12.9.1 The Univariate Case 255
12.9.2 The Bivariate Case 256
12.9.3 Multivariate Case 257
12.9.3.1 Variables versus Parameters 257
12.9.3.2 Solving the System 258
12.9.4 Further Reading 259
12.10 The Raddum-Semaev Method 259
12.10.1 Building the Graph 259
12.10.2 Agreeing 260
12.10.3 Propigation 261
12.10.4 Termination 261
12.10.5 Gluing 261
12.10.6 Splitting 263
12.10.7 Summary 263
12.11 The Zhuang-Zi Algorithm 264
12.12 Homotopy Approach 264
Applicability 265
Converting MQ to CNF-SAT 266
13.1 Summary 266
13.2 Introduction 267
13.2.1 Application to Cryptanalysis 268
13.3 Notation and Definitions 268
13.4 Converting MQ to SAT 269
13.4.1 The Conversion 269
13.4.1.1 Minor Technicality 269
Step One: From a Polynomial System to a Linear System 270
Step Two: From a Linear System to aConjunctive Normal Form Expression 270
13.4.2 Measures of Difficulty 271
13.4.2.1 Bounds on SAT 272
13.4.3 Preprocessing 273
The Reverse Massage 274
13.4.4 Fixing Variables in Advance 274
13.4.4.1 Parallelization of SAT 275
13.4.5 SAT-Solver Used 275
13.4.5.1 Note About Randomness 275
Error in Dissertation 276
13.5 Experimental Results 276
13.5.1 The Source of the Equations 276
13.5.2 Note About the Variance 276
13.5.3 The Log-Normal Distribution of Running Times 277
13.5.4 The Optimal Cutting Number 278
13.6 Cubic Systems 279
13.6.1 Do All Possible Monomials Appear? 279
13.6.2 Measures of Efficiency 281
13.7 Further Reading 281
13.7.1 Previous Work 281
13.7.2 Further Work 282
13.8 Conclusions 283
How do SAT-Solvers Operate? 284
14.1 The Problem Itself 284
14.1.1 Conjunctive Normal Form 285
14.2 Solvers like Walk-SAT 285
14.2.1 The Search Space 286
14.2.2 Papadimitriou’s Algorithm 286
14.2.3 Greedy SAT or G-SAT 287
14.2.4 Walk-SAT 288
14.2.5 Walk-SAT versus Papadimitriou 289
14.2.6 Where Heuristic Methods Fail 289
14.2.7 Closing Thoughts on Heuristic Methods 290
14.3 Back-Tracking 290
14.4 Chaff and its Descendants 293
14.4.1 Variable Management 293
14.4.2 Unit Propagation 294
14.4.3 The Method of Watched Literals 294
14.4.4 Absent Literals 295
14.4.5 Summary 295
14.5 Enhancements to Chaff 296
14.5.1 Learned Clauses 296
14.5.2 The Alarm Clock 296
14.5.3 The Third Finger 297
14.6 Economic Motivations 297
14.7 Further Reading 298
Applying SAT-Solvers to Extension Fields ofLow Degree 299
15.1 Introduction 299
15.2 Solving GF(2) Systems via SAT-Solvers 300
15.2.1 Sparsity 300
15.3 Overview 301
15.4 Polynomial Systems over Extension Fields of GF(2) 301
15.4.1 Extensions of the Coefficient Field 302
15.4.2 Difficulty in Bits 302
15.5 Finding Efficient Arithmetic Representations via Matrices 302
15.6 Using the Algebraic Normal Forms 306
15.6.1 Remarks on the Special Forms 307
15.6.2 Remarks on Degree 307
15.6.3 Remarks on Coefficients 308
15.6.4 Solving with Gr¨obner Bases 308
15.7 Experimental Results 309
Special Symbols in Results Table: 309
Underdefined Systems of Equations 310
On the Efficacy of the Translation 310
Larger Fields 311
15.7.1 Computers Used 311
15.7.2 Polynomial Systems Used 311
15.8 Inverses and Determinants 312
15.8.1 Determinants 312
15.8.2 Inverses 312
15.8.3 Rijndael and the Para-Inverse Operation 313
15.9 Conclusions 314
15.10 Review of Extension Fields 315
15.10.1 Constructing the Field 315
15.10.2 Regular Representation 317
15.11 Reversing the Isomorphism: The Existence of DeadGive-Aways 318
Appendix A 321
On the Philosophy of Block CiphersWith SmallBlocks 321
A.1 Definitions 321
A.2 Brute-Force Generic Attacks on Ciphers with Small Blocks 322
Point of View 1: Theoretical 322
Point of View 2: Practical 323
Summary 323
A.3 Key Recovery vs. Applications of Ciphers with Small Blocks 323
Scenario One: LORI-KPA/LORI-CPA 323
Scenario Two: Manufacturer Sub-Keys 324
Scenario Three: Short but Private Data 325
Scenario Four: Assigning Account Numbers 325
Scenario Five: Scratch Cards and Software Serial Numbers 325
Scenario Six: Random Number Generation 326
Scenario Seven: Fast Shuffling and Anonymity 326
A.4 The Keeloq Code-book—Practical Considerations 326
A.5 Conclusions 327
Appendix B 328
Formulas for the Field Multiplication law forLow-Degree Extensions of GF(2) 328
B.1 For GF(4) 328
B.2 For GF(8) 328
B.3 For GF(16) 329
B.4 For GF(32) 330
B.5 For GF(64) 331
Appendix C 333
Polynomials and Graph Coloring, with OtherApplications 333
C.1 A Very Useful Lemma 333
C.2 Graph Coloring 334
C.2.1 The c 6= pn Case 334
C.2.2 Application to GF(2) Polynomials 334
C.3 Related Applications 335
C.3.1 Radio Channel Assignments 335
C.3.2 Register Allocation 336
C.4 Interval Graphs 336
C.4.1 Scheduling an Interval Graph Scheduling Problem 337
C.4.2 Comparison to Other Problems 338
C.4.3 Moral of the Story 339
Appendix D 340
Options for Very Sparse Matrices 340
D.1 Preliminary Points 340
D.1.1 Accidental Cancellations 340
D.1.2 Solving Equations by Finding a Null Space 341
D.1.3 Data Structures and Storage 341
D.1.3.1 An Interesting Variation 342
D.2 Na¨ ve Sparse Gaussian Elimination 342
D.2.1 Sparse Matrices can have Dense Inverses 343
D.3 Markowitz’s Algorithm 343
D.4 The BlockWiedemann Algorithm 343
D.5 The Block Lanczos Algorithm 344
D.6 The Pomerance-Smith Algorithm 344
D.6.1 Overview 345
D.6.1.1 Objective 345
D.6.1.2 The Method 346
D.6.2 Inactive and Active Columns 346
D.6.3 The Operations 346
D.6.4 The Actual Algorithm 348
D.6.5 Fill-in and Memory Management 349
D.6.6 Technicalities 350
D.6.6.1 Why not Do Operation 0 only Once? 350
D.6.6.2 Random Matrices 350
D.6.6.3 Only Getting Part of the Null Space 351
D.6.7 Cremona’s Implementation 351
D.6.8 Further Reading 352
Appendix E 353
Inspirational Thoughts, Poetry and Philosophy 353
References 355
Index 367