An Introduction to Steganography

by Duncan Sellars

1. Executive Summary

Steganography, the art of hiding messages inside other messages, has until recently been the poor cousin of cryptography. Now, it is gaining new popularity with the current industry demands for digital watermarking and fingerprinting of audio and video.

What are watermarking and fingerprinting? Through the use of advanced computer software, authors of images, music and software can place a hidden ``trademark'' in their product, allowing them to keep a check on piracy. This is commonly known as watermarking. Hiding serial numbers or a set of characteristics that distinguishes an object from a similar object is known as fingerprinting. Together, these two are intended to fight piracy. The latter is used to detect copyright violators and the former is used to prosecute them. But these are only examples of the much wider field of steganography.

In this paper, we aim to present a general introduction to steganography, or data-hiding, as it is sometimes just known. A strong focus on the history of steganography is provided. We study the tricks the early Romans used, such as writing on the wood under wax tablets, through the developments of the Middle Ages and ending with the triumphs of World War II, such as the German microdot, hailed by J. Edgar Hoover as a ``... masterpiece of espionage''.

We then turn to data-hiding in three different media: that of text, images, and audio signals. Each offers different challenges, and solutions to those challenges.

When examining these data-hiding techniques, we bear in mind Bender's specifications, such as degradation of the cover data must be kept to a minimum, and the hidden data must be made as immune as possible to possible attack from manipulation of the cover data.

In studying steganography in text, we examine three main techniques: line-shift coding, word-shift coding, and feature coding. Each is designed to fight illegal distribution of text documents by stamping some recognisable feature into the text, either by shifting the lines, shifting the word spacing, or altering characteristics of the letters themselves. We find that some of these methods are quite strong, proving resistant to even 10 levels of photocopying.

We also look at some more interesting, alternative methods, such as using grammar to encode data.

Steganography in images has truly come of age with the invention of fast, powerful computers. Software is readily available off the Internet for any user to hide data inside images. The most popular technique is Least Significant Bit insertion, which we will look at. Also, we look at more complex methods such as masking and filtering, and algorithms and transformations, which offer the most robustness to attack, such as the Patchwork method in [1], which exploits the human eye's weakness to luminance variation.

The final medium, audio, is first explained through a look at how audio is stored and transmitted. It is then explored through four main methods of data-hiding: Least significant bit insertion, phase coding, spread spectrum coding, and echo hiding. Again, the techniques and their strengths and weaknesses are examined.

Finally, we will take a brief look at steganalysis, the science of detecting hidden messages.

We conclude by finding that steganography offers great potential for securing of data copyright, and detection of infringers. Soon, through steganography, all artistic creations, pictures, and songs can be protected from piracy.

2. Introduction

Perhaps when you were a child, you used lemon juice to write text on paper, then let the paper dry. Your writing would miraculously reappear on the apparently blank sheet of paper when you heated it.

Or perhaps when you were older, and were introduced to money, you noticed the image, or watermark, that would appear on bank notes when they were held up to the light. Both these types of situations are examples of steganography, the art of secret writing.

Steganography, from the Greek, means covered, or secret writing, and is a long-practised form of hiding information. Although related to cryptography, they are not the same. Steganography's intent is to hide the existence of the message, while cryptography scrambles a message so that it cannot be understood.

More precisely, as Kuhn puts it:

``the goal of steganography is to hide messages inside other harmless messages in a way that does not allow any enemy to even detect that there is a second secret message present.'' [2]

Steganography includes a vast array of techniques for hiding messages in a variety of media. Among these methods are invisible inks, microdots, digital signatures, covert channels and spread-spectrum communications. Today, thanks to modern technology, steganography is used on text, images, sound, signals, and more.

The advantage of steganography is that it can be used to secretly transmit messages without the fact of the transmission being discovered. Often, using encryption might identify the sender or receiver as somebody with something to hide. For example, that picture of your cat could conceal the plans for your company's latest technical innovation.

However, steganography has a number of disadvantages as well. Unlike encryption, it generally requires a lot of overhead to hide a relatively few bits of information. However, there are ways around this. Also, once a steganographic system is discovered, it is rendered useless. This problem, too, can be overcome if the hidden data depends on some sort of key for its insertion and extraction [3].

In fact, it is common practice to encrypt the hidden message before placing it in the cover message. However, it should be noted that the hidden message does not need to be encrypted to qualify as steganography. The message itself can be in plain English and still be a hidden message. However, most steganographers like the extra layer of protection that encryption provides. If your hidden message is found, then at least make it as protected as possible.

This paper aims to outline a general introduction to steganography - what it is, and where it comes from. Methods for hiding data in three varied media (text, image, and audio) will be described, and some guidelines for users of steganography will be provided where necessary. In addition, we will take a brief look at steganalysis, the science of detecting steganography, and destroying it.

