1.3 Steganography

by Marko Riedel

1.3.1 Idea

We provide a sample implementation of a basic steganography algorithm, by which hidden data are placed in a TIFF image, which is assumed to contain RGB values in either a planar or a meshed configuration. Think of the input data as a stream of bits. We place these bits in the image by altering the least significant bit of the red color component. The actual location of the data in the image is determined by a passphrase. This assures that even if someone can determine which pixels have been altered, she will not know in what order the altered pixels should be read.

1.3.2 Implementation

The first task is to construct a permutation of the pixel locations from the passphrase. We may think of the passphrase as an infinite sequence of bits (repeat the passphrase to get additional bits). We start by implementing a class that delivers chunks of bits from this source.

 
@interface BitSource : NSObject 
{ 
    unsigned char *source; 
    int pos, total, len; 
} 
 
+ (NSString *)bitString:(unsigned long)val count:(int)bc; 
 
- initWithString:(NSString *)str; 
- (unsigned long)getBits:(int)count; 
 
- (void)dealloc; 
 
@end

The class BitSource stores the passphrase, which we restrict to ASCII characters in the range from 32 to 127, so that every character provides seven bits. The total number of bits is seven times the length of the passphrase and repeats thereafter. Bitsource stores the position in the bit stream, the length of the phrase and the total number of bits. The method bitString:count: is used for debugging purposes. It converts some number of bits at the least significant end of an unsigned long integer into a string.

 
@implementation BitSource 
 
+ (NSString *)bitString:(unsigned long)val count:(int)bc 
{ 
    NSString *result = @””; 
    int cur; 
 
    for(cur=0; cur<bc; cur++){ 
        result = 
            [(val & 1 ? @”1” : @”0”) 
                stringByAppendingString:result]; 
 
        val >>=1; 
    } 
 
    return result; 
}

We extract the bits one after the other and prepend them to the result string (we prepend because the less significant bits come first).

The method initWithString: initializes a bit source from a passphrase. It checks that the phrase is not empty, allocates a buffer for the phrase, checks that no characters are out of range and copies the characters into the buffer. It initializes the postion to be at the beginning of the string and computes the total number of bits that the phrase can provide before it repeats.

 
- initWithString:(NSString *)str 
{ 
    const char *cstr = [str cString], *cur; 
    unsigned char *scur; 
 
    [super init]; 
 
    len = [str length]; 
    if(len<1){ 
        [NSException raise:NSInvalidArgumentException 
                      format:@”bit_source_from_empty_string”]; 
    } 
 
 
    source = scur = NSZoneMalloc(NSDefaultMallocZone(), 
                                  len*sizeof(unsigned char)); 
    for(cur=cstr; *cur; cur++, scur++){ 
        unsigned char item = *cur; 
        if(item<32 ∣∣ item>127){ 
            [NSException raise:NSRangeException 
                          format:@”char_out_of_range_(32-127):_%d”, 
                          item]; 
        } 
        *scur = item; 
    } 
 
    pos = 0; total = len*7; 
 
    return self; 
}

The method getBits: does the actual work. It returns the requested number of bits in an unsigned long integer, scanning the phrase from left to right and wrapping at the end of the phrase.

 
- (unsigned long)getBits:(int)count 
{ 
    unsigned long result = 0; 
    int index; 
 
    for(index=0; index<count; index++){ 
        int whatChar = pos/7, whatBit = 6-(pos%7); 
        int bit = 
            (source[whatChar] & 
             (1 << whatBit)) >> whatBit; 
 
        result = (result << 1) + bit; 
 
        pos = (pos+1)%total; 
    } 
 
    return result; 
}

The method computes what character corresponds to the current position and what bit to extract. It starts with the highest bit because the phrase is scanned from left to right. It writes the bit into the result integer and moves to the next position. It starts over if it reaches the end of the phrase. The method dealloc frees the buffer where the phrase was stored.

 
- (void)dealloc 
{ 
    NSZoneFree(NSDefaultMallocZone(), source); 
    [super dealloc]; 
} 
 
@end

We can now move on to the actual algorithm. There are several steps.

 
#define BUFSIZE 4096 
 
