.oO Phrack 49 Oo. Volume Seven, Issue Forty-Nine 10 of 16 A Steganography Implementation Improvement Proposal by: cjm1@concentric.net [ For those of you who do not know, steganography is cryptographic technique that simply hides messages inside of messages. The sender composes an innocuous message and then, using one of many tactics, injects the secret message into it. Some techniques involve: invisible inks, character distortion, handwriting differences, word/letter frequency doping, bit flipping, etc... The method the author discusses hinges upon a well known steganographic implementation, low-order bit flipping in graphic images. -d9 ] Steganography is a technique for hiding data in other data. The general method is to flip bits so that reading the low-order bit of each of 8-bytes gets one a character. This allows one to use a picture or a sound file and hide data, resulting in a small bit of hopefully unnoticeable noise in the data and a safely hidden cache of data that can later be extracted. This paper details a method for making steganographically hidden data more safe, by using pseudo-random dispersion. Ordinarily, if someone suspects that you have data hidden in, say, a GIF file, they can simply run the appropriate extractor and find the data. If the data is not encrypted, it will be plain for anyone to see. This can be ameliorated by using a simple password protection scheme, hiding the password in the GIF as a header, encrypting it first with itself. If someone does not know the password, they cannot extract the data. This is of course reasonably safe, depending on the encryption scheme used, and I recommend it. But, the hidden data can be made even safer. Pseudo-random dispersion works by hiding a password, and a seed for a random-number-generator in the encrypted header. then, a random number of bytes are passed by, before a low-order bit is flipped. To do this, one must first calculate how many bytes a bit can take up for itself. For instance, to hide an 800 character message in a GIF would mean each character needs 8 bytes (8 bits per character, 1 byte per low-order bit), so you need 6,400 bytes of data to hide the message in, 8 bytes per character. Let's say we have a GIF that is 10 times this size: 64,000 bytes. Thus we have 80 bytes per character to hide data in. Since each bit takes a byte, we have 10 bytes per bit to hide data in! Therefore, if we take a pseudo-random number between 1 and 10, and use that byte to hide our low-order bit in, we have achieved a message dispersed through the GIF in a pseudo-random fashion, much harder to extract. A message in which each byte has a bit which is significant to the steganographically hidden message can be extracted with ease relative to a message in which there are 10 possible bytes for each bit of each character. The later is exponentially harder to extract, given no esoteric knowledge. A slight improvement can be made to this algorithm. By re-calculating the number of available bytes left for each bit after each bit is hidden, the data is dispersed more evenly throughout the file, instead of being bunched up at the start, which would be a normal occurrence. If you use pseudo-random number generator, picking numbers from 0-9, over time, the values will smooth to 5. This will cause the hidden message to be clustered at the beginning of the GIF. By re-calculating each time the number of available bytes left we spread the data out throughout the file, with the added bonus that later bits will be further spread apart than earlier ones, resulting in possible search spaces of 20, 30, 100, or even 1,000 possible bytes per bit. This too serves to make the data much harder to extract. I recommend a header large enough for an 8 character ASCII password, an integral random-number seed, an integral version number, and an place holder left for future uses. The version number allows us to tweak the algorithm and still be able to be compatible with past versions of the program. The header should be encrypted and undispersed (ie: 1 byte per bit of data) since we haven't seeded the random-number generator yet for dispersion purposes. It is useful to make the extractor in such a way that it always extracts something, regardless of the password being correct or not. Doing this means that it is impossible to tell if you have guessed a correct password and gotten encrypted data out, or merely gotten out garbage that looks like encrypted data. Use of a password can also be made optional, so that none is necessary for extraction. A simple default password can be used in these cases. When hiding encrypted data, there is no difference to the naked eye between what is extracted and what is garbage, so no password is strictly necessary. This means no password has to be remembered, or transmitted to other parties. A third party cannot tell if a real password has been used or not. It is important for safety purposes to not hide the default password in the header if no password is used. Otherwise, a simple match can be made by anyone who knows the default password.