10:10 am, 21 Jan 07
legality of decryption
Yesterday 
xaosenkosmos, 
danerat, and brad came by for some .PUZ format hacking. We figured out some new bits and also hacked my JS viewer into a multiplayer state (with a lot of Gobby's help), but now we've got an interesting side project:
PUZ files typically (always?) have the solution contained within them. Newer .PUZ files have the solution, but it's been "scrambled" (encrypted?) and have associated keys to decrypt them. It seems like figuring out this algorithm would be fun -- using the above multiplayer game we painstakingly "gathered" some plaintext versions of puzzles (their encryption scheme has a side channel attack in that the cyphertext is accompanied by clues as to what the plaintext is :P) and we also have the keys (which are in a fairly limited space: almost always in (1000,10000)). We poked around a bit and found it's not a simple substitution cypher (character distribution of cyphertext is nearly random) but it can't be that bad. Surely someone on LJ would love to take a crack at it!
So here are some problems:
xaosenkosmos, danerat, and brad came by for some .PUZ format hacking. We figured out some new bits and also hacked my JS viewer into a multiplayer state (with a lot of Gobby's help), but now we've got an interesting side project:PUZ files typically (always?) have the solution contained within them. Newer .PUZ files have the solution, but it's been "scrambled" (encrypted?) and have associated keys to decrypt them. It seems like figuring out this algorithm would be fun -- using the above multiplayer game we painstakingly "gathered" some plaintext versions of puzzles (their encryption scheme has a side channel attack in that the cyphertext is accompanied by clues as to what the plaintext is :P) and we also have the keys (which are in a fairly limited space: almost always in (1000,10000)). We poked around a bit and found it's not a simple substitution cypher (character distribution of cyphertext is nearly random) but it can't be that bad. Surely someone on LJ would love to take a crack at it!
So here are some problems:
- The puzzles are surely copyrighted. Is posting plaintext+cyphertext+key a problem? It's not like you can play them without the clues...
- Is it violating the DMCA to do this? We're not circumventing copy protection, and it's all just for hobbyist fun anyway...
This made me laugh.
Of course, it's a beautiful illustration of the computational futility of most of DRM. I wonder if Lessig or Doctorow et al. would like to use that example.
Throwing (tiny) money at the problem
To sidestep the copyright problem of distributing plain- and cipher-text: everyone could just subscribe to the NY Times crossword site, which is a treasure trove of these things. You'll get a new ciphertext every day, along with yesterday's plaintext.i'm looking into implementing a crossword program like across lite or black ink, and one issue is decrypting solutions. have you made any progress in reverse engineering their algorithm?
the following seems like a natural first shot: start with some trivial puzzle (say all \0s) and a trivial key (say all \0s again) and see what happens. then perturb the key one bit at a time and perform a differential cryptanalysis against the entire algorithm (instead of the key). this document describes how to construct your own puzzles for the analysis.
i was going to start working over easter weekend... just checking in for the state of the art!
I never finished this doc: http://code.google.com/p/puz/wiki/FileFormat but we also figured out the tagged strings section at the end.
I've actually never ran the Across Lite software -- all the work I've done has been just on the files.
If you figure it out, I'd love to hear about your results.
This is a great project
I hope you get somewhere on this. I would be very curious to find out what their scrambling algorithm is. Any progress?- Alex Boisvert
http://www.alexboisvert.com/