int main(int argc, char** argv, char **env) 
{ 
    NSAutoreleasePool *pool = [NSAutoreleasePool new]; 
    NSProcessInfo *procInfo = [NSProcessInfo processInfo]; 
    NSArray *args = [procInfo arguments]; 
 
    NSFileManager *fm = [NSFileManager defaultManager]; 
 
    BOOL encode; 
    NSString *eswitch, *passphrase, *infile, *outfile; 
 
    BitSource *bits; 
 
    NSImage *img; 
    NSEnumerator *repEn; 
    NSBitmapImageRep *rep; 
    NSSize imgSize; 
    unsigned char *dplanes[5]; 
    int spp; 
    BOOL isPlanar; 
 
    unsigned long *permutation; 
    int pbits; 
    unsigned long width, height, pixels, pindex; 
 
    unsigned char dlbytes[sizeof(unsigned long)]; 
    long dindex, dlen; 
    int bpos, bit; 
    unsigned long where;

We start with several blocks of declarations: the first block lets us access the command line arguments; the second, the file manager, which we need to check whether the image is readable; the third, various strings, one for each command line argument; the fourth, the bit source; the fifth, the image that we’ll manipulate, the bitmap representation that wraps the image data, the data themselves, a flag to tell whether the image is planar or meshed, and how many samples there are per pixel; the sixth, the permutation of the pixel locations, how many bits we’ll need for each item in the permutation, and the dimensions of the image; the seventh and last block, a buffer for accessing individual bytes of the long integer that holds the message length and various integers that store state while we process the image.

Processing command line arguments is the easy part. First check that there is the right number of arguments; then check the value of the encode-decode switch.

 
    if([args count]!=4){ 
        [NSException raise:NSInvalidArgumentException 
                      format:@”args_are_-d/-e_passphrase_image”]; 
    } 
 
    eswitch = [args objectAtIndex:1]; 
    if([eswitch isEqualToString:@-e”]){ 
        encode = YES; 
    } 
    else if([eswitch isEqualToString:@-d”]){ 
        encode = NO; 
    } 
    else{ 
        [NSException raise:NSInvalidArgumentException 
                      format:@-d/-e_(de/encode)_expected”]; 
    }

Initialize the bit source from the passphrase:

 
    passphrase = [args objectAtIndex:2]; 
    bits = 
        [[BitSource alloc] initWithString:passphrase];

Get the file name and check that the file is readable, and construct the name of the output file, which we obtain by placing the string -stg between the extension TIFF and the rest of the filename.

 
    infile = [args objectAtIndex:3]; 
    if([fm isReadableFileAtPath:infile]==NO){ 
        [NSException raise:NSInvalidArgumentException 
                      format:@”%@_isn’t_readable”, infile]; 
    } 
 
    outfile = 
        [[[infile stringByDeletingPathExtension] 
             stringByAppendingString:@-stg”] 
            stringByAppendingPathExtension:@”tiff”];

Now open the image, extract the image dimensions and compute the total number of pixels. Compute the integer logarithm of this number. It tells us how many bits we need to request from the bit source when we construct the permutation of pixel locations.

 
    img = [[NSImage alloc] initWithContentsOfFile:infile]; 
    if(img==nil){ 
        [NSException raise:NSInvalidArgumentException 
                      format:@”no_image_in_%@”, infile]; 
    } 
 
    imgSize = [img size]; 
    width = imgSize.width; 
    height = imgSize.height; 
    pixels = width*height; 
 
    pbits = 1; 
    while(pixels > (1<<pbits)){ 
        pbits++; 
    }

The next step is to actually construct the permutation. We use the idea from The Art of Computer Programming, also discussed elsewhere in this document. Start with a fully ordered permutation and move an item it to the end; decrease the end marker, repeat. The choice of the item is not random in our case. It is determined by reading the required number of bits from the bit source. The item that we move to the end is given by the remainder of the bits modulo the length from the start to the current end marker.

 
    permutation = NSZoneMalloc(NSDefaultMallocZone(), 
                                pixels*sizeof(unsigned long)); 
    if(permutation==NULL){ 
        [NSException raise:NSMallocException 
                      format:@”malloc_failed_(%ld)”, pixels]; 
    } 
 
    for(pindex=0; pindex<pixels; pindex++){ 
        permutation[pindex] = pindex; 
    } 
    NSLog(@”width_%ld_height_%ld_pixels_%ld_bits_%d”, 
          width, height, pixels, pbits); 
 
    for(pindex=pixels-1; pindex>0; pindex--){ 
        int swaploc = [bits getBits:pbits] % (pindex+1); 
        unsigned long item; 
 
        item                = permutation[pindex]; 
        permutation[pindex] = permutation[swaploc]; 
        permutation[swaploc] = item; 
    }

The last step before the actual computation is to gain access to the data planes where the image is stored. The red data plane comes first in a planar configuration. We obtain the data by looking for a bitmap representation among the representations of the image and exit if no such representation is found. Otherwise we ask the representation for the data, and set the planarity flag and the number of samples per pixel.

 
    repEn = [[img representations] objectEnumerator]; 
    while((rep = [repEn nextObject])!=nil){ 
        if([rep isKindOfClass:[NSBitmapImageRep class]]==YES){ 
            break; 
        } 
    } 
    if(rep==nil){ 
        [NSException raise:NSInvalidArgumentException 
                      format:@”no_bitmap_image_rep_for_%@”, infile]; 
    } 
 
    [rep getBitmapDataPlanes:dplanes]; 
    spp = [rep samplesPerPixel]; 
    isPlanar = [rep isPlanar];

We now discuss the encode/decode process. The first step in the encode process is to compute the number of bytes the image can hold, read the data from the standard input and check that they fit into the image. We need an extra sizeof(unsigned long) bytes to store the length of the message.

 
    if(encode==YES){ 
        NSData *data; 
        unsigned long dmax = pixels/8-sizeof(unsigned long); 
        const unsigned char *dbytes; 
 
        data = [[NSFileHandle fileHandleWithStandardInput] 
                    readDataToEndOfFile]; 
        if((dlen = [data length])>dmax){ 
            [NSException raise:NSInvalidArgumentException 
                          format:@”image_can_only_hold_%ld_bytes”, 
                          dmax]; 
        } 
        else if(!dlen){ 
            [NSException raise:NSInvalidArgumentException 
                          format:@”no_data”]; 
        }

The actual write process consists of two steps: first write the message length, then write the message. The variable dlbytes provides access to the individual bytes of the message length value; dbytes, to the bytes of the bitmap data plane. We iterate over a range from negative the number of bytes that hold the message length, to the length of the message. First extract the byte that is about to be written. Then write all eight bits, one after the other. The permutation tells us where in the image the bit goes. We write the bit by first zeroing the target bit and then setting the target bit to the bit that we want to record. Note that there is a fifty percent chance in a diverse image that the target bit already agrees with the source bit and no change will be detected. We must multiply the index given by the permutation by the number of samples per pixel if the image is not planar (meshed). We write the most significant bit first to facilitate later reads.

 
        *(unsigned long *)dlbytes = dlen; 
        dbytes = [data bytes]; 
 
        for(pindex = 0, dindex=-sizeof(unsigned long); 
            dindex<dlen; dindex++){ 
            unsigned char tbyte, 
                byte = (dindex<0 ? 
                         dlbytes[-dindex-1] : dbytes[dindex]); 
 
            for(bpos=0; bpos<8; bpos++){ 
                where = permutation[pindex++]; 
 
                if(isPlanar==NO){ 
                     where *= spp; 
                } 
 
                bit = (byte & 1<<(7-bpos) ? 1 : 0); 
 
                tbyte = dplanes[0][where]; 
                tbyte >>= 1; tbyte <<= 1; tbyte += bit; 
                dplanes[0][where] = tbyte; 
            } 
        }

The last step of the encoding phase is to write the data to the output file.

 
        data = [rep TIFFRepresentation]; 
        if([data writeToFile:outfile atomically:NO]==NO){ 
            [NSException raise:@”data_write_failed” 
                          format:@”couldn’t_write_%@”, outfile]; 
        }

The decode process is even simpler. Start by allocating a mutable data object for the contents of the secret message. In fact we’ll write the message contents into a buffer and append the buffer contents to the data object when the buffer is full, so as not to invoke appendBytes:length: for every byte that we have extracted. Recall that the first sizeof(unsigned long) bytes contain the message length. We set the upper end of the loop range once this value has been extracted. We extract one byte at a time. The permutation tells us where the individual bits are located. We retrieve the least significant bit and write it to the byte being extracted. Recall that the most significant bit comes first, so we can just shift the byte when we record a new bit. We append the contents of the buffer to the data object whenever the buffer is full.

 
        NSMutableData *data = 
            [NSMutableData dataWithCapacity:8]; 
        unsigned char buf[BUFSIZE], *bptr = buf; 
 
        dlen = 0; 
        for(pindex = 0, dindex=-sizeof(unsigned long); 
            dindex<dlen; dindex++){ 
            unsigned char sbyte = 0; 
 
            for(bpos=0; bpos<8; bpos++){ 
                where = permutation[pindex++]; 
 
                if(isPlanar==NO){ 
                     where *= spp; 
                } 
 
                bit = dplanes[0][where] & 1; 
                sbyte = (sbyte << 1) + bit; 
            } 
 
            if(dindex<0){ 
                dlbytes[-dindex-1] = sbyte; 
            } 
            else{ 
                *bptr++ = sbyte; 
                if(bptr-buf==BUFSIZE){ 
                     [data appendBytes:buf length:BUFSIZE]; 
                     bptr = buf; 
                } 
            } 
 
            if(dindex==-1){ 
                dlen = *(unsigned long *)dlbytes; 
                NSLog(@”message_length_is_%ld”, dlen); 
            } 
        }

If there are data in the buffer at the end of the loop we record them in the data object. The last step of the decode process is to write the contents of the secret message to the standard output.

 
        if(bptr>buf){ 
           [data appendBytes:buf length:bptr-buf]; 
        } 
 
        [(NSFileHandle *) 
            [NSFileHandle fileHandleWithStandardOutput] 
            writeData:data];

The program frees memory that has been allocated before it exits.

 
    NSZoneFree(NSDefaultMallocZone(), permutation); 
 
    [bits release]; 
    [pool release]; 
    exit(0); 
}