0:00

We're finally in a position to describe the most important behaviors

Â that the cryptographic hash function needs to have.

Â Like most useful hash functions, we need it to be deterministic, meaning that,

Â given the same input, it will always produce the same output.

Â This sounds pretty obvious, but

Â there actually are hash functions that are probabilistic.

Â And there are even some cryptographic uses for them.

Â But the purposes we have been discussing require determinism.

Â 0:27

Although not a top priority, we do need it to be fast.

Â We don't want this to become the bottleneck in our ability to carry out

Â high speed communications.

Â But in general, we're usually willing to, and usually have to,

Â sacrifice a lot of speed before we start giving up performance in the other areas.

Â As a result, cryptographic hash functions are commonly hundreds of times slower

Â than their non cryptographic peers.

Â But in addition to raw speed,

Â we also want the hash function to be computationally simple.

Â So that it can be implemented in hardware and run on slow,

Â memory starved devices such as the chips used in credit cards.

Â While modern devices are incomparably faster and

Â more capable than devices from the latter half of the 20th century,

Â which is when many hardware oriented Cryptographic algorithms where pioneered.

Â The amount of complexity we can throw at the function and

Â still achieve acceptable speed and cost does require compromises in other areas.

Â 1:27

For instance, there were many provably secure hash functions

Â based on known mathematical problems that are believed to be quote hard, so hard,

Â in fact, that pretty much all of public key cryptography is based on them.

Â But these hash functions are seldom used, because they are too slow and

Â too computationally demanding to be acceptable for most applications.

Â Instead, most mainstream hash functions are actually quite ad hoc,

Â relying on design principles that have evolved somewhat by trial and error and

Â that really amount to little more than people hoping that they are secure enough

Â based on a lot of collective experience, but that they can't prove.

Â And this doesn't always work out in the long run as evidenced

Â by a host of eventual breaks against several of them.

Â 2:14

Thus we have another example of the reality that in most nearly

Â any form of engineering, there were seldom optimal solutions available and

Â practical solutions represent compromises.

Â At the end of the day, it comes down to carefully considering what

Â must be achieved, to consider the solution good enough.

Â And then accepting that if you have a solution that is good enough,

Â then it's good enough.

Â As the saying goes, there comes a point in the history of every project when

Â it's necessary to shoot the engineers and begin production.

Â We often have to do this knowing that what is good enough today

Â may not be good enough tomorrow.

Â So this is something that will tend to haunt us as we try to achieve

Â the rest of our design goals.

Â One of the more important of those goals is that we want the digest for

Â any two messages, no matter how closely related, to be uncorrelated.

Â Meaning that any similarity between the digests of two different messages

Â is as close to pure chance as we can make it.

Â This is most strongly evidenced by the behavior that even a single bit changed

Â anywhere in the message,

Â even the very last bit, results in about half of the bits in the digest flipping.

Â This requires what is known as strong avalanche,

Â in that every bit of the message has the ability to affect every bit of

Â the digest with about an even chance of actually doing so at any given time.

Â The effect of achieving this is that it becomes extremely difficult,

Â ideally impossible, to take a message and examine it's digest.

Â And then make an incremental change to the message with the intent of moving

Â the digest a little bit closer to the desired target.

Â If we could do this, then we could perform some type of differential or

Â gradient descent attack on the hash function

Â to find collisions much more efficiently than brute force.

Â A number of hash functions have fallen prey to such attacks.

Â So achieving this lack of correlation is very important.

Â Unfortunately, proving that we have achieved it is impossible for

Â most existing computationally efficient hash functions.

Â 4:18

In light in our earlier discussion of the attackers goals,

Â we need to function to be preimage resistant and

Â also second preimage resistant, which large it comes down to it being

Â a not invertible function, also known as a one-way function.

Â This in turn, means that we can't take the hash failure and

Â construct a message from it that will produce that hash.

Â If we could walk backward through the hashing algorithm,

Â then we could eventually work our way back to a suitable message.

Â It's tempting to think that since the most hash functions are implemented as pretty

Â basic combinatorial building blocks, that we should be able to take the outputs and

Â figure out the possible inputs that can produce it.

Â After all, if nothing else,

Â we should be able to write a truth table and then simply reverse it.

Â The result would be, for any given output, a set of possible inputs and

Â possibly a set of outputs that can never happen.

Â The problem is, once again, one of scale.

Â Many hash functions use 32-bit building blocks.

