Infoscience

Thesis

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.

Keywords: cryptanalysis ; cryptography ; hash functions ; stream ciphers ; block ciphers ; cryptanalyse ; cryptographie ; fonctions de hachage ; stream ciphers ; block ciphers

Thèse École polytechnique fédérale de Lausanne EPFL, n° 4506 (2009)
Programme doctoral Informatique, Communications et Information
Section des systèmes de communication
Faculté informatique et communications
Institut de systèmes de communication
Laboratoire de sécurité et de cryptographie

Reference

Record created on 2009-08-27, modified on 2013-10-02

Fulltext