Steganography and Steganalysis: Hiding Data in Plain Sight, and How to Find and Eliminate It

Steganography and Steganalysis : Hiding Data in Plain Sight, and How to Find and Eliminate It

Steganography , literally "secret writing," is the science of developing and/or applying techniques for concealing one message within another. In its earliest form, it was a highly popular diversion in the form of mind games , with writers encoding the answer to puzzles within the puzzle itself, or signing anonymous poems with a steganographically hidden signature.

One famous example, Hypnerotomachia Poliphili , is a curious work of fiction from 1499 that blends a treatise on architectural and landscape design with political theory and erotica in a dreamscape setting where the protagonist wanders, in search of his love Polia. The book is left without any identified author (though some ascribe it to Leon Battista Alberti, a contemporary author of architectural theory), but if one takes the illuminated letter from the beginning of each chapter, one finds the sentence " Poliam frater Franciscus Columna peramavit ." MIT makes the manuscript available at http://mitpress.mit.edu/e-books/HP/hyp000.htm, including, conveniently, the illuminated headletters as indices to the chapters. David Kahn, in "The Codebreakers: The Story of Secret Writing," notes that this translates as "Brother Francesco Colonna passionately loves Polia." Francesco Colonna was a Dominican monk, still alive when the book was published, lending some credence to the thought that he might have wished such a work to be published anonymously.

