Sunday, July 31, 2011

Yay me

I moved into the top 10 this week at MTC3, specifically into 3rd place, as well as #1 for the month and #1 for the year. I am probably also #1 for last month, retroactively, as all this is aided by the fact I was finally awarded points for the level X cipher I solved in June: a historical cipher by the KKK from the 1920s or so. Seems they didn't think anyone would ever solve a level X so they never coded that as an option :)

I think my next few posts will be historical ciphers that remained unsolved for hundreds of years but are solvable within minutes with modern, open source tools. Plus the constant updating of my Kryptos post. I intend for that to be quite thorough.

In the mean time I am off to Black Hat and DEFCON. Vegas baby!

Saturday, July 23, 2011

Kryptos

I was obsessed with the 4th Kryptos cipher for a few months and determined to solve it. However, the more I understood the artist Jim Sanborn, and the more I understood the cipher, the more I came to believe it is simply impossible to solve though cryptanalysis. Even if I programmed every cipher into a brute-force cracker and ran them all for eternity, which I considered, I believe that would not help. So I've kinda lost interest. (Edit: the bug came back a few months later, I'm going to try a little longer.) However, before moving on I thought I'd share everything I have learned and post it in one spot instead of spread all over the Internet intermingled with conspiracy theories and alphabet soup.

Note: This is very fact-dense and link-sparse article. I intended to add more citations, but they are spread so far and wide it was easier to just type up what I knew and get to the links later. Feel free to request links to anything I claim and I will update this blog with them.

The Sculpture

Kryptos contains 4 ciphers (refereed to as K1 through K4) on one side and an over-sized keyed Vigenère tableau on the the other. These are all carved into a thick copper plate, installed with a pond and petrified wood and strata of granite and copper with Morse code palindromes etched upon them. There are suggestions from the artist that once the 4 ciphers are solved there is a larger puzzle. Through mistakes and counting white-space and punctuation and an extra L in the tableau, the two sides have the same number of characters -- 869 (11x79) each. That is a lot of carving.

