(source)

Cracking the Code of a CIA Sculpture By John Schwartz
Washington Post Staff Writer
Monday, July 19, 1999; Page A01 It had reached the point that David Stein was seeing the letters in his head before drifting off to sleep at night. Arrayed in seemingly meaningless order on the copper sides of “Kryptos,” an oddly powerful sculpture at the headquarters of the Central Intelligence Agency, they had guarded a secret since the artwork was dedicated in October 1990.

The 865 characters on the sculpture are only about as many as appear in the first dozen or so paragraphs of this article. But, placed there as a whimsical challenge, they have stumped and obsessed cryptographers around the world for nearly a decade.

“Kryptos” rests in a courtyard in the agency’s closely guarded campus. The dense matrix of letters runs across a curving verdigris scroll that emerges from a column of petrified wood. There is a small, water-filled basin with other stones laid around, creating a quiet setting that encourages contemplation.

Stein, an intense physicist who works in the CIA building, rarely walked outside to look at it. He had written out the garbled message and played with the arrangements of the characters in his spare time, putting them through different combinations and waiting for hard work and intuition to give him a breakthrough.

And then, after more than 400 hours of brainwork, he realized he’d begun to crack it.

The letters were lining up, making sense. “I’d have to call it like a religious experience,” he recalls.

Stein’s epiphany came in February 1998, and within months he had cracked all but the last, 97-character passage on the sculpture, which hide behind an even tougher cryptographic system. His feat got little attention outside the CIA at the time. But when another amateur codebreaker, California computer scientist Jim Gillogly, stepped forward recently to announce on the Internet that he had made sense of all but those same 97 characters, Stein’s accomplishment also came to light.

On its face, the quest for its meaning is merely a nerd game. But on a deeper level, it’s about the deep human urge to solve puzzles, to learn secrets – to prove you’re smart. Never mind that the CIA offered no reward, set up no rules and put the sculpture in an area off-limits to the public.

Taking a Dual Approach

The two cryptographers now are playing out a modern-day John Henry legend, man against machine. Stein accomplished the feat with pencil and paper alone,the method preferred by the traditionalist creators of “Kryptos.” Gillogly has taken a high-tech approach, supplementing his analytical skills with computer programs of his own design. The National Security Agency confirms that three of its cryptographers, working on their own time, also have gotten to the same point in cracking the message, but declines to identify them or give details.

The story of this composition in copper, stone, water and code begins in the late 1980s, when the General Services Administration was looking for art to grace public buildings around the nation, including CIA headquarters in McLean.

Washington sculptor James Sanborn, whose work often deals with mystery and hidden forces of nature, jumped at the chance to do a sculpture for the intelligence agency. He proposed an artwork that contained its own puzzle, and the agency quickly agreed. He had done research into cryptography, but wanted help coming up with an encryption method. He recalls thinking over his options: “Maybe the Israelis. Maybe the Russians? Just go over to the embassy – wouldn’t they love that?”

Ultimately, he went to the CIA itself. The agency put him in touch with Ed Scheidt, the retiring chairman of its Cryptographic Center, and hailed by then-director William Webster as “The Wizard of Codes.” A quiet, professorial man who favors ties with hieroglyphic patterns, Scheidt spent four months devising the systems that Sanborn would use.

For Scheidt, the project presented a chance to teach, not just Sanborn, but those attempting to break the puzzle as well. “I could use methods to encrypt it that had a historic basis – that didn’t compromise any current methods” of cryptography used by the government, Scheidt says. Sanborn and Scheidt wanted “to make something that could eventually be deciphered or extracted, rather than something that will never be done, ever,” Scheidt says.

With the code system in hand, Sanborn set to encrypting the message he had chosen for his artwork. He did it on his own, during a four-day jag trucking the huge piece of petrified tree from Arizona for the sculpture.

When he dedicated the completed work, Webster called “Kryptos” something that “speaks to a sense of place.” He told Sanborn, “You have captured much of what this agency is about.”

Scheidt figured that the first chunks of the puzzle would stand a few years; the last part, perhaps ten. He didn’t know his own strength.

Labor of Love

Over the next eight years, Sanborn said, he was contacted repeatedly by amateur code-breakers hoping for advice, a clue, anything. “About every couple of months, sometimes more somebody would call me up. … I had nothing whatsoever to do with any of these people,” he said with disdain.

Some were working from photographs, but Sanborn had placed the stones around the sculpture strategically, so that a photo could not capture all of the elements. Transcriptions of the letters had begun floating around the Internet, but most of them did not fully show the slight misalignment of some letters along the matrix, which might figure in unlocking the secrets.

Stein, now 38, had barely noticed the sculpture in its first years. A puzzle-solver at heart, he’d never had much interest in cryptography. But friends suggested he give it a look, and he read a small shelf of books on the subject.

Gillogly was at work too. “The first step is to go at it with a mindset that it’s going to be breakable,” he recalls. “The second step is to go at it ’til you get something.”

Both men quickly realized Scheidt’s underlying goal: “the sculpture is, in some sense, a history of cryptography,” noted Gillogly, a past president of the American Cryptogram Association.

The first two sections, they found, are based on a system of tables similar to methods attributed to 16th Century French cryptographer Blaise de Vigenere that substitutes letters throughout a message, shifting from one alphabet order to another with each letter. The third section uses another of the great historic cryptographic schemes: transposing letters, or changing their position in the message according to an ordered plan.

Language Patterns Emerge

