On Tue, Jan 18, 2011 at 07:21:40PM +0200, Tari Mrkis wrote: > Thank you for your answer.It was obvious but I couldn't see it... > I can't see this one too: how do you get from 2^64 keystream space to 2^53 > stored data points?From what I understand from the 2^64 states > 2^3 states can be excluded due to the fact that after the 100 steps, > only 16% of the states can exist.
cut a factor of 8 (all invalid states through 100 forward clocks) cut a factor of 1.5 (because you can find A5/1 states in the neighbourhood of a match through forward-then-backward clocking that also produces the keystream that you are interested in) cut a factor of 204: each LAPDM frame gives you 4*51 64bit long segments of keystreams which all can produce a match in the table. 2^64 / 8 / 1.5 / 204 = 2^52.7 now that ignores the collisions that exist between a large number of the states in the table, but that is a different question, and you also cannot expect a 100% success rate for the same reason. the number of states in the tables is 6.2B * 2^15 * 40 of which a fraction are collisions. i cannot say how many there are, but i know that i threw away 2 billion chains per table because a collision happenen under the same round function and produced a chain merge. > From the remaining 2^61 how you end up at 2^56.5 or 2^57? > Or is it that you assume that 2^57(2^56.5) gives enough success rate with > the given lookup keystreams and so it suffices, and from that point on > taking > into account the 100 steps you end up at 2^53? > Thank you. > > On Fri, Jan 14, 2011 at 10:43 PM, <sascha.kriss...@web.de> wrote: > > > On Fri, Jan 14, 2011 at 05:28:27PM +0200, Tari Mrkis wrote: > > > Hi, > > > > > > I haven’t understood a very basic point. > > > > > > If there is the possibility of backclocking why do we have to build the > > > rainbow tables to begin with. I understand that if there is a hit in the > > > > It is not possible to clock back keystream. You have to know a A5/1 > > register assignment to be able to reach neighbouring states through > > forward/backclocking. You cannot know what the A5/1 register content > > is from examining keystream (because it is a cryptographic one way > > function). > > So with the time memory tradeoff attack you can reverse that function > > and end up anywhere in the state space of internal A5/1 registers along the > > path that was taken to generate said keystream; from where > > it is trivial to clock to a point where the frame number has been removed > > from the state. > > > > > table, either this is the state we are looking for (next to get rid of > > the > > > frame number) OR this state can be forward clocked for 100 times and then > > > backwards to reach some more valid states any of which can be the desired > > > one. So why don’t simply backclock the 64 bit sequence, find the valid > > > states and then backclock them all for 100 without the need to build > > tables. > > > From what I understand there is not a huge numbers of states, 1.4 states > > on > > > average for the 100 forward-back clocking, so for the 64 backwards > > clocking > > > this number may increase a little but not too much. > > > > > > Also one more question; the total size of the constructed tables is about > > > 1,7 GB with 40 tables of 42 GB each, is it right? > > > > 48 tables of 42GB each. > > _______________________________________________ > > A51 mailing list > > A51@lists.reflextor.com > > http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51 > > > _______________________________________________ > A51 mailing list > A51@lists.reflextor.com > http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51 _______________________________________________ A51 mailing list A51@lists.reflextor.com http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
