October 25 2009 Major bug

All versions prior to the one released on 25 of October 2009 use a buggy LFSR to generate round function values. Instead of producing 2⁶⁴-1 distinct values there are in fact only 32. This means that tables that ought to not produce chain merges in the event of a collision because of different round functions do produce merges. Luckily the buggy LFSR repeated after 31 rounds and since we are giving out round function advance numbers mod 32, the problem is less severe, since the same round function values applied in a different order produce different chains. Still we apologize for begin too self-confident where we should have been pedantic. Thanks to Frank Stevenson for finding the bug. We hope that most of you are still on board and keep growing the database.

The new version includes both the buggy LFSR and the fixed one. The fixed one is named lfsr2 and is also the default used in the configuration embedded in the binary. As a precaution, to use the old one, you have to invoke it with the force option as in

--roundfunc xor:condition=distinguished_point::bits=15:generator=lfsr::tablesize=32::advance=0::force

or the program will exit with an error message. If you have been generating a table so far, then we suggest that you take the number in the --advance parameter and add 32 to it and then use this value for your new table. As a small benefit, the overcomputed tables are interesting for statistical purposes to study collision and merge probability. Because of that and because it would complicate matters to have two different formats of tables, we will be collecting the old tables, see what big a fraction of them will be useless due to our mistake and take care of them ourselves so that they still contribute to the network. Give us a few days to work out a plan to collect the tables.

October 25 2009 minor bug

The windows port did not use binary file I/O to write tables, so you have a CR/LF when you only should have a LF in the tables. The correct table can be restored completely by running  this small program like:

$ crlf2lf input_file output_file

after running it for both the start and the end tables, they should be of equal size again.

Don't let us down

Finally to restore your confidence in the project, we have been testing the A5/1 implementation that we use on some real world ciphertext which was encrypted with a keystream generated from some known Ki and we were able to hear the original conversation. The fixed LFSR is also guaranteed to produce at least 32 million unique values, so we will not shoot in the same leg twice. While the decrypted conversation does not prove that the tables will work eventually and only ensures the correctness of our implementation of A5/1, we would be very much surprised to find one more critical bug. And of course you are invited to study the reference implementation yourself. With half of it proven correct (A5/1 and the round function LFSR) there are only a couple of lines of C code to verify.