Author:

Keywords:

hash function, block cipher, automated techniques, cryptography

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 arbitrary-length message into a fixed-length 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 SHA-1, two of the most commonly used hash functions today. Although the SHA-2 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: SHA-3.The research performed in this Ph.D. thesis closely follows the evaluation period of the SHA-3 competition. Results were obtained for hash functions ARIRANG, BLAKE, ESSENCE, Hamsi, Khichidi-1, LUX, Sarmal, Skein and TIB3. Outside of the competition, results were also obtained for a simplified version of the hash function HAS-V. 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, SHA-1 and SHA-2, as well two out of the five SHA-3 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 S-functions to allow for a simple and automated analysis.Recently, meet-in-the-middle 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 plaintext-ciphertext 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 differential-algebraic 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 symmetric-key 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 (Mixed-Integer 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 Enocoro-128v2 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 off-the-shelf solver.