Steganography

This article is about hidden messages. For shorthand, see Stenography.

Steganography is the art and science of writing hidden messages in such a way that no one apart from the intended recipient knows of the existence of the message; this is in contrast to cryptography, where the existence of the message itself is not disguised, but the content is obscured. With the advent of digital media, steganography has come to include the hiding of digital information within digital files. For example, the color value of every 100th pixel within a digital image could represent a letter in the alphabet.

The word steganography is of Greek origin and means "covered, or hidden writing". Its ancient origins can be traced back to 440 BC. Herodotus mentions two examples of steganography in The Histories of Herodotus [1]. Demeratus sent a warning about a forthcoming attack to Greece by writing it on a wooden panel and covering it in wax. Wax tablets were in common use then as re-usable writing surface, sometimes used for shorthand. Another ancient example is that of Histiaeus, who shaved the head of his most trusted slave and tattooed a message on it. After his hair had grown the message was hidden. The purpose was to instigate a revolt against the Persians. Later, Johannes Trithemius's book Steganographia is a treatise on cryptography and steganography disguised as a book on black magic.

Generally, a steganographic message will appear to be something else: a picture, an article, a shopping list, or some other message. This apparent message is the covertext. For instance, a message may be hidden by using invisible ink between the visible lines of innocuous documents.

The advantage of steganography over cryptography alone is that messages do not attract attention to themselves, to messengers, or to recipients. An unhidden coded message, no matter how unbreakable it is, will arouse suspicion and may in itself be incriminating, as in countries where encryption is illegal.[2] Oftentimes, steganography and cryptography are used together to ensure security of the covert message.

Steganography used in electronic communication include steganographic coding inside of a transport layer, such as an MP3 file, or a protocol, such as UDP.

