Information Security Stack Exchange is a question and answer site for information security professionals. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let's say I have a video file that is split into multiple parts. Each piece is 2 Megabytes. I also have a list of the *insert hash name here* for each piece and also for the full file.

Now assume that I have misplaced/lost/fubar one of these pieces.

Could I retrieve the lost piece from its hash, using brute force or any other method in a human-lifespan amount of time?

A rainbow-style table would be unfeasible, I think.

Bonus numerical question - how much would it take on a medium-size distributed computing network based on mostly consumer PCs? (Example: 4 GHz CPU + entry level GPU + 8 GB RAM)

share|improve this question
87  
that would be the best zip algorithm ever – Eumel Jan 25 at 10:54
6  
Dutch Jan Sloot claimed he could compress a complete movie down to 8 kilobytes of data. Perhaps he used these Sha256 checksums. Unfortunately he died before publishing his work. – Jeff Jan 25 at 18:03
3  
A very similar question was recently asked on Stack Overflow. – MvG Jan 25 at 18:19
14  
x + y = 10. Can I recover the exact values of x and y from 10? – Ajedi32 Jan 25 at 20:12
3  
A secure hash is not a checksum. – EJP Jan 25 at 21:28

10 Answers 10

A simple answer, NO.

It is like asking, if I know, that x%4 = 3, is it possible to find the value of x? No. Surely, there would be infinite values of x satisfying this equation, but you wouldn't simply know which one is correct.

Similarly, many(or infinite) video clips could result in a given hash value(obviously, infinite video clips have to be mapped to a specific number of hash values, so collisions are bound to happen). You wouldn't know which clip is correct.

That too, in human time? No.

EDIT: As pointed out in comments, since the file is chunked into pieces of 2 MB, there won't be infinite possibilities, but it would be pretty large(2 raised to power of 16.7 million, approximately). Brute-forcing such a large number of possibilities, in human time, is still close to impossible. But yeah, it's not infinite.

share|improve this answer
    
Good answer. explains it very simply, very good especially for people who dont understand all that techy stuff... – My1 Jan 25 at 8:56
19  
I disagree. "You wouldn't know which clip is correct" While it's true in general, here we have additional constraints: 1. data is 2MB in size, 2. data is a video file, 3. that video file is part of larger video. – el.pescado Jan 25 at 9:10
1  
@el.pescado Still, even then there would be infinite samples which would result in the same hash. Also, op needs it in human time. – Priyank Gupta Jan 25 at 9:59
2  
@PriyankGupta Well, there are only finitely many 2MB chunks. But there is certainly more information to be expected in a 2MB video chunk than can be expressed using the 512 bits of the effectively two SHA256 hashes. – Hagen von Eitzen Jan 25 at 13:18
2  
@PriyankGupta: There are not infinite possibilities but many - about 2^(2 * 8 * 1024^2 - 256). (not counting the mentioned constraints 2. and 3.) Anyway such a large number is like infinite for our imagination :) In Python 3: import decimal; '{:.2E}'.format(decimal.Decimal(2**(2*8*1024**2-256))): 1.57E+5050368 It is like guessing the 2 MB chunk shorter by the length of the hash (32 bytes). – pabouk Jan 25 at 13:42

This is not possible no matter how fast your computer is, simply because you cannot recreate the correct information out of practically nothing.

You are actually asking for restoring 2 MB from 32 byte (size of SHA-256) or at most 64 byte (SHA-256 for chunk and for total file). This would be an ratio of 1:65536 or 1:32768. Given that video is already heavily compressed the chance is practically zero that you could restore the original data from this few information. It might be that you could create a 2 MB chunk which results in the specific SHA-256 hashes but chances are very low that this would be that original chunk.

share|improve this answer
33  
If you actually manage to create a 2 MB chunk that results in a SHA-256 hash that you did not already know to be the result of that chunk, I think the NSA will want to have a word with you. – Mehrdad Jan 25 at 10:17
3  
@Mehrdad: Or the people running Powerball, for that matter. – Piskvor Jan 25 at 15:30

Let's say you have a computer that has infinite amounts of processing power, and can reliably check every possible message against every possible hash in a short time. Here's the problem you now face: collisions.

What's a collision? Many different files can match the exact same signature. Many different messages can match the exact same signature.

Hashing is one-way. You convert a series of characters to a hash. When you validate your hash, you are merely checking to see if the message matches the calculated value of the hash. The problem is that many different messages may match this same hash. It's called collision.

