Friday, March 03, 2017

Kryptos - The Cipher (Part 1)

Introduction

KRYPTOS - Von Jim Sanborn - Jim Sanborn, CC BY-SA 3.0,
https://commons.wikimedia.org/w/index.php?curid=8253447
Because i think KRYPTOS does not need an introduction, i will only give you briefly the details of one of the most famous and only partly solved cipher known today:
  1. KRYPTOS was constructed in Nov. 1990 on the ground of the CIA Headquarter in Langley, Virginia by Jim Sanborn
  2. It contains 4 ciphers (K1,K2,K3,K4) on its left side and some kind of Vigenère-Table on its right side.
  3. K1, K2 and K3 were solved by James Gillogly in 1999. Afterwards, the CIA and later the NSA claimed that they had a solution to the first three ciphers at an earlier point in time.
  4. Ed Scheidt, a cryptoanalyst and former director of the CIA, gave Sanborn the input of possible cryptographic techniques to use.
  5. K1 is a variant of the Vigenère-Cipher (Quagmire 3) with the codewords KRYPTOS and PALIMPSEST
  6. K2 is a variant of the Vigenère-Cipher (Quagmire 3) with the codewords KRYPTOS and ABSCISSA
  7. K3 is a Transposition cipher
  8. Jim Sanborn said that the previous ciphers K1,K2 and K3 contain information that will help to solve the last cipher K4
  9. 2010 Sanborn published the clue that the 6 letters from 64-69 of the ciphertext K4 decrypt to 'BERLIN'. Four years later, he revealed that the characters 70-74 decrypt to 'CLOCK'
  10. However, K4 remains unsolved. 
This post is more of introductory nature, so if you already know a lot of KRYPTOS you will probably not learn anything new.

Ciphertexts

Below you find the ciphertext of the K1-K4 ciphers: Orange:K1, green:K2, blue:K3, yellow:K4

$\small{\texttt{01| E M U F P H Z L R F A X Y U S D J K Z L D K R N S H G N F I V J}}$
$\small{\texttt{02| Y Q T Q U X Q B Q V Y U V L L T R E V J Y Q T M K Y R D M F D}}$
$\small{\texttt{03| V F P J U D E E H Z W E T Z Y V G W H K K Q E T G F Q J N C E}}$
$\small{\texttt{04| G G W H K K ? D Q M C P F Q Z D Q M M I A G P F X H Q R L G}}$
$\small{\texttt{05| T I M V M Z J A N Q L V K Q E D A G D V F R P J U N G E U N A}}$
$\small{\texttt{06| Q Z G Z L E C G Y U X U E E N J T B J L B Q C R T B J D F H R R}}$
$\small{\texttt{07| Y I Z E T K Z E M V D U F K S J H K F W H K U W Q L S Z F T I}}$
$\small{\texttt{08| H H D D D U V H ? D W K B F U F P W N T D F I Y C U Q Z E R E}}$
$\small{\texttt{09| E V L D K F E Z M O Q Q J L T T U G S Y Q P F E U N L A V I D X}}$
$\small{\texttt{10| F L G G T E Z ? F K Z B S F D Q V G O G I P U F X H H D R K F}}$
$\small{\texttt{11| F H Q N T G P U A E C N U V P D J M Q C L Q U M U N E D F Q}}$
$\small{\texttt{12| E L Z Z V R R G K F F V O E E X B D M V P N F Q X E Z L G R E}}$
$\small{\texttt{13| D N Q F M P N Z G L F L P M R J Q Y A L M G N U V P D X V K P}}$
$\small{\texttt{14| D Q U M E B E D M H D A F M J G Z N U P L G E W J L L A E T G}}$
$\small{\texttt{15| E N D}}$$\large{\texttt{ Y A }}$$\small{\texttt{H}}$$\large{\texttt{ R }}$$\small{\texttt{O H N L S R H E O C P T E O I B I D Y S H N A I A}}$
$\small{\texttt{16| C H T N R E Y U L D S L L S L L N O H S N O S M R W X M N E}}$
$\small{\texttt{17| T P R N G A T I H N R A R P E S L N N E L E B L P I I A C A E}}$
$\small{\texttt{18| W M T W N D I T E E N R A H C T E N E U D R E T N H A E O E}}$
$\small{\texttt{19| T F O L S E D T I W E N H A E I O Y T E Y Q H E E N C T A Y C R}}$
$\small{\texttt{20| E I F T B R S P A M H H E W E N A T A M A T E G Y E E R L B}}$
$\small{\texttt{21| T E E F O A S F I O T U E T U A E O T O A R M A E E R T N R T I}}$
$\small{\texttt{22| B S E D D N I A A H T T M S T E W P I E R O A G R I E W F E B}}$
$\small{\texttt{23| A E C T D D H I L C E I H S I T E G O E A O S D D R Y D L O R I T}}$
$\small{\texttt{24| R K L M L E H A G T D H A R D P N E O H M G F M F E U H E}}$
$\small{\texttt{25| E C D M R I P F E I M E H N L S S T T R T V D O H W ? }}$$\small{\texttt{ O B K R}}$
$\small{\texttt{26| U O X O G H U L B S O L I F B B W F L R V Q Q P R N G K S S O}}$
$\small{\texttt{27| T W T Q S J Q S S E K Z Z W A T J K L U D I A W I N F B N Y P}}$
$\small{\texttt{28| V T T M Z F P K W G D K Z X T J C D I G K U H U A U E K C A R}}$

