On 1/10/10 8:46 PM, sascha wrote: > On Sun, Jan 10, 2010 at 05:25:48PM +0100, M vd S wrote: > >> On 1/10/10 10:10 AM, sascha wrote: >> >>>> Maybe clock the illegal state forward N ticks and check each of the >>>> ancestors >>>> less than N + 5 clocks away from that new forward state whether there is >>>> one that produces the same keystream. If i am correct and the 2 compatible >>>> states are "close together" then they could very well be found that way. >>>> >>>> >>> to be more precise: >>> isn't any illegal state necessarily a dead end ancestor of some followup >>> state >>> >> yes - forward clocking is always possible >> >> >>> and thus the sibling of a valid state? >>> >>> >> No, consider (second bit is clock bit) >> 111111111 >> 011111111 >> 111111111 >> >> which cannot be clocked back. Clocking forward and back will always >> hit on this single invalid state. >> >> > if you clock a random state forward, does it open up new backclocking paths? > even if it does not work in the corner case above, with what probability does > it work with a random state? By it works i mean: find a sibling that produces > the same keystream. > > The figures I mailed earlier kind-of give this information, at least as far as the number of alternative (valid) backclocking paths are concerned:
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% So clocking forward once "heals" 84-75=11% of total states. But about the "same keystream" requirement... Considering healing a state with bit flips alone: For one thing, the offset between clock bits and the leftmost end of lfsrs is 10, 11 and 12 respectively. Healing a state with no direct ancestor would mean fiddling with the bit left of the clock bits. They are to influence keystream bits after 9, 10 and 11 lfsr clockticks respectively, so this must be compensated. This should be possible for states with the right clocking pattern right of the clockbits. This can however not been done without also interfering with the bits fed back in each lfsr. And I see no way to balance all these things without changing a bit to the keystream on *64* following clocks... Considering healing a state with a forward/backward clocking: (which would be beneficial to the value of the current tables, where possible) I thought it would not be likely to be possible, but I'm wrong. Consider state S: (third bit is clockbit, left = forward , right = backward clocking, dot = 0/1 irrelevant) .100 .011 .100 this cannot be reverse clocked. forward clocking leads to: F(s) 100. .011 100. clocking back along another pathway: state S' .100 ..011 .100 which is perfectly reversible (put in any bit you like at the dots) Clocking forward then by definition takes us along the same state as we would pass when clocking the illegal state forward (i.e. with the same lfsr offsets). The keystream would be equal, if the leftmost bits of lfsr2 in state S' are equal, so that's half the cases. This is the easy case, where the difference in lfsr offsets is that only one lfsr is off by one. In most cases, the forward/backward move will influence 2 rows twice, leading to one lfsr being shifted +1 and one -1. The puts the equal-bits requirement on leftmost bits of 2 lfsrs - 25% of the cases. Forwarding/reversing N times of course is possible as well but puts these requirements on even more bits. In practice a small brute force effort should try to find such valid states generating the same keystream, with maybe a 5% success rate of healing a failing rainbow table hit. (you would fix 11% of 84% in 25-50% of cases) This would I think be a viable strategy for using the existing tables, but will not be as effective as the strategy I proposed earlier. Regards, M _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
