Designing a hash function from first principles rather than depending on heuristics

Question

1. 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 "good" 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.

2. 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.

Answer 1

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).

Answer 2

Unlike physics, you cannot have formal definition of primitives in a system that is inherently probabilistic. In the case of hashes in particular, you want some "random looking" output for an input. The reason that the Merkle–Damgård construction is so popular is that it allows for a simple analysis of a single block in the chain of the hash construction, which is true for every other hash construction as well. In semiconductor physics, I can use first principles to derive everything in my drift, diffusion transport equations; however, in cryptographic hashes, you have a probabilistic nature that is different from that of the tangible facts that one expects from a first-principle system. (even if I consider the probabilities of the quantum space because there's convergence that one does not see in cryptography)

For these reasons, I would say that there have been no "first principles" definitions in cryptography in the same way that one sees in the classic sciences.

Answer 3

Designing something from first principles just requires inspiration, genius and madness. Look at:

SHA1("Hello wil3"/0x0a) = a45cc70b69b168e6010b6d1fe2fc9fd358b031ff

The main requirements are simply that it's one way, collision and preimage resistant. There's nothing fundamentally linking the two sides of this equation otherwise. There's also nothing (so far) in quantum or gravitational theory (essentially everything) that suggests a hash has to even have a block. Nothing at all. A stream cipher doesn't and that's cryptographic. No block means that the need for Merkle–Damgård disappears in a puff of logic.

The best cryptographic example of invention I can think of is the sponge. Read about PANAMA and RADIOGATUN which led to the evolution of innovative spongy hashes. Although to understand the thought processes, you'd probably need to interview the team members.

Parameter tweaking through heuristic rules is commonplace. This is one of the best examples I've seen of an evolved (rather than procedural) design. It's an antenna (honestly):-

It's glaringly apparent that this was incrementally evolved, rather than designed by a white collar radio engineer with a slide rule. It even looks like the route of a hill climbing technique. Such optimisation was also used to design S boxes, and had positive results. The main issue with these approaches is the danger of local optimums within the value function. Adding more and more bits to the SHA block width is still not as optimal as the completely different approach of Keccak. That leap requires a human. There's an interesting and vaguely similar discussion in From hash to Cryptographic hash.

But on the substantive issue, no, there aren't any short cuts to invention. I'll suggest a biography of Leonardo da Vinci, Alan Turing or Isaac Asimov. You're asking for a reference on how to create. Generally that's reserved for God, but there are a very few lucky individuals.