3. Introduction to Terms used

In the field of steganography, some terminology has developed.

The adjectives cover, embedded and stego were defined at the Information Hiding Workshop held in Cambridge, England. The term ``cover'' is used to describe the original, innocent message, data, audio, still, video and so on. When referring to audio signal steganography, the cover signal is sometimes called the ``host'' signal.

The information to be hidden in the cover data is known as the ``embedded'' data. The ``stego'' data is the data containing both the cover signal and the ``embedded'' information. Logically, the processing of putting the hidden, or embedded data, into the cover data, is sometimes known as embedding.

Occasionally, especially when referring to image steganography, the cover image is known as the container.

4. History

Our earliest records of steganography were recorded by the Greek historian Herodotus and date back to Greek times. When the Greek tyrant Histiaeus was held as a prisoner by king Darius in Susa during the 5th century BCE, he had to send a secret message to his son-in-law Aristagoras in Miletus. Histiaeus shaved the head of a slave and tattooed a message on his scalp. When the slave's hair had grown long enough he was dispatched to Miletus.

Another story from ancient Greece also comes to us via Herodotus. The writing medium of the time was text, written on wax-covered tablets. Demeratus, a Greek, needed to notify Sparta that Xerxes intended to invade Greece. To avoid capture, he scraped the wax off of the tablets and wrote the message on the underlying wood. Then he covered the tablets with wax again. The tablets appeared to be blank and unused so they passed inspection.

Invisible inks have always been a popular method of steganography. Ancient Romans used to write between lines using invisible inks based on readily-available substances such as fruit juices, urine and milk. When heated, the invisible inks would darken, and become legible. Invisible inks were used as recently as World War II.

An early researcher in steganography and cryptography was Johannes Trithemius (1462-1526), a German monk. His first work on steganography, Steganographia, described systems of magic and prophecy, but also contained a complex system of cryptography. It was only published posthumously, as Trithemius had feared the reaction of the authorities if it was published.

The earliest actual book on steganography was a four hundred page work written by Gaspari Schotti in 1665 and called Steganographica. Although most of the ideas came from Trithemius, it was a start.

Steganography continued to develop during the fifteenth and sixteenth centuries. Because they were often afraid of the wrath of powerful factions, authors of books such as histories often concealed their names in their work. A treatise on this concept was written by Bishop John Wilkins, later the master of Trinity College, Cambridge. He devised a number of schemes ranging from coding messages in music and string knots to invisible inks, described the principles of cryptanalysis by letter frequencies, and argued against those who opposed publication in the field.

Figure 1: Francis Bacon - the real Bard?

As an interesting example of steganography of this era, many scholars suspect the authorship of the Shakespearean plays can be attributed to Francis Bacon, the noted Elizabethan statesman and writer. They back this up with the discovery of several hidden texts - steganographies - in the plays, which contain the name of Bacon. These ciphers, together with some interesting background information on Shakespeare and Bacon, makes for a convincing argument. Penn Leary, in his book ``The Second Cryptographic Shakespeare'' discusses this in detail.

Further development in the field occurred in 1883, with the publication of Auguste Kerckhoffs' Cryptographie militaire. Although this work was mostly about cryptography, it describes some principles that are worth keeping in mind when designing a new steganographic system. Later, Les Filigranes, written by Charle Briquet in 1907, was a historical dictionary of watermarks.

But it was during the twentieth century that steganography truly flowered.

An example of this comes from early in the century, during the Boer War. Lord Robert Baden-Powell, founder of the Boy Scout movement, was employed as a scout by the British. His job was to mark the positions of Boer artillery bases. To ensure he was not suspected by the Boers if he was caught, he would work his maps into drawings of butterflies. Appearing innocent to a casual observer, certain markings on the wings were actually the positions of the enemy military installations.

World War II marked a period of intensive steganographical experimentation. Early in the war, steganographic technology consisted almost entirely of invisible inks.

Later, null ciphers (unencrypted messages) were used to hide secret messages. The null cipher, which often appeared to be an innocent message about ordinary occurrences, would not alert suspicion, and would thus not be intercepted [4]. For example, the following message was sent by a German spy during WWII:

Apparently neutral's protest is thoroughly discounted and ignored. Isman hard hit. Blockade issue affects pretext for embargo on by-products, ejecting suets and vegetable oils.

Decoding this message by taking the second letter in each word reveals the following secret message:

Pershing sails from NY June 1.

Document layout was also used to reveal information. By modulating the position of lines and words, messages could be marked and identified [4].

Techniques such as writing messages in typewriter correction ribbon, and using pin punctures to mark selected letters were used [3].