Plaintexts

The plaintexts of the ciphers K1, K2 and K3 are as follows:
K1
$\texttt{BETWEEN SUBTLE SHADING AND THE ABSENCE OF LIGHT}$
$\texttt{LIES THE NUANCE OF IQLUSION}$
K2
$\texttt{IT WAS TOTALLY INVISIBLE HOWS THAT POSSIBLE ?}$
$\texttt{THEY USED THE EARTHS MAGNETIC FIELD X}$
$\texttt{THE INFORMATION WAS GATHERED AND TRANSMITTED}$
$\texttt{UNDERGRUUND TO AN UNKNOWN LOCATION X}$
$\texttt{DOES LANGLEY KNOW ABOUT THIS ?}$
$\texttt{THEY SHOULD ITS BURIED OUT THERE SOMEWHERE X}$
$\texttt{WHO KNOWS THE EXACT LOCATION ?}$
$\texttt{ONLY WW THIS WAS HIS LAST MESSAGE X}$
$\texttt{THIRTY EIGHT DEGREES FIFTY SEVEN MINUTES SIX POINT FIVE SECONDS NORTH}$
$\texttt{SEVENTY SEVEN DEGREES EIGHT MINUTES FORTY FOUR SECONDS WEST X}$
$\texttt{LAYER TWO}$
K3
$\texttt{SLOWLY DESPARATLY SLOWLY THE REMAINS OF PASSAGE DEBRIS}$
$\texttt{THAT ENCUMBERED THE LOWER PART OF THE DOORWAY}$
$\texttt{WAS REMOVED WITH TREMBLING HANDS}$
$\texttt{I MADE A TINY BREACH IN THE UPPER LEFT HAND CORNER}$
$\texttt{AND THEN WIDENING THE HOLE A LITTLE}$
$\texttt{I INSERTED THE CANDLE AND PEERED IN }$
$\texttt{THE HOT AIR ESCAPING FROM THE CHAMBER CAUSED THE FLAME TO FLICKER}$
$\texttt{BUT PRESENTLY DETAILS OF THE ROOM WITHIN EMERGED FROM THE MIST X}$
$\texttt{CAN YOU SEE ANYTHING Q (?)}$

Intentional and unintentional errors and further oddities

Errors and other kinds of oddities play a huge role in cryptanalysis, since all these things can be clues for the key, the method or some hidden structure of the ciphertext/plaintext.

1 ▶ The first error is in line 2:
$\small{\texttt{02| Y Q T Q U X Q B Q V Y U V L L T R E V J Y Q T M }}$$\small{\texttt{ K }}$$\small{\texttt{ Y R D M F D}}$
The character 'K' is responsible for the 'Q' in "IQLUSION". The correct character, that has to stand at this position is 'W':
$\small{\texttt{02| Y Q T Q U X Q B Q V Y U V L L T R E V J Y Q T M }}$$\small{\texttt{ W }}$$\small{\texttt{ Y R D M F D}}$

