Mission Impossible: The Code Even the CIA Can't Crack

[Eugen Leitl]

http://www.wired.com/print/science/discoveries/magazine/17-05/ff_kryptos 

Mission Impossible: The Code Even the CIA Can't Crack

By Steven Levy Email 04.20.09

The sculpture named Kryptos at CIA headquarters contains a secret message ?
but not even the agency's brightest can crack its code.

Photo: Adrian Gaut

The most celebrated inscription at the Central Intelligence Agency's
headquarters in Langley, Virginia, used to be the biblical phrase chiseled
into marble in the main lobby: "And ye shall know the truth, and the truth
shall make you free." But in recent years, another text has been the subject
of intense scrutiny inside the Company and out: 865 characters of seeming
gibberish, punched out of half-inch-thick copper in a courtyard.

It's part of a sculpture called Kryptos, created by DC artist James Sanborn.
He got the commission in 1988, when the CIA was constructing a new building
behind its original headquarters. The agency wanted an outdoor installation
for the area between the two buildings, so a solicitation went out for a
piece of public art that the general public would never see. Sanborn named
his proposal after the Greek word for hidden. The work is a meditation on the
nature of secrecy and the elusiveness of truth, its message written entirely
in code.

Almost 20 years after its dedication, the text has yet to be fully
deciphered. A bleary-eyed global community of self-styled cryptanalysts?along
with some of the agency's own staffers?has seen three of its four sections
solved, revealing evocative prose that only makes the puzzle more confusing.
Still uncracked are the 97 characters of the fourth part (known as K4 in
Kryptos-speak). And the longer the deadlock continues, the crazier people
get.

Whether or not our top spooks intended it, the persistent opaqueness of
Kryptos subversively embodies the nature of the CIA itself?and serves as a
reminder of why secrecy and subterfuge so fascinate us. "The whole thing is
about the power of secrecy," Sanborn tells me when I visit his studio, a
barnlike structure on Jimmy Island in Chesapeake Bay (population: 2). He is
6'7", bearded, and looks a bit younger than his 63 years. Looming behind him
is his latest work in progress, a 28-foot-high re-creation of the world's
first particle accelerator, surrounded by some of the original hardware from
the Manhattan Project. The atomic gear fits nicely with the thrust of
Sanborn's oeuvre, which centers on what he calls invisible forces.

With Kryptos, Sanborn has made his strongest statement about what we don't
see and can't know. "He designed a piece that would resonate with this
workforce in particular," says Toni Hiley, who curates the employees-only CIA
museum. Sanborn's ambitious work includes the 9-foot 11-inch-high main
sculpture?an S-shaped wave of copper with cut-out letters, anchored by an
11-foot column of petrified wood?and huge pieces of granite abutting a low
fountain. And although most of the installation resides in a space near the
CIA cafeteria, where analysts and spies can enjoy it when they eat outside,
Kryptos extends beyond the courtyard to the other side of the new building.
There, copper plates near the entrance bear snippets of Morse code, and a
naturally magnetized lodestone sits by a compass rose etched in granite.

"People call me an agent of Satan," says artist Sanborn, "because I won't
tell my secret."

Photo: Adrian Gaut

The heart of the piece, though, is the encrypted text, scrambled, Sanborn
says, by "a coding system that would unravel itself slowly over a period of
time."

When he began the work, Sanborn knew very little about cryptography, so he
reluctantly accepted the CIA's offer to work with Ed Scheidt, who had just
retired as head of Langley's Cryptographic Center. Scheidt himself was
serving two masters. "I was reminded of my need to preserve the agency's
secrets," Scheidt says. "You know, don't tell him the current way of doing
business. And don't create something that you cannot break?but at the same
time, make it something that will last a while."