As new technologies were developed that could pass more information and be even less conspicuous were developed, message detection improved. The German invention of the microdot was dubbed by FBI Director J. Edgar Hoover as ``the enemy's masterpiece of espionage''. Microdots are photographs the size of a printed period having the clarity of standard-sized typewritten pages, which permits the transmission of large amounts of data, including drawings and photographs [4].

In fact, the atmosphere of paranoia about messages being transmitted was so intense that several restrictions were put in place that might seem ridiculous today. In the USA, the international mailing of postal chess games, knitting instructions, newspaper clippings, and children's drawings was banned. Even international orders for flower deliveries were eventually banned by the US and British governments [5].

With the computer age, steganography has been given a marvellous boost. Old methods, such as hiding messages in images, have been given new leases of life through the computer. We are sure to see a great expansion of steganographical techniques in the coming years.

5. Steganography under Various Media

In the following three sections we will try to show how steganography can and is being used through the media of text, images, and audio.

Often, although it is not necessary, the hidden messages will be encrypted. This meets a requirement posed by the ``Kerckhoff principle'' in cryptography. This principle states that the security of the system has to be based on the assumption that the enemy has full knowledge of the design and implementation details of the steganographic system. The only missing information for the enemy is a short, easily exchangeable random number sequence, the secret key. Without this secret key, the enemy should not have the chance to even suspect that on an observed communication channel, hidden communication is taking place. [6] Most of the software that we will discuss later meets this principle.

When embedding data, Bender et al. reminds us [1] that it is important to remember the following restrictions and features:

The cover data should not be significantly degraded by the embedded data, and the embedded data should be as imperceptible as possible. (This does not mean the embedded data needs to be invisible; it is possible for the data to be hidden while it remains in plain sight.)

The embedded data should be directly encoded into the media, rather than into a header or wrapper, to maintain data consistency across formats.

The embedded data should be as immune as possible to modifications from intelligent attacks or anticipated manipulations such as filtering and resampling.

Some distortion or degradation of the embedded data can be expected when the cover data is modified. To minimise this, error correcting codes should be used.

The embedded data should be self-clocking or arbitrarily re-entrant. This ensures that the embedded data can still be extracted when only portions of the cover data is available. For example, if only a part of image is available, the embedded data should still be recoverable.

6. Steganography in Text

One problem identified by Brassil and others is the illegal distribution of documents through modern electronic means, such as electronic mail. Means such as this allow infringers to make identical copies of documents without paying royalties or revenues to the original author. To counteract this possible wide-scale piracy, Brassil et al. discuss in [7] a method of marking printable documents with a unique codeword that is indiscernible to readers, but can be used to identify the intended recipient of a document just by examination of a recovered document.

The techniques they propose are intended to be used in conjunction with standard security measures. For example, documents should still be encrypted prior to transmission across a network. Primarily, their techniques are intended for use after a document has been decrypted, once it is readable to all.

An added advantage of their system is that it is not prone to distortion by methods such as photocopying, and can thus be used to trace paper copies back to their source.

An additional application of text steganography suggested by Bender, et al. is annotation, that is, checking that a document has not been tampered with. Hidden data in text could even by used by mail servers to check whether documents should be posted or not [1].

The marking techniques Brassil et al. describes are to be applied to either an image representation of a document or to a document format file, such as PostScript or TEXfiles. The idea is that a codeword (such as a binary number, for example) is embedded in the document by altering particular textual features. By applying each bit of the codeword to a particular document feature, we can encode the codeword. It is the type of feature that identifies a particular encoding method. Brassil identifies three features, that are described in the following subsections:

6.1 Line-Shift Coding

In this method, text lines are vertically shifted to encode the document uniquely. Encoding and decoding can generally be applied either to the format file of a document, or the bitmap of a page image.

By moving every second line of document either 1/300 of an inch up or down, Brassil et al. found that line-shift coding worked particularly well, and documents could still be completely decoded, even after the tenth photocopy.

However, this method is probably the most visible text coding technique to the reader. Also, line-shift encoding can be defeated by manual or automatic measurement of the number of pixels between text baselines. Random or uniform respacing of the lines can damage any attempts to decode the codeword.

However, if a document is marked with line-shift coding, it is particularly difficult to remove the encoding if the document is in paper format. Each page will need to be rescanned, altered, and reprinted. This is complicated even further if the printed document is a photocopy, as it will then suffer from effects such as blurring, and salt-and-pepper noise.

6.2 Word-Shift Coding

In word-shift coding, codewords are coded into a document by shifting the horizontal locations of words within text lines, while maintaining a natural spacing appearance. This encoding can also be applied to either the format file or the page image bitmap. The method, of course, is only applicable to documents with variable spacing between adjacent words, such as in documents that have been text-justified. As a result of this variable spacing, it is necessary to have the original image, or to at least know the spacing between words in the unencoded document.

