> I tried to do some timing on how long it takes to calculate / lookup > chains with more distinguishing bits. Currently tables are calculated > with 15 zero bits at the termination point. But I discovered that there > seems to be a limit to how many 0 bits A5/1 is capable of generating in > a row. ( Around 20+ bits ) - It could be that the only way to get longer > runs of 0, is to have all 0 bits in the lfsrs. This is a degenerate > state that doesn't occur in key-setup.
Since the keystream is the XOR of the most significant bit of each register, you can have zero in the keystream without the necessity of only zeros in R1-R3. So in theory the keystream could be zero for a very long time, but it gets very unlikely and maybe it never happens for zeros of a certain size. With 15 bits zero x 32 rounds you get chains in the length range of 500k - 1500k, with significant more chains around the expected length of 2^15 * 2^5. > > The distinguishing bits generalization that we use is somewhat flawed. > In my test runs, I eventually had to place the bits in a pattern like: > > (hex): 0f0f0f0f0f0f0f0f > > Ex check ( output & 0x00070f0f0f0f0f0fULL ) == 0UL etc.. > > Just checking on the lowest consecutive bits made the chain searching > non-terminating. Perfectly valid approach. You could also search for any value other than 0, as in output & 0xfffff == 0x12345. When you try to make the DP ranges longer and drop some of the rainbow table rounds you will still have to do something about the chain merges, which would be to make many tables with a constant round function (only one round function value instead of 32). Since your chains are very long then, you cannot have too many rows in each table before chain merges occur on more than 50% of new chains you try to add. So you have to make more tables to be able to store the required number of rows. So if you have chain lengths of a million on average and no rainbow colors, then you have to make 2^13.5 instead of 2^8.5 tables. With that you have gained nothing, but your lookups are only half as fast as before. The only reason to use a table with 32 rainbow colors is to merge 32 diffie hellman tables into one and safe 50% lookup time. > > In other news, building the A5 grinding code as a C dll, made it really > easy to add python bindings (ctypes) .. It would be nice to have a clean > python front-end, rather than trying to emulate a weakly typed language > through a maze of templates :-) > I was thinking about adding dynamic languages ontop of the framework, but since CPU usage is around 5% for the control app, it would have been totally reasonable to write the host part in perl. With the framework already written, i dont see a reason to replace it with a slower part. It would take you some weeks to recode the functionality. Other than the ATI device integration, future extension is about adding crypto algorithms or storage plugins where you can safely ignore the details of how everything is glued together. Also, during the lookup the CPU will get a bigger share of the load. And if you can avoid everything in static_sequence/*.hpp you will not be confronted too much with the dark science. A little documentation could still help. ______________________________________________________ GRATIS für alle WEB.DE-Nutzer: Die maxdome Movie-FLAT! Jetzt freischalten unter http://movieflat.web.de _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
