🥇Steganography in GIF

Introduction

Greetings.
Not long ago, while studying at university, I had a project for the course 'Software Methods of Information Protection'. The task was to create a program that embeds a message into GIF format files. I decided to do it in Java.

In this article, I will describe some theoretical aspects and how this small program was created.

Theoretical Part

GIF Format

GIF (Graphics Interchange Format) is a format for exchanging images, capable of storing compressed data without loss of quality in a format of up to 256 colors. This format was developed in 1987 (GIF87a) by CompuServe for transmitting raster images over networks. In 1989, the format was modified (GIF89a), adding support for transparency and animation.

GIF format files have a block structure. These data blocks always have a fixed length (or it depends on certain flags), so it is almost impossible to make a mistake about where each block is located. The structure of the simplest non-animated GIF image in GIF89a format:

Of all the blocks in the structure, we will be interested in the global palette block and the parameters that correspond to the palette:

CT — presence of a global palette. If this flag is set, the global palette should start immediately after the logical screen descriptor.
Size — size of the palette and number of colors in the image. The values for this parameter are:

Size
Number of Colors
Palette Size, bytes

7
256
768

6
128
384

5
64
192

4
32
96

3
16
48

2
8
24

1
4
12

0
2
6

Encryption Methods

The following methods will be used for encrypting messages in image files:

LSB Method (Least Significant Bit)
Palette Extension Method

LSB Method — a popular method of steganography. It involves replacing the least significant bits in the container (in our case, the bytes of the global palette) with the bits of the hidden message.

The program will use the last two bits in the bytes of the global palette. This means that for a 24-bit image, where the color palette consists of three bytes for red, blue, and green colors, each color component will change by a maximum of 3/255 gradations after embedding a message. Such a change, firstly, will be imperceptible or hard to notice for the human eye, and secondly, will not be distinguishable on low-quality output devices.

The amount of information will directly depend on the size of the image palette. Since the maximum palette size is 256 colors, and if two bits of the message are recorded in each color component, the maximum message length (with the maximum palette in the image) is 192 bytes. After embedding the message into the image, the file size does not change.

Palette extension method, which works only for GIF structure. It will be most effective in images with small palette sizes. Its essence is that it increases the palette size, thereby giving additional space to record the necessary bytes in the color byte locations. Considering that the minimum palette size is 2 colors (6 bytes), the maximum size of the embedded message can be 256×3–6=762 bytes. The drawback is low cryptographic protection; the embedded message can be read using any text editor if the message has not been subject to additional encryption.

Practical part

Designing the program

All necessary tools for implementing encryption and decryption algorithms will be found in the package com.tsarik.steganography. This package includes the interface Encryptor with methods encrypt and decrypt, class Binary, which provides the ability to work with bit arrays, as well as exception classes UnableToEncryptException and UnableToDecryptException, which should be used in the interface methods Encryptor in case of encoding and decoding errors, respectively.

The main package of the program com.tsarik.programs.gifed will include the executable class of the program with a static method main, allowing the program to be launched; a class that stores the program parameters; and packages with other classes.

The implementation of the algorithms themselves will be presented in the package com.tsarik.programs.gifed.gif classes GIFEncryptorByLSBMethod and GIFEncryptorByPaletteExtensionMethod. Both of these classes will implement the interface Encryptor.

Based on the structure of the GIF format, a general algorithm for embedding a message into the image palette can be composed:

To determine the presence of a message in the image, a specific sequence of bits must be added at the beginning of the message, which the decoder reads first and checks for correctness. If it does not match, it is considered that there is no hidden message in the image. Next, the length of the message must be specified. Then, the actual text of the message.

Class diagram of the entire application:

Program implementation

The implementation of the entire program can be divided into two components: the implementation of the encryption and decryption methods of the interface Encryptor, in the classes GIFEncryptorByLSBMethod and GIFEncryptorByPaletteExtensionMethod, and the implementation of the user interface.

Let's consider the class GIFEncryptorByLSBMethod.

Fields firstLSBit and secondLSBit store the bit positions of each byte of the image, where the message should be written to and read from. The field checkSequence holds the control sequence of bits for recognizing the embedded message. The static method getEncryptingFileParameters returns the parameters of the specified file and characteristics of the potential message.

The algorithm of the method encrypt class GIFEncryptorByLSBMethod:

And its code:

