Voiceover: Cryptographic hash functions
are basically fundamental building blocks
that are used within many cryptographic algorithms
and protocols,
and they have a number of very important
applications in the context of information security
as a whole.
Now, some of the more common algorithms
in this category that are known
as cryptographic has functions include:
things like MD5, and also,
it has some predecessors like MD4 and others,
as well as algorithms like SHA-256,
and actually, SHA-256 is preceded
by other algorithms like SHA-1 and so on,
and also there are some algorithms
that maybe you've heard of,
or maybe that are a bit lesser known,
but things like RIPEMD, and BLAKE, and Skein,
and others.
Now, cryptographic hash functions are basically
used as critical building blocks in many applications,
and really the first motivating application,
the first historical application
of these types of hash functions
was in the context of what's known
as a digital signature,
and digital signatures are used in so many different
cryptographic applications today.
They're the cornerstone of many
ecommerce protocols.
They are used in doing things like bitcoin generation
and so on.
Cryptographic has functions are also used
in things like message authentication protocols,
in pseudorandom number generation
and password security,
even encryption to some degree.
In fact, aside from their use in digital signatures,
these hash functions are also used in other places
in the bitcoin protocol as well.
First of all, let me talk about
what a cryptographic hash function actually is,
and of course, as the name implies,
the first thing it is,
it's a hash function.
And by hash function,
I basically mean that it will take input.
It's a mathematical function,
a transformation, if you will,
that takes a particular input,
and we call this input a message,
and the message can be of arbitrary length,
and the hash function basically applies
a mathematical transformation,
or maybe a set of mathematical transformations
to this input to produce a single output,
and we typically call this output a digest,
although, sometimes you will see
the output referred to as a tag, or as a hash,
or as a fingerprint,
but digest is sort of the most common nomenclature.
In fact, MD5, which was
one of the earlier hash functions,
stands for message digest 5,
and MD4 was message digest 4,
and so on, and so forth.
Now, the message, as I mentioned briefly
can be of arbitrary size.
It can be as long as you want,
or as short as you want,
but the output,
the size of the digest or the size of the tag,
is going to be fixed in length,
and for example, in the context of a hash function
like, let's say, SHA-256,
the digest will actually be exactly 256 bits in length.
It's going to have a fixed-length output,
but an arbitrary-length input.
The other thing I want to point out
about these cryptographic hash functions
is that the function here is a deterministic function,
and by that, I mean
that the output will always be the same
for a given input,
so if you have a given input,
you're going to see the exact same output.
You won't have a situation in which, maybe,
a given input will have two different possible outputs.
It's going to be consistent.
Now, traditional hash functions have been
used in computer science for quite some time,
and they are used in many
computing applications,
so, for example, you may have heard of something
like a hash function used in something
called a hash table,
but the kinds of hash functions that are used
in hash tables, and I want to stress this,
they aren't necessarily the same
as cryptographic hash functions.
The qualifier "cryptographic" here is very important,
and it usually means or implies that
that hash function has to have a certain set
of critical design goals and maybe some
particular properties in mind
that make it suitable for use
in applications that use cryptography
or cryptographic applications,
areas where perhaps security or privacy
or confidentiality or authentications
are a serious concern.
First and foremost,
maybe in describing some of these properties
is that, and maybe this almost goes without saying,
one of the first properties you want
of a cryptographic hash function
is that it should be computationally efficient,
and by that, I mean that it shouldn't take a lot of time
to compute the output from a given input.
If you're given a message
and you want to apply this set of transformations
to that message to get a digest,
that set of transformation should not take a long time
to implement on a computer.
It should be very fast, or relatively fast.
It almost goes without saying,
but I think it's important to stress and point it out
because I've seen people come up
with grossly inefficient hash functions sometimes,
and those would not be considered suitable
in the context of when typical
cryptographic hash functions are used
for cryptographic applications.
The second property you typically need
in the context,
and this is especially in the context of digital signing,
is that you want it to be the case
that it's hard to find two inputs that actually map
to the same output,
and I mean two distinct inputs
whose corresponding digest is identical.
This property is typically referred to as
collision resistance.
That means it's hard to find a colliding pair of input,
so in other words, if you have two inputs
and let's say you have a message M1,
and you have a message M2,
their output under the application
of the hash function should not be the same.
You won't ever have it be the same that the,
you won't even have it be the case, rather,
that the output of M1 and M2
under an application of the hash function
is the same.
They should never be the same.
It should always be different.
Now, I should take a step back here
and point out that of course in practice,
given that messages can be of arbitrary size
and given that the input or the output, rather,
is a fixed size,
it's not mathematically possible to guarantee
that the output will always be different
for two distinct messages,
but what you typically want is not that the outputs
are necessarily different,
but that it's hard to find two distinct messages
that produce the same output.
We know they exist by virtue of the fact
that there are many messages that can be hash,
and only a finite, small number,
relatively small number compared to
the number of messages,
a smaller number of possible digest values,
but aside from that consideration,
it should be hard. It should take a long time,
and by long, I mean an astromonically long time
to find two distinct messages that would result
in the same output
under the application of the hash function.
Now, the third thing that I want to point out
is that in many cases, you might want,
also, in the context of a hash function,
for the hash function to be able to hide
information about the inputs.
In other words,
given the output,
it should be hard to glean anything useful
or interesting about the input.
Anything, any relevant detail,
and I don't just mean the whole input,
but maybe even something as simple as
was the input an even number or an odd number?
I mean, that should be the kind of thing
that should be hard to infer when you see the output,
even something as simple as the,
the evenness or oddness of the input.
Now, a fourth property I want to point out
is that you typically want the output to be
well distributed.
In other words,
the output should look random.
In other words, it should look
like a set of coin flips took place,
not that there was a predictable way
in which the output was created.
Really, what that means is that,
and you can think of it maybe more conceptually as
it's almost as if you flipped a bunch of coins
to get to the output.
It should look just that random.
And so what you can maybe think of
cryptographic hash functions as,
as it's, perhaps, maybe the mathematical equivalent
or mathematical analog of a meat grinder of sort.
It can take inputs and apply
these mathematical transformations to them
such that the output looks,
for all intents and purposes,
completely random and unrelated
to the original input.
I do want to make a few quick remarks
about these particular properties,
and first of all, they are interrelated.
For example, if you have a situation
where the outputs, let's say,
really appear to bear no relationship to the input
and the outputs also look random,
then that will, in fact, give you to a large degree,
a lot of the collision resistance properties
because just the fact that you can't
predict the output
and the fact that it hides all this information
implies that it's going to be hard to find
two inputs that are distinct
that map to the same output.
And so sometimes, you get one property
in exchange for the others.
The second thing I want to point out
is that typically, these properties in practice,
or maybe in the underlying mathematics,
are things that you hope for
but you can't always guarantee
that they'll always hold,
and it may be entirely possible that
you could design a hash function
that you think is completely collision resistant,
but someone might come along a year from now
and come up with a more clever way for finding
a collision.
Maybe they'll find a clever shortcut
that does not involve doing a brute force search
of any sort.
It turns out that cryptographers,
for better or worse currently do not have
any mathematical techniques.
They haven't developed techniques for being able
to work around some of these limitations.
So we often do take it on face value
that these schemes are secure
based on how long they've been around.
Now, I also want to point out,
and the last thing I want to point out,
is that this treatment that I've given
is not meant to be mathematically rigorous
by any stretch of the imagination.
There are far more precise ways to describe
these underlying properties,
but my hope, instead, is that
this video gives you, maybe, a bit of a flavor
for what is required of a cryptographic hash function
without maybe getting bogged down in some of the
mathematical minutia and formalism.