Reading between the lines

befoRe anna paVlOvNa And the otHers HaD timE tO smile their appreCiAtion of tHe ViCoMte's EpigRaM, Pierre aGaIn BrokE iNtO the CoNvErsation, AnD thoUgh Anna Pavlovna fElT sUre he wouLd Say sOmEthiNg InapPropRiate, she Was uNable tO sTop hIm. "ThE execution of thE DUc d'ENgHien," deClarEd monsIeur PierRe, "WaS a PoliTiCal nEcessity, And iT sEems to me thAt napoleon ShOwEd GreaTnEss of sOul by not FeArInG to take oN himSeLf thE wHoLe respOnsibiLity Of thAt deed." "DiEu! mon DIeu!" mUtTeRed ANnA PavLoVna in a teRrified whiSpEr. "What, MoNsieUr piErRe... Do you consider that assassination shows greatness of soul?

Can you guess what this text represents ? :-) It's extract from the book "War and Peace" but not only that. This peace of text holds secret message also. When this text is decoded it gives such secret message:

the quick brown fox jumps over the lazy dog.

So this time i would like to add new meaning to phrase "reading between the lines" in computing world. Actually it's better to say "reading between the chars" in this case :-) Talk will be about text steganography - how to hide some secret message, aka. payload in original text fragment. Idea is to modulate letter casing so that casing of letters itself in original text would carry additional information which can be used for example to encode some secret message in text. So at first you need to choose some prefixed alphabet of characters to be used in secret message. It's better to have small alphabet, because bigger set will result in a need for a longer original text so that it could contain all secret message. I've used these chars for secret message - 'qwertyuiopasdfghjklzxcvbnm. |'. It's 30 characters. So you need at least 30 different secret states to represent these characters in text. I've chosen letter case to represent this secret state. Upper case of letter means bit 1, lower case - 0. So by using such scheme you can encode 1 bit into letter casing of 1 character (or 2 total states - uppercase,lowercase). Next step is to calculate how much letters of original text you need to encode 1 secret letter by using such scheme. We need to multiply number of states of each letter, so if one letter holds 2 states, 2 letters holds 2*2=4 states and so on. So 5 letters holds 2*2*2*2*2 = 32 states or 5-bit integer of additional information which is enough for our 30 letters alphabet. This integer will represent our secret letter index in our alphabet. So for 1 secret char you need 5 original text chars. General encoding algorithm idea is this (decoding procedure is very similar just some steps are in reverse order):

1. Get next secret char from the secret message
2. Get secret char index in your alphabet
3. Decompose this index into 5-bit binary pattern
4. Encode this 5-bit pattern into 5 letters from original text using uppercase mode as bit 1, lowercase mode - as bit 0
5. Repeat everything from point 1 until all chars of secret message are encoded

I've prepared for this algorithm Java program, you can download it and use as you wish,- as always no restrictions applied - use at your own risk :-) . There are just two classes - Test.java is main program and TextSteganography.java is class which encapsulates encode/decode methods for secret messages. Class TextSteganography.java holds two most important methods - "modulateText" and "extractSecretMessage" which code is this:

    public String modulateText(String text, String hiddenText) {
        hiddenText += '|';
        char[] inp = text.toCharArray();
        char[] hidden = hiddenText.toCharArray();
        int letterIx = -1;

        CheckCondition(containsOnlyValidChars(hiddenText), String.format("Hidden text can only contain chars from the set '%s'", 
                                                                         validChards.substring(0, validChards.length()-1)));
        int letterCount = countLetters(text);
        CheckCondition(letterCount >= 10 * hiddenText.length(), 
                       String.format("Must be at least %d letters in text, but given %d for current payload message", 10 * hiddenText.length(), letterCount));
        
        for (int i = 0; i < hidden.length; i++) {
            int ix = validChards.indexOf(hidden[i]);
            String patternString = "0000" + Integer.toBinaryString(ix);
            char[] pattern = patternString.substring(patternString.length() - 5).toCharArray();
            boolean[] convertToUppercase = upperCaseIsNeeded(pattern);
            
            for (int j = 0; j < convertToUppercase.length; j++) {
                letterIx = getNextLetterIndex(inp, letterIx);
                inp[letterIx] = (convertToUppercase[j])? changeLetterCase(inp[letterIx], LetterCase.UPPER_CASE) : 
                                                         changeLetterCase(inp[letterIx], LetterCase.LOWER_CASE);
                letterIx = getNextLetterIndex(inp, letterIx);
            }
        }
        
        return String.valueOf(inp);
    }
        
    public String extractSecretMessage(String text) {
        LinkedList charList = new LinkedList<>();
        char[] inp = text.toCharArray();
        int letterIx = -1;
        int letterCount = 0;
        int binaryPattern = 0;
        int newBit;
        
        while (true) {
            letterIx = getNextLetterIndex(inp, letterIx);
            if (letterIx != -1) {
                letterCount++;
                newBit = (getLetterCase(inp[letterIx]) == LetterCase.UPPER_CASE)? 1 : 0;
                binaryPattern = (binaryPattern << 1) + newBit;
                
                if (letterCount == 5) {
                    char c = validChards.charAt(binaryPattern);
                    if (c != '|')
                        charList.add(c);
                    letterCount = 0;
                    binaryPattern = 0;
                    if (c == '|')
                        break;
                }
                letterIx = getNextLetterIndex(inp, letterIx);
            }
            CheckCondition(letterIx != -1, "Text was not encoded with this steganography encoder !");
        }
        
        return charListToString(charList);
    }