@Override
public void encrypt(File in, File out, String text) throws UnableToEncodeException, NullPointerException, IOException {
	if (in == null) {
		throw new NullPointerException("Input file is null");
	}
	if (out == null) {
		throw new NullPointerException("Output file is null");
	}
	if (text == null) {
		throw new NullPointerException("Text is null");
	}
	
	// read bytes from input file
	byte[] bytes = new byte[(int)in.length()];
	InputStream is = new FileInputStream(in);
	is.read(bytes);
	is.close();
	
	// check format
	if (!(new String(bytes, 0, 6)).equals("GIF89a")) {
		throw new UnableToEncodeException("Input file has wrong GIF format");
	}
	
	// read palette size property from first three bits in the 10-th byte from the file
	byte[] b10 = Binary.toBitArray(bytes[10]);
	byte bsize = Binary.toByte(new byte[] {b10[0], b10[1], b10[2]});
	
	// calculate color count and possible message length
	int bOrigColorCount = (int)Math.pow(2, bsize+1);
	int possibleMessageLength = bOrigColorCount*3/4;
	int possibleTextLength = possibleMessageLength-2; // one byte for check and one byte for message length
	
	if (possibleTextLength < text.length()) {
		throw new UnableToEncodeException("Text is too big");
	}
	
	int n = 13;
	
	// write check sequence
	for (int i = 0; i < checkSequence.length/2; i++) {
		byte[] ba = Binary.toBitArray(bytes[n]);
		ba[firstLSBit] = checkSequence[2*i];
		ba[secondLSBit] = checkSequence[2*i+1];
		bytes[n] = Binary.toByte(ba);
		n++;
	}
	
	// write text length
	byte[] cl = Binary.toBitArray((byte)text.length());
	for (int i = 0; i < cl.length/2; i++) {
		byte[] ba = Binary.toBitArray(bytes[n]);
		ba[firstLSBit] = cl[2*i];
		ba[secondLSBit] = cl[2*i+1];
		bytes[n] = Binary.toByte(ba);
		n++;
	}
	
	// write message
	byte[] textBytes = text.getBytes();
	for (int i = 0; i < textBytes.length; i++) {
		byte[] c = Binary.toBitArray(textBytes[i]);
		for (int ci = 0; ci < c.length/2; ci++) {
			byte[] ba = Binary.toBitArray(bytes[n]);
			ba[firstLSBit] = c[2*ci];
			ba[secondLSBit] = c[2*ci+1];
			bytes[n] = Binary.toByte(ba);
			n++;
		}
	}
	
	// write output file
	OutputStream os = new FileOutputStream(out);
	os.write(bytes);
	os.close();
}

Algorithm and source code of the method decrypt class GIFEncryptorByLSBMethod:

@Override
public String decrypt(File in) throws UnableToDecodeException, NullPointerException, IOException {
	if (in == null) {
		throw new NullPointerException("Input file is null");
	}
	
	// read bytes from input file
	byte[] bytes = new byte[(int)in.length()];
	InputStream is = new FileInputStream(in);
	is.read(bytes);
	is.close();
	
	// check format
	if (!(new String(bytes, 0, 6)).equals("GIF89a")) {
		throw new UnableToDecodeException("Input file has wrong GIF format");
	}
	
	// read palette size property from first three bits in the 10-th byte from the file
	byte[] b10 = Binary.toBitArray(bytes[10]);
	byte bsize = Binary.toByte(new byte[] {b10[0], b10[1], b10[2]});
	
	// calculate color count and possible message length
	int bOrigColorCount = (int)Math.pow(2, bsize+1);
	int possibleMessageLength = bOrigColorCount*3/4;
	int possibleTextLength = possibleMessageLength-2;	// one byte for check and one byte for message length
	
	int n = 13;
	
	// read check sequence
	byte[] csBits = new byte[checkSequence.length];
	for (int i = 0; i < 4; i++) {
		byte[] ba = Binary.toBitArray(bytes[n]);
		csBits[2*i] = ba[firstLSBit];
		csBits[2*i+1] = ba[secondLSBit];
		n++;
	}
	byte cs = Binary.toByte(csBits);
	
	if (cs != Binary.toByte(checkSequence)) {
		throw new UnableToDecodeException("There is no encrypted message in the image (Check sequence is incorrect)");
	}
	
	// read text length
	byte[] cl = new byte[8];
	for (int i = 0; i < 4; i++) {
		byte[] ba = Binary.toBitArray(bytes[n]);
		cl[2*i] = ba[firstLSBit];
		cl[2*i+1] = ba[secondLSBit];
		n++;
	}
	byte textLength = Binary.toByte(cl);
	
	if (textLength < 0) {
		throw new UnableToDecodeException("Decoded text length is less than 0");
	}
	if (possibleTextLength < textLength) {
		throw new UnableToDecodeException("There is no messages (Decoded message length (" + textLength + ") is less than Possible message length (" + possibleTextLength + "))");
	}
	
	// read text bits and make text bytes
	byte[] bt = new byte[textLength];
	for (int i = 0; i < bt.length; i++) {
		byte[] bc = new byte[8];
		for (int bci = 0; bci < bc.length/2; bci++) {
			byte[] ba = Binary.toBitArray(bytes[n]);
			bc[2*bci] = ba[firstLSBit];
			bc[2*bci+1] = ba[secondLSBit];
			n++;
		}
		bt[i] = Binary.toByte(bc);
	}
	
	return new String(bt);
}

Class Implementation GIFEncryptorByPaletteExtensionMethod will be similar, only the method of saving/reading information differs.

In the class MainFrame methods are described as wrappers: encryptImage(Encryptor encryptor) and decryptImage(Encryptor encryptor), which process the results of the interface methods Encryptor and facilitate interaction with the user, i.e., they open file selection dialogs, display error messages, etc.; and other methods as well: openImage(), allowing the user to choose an image, exit(), which performs application exit. These methods are called from Action's corresponding menu items. This class also implements auxiliary methods: createComponents() — creation of form components, loadImageFile(File f) — loading an image into a special component from a file. The class implementation GIFEncryptorByPaletteExtensionMethod is analogous to the class implementation GIFEncryptorByLSBMethod, the main difference is in how the message bytes are written and read from the palette.

Program Operation

LBS Method

Suppose we have such an image:

In this image, the palette consists of 256 colors (as Paint saves). The first four colors are: white, black, red, green. The remaining colors are black. The bit sequence of the global palette will be as follows:

11111111 11111111 11111111 00000000 00000000 00000000 11111111 00000000 00000000 00000000 11111111 00000000…

After the embedding of the message, the highlighted bits will be replaced with bits from the message. The resulting image is almost indistinguishable from the original.