Scheidt schooled Sanborn in cryptographic techniques employed from the late
19th century until World War II, when field agents had to use pencil and
paper to encode and decode their messages. (These days, of course,
cryptography is all about rugged computer algorithms using long mathematical
keys.) After experimenting with a range of techniques, including
poly-alphabetic substitution, shifting matrices, and transposition, the two
arrived at a form of old-school, artisanal cryptography that they felt would
hold off code breakers long enough to generate some suspense. The solutions,
however, were Sanborn's alone, and he did not share them with Scheidt. "I
assumed the first three sections would be deciphered in a matter of weeks,
perhaps months," Sanborn says. Scheidt figured the whole puzzle would be
solved in less than seven years.

During the two years of construction, there were moments of intrigue and
paranoia, in keeping with the subject matter and the client. "We had to play
a little on the clandestine side," says Scheidt, who talks of unnamed
observers outside armed with long-range cameras and high-intensity
microphones. "We had people with ladders climbing up the walls of my studio
trying to photograph inside," Sanborn says. He came to believe that factions
within the CIA wanted to kill the project. There were unexplained obstacles.
For instance, he says, "one day a big truckload of stone for the courtyard
disappeared. Never found. I saw it in the evening, went back in the morning,
and it had vanished. Nobody would tell me what happened to it."

Sanborn finished the sculpture in time for a November 1990 dedication. The
agency released the enciphered text, and a frenzy erupted in the crypto world
as some of the best?and wackiest?cryptanalytic talent set to work. But it
took them more than seven years, not the few months Sanborn had expected, to
crack sections K1, K2, and K3. The first code breaker, a CIA employee named
David Stein, spent 400 hours working by hand on his own time. Stein, who
described the emergence of the first passage as a religious experience,
revealed his partial solution to a packed auditorium at Langley in February
1998. But not a word was leaked to the press. Sixteen months later, Jim
Gillogly, an LA-area cryptanalyst used a Pentium II computer and some custom
software to crack the same three sections. When news of Gillogly's success
broke, the CIA publicized Stein's earlier crack.

James Sanborn buried his sculpture's message so deeply that a CIA staffer
took seven years to solve just the first three sections. Here's what we know.

The first section, K1, uses a modified Vigenère cipher. It's encrypted
through substitution?each letter corresponds to another?and can be solved
only with the alphabetic rows of letters on the right. The keywords, which
help determine the substitutions, are KRYPTOS and PALIMPSEST. A
misspelling?in this case IQLUSION?may be a clue to cracking K4.

K2, like the first section, was also encrypted using the alphabets on the
right. One new trick Sanborn used, though, was to insert an X between some
sentences, making it harder to crack the code by tabulating letter frequency.
The keywords here are KRYPTOS and ABSCISSA. And there's another intriguing
misspelling: UNDERGRUUND.

A different cryptographic technique was used for K3: transposition. All the
letters are jumbled and can be deciphered only by uncovering the complex
matrices and mathematics that determined their misplacement. Of course, there
is a misspelling (DESPARATLY), and the last sentence (CAN YOU SEE ANYTHING?)
is strangely bracketed by an X and a Q.

Sanborn intentionally made K4 much harder to crack, hinting that the
plaintext itself is not standard English and would require a second level of
cryptanalysis. Misspellings and other anomalies in previous sections may
help. Some suspect that clues are present in other parts of the installation:
the Morse code, the compass rose, or perhaps the adjacent fountain.

But if anyone expected that solving the first three sections would lead to a
quick resolution of the whole puzzle, their hopes were soon dashed. The
partial solutions only deepened the Gillogly turned up that passage, he says,
he had "the same excitement and exultation that Carter described. In a way,
it seems that the plaintext is a metaphor for the work of the code breaker,
or perhaps of the CIA itself."

