Documents Reveal How the NSA Cracked the Kryptos Sculpture Years Before the CIA

The Kryptos Sculpture. Photo: Wikimedia Commons

It took more than eight years for a CIA analyst and a California computer scientist to crack three of the four coded messages on the CIA’s famed Kryptos sculpture in the late ’90s.
Little did either of them know that a small group of cryptanalysts inside the NSA had beat them to it, and deciphered the same three sections of Kryptos years earlier — and they did it in less than a month, according to new documents obtained from the NSA.
These days the NSA is best known for its broad, indiscriminate spying on Americans and foreigners. But the Kryptos crack shows how some of the agency’s smartest geeks once blew off steam in the relatively quiet days between the end of the Cold War and the September 11 attacks.
The popular story of Kryptos has long held that CIA analyst David Stein was the first to crack three of the cryptographic sculpture’s four puzzles in 1998.
Stein decrypted the coded messages after spending some 400 hours’ worth of lunch hours working through the puzzles using only paper and pencil. Many people, on and off the CIA campus in Langley, Virginia, had tried to break the coded puzzle, but only Stein, a member of the agency’s Directorate of Intelligence, succeeded. Stein’s work on the code was kept secret, however. In 1999, he wrote a fascinating account of how he cracked three of the sculpture’s four coded messages, but it was only published in an internal CIA newsletter that remained classified until years later.
The secrecy over Stein’s achievement allowed California computer scientist Jim Gillogly to steal the spotlight a year later in 1999, when he announced that he’d also cracked the same three messages, only he used a Pentium II to do it.
But new documents released by the National Security Agency show how the Defense Department’s spy agency beat Stein and Gillogly to the punch years earlier.

An internal NSA memo discussing the agency’s success at cracking three of the sculpture’s four puzzles. Courtesy of Elonka Dunin

It’s a story that has largely remained buried in the NSA archives until Elonka Dunin unearthed it in a recent FOIA request. Dunin is the premier expert on Kryptos who oversees a Google Group dedicated to cracking the code and also maintains a website dedicated to the sculpture.
Although a Baltimore Sun story about Kryptos in 2000 disclosed that the NSA had cracked three sections of the puzzle, many of the details behind the efforts were not revealed.
It all began in 1988 when the CIA Fine Arts Commission commissioned local artist James Sanborn to create a cryptographic sculpture for a courtyard on the CIA campus. Sanborn completed the two-part sculpture in 1990, which included stones laid out in International Morse code near the front entrance of the CIA campus, and a 12-foot-high, verdigrised copper, granite and petrified wood sculpture. The latter, which is the more famous part of Kryptos, was inscribed with four encrypted messages composed from some 1,800 letters carved out of the copper plate.
One of the memos notes that the layout of the two-part sculpture was “a landscaping scheme designed to recall the natural stone out-cropping that existed on the site before the Agency, and that will endure as do mountains.” The placement of the sculpture “in a geologic context reinforces the text’s ‘hidden-ness’ as if it were a fossil or an image frozen in time.”
In 1991, while on a trip to the CIA, a group of NSA cryptanalysis “interns” diligently scribbled all the letters from the sculpture onto sheets of paper and brought them back to the NSA so curious analysts there could take a crack at it. In December 1991 a group of NSA analysts met in a conference room at the NSA to discuss the sculpture and what methods of decryption they might apply, including classified methods used internally by the NSA.
A memo about this meeting indicates that “any discussion of ‘in-house’ techniques or applications (being classified) are not mentioned in this text as it is to be unclassified.” The memo also included a note to participants not to discuss their efforts to crack the puzzle in public, as some of the methods they used might be classified, as well as a message at the bottom of the memo indicating that “these notes were prepared at NO expense to the US Government.”
After that initial NSA meeting, however, nothing further was done on the puzzle. Over the next year, the CIA tried to crack the sculpture on its own, but with no success.
The sculpture remained unsolved until 1992, when Adm. William O. Studeman, the CIA’s then-deputy director and a former NSA director, issued a formal challenge to his former colleagues at the NSA to solve the CIA’s new courtyard puzzle. The NSA’s director at the time, Vice Admiral Mike McConnell, announced the challenge during an internal ceremony at the NSA, and a small cadre of cryptanalysts from the agency’s Z Group — the internal name for the cryptanalysts division — “enthusiastically responded.”
Left on their own, NSA employees had shown little passion for cracking the ciphers, but once a formal challenge was on the table from the CIA, it was hard to resist. The group was so intent on cracking the code that they formed an informal task force in November 1992, according to the recently released documents, which include a number of internal NSA memos describing how they cracked the ciphers.
Working from the transcription obtained by interns a year earlier, they quickly determined, using computer diagnostic tools, that the sculpture consisted of four parts — using at least three different ciphers — and a cryptographic table based on an encryption method developed in the 16th century by a Frenchman named Blaise de Vigenere that was key to helping them solve parts of the puzzle.
They were sure to note that subsequent analysis and solutions of the code “did not require any computer power” but were done by hand.
They quickly discovered that the encrypted sections included intentional spelling errors made by artist James Sanborn, and misaligned characters set higher on a line of text than characters around them.
Then “within two days of receiving the information tasking from Chief, Z,” they had solved parts one through three of the puzzle. They spent another day on the fourth section, but very quickly “a decision was made to stop any further work” on it. “Given the suspected cryptography, the last section is too short to solve without diverting a great deal of effort from operational problems,” they wrote in the memo.

NSA memo discussing how the cryptanalysts achieved their first breakthrough in deciphering the sculpture. Courtesy of Elonka Dunin