A steganographic message (the plaintext) is often first encrypted by some traditional means, producing a ciphertext. Then, a covertext is modified in some way to contain the ciphertext, resulting in stegotext. For example, the letter size, spacing, typeface, or other characteristics of a covertext can be manipulated to carry the hidden message; only the recipient (who must know the technique used) can recover the message and then decrypt it. Francis Bacon is known to have suggested such a technique to hide messages (see Bacon's cipher).

Steganographic techniques

Modern steganographic techniques

• Concealing messages within the lowest bits of noisy images or sound files.
• Concealing data within encrypted data. The data to be concealed is first encrypted before being used to overwrite part of a much larger block of encrypted data. This technique works most effectively where the decrypted version of data being overwritten has no special meaning or use: some cryptosystems, especially those designed for filesystems, add random looking padding bytes at the end of a ciphertext so that its size cannot be used to figure out the size of the original plaintext. Examples of software that use this technique include FreeOTFE and TrueCrypt.
• Chaffing and winnowing
• Invisible ink
• Null ciphers
• Concealed messages in tampered executable files, exploiting redundancy in the i386 instruction set [3].
• Embedded pictures in video material (optionally played at slower or faster speed).
• A new steganographic technique involves injecting imperceptible delays to packets sent over the network from the keyboard. Delays in keypresses in some applications (telnet or remote desktop software) can mean a delay in packets, and the delays in the packets can be used to encode data. There is no extra processor or network activity, so the steganographic technique is "invisible" to the user. This kind of steganography could be included in the firmware of keyboards, thus making it invisible to the system. The firmware could then be included in all keyboards, allowing someone to distribute a keylogger program to thousands without their knowledge.[4]
• Content-Aware Steganography hides information in the semantics a human user assigns a datagram; these systems offer security against a non-human adversary/warden.[5]
• The most important requirement for modern steganography is the embedding capacity, i.e., the amount of data that can be concealed in one vessel file. In case of BPCS-Steganography (http://www.datahide.com/BPCSe/) it is reported to have almost 50% of concealing capacity.

Historical steganographic techniques

Steganography has been widely used in historical times, especially before cryptographic systems were developed. Examples of historical usage include:

• Hidden messages in wax tablets: in ancient Greece, people wrote messages on the wood, then covered it with wax so that it looked like an ordinary, unused tablet.
• Hidden messages on messenger's body: also in ancient Greece. Herodotus tells the story of a message tattooed on a slave's shaved head, hidden by the growth of his hair, and exposed by shaving his head again. The message allegedly carried a warning to Greece about Persian invasion plans. (This method has obvious drawbacks:

1. 1. It is impossible to send a message as quickly as the slave can travel, because it takes months to grow hair.
   2. A slave can only be used once for this purpose. (This is why slaves were used: they were considered expendable.)

• Hidden messages on paper written in secret inks under other messages or on the blank parts of other messages.
• During and after World War II, espionage agents used photographically produced microdots to send information back and forth. Since the dots were typically extremely small -- the size of a period produced by a typewriter or even smaller -- the stegotext was whatever the dot was hidden within. If a letter or an address, it was some alphabetic characters. If under a postage stamp, it was the presence of the stamp. The problem with the WWII microdots was that they needed to be embedded in the paper, and covered with an adhesive (such as collodion), which could be detected by holding a suspected paper up to a light and viewing it almost edge on. The embedded microdot would reflect light differently than the paper.
• More obscurely, during World War II, a spy for the Japanese in New York City, Velvalee Dickinson, sent information to accommodation addresses in neutral South America. She was a dealer in dolls, and her letters discussed how many of this or that doll to ship. The stegotext in this case was the doll orders; the 'plaintext' being concealed was itself a codetext giving information about ship movements, etc. Her case became somewhat famous and she became known as the Doll Woman.
• Counter-propaganda: During the Pueblo Incident, US crew members of the USS Pueblo (AGER-2) research ship held as prisoners by North Korea communicated in sign language during staged photo ops to inform the United States that they had not defected, but had instead been captured by North Korea and were still loyal to the U.S. In other photos presented to the US, the crew members gave "the finger" to the unsuspecting North Koreans, in an attempt to discredit the pictures that showed them smiling and comfortable. [6]
• The one-time pad is a theoretically unbreakable cipher that produces ciphertexts indistinguishable from random texts: only those who have the private key can distinguish these ciphertexts from any other perfectly random texts. Thus, any perfectly random data can be used as a covertext for a theoretically unbreakable steganography. A modern example of OTP: in most cryptosystems, private symmetric session keys are supposed to be perfectly random (that is, generated by a good Random Number Generator), even very weak ones (for example, shorter than 128 bits). This means that users of weak crypto (in countries where strong crypto is forbidden) can safely hide OTP messages in their session keys.

Additional terminology

In general, terminology analogous to (and consistent with) more conventional radio and communications technology is used; however, a brief description of some terms which show up in software specifically, and are easily confused, is appropriate. These are most relevant to digital steganographic systems.

The payload is the data it is desirable to transport (and, therefore, to hide). The carrier is the signal, stream, or data file into which the payload is hidden; contrast "channel" (typically used to refer to the type of input, such as "a JPEG image"). The resulting signal, stream, or data file which has the payload encoded into it is sometimes referred to as the package, stego file, or covert message. The percentage of bytes, samples, or other signal elements which are modified to encode the payload is referred to as the encoding density and is typically expressed as a floating-point number between 0 and 1.

In a set of files, those files considered likely to contain a payload are called suspects. If the suspect was identified through some type of statistical analysis, it may be referred to as a candidate.

Countermeasures

The detection of steganographically encoded packages is called steganalysis. The simplest method to detect modified files, however, is to compare them to the originals. To detect information being moved through the graphics on a website, for example, an analyst can maintain known-clean copies of these materials and compare them against the current contents of the site. The differences (assuming the carrier is the same) will compose the payload.

In general, using an extremely high compression rate makes steganography difficult, but not impossible; while compression errors provide a good place to hide data, high compression reduces the amount of data available to hide the payload in, raising the encoding density and facilitating easier detection (in the extreme case, even by casual observation).

Applications

Usage in modern printers

Main article: Printer steganography

Steganography is used by some modern printers, including HP and Xerox brand color laser printers. Tiny yellow dots are added to each page. The dots are barely visible and contain encoded printer serial numbers, as well as date and time stamps.

An example from modern practice

Image of a tree.
By removing all but the last 2 bits of each color component, an almost completely black image results. Making the resulting image 85 times brighter results in the image below.

Image extracted from above image.

The larger the cover message is (in data content terms — number of bits) relative to the hidden message, the easier it is to hide the latter. For this reason, digital pictures (which contain large amounts of data) are used to hide messages on the Internet and on other communication media. It is not clear how commonly this is actually done. For example: a 24-bit bitmap will have 8 bits representing each of the three color values (red, green, and blue) at each pixel. If we consider just the blue there will be 2⁸ different values of blue. The difference between 11111111 and 11111110 in the value for blue intensity is likely to be undetectable by the human eye. Therefore, the least significant bit can be used (more or less undetectably) for something else other than color information. If we do it with the green and the red as well we can get one letter of ASCII text for every three pixels.

Stated somewhat more formally, the objective for making steganographic encoding difficult to detect is to ensure that the changes to the carrier (the original signal) due to the injection of the payload (the signal to covertly embed) are visually (and ideally, statistically) negligible; that is to say, the changes are indistinguishable from the noise floor of the carrier.

From an information theoretical point of view, this means that the channel must have more capacity than the 'surface' signal requires, that is, there must be redundancy. For a digital image, this may be noise from the imaging element; for digital audio, it may be noise from recording techniques or amplification equipment. In general, electronics that digitize an analog signal suffer from several noise sources such as thermal noise, flicker noise, and shot noise. This noise provides enough variation in the captured digital information that it can be exploited as a noise cover for hidden data. In addition, lossy compression schemes (such as JPEG) always introduce some error into the decompressed data; it is possible to exploit this for steganographic use as well.

Steganography can be used for digital watermarking, where a message (being simply an identifier) is hidden in an image so that its source can be tracked or verified.

In the era of digital video recorders and devices like TiVo, TV commercials authors have figured out how to make use of such devices as well - by putting a hidden message which becomes visible when played at frame-by-frame speed (see KFC Unveils 'TiVo-proof' Ad).

Rumored usage in terrorism

When one considers that messages could be encrypted steganographically in e-mail messages, particularly e-mail spam, the notion of junk e-mail takes on a whole new light. Coupled with the "chaffing and winnowing" technique, a sender could get messages out and cover their tracks all at once.

Rumors about terrorists using steganography started first in the daily newspaper USA Today on February 5, 2001 in two articles titled "Terrorist instructions hidden online" and "Terror groups hide behind Web encryption". In July of the same year, the information looked even more precise: "Militants wire Web with links to jihad".

A citation from the USA Today article: "Lately, al-Qaeda operatives have been sending hundreds of encrypted messages that have been hidden in files on digital photographs on the auction site eBay.com". These rumors were cited many times—without ever showing any actual proof—by other media worldwide, especially after the terrorist attack of 9/11.

For example, the Italian newspaper Corriere della Sera reported that an Al Qaeda cell which had been captured at the Via Quaranta mosque in Milan had pornographic images on their computers, and that these images had been used to hide secret messages (although no other Italian paper ever covered the story).

The USA Today articles were written by veteran foreign correspondent Jack Kelley, who in 2004 was fired after allegations emerged that he had fabricated stories and invented sources.

In October 2001, the New York Times published an article claiming that al-Qaeda had used steganographic techniques to encode messages into images, and then transported these via e-mail and possibly via USENET to prepare and execute the September 11, 2001 Terrorist Attack.

The Federal Plan for Cyber Security and Information Assurance Research and Development [7], published in April 2006 makes the following statements:

• "... immediate concerns also include the use of cyberspace for covert communications, particularly by terrorists but also by foreign intelligence services; espionage against sensitive but poorly defended data in government and industry systems; subversion by insiders, including vendors and contractors; criminal activity, primarily involving fraud and theft of financial or identity information, by hackers and organized crime groups; ..." (p 9-10)

• "International interest in R&D for steganography technologies and their commercialization and application has exploded in recent years. These technologies pose a potential threat to national security. Because steganography secretly embeds additional, and nearly undetectable, information content in digital products, the potential for covert dissemination of malicious software, mobile code, or information is great." (p 41-42)

• "The threat posed by steganography has been documented in numerous intelligence reports." (p 42)

Moreover, a captured terrorist training manual, the "Technical Mujahid, a Training Manual for Jihadis" contains a section entitled "Covert Communications and Hiding Secrets Inside Images." A brief summary is provided by the Jamestown Foundation [8].

To date, over 625 digital steganography applications have been identified by the Steganography Analysis and Research Center [9]

See also

• Canary trap
• Covert channel
• Steganographic file system
• Deniable encryption
• Encryption
• Polybius square
• Security engineering
• Camera/Shy Stand-alone browser that automatically scans for and delivers decrypted content straight from the Web.

External links

Books

• [10] Disappearing Cryptography by Peter Wayner
• [11] Information Hiding - Techniques for Steganography and Digital Watermarking edited by Stefan Katzenbeisser and Fabien, A.P. Petitcolas
• [12] Information Hiding: Steganography and Watermarking - Attacks and Countermeasures by Neil F. Johnson, Zoran Duric, and Sushil Jajodia

Steganography articles

• QuickStudy:Steganography: Hidden Data at computerworld.com
• Steganography Articles, Links, and Whitepapers at Forensics.nl
• Examples showing images hidden in other images
• FBI Article: An Overview of Steganography for the Computer Forensics Examiner
• Cryptography and Steganography (web version of PowerPoint slides), 2002. Elonka Dunin's presentation of an overview of steganography, as well as a discussion of whether or not Al Qaeda might have been using steganography to plan the September 11th, 2001 attacks
• Steganography & Digital Watermarking - papers and information related to steganography and steganalysis research by Neil F. Johnson from 1995 to the present.
• Detecting Steganographic Content on the Internet, 2001. Paper by Niels Provos and Peter Honeyman, Center for Information Technology Integration, University of Michigan
• Rights Protection for Natural Language Text, includes several articles on this topic
• Network Steganography, includes articles on network steganography (Wireless LANs and VoIP).
• Steganography, Steganalysis, and Cryptanalysis BlackHat and DefCon presentations by Michael T. Raggo (aka SpyHunter)

Steganalysis

• Steganography Analysis and Research Center (SARC) A Backbone Security Center of Excellence providing tools for steganography detection and extraction as well as steganography examiner training.
• Steganalysis papers on attacks against Steganography, Watermarking and Countermeasures to these attacks.
• Cyber warfare: steganography vs. steganalysis For every clever method and tool being developed to hide information in multimedia data, an equal number of clever methods and tools are being developed to detect and reveal its secrets.
• "Detecting Steganographic Content on the Internet", PDF file, 813 KB.
• Some sample pages of Gaspar Schott's Schola steganographica
• Research Group An example of ongoing research on Steganography.
• StegDetect A tool to automatically find hidden messages in images.
• StegSpy A tool that will detect hidden messages and the steganography program used to hide the message.
• Analyzing steganography applications: Practical examples on how some steganography software works, and how many of them are crackable.

Implementations

Online (Hiding text)

• mozaiq Has a large library of stock photos it provides if you can't supply a photo of your own. A good starting point for creating simple steganographic examples.
• spammimic.com will take a sentence that you provide and turn it into text that looks to all the world like spam.

Online (Hiding files)

• Stegger, PHP Steganography - PHPClasses Repository - An open source, feature rich, secure implementation of image steganography written in PHP.

Downloadable (Hiding text)

• Bapuli Online - implementing steganography using Visual Basic.
• BitCrypt BitCrypt is one of the easiest to use encryption tools which at the same time provide ultra-strong encryption. It uses up to 8192 long bit key ciphers to encrypt the text, and then stores the encrypted text within bitmap images.

Downloadable (Hiding files)

• Hiding Glyph: Bytewise Image Steganography: Hides any file (or folder) into any losslessly compressed image (BMP, PNG, etc...). (freeware)
• BestCrypt Commercial Windows/Linux disk encryption software that supports hiding one encrypted volume inside another
• Crypto-Stego Utility for the Zillions of Games program.
• Digital Invisible Ink Toolkit An open-source cross-platform image steganography suite that includes both steganography and steganalysis implementations.
• FreeOTFE Free, open-source Windows/PocketPC/Linux disk encryption software that supports hiding one encrypted volume inside another, without leaving any evidence that the second encrypted volume exists. This probably resists any statistical analysis (as opposed to tools that conceal data within images or sound files, which is relatively easy to detect).
• MP3 Steganographic File System, a description of an approach to create a file system which is implemeted over MP3 files.
• OutGuess A steganography application to find data in Jpeg images.
• PCopy A steganography commandline tool with a userfriendly wizard which can produce lossless images like PNG and BMP. Special features are RLE, Huffman compression, strong XOR encryption and the Hive archiving format which enables the injection of entire directories.
• Phonebook FS protects your disks with Deniable Encryption
• RevelationA platform independent tool created in Java that can hide any data file within a 24-bit bitmap image. Features a unique wizard style interface in the encoding and decoding process.
• stego and winstego Steganography by justified plain text.
• Stego-0.5, a GNOME/GTK+ based GUI for LSB algorithm. License (GPL)
• Stego Archive Source for a large variety of steganography software.
• Steghide Free .jpeg and .wav encryption for Linux and other operating systems.
• SteGUI Free GUI for Steghide for Linux.
• TrueCrypt Free, open-source Windows/Linux disk encryption software that supports hiding one encrypted volume inside another, without leaving any evidence that the second encrypted volume exists. This probably resists any statistical analysis (as opposed to tools that conceal data within images or sound files, which is relatively easy to detect).
• Peter Wayner's website - sample implementations of steganographic techniques, by the author of Disappearing Cryptography.
• NetTools Steganography by hiding data in pictures, archives, sounds, text files, html, and lists.