1 Oct 2010 06:07

## Re: Newbie question

```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