Analysis and design of symmetric cryptographic algorithms

This thesis is concerned with the analysis and design of symmetric cryptographic algorithms, with a focus on real-world algorithms. The first part describes original cryptanalysis results, including: The first nontrivial preimage attacks on the (reduced) hash function MD5, and on the full HAVAL. Our results were later improved by Sasaki and Aoki, giving a preimage attack on the full MD5. The best key-recovery attacks so far on reduced versions of the stream cipher Salsa20, selected by the European Network of Excellence ECRYPT as a recommendation for software applications, and one of the two ciphers (with AES) in the NaCl cryptographic library. The academic break of the block cipher MULTI2, used in the Japanese digital-TV standard ISDB. While MULTI2 was designed in 1988, our results are the first analysis of MULTI2 to appear as an international publication. We then present a general framework for distinguishers on symmetric cryptographic algorithms, based on the cube attacks of Dinur and Shamir: our cube testers build on algebraic property-testing algorithms to mount distinguishers on algorithms that possess some efficiently testable structure. We apply cube testers to some well known algorithms: On the compression function of MD6, we distinguish 18 rounds (out of 80) from a random function. On the stream cipher Trivium, we obtain the best distinguisher known so far, reaching 885 rounds out of 1152. On the stream cipher Grain-128, using FPGA devices to run high-complexity attacks, we obtain the best distinguisher known so far, and can conjecture the existence of a shortcut attack on the full Grain-128. These results were presented at FSE 2008, SAC 2008, FSE 2009, and SHARCS 2009. The second part of this thesis presents a new hash function, called BLAKE, which we submitted to the NIST Hash Competition. Besides a complete specification, we report on our implementations of BLAKE in hardware and software, and present a preliminary security analysis. As of August 2009, BLAKE is one of the 14 submissions accepted as Second Round Candidates by NIST, and no attack on BLAKE is known.