How are cryptographic hash functions designed?

Question

After reading about why one-way hash functions are one-way, I would like to know how to design a hash function. Yes, I know that it's a bad idea to not use a proven and tested hash function, but I would still like to know how what matters in the design, and what the design process is like.

I'm familiar with Feistel-network ciphers but those are necessarily reversible, which is horrible for a cryptographic hash. Is there some sort of construction that is well-used in cryptographic hashing? Something that makes it one-way?

Answer 1

Currently there is the NIST hash function competition running with the goal to find a replacement for the older SHA-1 and SHA-2 functions.
You can get whitepapers to all of the algorithms taking part there (see here for round 2 submissions). There are lots of different hash functions described, as well as their strengths and problems.

Answer 2

First of all you should read chapter 9 of "The Handbook". The full name of this book is "The Handbook Of Applied Cryptography".

Next I recommend that you look at the analysis of existing hash functions. For instance Skein is one of the strongest SHA-3 competitors. Skien's submission contains a lot of documentation on how it is constructed and proven to be secure.

Answer 3

The 'one-way'-ness of a hash function is not an easy thing to compute. Generally hash functions are shown to be good quality by withstanding scrutiny from the cryptographic community for an extended period. You could have a look at some of the published attacks on existing hash functions and try to design a hash function that specifically avoids these, but even then it may prove to be weak to another new attack.

For a very good starting point though I would recommend reading up on the NIST competition (see tanascius' answer).

Answer 4

You should start with Bruce Schneier's book It is a comprehensive introductory textbook on designing crytographic algorithms of all kinds

Answer 5

The PHD thesis of cryptographer Bart Preneel is a good overview of this subject: Analysis and Design of Cryptographic Hash Functions.

Answer 6

Hash function and other cryptographic functions are created with very strong mathematical concepts. Most of them are built thus it is not necessarily unable to reverse/decrypt them but depending on the performance of current computers, it is infeasible to do so. That was why previously certified DES and MD5 algorithm are now obsolete. That being told I suggest you read up on mathematical concepts related to cryptographic hash functions first. Which one's? I'd leave that for someone who is more knowledgeable than me :)

Answer 7

A cipher may be converted into a hash function by simply discarding part of the result. While that isn't the fastest way to produce a hash function, and it certainly won't work in cases where one might need a bijective hash function (e.g. a function which will take 128 bits of input and yield 128 bits of output, such that every possible output value will occur for some input) it should work adequately for many purposes.

The only type of bijective one-way function I've been able to formulate by myself would be (example given for 128->128):

1. Map an input of all zeroes to an output of all zeroes.
2. For any other input, load a linear feedback shift register with all 1's, interpret the input as a 128-bit shift count, and run the shifter for that many counts (note that this does not require actually doing 2^128 steps!).

Reversing the one-way hash would require solving the discrete log problem. For largeish numbers of bits, that is indeed a hard problem, but unfortunately I believe there are approaches for solving it with n=128. I suspect using a number base larger than 2, and using a fundamental operation other than xor, might improve the strength of the approach, but I have no idea how to analyze such tweaks to ensure the function is bijective.