I've always been fascinated with encryption. And, by always, I mean since the age of 7. That's when I "invented" my first encryption method. Of course, it was neither a new, nor a hard-to-break method (I shifted all vowels by one to the "right" and all consonants by one to the left), but still, it was an encryption method.



Since then, I've regularly tred myself both in inventing encryption methods and in deciphering encrypted messages. I can't say I was very successful. Most of my methods were mere letter shifts - or eventually amounted to such - and also I preserved white space. On the other hand, I usually managed to crack simple emcryption patterns.

Then along came the computer. My first encounter with real encryption was in 2004, when, as part of my job, I ported an ASP site to PHP. That's when I came across the ARCFOUR cipher. I was so excited! It was the first time I ever saw this kind of encryption method. I tried to understand its inner workings, but failed miserably. Eventually, I gave up and simply translated to PHP statement to statement.

However, the dice had been thrown. When I found some spare time, I sat down determined to figure this thing out. After all, it was only a bunch of commands - how hard could this be, really? Well, it was quite hard, if you've never seen tis kind of thing before. But eventually I made it. I even transfered the method to other languages (i.e. my favourite at the time, python). In any case, the ARCFOUR still remains my method of choice when it comes to using quick-and-dirty encryption.

And then, I came across this class. Hiding messages (or even files) in images, in such a way that the resulting image appears relatively untouched, now that was a different ballgame altogether. I tried to work the class, but failed, I never quite got it to function properly.

Time passed, and things got slow in the area. Until one day, when a colleague came with a joke, about a language so difficult that even a simple "Hello world" program would be forbiddingly hard to write. That got us into the fun of esoteric programming languages, most of which were simply made for the fun of it. We really laughed with their names, and of course the one that stood out was Brainfuck. The name alone is enough to cause a chuckle, let alone seeing what the source code for an actual program looks like.

At the time, I dismissed Brainfuck as another funny invention, but nothing more than that. So, the day before yesterday, while searching for something irrelevant, I found this little gem. Interestingly, they have enlisted the Brainfuck interpreter under security. That got me thinking. Although in itself, a brainuck program for printing a hard-coded string is actually quite longer than the string itself, the fact that Brainfuck only uses 8 symbols for any program can make things quite interesting: You only need 3 bits to encode each of the source code's commands. Actually, a program that simply prints a message uses only 7 of the 8 symbols (the eighth is there to allow user input), so one of the eight available slots in the three bits is free to use for other purposes. After quite some thinking, I came up with quite a plan for a steganography program. Here's what you'll need:

• a message to encrypt. Of course, noone forbids you to hide an already encrypted message.
  
• a 24-bit (or less) color image to use for medium. Any type (jpg, png, gif...) will do. The resulting image however, will be in png, so size (width x height) matters in two ways: a very small image can't hold a very large message (i.e. whose corresponding Brainfuck source code contains more commands than the number of pixels in the image), and a very large image will be huge when converted to png, and therefore harder to send to the recipient.
  
• A pseudo-random number generator that can be seeded. Usually, these produce floating point numbers from -1 to 1 or from 0 to 1. We'll be assuming that our generator can produce integers from 0 to the number of pixels in the image (exclusive). That's not too hard to achieve using the floating point numbers produced by the generator, the width and the height of the image in pixels.
  
• A table that maps the seven required Brainfuck commands to numbers 0 to 6, and an "End-Of-Message" mark to 7.
  

And here's how to do it, in human-talk:

• Convert the message to a Brainfuck program.
  
• Seed a pseudo-random number generator (PRNG) with a value derived from the image (e.g. width+height).
  
• get a value from the generator. Each value represents a pixel in such a way that if the top-left pixel is pixel 0, then the pixel N is at the [(N-N%width)/width] line and [N%width] column.
  
• Get the pixel pointed by the generator.
  
• Get the least significant bit (LSB) of the value of every color component for that pixel. You now have a 3-bit word.
  
• Check the integer value that corresponds to that 3-bit word and compare it to the 3-bit value of the Brainfuck command (you get that from the mapping table) you want to hide in the pixel. To make things even more obscure, instead of using the actual mapping table value, you can use a pseudo-randomly generated rotation of that table for each Brainfuck command. That's relatively easy to do: use another seeded PRNG, that produces values from 0 to 7, and use the XOR of a generated number and the integers in the mapping table.
  
• Flip the bits you got from the pixel so that they match the value you need to hide.
  
• Repeat this process with the next command, and the next generated number, making sure that there are no repetitions in the generated numbers for the selection of pixels.
  
• When you're done with all the commands, generate another number, and store an "End-of-Message" signal in the LSB's of the corresponding pixel.
  
• Save the image as png. Png is lossless, so all the bit-flipping we did is preserved.
  

The important thing about this method is that the original image is not needed to decrypt the message. Here's how you decrypt.

• Create two PRNG's and seed them both with the (known) value you extract from the image (in our case, width+height). One PRNG will generate values between 0 (inclusive) and the number of pixels in the image (exclusive) while the other will generate numbers between 0 and 7 (both inclusive).
  
• Start generating numbers
  
• For each new (i.e. not seen before) number you get from the "first" PRNG, go to the corresponding pixel
  
• Get the three LSB's from the color components of this pixel
  
• XOR this value with the value you get from the second PRNG. Since (a XOR b) XOR b = a, this makes sure we get the correct final value. Match this value to a Brainfuck command, using the mapping table. Store this command.
  
• Carry on until you hit an "End-of-Message" signal.
  
• Execute the Brainfuck program you got.
  
• The result is the original message.
  

This scheme could be used e.g. to store a serial number in a background (or logo) image of an application, and thus serve for license validation.

The attachment contains a .NET 3.5 windorms application that does just this.