Sylv1,
the short answer to your questions on table generation is:
http://reflextor.com/trac/a51/wiki/TableStructure
The lookups are done using 64 bit of known key stream. Each 114 bit
segment provides for 51 overlapping 64 bit key stream segments.
Happy Thanksgiving,
-Karsten
On Nov 26, 2009, at 9:12 AM, 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?
> 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
_______________________________________________
A51 mailing list
[email protected]
http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
