| | 1 | == October 25 2009 Major bug == |
| | 2 | |
| | 3 | All versions prior to the one released on 25 of October 2009 use a buggy LFSR to generate round function values. |
| | 4 | Instead of producing 2^64^-1 distinct values there are in fact only 32. This means that tables that ought to |
| | 5 | not produce chain merges in the event of a collision because of different round functions do produce merges. |
| | 6 | Luckily the buggy LFSR repeated after 31 rounds and since we are giving out round function advance numbers mod 32, |
| | 7 | the problem is less severe, since the same round function values applied in a different order produce different |
| | 8 | chains. Still we apologize for begin too self-confident where we should have been pedantic. Thanks to Frank Stevenson for |
| | 9 | finding the bug. We hope that most of you are still on board and keep growing the database. |
| | 10 | |
| | 11 | The new version includes both the buggy LFSR and the fixed one. The fixed one is named lfsr2 and is also the default used |
| | 12 | in the configuration embedded in the binary. As a precaution, to use the old one, you have to invoke it with the force option |
| | 13 | as in |
| | 14 | |
| | 15 | --roundfunc xor:condition=distinguished_point::bits=15:generator=lfsr::tablesize=32::advance=0::force |
| | 16 | |
| | 17 | or the program will exit with an error message. |
| | 18 | 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 |
| | 19 | it and then use this value for your new table. |
| | 20 | As a small benefit, the overcomputed tables are interesting for statistical purposes to study collision and merge probability. |
| | 21 | Because of that and because it would complicate matters to have two different formats of tables, we will be collecting the old |
| | 22 | 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 |
| | 23 | contribute to the network. Give us a few days to work out a plan to collect the tables. |
| | 24 | |
| | 25 | == October 25 2009 minor bug == |
| | 26 | |
| | 27 | 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. |
| | 28 | The correct table can be restored completely by running [http://reflextor.com/crlf2lf.exe this small program] like: |
| | 29 | |
| | 30 | $ crlf2lf input_file output_file |
| | 31 | |
| | 32 | after running it for both the start and the end tables, they should be of equal size again. |
| | 33 | |
| | 34 | == Don't let us down == |
| | 35 | |
| | 36 | Finally to restore your confidence in the project, we have been testing the A5/1 implementation that we use on some real world |
| | 37 | ciphertext which was encrypted with a keystream generated from some known Ki and we were able to hear the original conversation. |
| | 38 | The fixed LFSR is also guaranteed to produce at least 32 million unique values, so we will not shoot in the same leg twice. |
| | 39 | While the decrypted conversation does not prove that the tables will work eventually and only ensures the correctness of our implementation |
| | 40 | 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 |
| | 41 | 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. |