Update: That extra L was added for "aesthetic reasons." (read that somewhere, can't find a link though... did I imagine it?) Either kerning was adjusted to make room for the L, or mistakes in kerning were made requiring this L. Sanborn has left this L off of the models of Krypto he sells and says it is not important for solving Kryptos, so that suggests it was a kerning mistake. Or... he could just be OCD and having 869 characters on one side and 868 on the other was unaesthetic. I can respect that.

K1

K1 is a keyed Vigenère cipher. The keyed Vigenère tableau from the sculpture is used with the password PALIMPSEST (which means layers of writing, like from the re-use of old parchment, or maybe like the layers of Morse code and granite slabs in the sculpture, or maybe it's a hint to use part of the sculpture as a OTP). It was broken both by hand and by computer years ago, and is partially broken by a slight modification of the code found here (though using bi-grams and tri-grams could greatly improve the results, remind me to modify this code some day...). The solution is:

BETWEEN SUBTLE SHADING AND THE ABSENCE OF LIGHT LIES THE NUANCE OF IQLUSION

Some Kryptos fanatics will tell you that this and all misspellings are intentional and have some mysterious meaning (more on this later), but when you look at Sanborn's original paperwork it seems to be completely accidental.


(Click to enlarge.)

Sanborn misspelled "PALIMPCEST" and thus altered the ciphertext, resulting in "IQLUSION" when deciphered rather than the "ILLUSION" as written on the worksheet. He also misspelled it "PALIMPCEST" where he wrote the keyword at the top of the page. It also looks like he wrote "PLAIMPCEST" many times on the worksheet before correcting the C to and S in all but the last instance. This, to me, is 100% confirmation that this misspelling was completely accidental. (Again, I hear the distant screams of the fanatics, more on this later.)

K2

The second cipher uses the same algorithm and the same keyword, but with the password ABSCISSA, which seems to refer to the coordinates contained within the plaintext. It was solved by the same people at the same time as vaguely referred to earlier, and is solved instantly by the code mentioned above. It contains two mistakes which I have colored red:

The plaintext reads:

IT WAS TOTALLY INVISIBLE HOWS THAT POSSIBLE ? THEY USED THE EARTHS MAGNETIC FIELD X THE INFORMATION WAS GATHERED AND TRANSMITTED UNDERGRUUND TO AN UNKNOWN LOCATION X DOES LANGLEY KNOW ABOUT THIS ? THEY SHOULD ITS 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

Mistakes

Again, I can hear the Kryptos fanatics screaming at my blasphemy. Repeating this heresy once got me censored from the moderated Kryptos yahoo group, and here's why. In 2003, a 2nd-hand report claimed:
"He said that the misspellings were deliberate, but it was less important *what* they were, but, "it's more the orientation of those letters that's useful there." Later on in the evening, he repeated the point, saying that it was the "positioning" that was important."
This "fact" has been repeated by the press, for instance by the WSJ on 5/27/2005, and has become gospel. Note that "the misspellings" was never defined, but is believed by some to mean "all five misspellings," and to others it means "four misspellings except the misspelling that he later admitted was accidental", or perhaps it means "the misspellings in K3 which we were talking about at the time but that context was not mentioned in the 2nd-hand report." Though later context in that report suggests they were talking about K1 and/or K2, but as it seems obvious the error in K1 was accidental so perhaps Sanborn is still unaware of the error in K1 and was referring only to "undergruund" in K2?

This belief that all mistakes were unintentional is most interesting, since 3 years later on April 19, 2006 Sanborn admitted he hasn't been paying attention to the decipherments, even when they were personally presented to him in a powerpoint presentation by Elonka Dunn. He said he had just noticed he made a huge, unintentional mistake: that "ID BY ROWS" should have really been "X LAYER TWO" as he left out a character. That mistake, and the fact he didn't notice it in the decipherments for years and years despite them being projected in front of his face, does not speak well for his attention to detail.

Still, Kryptos fanatics will tell you that the other mistake in K2, "UNDERGRUUND," was intentional. This is also an odd claim because of the following evidence. First is his original worksheet:

This shows "UNDERGROUND" spelled correctly. Of course this does not tell us if he accidentally carved the wrong letter, understandable when carving hundreds and hundreds of letters, or if this was intentional for some mysterious reason. However, Sanbron included this cipher on another sculpture named Antipodes, and he did not repeat this mistake, but instead carved the letters exactly as shown on the worksheet. This seems to strongly suggest the mistake was accidental (I know Kryptos was carved by hand, perhaps Antipodes was done by a machine, far faster and mistake-free?) or maybe the mistake doesn't work with the geometry on Antipodes. Again, do not discuss this on the moderated email list, it is verboten. Instead please stick to rambling alphabet-soup claims that Nostradamus both predicted, and solved, K4 -- those are welcomed with open arms.
Edit/update: Elonka's photo of Antipodes. I circled location of missing K2 error.

So, it seems quite certain all of the mistakes in K1 and K2 were accidental, but reports claim Sanborn was just as certain they were not. So, there you go, clear as mud. Maybe that's why it's a banned subject.

K3

This cipher is a transposition cipher. It has been solved 3 different ways: one that starts with an offset and skips a period of characters, one that involves reading stuff backwards with a staircase pattern and shuffling with the keyword KRYPTOS (to which Sanborn said must be "a by-product of the original matrix system"), and one that seems, in my opinion, to be much more likely and matches Sanborn's affinity for "matrices."

Write the cipher in a 24x14 grid. (Note, there are three raised characters which I have written in lower case, plus the N in front of them which is offset(which no-one ever seems to mention/notice)):

ENDyaHrOHNLSRHEOCPTEOIBI
DYSHNAIACHTNREYULDSLLSLL

NOHSNOSMRWXMNETPRNGATIHN
RARPESLNNELEBLPIIACAEWMT

WNDITEENRAHCTENEUDRETNHA
EOETFOLSEDTIWENHAEIOYTEY

QHEENCTAYCREIFTBRSPAMHHE
WENATAMATEGYEERLBTEEFOAS

FIOTUETUAEOTOARMAEERTNRT
IBSEDDNIAAHTTMSTEWPIEROA

GRIEWFEBAECTDDHILCEIHSIT
EGOEAOSDDRYDLORITRKLMLEH

AGTDHARDPNEOHMGFMFEUHEEC

DMRIPFEIMEHNLSSTTRTVDOHW


Rotate this 90 degrees clockwise

DAEGIFWQEWRNDE
MGGRBIEHONAOYN
RTOISONEEDRHSD
IDEEETAETIPSHy
PHAWDUTNFTENNa
FAOFDEACOESOAH
ERSENTMTLELSIr
IDDBIUAASNNMAO
MPDAAATYERNRCH
ENREAEECDAEWHN
HEYCHOGRTHLXTL
NODTTTYEICEMNS
LHLDTOEIWTBNRR
SMODMAEFEELEEH
SGRHSRRTNNPTYE
TFIITMLBHEIPUO
TMTLEABRAUIRLC
RFRCWETSEDANDP
TEKEPEEPIRCGST
VULIIREAOEAALE
DHMHETFMYTETLO
OELSRNOHTNWISI
HEEIORANEHMHLB
WCHTATSEYATNLI

Reform it into a 8x42 grid

DAEGIFWQ
EWRNDEMG
GRBIEHON
AOYNRTOI

SONEEDRH
SDIDEEET
AETIPSHy
PHAWDUTN
FTENNaFA
OFDEACOE
SOAHERSE
NTMTLELS
IrIDDBIU
AASNNMAO
MPDAAATY
ERNRCHEN
REAEECDA
EWHNHEYC
HOGRTHLX
TLNODTTT
YEICEMNS
LHLDTOEI
WTBNRRSM
ODMAEFEE
LEEHSGRH
SRRTNNPT
YETFIITM
LBHEIPUO
TMTLEABR
AUIRLCRF
RCWETSED

ANDPTEKE
PEEPIRCG
STVULIIR
EAOEAALE
DHMHETFM
YTETLOOE
LSRNOHTN
WISIHEEI
ORANEHMH
LBWCHTAT
SEYATNLI


Rotate this 90 degrees clockwise

SLOWLYDESPARATLYSLOWLYTHEREMAINSOFPASSAGED EBRISTHATENCUMBEREDTHELOWERPArTOFTHEDOORWA YWASREMOVEDWITHTREMBLINGHANDSIMADEATINYBRE ACNINTHEUPPERLEFTHANDCORNERANDTHENWIDENING THEHOLEALITTLEIINSERTEDTHECANDLEANDPEEREDI NTHEHOTAIRESCAPINGFROMTHECHAMBERCaUSEDTHEF LAMETOFLICKERBUTPRESENTLYDETAILSOFTHEROOMW ITHINEMERGEDFROMTHEMISTXCANYOUSEEANyTHINGQ

I colored the YAR red and the N green for readability, now a "ray" from the upper left-hand side. Perhaps "ray" is a hint for the whole puzzle, or maybe K4. Maybe the N means something, given the compass rose on site, maybe not.

Note there are two misspellings in the word "DESPARATLY" which should be "desperately" -- one letter longer and with an E instead of the first A. Clearly if the plaintext was one letter longer this encryption/decryption scheme would not work, so it seems this must be intentional, and perhaps this is the intentional misspelling Sanborn referred to. From that 2003 report:
"I asked him if the "desparatly" typo was deliberate or accidental, and he
declined to answer."
(Yet he answered about the other mistakes? Suggesting there are other intentional mistakes? Or he's nuts?) But why change an E to an A? Why would that be important? Is it a random mistake he was embarrassed about? Is this plaintext somehow used to decrypt K4?

The latter seems to be suggested from Sanborn's worksheets, as shown in an episode of NOVA:



Does "P" refer to "plaintext" and "C" to "ciphertext? Is this the mask or part of the encryption in K4? Or am just I seeing what I want to see?

K4

So this is all intriguing and there seems to be lots of hints and the earlier ciphers were pretty easy with modern tools, and Sanborn even announced the location of the plaintext letters "BERLIN" in K4, so why give up? Well, according to hints Sanborn and his CIA crypto-teacher have given, K4 is enciphered in a two step process. The first step is a "mask" to "hide the plain text letter frequencies." Then that encrypted text is encrypted again. And did I mention the final text is only 97 letters long?

And Sanborn has alluded to the mask not having anything to do with cryptography or things us nerds would think to analyze, but is more of a subjective, artistic thing.

Now, if it was something as simple as a mono-alphabetic substitution, one could simply try every key of a/every cipher for part 2, and then look for English-like letter frequency distributions and break K1. (I tried this to some degree, and was considering a larger scale before I got disillusioned.) But that is not the impression I get as to what the mask is. I'm guessing it is some sort of poly-alphabetic pattern, using characters from other parts of the artwork (he hinted that all the characters are there or something) and with only 97 letters this is a lost cause until more hints are released. In fact, if I am right that the mask is poly-alphabetic, then even if the entire plaintext was released I still don't think it would be possible to determine the two ciphers used. We would need hints specific to the mask.

Edit: perhaps I was being too hasty, and I also confused the author of a quote about the mask (I should really find more of those links to prevent more mistakes...) It was Scheidt who said the other ciphers didn't hide the statistics, and he was right. An amateur might think a keyed Vigenère cipher hides the stats, but not an ex chairman of the CIA. So to "mask" those doesn't necessarily mean using a two stage cipher. It could mean a cipher like ADFGX, or perhaps previous parts of the cipher are used as a One Time Pad (is that subjective and artistic?), that would certainly mask that statistics. I even had a few ideas on that I will add in a future blog...

Edit: even more Antipodes scribbles. I reversed images taken from the inside so you can see the full text of: K3, K4, K1, K2, K3, K4, K1, and the beginning of K2. The error in K1 appears twice. The error in K2 is not present twice. The missing S at the end of K2 is still missing from the one ending of K2.
Antipodes top and center
Antipodes center and bottom. Not there is overlap in the images (partial K2 and K3)

Friday, July 22, 2011

Mystery Twister

I am so addicted to this crypto challenge website! It has been occupying way too much of my time lately, but luckily I am almost out of level 1 challenges and the level 2s take a lot longer to work out, versus obsessively knocking out one after another. My big accomplishment this week was getting into the top 20 and having the most level 1s solved. If I could just get that last one...

Anyway, a new RSA challenge opened up today, beat it in 0 days and get double the points :)