Thank you very much for all your answers!
________________________________ From: sascha <[email protected]> To: [email protected] Sent: Tue, May 18, 2010 1:31:07 AM Subject: Re: [A51] internal A5/1 state after lookup 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. _______________________________________________ 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
