20 May 2015 05:00

Let's say that you are walking down the halls of a high school, and on a locker you find a rather conspicuous note that reads, "YBIRL BHZHP UYLFD HVFUL ORNEK BKBQN A". Overly curious, you write down the letters and try to find out what they mean while in class. Very quickly, you realize that by shifting each letter by 13 spaces (ie. A becomes N, B becomes O, etc), the message reads, "Love you muchly squishy bear! XOXO ~Dan". Embarrassing!

Yesterday, Dan and Rei (his girlfriend) had a small argument, and he wanted to make it up to her by giving her a secret message only a computer geek like Rei would understand. Once his romantic message was prepared, Dan tried to use what is called cryptography in order to hide the true nature of his message from everybody except the intended recipient, in this case, Rei. Unfortunately for Dan, the code he used to encrypt his love message was really really bad and can be figured out easily despite only Rei knowing his algorithm ahead of time. Maybe Dan could find a different means of having his "secret" conversations with Rei?

Usually, people simply come up with a better code that is much harder for the average person to crack. Certainly, Dan could try the same thing. However, no matter what method he uses to encrypt his message, it will always be obvious that a message does exist, and hence sufficiently curious people will want to try and crack it. Letters arranged in random assortment taped onto someone's high school locker tends to attract attention! You'd want to know what it says, right (well, it's high school, so probably not, but…)?

Simply encrypting the message is not sufficient for Dan. Query must be avoided altogether. Understanding this, Dan wants to actually hide the fact that he is sending a message in the first place. Interestingly, this practice is called steganography. Steganography looks at how messages can be embedded into inconspicuous forms (like pictures or text); cryptography, on the other hand, just changes the form of the message. Hiding messages in plain sight is the name of the game.

You want to know a secret? Back up to the top of the page and you will see a picture of a chameleon. Embedded into this image is some secret text! An encrypted message, while secure, tends to attract the attention of adversaries trying to breach security. Rather, a stegoed message, circumvents curiosity altogether so that no one even suspects a message exists. Disguised as a picture, you may not have suspected a message at all, demonstrating the power of steganography.

Any media (images, music, blog posts, you name it) can have messages embedded into them. Nevertheless, the right rules must be used in order for the message to be as undetectable as possible. For digital images like the chameleon image above, we utilize the fact that the human eye cannot distinguish between two colors that are sufficiently close to one another despite being different in reality. For example, this blue and that blue are actually different shades, but the difference is so miniscule that you likely cannot tell.

Therefore, we can actually alter what is called the Lowest Significant Bit (LSB) of each pixel in an image so that, when stringed together, they form a message. For example, one pixel might have the binary value 01011100. However, we can change the last 0 into a 1 without changing the visual appearance of the image. You can read more about this technique in detail here.

Below is Haxe code that will embed/extract secret messages to/from images (stored as a Bytes object). If you are sufficiently curious, try to see if you can extract the message from the chameleon image!

function embed(img:Bytes, msg:String, stride = 1):Bytes {
    var mask:Int = ~((1 << stride) - 1);
    var msgData = Bytes.ofString(msg + String.fromCharCode(0));
    var imgIt = 54;
 
    for (i in 0...msgData.length) {
        var char = msgData.get(i);
        var u = 8 - stride;
        while (u >= 0) {
            var imgByte = img.get(imgIt);
            var charBits = (char >> u) & ~mask;
            imgByte = (imgByte & mask) | charBits;
            img.set(imgIt, imgByte);
            u -= stride;
            if (++imgIt > img.length) {
                trace("Warning: Image length exceeded");
                return img;
            }
        }
    }
    return img;
}

function extract(img:Bytes, stride = 1):String {
    var mask:Int = (1 << stride) - 1;
    var imgIt = 54;
    var msg = new StringBuf();
 
    var char = 1;
    while (imgIt < img.length && char > 0) {
        char = 0;
        var u = 8 - stride;
 
        while (imgIt < img.length && u >= 0) {
            var imgByte = img.get(imgIt);
            char |= (imgByte & mask) << u;
            u -= stride;
            ++imgIt;
        }
 
        msg.addChar(char);
    }
 
    return msg.toString();
}

Over the years, many steganographic techniques have been developed, both physical and digital. Some of these include:

  • Using invisible ink to write between lines of real ink
  • Packaging zip files into gif files
  • Invoking processes that measurably raise and lower computer temperature
  • The order of moves used in Tic-Tac-Toe
  • Using invisible Unicode characters to write data within text (this technique was actually used in The Coconut-Monkey Problem post to demonstrate a class project)

If you have never heard of steganography before, then hopefully this post has opened up an entirely new world of hidden information to you. Who knows how many of the images on Google's searches contain concealed messages?

If you liked this kind of informational article, be sure to say so in the comments! I may do an algorithmic analysis on a steganographic technique, so if you are interested, be sure to tell me which method intrigues you most.

Resources:

Image Courtesy: http://wallpapershome.com/animals/reptiles/chameleon-color-change-lizard-veiled-chameleon-panther-3710.html

Comments

cover.png

Shannon's Maxim and Steganography