On Sun, Jan 10, 2010 at 05:15:46PM +0100, M vd S wrote: > On 1/9/10 7:30 PM, sascha wrote: > >Help me understand this please: > > > >Not all of the 2^64 possible A5/1 register states is valid, considering > >the 100+ extra clockings before. Ok that makes sense. > >You say 40% out of all states can be clocked backwards more than 16 times, > >lets assume that is also the number of states that can be clocked backwards > >100+ times (do you have a better number here?) > Here you go: > > 16 back: 57% illegal states > 32 back: 68% illegal states > 48 back: 74% illegal states > 64 back: 78% illegal states > 80 back: 82% illegal states > 96 back: 84% illegal states > > These numbers are based on one chain. (de001bc0006f0000 [0] -> > 36dc483fb4fe0000) > > I verified superficially with chains > de001bc034563200 [0] -> d59ebd1df40d8000 > f1234678e5f7d600 [0] -> 61df56b387178000 > > and both give the same pattern. Clocking back 150 times (the maximum > in practice) gives 89% illegal states.
thanks > > Apart from the optimization, we can also observe that the state > space converges to 2^64 * (1-84%) before generating the keystream. > This must also mean that only 16% of 2^64 possible 64 bit keystream > can exist. I wouldn't know how this can be of value to us right now, > but it is worth noting. well it is of great value: our tables need only be 16% the size they were before. at the cost of 2-3 times more computational effort. > > >Our keyspace shrinks down to 2^64 * 0.4, provided that we can eliminate the > >illegal states. 16 extra forward clockings would slow down the table > >generation by 25%, do you think this would rule out the majority of the > >illegal states? I think backclocking is out of the question for the table > >generation, as it would slow down everything too much. > There is no real need for backclocking to find illegal states. A > 32kb lookup table will suffice to know if a state can be clocked > back 6 times (2^(3*6) bits = 2^15 bytes). This would rule out some > 47% of states as illegal, leaving 37% illegal states alongside 16% > legal states. This would be a factor 2 improvement at the cost of > 32kb of memory and a fairly simple lookup. But for bitsliced > implementations this maybe isn't so easy at all. > > Forward clocking to sanitize the state is something I tried, but we > must be sure that doesn't lead to another subset of state space > which does not encompass the actual observed state space in > practice. > > Since there is no need to generate keystream for these forward > clockings, the cost might be slightly less than that for > keystream-generating clocking. Sanitizing only illegal states by > forward clocking doesn't sound like a great idea. > > > Simply clocking forward N times modifies the 96 backclock figure as follows: > N S (96 back illegal states) > 0 84% > 1 75% > 2 72% > 4 68% > 8 63% > 16 53% > 32 37% > 64 12% > 96 0% > > defining cpu cost factor as (1+N/64), and table efficiency factor as > (1-S(N))/(1-S(0)) (so for N=4 we get 32% legal states which is twice > 16% at N=0, and thus eff.factor=2) > > and taking total efficiency as (1-S(N))/(1-S(0)) / (1+N/64), we get: > N S cpu cost table eff total eff > 0 84% 1.00 1.00 1.00 > 1 75% 1.02 1.56 1.54 > 2 72% 1.03 1.75 1.70 > 4 68% 1.06 2.00 1.88 > 8 63% 1.13 2.31 2.06 > 16 53% 1.25 2.94 2.35 > 32 37% 1.50 3.94 2.63 > 64 12% 2.00 5.50 2.75 > 96 0% 2.50 6.25 2.50 the extra time needed is N factor 32 1.47 64 1.89 96 2.3 not xoring, not storing in the extra rounds. total execution time of a 8192 operations kernel taken as basis. _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