The following is a simple example of how word-shifting might work. For each text-line, the largest and smallest spaces between words are found. To code a line, the largest spacing is reduced by a certain amount, and the smallest is extended by the same amount. This maintains the line length, and produces little visible change to the text.

Word-shift coding should be less visible to the reader than line-shift coding, since the spacing between adjacent words on a line is often shifted to support text justification.

However, word-shifting can also be detected and defeated, in either of two ways.

If one knows the algorithm used by the formatter for text justification, actual spaces between words could then be measured and compared to the formatter's expected spacing. The differences in spacing would reveal encoded data.

A second method is to take two or more distinctly encoded, uncorrupted documents and perform page by page pixel-wise difference operations on the page images. One could then quickly pick up word shifts and the size of the word displacement.

By respacing the shifted words back to the original spacing produced under the formatter, or merely applying random horizontal shifts to all words in the document not found at column edges, an attacker could eliminate the encoding. However, it is felt that these methods would be time-consuming and painstaking.

6.3 Feature Coding

A third method of coding data into text suggested by Brassil et al. is known as feature coding. This is applied either to the bitmap image of a document, or to a format file. In feature coding, certain text features are altered, or not altered, depending on the codeword. For example, one could encode bits into text by extending or shortening the upward, vertical endlines of letters such as b, d, h, etc. Generally, before encoding, feature randomisation takes place. That is, character endline lengths would be randomly lengthened or shortened, then altered again to encode the specific data. This removes the possibility of visual decoding, as the original endline lengths would not be known. Of course, to decode, one requires the original image, or at least a specification of the change in pixels at a feature.

Due to the frequently high number of features in documents that can be altered, feature coding supports a high amount of data encoding. Also, feature encoding is largely indiscernible to the reader. Finally, feature encoding can be applied directly to image files, which leaves out the need for a format file.

when trying to attack a feature-coded document, it is interesting that a purely random adjustment of endline lengths is not a particularly strong attack on this coding method. Feature coding can be defeated by adjusting each endline length to a fixed value. This can be done manually, but would be painstaking. Although this process can be automated, it can be made more challenging by varying the particular feature to be encoded. To even further complicate the issue, word shifting might be used in conjunction with feature coding, for example. Efforts such as this can place enough impediments in the attacker's way to make his job difficult and time-consuming.

6.4 Alternative Methods

Alternative, interesting text-coding methods are provided by Bender, et al. in [1]. He suggests three major method of encoding data:

Open space methods, similar to the ones suggested by Brassil
Syntactic methods, that utilise punctuation and contractions
Semantic methods, that encode using manipulation of the words themselves The syntactic and semantic methods are particularly interesting. In syntactic methods, multiple methods of punctuation are harnessed to encode data. For example, the two phrases below are both considered correct, although the first line has an extra comma:

bread, butter, and milk bread, butter and milk

Alternation between these two forms of listing can be used to represent binary data. Other methods of syntactic encoding include the controlled use of contractions and abbreviations. Although such syntactic encoding is very possible in the English language, the amount of data that could be encoded would be very low, somewhere in the order of a several bits per kilobyte of text.

The final category of data hiding suggested by Bender, et al. is semantic methods. By assigning values to synonyms, data could be encoded into the actual words of the text. For example, the word big might be given a value of one, the word large a value of zero. Then, when the word big is encountered in the coded text, a value of one can be decoded. Further synonyms can mean greater bit encoding. However, these methods can sometimes interfere with the nuances of meaning.

7. Steganography in Images

In this section we deal with data encoding in still digital images. In essence, image steganography is about exploiting the limited powers of the human visual system (HVS) [1]. Within reason, any plain text, ciphertext, other images, or anything that can be embedded in a bit stream can be hidden in an image. Image steganography has come quite far in recent years with the development of fast, powerful graphical computers, and steganographic software is now readily available over the Internet for everyday users.

7.1 Some Guidelines to Image Steganography

Before proceeding further, some explanation of image files is necessary. To a computer, an image is an array of numbers that represent light intensities at various points, or pixels. These pixels make up the image's raster data. An image size of 640 by 480 pixels, utilising 256 colours (8 bits per pixel) is fairly common. Such an image would contain around 300 kilobits of data [4].

Digital images are typically stored in either 24-bit or 8-bit per pixel files. 24-bit images are sometimes known as true colour images. Obviously, a 24-bit image provides more space for hiding information; however, 24-bit images are generally large and not that common. A 24-bit image 1024 pixels wide by 768 pixels high would have a size in excess of 2 megabytes. As such large files would attract attention were they to be transmitted across a network or the Internet, image compression is desirable. However, compression brings with it other problems, as will explained shortly.

