Slashdot Mirror
Program Hides Secret Messages in Executables
DmuZ writes "My friend Rakan has created a new steganographic tool named Hydan which can embed messages into an executable without altering its size. He recently presented this tool to the public for the first time at codecon. This new technique was intriguing enough to get coverage on SecurityFocus.com. The code is available here."
Add -ldl to the LDFLAGS in the Makefile.
This is a well known technique that was used in the mid-80s by Eric Isaacson in his product "a86". See here: http://eji.com/a86/
Eric Isaacson used the technique to mark executables, so that he could determine if they were created with an unregistered copy of a86.
Some instructions have dont care bits in them.
You could remove these bits in order to compress the file but they occur so rarely its not worth it.
And yes the redundency would have been used up.
Mouse powered Chips, Open source Processors and Lego
It just means that you can encode certain stuff in equivalent ways (*). Like: mov eax, 0 xor eax, eax sub eax, eax are all equivalent in functionality to zero the eax register.
* = Taking into account flags and instruction size restrictions, etc.
The "redundancy" comes from these facts. So, it's not size redundancy as such, and you can't remove the redundancy. It's more like permutations of the instructions are equivalent (length stays the same).
Can someone explain to me exactly what this means? Will all i386 executable binaries have unnecessary redundancy? Could the size of the binary be harmlessly reduced by removing it? If so, then why isn't this done?
It means that if you want to add 50 to a number, you can choose to do (+50) or (-(-50)). They both take up the same amount of space and do the same thing. But if you first process a program to ensure that all additions and subtractions are actually additions, then you can encode data into the list of additions by making some of them into subtractions.
er...
Steganography requires that it is impossible to prove that data is being hidden there. (Without reference to other material, etc etc).
From The Free On-line Dictionary of Computing (09 FEB 02):
steganography
Hiding a secret message within a larger one in such a way that others can not discern the presence or contents of the hidden message. For example, a message might be hidden within an image by changing the least significant bits to be the message bits.
You are both correct and incorrect. While it's obviously not possible to simply go through changing instructions, operators and operands without consideration as to the effect on the program, it is possible to leverage functionally identical instructions to represent a bit.
If you read the article, a trivial example would be subtracting -5, rather than adding +5. The presence of a subtraction operation, rather than an addition operation can signify a binary digit.
Unfortunately, due to the consistent output from compilers, this is not steganography - you can both tell that the executable has been altered, and read the message! His plans for the future (parameter organisation, etc.) may be more relevant, but at the moment this is a proof of concept implementation, not a usable system.
Anyone interested in other forms of steganography could do worse than to read Andrew Tanenbaum's page on the subject.
Now what the author does is, alter the original binary string to that bit-string data of our interest (of the same length). This process requires flipping of instructions. For example, if some instruction is addition (1), but your data requires it to be (0) bit, you change the instruction to subtraction, and change the operand to a negative of the original value. Same applies to flipping a '0' to '1'.
Addition-subtraction works because there are no overflow issues (atleast with signed ints). Since this is also a very common operation, your executable is likely to be large enough to "hold" sizeable data.
Never. The information, though contained in an executable file, is not itself executable (unless you went and took that information out and then executed it separately. The whole point is it does not affect the execution of the program that you hide the information into. So you can put whatever information you want in there (even the code for a virus) and it will still not be a virus, because that information will never get executed unless you actively go in there, extract it, paste it as an executable file somewhere else (eg in memory) and then execute it - so you'd need another virus to do this, basically.
Daniel
Carpe Diem
Hiding messages within messages are used often in many contexts, like the radio broadcasts in WW2 sending "birthday greetings" among other things
This is no hoax
I has the same properties as:
a*b gives the same result as b*a.
You have options on what instructions to use which yields the same results.
Lets say a*b is a 1 and b*a is a 0. You could describe a byte with eight occurancies of the (a*b || b*a) operation.
a*b b*a b*a a*b a*b a*b b*a a*b == 10011101
A common practice with x86 is to use XOR AX, AX instead of MOV AX, 0 to clear the AX register.
However, this is not interchangeable since they do not have the same size. The XOR method is often used because it is faster and have less size IIRC.
Did you read the article?
First, executables are called executables because the computer interprets them. They are made of instructions, and unlike a document you cannot simply tamper with things because it will confuse the computer when it tries to run the executable.
Of course you can tamper with executables! As long as your modified version does the same thing, there is no harm done. If you change the addition of a positive number to the subtraction of a negative number, you get the same result if you run it. You run through the binary and if the current bit of data to be hidden is a 0, you don't modify that particular addition instruction and if the data bit is 1 then you *do* modify it. If you compare the modified binary to an original, you can see all the changes and extract the hidden data.
Second, and most importantly, the size of the file is dependent on the size of the bytes within the file. Because the bytes in the file have differing values depending on the instructions they encode, altering the data will alter the size unless you're borrowing from one byte to inflate another -- and in this case, again, you run afoul of the first problem.
This makes no sense to me. The replacement instruction is the same size as the original.
I'm surprised the editors didn't review this before approving it for posting. This is really pretty elementary to anyone who understands object code.
I don't doubt that you understand object code but you don't seem to understand this technique.
It should be easy enough to get around this. The statistical telltale is only due to the fact that El-Khalil consistently uses the same type of instruction to encode a certain bit value. Have Hydan XOR the hidden message with a secret key that produces the right distribution of ones and zeros prior to encoding the message and the problem disappears.
I'm afraid this will not work.
Problem is: 'normal' programs will do 'sub 50' instead of 'add -50'. If you don't want to be visible that a message is contained, you cannot change that. But if you don't change that (in about 50% of the cases), you can't hide the information! The only key that would work here would be as long as the message itself!
The technique you propose will work to get a more even distribution of ones and zeros, but not the 'all zeros' (sub 50) distribution that is present in 'standard' programs.
All stenographic methods that I've heard of leave some signs of tampering. For instance, the common method of hiding information in an image file by fiddling with the least signifigant bits in the RPG values is completely undetectable to the eye, however a statistical analysis of those low bits will reveal an unnatural amount of randomness. Really this is unavoidable since most any innocent looking data is going to have some natural order to it.
We hope your rules and wisdom choke you / Now we are one in everlasting peace