2 ▶ The second error is in line 6:
$\small{\texttt{06| Q Z G Z L E C G Y U X U E E N J T B J L B Q C }}$$\small{\texttt{ R }}$$\small{\texttt{ T B J D F H R R}}$
The character 'R' is responsible for the wrong 'U' in "UNDERGRUUND". The correct character, that has to stand at this position is 'E':
$\small{\texttt{06| Q Z G Z L E C G Y U X U E E N J T B J L B Q C }}$$\small{\texttt{ E }}$$\small{\texttt{ T B J D F H R R}}$ 

According to Elonka Dunin [1], Sanborn said the following to those two errors:
"Those errors are deliberate.  It's not *what* they are that's so important though, as their orientation or positioning"
3 ▶ The third error is in line 17: 
$\small{\texttt{17| T P R N G A T I H N R A R P E S L N N E L E B L P I I }}$$\small{\texttt{ A }}$$\small{\texttt{ C A E}}$ 
The character 'A' is responsible for the wrong 'A' in DESPARATLY. The correct character, that has to stand at this position is 'E':
$\small{\texttt{17| T P R N G A T I H N R A R P E S L N N E L E B L P I I }}$$\small{\texttt{ E }}$$\small{\texttt{ C A E}}$

Since the wrong 'A' appears at position 11 in the plaintext, some people mark the eleventh character in the ciphertext (the 'L' in line 15) as the wrong character instead of the 'A'. There is obvious another error in this word, the missing 'E' between 'T' and 'L'.

KRYPTOS - Unaligned letters; Source [1]
4 ▶ Another abnormality can be found in line 15. The 'Y', 'A' and 'R' are not in line with the other characters. In the original cipher, their baseline is a little bit above the others (see image on the right). Here, i indicated this by making them a little bit larger. According to Elonka Dunin [1], Sanborn said the following to these non alignments:


"This is important"  



5 ▶ The ciphertext of K2 shown above actually decrypts to a plaintext that ends with
$\texttt{…FOUR SECONDS WEST ID BY ROWS}$
Since this are all perfect english words, nobody noticed the mistake several years. What happened is, that Sanborn admitted that he removed the character 'S' from the ciphertext and thought that this would cause the last characters to decrypt to garbage. If one reinserts the character 'S' at the correct position:
$\small{\texttt{14| D Q U M E B E D M H D A F M J G Z N U P L G E }}$$\small{\texttt{ S }}$$\small{\texttt{ W J L L A E T G}}$
one gets
$\texttt{…FOUR SECONDS WEST X LAYER TWO}$
Sanborn himself notified the Yahoo Kryptos Group about this mistake and acknowledged that X LAYER TWO is the correct plaintext end of K3. If this "accidential" decryption to ID BY ROWS is really accidential or contains some deeper meaning is unknown.

6 ▶ The Vigenère-Table on the right side contains in line 15 an additional character:

$\small{\texttt{13| L E F G H I J L M N Q U V W X Z K R Y P T O S A B C D E F G H}}$
$\small{\texttt{14| M F G H I J L M N Q U V W X Z K R Y P T O S A B C D E F G H I}}$

$\small{\texttt{15| N G H I J L M N Q U V W X Z K R Y P T O S A B C D E F G H I J}}$$\small{\texttt{ L}}$
$\small{\texttt{16| O H I J L M N Q U V W X Z K R Y P T O S A B C D E F G H I J L}}$

This creates in the last column, together with the two rows above and the one row below, the word 'HILL'. There are speculations that this is a hint towards the usage of the Hill Cipher for K4 [2]. I come back on this in Part 2 of this post.

7 ▶ The 'Q' at the end of K3. Is this character only added to make up a perfect rectangle of 14x24 characters for the transpositions cipher?

Given Hints

1 ▚ 2010 Sanborn revealed that, $\small{\texttt{N Y P V T T }} ≙ \small{\texttt{ B E R L I N}}$ (chars 64-69 in the ciphertext) in a one-to-one relationship. Sanborn said that during the time he constructed KRYPTOS, the fall of the Berlin wall took place and he obviously was influenced by the happening. This clue lifts the available methods to use from Ciphertext Only attacks to Known Plaintext attacks.

2 ▚ 2014 Sanborn gave another clue, namely that the characters 70-74 decrypt to $\small{\texttt{C L O C K}}$, i.e., $\small{\texttt{N Y P V T T M Z F P K }} ≙ \small{\texttt{ B E R L I N C L O C K}}$.


