Hello and welcome to this fundamentals of cryptography.
Course, in the previous video, we talked about what a hash function is and some of its applications,
mainly that it's used most commonly to provide integrity, protection for data.
If you include a hash value alongside data and before it's sent to someone else, it's easy to verify
that that hash value hasn't or that data hasn't been changed by comparing the hash values in this video.
We're going to dive into the security assumptions of hash functions, namely the features that a hash
algorithm has to have in order to provide that strong integrity protection.
In this video, we're going to have three main sections.
We're going to start out by talking about some of the security requirements that a hash function must
have in order to do its job.
Then we're going to dive in to the pigeon hole principle, which is a principle that governs and limits
how secure a hash function really can be.
And then finally, we're going to talk about hash function, collision resistance.
So collision resistance is the principle that a hash function needs to have to be useful for integrity
protection.
And we'll look at what features a hash algorithm has to have in order to actually provide collision
resistance.
And so what are the security requirements of a hash function?
So hash functions are commonly used to protect data integrity and ideally we want to ensure that it's
impossible for two inputs to produce the same output.
However, ensuring that's impossible.
We talked about in the previous video that there are an infinite number of possible inputs to a hash
function, but a finite number of possible outputs.
And so it's impossible to ensure that you can't find two inputs that produce the same output.
Because in reality, an infinite number of inputs map to the same output.
So we're going to have to lower our bar of expectations a little bit and say that we need to ensure
that it's hard to find any two of those inputs that produce the same output.
And this is called collision resistance.
If we can accomplish this.
And so hash functions are designed to be collision resistant.
We can't find those two inputs with the same output.
And hash functions are designed to have an infinite number of inputs, but a finite number of outputs.
And so the pigeonhole principle really describes not only the fact that it's impossible for us to have
perfect collision resistance.
No two inputs create the same output, but also the limits on our collision resistance.
Essentially, the maximum amount of work that an attacker would have to do to find a collision in a
hash function.
And the pigeon hole principle says that for a function with any possible outputs, trying at least.
And plus one inputs guarantees a collision.
And so what we're seeing here on the right side of the screen is a image of nine pigeonholes.
And so by the time if we are randomly assigning pigeons to pigeon holes.
By the time we get to our tenth pigeon, we are guaranteed to have a collision or two pigeons that have
been placed in the same pigeon hole.
And the reason why is there's no possible mapping of 10 pigeons to nine pigeonholes where every pigeon
gets its own pigeon hole.
And so this puts our upper bound on the complexity of attacking a hash function, because if we have
a finite number of outputs, all an attacker has to do is search through all a set of inputs of the
same size as the possible outputs.
And by the time they reach that value plus one, they're guaranteed to have found a collision.
Might not be a collision that they want, but there will be a collision.
And in fact, in actuality, the number that of ones that they'll have to check is much lower than that.
And.
And won't get into this here, but look into the birthday paradox, which describes how much in reality
an attacker would have to search the possible space of input's before they're likely to find a collision.
If you want to guarantee you need to search a space the same size as the output space, but the actual
number that you need to search to find, say, 95 percent probability is much, much smaller.
And so with hash functions, we can't guarantee that it's impossible to find a coalition.
Infinite inputs, finite outputs, et cetera.
So hash functions are designed to make finding that collision extremely difficult, which requires a
few different properties.
The first is that the hash function needs to be a one way function.
If you can go from output to input, then finding collision could be a lot easier.
For example, if you can figure out the equation of the hash function uses and reverse it and determine
what bit of data is dropped.
If you try different values for that bit of data, you probably will find cases where you can easily
find collisions.
Any data that's dropped when shrinking from an infinite input to a finite output that doesn't appear
in that output means that we can easily find collisions.
So you need a completely a one way function.
Secondly, you need a large state space.
So this comes from our pigeonhole principle.
If there are only five possible outputs to a hash function, you only need to try six possible inputs
before you find a collision.
And so in order to be secure and protect against hash function collisions, you need enough outputs
that this space of inputs an attacker would have to search through to find a collision is too large
to do so on modern computers.
So for an example of this, take SHA 256, which is a 256 bit hash function.
That means that there are two to the 256 possible outputs, which is an extremely large number.
If we're talking atoms, we're talking values that aren't that much smaller than the size of the universe
and atoms proximately two to the sixtieth atoms in the universe.
And so that's only a few times larger than the number of possible outputs of SHA 256.
And so the simple way of breaking a hash function, that brute force search isn't really applicable.
And the third property of a hash function that's necessary for collision resistance is non locality.
And so what non locality means is that similar inputs can not produce similar outputs.
For example, if I set put an input X and get output Y, I can't say put an input X plus one and get
output Y plus one or something like that.
Like for example, if we use the modulus function as our hash function.
And the reason for this is that if similar inputs produce similar outputs, then it's possible to perform
a hill climbing attack and a hill climbing attack.
An attack would take an input to the hash function, calculate Atash and get an output.
They didn't take that same input change one bit of its value.
Pass it through the hash function and get an output and compare those two outputs.
If that new output is closer to their goal than the original one, they keep the change and repeat the
process using the new input.
Otherwise, they discard the change and take the original input and tweak a different bit on it.
And so why this works in the long run is if similar inputs produce similar outputs, eventually they'll
work their way to a maximum or a point where they achieved their goal.
And the reason why is that the similarity between outputs for similar inputs provides some feedback
on whether they're moving the right direction.
A cryptographically secure hash function, one that offers collision resistance, won't provide any
of that additional information.
In fact, it's about, on average, about half of the bits and the output should be different from the
previous output.
If there's only one bit of difference between the two inputs, because this destroys as much information
as possible.
And so without that valuable feedback sort of guiding towards a solution, the best way to break a hash
function is random guessing.
And then we get back to that massive state space, which makes random guessing infeasible.
It's certainly possible that hash functions that we use today have weaknesses that would allow them
to be broken better than random guessing.
But they haven't been discovered yet.
And for the hash functions that have been broken, we'll talk about this in a later video.
Those hash functions have been broken because are state space was too small.
And it was possible to brute force a collision in most cases.
And so in a recap, the security requirements of a hash function, we need that one way function with
collision resistance according to the pigeon hole principle.
We can't have perfect collision resistance if you have a finite space of possible outputs is guaranteed
that you can find two inputs that collide as long as you search a space at least as large as that space
of outputs.
In reality, you have a high probability of success.
Much, much earlier.
Again, look up the birthday paradox.
However, the only way to get that guarantee is to search a space of the same size.
And so in order to provide collision resistance, we need that one way function.
So information is destroyed.
You can't go from output to input.
We need a very large state space that protects against the brute force search.
If you're trying to try a set of inputs at least as large as the set of outputs, it should be computationally
feasible on modern hardware.
And then finally, we need non locality where there's no feedback loop there, where you can say that
similar inputs produce somewhat similar outputs.
And so judging by the relationship between the outputs, you learn whether you're moving in the right
direction as you change your inputs.
And so this concludes this discussion of the security requirements for hash functions.
Thank you.