Title:  Automated Techniques for Hash Function and Block Cipher Cryptanalysis (Automatische technieken voor hashfunctie en blokcijfercryptanalyse) 
Other Titles:  Automated Techniques for Hash Function and Block Cipher Cryptanalysis 
Authors:  Mouha, Nicky 
Issue Date:  25Jun2012 
Abstract:  Cryptography is the study of mathematical techniques that ensure the confidentiality and integrity of information. This relatively new field started out as classified military technology, but has now become commonplace in our daily lives. Cryptography is not only used in banking cards, secure websites and electronic signatures, but also in public transport cards, car keys and garage door openers.Two building blocks in the domain of cryptography are block ciphers and (cryptographic) hash functions. Block ciphers use a secret key to transform a plaintext into a ciphertext, in such a way that this secret key is needed to recover the original plaintext. Hash functions transform an arbitrarylength message into a fixedlength hash value. These hash values can serve as "fingerprints" for the original messages: it should be infeasible to find two distinct messages with the same hash value (a collision).Yet, Wang et al. recently showed that finding collisions is feasible for MD5 and SHA1, two of the most commonly used hash functions today. Although the SHA2 family currently remains unbroken, its design is very similar. For this reason, the United States National Institute of Standards and Technology (NIST) launched an international competition for a new hash function standard: SHA3.The research performed in this Ph.D. thesis closely follows the evaluation period of the SHA3 competition. Results were obtained for hash functions ARIRANG, BLAKE, ESSENCE, Hamsi, Khichidi1, LUX, Sarmal, Skein and TIB3. Outside of the competition, results were also obtained for a simplified version of the hash function HASV. In the area of cryptographic theory, observations were made on the resistance of regular hash functions against the birthday attack.The most commonly used hash functions: MD5, SHA1 and SHA2, as well two out of the five SHA3 finalists (BLAKE and Skein) use operations such as addition modulo 2 to the power of n, exclusive OR, bitwise Boolean functions, bit shifts and bit rotations. Dissatisfied with commonly used ad hoc techniques to analyze such constructions, we introduced the framework of Sfunctions to allow for a simple and automated analysis.Recently, meetinthemiddle attacks became a very popular way to analyze block ciphers and hash functions. We constructed a novel variant of this technique, and applied it in an automated way to the block ciphers XTEA and GOST. Our attacks require very few known plaintextciphertext pairs.Automated "black box" techniques, such as SAT solvers or Gröbner basis computations, have become increasingly sophisticated and powerful. In the domain of algebraic cryptanalysis, they are used to attack cryptosystems. What are the limits of these techniques? We revisited the differentialalgebraic attacks of Albrecht and Cid, and showed that their attacks do not perform better than differential cryptanalysis. As a result, it seems that there is currently no efficient symmetrickey cipher that can be broken faster using algebraic techniques than using conventional techniques.But not all hope in automatic solvers is lost. We showed how MILP (MixedInteger Linear Programming) solvers can be used to prove the security of ciphers against linear and differential cryptanalysis. Our technique involves writing out only simple linear inequality constraints, and therefore significantly reduces the workload of cryptanalysts and the probability of making of errors. We applied our technique to the Enocoro128v2 stream cipher and to the block cipher AES, and illustrated how we can prove the security of these ciphers against linear and differential cryptanalysis in less than five minutes using an offtheshelf solver. 
Table of Contents:  Acknowledgments
Abstract
Samenvatting
Contents
List of Figures
List of Tables
List of Symbols
List of Abbreviations
I Automated Techniques for Hash Function and Block Cipher Cryptanalysis
1 Introduction
1.1 Motivation
1.2 Challenges
1.3 Thesis Outline
2 Hash Functions
2.1 Introduction
2.2 Deﬁnition
2.2.1 Preimage Resistance
2.2.2 Second Preimage Resistance
2.2.3 Collision Resistance
2.3 Other Security Requirements
2.4 Theory of Hash Functions
2.5 Iterated Hash Functions
2.5.1 MerkleDamgård construction
2.6 Analysis of Hash Functions
2.6.1 Introduction
2.6.2 ESSENCE
2.6.3 Khichidi1
2.6.4 LUX
2.6.5 Sarmal
2.6.6 Skein and BLAKE
2.6.7 Other SHA3 Results
2.6.8 HASV
2.7 Conclusion
3 Block Ciphers
3.1 Introduction
3.2 Deﬁnition
3.2.1 Attack Models
3.2.2 RelatedKey Attacks
3.3 MeetintheMiddle Attacks
3.3.1 XTEA
3.3.2 GOST
3.4 Conclusion
4 Automated Techniques
4.1 Introduction
4.2 Differential and Linear Cryptanalysis
4.3 Sfunctions
4.3.1 Introduction
4.3.2 Background
4.3.3 Our Results
4.4 DifferentialAlgebraic Attacks
4.4.1 Our Results
4.5 Mixed IntegerLinear Programming
4.5.1 Our Results
4.6 Conclusion
5 Conclusion
5.1 Directions for Future Research
Bibliography
II Publications
List of Publications
Finding Collisions for a 45Step Simpliﬁed HASV
1 Introduction
2 A Simpliﬁed HASV
2.1 Description
2.2 Cyclic Description
3 NLcharacteristics
3.1 Representation of Conditions on One Bit ∇Qt+1[i]
3.2 Propagation of Conditions for Every Word ∇Qt+1
3.3 Double Conditions
3.4 Work Factor
4 Finding NLcharacteristics for 45 Steps
5 Conclusion and Future Work
6 Acknowledgments
References
A NLcharacteristics
B A Twobit Example
B.1 Introduction
B.2 Visualizing xdp+(11,01→10) in a Graph
B.3 Calculating xdp+(11,01→10) Using Matrix Multiplications
B.4 Extending the Graph Method
Cryptanalysis of the ESSENCE Family of Hash Functions
1 Introduction
2 Description of the Compression Function of ESSENCE
3 Branching Number of the L Function
4 A 31Round SemiFreeStart Collision Attack For ESSENCE512
5 Finding Message Pairs for the First Nine Rounds
6 Distinguishing Attacks
6.1 Weakness in the Feedback Function of ESSENCE
6.2 Distinguishers on 14Round ESSENCE
6.3 The Distinguisher
6.4 Distinguishers using Biases in Other Bits
6.5 Distinguishers for the Compression Function
6.6 KeyRecovery Attacks
7 Slide Attack
7.1 Slid Pairs with Identical Chaining Values
8 Fixed Points for the ESSENCE Block Cipher
9 Measures to Improve the Security of ESSENCE
10 Conclusions and Open Problems
11 Acknowledgments
References
A Finding the Lowest Weight Difference A
B Making F Behave as a Linear Transformation
C A Message Pair for the First Nine Rounds
D The Feedback Function F
E Distinguishing Attacks on the Full 32Round ESSENCE256
F KeyRecovery Attacks on 32Round ESSENCE
The Differential Analysis of SFunctions
1 Introduction
2 SFunctions
3 Computation of xdp+
3.1 Introduction
3.2 Deﬁning the Probability xdp+
3.3 Constructing the SFunction for xdp+
3.4 Computing the Probability xdp+
3.5 Minimizing the Size of the Matrices for xdp+
3.6 Extensions of xdp+
4 Computation of adp⊕
4.1 Introduction
4.2 Deﬁning the Probability adp⊕
4.3 Constructing the Sfunction for adp⊕
4.4 Computing the Probability adp⊕
5 Counting Possible Output Differences
5.1 Introduction
5.2 Algorithm with a Exponential Time in n
5.3 Algorithm with a Linear Time in n
5.4 Computing the Number of Output Differences xdc+
5.5 Calculation of adc⊕
6 Conclusion
References
A Matrices for xdp+
B All Possible Subgraphs for xdp+
C Computation of xdp+ with Multiple Inputs
D Computation of xdp×3
Correction
MeetintheMiddle Attacks on ReducedRound XTEA
1 Introduction
2 Notation and Convention
3 Description of XTEA
4 Motivational Observation
5 Attacks on 15 Rounds of XTEA
6 Attacks on 23 Rounds of XTEA
7 Conclusions and Open Problems
References
A Countermeasures
B Illustration of the Attack on Rounds 1638
C Randomness of the InnerRound Subkeys in the 15Round Attacks
MeetintheMiddle Attacks on ReducedRound GOST
1 Introduction
2 Description of GOST
3 Attacking up to 14 Rounds of GOST
4 Attack on 16Round GOST
5 Attack on 22Round GOST
6 Conclusions and Open Problems
References
Challenging the Increased Resistance of Regular Hash Functions Against Birthday Attacks
1 Introduction
2 The Birthday Problem
3 Balance and Regularity in Existing Literature
4 Fraction of Regular Functions
5 Subset Regularity
6 Linear Subset Regularity
7 Impact on the Birthday Attack
8 Related Work
9 Random Functions
10 Conclusions
References
A Linear Subset Regularity for 3to1 Bit Hash Functions
B Calculating the Inverses of Matrices A_d
Algebraic Techniques in Differential Cryptanalysis Revisited
1 Introduction
2 Description of Albrecht's DifferentialAlgebraic Attack
3 Inapplicability of Albrecht et al.'s Attacks
3.1 Inapplicability of Attack C
3.2 Inapplicability of Attack B to PRESENT
4 New DifferentialAlgebraic Attacks
4.1 Attack 1 for the PRESENT Block Cipher
4.2 Attack 2 for the PRESENT Block Cipher
5 Conclusion
References
Differential and Linear Cryptanalysis using MixedInteger Linear Programming
1 Introduction
2 Constructing an MILP Program to Calculate the Minimum Number of Active Sboxes
2.1 Differential Cryptanalysis
2.2 Linear Cryptanalysis
3 Description of Enocoro128v2
4 Differential Cryptanalysis of Enocoro128v2
4.1 Constructing the MILP Program
4.2 The Minimum Number of Active Sboxes for Differential Cryptanalysis
5 Linear Cryptanalysis of Enocoro128v2
5.1 Constructing the MILP Program
5.2 The Minimum Number of Active Sboxes for Linear Cryptanalysis
6 Future Work
7 Conclusion
References
A Number of Active Sboxes for AES
Curriculum Vitae 
ISBN:  9789460185359 
Publication status:  published 
KU Leuven publication type:  TH 
Appears in Collections:  ESAT  STADIUS, Stadius Centre for Dynamical Systems, Signal Processing and Data Analytics