Another example, perhaps more interesting, though currently thought of as infamous rather than famous, concerns the apparent lack of solid historical evidence for the author known as Shakespeare. There has long been a contention that the William Shakspere, or Shaxpere, Shagspere, Shackspere or Shakspre (depending on which of the various legal documents of the time you might guess to contain his real signature, if any of them do) of Stratford-on-Avon, with regards to whom a few concrete historic documents exist, is not the same Shake-speare who wrote "Shakespeare's" Sonnets (this is the way the Sonnets are attributed in their original printing ”with a hyphenated name ). Curiously, there are a number of good arguments that suggest that the Shakspere recorded in the historical documents was illiterate. One of the best of these was put forward by Sir Edward Durning Lawrence (http://www.sirbacon.org/edllibrary.htm) in his treatise "The Shakespeare Myth" (http://home.att.net/~tleary/sigs.htm). There is simultaneously an abundance of suggestions, though whether by way of coincidence or intent it cannot be said, that Sir Francis Bacon may have in fact been the author (http://www.sirbacon.org/links/evidence.htm). Included among these is the fact that Bacon considered Pallas Athene (Athena, the "Spear Shaker") to be his muse. Recently, and rather controversially, there has been discovered what appears to be a steganographically encoded cipher in the title page and dedication to the Sonnets . Deciphered, the message reads "nypir cypphrs bekaan bacon" ("The Second Cryptographic Shakespeare," Penn Leary, Weschesterhouse Publishers, also http://home.att.net/~mleary/pennl10.htm). As spelling was mostly a phonetic exercise at the time, and not bound by today's absolute rules, the curious spellings are possibly excusable. It should be noted that John Napier (also Napeir, Nepair, Nepeir, Neper, Napare, Napar, and Naipper, depending which documents of his you read) is a contemporary of Bacon who developed the notion of mathematical logarithms, and that Bacon was fascinated with cryptology and steganography, and the possibilities that Napier's mathematical ideas brought to these fields.

More currently, steganography has made its way into the world of high-tech watermarking, where its goal becomes not simply the hiding of some message, but doing it in such a way that even if the original is altered , the message can still be detected . The primary driving force behind this move is the proliferation of digital forms of many types of media, such as audio, video, and still imagery. Artists and copyright holders are concerned that these items can be easily duplicated , depriving them of the rights and royalties to which they are legally due. In response, companies tried to solve this problem by finding ways to embed digital signatures and watermarks into digital media. With sufficient industry cooperation, the hardware and software was designed so that the watermarks can be detected, and the media rejected as an invalid file to copy, tape to duplicate, or CD to record.

Contrary to popular belief, these actions aren't specifically abridging consumer rights. They may be making exercise of certain rights more difficult, but the widely held belief that it's legal to copy one's CD if one doesn't sell it to someone (that is, "for personal use"), isn't upheld by what the laws actually say (U.S. Code, Title 17, http://www4.law.cornell.edu/uscode/17/). The law says that the copyright holder has the exclusive right to make and authorize copies (U.S. Code, Title 17, Chapter 1, Section 106, http://www4.law.cornell.edu/uscode/17/106.html). It makes no exception for "personal use." A number of people wave the flag of the "Fair Use" doctrine as supporting their claim that personal use is acceptable under the law, but they are either ill-informed, or deliberately attempting to confuse the issue. Fair Use (U.S. Code, Title 17, Chapter 1, Section 107, http://www4.law.cornell.edu/uscode/17/107.html) provides for certain conditions under which the copyright holder's rights may be circumvented without the use being against the law. These include a number of very specific cases where the circumvention is allowable , such as for satire , political commentary , to provide educational material in a classroom setting, or to use the work as a reference in a critique. None of these apply, or come anywhere near applying to copying a work for one's personal convenience. Thankfully, penalties for violation of a copyright holder's rights are based largely on the potential revenue lost due to the action of the violator (U.S. Code, Title 17, Chapter 5, http://www4.law.cornell.edu/uscode/17/ch5.html), so it appears unlikely that publishing houses are going to invest in the legal expenses necessary to recover the $12 one might have deprived them of by copying a CD. In response to this, many companies are endorsing technologies that allow consumers to make a single copy of a digital original, but that prevent subsequent copying of the copy.

Unfortunately, the large corporate publishing concerns that have purchased most of the copyrights to valuable contemporary commodities have seen this as such a large threat that they have railroaded a number of bad laws through the U.S. government, putting legal barricades in place against consumers exercising rights that are clearly granted to them by other sections of the U.S. code. Chief among these poorly thought-out packages of legalese is the act known as the DMCA ”the Digital Millennium Copyright Act (U.S. Code, Title 17, Chapter 12, Section 1201, and other sections, http://www4.law.cornell.edu/uscode/17/1201.html). Among the ludicrously anticonsumer ideas put into law by this boondoggle is a section that makes it illegal to "traffic in" any technology (that is, "invent, discuss, etc.") that is primarily useful for circumventing a technological measure put in place to control access to a work.

When coupled with the fact that the copyright for any material work you create and fix in some medium automatically belongs to you from the moment of creation (though the copyright is not registered), the result is that if any technology is used to protect any work you create (encrypted email, for example), it immediately becomes illegal for anyone to "traffic" in any technologies that could circumvent that protection. Put another way, at the moment some technology is first used to protect any copyrighted work, it thenceforth becomes illegal for anyone to examine the protections in that technology, attempt to break it, improve it, or even discuss it.

The upshot of this is that some lawyer out there would probably throw a hissy fit if we were to tell you much at all about the field of steganalysis , which is the study of ways to find and eliminate such watermarking or protection from works. At least one academician, a professor from Princeton has already been threatened with legal action if he published a paper on a flaw he discovered in an encryption algorithm (http://www.cs.princeton.edu/sip/sdmi/announcement.html, http://www.cs.princeton.edu/sip/sdmi/riaaletter.html, and http://www.cs.princeton.edu/sip/sdmi/sdmimessage.txt), and several Web sites have been successfully sued, forcing them to remove any mention of security holes that have been found in other products (http://www.2600.com/news/display/display.shtml?id=378). The silliness has even extended to some companies suing others over links being placed to their Web sites, claiming that bypassing their front page by pointing a visitor directly to interesting internal content was circumventing their ability to properly indoctrinate the visitor with the information from the earlier higher pages and thereby "defeating a technological measure protecting a work" (http://www.internetnews.com/bus-news/article.php/3_1138351, http://www.salon.com/tech/col/rose/1999/08/12/deep_links/, and http://www.dontlink.com/). Perhaps most informative of the ulterior motives in these cases, the legal beagles in at least one of the cases likened the practice to "changing the channel, or using a VCR to skip over commercials in broadcast television," as such use of a VCR was clearly a violation of the broadcaster 's right to earn revenue.

Many of the major software and hardware manufacturers are jumping on the bandwagon to implement methods to force the consumer to adhere to these laws (and to make it that much more illegal for the consumer to circumvent them). Microsoft recently demonstrated an audio watermarking technology that embeds an audio watermark into music so solidly that the watermark can still be detected and recording prevented even if the source is being played aloud in a crowded room, and the recording is attempted from this "live" source (http://slashdot.org/features/01/05/03/2043244.shtml, http://www.wired.com/news/print/0,1294,43389,00.html). See where this is going? Personally, we prefer the Tivo to the VCR, but they want to keep us from skipping commercials by making it illegal? Thank whatever God or gods you believe in for the hackers, the crackers, and the company that said "1984 won't be like 1984"! Apple has thus far stood impressively far from the crowd in their refusal to implement such anticonsumer technologies in their products, appearing at this point to be comfortable with allowing their customers to be responsible for their own actions, rather than treating them like a- priori -criminals.

Perhaps the saddest outcome, however, is that the application of the law has risen to the level of absurdity that cryptology and steganography experts were predicting much faster than ever predicted . It is now illegal to possess a certain prime number, as that prime number happens to be related in an interesting fashion to a method of breaking the particularly poor encryption that was ill-advisedly employed by the DVD consortium to protect DVDs from copying, who apparently expected that they could pull an algorithm out of thin air and have it remain secure. The following number is not a prime (we don't want to get in trouble by possessing or distributing an illegal number), but there's an interesting prime near it that can be decoded into a crack for the DVD encryption algorithm. If you'd like to see how hard that prime-number factoring business that we discussed earlier in this chapter really is, you can see whether you can figure out what the prime is with a few well- chosen guesses. It's only 1401 digits ”shouldn't be that hard...

 4 8565078965 7397829309 8418946942 8613770744 2087351357 9240196520 7366869851 3401047237 4469687974 3992611751 0973777701 0274475280 4905883138 4037549709 9879096539 5522701171 2157025974 6669932402 2683459661 9606034851 7424977358 4685188556 7457025712 5474999648 2194184655 7100841190 8625971694 7970799152 0048667099 7592359606 1320725973 7979936188 6063169144 7358830024 5336972781 8139147979 5551339994 9394882899 8469178361 0018259789 0103160196 1835034344 8956870538 4520853804 5842415654 8248893338 0474758711 2833959896 8522325446 0840897111 9771276941 2079586244 0547161321 0050064598 2017696177 1809478113 6220027234 4827224932 3259547234 6880029277 7649790614 8129840428 3457201463 4896854716 9082354737 8356619721 8622496943 1622716663 9390554302 4156473292 4855248991 2257394665 4862714048 2117138124 3882177176 0298412552 4464744505 5834628144 8833563190 2725319590 4392838737 6407391689 1257924055 0156208897 8716337599 9107887084 9081590975 4801928576 8451988596 3053238234 9055809203 2999603234 4711407760 1984716353 1161713078 5760848622 3637028357 0104961259 5681846785 9653331007 7017991614 6744725492 7283348691 6000647585 9174627812 1269007351 8309241530 1063028932 9566584366 2000800476 7789679843 8209079761 9859493646 3093805863 3672146969 5975027968 7712057249 9666698056 1453382074 1203159337 7030994915 2746918356 5937621022 2006812679 8273445760 9380203044 7912277498 0917955938 3871210005 8876668925 8448700470 7725524970 6044465212 7130404321 1826101035 9118647666 2963858495 0874484973 7347686142 0880529442

As mentioned earlier, the only way to develop secure algorithms is by subjecting them to constant and vigorous public scrutiny. The end result of this critically flawed law will be that we, the consumers, are going to be forced to accept much poorer quality encryption software to protect our data, while the criminal element that would circumvent the protections for profit will have it much easier, as the algorithms will have not been subjected to rigorous academic review.

Mac OS X Steganography Products

At this point, there isn't much software out there to allow you to experiment with steganography, but you can expect that there will be more toys coming, as the battle heats up between corporate interests trying to protect their right to a profit and the hackers interested in advancing the arts of cryptography and steganography. In the meantime, you can examine a few interesting (or in one case, at least amusing) products if you're interested in experimenting a bit, or using steganographic techniques to conceal textual data.

Adobe's PhotoShop includes a pair of filters named Digimarc "Embed Watermark" and "Read Watermark," which respectively embed a copyright statement into an image as a watermark or decode it again.
Precious Gem software distributes Corundum (http://preciousgem.dnsalias.com:90/PreciousGem/Corundum/Corundum.html), which allows you to steganographically hide textual information in images.
Spam Mimic (http://www.spammimic.com/index.shtml) provides the steganographic service of hiding short text messages in email that looks like spam. Nobody looks at spam email, right? Where better to hide something than in a plain-sight email transmission, that people will do their best to avoid seeing?

These products conveniently display complementary features. The purpose of the PhotoShop filter is to allow watermarking images so that the copyright information is indelibly embedded in the image. This is an attempt to provide for some way of proving that commercial digital images are copyrighted, so that, for example, as images are snagged off of a Web site and transferred around the Internet, the ownership information remains with the file. The copyright watermark embedded by Digimarc is immune to most simple transformations of the image: Cropping it, rotating it, mirroring, skewing, mild blurs, noise, and most other simple adulterations won't erase the watermark. Unfortunately, in a brilliant display of what we've been repeating about security not being secure unless it's open , tested , and verified , the Digimarc/PictureMarc system is tragically flawed in its ability to actually secure an image. As Fabien Peticolas demonstrates at http://www.cl.cam.ac.uk/~fapp2/watermarking/index.html, it takes only a few minutes of brute-force attempts against PictureMarc 1.51 images to guess the code necessary to remove or modify the original watermark and replace it with one of your own. Trying to eradicate it through the use of image manipulations probably takes longer.

The Corundum application, on the other hand, is designed with the intent of embedding information so that it can't be found, but not so that it can't be damaged by modifying the image. We'd show you before and after images of what things look like with the data encoded into them, but there's really little point ”to the limits of reproduction in this book, the images with data encoded into them are indistinguishable from the originals . While you're waiting for some of the two dozen or so steganography projects underway on Sourceforge to make their way to the Mac, you might want to check out the Web pages of Johnson and Johnson Technology Consultants, who have published and provided some very nice papers on steganographic techniques, steganalysis, and the current state of the art at http://www.jjtc.com/Steganography/. Specifically, Niel F. Johnson's papers (http://www.jjtc.com/stegdoc/steg1995.html and http://www.jjtc.com/pub/nfjidr99.pdf) should be interesting to those considering how this technology might be either helpful or damaging to their computing security.

Spam Mimic, by way of comparison, doesn't try to so hard to encode the information in an invisible fashion, as to make the carrier so common and ugly that no one will give it a second look. If you enter a short message such as the following:

 Hi Joan, I'll be home by 5:30.

You'll be presented with a result that you can email that starts off:

 Dear E-Commerce professional ; This letter was specially selected to be sent to you . This is a one time mailing there is no need to request removal if you won't want any more . This mail is being sent in compliance with Senate bill  1624 , Title 2 ; Section 304 ! This is different than anything else you've seen ! Why work for somebody else when you can become rich within 57 WEEKS...

Who's going to bother looking at that to see whether it has interesting information in it?

Although it's not available for Mac OS X yet, another application you might want to keep an eye out for is Hydan from Columbia University student Rakan El-Khalil. SecurityFocus reports that at a small computing security conference held in February 2003, Rakan demonstrated an application that uses other executable applications as a place to hide information (http://www.securityfocus.com/news/2623). Cleverly, this application does not hide the information by stuffing it into unused nooks and crannies in the executable, but instead by subtly modifying the way that the executable host performs its calculations, and thereby using the code of the application itself as the carrier for the hidden information.

Top