On Thu, Sep 30, 2010 at 11:18:20PM +0200, Václav wrote: > Question regarding table construction: > > let’s say that we have some chains from the table: > (we only know first and the last value in each chain) > 1. 2. 30. 31. 32. > X-x-x-x- -x-x-x-x-x- ... -x-x-x-x-x- -x-x-x-x-x- -x-x-x-x-X > X-x-x-x-x- -x-x-x-x- ... -x-x-x-x -x-x-x-x- -x-x-x-x-X > X-x-x- -x-x-x-x-x- ... -x-x-x-x-x- -x-x-x-x- -x-x-x-X > A-b-c-d-e- -f-g-h-i-j- ... -k-l-m-n-o- -p-q-r-s-t- -u-v-w-y-Z > X-x-x-x-x- -x-x-x-x- ... -x-x-x -x-x-x-x-x- -x-x-x-x-X > X-x-x-x- -x-x-x-x-x- ... -x-x-x-x-x- -x-x-x-x-x- -x-x-X > ( i don’t have the time to write a million character chain > so i wrote just a few characters per round :) ) > > Now, for example we have the key M and we want to know what A5 inner > state generated this key. > > We start calculating the chain from the key M. > After some time we calculate a value with 15 zero bits > we then check if it could be found in the table. > It can't be found so we continue with next round. > > again after some time we calculate a value with 15 zero bits > we then check if it could be found in the table. > It can't be found so we continue with next round. > > Now, after some time we calculate a value with 15 zero bits > we then check if it could be found in the table. > We FOUND it! It is 'Z'! > so we get this chain: M-n-o- -p-q-r-s-t- -u-v-w-y-Z > > that means that our chain corresponds with chain from the table like this: > > A-b-c-d-e- -f-g-h-i-j- ... -k-l-m-n-o- -p-q-r-s-t- -u-v-w-y-Z > | | | | | | | | | | | | | > M-n-o- -p-q-r-s-t- -u-v-w-y-Z > > Now we have to calculate the chain from the table again (starting from A) > so we can find out what was the value before M. > The result is L! > > Is that how it works? > > If that is the case, > how do we know that state M was in round 30 (so we could apply correct > round function) ? > Or do we calculate the same thing starting from round 1, then starting > from round 2, ..., then starting from round 32?
exactly, and you do not do a lookup in the table if you have a distinguished point, but only if you have a distinguished point at round 32. So given M, you calculate x1 = Round(31, M), SearchFor(M, 31, Rounds(0-30, lookup(x))) x2 = Round(31, Round(30, M)), SearchFor(M, 30, Rounds(0-29, lookup(x))) Round(x, val): calculate val in round x until DP Rounds(a-d, val): Round(d, Round(c, Round(b, Round(a, val)))) SearchFor(value-to-find, round function to use, val) For a single 64bit keystream segment, you calculate 1 + 2 + 3 + 4 + ... + 32 round segments to get to 32 possible end values. You could also say you calculate 0.5 + 1.5 + 2.5 + 3.5 + ... + 31.5 rounds, because your M will likely bring you into the middle of a round. Additionally, if your M and m are not the same, but both p above produce the same q then you will find Z but you will not find M when starting from A. Meaning that the chain you construct during lookup can merge with a target chain after the first step and turn out to be a false positive (i.e. end value matches, but its bogus still). This happens 50% of the time as a rule of thumb and out of your 32 candidates you would have to check around 16 chains from the start with 15 false positives. The actual tables nowadays have 12 bit DP and 8 rounds. _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
