Is it possible to insert the hash of an executable into the executable itself without changing the resulting hash? What's the best alternative?

Question

I've been thinking about this problem recently and it really doesn't seem like it's possible, but I figured that I'd ask just in case.

Assume a simple program, in pseudocode:

run hash on an executable we think is mimicing the true executable
check the value against the hash that's hard coded into this executable
if it matches, do x
if not, do y

In theory it should be quite secure, since only the true executable would be able to produce the same hash that's coded into the executable, but the minute that hash is compiled into that executable the hash would change.

Do you think it's even possible to hard code the resulting hash in any realistic way?

On to the question that has a more likely answer; what would be the most secure way to make sure that an executable is in fact the same executable that was distributed with a program and not some impostor executable trying to hijack the system?

Answer 1

what would be the most secure way to make sure that an executable is in fact the same executable that was distributed with a program and not some impostor executable trying to hijack the system?

This has been solved.

You have to use a separate channel for the signature.

Any separate channel.

There are a lot of choices.

Trust comes from multiple stages of agreement. There is no absolute in trustworthiness. At any stage (any!) someone could be playing you false. Even if someone handed you a sealed and locked DVD with encryption and passwords required to mount and extract the binaries, the person preparing it could be lying. Nothing is absolute or final

Because trust requires multiple stages of agreement, you have to keep the hash separate from the executable.

You often see sites with yet more metadata like sizes, date stamps, and SVN keywords buried in the executable so that you can check many things to convince yourself that the executable is worthy of trust.

Which is, BTW, isomorphic to trusting the source for that executable as well as the channel between you and the source.

In the olden days we used to send activation keys by fax -- never by email -- to be sure that we were using another channel than the internet.

Answer 2

If the signature is bundled inside the executable, then nothing prohibits the adversary from modifying it to match the malicious executable. The only way to verify the executable is to compare with the hash fetched independently from a different source, or validate the signature using a verified public key.

Answer 3

The usual way of embedding hashes into a program would be to place the hash value in a specific known place in the executable, at the end is simplest. Build the application with a dummy value and then hash everything except the hash location. You can then update the hash value in the executable without changing it's value.

Any method of security relying on a single source will end up being an arms race. You can use this kind of hashing to protect against idle curiosity or generic viruses, but anyone with a motive will be able to break it.

Answer 4

First think about the threat model against which you want protection.

Do you just want to make sure that the executable isn't randomly modified, eg. by a virus? You can provide the hash in a separate file aside the executable.

Do you want to make sure that it isn't modified while downloading it? Provide the hash from a different source.

Do you want the best possible protection, even against malware that specifically targets your executable? Use a cryptographic signature with keys signed by a public certificate authority.

http://en.wikipedia.org/wiki/Code_signing

Don't forget to think it one step further. If you need an additional tool to check the integrity, and the attacker knows about your security system and was able to modify your executable, what makes you sure that he didn't also modify the tool for the check?

Answer 5

what you are asking is this: lets say we have a string. and hashing f(x) defined as string -> hash code where group "hash code" is subset of string.

so f(string) = sign

so we get "sign" as the result of the hashing.

now lets add the sign to the string (we dont care where so lets assume that operator + handles the position) and we get

f(string+sign) = totalSign

so we know we are looking for that totalSign to present to the other side.

however we want that sign=totalSign

when could that happen? well, f(string) = f(string+sign) is easy to know with out that porcess

bu a closer look will yeied since we know that f is the same so

string = mod(string + sign)

when sign is zero hash for f(x) or mod(sign) would be zero. that would work for only special cases.

can you see any other case that it would be possible?