The 97 characters of K4 remain impenetrable. They have become, as one
would-be cracker calls it, the Everest of codes. Both Scheidt and Sanborn
confirm that they intended the final segment to be the biggest challenge.
There are endless theories about how to solve it. Is access to the sculpture
required? Is the Morse code a clue? Every aspect of the project has come
under electron-microscopic scrutiny, as thousands of people?hardcore
cryptographers and amateur code breakers alike?have taken a whack at it. Some
have gone off the deep end: A Michigan man abandoned his computer-software
business to do construction so he'd have more time to work on it. Thirteen
hundred members of a fanatical Yahoo group try to move the ball forward with
everything from complex math to astrology. One typical Kryptos maniac is
Randy Thompson, a 43-year-old physicist who has devoted three years to the
problem. "I think I'm onto the solution," he says. "It could happen tomorrow,
or it could take the rest of my life." Meanwhile, some of the seekers are
getting tired. "I just want to see it solved," says Elonka Dunin, a
50-year-old St. Louis game developer who runs a clearinghouse site for
Kryptos information and gossip. "I want it off my plate."

Making the effort more complicated is the fact that the puzzle maker is alive
and, in theory at least, a potential resource. For years, there has been a
delicate pas de deux between the artist and the rabid Kryptos community.
Every word Sanborn utters is eagerly examined for hints. But they also have
to wonder whether he's trying to help them or throw them off track. Scheidt
says that this process parallels the work of the CIA: "The intelligence
picture includes mirrors and obfuscation." Photo: Adrian Gaut

"It's not my intent to put out disinformation," Sanborn says. "I'm a
benevolent cryptographer." Some think otherwise, and Sanborn occasionally
receives messages from people enraged that he knows the secret and they
don't. "It's the fact that I have some sort of power," he says. "You get
stalkers. I don't know how they get my cell numbers and everything off the
Internet, but they do. People have called me and said pretty terrible things.
There are some who say I'm an agent of Satan because I have a secret I won't
tell."

Though Sanborn's usual practice is to stay in the background, every so often
he feels obliged to comment. In 2005, he refuted author Dan Brown's claim
that the "WW" in the plaintext of K3 could be inverted to "MM," implying Mary
Magdalene. (Brown included pieces of Kryptos on the book jacket of The Da
Vinci Code and has hinted that his next novel will draw on the CIA sculpture,
a prospect that deeply annoys Sanborn.)

Intentional or not, Sanborn's comments (or lack thereof) seem to generate an
added layer of confusion. Even a straightforward question, like who besides
him knows the solution, opens up new wormholes. The official story is that
Sanborn shared the answer with only one person, the CIA director at the time,
William Webster. Indeed, the decoded K3 text reads in part, "Who knowshat it
says." What does the CIA make of all this? "When it comes to the solution,"
says spokesperson Marie Harf, "those who need to know, know."

If anyone manages to solve the last cipher, that won't end the hunt for the
ultimate truth about Kryptos. "There may be more to the puzzle than what you
see," Scheidt says. "Just because you broke it doesn't mean you have the
answer." All of this leads one to ask: Is there a solution? Sanborn insists
there is?but he would be just as happy if no one ever discovered it. "In some
ways, I'd rather die knowing it wasn't cracked," he says. "Once an artwork
loses its mystery, it's lost a lot."

The day I visited Kryptos, a rare snowstorm in Virginia had blanketed the
courtyard in white. I circled the sculpture carefully, marveling at the way
the colors and texture of the surrounding landscape affected the panels, as
some character strings became highlighted in white and other phrases
shimmered, reflecting the dull light bouncing off the windows. I examined all
the pieces, brushing aside the snow to uncover the Morse code and the compass
rose. It was like unearthing hieroglyphs in some ancient ruin. Agents and
bureaucrats shuffled past, deep in thought, clutching cups of coffee from the
onsite Starbucks. In their midst, Jim Sanborn's statement in copper, wood,
and granite remains, proof that even in the house of spies, some truths may
never be found.

Senior writer Steven Levy (steven_levy at wired.com) wrote about the 20th
anniversary of the Mac in issue 17.01.


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com