Finding and decoding that secret message in encrypted text has lured treasure seekers over the high seas and readers by the thousands to the “Da Vinci Code.” Far less romantic, but infinitely more common and destructive, are the hidden messages embedded in computer documents and pictures that the sender never knows about.
The U.S. military suspects such cyber marks as potential conduits for terrorist plans, although none yet have been unearthed. Civil liberties groups fear, with somewhat more evidence, that governmental agencies use embedded marks to illegally spy on citizens. Some cases of encryption, of course, are perfectly legal, e.g. hidden marks on rented DVDs preventing their unlawful reproduction. Whatever the use, the art of unseen encryption has proliferated exponentially both in technology and occurrence over the last decade. With it has emerged the field of steganography — the art/science of detecting such messages — by experts like Jessica Fridrich, professor of electrical and computer engineering at SUNY Binghamton.
Fridrich’s presentation “Steganalysis by Subtractive Pixel Adjacency Matrix,” joins those of other steganographic authorities as just one topic in the ACM workshop on multimedia and security on Monday and Tuesday, September 7 and 8, beginning at 8:30 a.m. at Princeton University’s Friend Center Convocation Room in Princeton. Cost $385. Visit www.mmsec.nfhost.com.
Fridrich claims to have always had a love for numbers and games. Growing up in Ostrava, an eastern city in the Czech Republic, she caught her love of things technical from her father. Attending the Czech Technology University, she graduated with a bachelor’s in mathematics in 1987. Seeking to complete her graduate studies in the United States, she came to the T.J Watson School of Applied Science in SUNY Binghamton’s electrical and computer engineering department.
Upon earning her computer science Ph.D., Fridrich stayed on at her alma mater as an active professor and researcher. Her work in all kinds of authentication, tamper-detection, and steganography has been funded by the U.S. Air Force. “I’m not really sure what they want to use all my findings for,” Fridrich says. Her latest book, “Steganalysis and Visible Images — Principles, Algorithms, and Applications,” comes out this October.
Forget the Hollywood-style microdots that betray our Iraq invasion plans in a single printed period. Today’s encryptions can magnetically piggyback onto any Internet image or missive and be interpreted up at any stop or any computer hard drive. No need to hijack the website or break into the E-mail. Like most computer functions, even a child can perform it.
Embedding 101. It is this user-friendliness that has fused the explosion of encryptions and embedded messages. “I have grad students who have never tried it before, and within a day, they have embedded amazingly untraceable messages,” says Fridrich. If the would-be embedder does not have a grad student handy, more than a dozen websites stand at the ready to guide him step by step through his first implant.
Most favored and easily transcribed is the Least-Significant-Bit Embedding process (LSBE). This method tweaks the algorithms (directional flow charts) that govern the pixels’ color in a certain image. All directions guiding a computer function are given in binary code — either 1 or 0 (zero). To provide an image with color contrast, each pixel is weighted with a specific light intensity. That intensity is assigned a numeric value so it may be transferred across cyberspace and rebuilt on the receiving screen exactly as transmitted. The embedder merely makes the least significant shift in the color algorithm between the pixel instructions originally sent and those received.
The human eye cannot detect any anomaly in the image, but the succession of implanted patterns can actually spell out a definite message to the recipient with the right software. “These changes are all streamed along into the image by very rapid programs,” says Fridrich, “so there is not enormous time or labor to encode.”
Techie Detecting. Least Significant Bit Embedding leaves a trace, or artifact, as stegnographic gurus call them. “There is a certain symmetry, and laws of change that in themselves become a pattern,” says Fridrich. For example an original message beginning with a binary 5 (11111) may be changed to binary 6 (000000), but it may not be changed to a seven or nine. It must change to its nearby higher even number.
Now, all Fridrich has to do is develop a mathematical algorithm that hunts for a predominance of such changes and applies it through the full four megapixels of a digitalized image. The hours crouched over the computer gradually, brilliantly bear fruit. The artifact-discovery program she invented may run through and verify a full image within minutes.
Yet as detection steps ahead, embedding also adds another layer of sophistication. Recently, more difficult programs have been invented that can defy the LSBE symmetry rules. “The trick to catching these guys is that they get greedy,” Fridrich says. “Normally you can embed up to 10,000 bits of information in a 4 megapixel image undetected. But you’d be amazed with what some of these people try to get away with.”
While active clients, the military and intelligence groups are no longer the sole employers of Fridrich’s rarefied expertise. Law enforcement now seeks such secret decoding software. Likewise, businesses fearing espionage have become ever on guard against encoded cyberleaks. Such preventative complexities are all part of the price of progress. Since the invention of the first lock and lock pick, ’twas ever thus.