On Jan 13, 2010, at 1:32 AM, M vd S wrote: > On 1/12/10 11:46 AM, Karsten Nohl wrote: >> This is one of the most effective optimizations we found so far. >> Thank >> you, M. >> >> I'm reading the data as: Clocking the cipher in each chain link by an >> additional 100 steps will decrease the state space from to 2^61.36. >> Given the available trade-offs, this will either make the attack 39 >> times faster (=2^(2*2.64)), the tables 6.23 times smaller (=2^2.64), >> or a combination between the two (see trade-offs below). >> >> When choosing performance over size, the pre-computation time roughly >> doubles due the additional 100 clocks; when choosing smaller tables, >> the pre-computation time stays about the same but produces less data. >> >> I would prefer to generate faster tables instead of smaller ones, >> still shooting for 1TB in tables. All other table parameters are >> affected by these new choices, of course. At 32 colors, we would need >> only 88 fairly large tables. Further increasing the number of colors >> decreases the number of tables and hence the ability to distribute >> the >> work while only improving the attack time by <10%. >> > > Please note that the color serves a new purpose as well now. We don't > want to curb in the initial (pre-100-round) state space, and > preferably > keep it at 2^64 - since it probably is this big in practice. > > Since post-100-round state space is at most 14% of 2^64 (considering > irreversible states), the keystream space and thus next-chain state > space cannot be bigger than that. > > The effective post-100-round state space seems to be smaller, since > the > expected number of ancestors for a post-100-round state is 13. > > So although the entire initial field of 2^64 samples is projected onto > 14% of 2^64 of keystream space, a *sample* of the initial field will > project onto an expected 1/13=7.7% of 2^64 keystream space. In other > words: some keystreams are preferred above others. (Luckily, this > holds > for keystreams observed in practice as well) > > > > The link to the color and round function is then that they serve to > map > the 7.7% of 2^64 space back to the entire 2^64 initial field, so we > don't get ourselves trapped in some subset. > > Unfortunately, I still haven't found or seen any hint as to how the > 7.7% > preferred keystream space looks like (my experiments on Sacha's good/ > bad > xor patterns have lead nowhere). In theory, 1/7.7% = 13 round > functions > could be enough. In practice, assuming that our round functions are > random to this subset, 32 colors will lead us to cover > > 1 - (1-7.7%)^32 = 92% of the initial 64 bit field.
This is an important consideration. If the number of different round functions is too small, we really might be missing some possible keys. However, two trends already mitigate this problem: 1. We try hundreds of times to find a hit in the tables. Theoretical coverage of 92% would be well sufficient. We even chose to only compute about 1% of that space anyway for efficiency reasons. 2. We use 32 round functions per table; each of which then covers a different 92% subset. The hundreds of tables will be able to reach almost every corner of the 2^64 key space. _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