Alternatively, 8-bit colour images can be used to hide information. In 8-bit colour images, (such as GIF files), each pixel is represented as a single byte. Each pixel merely points to a colour index table, or palette, with 256 possible colours. The pixel's value, then, is between 0 and 255. The image software merely needs to paint the indicated colour on the screen at the selected pixel position.

If using an 8-bit image as the cover-image, many steganography experts recommend using images featuring 256 shades of grey as the palette, for reasons that will become apparent. Grey-scale images are preferred because the shades change very gradually between palette entries. This increases the image's ability to hide information.

When dealing with 8-bit images, the steganographer will need to consider the image as well as the palette. Obviously, an image with large areas of solid colour is a poor choice, as variances created by embedded data might be noticeable. Once a suitable cover image has been selected, an image encoding technique needs to be chosen.

7.2 Image Compression

Image compression offers a solution to large image files. Two kinds of image compression are lossless and lossy compression. Both methods save storage space but have differing effects on any uncompressed hidden data in the image.

Lossy compression, as typified by JPEG (Joint Photographic Experts Group) format files, offers high compression, but may not maintain the original image's integrity. This can impact negatively on any hidden data in the image. This is due to the lossy compression algorithm, which may ``lose'' unnecessary image data, providing a close approximation to high-quality digital images, but not an exact duplicate. Hence, the term ``lossy'' compression. Lossy compression is frequently used on true-colour images, as it offers high compression rates.

Lossless compression maintains the original image data exactly; hence it is preferred when the original information must remain intact. It is thus more favoured by steganographic techniques. Unfortunately, lossless compression does not offer such high compression rates as lossy compression. Typical examples of lossless compression formats are Compuserve's GIF (Graphics Interchange Format) and Microsoft's BMP (Bitmap) format.

7.3 Image Encoding Techniques

Information can be hidden many different ways in images. Straight message insertion can be done, which will simply encode every bit of information in the image. More complex encoding can be done to embed the message only in ``noisy'' areas of the image, that will attract less attention. The message may also be scattered randomly throughout the cover image [4].

The most common approaches to information hiding in images are:

Least significant bit (LSB) insertion
Masking and filtering techniques
Algorithms and transformations

Each of these can be applied to various images, with varying degrees of success. Each of them suffers to varying degrees from operations performed on images, such as cropping, or resolution decrementing, or decreases in the colour depth.

7.3.1 Least Significant bit insertion

The least significant bit insertion method is probably the most well known image steganography technique. It is a common, simple approach to embedding information in a graphical image file. Unfortunately, it is extremely vulnerable to attacks, such as image manipulation. A simple conversion from a GIF or BMP format to a lossy compression format such as JPEG can destroy the hidden information in the image.

When applying LSB techniques to each byte of a 24-bit image, three bits can be encoded into each pixel. (As each pixel is represented by three bytes.) Any changes in the pixel bits will be indiscernible to the human eye. For example, the letter A can be hidden in three pixels. Assume the original three pixels are represented by the three 24-bit words below:

( 00100111 11101001 11001000 ) ( 00100111 11001000 11101001 ) ( 11001000 00100111 11101001 )

The binary value for the letter A is (10000011). Inserting the binary value of A into the three pixels, starting from the top left byte, would result in:

( 00100111 11101000 11001000 ) ( 00100110 11001000 11101000 ) ( 11001000 00100111 11101001 )

The emphasised bits are the only bits that actually changed. The main advantage of LSB insertion is that data can be hidden in the least and second to least bits and still the human eye would be unable to notice it.

When using LSB techniques on 8-bit images, more care needs to be taken, as 8-bit formats are not as forgiving to data changes as 24-bit formats are. Care needs to be taken in the selection of the cover image, so that changes to the data will not be visible in the stego-image. Commonly known images, (such as famous paintings, like the Mona Lisa) should be avoided. In fact, a simple picture of your dog would be quite sufficient.

When modifying the LSB bits in 8-bit images, the pointers to entries in the palette are changed. It is important to remember that a change of even one bit could mean the difference between a shade of red and a shade of blue. Such a change would be immediately noticeable on the displayed image, and is thus unacceptable. For this reason, data-hiding experts recommend using grey-scale palettes, where the differences between shades is not as pronounced. Alternatively, images consisting mostly of one colour, such as the so-called Renoir palette, named because it comes from a 256 colour version of Renoir's ``Le Moulin de la Galette''.

7.3.2 Masking and filtering

Masking and filtering techniques hide information by marking an image in a manner similar to paper watermarks. Because watermarking techniques are more integrated into the image, they may be applied without fear of image destruction from lossy compression. By covering, or masking a faint but perceptible signal with another to make the first non-perceptible, we exploit the fact that the human visual system cannot detect slight changes in certain temporal domains of the image [8].

