<< Newer | Article #205 | Older >> |

## FD1094 Analysis, part 2

The next step in analyzing the FD1094 keys was to see if I couldn't replicate the pattern of the existing keys using a linear congruential generator (LCG). A LCG is typically written in the form:

*x'* = (**a** * *x* + **b**)
% **c**

which requires three constant parameters **a**, **b**, and **c**
to be determined. Assuming that this was done with 32-bit math, that would
be 2^{32} x 2^{32} x 2^{32} = 2^{96} possible
combinations. That's a bit much to brute-force examine.

Fortunately, thanks to the fact that the bit sequences repeat at even powers
of two, we can eliminate **c** from the equation entirely, since it
is just a mask. Furthermore, a property of LCGs with even power of 2 values
for **c** is that bit *n* repeats with a frequency of 2^{n}.

Beyond these two factors, if you think about it, bits in *x* that
sit higher than the one we are interested in don't really matter. For example,
if we are interested in bit 8, and **a** is $7F and **b** is $42,
then we will get the same bit sequence in bit 8 as we would if **a**
were $F87F and **b** were $10442 (you may need to do the math to convince
yourself -- I did). Thus, only the bits below bit 8 matter when searching
for **a** and **b**.

Given these additional constraints, our search space got significantaly
smaller. Taking, for example, a bit that repeats with a frequency of 8192
(2^{13}), we need only look at 2^{13} values for **a**
and 2^{13} values for **b**, or 2^{26} total possibilities.
Not bad at all. Of course, for each **a**/**b** combination, we had
to generate the sequence of 2^{13} bits in order to compare against
our existing data.

After doing some searching across all the keys, eventually I found that
a consistent value for **a** worked to generate the low six bits of
all the keys, when combined with an initial seed value, one of 5 different
initial values for **b**, and one of 6 different shift amounts (i.e.,
compute *x'*, then shift right by a given amount, and mask against
$3F to get the low six bits). It turned out that every single one of the
existing FD1094 keys could have its low six bits generated in this fashion,
and through this mechanism, I was able to fix single-bit errors in several
keys. At last, the analysis was starting to pay off!

Nicola noticed something odd about the values for **a** and **b**,
and further reduced the equation to:

*t* = **a** * *x*

*x'* = *t* + (*t* << 16)

The nice thing about this equation is that it gets rid of the arbitrary
shift and **b** values entirely, leaving only an initial seed value
which is unique for each game.

So, with the mystery of the low 6 bits solved, and one of the two remaining bits fixed across most of the key, all that is left is to figure out what the final bit is for each of the 8192 bytes of the key. Unfortunately, it turns out that this bit does not appear to be algorithmically generated. More on that in part 3.