The table parameters are contingent on: A. Key space B. Available storage C. Required success probability D. Number of key stream samples
-Karsten On 19-May-10 9:50, satwik goud wrote: > hello > iam a research student, actually i want to understand TMTO attack on a5/1 > stream cipher > i have only one pc with me i had taken a small lfsrs of length 3,5,8 and > irregular clocking after 25 regulat clocks for this algorithm i want to > impliment TMTO attack can u please help me for the table parameters like > no. of columns and no.of DP bits and no of chains . > thanks > > On 18 May 2010 15:30, <[email protected]> wrote: > >> Send A51 mailing list submissions to >> [email protected] >> >> To subscribe or unsubscribe via the World Wide Web, visit >> http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51 >> or, via email, send a message with subject or body 'help' to >> [email protected] >> >> You can reach the person managing the list at >> [email protected] >> >> When replying, please edit your Subject line so it is more specific >> than "Re: Contents of A51 digest..." >> >> >> Today's Topics: >> >> 1. Re: internal A5/1 state after lookup (M vd S) >> 2. Re: internal A5/1 state after lookup (sascha) >> 3. Re: internal A5/1 state after lookup (sascha) >> >> >> ---------------------------------------------------------------------- >> >> Message: 1 >> Date: Mon, 17 May 2010 22:34:41 +0200 >> From: M vd S <[email protected]> >> Subject: Re: [A51] internal A5/1 state after lookup >> To: sascha <[email protected]> >> Cc: [email protected] >> Message-ID: <[email protected]> >> Content-Type: text/plain; charset=ISO-8859-1; format=flowed >> >> On 05/17/2010 11:13 AM, sascha wrote: >>> On Mon, May 17, 2010 at 02:01:34AM -0700, MIHAITA ADELA wrote: >>> >>>> Hello, >>>> >>>> I'm not sure I understood the whole process of the A5/1 attack and I >> have two more questions: >>>> >>>> 1) the tables and the lookup provides an A5/1 state that generates those >> 64 bits of keystream.; which state is this? is it the state after the 100 >> steps with majority clocking and that's why you need to backclock the state >> provided by the tables? >>>> >>> >>> >> (NB: please note that the table format has recently been changed in this >> respect. Not all information you might find necessarily reflects this) >> >>> The immediate result from the table lookup process gives you the >>> state before 100 clockings. With a little forward-then-backward clocking >>> on this result you can find a few more valid states (i think it was 3%). >>> >> >> This is not entirely correct. With 100 clockings forward, and 100 >> backward (all done with majority clocking), you get to some 13.0 states >> on average, which all (by definition) produce the same keystream. >> >> Clocking further forward and backward than 100 is possible, but then the >> keystream may be different. If you verify that the same keystream will >> be produced, you will find that there's a 3% increase in states that >> lead to the observed keystream after 100 clockings. >> >> So that means that if you find a hit, you find 13.4 states on average >> producing the keystream you were looking for. Or, put in other words, >> for every value contained in the tables, 13.4 real-world values can be >> cracked. >> >>> Still you have to backclock the result to get rid of the frame number >>> forward clocking step to arrive at Kc. So apart from the above >> optimization, >>> all the backclocking you have to do is in no-majority-clocking mode. >>> >>> >> >> Again, you do need to clock forward and backward in majority-clocking >> mode to enhance your table's hit-rate by a factor of 13.4. (or 13.0 if >> you skip the 3% trick) >> >> And as far as I know you never really arrive at Kc without some extra >> effort (namely: clocking the lfsr's to an empty state without the help >> of majority clocking) >> >> But, for the purpose of decrypting one connection, all you want to know >> is the lfsr state after clocking Kc in, so you don't really need Kc anyway. >> >> Cheers, M. >> >> >> >> ------------------------------ >> >> Message: 2 >> Date: Tue, 18 May 2010 00:31:07 +0200 >> From: sascha <[email protected]> >> Subject: Re: [A51] internal A5/1 state after lookup >> To: [email protected] >> Message-ID: <20100517223107.ga3...@test> >> Content-Type: text/plain; charset=us-ascii >> >> On Mon, May 17, 2010 at 10:34:41PM +0200, M vd S wrote: >>> On 05/17/2010 11:13 AM, sascha wrote: >>>> The immediate result from the table lookup process gives you the >>>> state before 100 clockings. With a little forward-then-backward clocking >>>> on this result you can find a few more valid states (i think it was 3%). >>> >>> This is not entirely correct. With 100 clockings forward, and 100 >>> backward (all done with majority clocking), you get to some 13.0 >>> states on average, which all (by definition) produce the same >>> keystream. >> >> True. >> Take a look at this picture: >> http://reflextor.com/trac/a51/attachment/wiki/BackclockA51/a51map.png >> >> The 64 bits of keystream that is used as the input to the table lookup >> would be found outside of the picture on the right side. >> The table maps the A5/1 state that is in column 0 of the pic to this >> 64 bits of keystream. Even though all states within a green cloud converge >> on the same internal state on the right side, they do not produce the >> same keystream during the 100 clockings. >> You should visualize another plane on top of the picture that represents >> the keystream (with width 100 and height 128). If you mark a 1 with a black >> dot and a 0 with a white dot then it would look like white noise, i.e. >> even though the states in a green cloud converge there is no similarity >> in their keystream. It is easy to generate the keystream plane from the >> register state plane, but not the other way around. >> >> Now take a single path of a green cloud and of that path save the value >> at column 0 (64 bits of A5/1 register state). Take 64 columns of the >> path on the right side of the picture, but from the keystream plane >> (64 bits of keystream). Store both values in the table, sorted by >> keystream. >> >> After a successful hit in the table you have the value at column 0 of a >> green >> clound. Clock forward 100 times and you have the value at column 100. >> Clock backward 100 times and you have on average 13 paths, i.e. you have >> regenerated the green cloud and you have found 13 A5/1 register states >> that produce a particular keystream (from clock 100 forward). >> >>> >>> Clocking further forward and backward than 100 is possible, but then >>> the keystream may be different. If you verify that the same >>> keystream will be produced, you will find that there's a 3% increase >>> in states that lead to the observed keystream after 100 clockings. >> >> Which is the same as to say that the keystream plane is not purely white >> noise, but there are converging states that produce the same keystream. >> You will probably find quite some order there, but 64 bits of equalness >> is as rare as 3%. >> To visualize that, you can think of the rightmost dot in our green cloud >> to be one of the leftmost dots in another green cloud, only that now >> your criteria for colouring is that the keystream is the same as well as >> the fact that the states converge and your new cloud is of thickness >> 1.03 left and 1 on the right and the cloud is of width 64 instead of 100. >> A put in a non-statistical way, most of the time, your new cloud would >> be a single path and in 3% of the cases it would be 2 paths. >> >>> >>> So that means that if you find a hit, you find 13.4 states on >>> average producing the keystream you were looking for. Or, put in >>> other words, for every value contained in the tables, 13.4 >>> real-world values can be cracked. >>> >>>> Still you have to backclock the result to get rid of the frame number >>>> forward clocking step to arrive at Kc. So apart from the above >> optimization, >>>> all the backclocking you have to do is in no-majority-clocking mode. >>>> >>> >>> Again, you do need to clock forward and backward in >>> majority-clocking mode to enhance your table's hit-rate by a factor >>> of 13.4. (or 13.0 if you skip the 3% trick) >>> >>> And as far as I know you never really arrive at Kc without some >>> extra effort (namely: clocking the lfsr's to an empty state without >>> the help of majority clocking) >>> >>> But, for the purpose of decrypting one connection, all you want to >>> know is the lfsr state after clocking Kc in, so you don't really >>> need Kc anyway. >>> >> >> True. >> >> >> >> ------------------------------ >> >> Message: 3 >> Date: Tue, 18 May 2010 01:13:17 +0200 >> From: sascha <[email protected]> >> Subject: Re: [A51] internal A5/1 state after lookup >> To: [email protected] >> Message-ID: <20100517231317.ga3...@test> >> Content-Type: text/plain; charset=us-ascii >> >> The procudure with the old table format would have been that the mapping >> was from the 64 bits of keystream to any of the rightmost coordinates >> on the register state plane and the lookup result would have to >> be backclocked 100 times. When a grey cloud would have been hit by that, >> the lookup result would have been useless. And a hit in a green cloud >> would have been as useful as before. That means each hit not in a grey >> cloud would have yielded 13 states on average but you would hit a grey >> cloud 13 times more often than a coloured cloud. >> To rule out all the grey clouds, the 100 extra clockings have to be done >> during table generation (if you are in a grey cloud and clock forward >> 100 times you cannot be in a grey cloud anymore of course, at least >> one of your paths can be clocked back 100 times). >> Also if you clock the whole picture one more step forward, it would look >> quite a bit different, because with each forward clocking you open up >> 3 more possibilities to clock back (the majority rule allows 4 different >> clocking patterns). Each clocking forward would shift the current picture >> as is one column to the left (changing the colors only gradually) and >> open up 3 new planes with a basically quite different appearance. >> >> If you ignore the extra planes spawning, you would see green clouds >> in the original plane fading towards a single red path with no bulge in >> the middle, red clouds with a bulge in the middle would have the same >> destiny and you would see new green and red and orange clouds form in the >> grey clouds. Red clouds would turn green as their bulge hits the left side. >> Also, those single red paths would constantly flow out >> of the picture into different y coordinates in the keyspace, but they never >> end. >> >> >> ------------------------------ >> >> _______________________________________________ >> A51 mailing list >> [email protected] >> http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51 >> >> >> End of A51 Digest, Vol 12, Issue 6 >> ********************************** >> > > > > _______________________________________________ > A51 mailing list > [email protected] > http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51 _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