Technically, watermarking is not a steganographic form. Strictly, steganography conceals data in the image; watermarking extends the image information and becomes an attribute of the cover image, providing license, ownership or copyright details.

Masking techniques are more suitable for use in lossy JPEG images than LSB insertion because of their relative immunity to image operations such as compression and cropping.

7.3.3 Algorithms and transformations

Because they are high quality colour images with good compression, it is desirable to use JPEG images across networks such as the Internet. Indeed, JPEG images are becoming abundant on the Internet.

JPEG images use the discrete cosine transform (DCT) to achieve compression. DCT is a lossy compression transform, because the cosine values cannot be calculated precisely, and rounding errors may be introduced. Variances between the original data and the recovered data depends on the values and methods used the calculate the DCT.

Images can also be processed using fast Fourier transformation and wavelet transformation. Other properties such as luminance can also be utilised. The HVS has a very low sensitivity to small changes in luminance, being able to discern changes of no less than one part in thirty for random patterns. This figure goes up to one part in 240 for uniform regions of an image.

Modern steganographic systems use spread-spectrum communications to transmit a narrowband signal over a much larger bandwidth so that the spectral density of the signal in the channel looks like noise.

The two different spread-spectrum techniques these tools employ are called direct-sequence and frequency hopping. The former hides information by phase-modulating the data signal (carrier) with a pseudorandom number sequence that both the sender and the receiver know. The latter divides the available bandwidth into multiple channels and hops between these channels (also triggered by a pseudorandom number sequence) [9].

The Patchwork method explored in [1] is based on a pseudorandom, statistical process that takes advantage of the human weaknesses to luminance variation. Using redundant pattern encoding to repeatedly scatter hidden information throughout the cover image, like a patchwork, Patchwork can hide a reasonably small message many times in a image. In the Patchwork method, n pairs of image points (a,b) are randomly chosen. The brightness of a is decreased by one and the brightness of b is increased by one. For a labeled image, the expected value of the sum of the differences of the n pairs of points is then 2n. Bender shows that after JPEG compression, with the quality factor set to 75, the message can still be decoded with an 85

This algorithm is more robust to image processing such as cropping and rotating, but at the cost of message size. Techniques such as Patchwork are ideal for watermarking of images. Even if the image is cropped, there is a good probability that the watermark will still be readable.

Other methods suggested by [10] also attempt to mark labels into the images by altering the brightness of pixel blocks of the image by a selected value k. This value k is dependent on a lower quality JPEG compressed version of the labelled block. This method is fairly resistant to JPEG compression, depending on the size of the pixel blocks used, and offers low visibility of the label. Unfortunately, it is not very suitable to real-time applications.

Other techniques encrypt and scatter the hidden throughout the image in some pre-determined manner. It is assumed that even if the message bits are extracted, they will be useless without the algorithm and stego-key to decode them. Although such techniques do help protect against hidden message extraction, they are not immune to destruction of the hidden message through image manipulation.

7.4 The Image Downgrading Problem

In multilevel security systems, such as the ones used by the army, it sometimes becomes necessary to declassify some information from a high level of access to a lower level. Unfortunately, downgrading of images can present a problem. Information could be covertly hidden in a ``top secret'' image for later retrieval when the image is declassified [11].

This problem has been pointed out by Kurak and McHugh [12], and is well demonstrated by the following sets of photographs, which illustrate how well data can be hidden. As can be seen in figures 2 and 3 on the following pages, the image of the Pentagon on the right of figure 2 is hidden in the picture of the original chapel on the left, giving the contaminated chapel picture and the encoded Pentagon picture on the right and left figure 3.

Figure 2: Original chapel and original Pentagon

Figure 3: Contaminated chapel and encoded Pentagon

8. Steganography in Audio

Because of the range of the human auditory system (HAS), data hiding in audio signals is especially challenging. The HAS perceives over a range of power greater than one billion to one and range of frequencies greater than one thousand to one. Also, the auditory system is very sensitive to additive random noise. Any disturbances in a sound file can be detected as low as one part in ten million (80dB below ambient level) [1]. However, while the HAS has a large dynamic range, it has a fairly small differential range - large sounds tend to drown quiet sounds.

When performing data hiding on audio, one must exploit the weaknesses of the HAS, while at the same time being aware of the extreme sensitivity of the human auditory system.

8.1 Audio Environments

When working with transmitted audio signals, one should bear in mind two main considerations. First, the means of audio storage, or digital representation of the audio, and second, the transmission medium the signal might take.

8.1.1 Digital representation

Digital audio files generally have two primary characteristics:

Sample quantisation method: The most popular format for representing samples of high-quality digital audio is a 16-bit linear quantisation, such as that used by WAV (Windows Audio-Visual) and AIFF (Audio Interchange File Format). Some signal distortion is introduced by this format.

