1

Theoretically, is it possible to hash an executable file and have the output hash end up being another executable file?

I know the chances of this are unimaginably small, but I'm curious.

| improve this question | | | | |
  • 1
    Wait, are you asking if a hash itself could end up being executable? If that's what you are asking, then no, that's not how hashes or executables work. – schroeder Sep 24 '19 at 11:32
  • @schroeder yes, that's what I was asking sorry for bad wording. I thought that was the case but me and my friend were debating it. He says if you hash the data of the executable, then turn the hash back into bytes there is a tiny chance that the file will be a valid executable file. – Owen Throup Sep 24 '19 at 11:33
  • 1
    Only as much as any random string has a chance to end up being ordered. – schroeder Sep 24 '19 at 11:42
  • 1
    In other words: "tiny chance" is a huge exaggeration. The probability of this happening is so much near zero that it will not happen in practice. This is at least true for the common understanding of "to hash" and "turn into bytes". One could create a hash algorithm or a "turn into bytes" algorithms where each output is an executable program. – Steffen Ullrich Sep 24 '19 at 11:50
  • 2
    If you ran a random character generator, could you end up with the first line of Hamlet but in Klingon? Yes. That's the type of scenario that you are imagining here and it really doesn't have anything to do with hashing, really. – schroeder Sep 24 '19 at 12:02
4

Well... rather than worry about the statistics, which as you mentioned is unimaginably small. Let’s take another angle.

Depending on the hash function, the output is usually 256-512 bits long, but according to this the smallest possible exec in Windows is 97 Bytes — which is 776 bits.

Hence if you’re using Sha256 or Sha512, I Guess the answer is definitely no, as there’s just not enough bits in the output to make the file.

Different hash functions that can output hashes that are at least 776 bits Long are the only ones that are possible to ever be able to make an exe by hashing another exe.

Nice theoretical question — but again, very very very Low probability.

| improve this answer | | | | |
  • How about encrypting rather than hashing the executable? – Owen Throup Sep 25 '19 at 10:11
  • Then if you encrypt any large enough payload -- you can possibly find that the output of the encryption would also be another executable.... but again vanishingly small probability. That being said, encrypted files are rarely given .exe extensions in Windows, or executable permissions in Linux – keithRozario Sep 25 '19 at 14:30
2

No. The hash function is used to index the original value or key and then used later each time the data associated with the value or key is to be retrieved. Thus, hashing is always a one-way operation. You cannot recreate a file from it's hash. Thing of hashing as a more complex parity check.

What you can do is index what hash results by hashing a known file (.exe or not) and then re-associate the indexed data to the hash when you need. But for that you would need the indexed content. That is a tactic used for password dictionaries. They store the original values (the passwords) so you can find them by searching for a hash.

If the question was trying to determine if a hash could end up being executable, the answer is NO again, since an .exe starts with specific, special characters and hash results do not contain those special characters.

In the case of normal executables, you must have MZ+some special ASCII to start with, otherwise the .exe would not be valid.

In the case of old .com files, again, for something to execute it will have to contain non-alphabetical ASCII.

One of the shortest .com files I've ever created was a 20-character one, used for restarting MS-DOS PCs. Out of those 20 characters, only 4 are obtainable by hashing.

| improve this answer | | | | |
  • Only 4 are obtainable by hashing? A .com file has no headers at all, so any string is a valid .com file (but few do anything interesting). I can't see how are only 4 obtainable by hashing - unless you use hexadecimal hashes. Either way, anything is a .com executable, so that format is probably not worth considering for the purposes of this question. – my pronoun is monicareinstate Sep 25 '19 at 12:36
  • If we ignore .coms we're pretty safe with a definite No answer. – Overmind Sep 25 '19 at 12:54
2

Not in a Linux system no. An executable file in Linux is determined by whether or not the executable permission bit is set. The executable permission bit is part of the file metadata, not file content.

With Windows, it's also not possible, because executable is defined by file extension. Unless the hash is being used for the filename as well, and unless the hash encoding allows a . in the output, there's no chance of accidentally producing an executable file.

With that said, I think the real question here is whether it is possible that the hash of a file could produce a valid ELF file or PE file file.

If you're using hex encoded hash (which is the most common way a hash is encoded and used by users), then the answer is simply no. Both ELF and PE files requires non printable characters in their magic number (ELF: 0x7F followed by ELF (45 4c 46), PE: "PE\0\0" (the letters "P" and "E" followed by two null bytes).).

If in the other hand, you're using raw hash (byte encoding), then it is theoretically capable of producing any files that are shorter than the hash size. According to this, the smallest ELF file is 45 bytes (~1405-bit); according to this, the smallest PE file is 97 bytes (~1689-bit). So to have a chance of colliding with these files you need a hash algorithm that produces at the very least 1405-bit and 1689-bit output respectively. This is way larger than most standard hash sizes, which rarely go beyond 512-bit.

So, no, it's plainly not possible with standard hashes to collide with an executable file, not even in theory. Though it's certainly possible with the concatenation of multiple hashes or with non standard hash with large output size or non standard encoding.

| improve this answer | | | | |
1

Yes, theoretically possible. As is throwing 256 coins on the air and all of them coming down tails. There's no law forbidding this to occur, but the same laws dictate that the probability is so close to zero that you can, for all practical effects, call it impossible.

unimaginably small

It's not unimaginable small. Is dozens of orders of magnitude smaller than that. If you can get every single executable file ever created, and hash every single one using every single hash function ever invented (even by first grade kids, if any), I would bet on throwing that 256 coins in the air, and getting tails on every one.

| improve this answer | | | | |
  • There is more than one possible executable for any given string length (if it is long enough to fit a header, I'm not sure if 32 bytes are enough for a modern format), so, assuming your hash is 256 bits long, it's more likely than all of them coming tails. – my pronoun is monicareinstate Sep 24 '19 at 12:43
  • Smallest possible PE executable: 97 bytes. Try with 776 coins, the chances are the same. – ThoriumBR Sep 24 '19 at 12:53
  • 1
    And this guy created a 45 byte ELF file. I still bet on the coins. – ThoriumBR Sep 24 '19 at 12:56
  • 1
    My smallest executable file has 20 bytes. At 174 bytes I already got a screensaver. But what you say cannot practically happen. See a little the second part of my answer. – Overmind Sep 25 '19 at 8:15
  • @Overmind one can invent a hash function that uses the entire 256 ASCII values, so the last part of my answer checks out. A .COM file with only INT 19 on it would be shorter (would reboot MS-DOS), but I wouldn't consider that an executable... – ThoriumBR Sep 25 '19 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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