Some additional interesting comments. At first I wanted to use assertions in Java. But I've found information that assertions are not recommended in general, at least in production code. Besides they are turned-off by default in Java virtual machine. You need to turn them on by -ea switch. But I like assertions very much, because they gives you an opportunity to check some conditions in fast way without writing 'if(s)'. So I wrote function "CheckCondition" which is assert analog but acts in recommended way - throws an exception if condition is not met. Next interesting note - when I profiled an application I found that secret message extraction is relatively slow because each decoded character was appended to output string by StringBuilder. And that's natural, because as I've understood String is just a wrapper around char array. And as we know appending new array element is slow procedure, because you need to re-size array, copy elements to new array and etc, and this takes time. So instead I append new decoded characters into LinkedList of chars and later I converted this list into usual String. This approach works faster when you need to build new String incrementally. That's all.
Have fun in using text steganography !

Steganography Pixel Shader

Steganography is method for hidding secret message in covert message. In this case I mean hidding secret image into covert image. So, sometimes What You See Is NOT What You Get :) How can we hide secret 3-bit image into other 24-bit image ?

Encoding procedure

1.
secret 3-bit image means that we can hide 2^3 = 8 color palette image.
So at first we need to map these 8 colors to 3-bit pattern. Lets use such mappings:

--------------------------
  RGB       | Bit pattern
--------------------------
2,2,2       | 0,0,0
38,38,38    | 0,0,1
74,74,74    | 0,1,0
110,110,110 | 1,0,0
146,146,146 | 0,1,1
182,182,182 | 1,1,0
218,218,218 | 1,0,1
254,254,254 | 1,1,1
--------------------------

2.
Now as we have color table, we just need to get 3-bit image required pixel and encode it's 3-bit pattern into covert RGB image. One way of doing this is to define secret bit meaning as follows: 0 means covert RBG byte is even, 1 means - odd.
So according to this definition we adjust covert image RGB bytes to be even or odd - depending to required 3-bit secret pattern. For example-
if 3-bit pattern is (1,0,1) and covert RGB pixel is (140,39,16) - then it will be converted to (141,40,17).

Decoding procedure
Secret image extraction from covert image procedure is a reversal of encoding:
1. Check covert RGB bytes are even or odd.
2. From that extract 3-bit pattern.
3. Map this 3-bit pattern to 8 color palette.

Properties of this image hidding method
1. Can be used in image formats which doesn't support alpha (transparency) channel.
2. Original image looses only 3/24 = 12.5 percents of quality, which means that it is hard or impossible to spot by eyes that something is wrong with covert image.
3. Regardless of good image quality after conversion, image histogram can show some signs of payload image. Because in some cases histogram is modulated after conversion.

Now code examples. Encoding part is left as exercise to the reader :) But here it is payload image extraction code (as always in GLSL shader language):
a) Vertex Shader (we need it for correct sampling of texels)

---

varying vec2 texCoord;

void main(void)
{
   gl_Position = vec4(gl_Vertex.xy, 0.0, 1.0 );
   texCoord = 0.5 * gl_Position.xy + vec2(0.5);     
}

---

b) Pixel Shader (real program doing payload image extraction)

---

#version 120
uniform sampler2D Texture0;
varying vec2 texCoord;

int binaryToDecimal(in int d1, in int d2, in int d3) {
   return 4*d1+2*d2+d3;
}

void fillColors(inout float[8] colors) {
   colors[0] = 2./255.;
   colors[1] = 38./255.;
   colors[2] = 74./255.;
   colors[3] = 146./255.;
   colors[4] = 110./255.;
   colors[5] = 218./255.;
   colors[6] = 182./255.;
   colors[7] = 254./255.;
}

int Odd(in float num) {
   return int(mod(num,2.)!=0.);
}

void main()
{   
   float colTable[8];
   fillColors(colTable);
   vec4 col = texture2D(Texture0, texCoord);
   int d1 = Odd(col.r*255.);
   int d2 = Odd(col.g*255.);
   int d3 = Odd(col.b*255.);
   float level = colTable[binaryToDecimal(d1,d2,d3)];
   gl_FragColor = vec4(level,level,level,1.0);
}

---

NOTE: When using this GLSL shader for image below - make sure that covert texture is rendered to screen aligned quad of EXACTLY 512x512 pixel dimensions. Otherwise you will not get hidden image, but instead you will get just noise because of incorrect pixel/texel samplings !!!

Finally,- results. This is covert image:

and this is payload image extracted from above image (after extraction GLSL shader applied):


Have fun in making/analyzing covert images !