However, since you also have infinite computational power, you can also eventually reconstruct the file through supermassive trial and error. However, once you have all of the possible examples for this hash value, how are you going to tell which one is which?


So you're telling me there's a chance?

So you're telling me there's a chance?

With today's technology, and since we'll never have infinite computational power, it will be completely impossible. Even taking the entire world's combined computing power, and multiplying it by a billion, you cannot do this. Even if you somehow did this, how would you be able to tell which message was correct?


Where would my idea apply?

  • Hashing is one-way. With the provided key, you only validate that it matches your calculated hash.
  • Encryption is two-way. With the provided key, you get the results back.

Your idea would apply under encryption, not hashing. With encryption, if you have the key, you can get the decrypted contents of the file.

share|improve this answer

You could not reproduce the file in any reasonable amount of time. The reason is that the only way to 'reverse' a hash is via brute-force, and considering how large the original file was, it would take you that exact amount of bytes to brute force.

Let's say you have a video file that is 100MB large, precisely.

  • 1MB = 1,000,000 bytes
  • 100MB = 100,000,000 bytes

This means you would need to brute force this original file and verify it's hash, you'd need to try n^r permutations. Assuming the video file uses only 256 characters per byte (ascii), we'd be looking at:

256100,000,000 ≈ 10240,823,997 ≈ ∞

That's essentially infinite -- it would take basically FOREVER to compute this, regardless of CPU resources.

UPDATE: There's also, of course, the issue with hash collisions that I left out here -- with a Sha256 hash, you're likely going to run into pretty much an infinite amount of collisions with a file as large as our example. I neglected to mention this earlier for simplicity's sake.

share|improve this answer
11  
This isn't even the real problem, it's not possible even given infinite CPU power and time. The real problem is that with a file significantly larger than the hash size you're just going to find practically infinite hash collisions. You're equally as likely to find a 2 megabyte clip of the movie Inception as your original video. – Matti Virkkunen Jan 25 at 8:04
4  
This answer is completely wrong. The real reason why you can't recover is because there are a possibly infinite number of files which produce the same hash. How would you know which one is the correct one. Another way to look at it is this. If the hash contained all the information, why not store the hash instead of a much larger file? – Roy T. Jan 25 at 8:29
8  
@RoyT. - An infinite number of files, but not an infinite number of files of that size. – Compro01 Jan 25 at 8:55
6  
@wireghoul: Here's a thought experiment for you: Take any valid 2MB video file, and change pixel values around ever so slightly (it's lossy compression so it's unnoticeable anyways), until you get a hash collision. This will happen within 2^256 tries for SHA-256 because you literally run out of hash bits to be different. Given infinite CPU power or time you can generate practically any video content that matches a given hash. – Matti Virkkunen Jan 25 at 10:38
2  
@wireghoul: Obviously this is impossible in practice with current computing resources, but it shows how it is impossible to recover a video based on just the hash. Now of course if the original file had been stored somewhere in a searchable location, the hash is a practically perfect way to find and identify it, because the probability of a random collision is almost nonexistent. – Matti Virkkunen Jan 25 at 10:39

It is hard if the underlying file has high enough entropy. If you know something about the underlying data, then you may well be able to recover it. For example, if there is a hacker anywhere in the vicinity it won't be long at all before someone tells you what I md5 hashed to get:

73868cb1848a216984dca1b6b0ee37bc

However video usually has lots of entropy, making this a lost cause or at least a darn hard one. You'd need the video to be a videocam and you'd have to hope that the missing chunk shows an hour of black as black night. Let's put this in perspective: Creating a bitcoin is essentially a matter of inverting a hash. Inverting a very short video snip is probably akin to making about 20 bitcoins, maybe more. So in your shoes I'd make the bitcoins, buy a fresh copy of the video and pocket the change. Nearly eight thousand dollars worth of change. Maybe I'd buy shares in a quantum computer company and make future exploits easier; it's fun doing the "impossible".

To those who say, "hashes are many to one, so you cannot tell what was hashed": That is true, but of all the many values that hash to that one value, some will be more plausible than others. If you invert the hash above you will have not the least doubt that you found the right input. Have fun! :-)

share|improve this answer
    
Finally, someone who considers plausibility of things being hashed =D – justhalf Jan 26 at 6:43

A comment but it's too long:

As others have shown, this isn't possible. However, there is a related problem that certainly is reasonable:

Ok, you can't reconstruct that 200mb video that was split into 100 2mb files of which you have 99.

