Steganography with Brainfuck
imrannazar.com
imrannazar.com
Actually, steganography is not a type of encryption, and is simply the process of hiding a message, be it inside of an image, another message, the closing values of the DJIA, or not inside of anything at all.
I'm curious why you didn't simply duplicate the palette 16 times, then use the gray values in 0x0X, and the brainfuck character component in 0xX0. You'd be able to fit vastly more brainfuck data into an image, depending on the characteristics of the image and the code.
The original idea that popped into my head was, "what if an image was a BF program?" With compression and/or palette reorganisation, of course more BF can be fit into an image, but it wouldn't be a pure BF program.
How about, if you'd take an 8 bit grayscale image, and allow each pixel a margin of error, say 2 values up or down. Then you could process the pixels sequentially while looking for the next value that is within the range of +/- 2 of your next BF token and adjust it to the correct value. If instead you happen upon an incorrect BF token, you can also adjust it so that it either turns into the correct one or a non-BF instruction byte.
Of course there's no guarantee that you'll be able to fit the whole program since you'll be skipping a lot of pixels. But an image is big and the message is short, so there's a good chance. Especially if you retry with different BF encodings of the same message, and failing that upping the error margin to +/- 3, then +/- 4, etc.
A higher palette resolution would, as you say, increase the amount of space taken by the message, but would result in a higher fidelity of the image.
You'd need a modified interpreter, though, but by picking different values for the BF instructions, spaced further apart in the 0-255 range, you'd get less collisions (incorrect BF tokens appearing at the wrong spot in your stream).
Another possibility would be to pick different code points for each image/message encoded. Though you'd need another channel to specify which 8 bytes encode for which BF tokens. You could even not specify it, but limit the choices for the 8 byte values and try all combinations, then see which ones decode to a string that comes closest to character distribution in English language (this is the same method used by online translators to determine source language, character distribution is highly distinctive).
It's not a rigorous academic study of the merits of Brainfuck as a steganographic technique.
Hackery, pretty much.
> if the message was discovered, then brainfuck does not represent much of an obstacle to reading it.
The point of stego is that the message is not suspected. Usually this is done via statistical analysis(1). However, this just tells the adversary that "a message could be there". Given that information, they still need to find out which bytes are information-carrying, and that those bytes encode to a BF program. Stego is all about the extra hurdles, it is literal security-through-obscurity. But once they got that, yeah, the message will be exposed.
(1) Which is why encrypting the message before stego is not a straightforward good idea, as encrypted data looks like white noise, and contrary to popular belief, the lowest bits in most photos are not distributed like white noise (as a naive stego algorithm would just hide an encrypted message in the image's least significant bits).
This is true as far as it goes. It should be noted, however, that in many threat models for steganography, this problem is solved through rubber-hose cryptanalysis. http://en.wikipedia.org/wiki/Rubber-hose_cryptanalysis
Slightly less awful than torture, you also lose plausible deniability in a legal setting, or even other situations.
I agree the most important thing about stego is that the existence of the message is not discovered at all.
Sounds like that means encryption before stego is pretty much useless, then? Still something in my head says "better safe than sorry", even though you're not mitigating all that much risk.
A better idea might be to compress the message before stego. That way you need to hide less bits, even though the bits will be distributed like white noise, which can be harder to hide, but could perhaps also be something that can be relied on in some sense.