How does hashing work?

Hashing consists of passing data of arbitrary size through a function that transforms it into data of a defined size.

For passwords for example, the output size is often larger than the input.

Unlike encryption, a hashing function is destructive (or one-way) because we lose the original data, it is impossible to go back.

Simplified concept

Let's take the simplest possible theoretical hashing function, say our function takes a string as input, and returns its length:

f(x) => length(x)

Which gives us "hello" => 5, "password" => 8 and "dog" => 3

Why use a hash?

For passwords

We can clearly see in the previous example that once passed through the function, the password can no longer be retrieved, so if we store it in a database, it is "protected".

Impossible to retrieve the word "hello" from the simple number 5

For authentication, it will suffice to hash the password provided by the user in real time and compare it to the hash stored in the database, because the hashing function must always return the same hash for the same input data.

To simplify/represent data

A hash is a simplified representation of data. There are many different algorithms, but good practice dictates that two hashes, resulting from two nearly identical pieces of data differing by only a few bits, should be very different.

Theoretical example: the hash of the word "hello" equals "ABCDEF" while the hash of "hellp" equals "ZYXWV"

This means that comparing hashes, rather than the original data, is more optimized, because the first bits of the hash are already different.

And in the case of comparing large files, the hash used will be much lighter than the entirety of the data contained, so the comparison will be more efficient, this is what we call the "checksum".

Which algorithms?

You will have understood, the problem with our simplified hashing function is collisions. Because in this case, the hash of "hello" equals 5 but the hash of "world" also equals 5, this is what we call a collision, and it is one of the issues with hashing.

In practice, cryptographic hashing functions generate fairly long hashes, sometimes longer than the input value, for example the hash of the word "hello" with the SHA-256 algorithm equals:

2cb4b1431b84ec15d35ed83bb927e27e8967d75f4bcd9cc4b25c8d879ae23e18

while the hash of the word "world" equals:

73beed7425bd31551890c0727f4b169cd99b5c708fa8d50a713747e0878e2580

The complexity of a hashing algorithm lies in its ratio between execution time and the number of possible collisions, for example the SHA family of algorithms is faster to execute, but its number of possible collisions is higher than other algorithms like Bcrypt.

Unless execution time constraint is a major issue, it is recommended to use the BCrypt algorithm for passwords for example.

But there are also other even faster algorithms, because collisions are less critical, such as the MD5 hash which is very fast and allows for efficient checksumming!