Probability - Hashing

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

YoungStudent
Posts: 127
Joined: Wed Sep 10, 2008 10:14 am UTC

Probability - Hashing

Postby YoungStudent » Sat Apr 14, 2012 11:29 pm UTC

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.
Okay, quote me - We try to explain magic, presence of spirits and supernatural with science, which only explains 'the physical world' that we observe. It's like blind earthworm declaring that there is no light.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26765
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Probability - Hashing

Postby gmalivuk » Sun Apr 15, 2012 12:03 am UTC

YoungStudent wrote: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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Sagekilla
Posts: 382
Joined: Fri Aug 21, 2009 1:02 am UTC
Location: Long Island, NY

Re: Probability - Hashing

Postby Sagekilla » Sun Apr 15, 2012 12:57 am UTC

YoungStudent wrote: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.
http://en.wikipedia.org/wiki/DSV_Alvin#Sinking wrote:Researchers found a cheese sandwich which exhibited no visible signs of decomposition, and was in fact eaten.

YoungStudent
Posts: 127
Joined: Wed Sep 10, 2008 10:14 am UTC

Re: Probability - Hashing

Postby YoungStudent » Sun Apr 15, 2012 1:27 am UTC

gmalivuk wrote:
YoungStudent wrote: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.
Okay, quote me - We try to explain magic, presence of spirits and supernatural with science, which only explains 'the physical world' that we observe. It's like blind earthworm declaring that there is no light.

++$_
Mo' Money
Posts: 2370
Joined: Thu Nov 01, 2007 4:06 am UTC

Re: Probability - Hashing

Postby ++$_ » Sun Apr 15, 2012 1:33 am UTC

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

There are 28,000,000,000 different 1-gigabyte movies. There are 2128 different MD5 hashes. This means that there are 27,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
Posts: 127
Joined: Wed Sep 10, 2008 10:14 am UTC

Re: Probability - Hashing

Postby YoungStudent » Sun Apr 15, 2012 1:35 am UTC

And that answered my question perfectly.
Thank you.

:oops:
Okay, quote me - We try to explain magic, presence of spirits and supernatural with science, which only explains 'the physical world' that we observe. It's like blind earthworm declaring that there is no light.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26765
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Probability - Hashing

Postby gmalivuk » Sun Apr 15, 2012 2:47 am UTC

The fact that different inputs can result in the same hash output can actually be exploited in what's called a collision attack.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Probability - Hashing

Postby Yakk » Mon Apr 16, 2012 2:28 pm UTC

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.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
MisterH
Posts: 31
Joined: Thu Jul 21, 2011 11:02 am UTC

Re: Probability - Hashing

Postby MisterH » Tue Apr 24, 2012 5:29 pm UTC

++$_ wrote:There are 28,000,000,000 different 1-gigabyte movies. There are 2128 different MD5 hashes. This means that there are 27,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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Probability - Hashing

Postby skeptical scientist » Tue Apr 24, 2012 11:54 pm UTC

MisterH wrote:
++$_ wrote:There are 28,000,000,000 different 1-gigabyte movies. There are 2128 different MD5 hashes. This means that there are 27,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 27,999,999,872 movies and find the good ones.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 9 guests