A Brief History of Information Hiding
In this section we do not intend to cover the whole history of information hiding, rather just give the important landmarks.
The most famous examples of steganography go back to antiquity. In his Histories , Herodotus (c. 486-425 B.C.) tells how around 440 B.C. Histiæus shaved the head of his most trusted slave and tattooed it with a message which disappeared after the hair had regrown. The purpose was to instigate a revolt against the Persians. Astonishingly, the method was still used by some German spies at the beginning of the 20th century .
Herodotus also tells how Demeratus, a Greek at the Persian court, warned Sparta of an imminent invasion by Xerxes, King of Persia: he removed the wax from a writing tablet, wrote his message on the wood underneath and then covered the message with wax. The tablet looked exactly like a blank one (it almost fooled the recipient as well as the customs men). A large number of techniques were invented or reported by Æneas the Tactician , including letters hidden in messengers' soles or women’s earrings, text written on wood tablets and then whitewashed, and notes carried by pigeons. He also proposed hiding text by changing the heights of letterstrokes or by making very small holes above or below letters in a cover-text. This latter technique was still in use during the 17th century, but was improved by Wilkins (1614–1672) who used invisible ink to print very small dots instead of making holes  and was reused again by German spies during both World Wars [8, p. 83]. A modern adaptation of this technique is still in use for document security  and prints blocks of tiny pixels across a page to encode information such as date, printer identifier, and user identifier.
In 1857, Brewster already suggested hiding secret messages “in spaces not larger than a full stop or small dot of ink”  and by 1860 the basic problems of making tiny images had been solved by Dragon, a French photographer: during the Franco-Prussian War of 1870–1871, while Paris was besieged, messages on microfilm were sent out by pigeon post [17, 18]. During the Russo-Japanese war of 1905, microscopic images were hidden in ears, nostrils, and under fingernails . Finally, Brewster’s idea became real by World War I when messages to and from spies were reduced to microdots by several stages of photographic reduction and then stuck on top of printed periods or commas in innocuous cover material such as magazines [12, 20].
Invisible inks have been used extensively. They were originally made of available organic substances (such as milk or urine) or “salt armoniack dissolved in water” [14, V, pp. 37–47] and developed with heat; progress in chemistry helped to create more sophisticated combinations of ink and developer by the first World War, but the technology fell into disuse with the invention of “universal developers” which could determine which parts of a piece of paper had been wetted from the effects on the surfaces of the fibers [8, pp. 523–525]. This leads to the more familiar application-specific information hiding and marking technologies found in the world of secure printing [21, 22]. Watermarks in paper are a very old anticounterfeiting technique; more recent innovations include special ultraviolet fluorescent inks used in printing traveler’s checks. As the lamps used in photocopiers have a high ultra-violet content, it can be arranged that photocopies come out overprinted with “void” in large letters. The reader is referred to van Renesse [21, 22] for a survey of recent developments.
Another example comes from architecture: since its early days, artists have understood that works of sculpture or painting appear different from certain angles, and established rules for perspective and anamorphosis . Through the 16th and 17th centuries anamorphic images supplied an ideal means of camouflaging dangerous political statements and heretical ideas . A masterpiece of hidden anamorphic imagery—the Vexierbild—was created in the 1530s by Shö, a Nürnberg engraver, pupil of Dürer (1471–1528); when one looks at it straight on, one sees a strange landscape, but looking from the side reveals portraits of famous kings.
A widely used method of linguistic steganography is the acrostic. The most famous example is probably Giovanni Boccaccio’s (1313–1375) Amorosa visione which is said to be the “world’s hugest acrostic”. Boccaccio first wrote three sonnets—containing about 1,500 letters all together—and then wrote other poems such that the initial of the successive tercets correspond exactly to the letters of the sonnets. Another famous example of acrostic comes from the Hypnerotomachia Poliphili ,1 published in 1499. This puzzling and enigmatic book, written anonymously, reveals the guilty love between a monk and a woman: the first letter of the thirty eight chapters spelled out “Poliam frater Franciscus Columna peramavit.”
Expanding on the simple idea of the acrostic, monks and other literate people found ways to better conceal messages mainly into text. By the 16th and 17th centuries, there had arisen a large amount of literature on steganography and many of the methods depended on novel means of encoding information. In his 400 page book Schola Steganographica , Gaspar Schott (1608–1666) expands the “Ave Maria” code proposed by Trithemius in Polygraphiæ, together with Steganographia (see Figure 1.2) two of the first known books in the field of cryptography and steganography. The expanded code uses 40 tables, each of which contains 24 entries (one for each letter of the alphabet of that time) in four languages: Latin, German, Italian, and French. Each letter of the plain-text is replaced by the word or phrase that appears in the corresponding table entry and the stego-text ends up looking like a prayer, a simple correspondence letter, or a magic spell. Schott also explains how to hide messages in music scores; each note corresponds to a letter (Figure 1.1). Another method, based on the number of occurrences of notes used by J. S. Bach, is mentioned by Bauer . John Wilkins, showed how “two Musicians may discourse with one another by playing upon their instruments of musick as well as by talking with their instruments of speech” [14, XVIII, pp. 143–150]. He also explains how one can hide secretly a message into a geometric drawing using points, lines, or triangles: “the point, the ends of the lines and the angles of the figures do each of them by their different situation express a several letter” [14, XI, pp. 88–96]. An improvement is made when the message is hidden at random locations in the cover-text. This idea is the core of many current steganographic systems. In a security protocol developed in ancient China, the sender and the receiver had copies of a paper mask with a number of holes cut at random locations. The sender would place his mask over a sheet of paper, write the secret message into the holes, remove the mask, and then compose a cover message incorporating the code ideograms. The receiver could read the secret message at once by placing his mask over the resulting letter. In the early 16th century Cardan (1501–1576), an Italian mathematician, reinvented this method which is now known as the Cardan grille.
The presence of errors or stylistic features at predetermined points in the cover material is another way to select the location of the embedded information. An early example was a technique used by Francis Bacon (1561–1626) in his biliterarie alphabet [29, pp. 266], which seems to be linked to the controversy of whether he wrote the works attributed to Shakespeare . In this method each letter is encoded in a five-bit binary code and embedded in the cover-text by printing the letters in either normal or italic fonts. The variability of 16th century typography acted as camouflage. Similar techniques have been used in an electronic publishing pilot project: copyright messages and serial numbers have been hidden in the line spacing and other format features of documents (e.g., Brassil et al. ). It was found that shifting text lines up or down by one-three-hundredth of an inch to encode zeros and ones was robust against multigeneration photocopying and could not be noticed by most people. Further examples come from the world of mathematical tables. Publishers of logarithm tables and astronomical ephemerides in the 17th and 18th century used to introduce errors deliberately in the least significant digits (e.g., ). To this day, database and mailing list vendors insert bogus entries in order to identify customers who try to resell their products.<< Wisdom from Cryptography || Introduction to Information Hiding >>