Cryptic Crossword: Amateur Crypto and Reverse Engineering

The punchline to this story is that a few years ago the Times stopped scrambling their .puz files, making all this reverse-engineering work largely irrelevant.

(At the time I was using a modified version of the "xword" program in Debian's repo, which didn't detect whether the file was scrambled. In other words, it treated every letter as wrong because it didn't match the enciphered grid. I ended up hacking in some code to detect these files and disable the check/reveal features when playing them.)

This is a great and entertaining read about reverse engineering.

It's such a good read that this is almost beside the point... but, as it happens, I worked on and reverse-engineered this same "encryption" scheme (I hesitate to use the word) for an iOS app that never shipped. I just dumped the code (which seems to have been written in late 2008) up on github... it's old, and messy, but hey, maybe it's fun for someone:

https://github.com/davepeck/puzfile

Very cool rundown of the approach to trying to decode this. FWIW there is also a significant archive of information about the format here, including information about the scrambling: https://code.google.com/p/puz/wiki/FileFormat

Extremely methodical and determined approach. Especially analysis of the errors that partially successful approaches encountered. Well done.

>In a way this is just a restatement of Occam's Razor, but I like it because it clarifies why Occam's Razor is a good idea. It's not because simpler solutions are actually more likely to be true; they usually aren't. It's because it's almost always easier to improve a simple solution by adding complexity, than it is to improve a complicated solution by digging out a simple solution buried within it.

While the second part of that is an interesting observation, the first part is simply false. It basically comes down to prior probabilities and conjunctions. Every bit of new information implied by a hypothesis is another "and". It is a simple fact that P(X) ≥ P(X and Y), so the more conjunctions your hypothesis implies (the more complex it is) the lower its prior probability.

Wouldn't it have been easier to disassemble the program that works with these files, and analyze the code?

Man, reading little-endian binary formats makes my head hurt. I get why it's done that way, but what a nightmare for comprehending what you're reading.