In the end, it was just three analysts who solved the codes, one tackling each section of the puzzle. Although the names are redacted in the documents released by the NSA, Dennis McDaniels was identified as one of the crackers in the Baltimore Sun article. Ken Miller was also identified as another member of the group, though someone knowledgeable about the project told Wired that he didn’t decipher any of the sections but worked closely with the group to write up their notes.
In June 1993, after the three parts were cracked, an internal letter announcing the feat was sent to Admiral McConnell at the NSA, marked “For Official Use Only” and informing him that the deed was done. It was returned with a request to forward the note to Admiral Studeman at the CIA, no doubt with an air of glee and arrogance that the NSA had beat the CIA at cracking its own puzzle. Another scribbled note on the memo read, “Great Story!”
The documents describe their efforts through “many wrong turns” to arrive at the solutions.
The first part of the sculpture used a periodic polyalphabetic substitution cipher using 10 alphabets, and when decrypted was a poetic phrase that Sanborn had composed himself: “Between subtle shading and the absence of light lies the nuance of iqlusion” (“iqlusion” was an intentional misspelling of illusion).
Part two used a periodic polyalphabetic substitution cipher using 8 alphabets. When decrypted, the passage hinted at something buried:

It was totally invisible. How’s that possible? They used the Earth’s magnetic field. x The information was gathered and transmitted underground to an unknown location. x Does Langley know about this? They should: It’s buried out there somewhere. x Who knows the exact location? Only WW. This was his last message. x Thirty-eight degrees fifty-seven minutes six point five seconds north, seventy-seven degrees eight minutes forty-four seconds west. ID by rows.

The cryptanalysts correctly guessed that WW referred to William Webster, which Wired confirmed in 2005 during an interview with artist Sanborn. “The coordinates,” the memo noted, “refer to the location of or a location within the Central Intelligence Agency.” But the significance of the I.D. by Rows? That remained “undetermined,” the NSA’s puzzle crackers wrote.
In fact, Sanborn had made an error in the puzzle and inadvertently introduced a typo in the section. The mistake involved an “x” that he intentionally deleted from the end of a line in section two for aesthetic reasons, to keep the sculpture visually balanced. The “x” was supposed to signify a period or section break at the end of a phrase, but Sanborn removed it thinking it wouldn’t affect the way the puzzle was deciphered. It turned out the “x” made all the difference, however.
Instead of “ID by rows” it actually should have been deciphered to read “layer two,” though code breakers wouldn’t discover this until years after the NSA cryptanalysts had their crack at the code.
Part three used a keyed columnar transposition cipher, which the cryptanalysts partly diagnosed solely by “eyeballing” the text.
“The most likely explanation for this is a transposition system,” they write, “perhaps a keyed columnar transposition. In such a system, the plain text is inscribed horizontally into a matrix, normally a rectangle, and then the latter are extracted vertically, according to a pre-determined sequence.”
When decrypted, it was a paraphrased page taken from the diary of archaeologist Howard Carter describing the opening of a door in King Tut’s tomb on Nov. 26, 1922.

Slowly, desperately 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? q

According to a former Defense Department cryptanalyst who spoke with Wired, McDaniels was responsible for cracking section three and did it in just six hours lying on his living room couch with paper and pencil after coming home exhausted one day from playing volleyball. McDaniels is now retired from the NSA and declined to speak with Wired about his work on the sculpture. But the source told Wired that McDaniels had been out all day playing volleyball and came home around 10pm.
“He plopped down on the couch in the living room, picked up his draft notes for K3,” the source said. “He had tinkered with it before but could never get into it. He knew it was just basic transposition, so he started with the letter Q and [the letter U after it] and found there were five instances of the letter U, and he just tried all five of those. Then he had to try every other vowel that came after and he finally found something that broke it. By then it was about 4am and he was done.”
Unfortunately the fourth section stymied the NSA code breakers, as it has continued to do other cryptanalysts for 23 years. The documents noted that “although ideas abound” for deciphering it, the final 97 characters of the sculpture “continue to elude solution.”

OBKR
UOXOGHULBSOLIFBBWFLRVQQPRNGKSSO
TWTQSJQSSEKZZWATJKLUDIAWINFBNYP
VTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR

They speculated that this section might employ a combination of the techniques used in other sections. “First the message is encrypted using some set of alphabets,” they write, “as was done in the first and third breakthroughs, and then the cipher is put through a transposition, such as that used in the second breakthrough.” But even with that they were never able to solve it.
In 2010, Sanborn, surprised that the final section had remained unsolved for so long, and perhaps feeling guilty about an error he had made in the sculpture that misled puzzle-solvers for years, decided to disclose six of the 97 letters in the last section. The six letters — NYPVTT — are the 64th through 69th letters of the final section and when deciphered spell out the word “BERLIN.”
The clue has yet to be the breakthrough that code crackers had hoped it would be, however, and the last section still remains unsolved.
Even when that final section is solved, however, sleuths still won’t know what the sculpture means. The deciphered text contains a riddle, which will require them to be on the CIA grounds in order to solve it.
“In part of the code that’s been deciphered, I refer to an act that took place when I was at the agency and a location that’s on the ground of the agency,” Sanborn told Wired in 2005. He may be referring to something he buried on the CIA grounds, though he won’t say for sure. The decrypted text gives latitude and longitude coordinates (38 57 6.5 N, 77 8 44 W), which Sanborn has said refer to “locations of the agency.” So sleuths will have to first decipher the code then find their way onto the CIA grounds and locate that place in order to finally discover what it all means.

http://www.wired.com/threatlevel/2013/07/nsa-cracked-kryptos-before-cia/?cid=9651674

T H A N K S