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."
> El-Khalil concedes that the method is imperfect -- an application that's been impressed with a secret message has considerably more "negative subtractions" than an unadulterated program, making it easy to pick out through a statistical analysis.
Note that as far as I remember, stenography by definition is supposed to make it imposible to prove that there is data hidden there - one step further than normal encryption. It's not so much as about hiding the data as being able to deny its existance.
One reason for this is if you have encrypted data on your disk, then courts can demand the password for it. Stenography allows you to insist there is no hidden data.
It exploits redundancy in the i386 instruction set by defining sets of functionally equivalent instructions.
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?
If a message is embedded in a binary with this method, can another message be embedded in the resulting binary the same way, or has the required redundancy already been eliminated?
$x='S24;r)>63/* h@<5+oZ)32"5cz';$me='phroggy'x$];
$x=~y+ -xz+\0-Tx+;print$_^chop$me for split'',$x;
if you are using a relatively common binary. Then you just have to compare the MD5 checksums against a known-good (known-bad in MSFT's case ;P ) to identify a binary that could possibly contain encrypted data. Would it then be too much harder to go back through and disassemble the two and pick out the differences and hence identify the bits?
Novel idea though!
...until somebody embeds "seineeW erA sreenignE epacsteN"?
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.
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).
so how do i add my 6MB ogg to the 526K ls?
Yeah, I know another unchecked perpetual motion machine story from timothy. But no, in this case, the story is not wrong, its just 15 years old (the technique was used 15 year ago, I mean.)
The key point is to exploit x86 instruction set redundancy to find a few bits of entropy here and there strewn throughout the executable code. RISC instructions have the same potential. For example:
add r0, r1, r2
add r0, r2, r1 # not much different
> Second, and most importantly, the size of the file is dependent on the size of the bytes
> within the file.
I don't know about you, but where I come from all bytes are pretty much 8 bits in size.
>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.
Altering the value of a byte changes its size?
Man, I need to get me some of them new magic size-changing bytes! Down with the tyranny of 8-bit bytes!
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.
the size of the file is dependent on the size of the bytes within the file
:D ..... mkaaay.
so a byte containing the value 233 will create a larger file than one containing the value 3? interesting. Maybe you should stick to prgramming in c#.
my sig
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.
The most interesting and difficult part I get from this is how can you be sure that the modifications are not done in DATA or in executable format headers (ELF eg).
I would recon you would need to be able to disassemble the whole thing before being able to make modifications. Otherwise you could touch static data (vars initialized in the code) or the executable format (some of the metadata about the executable, the ARCH field in and ELF binary eg).
I spoke too soon! Actually now that I've read the article myself and dug deeper in the story I realize there is a bigger issue here. The technique used in "Hydan" actually is broken! The ADD and SUB instruction will set the carry flag in opposite directions meaning simple code sequences like:
...
...
...
A -= 3;
if (A 0)
Which might be encoded as:
SUB EAX, 3
JC
will cease to function correctly!! The technique I cite (which has been proven and used in the a86 assembler) *DOES* work, since you don't change any of the instruction semantics, but just the instruction encodings.
So in fact, this *IS* yet another bogus story posted by timothy
You work with pretty old computers like the IA32 then, and ancient character sets to boot :-P
Where I come from (which is C), the byte is defined as the smallest addressable unit of store (memory, IOW) that can hold one character from the execution character set (i.e. the number of bits in a char). If I'm using ASCII, then the character set is seven bits wide and the smallest addressable unit of store on an i686 is 8 bits, so the byte would be 8 bits. If I'm using EBCDIC on a computer that can address eight-bit-wide units of store, then the byte is still 8 bits.
But now consider a computer that can address eight-bit-wide areas of store, but my OS uses 16-bit Unicode. The byte is now 16 bits, as that's the smallest chunk of memory that can hold a single char. Or a computer that deals in 32-bit-wide chunks only, but I'm (for some Godforsaken reason) using Baudot coding as my execution character set. Now my character set only takes up five bits, but as the minimum addressable unit of store is 32 bits wide, the byte has to be 32 bits.
A common misconception is to think that the byte and the octet are interchangable concepts. They aren't. The octet is eight bits, the byte is defined as above (see the ISO C99 standard, for example). It's probable that every system you've used has an 8-bit byte; but don't start thinking that's a universal concept.
Just kidding, but you KNOW that's how it will be viewed by the 'outside'..
I bet the get shut down, under the patriot act, before you can say 'what's that knock at the door'..
---- Booth was a patriot ----
You're confusing "byte" and "char". "char" is related to character sets, "byte" has nothing to do with them. Just because you're using 16 bit unicode does not change the size of the byte, it simply means that your "char" is two "bytes" (if your bytes are 8 bits). Why would a unicode system half the resolution of memory just because of the character set used? You could have a byte of 8 bits, a character of two bytes, or a byte of 128 bits and a character of 256 bits. No connection between the two.
There are cases in which the way the carry flag is set doesn't actually matter. In fact, I suspect that in most cases it doesn't actually matter. But, you're right, unless Hydan carefully analyzes the code to make sure it doesn't matter, it's broken.
Need a Python, C++, Unix, Linux develop
...but why?
Why would I want to hide messages in my executable files?
Because I'm a secret little squirrel who just in general likes to hide stuff, like INSIDE other stuff?
- Replace length fields with two fields (length of length, and length) to avoid attacks on stream cipher.
Attacks on stream cipher?
And that's only one reason too ;)
Why is C the authority on what a byte it? Bytes were around a long time before C.
I'm not so sure about hiding messages in executables, but there were two interesting messages hidden in the n64 game The new tetris. The messages were hidden in 00B8FF90 of the US ROM. They were also in the PAL rom about 2k further. Anyway, here it goes:
****START MARTIST RANT**** I must say, this was a fun time coming down to San Francisco to do The New Tetris. Allthough there were a few problems. First of all being our producer.. D*N, my god.. is this guy useless or what?? I don't hate you D*N.. but you SUCK, and I mean SUCK as a producer. You should go back to testing video games, but I doubt you could even manage that properly. I feel sorry for you. During this project you just sat around and played video games.. starcraft and everquest. Don't even deny that.. when you WERE working, it was making stupid Excel (tm) spreadsheets to try and tell me how many bugs I had left to fix on a graph.. like WTF is that??? who cares.. I have the bug list in front of me, like I need to see it in freaking technicolor. So D*N, I must say this.. hold onto, and fake your job while you can, because once they find out how truely useless you are, you will be out of a job. I cannot think of any skillset you would fit into in this industry, so you better hold on tight. (This guy thought I could save a name in 8.4 BITS.. like umm.. .4 BITS?? WTF is .4 BITS?? its either ON or OFF, not in between... anyhow, Enough about you though. To Nintendo.. It has been nice working with you.. Alot of you are great or were great. Tom 'Snoop Dog' Hertzog - you were great.. one of the nicest people I have ever met at Nintendo. You and your crews bug testing was outstanding and I commend you for the excellent work. Erich Waas - You know we have been friends a long time, but I must say this. After you had accepted the ART form for The New Tetris, and later on your higher ups said it was not UNISEX enough, you slapped the blame on H2O, Chris Bretz in particular. You did not have the balls to accept blame for your mistake, and stuck our entire team under IMMENSE stress and FRENZY. This to save your A$$ from getting in trouble at Nintendo. I still like you Erich, which is more than I can say for the rest of the team that you screwed because of this. But I guess your standing at Nintendo is more important than the friendships you had here. You always knew we had telent and you recognized that. I know you wanted to work with us again one day maybe outside of Nintendo, I think you screwed up those chances though. While I am screaming.. I might as well say this: Niel Voss.. your music is freaking KICK A$$.. you are one really damn talented boy. BUT, you are one of the laziest music guys I think there is You could go far if you wanted to, but you just lack the GO for it. It is a shame. I wish you all the luck and would reccomend you to ANYBODY just because even though everything is last minute, and like pulling teeth, the end result is AMAZING. I am leaving H2O after this project to work at 3DO. I hope this will be a good move for me. I love H2O, As amazingly disorganized of a company it is. I LOVE the people, I have so many good friends there. It will be hard to move on. Of course they will stay my friends. They were more than just co-workers.. they were FRIENDS. They were the people I lived with, spent my days and nights with.. went to bars with, camped with, drank with (alot), did other bad things with (wont elaborate ). They are true great friends, and I love them all and will miss them dearly. Allthough Vancouver is only a 2 hour flight away, I hope I can visit often. My best friends would include. Ross, Max, Scott, Jake, Bretz, Roland, Johnny, Sarah.. these are the people I love the most. And I wish you success. My 4.5 years at H2O were basically, making games.. drinking alot, playing pool alot, going to bars and raves and dancing while really screwed up in the head. THAT HAS TO BE THE MOST FUN I HAVE EVER HAD, and probably ever will. The good old days. These guys are in Vancouver right now because I got stuck finishing this project in San Francisco (Which by all means I LOVE and am staying (hence 3DO)) Well boys and girls, I just thought I would immortalize some thoughts I have at the moment into a rom which will be burned forever. This game sucks. The music is great but the game itself is not how we wanted it unfortunately. I mean, it is a good game, but some things could be polished, as well as sped up. Could use another month to finish this thing off AFTER all the bugs are fixed. oh well, woh is me. I would love to give special loves and kisses to the following. My Girlfriend Amy Bond, My Family (Joy, Allyson, Jon Pridie, Brant Sangster), My really really best old friends Selim Arikan, Cory Haberly, Jason Vasilash, Alfred Huger, Oliver Friedrichs. Goodbye H2O, it was a blast, and I mean that with all my heart. (C) 1999 July 1 David Pridie If you are reading this, you can obviously see this disclaimer. All this material belongs to David Pridie. If you find it and want to post it in ANY media format, you must get my permission or feel my wrath . This text if it is ever read, is intended to be read by hackers whom have dumped the contents of this rom and viewed it. That is ALL it is for. And maybe some of them will remember me from the C64 and PC days, Martial Artist of PE/TDT/RAZOR 1911/INC/FLT/TRN/FBR, I was in them all.. and I made trainers and intros mostly. I thank that scene for teaching me how to program, because without it I don't think I would be where I am today. Well that does it 4.5 years and Two games later (Tetrisphere and New Tetris). Unfortunately I wont be working on Nomans Quest.. but oh well. HAPPY CANADA DAY. ******END MARTIAL ARTIST RANT ******
*****START LUPIN RANT FOR 50 MOST HATED THINGS*****1] Idiot teens hanging out in front of 7'11s, KFC, McDonalds, Jack In The Box etc... Your life REALLY SUCKS if that's the high point of your day...2] A$$holes who spit on the sidewalk.3] Drivers who don't know how to use a turn signal. I can reach mine with my pinky while driving. It's not that hard.4] Teens with their pants around their a$$.5] People with personalized licence plates.6] BMX bikes.7] People panhandling me. Get a job losers! McDonalds is always hiring!8] Bums with dogs. I'm sure the dog loves eating cheese from old pizza boxes.9] The cheeseheads from asia who take a Honda Civic, slap some stickers on it, put a muffler on it that makes it sound like a riding lawnmower, a ridiculous sized fin on the back and think they have a formula 1 racer. 'Devastating Power!' my a$$!10] The same idiots who then drive their 'hot' civic like they are in the Indy 500 through busy traffic.11] The huge complex hairdos on african american women, 5 layers, 6000 curls, 4 sprouting areas, 200 dangling bits, 6000 beads, air conditioning and enough hairspray in it that it wouldn't move if Hurricane George hit it.12] People with Kleenex, plants, knitted blankets, stuffed animals, or lacey things in their cars rear window. I should be allowed to pull over and shoot them.13] People on the bus who talk so loud your forced to hear about their pointless lives.14] Crappy parkers who park their car REALLY close to the painted line so that you have half a foot to get out.15] Those old cars (ie, Cadillacs, Lincoln Town Cars, etc...)usually white for some strange reason... with the acient driver who always drives WAY under the speed limit.16] People who write a cheque for a $2 bag of nachos at Safeway.17] Corvettes, Comaros and Firebirds. Come on, the 80s are OVER!18] A$$hole tailgaters.19] Idiots who think they can pedal a bike as fast as a car, so they ride in the middle of a traffic lane. You should be allowed to run them over, it looks like natural selection to me.20] Teenagers on television news reports expressing their opinions on something. If your under 18 I don't give a sh1t about what you have to say...21] The singer Brandy, Celine Dion, all the divas....22] Twits who wear a huge parka outside when its sunny and a mild 5-10 C. The same thing goes with the whole scarf thing.23] Muni busses that smell like urine. Which is most of them.24] Corporate Broadcasting logos in the corner of the channel your watching.25] Web pages that pop open other pages and windows and then disable your 'back' button.26] People who walk around with a huge 'portable' stereos blaring, sharing their music with everyone around them. Usually crap rap.27] Junk mail.28] Peice of sh1t cars that spew out huge noxious clouds behind them.29] People that throw out huge items on the curb expecting the garbage people to remove it. Like old dirty matresses. They don't of course, and it sits on the curb for weeks.30] Budweiser beer and the people who drink it. I'd rather suck the piss out of a pig... Its time to poison the bud.31] Drivers who turn onto the road RIGHT in front of you causing you to slam on the brakes, even though there is no one for hundereds of feet behind you.32] People who drive 3/4 in one lane and 1/4 in another... what the hell is that????33] Religous people who push their drivel on you when your walking down the street. Or come knocking on your door.34] Dead web page links and 'Document not found' errors.35] Racisist people and the crap they spew out.36] Those stupid add banners from Geocities on the Internet when you hit someones home page going through them...37] All country music.38] Minivans.39] People who spray paint their names on rocks, signs, trees etc, in national parks. Like I care that Bill graduated in 86.40] Small yappy 'feeder' dogs. Like little Yorkies, poodles, etc...41] People in the fast lane who drive just 2 km/hr faster than the guy in the 'slow' lane, dawdling along.42] Film crews making bad movies most people doent want to see blocking the streets and being annoying.43] Big fat bugs that splat on my windshield.44] Those really tight spandex cycling pants on men, they are usually sooooo tight, you can tell if they are cirumcised.45] Those really tight spandex cycling pants on 90% of the women. Big fat a$$es and *wiiiiiiiiiiiiiiiiiide* camel toes.46] Those really annoying commericals from Rogers Cable that tell you all about the 'evils' of satalite tv and how lucky you are to be getting cable for a mere $65 a month.47] Commercials that are SO bad on tv, you have to wonder about the sh1t for brains who thought them up. Like the Old Navy commericals, or the old as hell commercial for Sarah Lee, that is STILL ON THE AIR, 'let them eat cake' and 'But Patrick, I'm to old for life insurance.' Shoot them ALL!48] Losers that listen to totally cheezy radio stations and then slap dozens of their stupid stickers all over thier car.49] Lilith Fair. I say when they are all hugging, listening to the music, sharing tampons, and bitching about how evil men are, toss in a few hundered grenades while recording it on camera. Sell the video as a 'To Hot for TV' tape late at night.50] Cheap a$$ manufacturers of DVDs who list as 'features' chapters, interactive menues, and the time. These arent features. Thats like calling your computers keyboard a 'feature'. Lame a$$ marketing people.51] DVD manufactureres that sell their DVDs for $40 and up, just because they know people will pay for it. DVDs have actually become MORE expensive than when they first came out.52] Nintendo and everything about them.53] Old people who clog up the sidewalk walking super slow when you want to get somewhere.54] Looking at demo-reels at work that are so incredibly bad, that I just want to call them up and tell them to go f*ck their demo reel and to never EVER send another one out to anybody. EVER.55] Spiders. All spiders. Everyone of them.56] How on the Nintendo 64 game machine, half the damn titles for it are called 'miscvidgame 64'. Why not come up with a real name? Why is everyone just slapping a 64 on all the games?**********END LUPIN RANT******** I got these rants from dextrose
13 year old white supremacists are shitty web designers.
This like any solution is not fool proof. The catch is if you have managed to get hold of both the orginal and the modified copy. A quick MD5 check will reveal that both are different and could lead someone to suspect that something has been done. Now which one is the modified version? You could do this using a statistical method, by finding out which occurrence appears more often on the net. So to achieve the trick correctly you need to make the modification to an executable that does not exist on the net.
Another method to detecting an executable that contains hidden data is to work out whether the executable uses the most unusual method of implementing its assembly.
Of course just like in the film 'A Beutiful Mind', you could just end up seeing encrypted data left right and center, whether or not it is really there.
Jumpstart the tartan drive.
Surely, a declaration of independence should be stored in a non Microsoft product.
I hide all sorts of stuff in my C comments.
Nobody can detect them in my executables.
HA! I'm so sneaky!
Moneyed corporations, non-working 'poor' and criminal prisoners are turning productive citizens into tax-slaves.
Ahhh! If my byte moved from 8 bits to 16 bits, did my nibble become 8 bits instead of 4? Did my bit beceome 2 bits? If my bits can double, I'm in trouble! - Head Explodes -
Friends don't help friends install M$ junk.
There is no "byte" data type in C
There are distinct "byte" and "char" data types in the Java programming language. The "byte" is 8-bit as expected in PC-type and RISC architectures, but because the Java programming language's native character encoding is UTF-16 Unicode, "char" is 16-bit.
Will I retire or break 10K?
"The SUB instruction
Which means that the CF stays the same for both instructions since their results are the same.Is the same as:So, "Hydan" works.
-j
The picture had a caption that said, "Everytime you masturbate, God kills a kitten... and a plane full of infidels."
Furthermore, there might be cases where it doesn't matter if the program works. So the program crashes or has logical errors. Does that make you 'guilty' of having hidden data in your file?
It'll be a strange day in legal history when the _user_ gets arrested/blamed/indicted because his computer crashes.