[difficulty: 6][protection: multivariate]
I'm pleased to report that after nearly half a year of obsession, SDDecoder is solved. It is one of the most enigmatic crackmes posted to crackmes.de IMHO.
NNE92-NS62P-TZ9QC-NGEII-6UJ4V (id: 0xDDDD)
PMOFN-WJIJW-DQ9T9-IOM62-RXIIR (id: 0xBBBB)
FGU6J-WAHFJ-T6ZD7-CBKOQ-6LJHD (id: 0x9999)
JT2CQ-6HY7O-6B3DJ-HIAJC-BEC2Q (id: 0x5678)
My attack should work in general for any overlapping s-box scheme. The first implementation was made against SDD64 (the very reason SDD64 was written!) and can generate every possible key for an arbitrary ID. While converting this to 128-bit, I made some error because some id's for the real SDDecoder won't solve, and without the private info, it's difficult to trace why.
It took about 2 single-machine days to extract the private data needed from the public key, and each key generation takes a few minutes (the ones that succeed). When the keygen is debugged I'll submit a solution.
Jan 13th, 2010 EDIT: Solution uploaded! SDDecoder JR v2 falls even better to this same attack, so I downgraded the difficulty to 2... I'm off now exploring other MQ stuff (original C*, HFE, Oil and Vinegar, etc.) Some bonus keys:
Jan 27th, 2010 EDIT: Not challenged enough? See how SDDecoder (DRegZ) was built, and try JRegZ and QRegZ at http://www.webalice.it/giuliano.bertoletti/lca.html.