4 ms·

Steganography with Brainfuck

75 points by Two9A 15y ago

CGamesPlay 15y ago
> Steganography is a name given for a set of encryption techniques, where the targeted message is hidden inside an image in some form. 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.
- Two9A 15y ago
  You make a fine point. Amended the intro. 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.
tripzilch 15y ago
So the basic idea is that a BF interpreter will ignore any non-BF characters? 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.
- Two9A 15y ago
  Mm, sounds like a plan. In taking the 8-bit greyscale image down to 4-bit, I've essentially introduced a margin of error of +/- 8, which explains why the message was able to fit into just the first ten or so rows of a 128-row image. 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.
  - tripzilch 15y ago
    Another idea is to substitute the eight BF instructions to different bytes. Right now the byte-values for most instructions are within 1 or 2 values from eachother. 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).
philh 15y ago
It seems like this would be pretty easy to do with XPM2. Duplicate certain colours as [.,<>+-] (at the beginning of a program, that's a no-op) and insert the program into the pixel data. It's probably less well-hidden though, since someone's more likely to look at it in a text editor. http://en.wikipedia.org/wiki/X_PixMap#XPM2 http://en.wikipedia.org/wiki/X_PixMap#XPM2
SagelyGuru 15y ago
This looks like 'snake oil'. What exactly is the purpose of using the brainfuck code instead of the message itself? Surely, if steganography fulfilled its purpose and the message was not discovered, then the simplest/most compact form of the message would have been the best. On the other hand, if the message was discovered, then brainfuck does not represent much of an obstacle to reading it.
- Two9A 15y ago
  I wouldn't go so far as "snake oil", just "pointless fun". As mentioned elsewhere in these comments, the idea behind this was "what if I could run an image file as a Brainfuck program?" It's not a rigorous academic study of the merits of Brainfuck as a steganographic technique.
- tripzilch 15y ago
  > This looks like 'snake oil'. What exactly is the purpose of using the brainfuck code instead of the message itself? 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).
  - waitwhat 15y ago
    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 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 http://en.wikipedia.org/wiki/Rubber-hose_cryptanalysis

75 points by Two9A 15y ago

> Steganography is a name given for a set of encryption techniques, where the targeted message is hidden inside an image in some form. 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.

Two9A 15y ago
You make a fine point. Amended the intro. 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.

tripzilch 15y ago

So the basic idea is that a BF interpreter will ignore any non-BF characters? 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.

Two9A 15y ago
Mm, sounds like a plan. In taking the 8-bit greyscale image down to 4-bit, I've essentially introduced a margin of error of +/- 8, which explains why the message was able to fit into just the first ten or so rows of a 128-row image. 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.
- tripzilch 15y ago
  Another idea is to substitute the eight BF instructions to different bytes. Right now the byte-values for most instructions are within 1 or 2 values from eachother. 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).

philh 15y ago

It seems like this would be pretty easy to do with XPM2. Duplicate certain colours as [.,<>+-] (at the beginning of a program, that's a no-op) and insert the program into the pixel data. It's probably less well-hidden though, since someone's more likely to look at it in a text editor. http://en.wikipedia.org/wiki/X_PixMap#XPM2 http://en.wikipedia.org/wiki/X_PixMap#XPM2

SagelyGuru 15y ago

This looks like 'snake oil'. What exactly is the purpose of using the brainfuck code instead of the message itself? Surely, if steganography fulfilled its purpose and the message was not discovered, then the simplest/most compact form of the message would have been the best. On the other hand, if the message was discovered, then brainfuck does not represent much of an obstacle to reading it.

Two9A 15y ago
I wouldn't go so far as "snake oil", just "pointless fun". As mentioned elsewhere in these comments, the idea behind this was "what if I could run an image file as a Brainfuck program?" It's not a rigorous academic study of the merits of Brainfuck as a steganographic technique.
tripzilch 15y ago
> This looks like 'snake oil'. What exactly is the purpose of using the brainfuck code instead of the message itself? 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).
- waitwhat 15y ago
  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 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 http://en.wikipedia.org/wiki/Rubber-hose_cryptanalysis