Â For instance, SHA-1 uses 5 such blocks for 160 bits of internal state.

Â And the primary hashing element is a block that combines 3 of these

Â blocks via simple but nonlinear bitwise logic functions.

Â So while there are only 4 billion possible outputs,

Â there are two to the 96th possible outputs.

Â Enumerating this table gets us right back into those

Â astronomically large numbers we've seen before.

Â And that's just one piece of the process.

Â To generate the final 32-bit output that becomes just part of the next state,

Â not only are 160 bits of the previous state used, but

Â also 32 bits that are derived from the message and

Â a 32-bit constant that changes depending on what stage the algorithm is at.

Â 6:06

Thus just to determine 32 bits of the next state, not even the final

Â output of the hash, there are 204 bits of information that are used.

Â To make matters worse, this process is repeated a total of 80 times for

Â each 512 bits of the message.

Â 6:23

This is not to say that this logic function can't be inverted.

Â As already emphasized, we'd like to base our functions on hard math problems and

Â this is possible.

Â It's just not computationally practical yet.

Â So we use functions that really mix things up and

Â then we repeat this process over and over.

Â But invariably,

Â some of the steps will be found to be somewhat invertible, which we can use to

Â reduce the amount of effort required to carry out a sophisticated attack.

Â When that happens, we use what has been learned to try to avoid incorporating

Â similar weaknesses into future generations of functions.

Â It is very much a black art as well as a science.

Â We also need it to be collision resistant,

Â meaning that it is hard to find any two messages that yield the same hash value.

Â The goal here is to make the best way of finding collisions a brute

Â force birthday attack.

Â Again, real hash functions that are not based on hard problems are subject to

Â death by 1,000 cuts.

Â By finding enough small but exploitable weaknesses to reduce the number of digests

Â needed to carry out a birthday attack to a doable number.

Â This is essentially what happened to SHA-1, where a number of weaknesses were

Â discovered, the net effect of which was to reduce the number of digests needed from 2

Â to the 80th down to about 2 to the 63rd, a reduction by about a factor of 100,000.

Â And even so it took about a year to carry out the attack using some massively

Â parallel computing resources.

Â 7:52

Next let's consider a couple of interactions between these properties.

Â Any hash function that is collision resistant

Â is also second-preimage resistant.

Â After all, if I have a function that is not second-preimage resistant,

Â then it is not collision resistant, since the result of a successful

Â second-preimage attack is a hash collision.

Â However, collision resistance does not imply preimage resistance,

Â at least in the strict sense.

Â That might seem rather strange,

Â since it implies that we could have a hash function for which, given a digest, or

Â at least some digest, we can efficiently find a message that produces that digest.

Â But that we can't efficiently find any collisions.

Â 8:35

But it's actually quite easy to construct hash functions for

Â which this is true, though they tend to be pathological,

Â meaning that they have a weakness, not because we discovered it, but

Â because we designed it specifically so as to have that weakness.

Â One example is our identity hash function

Â that simply sets the digest equal to the message.

Â It is trivially invertible, but no collisions exist.

Â But this requires that we restrict the message to being the same size as

Â the digest, which few real hash functions do.

Â So if this is the only way we can get this behavior,

Â then it is of no real consequence.

Â But can we construct a hash function that takes arbitrarily sized messages and yet

Â still has this behaviour?

Â Consider the following N-bit hash function, if a message happens to be

Â exactly N-1 bits, then our digest is 0 appended with the message.

Â Otherwise, we run the message through an N-1 bit collision resistant hash function,

Â perhaps a Random Oracle.

Â And our digest is a 1 appended with its output.

Â Now if you give me a digest that starts with a 0,

Â I can give you a message that produced that digest.

Â The fact that I can't efficiently do this for

Â a digest starting with a 1 doesn't matter.

Â In order to be resistant, it must be on the order of brute force for all digests.

Â In practice, any hash function that is collision resistant

Â is probably preimage resistant, but we can't just assume that it is.

Â 10:06

This has been a short, succinct lesson, so our review isn't going to to be very much.

Â Cryptographic hash functions need to be deterministic, uncorrelated, efficient,

Â preimage resistant, second preimage resistant, and collision resistant.

Â No real hash function is likely to achieve all of these goals, and

Â instead are going to represent compromises between them.

Â Unfortunately, the nature of the compromises are often such that

Â the implications of how much we are giving up in the other areas

Â often are not really known, which leaves the door open for Mallory and his friends.

Â