On Thu, Nov 26, 2009 at 12:12:11AM -0800, Sylv1 wrote: > Hey, > thks for the answer. > I still come with some more consideration and misunderstanding ^^. > > You meen that we use a RT that used the same reduction function until we > reach a dinstiguishing point and then we change the reduction function? But > when the chain stops in this case? Are chains all the same length as in > standard oechslin RT?
the chain ends at a distinguished point. it is 15 bits long as all other DPs. You could also say that the chain ends at round 32. The chains are not of equal length. You have a gaussian distribution of chain lengths, with the top of the curve around 2^20, which is 2^15 * 32. there are chains only 2^19 long and i suspect also 2^21 can be found, but these extreme cases are sub 1%. If you had only one DP in your chains of size 20 bits then the distribution of lengths can be expected to be wider. To use 32 smaller DP segments shifts the properties of the chains more from single DP chains to constant length chains. Our chains have properties of both of these, with a strong emphasis on DP. If you made chains with 10bit DPs and 1024 rounds, they would also be 2^20 on average, but the gaussian curve can be expected to be thinner and steeper. > What are the reasons to choose this structure and not standard Oechslin RT > with different reduction function each step? You would use pure oechslin RTs in cases where you want to map close to 100% of the keyspace where you have many more collisions then we have. we only map 1/128th of the whole keyspace, so collisions are not such a big problem for us. We use 32 rounds, so we have to start generating our speculative lookup chains at 32 starting points. If we used ochslin tables, we would have 2^20 starting points. So the complexity of constructing lookup chains with our layout is (1+2+3+..+32)*2^15, which is ~ 2^24. In the oechslin case it would be (1+2+3+...+1048576) = 2^39. The moral is that those chainlengths are infeasible and you would have to make chains shorter and compute more chains, meaning you would need more storage (much more). So if collision rate is manageable you can make your chains longer without spending too much time in the lookup phase by using constant round function segments. We are in the lucky position that we need less than 1% of the keyspace, instead of 99,9%. > > For the RR message, i still don't understand. When i will eavesdropp on GSM > messages (lot of work do be done to be able to syncronize ^^) i will get 4 > 114-bits messages representing the CiphermodeComplete right? Then i would xor > that ciphertext with the known plaintext and get 4 114-bits frame of > keystream. If i understand well what u explained, i have to create keystreams > samples of this messages and do the lookup with this mesages. Wouldn't there > be some false positiv with repsect to a lookup in tables mapping Initial > states to 114-bits keystream messages? Or is there something that i've missed? The tables map A5/1 internal states to the first 64bits of keystream. There may be more than one A5/1 state that produces the same 64bits of keystream. But if you found a register state then you can keep generating more keystream bits to verify whether you have a false positive faster than you can say gigahertz. In that case you keep searching. But even a near match could be useful (further investigation needed). Different A5/1 states that produce the same 64bits of keystream usually differ only in a few bits. there may be a simple way to produce a few states that have this property. But as said above this is just a faint idea and we do not depend on this to meet our goals. The solid strategy is verify, dump it and move on if we find a false positive. Also those false positives are 1) very rare, about as rare as a hit, so not to be confused with false positives in the RT lookup which are more common and 2) they can be verified almost for free in an instant, so these false positives are not a problem at all. _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