Temporal sampling rate: The most popular temporal sampling rates for audio include 8kHz (kilohertz, 9.6kHz, 10kHz, 12kHz, 16kHz, 22.05kHz and 44.1kHz. Sampling rate puts an upper bound on the usable portion of the frequency range. Generally, usable data space increases at least linearly with increased sampling rate.

Another digital representation that should be considered is the ISO MPEG-Audio format, a perceptual encoding standard. This format drastically changes the statistics of the signal by encoding only the parts the listener perceives, thus maintaining the sound, but changing the signal.

8.1.2 Transmission medium

The transmission medium, or transmission environment, of an audio signal refers to the environments the signal might go through on its way from encoder to decoder.

Bender in identifies four possible transmission environments:

Digital end-to-end environment: If a sound file is copied directly from machine to machine, but never modified, then it will go through this environment. As a result, the sampling will be exactly the same between the encoder and decoder. Very little constraints are put on data-hiding in this environment. Increased/decreased resampling environment: In this environment, a signal is resampled to a higher or lower sampling rate, but remains digital throughout. Although the absolute magnitude and phase of most of the signal are preserved, the temporal characteristics of the signal are changed.

Analog transmission and resampling: This occurs when a signal is converted to an analog state, played on a relatively clean analog line, and resampled. Absolute signal magnitude, sample quantisation and temporal sampling rate are not preserved. In general, phase will be preserved.

''Over the air'' environment: This occurs when the signal is ``played into the air'' and ``resampled with a microphone''. The signal will be subjected to possible unknown nonlinear modifications causing phase changes, amplitude changes, drifting of different frequency components, echoes, etc.

The signal representation and transmission environment both need to be considered when choosing a data-hiding method.

8.2 Methods of Audio Data Hiding

We now need to consider some methods of audio data-hiding.

8.2.1 Low-bit encoding

Similarly to how data was stored in the least-significant bit of images, binary data can be stored in the least-significant bit of audio files. Ideally the channel capacity is 1kb per second per kilohertz, so for example, the channel capacity would be 44kbps in a 44kHz sampled sequence. Unfortunately, this introduces audible noise. Of course, the primary disadvantage of this method is its poor immunity to manipulation. Factors such as channel noise and resampling can easily destroy the hidden signal.

A particularly robust implementation of such a method is described by Bassia and Pitas in [8]. The result is a slight amplitude modification of each sample in a way that does not produce any perceptual difference. Their implementation offers high robustness to MPEG compression plus other forms of signal manipulation, such as filtering, resampling and requantization.

8.2.2 Phase coding

The phase coding method works by substituting the phase of an initial audio segment with a reference phase that represents the data. The procedure for phase coding is as follows:

The original sound sequence is broken into a series of N short segments. A discrete Fourier transform (DFT) is applied to each segment, to break create a matrix of the phase and magnitude.

The phase difference between each adjacent segment is calculated. For segment S0, the first segment, an artificial absolute phase p0 is created. For all other segments, new phase frames are created.

The new phase and original magnitude are combined to get a new segment, Sn. Finally, the new segments are concatenated to create the encoded output.

For the decoding process, the synchronisation of the sequence is done before the decoding. The length of the segment, the DFT points, and the data interval must be known at the receiver. The value of the underlying phase of the first segment is detected as 0 or 1, which represents the coded binary string.

8.2.3 Spread spectrum

Most communication channels try to concentrate audio data in as narrow a region of the frequency spectrum as possible in order to conserve bandwidth and power. When using a spread spectrum technique, however, the encoded data is spread across as much of the frequency spectrum as possible.

One particular method discussed in [1], Direct Sequence Spread Spectrum (DSSS) encoding, spreads the signal by multiplying it by a certain maximal length pseudorandom sequence, known as a chip. The sampling rate of the host signal is used as the chip rate for coding. The calculation of the start and end quanta for phase locking purposes is taken care of by the discrete, sampled nature of the host signal. As a result, a higher chip rate and therefore a higher associated data rate, is possible.

However, unlike phase coding, DSSS does introduce additive random noise to the sound.

8.2.4 Echo data hiding

Echo data hiding embeds data into a host signal by introducing an echo. The data are hidden by varying three parameters of the echo: initial amplitude, decay rate, and offset, or delay. As the offset between the original and the echo decreases, the two signals blend. At a certain point, the human ear cannot distinguish between the two signals, and the echo is merely heard as added resonance. This point depends on factors such as the quality of the original recording, the type of sound, and the listener.

By using two different delay times, both below the human ear's perceptual level, we can encode a binary one or zero. The decay rate and initial amplitude can also be adjusted below the audible threshold of the ear, to ensure that the information is not perceivable. To encode more than one bit, the original signal is divided into smaller portions, each of which can be echoed to encode the desired bit. The final encoded signal is then just the recombination of all independently encoded signal portions.

As a binary one is represented by a certain delay y, and a binary zero is represented by a certain delay x, detection of the embedded signal then just involves the detection of spacing between the echoes. A process for doing this is described in Gruhl, et al.s work, [13].

Echo hiding was found to work exceptionally well on sound files where there is no additional degradation, such as from line noise or lossy encoding, and where there is no gaps of silence. Work to eliminate these drawbacks is being done.

9. Steganalysis

Whereas the goal of steganography is the avoidance of suspicion to hidden messages in other data, steganalysis aims to discover and render useless such covert messages [14].

Two aspects of attacks on steganography are detection and destruction of the embedded message. In [15], Johnson explores attacks on the data-hiding capabilities of some contemporary steganography software tools.

In [16], the authors propose to use a public watermark detector as an oracle to estimate a secret spread spectrum watermark with a complexity quadratic in the number of samples. The image is first degraded until no watermark can be found, then random signals are added while the watermark cannot be detected.

A wide range of further literature on steganalysis is available, but is beyond the scope of this paper.

10. Conclusion

In this paper, we take an introductory look at steganography. Historical detail is discussed. Several methods for hiding data in text, images, and audio are described, with appropriate introductions to the environments of each medium, as well as the strengths and weaknesses of each method. Most data-hiding systems take advantage of human perceptual weaknesses, but have weaknesses of their own. We conclude that for now, it seems that no system of data-hiding is totally immune to attack.

However, steganography has its place in security. It in no way can replace cryptography, but is intended to supplement it. Its application in watermarking and fingerprinting, for use in detection of unauthorised, illegally copied material, is continually being realised and developed.

Also, in places where standard cryptography and encryption is outlawed, steganography can be used for covert data transmission. Steganography, formerly just an interest of the military, is now gaining popularity among the masses. Soon, any computer user will be able to put his own watermark on his artistic creations.

Bibliography

1 W. Bender, D. Gruhl, N. Morimoto, and A. Lu. Techniques for data hiding. In IBM Systems Journal, Vol. 35, Nos. 3-4, pages 313-336, February 1996.

2 N.F. Johnson. Steganography. WWW: http://www.jjtc.com/stegdoc/. George Mason University.

3 William Stalling. Network and Internetwork Security. Addison-Wesley professional computing series. Addison-Wesley, 1996. ISBN 0-201-63337-X.

4 N.F. Johnson and S. Jajodia. Exploring steganography: Seeing the unseen. Computer, 31, no 2:26-34, February 1998.

5 Michael Berkowitz. Privacy on the net - steganography. WWW: http://www.tamos.com/privacy/steganoen.htm, 1998.

6 M. Kuhn. Steganography mailing list. WWW: http://www.jjtc.com/Steganography/steglist.htm, 1995. Private Site, Hamburg, Germany.

7 J. Brassil, S. Low, N. Maxemchuk, and L. O'Garman. Electronic marking and identification techniques to discourage document copying. In IEEE Infocom 94, pages 1278-1287, 1994.

8 P. Bassia and I. Pitas. Robust audio watermarking in the time domain. Findings report, Dept. of Informatics, University of Thessaloniki, 1998. http://poseidon.csd.auth.gr/ voyatzis/creus.zip.

9 Jian Zhao. Look, it's not there. Byte, 1:401-407, January 1997.

10 G.C. Langelaar, Jan C.A. van der Lubbe, and Reginald L. Lagendijk. Robust labelling methods for copy protection of images. Findings report, Department of Electrical Engineering, Information Theory Group, Delft University of Technology, 1997. http://www-it.et.tudelft.nl/ gerhard/spie97.zip.

11 F.A.B. Petitcolas. The information hiding homepage -digital watermarking and steganography. WWW: http://www.cl.cam.ac.uk/ fapp2/steganography, 1997. University of Cambridge, Computer Laboratory, Security Group.

12 C. Kurak and J. McHugh. A cautionary note on image downgrading. In Proceedings of the 8th Annual Computer Security Applications Conference, pages 153-159, 1992.

13 Daniel Gruhl, Walter Bender, and Antony Lu. Echo hiding. Findings report, Massachusetts Institute of Technology Media Laboratory, 1996. http://www.media.mit.edu/ druid/documents/edh2.ps.

14 N.F. Johnson. Steganography and digital watermarking - information hiding. WWW: http://www.jjtc.com/Steganography/, 1996.

1 N.F. Johnson. Steganalysis of images created using current steganography software. Findings report, Center for Secure Information Systems, George Mason University, 1998.

16 T. Kalker. Watermark estimation through detector observations. In Proceedings of the Benelux Signal Processing Symposium, 98, pages 128-139, 1998.