<< 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 232 x 232 x 232 = 296 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 2n.

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 (213), we need only look at 213 values for a and 213 values for b, or 226 total possibilities. Not bad at all. Of course, for each a/b combination, we had to generate the sequence of 213 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.