St. Louis Post-Dispatch August 12, 2003 Picture this: Technology lets you hide information inside an image By Angela Vierling (Reprinted with permission from the St. Louis Post-Dispatch) You are looking through a big box of photographs that you meant to put into albums long ago. Here's a snapshot of your family smiling in the woods. Was this your trip to Shawnee National Forest in 1995? Imagine never having to wonder again. Imagine you scan the photo into your computer and the computer reads information hidden in your photograph: Mark Twain National Forest, July 16, 1996. Oh, you'd forgotten that trip! Welcome to the emerging field of "information hiding." In addition to hiding dates and locations in photographs, the technology has applications for business and national security. While private industry funds most of the commercial development, researchers at Washington University, the University of Illinois at Urbana-Champaign, and other schools are making important theoretical advances in the field. Watermarking is an ancient type of information hiding. If you hold up a $5 bill to the light, you'll notice that, to the right of the printed image of Lincoln on the bill's front, there is a smaller image of Lincoln watermarked into the bill. The Lincoln watermark can help you distinguish a real bill from a counterfeit. Similarly, digital watermarks can identify the owner or authenticity of an image or document. Digital watermarks are invisible, and computer programs can erase or alter them. Ed Delp, a professor of electrical and computer engineering at Purdue University, has been working on digital watermarking for about eight years. Within 10 years, he says, it's possible that "any kind of media content that you personally did not create will be digitally watermarked. ... A boarding pass you get on an airplane will have a watermark." In a type of information hiding known as "steganography," secret information is hidden so that it can be passed from person to person without arousing suspicion. For instance, the question "Is Stacy planning your aunt's silly escapade?" hides the message "St. Louis" if you know to look at the second letter of every word. During World War II, the Nazis hid technical drawings and other information in innocuous messages by shrinking them down to the size of a printed period, called a microdot. In 2001, seven months before the terrorist attacks of Sept. 11, USA Today reported that, according to unidentified sources, Osama bin Laden was hiding terrorist plans in pictures on pornographic and other Web sites. To date, there has been no evidence of al-Qaida's hidden messages. However, steganography programs are available to anyone on the Web. The possibility of terrorists using steganography to pass messages is still real, although its use may not be widespread. Niels Provos, a Ph.D. candidate at the University of Michigan, developed a computer program that searched millions of images on the Web looking for secret messages but failed to find any. "That we did not find anything is an indication that there is no widespread use of steganography in general," he said in an e-mail interview. As the field of information hiding has developed, people have come up with strategies to detect and reveal hidden messages. Until now, no one has known the maximum amount of information that could be hidden in an image or document without the data being discovered. When new techniques for concealing information come out, the only way to test their effectiveness has been for others to try to attack them. Joseph O'Sullivan of Washington University and Pierre Moulin of the University of Illinois are working to fix that. The researchers have established limits on the amount of information that can be hidden, as well as general guidelines for effectively hiding and recovering information. Their research was in the March 2003 Transactions on Information Theory published by the Institute of Electrical and Electronics Engineers. Delp, at Purdue, says O'Sullivan and Moulin's research, although abstract, is important to the field. "It will tell you what the ultimate performance of these watermarking techniques can be." O'Sullivan and Moulin used a branch of mathematics called "game theory" to analyze information hiding techniques. "We view this problem as a game played between an information hider and an information attacker," said O'Sullivan. In a casino game such as blackjack, the player is trying to maximize the payoff and the dealer is trying to minimize it. It is possible to mathematically determine the payoff value of blackjack - the amount a person should expect to win playing blackjack repeatedly over time. O'Sullivan and Moulin determined the payoff value of the information hiding game, which is a measure of how much information can be hidden. In this game, the hider is trying to maximize the payoff and the attacker is trying to minimize it. The researchers were the first to calculate the payoff value and show how much data can be reliably hidden. O'Sullivan is careful to note that the data hider may be a "good guy," as in the case of a photographer wanting to preserve rights to a photograph, or a "bad guy," such as a terrorist operative. The game is played the same in either case, and the same limits hold. "Just as the laws of physics cannot be violated, our bounds can never be improved upon," said O'Sullivan. Reporter Angela Vierling Research by Angela Vierling and Anne Wickersham Copyright 2003, St. Louis Post-Dispatch, Inc. (To see the St. Louis Post-Dispatch online, go to http://www.stltoday.com)