Cryptographic Hash Functions:Cryptanalysis, Design and Applications

Praveen Gauravaram

Research output: Book/ReportPh.D. thesisResearch


Cryptographic hash functions are an important tool in cryptography to achieve certain security goals such as authenticity, digital signatures, digital time stamping, and entity authentication. They are also strongly related to other important cryptographic tools such as block ciphers and pseudorandom functions. The standard and widely used hash functions such as MD5 and SHA-1 follow the design principle of Merkle-Damg{\aa}rd iterated hash function construction which was presented independently by Ivan Damg{\aa}rd and Ralph Merkle at Crypto'89. It has been established that neither these hash functions nor the Merkle-Damg{\aa}rd construction itself meet certain security requirements. This thesis aims to study the attacks on this popular construction and propose schemes that offer more resistance against these attacks as well as investigating alternative approaches to the Merkle-Damg{\aa}rd style of designing hash functions. This thesis aims at analysing the security of the standard hash function Cellular Authentication and Voice Encryption Algorithm (CAVE) used for authentication and key-derivation in the second generation (2G) North American IS-41 mobile phone system. In addition, this thesis studies the analysis issues of message authentication codes (MACs) designed using hash functions. With the aim to propose some efficient and secure MAC schemes based on hash functions. This thesis works on three aspects of hash functions: design, cryptanalysis and applications with the following significant contributions: 1.Proposes a family of variants to the Damg{\aa}rd-Merkle construction called 3CG for better protection against specific and generic attacks. Analysis of the linear variant of 3CG called 3C is presented including its resistance to some of the known attacks on hash functions. 2. Improves the known cryptanalytical techniques to attack 3C and some other similar designs including a linear xor variant of GOST, a Russian standard hash function. 3. Proposes a completely novel approach called Iterated Halving, alternative to the standard block iterated hash function construction. 4. Analyses provably secure HMAC and NMAC message authentication codes (MACs) based on weaker assumptions than stated in their proofs of security. Proposes an efficient variant for NMAC called NMAC-1 to authenticate short messages. Proposes a variant for NMAC called M-NMAC which offers better protection against the complete key-recovery attacks than NMAC. As well it is shown that M-NMAC with hash functions also resists side-channel attacks against which HMAC and NMAC are vulnerable. Proposes a new MAC scheme called O-NMAC based on hash functions using just one secret key. 5. Improves the open cryptanalysis of the CAVE algorithm. 6. Analyses the security and legal implications of the latest collision attacks on the widely used MD5 and SHA-1 hash functions.
Keyword: Merkle-Damg{\aa}rd,Cryptanalysis,Hash functions,Applications,Design
Original languageEnglish
Number of pages298
Publication statusPublished - Sep 2007
Externally publishedYes


Dive into the research topics of 'Cryptographic Hash Functions:Cryptanalysis, Design and Applications'. Together they form a unique fingerprint.

Cite this