Back in 2007, I made a blog post entitled “Code Challenge”, where I put forth a code challenge.

Code Challenge | brainwagon.

Nobody took the challenge. But what was slightly odder was that I had no recollection of making this challenge, or even what type of cipher it was. The only clue that I had was that it was apparently in response to an episode of the increasingly mediocre television show Numb3rs.

So, I considered it a challenge sent from past Mark to future Mark. The first thing I had to do was to try to identify the type of cipher. I had made this posting in June of 2007, and I guessed that I would have been watching episodes from that season (season 3) but possibly in reruns. I relatively quickly located “The Janus List” and its “straddling checkerboard cipher” as the likely method. Indeed, reading the description of the cipher (try this blog entry for details) it began to come back to me.

So, I tried to think of how to crack it. Here’s the insight. The straddling checkerboard cipher is essentially a simple subsitution cipher, except that each character is either encoded into one or two characters. What makes it easy is that there are eight single character letters, and twenty double character letters, but all double character letters start with one of the two non-single character letters. So, you can proceed by guessing what those two prefix characters are, and then scanning through the message. If you get more than 26 (or 28, if you include period and slash as most straddling checkerboard implementations do), then you know you haven’t gotten the right answer. But a quick look at the single letter frequencies in my case indicated that the characters 6 and 8 were vastly more frequent than the other characters, so I guessed that those were the right characters. When I busted the cipher up into characters, I ended up with 23 distinct symbols, which seemed entirely appropriate. I could then assign a random letter to each of those 23 symbols, and I’d have a simple cryptogram.

Here’s the resulting cryptogram:

WRAFSIFFKVIQKFINCOMGWIDUFANVKFWKVVIOIDCRICEIOBHKODCAGRIOQRACRMHUGOHBKBT
MRKJIKTOIKDMLAVUOIDHUWALMHUKOIOIKDANVWRAFCHNVOKWUTKWIMHUOFITLHNBIANVIPC
IIDANVTMCTIJIOKNDWINKCAHUFADHUBWKNMHNIQATTKCWUKTTMQHOERKODINHUVRWHKCWUK
TTMDICHDIWRAFSIFFKVIFUCCIFFLUTTM

Mind you, I might have accidently assigned a letter to itself here, so it’s not quite like a normal cryptogram. But it isn’t hard to make some guesses. ‘I’ is the most common letter, so is probably E. The last three characters are TTM, which implies a double letter right at the end, which suggested LLY. The double letter digraph FF occurs three times, which suggests that F might map to S. Putting these together makes the last word to look like SuccESSluLLY. Wow! U and C both look like they map to themselves. L is F. The message starts TraS, which suggests THIS. R becomes H, A becomes I. Now we have traction, K is A, S is M, V is G…

THISMESSAGE.ASE.C.Y.TE.USI.GASTAGGE.E.CHEC.E...A..CI.HE..HICHY.U....A.L
YHA.EAL.EA.YFIGU.E..UTIFY.UA.E.EA.I.GTHISC..G.ATULATEY.U.SELF...EI.GE.C
EE.I.GLYCLE.E.A..TE.ACI.USI..U.TA.Y..E.ILLACTUALLY....HA..E..UGHT.ACTUA
LLY.EC..ETHISMESSAGESUCCESSFULLY

It’s a short skip and a jump to the complete decode:

THISMESSAGEWASENCRYPTEDUSINGASTAGGEREDCHECKERBOARDCIPHERWHICHYOUPROBABL
YHAVEALREADYFIGUREDOUTIFYOUAREREADINGTHISCONGRATULATEYOURSELFONBEINGEXC
EEDINGLYCLEVERANDTENACIOUSIDOUBTANYONEWILLACTUALLYWORKHARDENOUGHTOACTUA
LLYDECODETHISMESSAGESUCCESSFULLY

Apparently, I was tenacious enough.

The other day, my friend Jeff sent me an email detailing the latest benchmarking of his new 8 core Intel box. He had written a program to compute return rates for all possible draws in video poker. A few years ago, this program had taken a month of computer time to complete, and he wondered how how quickly it would run on his new box. The answer: around 12 hours.

This got me thinking back to my experience using Simon Singh’s “Cipher Challenge” that I did back in 2000. I hadn’t tried to solve Stage 9, because at the time it seemed a daunting task, requiring computational resources far in excess of what I had at the time. But Jeff’s email got me thinking, so I decided to run an experiment: how long would it really take?

I didn’t have a fast, optimized DES implementation of my own, so I decided to dig around. It turns out that OpenSSL contains an implementation of DES, and a few minutes of writing some code verified that it could actually decode the challenge message. So, the question was: how long would it take to break this code?

Stage 8 had revealed 8 of the 56 key bits, leaving a keyspace of 2^48 entries left (about 281 trillion entries). So, I coded up a small test program that did a million DES_set_key calls, followed by a decryption of the message. I found that it took about 21 microseconds to do a test. On average, we’ll search half the keyspace (around 140 trillion keys) before we find the key, so if you multiply it out, you get…. 93.65 years. We have eight cores, which brings it down to about 11.7 years. Not so good…

But here’s the thing: we probably don’t have to really decode the entire message. If we believe that the output is ASCII, then each of the output bytes should have the top bit clear. Any block which doesn’t have this feature indicates our key is on the wrong track. The odds of getting all those bits clear by random chance is one in 256. If we try to only decode the first six blocks, then our chance that we got something wrong is about one in 2^48th, which is just about the size of the keyspace, so we’d probably wouldn’t see very many false positives. If we modify the rule to just check the first six blocks, then it only takes about 1.16 microseconds to do a key set and a decode. Now my single machine can get the run time down to 236 days. Still pretty darned slow actually. It’s clear that openssl’s DES implementation isn’t really up to the task. I suspect that there are software implementations which are several times faster than this. I’ll try to dig one up and see what could really be done.

Addendum: When I got home, I dug up a copy of Eric Young’s libdes library, and ran some basic speed tests using the “speed” program that’s part of the distributions. I wasn’t running it on the same machine, so the numbers aren’t directly comparable, but my home machine quite a bit slower. Nevertheless, I got some interesting numbers:

[chessboard] % ./speed
Doing set_key for 10 seconds
29270676 set_key's in 10.00 seconds
Doing des_encrypt's for 10 seconds
54502334 des_encrypt's in 9.93 second
Doing des_cbc_encrypt on 1024 byte blocks for 10 seconds
402292 des_cbc_encrypt's of 1024 byte blocks in 10.00 second
Doing des_ede_cbc_encrypt on 1024 byte blocks for 10 seconds
146870 des_ede_cbc_encrypt's of 1024 byte blocks in 10.01 second
Doing crypt for 10 seconds
1731166 crypts in 9.92 second
set_key            per sec =   2927067.60 (    0.342uS)
DES raw ecb bytes  per sec =  43909231.82 (    0.182uS)
DES cbc bytes      per sec =  41194700.80 (    0.194uS)
DES ede cbc bytes  per sec =  15024463.54 (    0.532uS)
crypt              per sec =    174512.70 (    5.730uS)

If you add the set_key time to 48 times the raw ecb encode, you get about 9 microseconds. Using both of its two cores, that works out to about 20 years. That’s about 31 times slower, or nearly 8x slower per core.