| << Newer | Article #203 | Older >> |
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:
- bytes in the key at addresses $0004-0FFF all have bit $80 set
- bytes in the key at addresses $1004-1FFF all have bit $40 set
- bits 0-5 of each key are very uniformly random (almost exactly 50/50 0's versus 1's)
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.