Hi, I've been studying the A5/1 cipher in some more detail. As I noted before, 24 out of 64 randomly generated states cannot be reversed 1 step. Such a state I would like to call an illegal state, since there is no way that the state in an actual a5/1 implementation will ever have that value after clocking 100 times with majority clocking.
When considering clocking back more times, the number of illegal states rises to some 60-65% (in theory). Note that an illegal state *does* produce a 64 bit keystream nonetheless. This means that when you find a hit while cracking, there's a 60% chance of finding an illegal a5/1 state, which was certainly not the state the phone had in mind before generating the ciphertext, and which is certainly useless in trying to decrypt a conversation. (assuming random keystream distribution in practice) It also means that 60% of a5/1 rounds are calculated in vain. Detecting an invalid state is trivial. Transforming an invalid state into a valid one as well. The easiest way would be to just sanitize the state by stepping *forward* a few times, in the hope of opening up at least one new pathway on the way back. It would require very little changes to existing code, cost very little cpu time, while not invalidating existing tables (although lookup code should be aware of the two table versions thus introduced). It is open to discussion if you should only sanitize illegal states this way, or just clock forward every state a few times before taking the 64 bits of keystream as the next state. If such an approach would be taken, every hit will at least generate a reversible state. Every chain will be 2.5 times more useful. With only 40% of these new tables, you would have the same success you have in decrypting with the current tables. To demonstrate that the stated percentages are real, I've modified a reference C implementation of chain generating code (kindly provided by Frank) to put this into practice, and count the number of ancestor states when clocking back N times, as well as the number of back-clockings before hitting an illegal state (/only illegal states after branching) These are the preliminary results: (for 1 chain, N=16) Evaluated 504062 (57%) 16-step illegal states, 870384 total. clocking back 16 times gave: 0 pathways in 504062 cases (57.91%) 1 pathways in 186024 cases (21.37%) 2 pathways in 48875 cases (5.62%) 3 pathways in 62250 cases (7.15%) 4 pathways in 27368 cases (3.14%) 5 pathways in 15404 cases (1.77%) 6 pathways in 7952 cases (0.91%) 7 pathways in 7360 cases (0.85%) 8 pathways in 3166 cases (0.36%) 9 pathways in 2284 cases (0.26%) 10 pathways in 2071 cases (0.24%) 11 pathways in 930 cases (0.11%) 12 pathways in 724 cases (0.08%) 13 pathways in 601 cases (0.07%) 14 pathways in 353 cases (0.04%) 15 pathways in 262 cases (0.03%) 16 pathways in 179 cases (0.02%) 17 pathways in 141 cases (0.02%) 18 pathways in 91 cases (0.01%) 19 pathways in 75 cases (0.01%) 20 pathways in 45 cases (0.01%) 21 pathways in 38 cases (0.00%) 22 pathways in 32 cases (0.00%) 23 pathways in 27 cases (0.00%) 24 pathways in 11 cases (0.00%) 25 pathways in 12 cases (0.00%) 26 pathways in 11 cases (0.00%) 27 pathways in 10 cases (0.00%) 28 pathways in 10 cases (0.00%) 29 pathways in 3 cases (0.00%) 30 pathways in 4 cases (0.00%) 31 pathways in 4 cases (0.00%) 32 pathways in 3 cases (0.00%) 33 pathways in 1 cases (0.00%) 34 pathways in 1 cases (0.00%) depth reached: depth 0 reached 326278 times (37.49%) depth 1 reached 40753 times (4.68%) depth 2 reached 15433 times (1.77%) depth 3 reached 12179 times (1.40%) depth 4 reached 11289 times (1.30%) depth 5 reached 10856 times (1.25%) depth 6 reached 10251 times (1.18%) depth 7 reached 9817 times (1.13%) depth 8 reached 9564 times (1.10%) depth 9 reached 9272 times (1.07%) depth 10 reached 8832 times (1.01%) depth 11 reached 8357 times (0.96%) depth 12 reached 8270 times (0.95%) depth 13 reached 7985 times (0.92%) depth 14 reached 7588 times (0.87%) depth 15 reached 7338 times (0.84%) depth 16 reached 366322 times (42.09%) de001bc0006f0000 [0] -> 36dc483fb4fe0000 Completed 1 chains So 57% of the states cannot be clocked back more than 16 times - and we need at least 100 steps to get to the point where the key and frame number is mixed in. 37.49% of the states cannot be clocked back even once (theory says 24/64=37.5%), which is determined easily (6 bit lookup or simple bit logic). If only this test would be performed, the efficiency increase would be 60%. If testing is done rigorously (32 steps back, giving 68% illegal states) the efficiency increase would be 212%, of 3.12 times more efficient. Taking 16 steps back as a tradeoff, the process will be about 2.5x more efficient. Not testing at all but just stepping forward a few times might be the easiest workaround. The optimum number of steps would have to be determined emperically. (Another worry I have is the number of ancestor states. The expected value of ancestor states 16 steps back, or E[anc(16)], in the above example is 1.0015, but when we leave out the illegal states (which do not occur in practice) I get E[anc(16)!=0] = 2.38. This would mean stepping back e.g. 128 times takes this to the power of 8, leading to some 1000 possible Kc - still manageable but way more than the reported 1-10 someone stated before) Kind regards, M. _______________________________________________ A51 mailing list A51@lists.reflextor.com http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
