Structural Analysis Of Symmetric-key Algorithms And Hash Functions

Symmetric-key algorithms and hash functions play a fundamental role in modern cryp-tography. They are primitives in cryptography and many high-level protocols can be buildfrom these primitives. However, it is hard to give a provable security analysis on symmetric-key cryptography. Many symmetric-key algorithms and hash functions are built by experi-ence and lack of rigorous theoretical proof.Fortunately, there are some principles for us to design block ciphers and hash functions.We usually first build a high-level construction and framework based on some ideal com-ponents, then we consider the details in the internal component. For block cipher construc-tions, there are two main designs: Feistel structure and Substitution-Permutation-Networkstructure, there are also many extended designs such as Lai-Massey, Gen-Skipjack, Gen-CAST256, Gen-MARS, SMS4, Four-Cell, RC6. Usually a stream cipher is based on linearfeedback shift registers (LFSR), but some stream ciphers are built from block ciphers byusing the corresponding mode of operation. For hash functions, actually most constructionsare based on block ciphers, such as MD4, MD5, SHA-1, MDC-2.We usually treat a good block cipher as a pseudorandom permutation, thus cryptanal-ysis on a block cipher usually is related to the pseudorandomness or indistinguishabilityof this cipher. If we have an ideal internal component and we can prove the security of aconstruction based on this internal component, we say it is a construction with provable se-curity. It is also a popular research line for researchers in the literature. For LFSR-basedstream ciphers, researchers usually focus on the pseudorandomnes of the key stream, suchas period, balance and auto-correlation property. This method is different from that analysisin block ciphers and more knowledge about finite fields are required. The benefit of this typeof stream cipher is that some of the security properties can be proved, a typical example isthe WG stream cipher which has long period, balance and ideal two-level auto-correlationproperty. LFSR-based stream ciphers are also widely used in practice since they are veryefficient in hardware. After flaws in widely used hash functions such as MD5, SHA-1are found, researchon hash functions is becoming hot. Some new security models such as Indistinguishability,Indifferentiability are proposed to prove the security of the iterative modes of hash construc-tions. For compression function constructions, the popular way is to built on block ciphers.But some compression functions are based on hard mathematical problems, such as multi-variate polynomial based hash functions.In this thesis we give a structural analysis on symmetric-key algorithms and hash func-tions due to their design similarity. We obtain the following results:1. We find that the two-round (extended) Lai-Massey scheme is not pseudorandom andthree-round (extended) Lai-Massey is not strong pseudorandom. We use the couplingtechnology from Markov chain theory to prove beyond-birthday-bound for the (strong)pseudorandomness of many-round Lai-Massey. Currently this is the best securitybound for Lai-Massey scheme.2. We give an impossible differential cryptanalysis on Gen-Skipjack, Gen-CAST256,Gen-MARS, SMS4, Four-Cell, RC6block cipher structure and obtain some goodresults. According to the results, we disprove Sung et al.’s conjecture proposed inAsiacrypt’2000and Pudovkina’s claim in FSE’2009.3. We design a lightweight stream cipher WG-7based on the original WG stream cipher.We analyze the security and apply it to RFID authentication protocols.4. We analyze the security of multivariate polynomial hash functions and point out thesehash functions cannot be secure against high order differential cryptanalysis.5. We give a synthesis analysis on blockcipher-based hash functions and solve the openproblem left by Hirose and discover the flaws in the best paper of FSE’2009.6. We succeed in attacking a rate-2/3hash construction proposed by Lee et al. Our attackcontradicts its security claims made by the designer.7. We give a synthesis indifferentiable analysis of the pfMD, chopMD, NMAC/HMACbased on different PGV constructions. We show that these four constructions havedifferent security under different PGV constructions. We also revise Coron et al. andChang et al.’s security proof.