<p>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.</p>

CC BY-SA 3.0
2012-12-30T18:35:14.303Z
Downvoted because this is too speculative and non-mathematical to be helpful as an answer here.
David Eppstein
CC BY-SA 3.0
2012-03-21T13:39:21.200Z
2012-03-21T13:39:21.200Z
Jeremy List
<p>No.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-07-06T21:15:48.873Z
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.
Jay
CC BY-SA 3.0
2011-07-06T15:12:23.100Z
2011-07-06T15:12:23.100Z
deong
<p>Is it theoretically possible to reconstruct the contents of a file from its id using evolutionary computing? </p>

<p>A file in this case can be a text, image, video or audio file.</p>

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

<p>And evolutionary computing here can refer to genetic programming, genetic algorithms, annealing....</p>

CC BY-SA 3.0
2011-07-06T15:00:39.037Z
You are asking to reverse the md5/sha1 algorithm?
Dave Clarke
CC BY-SA 3.0
2011-07-06T20:25:44.007Z
That was not the intent of the question. But I believe that it could be unintended side effect
Jay
CC BY-SA 3.0
2011-07-06T23:34:00.890Z
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.
George
CC BY-SA 3.0
2011-07-07T08:23:15.003Z
A hash is meant to be unique for every piece of datum. Isn't that the purpose for using algorithms like md5 and sha1?
Jay
CC BY-SA 3.0
2011-07-08T23:11:19.530Z
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.
deong
CC BY-SA 3.0
2011-07-11T17:44:55.540Z
Thank you very much. That made a lot more sense than all the down votes this question has received. Now I know it would be futile to even think about what I am suggesting in this question. So in conclusion, it is mathematically impossible to reconstruct a file from its hash(sha1,md5), since; depending on the size of the file, every hash can be mapped to more than one file of the same size...and hence, its hash ceases to be unique.
Jay
CC BY-SA 3.0
2012-03-08T19:02:41.400Z
Like the [Pigeonhole principle](http://en.wikipedia.org/wiki/Pigeonhole_principle).... if you have 9 holes and 10 pigeons, then you know at least 1 hole is going to have to share at least 2 pigeons.  Same problem with your id that you hoped was going to turn into a jpg file of Jodie Foster, but instead after "evolving" from your id a jpg of Queen Elizabeth comes out instead. It's a hash collision.
Marcos
<ne.neural-evol><genetic-algorithms><genetic-programming>
Genetic algorithms
Jay
# Genetic algorithms

(Asked by: username_0 on 2011-07-06)

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....

**Tags:** ne.neural-evol, genetic-algorithms, genetic-programming

> **Comments:**
> **username_1**: You are asking to reverse the md5/sha1 algorithm?  
> **username_0**: That was not the intent of the question. But I believe that it could be unintended side effect  
> **username_2**: 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.  
> **username_0**: A hash is meant to be unique for every piece of datum. Isn't that the purpose for using algorithms like md5 and sha1?  
> **username_3**: 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.  
> **username_0**: Thank you very much. That made a lot more sense than all the down votes this question has received. Now I know it would be futile to even think about what I am suggesting in this question. So in conclusion, it is mathematically impossible to reconstruct a file from its hash(sha1,md5), since; depending on the size of the file, every hash can be mapped to more than one file of the same size...and hence, its hash ceases to be unique.  
> **username_4**: Like the [Pigeonhole principle](http://en.wikipedia.org/wiki/Pigeonhole_principle).... if you have 9 holes and 10 pigeons, then you know at least 1 hole is going to have to share at least 2 pigeons.  Same problem with your id that you hoped was going to turn into a jpg file of Jodie Foster, but instead after "evolving" from your id a jpg of Queen Elizabeth comes out instead. It's a hash collision.  

---

## 2 answers

### Answer by username_3 on 2011-07-06. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_5 on 2012-03-21. Score: -1

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.

> **Comments:**
> **username_6**: Downvoted because this is too speculative and non-mathematical to be helpful as an answer here.  

---

