C[omp]ute

From: andrew cooke <andrew@...>

Date: Fri, 10 Jan 2014 20:03:57 -0300

I just got this to work!  Yay!  It's a search of cipher state.  Brute force
(depth first search of the space), but using the lack of correlation between
bits (from the lack of rotation) to make things much more efficient (going
from O(2^n) to something much more like O(n).

The final trick was an adaptive filter.  You can't check *all* characters are
encoded correctly as you search, so you need to select some subset.  I made
that subset adaptive (injecting a new random input every 1000 "loops"), which
helped avoid exploring "dead ends".

Also, of course, efficient code for the central loop.  I think I have
everything (code and lookup tables) inside the L1 cache on my Celeron (64kB)
and am trying ~3 million values every ~10s.

So in about half an hour (over dinner) it solved 5 rounds at 32 bits, that's
12*32 = 384 bits of state (2^384 is 39,402,006,196,394,479,212,279,040,100,
143,613,805,079,739,270,465,446,667,948,293,404,245,721,771,497,210,611,414,
266,254,884,915,640,806,627,990,306,816) with just ~30*60*3000000/10 =
540,000,000 evaluations.

Andrew