Progress on the Chaocipher…

My brain has got a bug now. It’s called Chaocipher.

Despite the fact that I’m spending my days off with my family, I find that in my odd moments my brain keeps leaping back to Byrne’s cipher. The other night I implemented the basics of key recovery using a chosen plaintext attack (if you have both plain and cipher text, recover the key). It proceeds according to the following idea: initialize a Chaocipher machine with all ‘?’ in every entry. Then, for every cipher/plaintext pair, check to see if the cipher or the plain text letter has already been placed in the wheel. If it has, then they better be in the same slot in each of the respective wheels. If they aren’t, then the placement is bad, and you need to backtrack. If only one has been placed opposite a ‘?’, then you fill in the ‘?’ and proceed to the next pair. If neither has been placed, then you have to try all places where two ‘?’ are opposite one another. If you manage to exhaust the input, then you probably have the right wheel, so I then run the machine in reverse back to the beginning to recover the initial key settings.

I’ve had some success on this with some of my own test cases, but have not managed to crack Exhibit 1 or Exhibit 2 on the Chaocipher Clearing House website. I’m not sure if this is due to problems in my own implementation or a more general problem. I haven’t worked on trying to generalize this into a cipher-text only cracking program, but I suspect that it’s possible. The techniques that I remember from cracking the Enigma don’t really apply here, since the permutations are dependent on the plaintext. I have a couple of ideas that I’ll be pondering during the three plus hours of driving that I am going to do today.

I left the solver working on Exhibit 2. It’s searched about a billion keys in the five minutes or so I’ve had it running: we’ll see if it can solve the cipher by the time I get back tonight.

Addendum: it searched about 20 billion nodes, before returning a partial key that properly recovers the first 51 characters of the plaintext. Not sure if there is a problem in my implementation or in the transcript of Exhibit 2. I’ll think about it more over the next few days.