Hash functions
This week, we will look at cryptographic hash functions. These are another widely used tool in modern cryptography that allow for secure communication. In brief, they take an input and scramble or ‘hash’ it to form an output — they are a way to hide information. In this tutorial, we will look at what a hash function is and some of the properties we require them to have.
What is a hash function?
A hash function can be thought of as a normal mathematical function. It takes an input message (m) that is of any length and out outputs what is called the hashed value, that is of a specific length depending on the hash function. In this way, the inputted messaged is compressed (made shorter) by the hash function.
What are the main features of a hash function?
As mentioned before, the output of the hash function or hashed value will be of a fixed length; this length is usually shorter than the input.
The hash function can be computed quickly. This is essential as these operations are used in most real world cryptographic protocols (often multiple times). Therefore, we cannot afford for them to be computationally expensive, which means we do not want them to take a lot of computing power to calculate.
What are the properties we require of hash functions?
- Rather like one way functions in cryptography, we require that a hash function is hard to invert. That is, given the hashed value one cannot reverse the process to get the original input;
- It should not be possible to find two inputs that result in the same hashed value: it should be hard to find x and y, such that h(x) = h(y).
Question:
- Why do you think the properties we require of hash functions are important?
- The second property is often called collision resistant. Do you think it is possible for a hash function to be collusion resistant?
The solutions are at the very end of this article.
This article was written by David Butler, one of the course creators and teachers at Oxbridge Inspire. David is studying for a PhD at the Alan Turing Institute in London.
Oxbridge Inspire delivers innovative STEM education and provides guidance and inspiration to young people wishing to pursue STEM subjects at University and beyond. To find out more about Oxbridge Inspire and the courses and activities we offer, visit our website.
Answer 1:
- If they were easy to invert, an adversary could easily find out the input and it might be a secret piece of information.
- This property means an adversary cannot substitute the input to a hash. This may provide the adversary with an advantage in breaking an encryption.
Answer 2:
No, it is not possible. We have stated that the length of the hashed value is shorter than the length of the input. Therefore some hashed values must be the same. This is because the domain is larger than the range (think about the number of elements in the sets depicted in the diagram).
