Designing a hash function from first principles rather than depending on heuristics Is there a general method to design a cryptographic hash function (with desired properties) from first principles? That is, is there a general process for constructing such functions? I get the impression that Merkle–Damgård construction simplifies the process by allowing collision-resistant compression functions to be used, but are there any general ways of finding &quot;good&quot; compression functions other than by using trial-and-error?
In the entries to the most recent NIST challenge, it seemed to me as if the teams were using very different approaches based on different heuristics, and then essentially testing their functions against many inputs, tweaking parameters, and after that iterating until all evidence pointed to their functions as being secure.

To what extent is this an accurate summary of their approaches? I would really appreciate a reference to a thesis or other publication on this subject.
You should design your hash on the bit level.

Regardless how you design your hash, at the end of the day you have a $m$ booleans functions for each output bit from an arbitrary $n$ bits of input.

Some properties of boolean functions

All your output bits will be some boolean function of your input bits.

All boolean functions can be turned into the so called algebraic normal form (ANF), which means your input bits are combined using AND and XOR operators only.

XOR operator is just addition modulo 2. AND operation is just multiplication modulo 2. And these operations are usually denoted with multiplication and addition respectively. In modulo 2 arithmetic addition and subtraction are the same operation, so don't be surprised when I use + when talking about differences.

The modulo 2 arithmetic forms a field, which means all your usual algebraic identities you know are true.

So now the operation of your cipher is just a system of $m$ equations for $n$ bits of input.

Due to nature of modulo 2, a lots of things cancel. Powers cancel: $0^n = 0$, $1^n = 1$. Even coefficients cancel: $x + x = 2x = 0$. 

This means the equations for the output is simpler: The only possible coefficient is 1 (or 0 which means a missing term). And all of them is on the first power.

Nonlinearity

If you try to make a cryptographic hash function that only uses XOR and shifting, the equations will be linear even after infinitely many rounds, now the analyst is just a single Gauss elimination away from solving it and now they have the ability to create arbitrary preimages.

In order to avoid that, you need to make your equations non-linear by using the AND operator. Hashes do all sorts of shifting and XOR-ing but this non-linear step is what makes them secure.

But having non-linear terms are not enough. You must make sure the attacker cannot effectively cancel out the non-linear terms out of your equations by fixing some inputs to 1 or 0. Also you need to make sure the terms will not cancel if the attackers takes the difference of two equations. If you have the formula $xy + x + y$ for one and another formula $xy + y + z$ for another bit. Adding these two will give $x + z$ which is now linear and allows the attacker to solve it to get the relationship between two out bits.
Every independent linear equation an attacker can create will reduce the security of your hash with 1 bit. One way to mitigate this is making sure all the functions for the output bits contain different terms. In the previous example if we replace the $xy$ to $xz$ to the second formula. Adding together will not yield linear equation then. But if the attacker fixes the $x$ to a constant value then it becomes a linear equation. This is probably the most challenging part of designing your hash.

Balance

Another thing to consider is balance. You want your hash behave like the so called random oracle. This is important if you want your hash useful as a cryptographically secure random number generator for example. You should make sure all your bits in the resulting hash have 50% chance to be 1. The XOR operator have a very good property that makes it possible: in $a + b$, if either term have 50% chance to be 1, the entire expression will have 50% chance to be 1. To prove this let's consider $A$ and $B$ the probability that $a$ and $b$ are 1 respectively. The probability that $a + b$ is 1 is: $A(1-B) + B(1-A)$. That is either $A$ is 1 and B is 0, or $A$ is 0 and $B$ is 1. If we expand this we have: $A + B - 2AB$. Substituting 0.5 for $A$ gives: $0.5 + B - B = 0.5$. So as long as you can ensure there is at least one term in the final equations that has 50% chance to be 1 independent from other terms, then that will ensure your function is balanced. The simplest way to achieve this, is making sure at least one first order input bit term appears in the functions of all output bits and it will anchor the 50% chance.

Strict avalanche criterion

The next thing to consider is the strict avalanche criterion (SAC).  This means if you change any bit (or more generally any bit pattern) in the input, all bits in the output must have 50% chance to change. Failing to do so can give information to the attacker about the input, and makes your hash vulnerable to differential cryptanalysis. Let $H(x)$ the original hash, let $H(x + \alpha)$ the hash of the changed input. In $H(x) + H(x + \alpha)$ the changed bits will be set. You must make sure this function is balanced too so any bit has 50% chance to be set. Let's se what it means. Let x be the bit we changed. Let $xy + xz + yz$ the expression we test. Let $\bar x$ be the flipped $x$. So the test expression will be: $(xy + xz + yz) + (\bar xy + \bar xz + yz) = xy + xz + \bar xy + \bar xz = (x + \bar x)y + (x + \bar x)z = y + z$. Basically terms that doesn't cointain $x$ will be removed, and $x$ will will be removed from terms that contain $x$. This implies that in order to reach SAC it's a necessary condition that  every output bit depends on every input bit. If there is an output bit that doesn't depend on some input bit, your hash will fail to demonstrate SAC if that bit is flipped.

So now how can you make sure that $H(x) + H(x + \alpha)$ is balanced? There is a class of boolean functions that ensure that. They are the so called bent functions. The simplest bent function is just $xy$ where $x$ and $y$ are independent bits. These bent functions can be combined together by adding them up, so $ab + cd + ef + gh$ will be a bent function too ($a$-$h$ are independent bits). There are other more complex construction too (but I didn't find good examples). So if you want to have SAC, use bent functions. But bent functions come with a drawback: they can't be balanced. There will be a $2^{-n/2}$ bias releative to the 50%. 
But this bias approaches zero as the number of bits reaches infinite.



My summary is no way exhaustive.

As the time passes and more and more attacks are discovered so new hash designs need to satisfy more and more conditions, balance, SAC and nonlinearity is a good starting point but probably not enough (I don't know all attacks).