Help me understand this please: Not all of the 2^64 possible A5/1 register states is valid, considering the 100+ extra clockings before. Ok that makes sense. You say 40% out of all states can be clocked backwards more than 16 times, lets assume that is also the number of states that can be clocked backwards 100+ times (do you have a better number here?) Our keyspace shrinks down to 2^64 * 0.4, provided that we can eliminate the illegal states. 16 extra forward clockings would slow down the table generation by 25%, do you think this would rule out the majority of the illegal states? I think backclocking is out of the question for the table generation, as it would slow down everything too much. Another strategy would be to flip bits of an illegal state to change it into the closest (in term of bit flips) legal state. This would be very fast and should reduce the number of left over illegal states by quite a bit.
Also note that the great majority of values in a table are never looked up but exist only as a link between the state we are interested in and the end value that is looked up in the data base. A false positive that does not pass the backclocking test is a rare case and does not influence the attack time very much. (is this true? how long does it take to to the backclocking?). Still we would need 2 times the storage if we use the old method. Your optimization seems to suggest that we can cut down our search space by roughly 50% if we invest a few more (processor) clock cycles at each link. If you would find a fast way to turn illegal states into legal (or probable legal) states then this could be used for new tables. Since you already have code running, could you try various strategies, like flipping bits, clocking N (N between 1 and say 16) forward and see how that influences the ability to backclock the state? This extra computation should obviously not increase generation time by much more than 100%. 120% would still be ok, since we also reduce our storage requirement by 50%. Also note that there is no way to do the extra calculation only on illegal states, since they are bitsliced. You can of course only modifiy illegal states but you would have to do the calculation with every chain (and then ignore the result for legal states). On Sat, Jan 09, 2010 at 02:01:30PM +0100, M vd S wrote: > 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 > [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
