This seems like it'd be almost comically easy to detect, because normal compilers and assemblers would consistently use either 31 C0 or 33 C0 all the time, rather than bouncing back and forth between them within a single program.
back
3 comments
Author here: it is indeed easy to detect. I didn't base my work off of Hydan but it uses a similar strategy, and there are several[1][2] public steganalyses of it.
Edit: I previously claimed that this method might be easy to deny. It isn't, and I've added a note to the post as well.
[1]: https://cosec.inf.uc3m.es/~juan-tapiador/papers/2009sec.pdf
[2]: https://www.sans.org/reading-room/whitepapers/stenganography...
It's not easy to deny. Normal compilers flat out don't produce binaries that look like this, so if a binary looks like this then you definitely know something fishy is going on even if you can't decrypt it.
Contrast with steganography in least significant image bits; you genuinely cannot determine at all if an image is carrying hidden encrypted data. That's what easy to deny looks like.
> It's not easy to deny. Normal compilers flat out don't produce binaries that look like this, so if a binary looks like this then you definitely know something fishy is going on even if you can't decrypt it.
Yes, you're right. I've updated the post to include a note at the bottom saying that this technique is difficult to provide deniability with.
> Contrast with steganography in least significant image bits; you genuinely cannot determine at all if an image is carrying hidden encrypted data. That's what easy to deny looks like.
This might be a misunderstanding on my part, but I thought that LSB-style steganography had been broken by both statistical analyses and ML models for a while now[1]. But it's possible that these methods only work on plaintext messages; I haven't looked deeply into it.
You are right, in the sense that there are companies out there (I used to work for one of them) that do image, video and audio watermarking. In the simplest terms that's also adding imperceptible "noise" that statistically builds up to a few bits of data.
I am not sure to understand how the program can make a distinction between 33 C0 (because it is written as 33 C0) and 33 C0 (because it was written as 31 C0 and was later changed by steg86 to 33 C0)?
Or, seen the other way, maybe steg86 can "extract" (from already existing untouched binaries) secret messages that were never intentionally written?
This is a really good question!
steg86 currently embeds a 32-bit header for itself. You can see the relevant constants here[1]. If the header doesn't validate during extraction, steg86 fails instead of extracting potential garbage.
[1]: https://github.com/woodruffw/steg86/blob/master/src/steg86/b...
OK, but how is the 32-bit header itself embedded?
The header is a good thing for preventing accidental extraction from binaries not treated with steg86, but still you need to modify 4 bytes (or 4 instructions) to embed this header, so - at least theorically - the possibility of a "collision" or of a false positive seems relatively high to me.
> OK, but how is the 32-bit header itself embedded?
The header is embedded according to the same rules as the rest of the message: it's treated as a bitstring, and flippable instructions are flipped appropriately to encode it.
> the possibility of a "collision" or of a false positive seems relatively high to me.
As others have pointed out, compilers (and assemblers) tend to stick to a single selection choice for register-to-register ops. Even in the case where a compiler writer flips between them randomly, their 32 random choices would have to align precisely with the expected header. It's certainly not impossible, but pretty unlikely. It's also completely remediable with a CRC32 or similar field tacked onto the header; I just didn't think the likelihood warranted that for the initial design.
4 bytes of the encoded header isn't 4 instructions, it's 32 consecutive instructions that each translate to a bit depending on their semantic form.
So there is virtually no chance for a compiler to generate a valid sequence randomly.
I see, each changed instruction gives a single bit (not byte) of information, my bad.
Are there other semantic duals in the instruction sets? If so, when combined with cryptography, it would offer some additional level of plausible deniability over which of the possible messages (due to parameter selection) is the cryptotext.
The two most obvious are:
- Register allocation choices
- Instruction ordering choices
Also conditional branches because you can conceivably do the comparison, branch, and fall-through in several different ways. Consider the initial case
cmp ax,bx
jge foo
bar:
; code that gets run if ax < bx
foo:
; code that gets run if ax >= bx
But that's not a fundamental issue of the idea and rather a quirk in the steg86 implementation, right?
Which part? The header is specific to steg86, and some of its constraints (like the maximum message size) are a product of that. Otherwise, there aren't any quirks in the implementation that I'm currently aware of.
The same problem is faced when you present basically any kind of encryption scheme with random data. It would be easy to fix that kind of problem by adding a checksum to the secret message.
Besides, in what scenario would you be decrypting arbitrary binaries with this, such that it would be a problem for you to have false positives? Just make sure to use it only on files which you know contain secret messages.
>Besides, in what scenario would you be decrypting arbitrary binaries with this, such that it would be a problem for you to have false positives? Just make sure to use it only on files which you know contain secret messages.
Well, more or less cryptography/steganography can be used to either store "secrets" or to communicate them.
If I used something like this to communicate, I would probably tell the other part to download (say) a .iso full of binaries, as opposed to a single binary.
I think from the perspective of steganography the question is also: How often is byte code checked for anything like this?
Steganography is like a magician's act; it's only undetected if you don't go and look for it. I think, in principle, if you are the only one using the tool, and didn't tell anyone, why would anyone look for it?
This particular trick is easy to detect when you're looking for it, but that doesn't mean that it's easy to realise that you should look for this trick (I'm not about to make "check the assembler for strange compiler choices" part of my workflow for installation of a new binary), or that all possible such tricks could be so easily caught.
Surely there is some way to verify if a build tempered with, cough file integrity hashes.
Which is a point made in the article - the technique is not meant to be hard to detect a la cryptography, it's meant to be non-obvious to spot. By exploiting the fact that nobody is going to look through (or edit) machine instructions for patterns in register bytes, you can include a message that is easy to overlook.