However, you can create another file that will be a hair over 2mb that will allow you to reconstruct any one missing file. Two such files will allow you to reconstruct any two missing files and so on. While the block size can't profitably be set higher than the file size (a 4mb repair file still only fixes one missing file) it can be set lower which can be of value if partial damage is a possibility. (The calc time goes up, the files get slightly larger but you have more ability to recover from damage.)

The standard program for a long time was: Quickpar but it hasn't been updated in ages. The more modern alternative that I'm aware of (but have not used much yet) is Multipar (Note: This site is in Japanese. The program is in good English, though.)

If I'm going to back up some data to a DVD I routinely create extra repair files just in case something happens--the extra space on the DVD is going to waste anyway, why not put some insurance there? Multipar even has modes specifically for this (although I have not yet tried them) where it will generate blocks to fill out a DVD-R or BD-R disk.

share|improve this answer

The answer is NO, and it seems that you're mixing up two different things :

  • Checksums and Hashes are one-way Integrity checkers. The purpose of their usage in that matter is to make sure that the data was not corrupted, and nothing else
  • Recovery codes are the ones you're using if you need to recover your data by code provided. The most shining example is a Reed-Solomon code for recovering CD-ROM data. The purpose of their usage in this matter is to help you recover data corrupted/lost by some reason

They're seem to be similar from a first sight, but they're a VERY different things.

share|improve this answer

It is effectively impossible, due to information theory. Effectively impossible, as in "heat death of the universe" becomes a legitimate limiting factor on your search.

You have a 2,000,000 byte (2MB) slice missing. A hash like SHA-1 has 20 bytes of information in it. By information theory, we should expect that there are 1,999,980 bytes which are still unknown. That means 2^(8*1,999,980) possible files to explore. That is a number so large that you start talking about heat death of the universe before every atom in the universe magically acting as a 2Ghz processor, working in tandem, could find it. And that doesn't include the challenge of actually figuring out which of the solutions is the right one. It's just the cost of eventually producing the right one.

Some have mentioned that you have additional information. For example, you have the SHA-1 of the entire file. Sadly, this is not very useful. Presuming you have this hash as well, you now have 1,999,960 bytes of information which are still unknown, and thus 2^(8*199,960) possible slices to consider. We're still in the heat death of the universe realm. We could add additional constraints, such as continuity with the existing video, but eventually we're going to run into limits as to how much we could possibly know about the slice without having enough information to just recreate it directly from the information we know.

The best chance you would have is to have the entire world all band together to solve your problem, and feed you every 2MB slice of data in the entire internet. It is highly likely that if you "lost" the data, someone else might have a copy of it. It's much easier to scan through the petabytes of data humanity has gathered than to can through the far larger number of possibilities 2MB of arbitrary data has to offer.

share|improve this answer

It´ll basically take too long to achieve a satisfying result, addressing both: generating the missing video-part (according to computable criteria) and sorting the best ones out of them (that needs human intelligence or extremely high developed AI). Even if you finally have a nice video matching all criteria, you´ll never know if the original movie had the same contents. It might make no sense trying to "reconstruct" something that can be most variable - better and faster: use your own fantasy.

Certainly some "crossfiring" 10 Byte hash-values can´t represent/contain the information of 10 MB, so I think your gist is the following:

Even if you have lots of additional information for corrections inside the whole video-file: data-format, frames, the storyboard itself, voices of the actors and so on: there will be thousands of more or less different videos that will fit all known criteria. I´d even assume that a handful of single video-frames here and there could make any video leading to the same hashes.

This question is very alike: Is it possible for a (small) virus to add itself to a (big) file while keeping the file´s checksum the same value by padding a (not so big) amount of variable bytes? I guess it´s possible, though hard to calculate in time today. On the other hand, we know that many possible codes lead to the same hash, so computing time might be overestimated. Maybe it´s possible in seconds - only hackers will know.

Edit: Over night I got the inspiration for a nice additional comparison of your "lost-video-part-problem": For such cases (complete data recovery) there has already been invented the RAID-5 technology (Wiki see here: https://en.wikipedia.org/wiki/RAID ). One out of three or more harddrives could fail and all data can be reconstructed lossless. Certainly you have lots of data-overhead (redundancy for error-correction) stored over all drives to be able to do so.

Hashes/Checksums are good for detection of little (bits or few bytes) tampering/errors that occured somewhere inside a file. More advanced are CRCs with error-correction. At least we have redundacy-systems like RAID.

share|improve this answer

Hashes are designed to be one way. Its easy to travel from left to right, but it is practically impossible to travel from right to left when talking about Hashing.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.