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? What are the reasons to choose this structure and not standard Oechslin RT with different reduction function each step? 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? Thanks regards, Sylv1
--- On Wed, 11/25/09, sascha <[email protected]> wrote: From: sascha <[email protected]> Subject: Re: [A51] theoretical questions To: [email protected] Date: Wednesday, November 25, 2009, 12:53 PM On Wed, Nov 25, 2009 at 02:27:15AM -0800, Sylv1 wrote: > Hey all, waiting for a new computer to install my gtx260 (older was not > powerfull enough and overheat :-s) im going into the theoritical stuff. > I have some questions. The project is using rainbow tables. Is this the > version presented by Philippe Oechslin? Or is it just the standard > time-memory tradoff from Hellman?From what i know about rainbow table, it is > only a big table with a reduction function different for each column of the > table. Advantages of rainbow table is that merging can only occurs at the > same level due to the different reduction function between level (by level i > mean column of the table).Now for this project, we are talking of generating > 2^(8.5) tables. So this is not a unique rainbow table right? What is the goal > of having more than one table if we use so-called rainbow table? Can anyone > explain to me?Maybe the goal is to decrease the look-up time that is in > theory N^(2/3) (N the keyspace size) by having a smaller N value and get a > distributed lookup within more than one rainbow table? Can a1 confirm (or > not)? Each table is an oechslin rainbow table with the variation that the round function does not change every column, but only when there is a distinguished point of 15 bits. We have more than 1 table, because this makes a distributed lookup possible. To have completely independent tables is comparable to hellman tables. If we ignore the fact that each of our tables has a structure, the lookup complexity (time needed to search a single table) * (number of tables) is comparable to a hellman setup. If you were to do all the lookups on a single computer, then you would have saved half the time during lookup if you had generated a single table, because you would have applied oechslins optimization by combining many tables into one. of course you loose the ability to do distributed lookups then. What most people fail to understand first is that rainbow tables do not reduce chain merges, they only reduce lookup time. The number of chain merges in N hellman tables with chainlength N of height M is the same as that of 1 RT table with N columns (and thus chainlength N) and height M * N. The lookup time is N^2 for Hellman and N^2/2 for Oechslin. > Another thing is about the RRCipherModeCompleteMessage. This message gives 4 > frames of 114 bits, so why do we limit the size of the arrival space to 64 > bits messages? How is the mapping between RR message and 64-bit keystream > done?Since the whole 114-bit RR message is encrypted with the keystream > output of A5/1 that is also 114bits, i don't understand why we are using a > sliding version of a 64-bits keystream to get 50 ciphertext messages. > Can anyone explain to me what i've missed? A burst of size 114 has 51 windows of size 64 bit. that is bit 0-63, 1-64, 2-65, ..., 50-114 One LAPDm frame is 4 bursts, so you get 51 * 4 = 204 keystream samples if you can predict the plaintext content of a whole LAPDm frame. Of the 23 bytes of the CipherModeComplete frame, 20 bytes are padding and 3 bytes are constant message code etc. IIRC. Since we have 204 keystream samples, with a total table size of 2^64/204 we find a match with a probability of 50%. _______________________________________________ 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
