Hashing(Part 2): making a basic hash function

The accompanying video can be found here.

A recap and a question

So, in the last article, I covered some of the basics of hashing, what it is, what it is used for, and desirable characteristics in hash functions. This time, I want to cover more about how hashing works. This will be by no means an in-depth discussion, that could be an entire book, or series of books. Instead, I want to explain some of the basic principals and techniques behind how hash functions work by looking at how we might develop a basic hash function, and what we want to achieve. So, a question: is n mod 10 a hash function?

Removing information

In general, in a hash function, information from the input is lost to form a constant length hash, and the most basic hash you could create is to truncate an input to the length of the hash. To deal with cases where the input is shorter than the hash, we could just pad it with zeros. A major downside of hashing like this is it is very possible to have two slightly different outputs generate the same hash. Let's take a quick look at an example, defining our hashing algorithm as truncating the input to 10 characters, or padding it to 10 with zeros. We will now generate hashes for the following inputs:

input1
input2
Hello world!
jhfajw3784y23h51a8
Lorem ipsum dolor
Lorem ipsum color

The hashes are:

Here, we can readily see that all the first 5 are different, but the hashes would indicate that the fifth and sixth inputs are the same. This is because the hash function does not use the entire input.

This is where the question I asked at the start comes in, and yes, it is a basic hash function, with an input n, and the hash is the remainder when the input is divided by 10. We can express this in a more general way as n mod m, where n is the input, and m is some number, but I'll expand on the effect of changing m in a minute.

We can improve our hashes by using this function, but for the sake of simplicity, let's take some random numbers as inputs to a hash function. Let's say:

3
98
291
292
293

While I have used numbers here for simplicity's sake, you could use this for the previous examples, you'd just have to convert the inputs into some numerical form. The hashes for these inputs with this function are:

So as you can see here, we already have an improvement over the last hash function in that the last three values are different, but now we have a different problem. 3 and 293 have the same hash. The problem here becomes apparent if we just take the numbers 1 to 30 and calculate the hashes we get the following:

So basically, anything ending in 1 has a hash of 1, anything ending in 2 has a hash of 2, and so on. Now, a simple solution could be to divide by 100 instead of 10, and this would mitigate the issue to some extent, with the new hashes as follows. Basically, we can control the length of the hash with m.

Unfortunately, this method does not produce a characteristic often desired in hash functions that I mentioned in the first article in this series, that of irreversibility. With the current hash function we are considering, it is very easy to work out the possible inputs that would produce a given hash. For example if we take the hash value of 5, we can immediately work out the set of inputs that produces the hash, in this case: 5, 15, 25, 35, .... While this pattern and predictability is only a small issue where hashing is used to ensure data integrity, it is a massive issue in security applications like password authentication. Basically, what we need, is a hash function that cannot be reversed and used to work out the input, I might explain why another time.

This is where an effect I mentioned in the last article, the avalanche effect comes in. To demonstrate this effect, here are those numbers from 1-30 hashed with a function I also mentioned last video: SHA256.

Aside from the obvious fact that these hashes are much larger, we can also observe something else, they are all very different. These differences are the manifestation of the avalanche effect.

This effect is one of the most commonly sought after features in hash functions, and it is closely related to another effect called the butterfly effect. The butterfly effect is where in a system, a small change to the inputs has a large effect on the output. As simple example of this, consider the equation y=x^2. In this case, let us use $x$ as our input, and y as our output. If we graph this for when x is greater than 0, we get this. As x increases, y also increases, but not at the same rate. Lets start at x equals 0. Here, y also equals 0. increasing x to one gives us y equals 1, but increasing x to 2, we get y equals 4, at x equals 3, y equals 9. At x equals 4, y equals 16, but you get the idea. As x, the input, gets larger, y, the output also increases, but not at the same rate, and this effect gets even more pronounced as x gets larger. Lets take x = 100, and x = 101 for example. Here the y values are 10,000, and 10,201, respectively. With x being 2 and 3, the difference between the outputs was 5, here it is much larger, 201 to be precise, and this is only a fairly tame example. Using the values 2, 3, 100, and 101, just for fun lets change that equation slightly to y=2^x. Now our values are very different, and the effect is much more pronounced.

Make that much, much more pronounced, and bear in mind that this is a very small and simple system. Anyway, that was a bit of a sidetrack, lets get back to the avalanche effect in hash functions. In general, to create a good irreversible hash function, we apply a variety of techniques, and I am not going to explain SHA256 right now, but I will mention a couple more key principles that are important to good hashing, and in fact cryptography in general. They are confusion and diffusion. Confusion is where each bit of the hash is dependent on several separate parts of the input, and there is no way to find the connection between the parts of input based on the hash.

Diffusion is where changing one bit of the input changes roughly half of the hash.

That's all for this time, but I hope to go over an application of hash functions in the next video.

Reference articles / further reading

Confusion and diffusion - Wikipedia