Articles posted March 2007 Older >>

#1 With A…

I took a break from Excite League and decided to look at Bullet instead, mainly because it was a bigger unknown than a baseball game. After some more aggressive improvements to my analysis tools and many hours of tedium, I managed to get almost all of the code for the game successfully idenitified. Out of the 8192 key bytes, I'm down to less than 100 ambiguous cases, and have over 67% of the mystery bits in the key identified.

With this work, I'm finally able to get the game up and running. It passes all tests, the attract mode runs, and the game is pretty playable, though I think there are a few minor glitches that still need to be worked out.

Interestingly, it appears to be the only 3-player dual-joystick game I can think of. Haven't gotten far enough into the game to really get a feel for what it's like, but I will include the current partial key with the next MAME update so you can have a look yourself.

FD1094 Analysis, part 3

Unfortunately, just knowing the pseudo-random number generation formula is only good enough to identify the low 6 bits in 8188 out of the 8192 bytes of the key. The top two bits aren't generated by the formula, and the first four bytes are completely independent.

The first four bytes of the FD1094 key are what's known as the "global" key. The first byte indicates which internal mode the FD1094 switches into whenever an interrupt is taken (the FD1094 has 256 different modes that it can be in, and programs can switch between them at will while running). The three bytes following affect how the bit permutations work across the entire key, which is why we generally refer to it as the "global" key. In order to decrypt a given word of the program code, we take the 8-bit value from the key at the corresponding address, plus the 24 bits from the global key, plus the 8-bit current mode, and use those 40 bits to determine how to shuffle the bits to produce the final result.

Fortunately, there are some patterns in the global key that help reduce the keyspace by a few bits (each bit that is "locked" reduces the search space by a factor of 2, so each bit counts!), so in the end we only have to search all 8 bits of the first byte, and 16 bits over the next three bytes, so 24 bits total. Add that to the 22 bits necessary to fully describe a seed value for the random number generator, and we're up to 46 bits worth of "root" key data necessary to generate all of the full 8192-byte key, minus the top two bits.

So, what's in those top two bits of the rest of the key? Well, as I mentioned in part 1, bit $80 is set consistently at addresses from $0004-$0FFF, and bit $40 is set consistently at addresses from $1004-$1FFF. So actually, for most of the bytes, one of the two remaining bits is a constant value.

It's that final bit that is the tricky part. One of the features of the FD1094 is that, after all the bit permutation has completed, certain decrypted values are thrown away and replaced by the value $FFFF. This was likely done either to prevent the use of certain opcodes, or (more likely) so that $FF fills--which are a common encryption weakness--could be encrypted in a random fashion. Regardless of the reasons, the final bit has a significant effect on this $FFFF replacement step. If the bit is 0, a certain subset of decrypted values are replaced; if the bit is 1, a more expansive set of decrypted values are replaced (including all of those that get replaced if the bit is 0).

To simplify the following explanation, I'm going to break the decrypted values into 3 categories. Category A opcodes are never converted to $FFFF. Category B opcodes are always converted to $FFFF, regardless of the state of the mystery bit. And Category C opcodes are only coverted to $FFFF if the mystery bit is set to 1.

Thus, at encryption time, the programmers had to be careful about what opcodes were present in the original code stream. Obviously opcodes in Category A were fine. However, opcodes in Category B are always converted to $FFFF, so they had to completely avoided; presumably there was some mechanism to avoid that problem. And for the opcodes in Category C, it had to be ensured that the mystery bit was set to 0 in the key.

Now, there are several potential theories about how the mystery bit was generated for the key. One theory is that the bit comes from the random number generator, but is then modified to change the bit to 0 wherever there is an opcode from Category C in the path. Statistical analysis of all the existing keys disproves this theory: if it were true, then the mystery bit should be set to 0 consistently less than 50% of the time. In reality the mystery bit varies quite a bit; on some games it is 0 in 30% of the bytes, and on others it goes as high as 70%.

A second theory is that by default the mystery bit is set to 1 everywhere except where there is an opcode from Category C. This would mean that the mystery bit is strictly determined by the original code. This theory seems more likely. A quick analysis of the simplest game (Sonic Boom) reveals that the mystery bit is only 0 if there is at least one Category C opcode present, and is 1 in all other cases. This is not definitive, but it is a good indication.

So, how can we figure out what that last bit is? That's the trick, and the reason that I've been pounding away at creating some new debugger extensions. It involves a lot of tedious work, and I don't think we'll get 100% perfect results, but I'm hopeful we can get something playable at least. It essentially involves analyzing all possible decrypted combinations that you get when you decrypt the code with the mystery bit set and clear, discarding any invalid opcodes, and then manually selecting the right answer based on analysis of the code. Through this mechanism I've managed to get the title screen of Excite League to come up, and have identified over 30% of the mystery bits in Bullet.

Keep your eyes peeled here for news of additional progress....

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.

Title Screen!

FD1094 Analysis, part 1

As you might have noticed, there has been some good recent progress on emulating the remaining encrypted Sega games, even though we don't have the CPUs available for analysis. This has stemmed from some analysis of the keys used in the games. For the MC8123-based games, Nicola has taken the analysis to its final conclusion and successfully generated full keys. Unfortunately for the FD1094, it's not quite that simple, but progress is being made, and I'm still hopeful the game code can be decoded.

Now, I'm no encryption expert (as I've said many times before), but for a while now I've had the sneaking suspicion that that keys stored in the FD1094 CPUs used by Sega were too large to be anything other than algorithmically generated. About a month ago, I posted the idea to the MAME developer list, asking if anyone else thought this might be an avenue worth pursuing, but didn't get much of a response. So I decided to start an analysis of the FD1094 keys that we currently have.

I started by looking for obvious patterns. There are a couple of interesting ones. Namely:

Armed with this knowledge, I decided to start looking for repetitions in each of the low 6 bits of all the keys we had. The theory I was going under is that some sort of pseudo-random number generator was responsible for producing these bits. At the time these devices were created, there was not a big focus on cryptographically secure random number generation, so I was hoping they used some kind of simple linear congruential generator (LCG). If they did, then eventually any sequence they generated would repeat.

My initial theory was that there was one generator, and that by stringing together bits from different keys, we might be able to reconstruct the algorithm that generated them. So I wrote a program that read in all the keys and looked for sequences where the ending set of values from one key overlapped the starting set of values from another key, taking each bit independently. Sure enough, it didn't take long to discover that there were what looked to be several long sequences of bits, some of which repeated at regular intervals.

The interesting thing here is that the bit sequences I was finding repeated at even power of 2 intervals, which initially made me think that perhaps the algorithm for generating the keys was more of a bit permutation than an LCG, but OG helpfully pointed out that an LCG with a modulus of an even power of 2 will repeat its bits at an even power of 2 frequency.

Even more interesting was the discovery that in the cases where bit 0 of a key had a period of 2n, bit 1 would have a period of 2n+1, bit 2 would have a period of 2n+2, etc. This indicated that it was quite likely the case that the low 6 bits were generated all at once with a single LCG. This was even better news than I had hoped.

The next step, then, was to figure out what the parameters of the LCG were. I'll talk about that in part 2.