Probability - Hashing

[YoungStudent]

If you know the MD5 hash of 60 minute movie and you have the clip of it between 5th and 6th minute...how long would it take with current computing power to generate full movie from that knowledge?

Also if we would have Quantum Computers with extreme speed, couldn't all files get stored like that?

It's just an idea, i'm not very good at math so take it easy on me.

I find it interesting question.

[gmalivuk]

If you know the MD5 hash of 60 minute movie and you have the clip of it between 5th and 6th minute...how long would it take with current computing power to generate full movie from that knowledge?

You couldn't. One minute of movie and a single MD5 hash aren't enough to reproduce an entire movie, because movies don't all have distinct hashes.

[Sagekilla]

Also if we would have Quantum Computers with extreme speed, couldn't all files get stored like that?

Quantum computers are not as fast as you think they may be. They allow certain types of algorithms to be done
efficiently, but they won't be any faster than a normal computer.

[YoungStudent]

If you know the MD5 hash of 60 minute movie and you have the clip of it between 5th and 6th minute...how long would it take with current computing power to generate full movie from that knowledge?

You couldn't. One minute of movie and a single MD5 hash aren't enough to reproduce an entire movie, because movies don't all have distinct hashes.

I think you missed my point here.

Basically what i meant was to keep generating MD5 hashes until an file has been generated which has identical "video data" between 5th and 6th minute.

Given that you would get same MD5 hash from the 5th and 6th minute of generated video aswell as the MD5 hash for the original 5th and 6th minute was.

Thus "reverse" hashing the whole movie from only 1 minute of data.

Sure it wouldn't be efficent in any possible way...but is there any "probability" math that could be done on that subject?

In MY theory you could store movies just by storing their MD5 hash and 5 seconds of footage...given that you have near-unlimited computing power.

But i might be missing an important point somewhere that totally wrecks this theory, and that's also why i made this topic.

[++$_]

It is not possible even in theory. An MD5 hash is not an encoding of a movie. It is merely a signature.

There are 2^{8,000,000,000} different 1-gigabyte movies. There are 2¹²⁸ different MD5 hashes. This means that there are 2^{7,999,999,872} different movies for each hash. There is absolutely no way to tell which was the original movie.

Even if you have a clip of the movie 1 minute in length, and the whole movie is 1 hour, there are still approximately 2^{(59/60)*7,999,999,872} different movies corresponding to the hash and having the 1-minute clip in the appropriate place. You still can't tell which of them is the original.

[YoungStudent]

And that answered my question perfectly.
Thank you.

[gmalivuk]

The fact that different inputs can result in the same hash output can actually be exploited in what's called a collision attack.

[Yakk]

To be fair, most of the movies in that set are random noise. However, the distance of pretty much any arbitrary movie with that 1 minute part is going to be on the order of 128 changed bits away from a movie with the identical hash.

So given any movie, with that 1 minute bit inserted, it would be an extremely hard (yet possible in theory) computational task to make a movie that is visually indistinguishable to the casual observer from it, yet has the target hash value. (In some formats, you could sneak "junk" data in somewhere and make it completely indistinguishable from the arbitrary movie, yet have the target hash).

However, doing so is quite hard. As in "it would take the entire world's computer resources more than the age of the universe" level of difficulty.

In theory, a fully nondeterministic ~128 bit computer could do this in a few cycles. I don't know if there is a quantum computation based MD5 hash collision attack or not.

[MisterH]

There are 2^{8,000,000,000} different 1-gigabyte movies. There are 2¹²⁸ different MD5 hashes. This means that there are 2^{7,999,999,872} different movies for each hash. There is absolutely no way to tell which was the original movie.

But in many cases a good few of the alternatives will actually be better than the original.

[skeptical scientist]

There are 2^{8,000,000,000} different 1-gigabyte movies. There are 2¹²⁸ different MD5 hashes. This means that there are 2^{7,999,999,872} different movies for each hash. There is absolutely no way to tell which was the original movie.

But in many cases a good few of the alternatives will actually be better than the original.

I invite you to watch all 2^{7,999,999,872} movies and find the good ones.