Much of the initial work involves counting the occurance of each letter and performing a statistical analysis on those counts, since many crypto-systems reflect the patterns of language. The letter E is simply going to occur more often than other letters – roughly 130 times for every thousand letters, in fact – and that frequency can help a codebreaker begin to determine how the letters have been scrambled.

Stein and Gillogly (he has never actually seen the sculpture, relying on transcriptions) went through hundreds of false starts. They tried one approach after another, getting gibberish as a result.

Stein worked things out in his head, analyzing avenues of attack and then writing out the results, one test after another. “There’s probably a thousand things to do – I probably did 900 of them,” he recalls with a sheepish smile.

Gillogly would use a similar process of thinking up the attack, but left the trial and error work to his PC. The machine didn’t do the thinking; it merely eliminated drudgery, Gillogly argues. “It’s very easy to say, ‘Throw one of the … NSA supercomputers at a problem and it will be solved.’ ” But “computer programming and computer solving are not as easy as that … there was quite a lot of skull work.” Just as Stein was comfortable with pad and pencil, “I think best with a computer in my hands,” Gillogly says.

Of the two, Gillogly is more representative of today’s codebreakers, who tend to be computer-savvy and Internet-wired, constantly communicating with others in the idiosyncratic crypto community of mathematicians, computer scientists, academics and cranks. Stein, on the other hand, doesn’t even have an e-mail account.

Stein says he would drop the problem during periods of intense work, or when he was doing the final work on his masters degree. But he always came back, “Sunday afternoons, things like that,” keeping detailed notes of his attempts. “It’s sickening, but it gets to the point that you’re lying in bed and playing with this in your mind,” Stein says. “That’s the ‘get a life’ part, I guess.”

Close to a Breakthrough

Then in February 1998, “I felt I was close to it … It’s hard to describe the feeling of the breakthrough.” On a hunch, he was working from the assumption that the first letters of the passage he focused on were “T” and “H,” for “the.” He had been hashing and rehashing letter sequences to find the alphabets that were being substituted for the original message. The letters “T” and “H” finally lined up properly. There were still several thousand potential combinations to work through to get the rest of the letters, but “suddenly, at this point, I clearly saw the right path.”

“I actually had a hard time calming down enough to proceed,” Stein recalls. (As it turned out, that first word was “They,” not “The” – a lucky coincidence that still allowed Stein to move forward.) When he actually had completed the passages, Stein recalls, “I was a little disappointed. … It was like [finishing] a good book.”

Stein told friends about his partial success, and they suggested that he conduct a briefing. Stein agreed, and prepared quite a few viewgraphs, even though he expected perhaps 30 people to show up. In fact, once word got out that the puzzle had been largely cracked, the event had to be moved to an auditorium; some 250 people showed up. “Ed came up to me after the briefing,” Stein recalls, “and said ‘the solution is correct, but you didn’t do it in the way I intended you to do it.'”

The answer? In some ways, it as mysterious as the rest of the puzzle. The first passage reads: “Between subtle shading and the absence of light lies the nuance of iqlusion. ” Sanborn, it turns out, introduced a few misspellings to throw the codebreakers off the scent.

The second part contains a veiled reference to former CIA chief Webster; Sanborn gave Webster the key to deciphering the message, and the agency suggests but won’t confirm that it has been passed from director to director since. The passage includes the latitude and longitude of the CIA’s headquarters, and this: “Does Langley know about this? They should: it’s buried out there somewhere. X Who knows the exact location? Only WW.”

The third passage comes from Egyptologist Howard Carter’s account of opening King Tut’s tomb – a passage Sanborn says he has loved since childhood: “Slowly, desparatly slowly, the remains of passage debris that encumbered the lower part of the doorway was removed. With trembling hands I made a tiny breach in the upper left-hand corner. And then, widening the hole a little, I inserted the candle and peered in. The hot air escaping from the chamber caused the flame to flicker, but presently details of the room within emerged from the mist. x Can you see anything?”

It’s about the thrill of discovery, Sanborn says.

Sanborn suggests that even after the text is decrypted, there will be riddles of analysis to come. “I think all art should be subject to as many interpretations as possible. … If there’s nothing more to discover about it, then it’s not a very interesting artwork.”

An Artist’s Reward

Scheidt says he is happy to see the sculpture he helped create continue to engage the attention of people around the world. “Most people talk about cryptography, they remember it in the context of the cryptoanalyst,” like the World War II geniuses who cracked the Axis codes. “Very few people actually talk about the person who designs the thing,” says Scheidt, who founded a Vienna cryptography company called TecSec after leaving the CIA.

The last 97 characters? Don’t hold your breath. Scheidt says with satisfaction, “I saved the best for last.”

“No clues, sorry.”

In an e-mail message, Gillogly says he’s working away on them. “I’ve tried on the order of 20 billion trial decryptions spread over two dozen different systems with perhaps 5 or 10 variations each, on average. … It’s all pretty much shooting in the dark, since you don’t know you’ve gotten close until you hear a scream. :)” In e-mail, that final symbol signifies a joke.

Gillogly wants hints badly, asking whether Scheidt or Sanborn has let anything slip in interviews; his jovial voice belies an undertone of hunger, even in e-mail. “Please give Jim Sanborn my regards and let him know I’m still plugging hard on the last 97 … and pump him for clues for all you’re worth!”

For his part, Stein says he doesn’t want help. He got this far on his own, and that’s how he intends to finish the job. For now, however, he’s got a bigger puzzle on his hands: raising his first child. If he’s not the first to break the last passage, he doesn’t want to know what it says; he will return some day to crack it himself.

“Even if it’s solved, I won’t look.”

reposted – Kryptosfan