BERLIN CLOCK; Source: https://everplaces.com
I think one has to be cautious with this hints. The Berlin Clock is a special clock. Its a existing clock in Berlin, which Sanborn was really excited about. Created 1975 by Dieter Binninger it shows the time using lights via a basis-5 representation. If $\text{lights}(x)$ denotes the number of lighted fields in each of the four rows (the circle on top only counts the parity of the seconds), then the hours are calculated via: $\text{lights}(1)\cdot 5^1 + \text{lights}(2)\cdot 5^0$ and the minutes via:$\text{lights}(3)\cdot 5^1 + \text{lights}(4)\cdot 5^0$. Hence, the time that is shown on the right is 14:14.



In an interview with the New York Times in 2004 [3] he was asked about this clock and said:
“There are several really interesting clocks in Berlin”. He added, “You’d better delve into that particular clock,”
The last sentence "You’d better delve into that particular clock" reveals that this somehow is not only a plaintext word, but there is some deeper meaning of the clock. So, is he really revealing a plaintext section, or does he rather reveal a hint towards decrypting the entire message? The Berlin Clock uses lights to illustrate the time. Lights and in general natural forces are a central concept in his sculptures (See Cyrillic Projector) and even the plaintext of K1 and partly of K3 have references to lights and fire.

3 ▚ There are a lot more indirect clues that can be extracted from interviews given by Jim Sanborn and also Ed Scheidt. Good places to start are [4] and [5]. For instance, in an interview with WIRED in 2005, Sanborn stated:
"The answer [to K4] will be far more ambiguous. Of the part that's been decoded already there is certain ambiguity in the last few sentences and it's been open to interpretation, as has the whole piece."
4 ▚ An anonymous tipp/clue was given to Elonka Dunin in December 11,2003. She received a instant message with the content:

MolleeH [3:29 PM]: The key to Kryptos is "komitet."

The IM account MolleeH was deleted shortly afterwards. Molly Hale is the name of the (former?) head of the CIA's Public Affairs department. The word komitet is reasonable, since it stands for the K in KGB. And since the ciphertext of the Cyrillic Projector (another sculpture of Jim Sanborn from the early 1990s with a ciphertext, that got cracked in 2003) was even written in russian, a key that uses a russian word related to an russian agency makes absolutely sense.

Conclusion

Sanborn must have devised something really strange to make K4 that hard to crack. It was designed to be the hardest of the four ciphers but that it would last more than a quarter of a century was probably not expected. The CIA, the NSA and hundreds if not thousands of people attacked the cipher and nowadays even with sophisticated computer programs that try millions of possibilities in a matter of seconds. The idea for the used encryption methods came from Ed Scheidt, the former CIA director, who probably knew how to make things difficult. To increase the hardness of K4, Scheidt would probably rather think in lines of a cryptanalyst, i.e., trying to increase the algorithm complexity, the key space size or maybe the plaintext alphabet. In contrast, maybe an artist like Sanborn, has a focus that is more visual than theoretical. So he changed something totally unexpected, something a cryptanalyst would never ever thought about. Something computers couldn't find because they can not "see" it.

Go to Kryptos - The Cipher (Part 2)


[1] Elonka Dunin, Slides - Def Con 12, Jul. 14 - Aug. 01, 2004
[2] Craig Bauer, Gregory Link & Dante Molle, James Sanborn’s Kryptos and the matrix encryption conjecture, pages: 541-552, Cryptologica, published online: 27 Apr 2016
[3] https://www.nytimes.com/2014/11/21/us/another-kryptos-clue-is-offered-in-a-24-year-old-mystery-at-the-cia.html?_r=0
[4] http://kryptools.com/hints.htm
[5] http://www.elonka.com/kryptos/

4 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. Hi Christian, that Cryptologica reference no longer appears to be online. Could you send me a copy? mark.t.clinton@gmail.com

    ReplyDelete
  3. Hi, i only have a printed copy of the article, which is currently circulating somewhere in the department.

    ReplyDelete
  4. Hi,
    Artist Jim Sanborn said that the KRYPTOS cipher is very easy and should be broken after a few weeks. I think that this cipher is very easy and I broke it two years ago in two days. The effect of decrypting the Kryptos code is the LEEDS password. The slogan is related to the artist's youth. My email is leokadiaarent@gmail.com. Greetings from Poland https://www.facebook.com/leokadia.arentjaniszewska

    ReplyDelete