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
