-6
$\begingroup$

Is it theoretically possible to reconstruct the contents of a file from its id using evolutionary computing?

A file in this case can be a text, image, video or audio file.

The 'id' in this case, refers to any string that uniquely identifies that file. For instance, an md5 checksum or a sha1 hash...

And evolutionary computing here can refer to genetic programming, genetic algorithms, annealing....

Improve this question
$\endgroup$
7
  • 5
    $\begingroup$ You are asking to reverse the md5/sha1 algorithm? $\endgroup$
    – Dave Clarke
    Jul 6, 2011 at 15:00
  • $\begingroup$ That was not the intent of the question. But I believe that it could be unintended side effect $\endgroup$
    – Jay
    Jul 6, 2011 at 20:25
  • 1
    $\begingroup$ A hash can't be unique (at least not with a constant number of bits). Also, if the id uniquely identifies a file, it should be possible (not necessarily with genetic algorithms), but I think you need to have more information on the relation between the file and the id. $\endgroup$
    – George
    Jul 6, 2011 at 23:34
  • $\begingroup$ A hash is meant to be unique for every piece of datum. Isn't that the purpose for using algorithms like md5 and sha1? $\endgroup$
    – Jay
    Jul 7, 2011 at 8:23
  • $\begingroup$ Let's take sha1 for example. It produces 160 bits of output. There are thus 2^160 possible hashed values, which is admittedly a lot. But it's the same number as there are possible 160 bit files. Consider only the set of videos that are exactly 10MB. 10MB = 8*10*2^20 = 83,886,080 bits, which gives 2^83,886,080 possible 10MB videos (minus a few orders of magnitude, as all videos have to have certain headers and such). That means that there are 2^(83,886,080-160) = 2^(83,885,920) videos for each sha1 hash, or about 1 with 25,252,178 zeros. And that's only hashing exactly 10MB videos. $\endgroup$
    – deong
    Jul 8, 2011 at 23:11

2 Answers 2

Reset to default
6
$\begingroup$

No.

First off, note that there isn't nearly enough information in a hashed value to reconstruct any reasonable representation of content. Trivially, you could simply use the hash as an index into a lookup table, but presumably that isn't what you're asking.

If the question is can an evolutionary algorithm learn to match a hash with the specific video it was generated from (as opposed to constructing the video from scratch), then the answer is still "no", but for a more interesting reason. Search algorithms like GAs exploit structure inherent in a problem to find solutions without having to exhaustively search the space. Hash functions like sha1 or md5 are specifically designed to not possess this sort of smooth structure. Change one bit in a file, and the hash of the file changes arbitrarily. From the view of an optimization algorithm, the function it's being asked to learn is essentially random. With no structure to exploit, everything degenerates to random search.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I agree that there isn't enough information in a hash id to reconstruct the content of the file.But,I also think that each bit in the hashed value is a clue into the specific hyperplane that needs to be searched.As the GA finds solutions that have more and more bits in the right place, would it not be theoretically possible to narrow down the search to a small window?I have to admit,that I am by no way an expert on Evolutionary computing.It just dawned on me that maybe something like this could work.Whether it works or not,I end up learning something new.And that's the motive for the question. $\endgroup$
    – Jay
    Jul 6, 2011 at 21:15
-1
$\begingroup$

It is indeed impossible to reverse a function unless either it's injective or you're happy for the reversal to have an unknown number of results. But I don't think that completely answers the question. Genetic algorithms can be used as universal function approximators. If the representation used for the individuals is versatile enough (for example: a Turing-complete language): this can include functions from the set of all byte strings to itself. For example: you could use a set of pre-existing video files as training data and evolve an algorithm that takes the filename of any of the videos as input and outputs the corresponding video. One of my current hobby projects involves using this idea as the basis of a compression system. Depending on what kind of algorithm emerges you may even get valid video files by querying it with filenames that weren't in the training set, although I wouldn't bet on them being entertaining.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Downvoted because this is too speculative and non-mathematical to be helpful as an answer here. $\endgroup$
    – David Eppstein
    Dec 30, 2012 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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