Copyright Scientific American
The 35-year-old saga of Kryptos, an enigmatic sculpture containing four encrypted messages outside the CIA headquarters, just took a bizarre twist. Though cryptographers broke the first three passages in the 1990s, just a few years after artist Jim Sanborn erected the copper monolith, the fourth, known as K4, remained a 97-character fortress—that is, until September 2, when journalists Jarett Kobek and Richard Byrne discovered the answer in the Smithsonian archives. How does one crack the world’s most famous code? The breakthroughs on Kryptos provide a guided tour through the cat and mouse game between code makers and code breakers that has defined information security for millennia. The core challenge of cryptography is to send a secret message securely in the presence of eavesdroppers. The strategy always involves the same ingredients: The message, called the plaintext, gets distorted (the encryption) so that anybody who intercepts it sees only garbled gibberish (the ciphertext). Ideally only those with a secret key can decrypt it. If you share your secret key with the intended recipient and nobody else, then you can, in theory, communicate with them in code. Cryptography underlies everyday financial transactions and online communication, not just spy messages. On supporting science journalism If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today. To understand Kryptos, we’ll need to dig into early cryptosystems and why they failed. One of the simplest and oldest encryption methods dates back to a historical secret keeper: Julius Caesar. The Caesar cipher obscures messages by shifting every letter of the alphabet by some fixed amount. Here the key is a number between 1 and 25. Say we pick 5. The encryption of “hello” would be “mjqqt” because M is five letters after H, J is five letters after E, and so on. (If you reach the end of the alphabet, then wrap back around to the beginning.) For a more entertaining example, astute fans of 2001: A Space Odyssey have noticed that the name of the rogue AI called HAL spells “IBM” with a Caesar cipher shift of one letter backward. (Director Stanley Kubrick insisted that this was a coincidence.) Although Caesar trusted this method for his confidential correspondence, it’s a lousy way to protect state secrets. If an adversary learns that you encrypt messages with a Caesar cipher, they only need to try 25 different keys to recover the original text. A general substitution cipher offers the most natural upgrade. Instead of merely shifting the alphabet, you scramble it. The letter A might become Q, B might become X, C might become D, and so on, in no particular order. This seems far more secure. A Caesar cipher has only 25 possible keys, but a full substitution cipher has 403,291,461,126,605,635,584,000,000. (There are 26 factorial ways to mix up the alphabet, or 26 × 25 × 24 × 23 ... 3 × 2 × 1.) A brute-force search of checking every key isn’t feasible, yet substitution ciphers are still woefully insecure by today’s standards. If you don’t already know why, ask yourself how you would go about decoding a page of text encrypted with a substitution cipher. The flaw in a substitution cipher is that it leaves patterns in language intact. English has a distinct fingerprint. E accounts for more than 12 percent of all letters in English text, whereas the letter Z crops up less than 0.1 percent of the time. If you intercept a page of gibberish encrypted with a substitution cipher and the letter J appears more often than any other letter, it’s a good bet that J stands for E. The second-most-common letter is probably a T. Furthermore, single-letter words almost certainly stand for A or I (the only frequently used one-letter English words), and common two- and three-letter words can give code breakers a foot in the door as well. Called frequency analysis, this method is the subject of popular newspaper puzzles called cryptograms; it also played a critical role in deciphering the first three Kryptos passages. Sanborn encrypted the first two Kryptos messages, called K1 and K2, and which contain 63 and 372 characters, respectively, using the next level up: the Vigenère cipher. Invented in the 16th century and named after the cryptographer Blaise de Vigenère, it stood unbroken for 300 years, earning it the nickname “le chiffre indéchiffrable” (the indecipherable cipher). It works by applying several different Caesar ciphers to a single plaintext. For example, maybe we shift the first letter of the message forward by 19, the second letter forward by 16, the third letter forward by 25 and then repeat. (The fourth letter shifts by 19, the fifth by 16, the sixth by 25, and so on.) These shift amounts constitute the key, which is typically represented by a word corresponding to those locations in the alphabet. In this case, the key is SPY because S, P and Y are the 19th, 16th and 25th letters. The Vigenère cipher ingeniously defeats straightforward frequency analysis because not all E’s, for example, will get mapped to the same letter. Imagine that the first two letters of a message are both E. The first gets shifted by 19 to become an X and the second by 16 to become a U. But clever cryptanalysts can still break through. If you can guess the length of the key (for example, three for SPY), you can break the problem apart. You take the first, fourth, seventh and 10th letters, and so on, of the ciphertext and put them in a pile. All of these were shifted according to the same key letter: S. Now you can conduct frequency analysis on just that pile. You do the same for the second, fifth and eighth letters, all shifted according to P, and so on. The “unbreakable” cipher becomes three simple Caesar ciphers. Not sure of the length of the key? Careful scrutiny of the ciphertext can sometimes provide clues, but if all else fails, try all possible lengths. Too time-consuming? A computer program can help with the search. Sanborn encrypted K1 and K2 with the keys “PALIMPSEST” and “ABSCISSA,” respectively. The former, a poetic choice, refers to a piece of writing that has been erased and written over multiple times. Abscissa is the x coordinate of an (x, y) coordinate pair. As is common practice in Vigenère ciphers, Sanborn also used a modified alphabet for the shifting: in this case, KRYPTOSABCDEFGHIJLMNQUVWXZ, which he etched into the sculpture. Sanborn switched methods for K3, a 337-character ciphertext. Here he opted for a transposition cipher in which he simply jumbled all of the letters in the message as though it were a massive anagram. The jumble in this type of cipher typically follows certain rules so that an intended recipient with a key can easily restore the letters to their rightful order. Cryptographers readily suspected that K3 used this cipher. How? You guessed it—frequency analysis. The letter distribution in the ciphertext matched what would be expected in typical English text, suggesting that letters had not been substituted, merely shuffled. At least three independent efforts deciphered the first three Kryptos messages. Computer scientist Jim Gillogly announced that he had broken them with the aid of a computer in 1999. Only then did the CIA reveal that its analyst David Stein had solved all three by hand in 1998. And only then did the National Security Agency advertise that a small internal team had conquered them way back in 1992. K4 had resisted all attempts for 35 years. Perhaps Sanborn intentionally cranked up its complexity to reflect the strides made in cryptographic science since the days of Vigenère. Breaking full-fledged modern cryptography wouldn’t merely amount to a cleverer deployment of frequency analysis but a revolution in our understanding of math itself. That’s because cutting-edge encryption shrouds information behind mathematical problems (such as factoring enormous numbers) that are conjectured to be unsolvable in any practical amount of time. To break the encryption would mean finding a fast solution to these supposedly infeasible problems, an act that would overturn a foundational assumption of modern math. This fall Sanborn was planning to auction off the solution to K4—an encrypted message that starts with “OBKR”—to relieve himself of the role of sole steward to its secrets. The auction announcement referenced original “coding charts” at the Smithsonian. Rather than actually deciphering K4, journalists Kobek and Byrne requested access to the documents and found scraps of paper containing K4’s plaintext. On September 3 the duo e-mailed Sanborn with the solution. Journalists uncovering the answer to K4 in the Smithsonian archives perfectly exemplifies how hackers infiltrate 21st-century cryptography: through side doors. To the best of anyone’s knowledge, the modern encryption that protects your e-mails and credit card purchases, when implemented correctly, works. Data breaches are rarely the result of hackers breaking an encryption but rather finding some other weak link in the security chain. They run phishing scams to trick people into disclosing their login credentials. They exploit a bug in a website’s code. That is, they target the flawed, forgetful and disorganized humans who use encryption. The discovery of K4’s plaintext was akin to finding somebody’s password scribbled on a sticky note in their office. Some find this climax disappointing, but we could also view it as a fitting metaphor for an art piece meant to honor cryptography through the ages.
