Nicola's MAME Ramblings

CPS2 not much left to do

2007-02-17T13:06:00.000+01:00

When I originally wrote the key searching program, that was on the assumption that the key for the second Feistel network was 96 bits long.

Each (E,D) pair reduces the key space by a factor of about 2¹⁶, so to isolate the correct key with good confidence one would need at least 96/16 = 6 (E,D) pairs.

The big problem is finding those pairs. Remember that they must be at compatible addresses, that is addresses whose bottom 17 bits are the same. This is a serious limitation, because the code of several games only covers a range of 0x80000 bytes, which would give a maximum of 4 pairs at any address. For the Super Puzzle Fighter 2 games, the range is just 0x40000 bytes, giving just 2 pairs per address.
One can find hundreds, even thousands of of (E,D) pairs, but if they are not at compatible addresses they are of no use to find the key using this attack.

However, now we know that the key actually has only 64 significant bits, some of which are repeated. I therefore rewrote the program to take that into account. This means that only 4 (E,D) pairs are needed to isolate the key.

Also, I made several important optimisations that I missed the first time around, like caching intermediate results and speeding up the s-boxes calculations by using precalculated tables (this last optimisation also made into MAME so the decryption when loading a game is now faster).

The end result is a program that is orders of magnitude faster than the previous one.
Now it takes just 15 seconds to find the key given 8 (E,D) pairs. With 5 pairs, which was just plain impossible before, it takes 5 minutes. With 4 pairs, 35 minutes.

These improvement made it simple to find most of the remaining keys, even for games that didn't have a matching revision already decrypted (most notably some of the Steeet Fighter Zero versions).

But there's more: the program is now fast enough to go one step further, and look for the key with just 3 pairs. Of course 3 pairs are not enough to isolate the right key: they only reduce the key space by about 2⁴⁸, therefore leaving about 2¹⁶ keys which are compatible with the data. Once a 64-bit key for the second Feistel network is selected, the compatible 64-bit master keys can then be easily generated, and used to verify other (E,D) pairs at different addresses. This allows to find the correct key in less than one day, and I had to use this extended attack for a couple of the most problematic games.

In the meantime, Andreas Naive has been busy implementing the attack he had described on his blog, and was able to find the keys for two of the Super Puzzle Fighter 2 games. Unfortunately, the attack failed on the third. Work is still in progress on that one, and there is some hope that the key will eventually be found.

The only other games that are missing a key are the two CPS2 versions of Mega Man. There is no decrypted CPS2 version of that game to compare with, and the CPS1 version seems to be too different to be able to find good pairs.

CPS2 Key Bit Order

2007-01-21T12:05:00.000+01:00

As previously mentioned, the 64-bit keys I'm currently using should be the same as the hardware ones, except for a fixed permutation of the bits.

The permutation is actually irrelevant as far as the algorithm is concerned, since it is already taken into account when generating subkeys. The difference that it does make, however, is that there are strong suspicions that some of the keys are not random numbers, so what looks like random gibberish currently would show some order if we had the correct permutation.

Take the ssf2 versions for example. There are currently 6 different versions supported: World, USA, Asia, Japan, Tournament World, Tournament Japan. Here are the keys (in a different order):

3D9E1E15A58C32CE
3599DF35AD98284C
B74433502F4653D7
8758E3923FFA1A50
F0AE3D08420DD6BF
6260014FD857F7A7

there is something immediately obvious about those keys: they all contain exactly 32 0s and 32 1s.
When picking one random 64-bit numbers, the likelihood of this happening is about 1 in 10, so it's ok. But the likelihood of it happening for SIX numbers is about 1 in 1 million! So we can be pretty sure that those keys are not random numbers.

What is one particularly simple sequence that has exactly 32 1s? Well, of course 0123456789ABCDEF. And sure enough, after looking at the bits for a while and applying an appropriate permutation, here is what the above keys become:

0123456789ABCDEF
1032547698BADCFE
45673210CDEFAB89
67451032FEDC98BA
89ABDCEF45672301
CDEFBA9823016754

looks much better doesn't it?
Though there's no way to tell how close it is to the real thing.

CPS2 Moving Slowly Now

2007-01-19T22:37:00.000+01:00

The improved attack works, and I've been able to recover a few more keys, but it takes a lot of computation time--several hours per game.

I've also experienced some failures, e.g. I could find the key for dimahoo but not for gmahou. This might have been because of a false positive when looking for pairs with the complementation property, so now I'm trying again with a different pair. Since the searches take so long, experimenting isn't easy.

On the plus side, I've applied the improved attack also to some games for which XOR files were not available, and it worked in a number of cases--though it failed in many others.

One of the new versions supported is mshb, which I is the first Brazilian version of a CPS2 game to work.

Andreas has published details on a theoretical attack using differential cryptanalysis which looks promising. If Andy's calculations are correct, it should allow to retrive the key for the three most problematic games: spf2t, spf2xj, and spf2ta. It does require a lot of (E,D,k) triplets, something in the order of 2¹⁶-2¹⁷, which is a bit steep, but we should be able to do that in a few cases.

One thing to note about my attack, which I might not have explained clearly, is that it requires a remarkably small amount of data: it has worked for many games with just 7 (E,D) pairs. The problem is that those pairs must all be at the same address (as far as the encryption is concerned; that is, bits 1-16 of the address must be the same). Those 7 pairs allow to retrieve the 96-bit key for the second round at that address, and once that is known, the 64-bit master key can be found in less than 1 second, without having to know ANY other (E,D) pair at any address.

Unfortunately for game like spf2t, whose full encryption range covers just 2 repetitions of an address, we are never going to have 7 pairs so the attack will never work.

CPS2 The Fight Continues

2007-01-17T23:38:00.000+01:00

I've finished going through all the games previously supported by MAME using XOR files, and generating keys using this attack.

The attack needs a minimum of 7 (E,D) pairs at some address in order to work, though with just 7 pairs it takes several hours to find the key.

Most of the games provided at least 8 pairs, a few 7, so the attack worked.

On 11 games the attack didn't work. Three of them only provide 2 pairs, so there's no way for the attack to work--a different approach will be needed.

The others provide 4 pairs, and I'm now trying to still perform the attack, using a new trick.

Remember the complementation property? For every address A, we know that exists another address A₁ such that D(X, A) = D(X ^ 0xffff, A₁) ^ 0xffff. The problem is that we don't know A₁. We can search it, however, using the XOR data. Pick an address, look at the four (E,D) pairs associated to it, and then see if at another address there is a pair (E ^ 0xffff, D ^ 0xffff). That way we can put together the information from the two addresses, raising the number of pairs from 4 to 7, barely enough to run the attack.

There's a possibility of false positives when doing this, so avoid all pairs where E or D are 0x0000 or 0xffff, because those values are very common and make the probablity of a false positive much higher.

In theory this trick should work, though it will require some luck and a lot of time. The holy grail remains an attack which could use pairs from different addresses; that would be the only way to retrieve the key for the games that lack XORs.

CPS2 Getting Closer

2007-01-14T19:37:00.000+01:00

The correlations between the 96-bit keys of the two Feistel networks were crucial in getting the s-boxes with 4 or 5 inputs "in sync"--that is, make them idential to the real ones apart from a fixed XOR or permutation applied to the whole box.

Eventually, I ended with a layout which I'm 99.9% sure is equivalent to the real one. We cannot know the exact contents of the real s-boxes without getting them from the actual hardware, but the current ones should be matematically equivalent.
The result is here: http://xoomer.alice.it/nicola.salmoria/cps2crptv2.zip.

The most notable news is that the key is now reduced to 64 bits, and the one we are currently using should be identical to the one used by the hardware, apart from a fixed permutation of the bits.
Finding the real permutation would be nice, but obviously that's not something we can determine from the algorithm, since the order of the bits of the key is completely irrelevant.

What is interesting to note is that the keys used by some games don't seem to be random. If they were random one would expect there to be around 32 0s and 32 1s, but sometimes this isn't the case. E.g.

pzloop2:  3332206a0077f829
mshj:     01c0c951370f4c80
dstlka:   04048b4e2a498879
ringdest: 0405541367806575
cybotsj:  0404821534388354

Of these, the last three literally scream "I'm not a random number!". Guessing the right bit order to make something appear, of course, is another matter.
Some of the watchdog values contain birth dates, e.g. cmpi.l #$19660419,D1, so I expect the same thing might be happening here.
Also, it makes sense for the pzloop2 one to be more regular than the others because it's third party game.

On the key extraction front, things are going reasonably well. The brute force attack described in the previous article is working decently on most games, however for some of them the available data isn't enough. I'll have a more precise list once I've finished going through all the games. After that, we'll need to devise a better attack if we want to get the missing keys.

The discovery that the key is only 64 bits might help to construct a better attack, though at the moment I don't have many ideas. The fact that the algorithm is divided in two parts, with the output of the first one affecting the key on the second part, complicates things.

How to bruteforce CPS2

2007-01-12T19:36:00.000+01:00

I couldn't devise an attack using differential cryptanalysis and the XOR files. The fact that the second 96-bit key changes with the address makes thing more difficult, and I couldn't think of a way to effectively use data from different addresses.

The XOR files give us no more than 8-16 (E,D) pairs at a given address (remember that the encryption only uses the low 16 bits of the address). We have no choice of what data we have, so we have to make the best of it.

So the idea I had is to use a meet in the middle brute force attack which exploits a weakness in the s-boxes.

Remember that

L₁ = R₀
R₁ = L₀ XOR f₁(R₀)

L₂ = R₁
R₂ = L₁ XOR f₂(R₁)

L₃ = R₂
R₃ = L₂ XOR f₃(R₂)

L₄ = R₃
R₄ = L₃ XOR f₄(R₃)

Remember also that the f_n round functions are made of 4 s-boxes each.
These are the 16 s-boxes, with their inputs and outputs:

f1b1  03457- 67
f1b2  12346- 35
f1b3  124567 14
f1b4  023567 02

f2b1  0246-- 46
f2b2  134567 03
f2b3  013457 17
f2b4  123567 25

f3b1  2346-- 35
f3b2  01357- 02
f3b3  012357 16
f3b4  024567 47

f4b1  01367- 03
f4b2  012456 47
f4b3  023457 12
f4b4  234567 56

f2b1 is the weakest link. It has only four inputs, 0246. To get those four inputs, we need just three boxes in round 1: f1b1, which outputs 67, f1b3, which outputs 14, and f1b4, which outputs 02. We don't need f1b2, which outputs 35.

So if we start from the ciphertext and run it through the first two rounds of the Feistel network, scanning all 2²⁴ possible keys for f1b1, f1b3, f1b4, and f2b1, we'll get all possible values for bits 46 of R2.

Now let's start from the plaintext instead, and go up. If we scan all 2⁶ keys for f4b2, we'll get all possible values for bits 47 of R2 again.

Now we impose that bit 4 calculated in these two ways is the same, and given enough (E,D) pairs we have a huge pruning of the valid keys. From experiments, at least 8 pairs are needed for the attack to work effectively, but with 12 it's faster.

When we have a match on bit 4, we start adding more key bits, 6 or 12 at a time. First f4b4, to match bit 6 of R2. Then f1b2 and f2b3, to match bit 7 of R2. At this point, we are most likely already left with a single key, so adding more key bits doesn't increase the computation time. The important thing is to do it 6 bits at a time, in order to avoid unnecessary calculations. Soon enough, we have reconstructed the whole 96-bit key.

This will be the key at a specific address--of course, before running the search we'd have scanned the whole data and selected the address with most different pairs, in order to make the attack more effective.

After the 96-bit key at one address is found, the rest is easy. Since the 96-bit key is modified by the 16-bit result of the first FN in a fixed way, we just use brute force to find the correct 16-bit value at every address, and then we have a full subkey table as when we had the full 8GB tables at the beginning.

The process is working reasonably well, it's taking me 20-40 minutes to find the 192-bit key for a game. It could be made faster, probably. I've done some games for which I had more data, and Razoola was kind enough to provide additional data that will help with many other games. I'm not yet sure that the attack will work on all games, but it surely will on a good percentage.

Some very good news after obtaining more keys is that I found strong correlations between the first and second 96-bit keys, so they are effectively the same key, just permuted. This will also allow to fix the order of the subtables in the s-boxes of the first FN, in the same way I did for the second.

Should we consider ourselves finished after that?

Not yet: whether it will be possible to generate keys for games for which we lack XOR data is an open problem. In that case, the best we can expect to do is to match the startup code from a different version of the game, so we'll have several (E,D) pairs at consecutive addresses, and no more than one pair at a given address. A new attack will have to be devised in order to use that kind of information. Hopefully the discovery that the first and second 96-bit keys are correlated will help.

CPS2 coming to MAME

2007-01-09T23:26:00.000+01:00

I've submitted to MAMEDEV the code to replace the 4GB CHDs with 192-bit keys.
The code is here: http://xoomer.alice.it/nicola.salmoria/cps2crpt.zip
It contains all the information needed to understand the algorithm, including the s-boxes.

There is still a lot of uncertainty about the contents of the s-boxes. They do their job, but since they are different from the originals they also affect the key. Using the real s-boxes might make correlations between the key bits more apparent, if they exist (anyway, having only 7 keys to look at, there's not enough data to speculate on any kind of correlation).

I'm hoping that it will be possible to extract the s-boxes contents from photos of the decapped CPS2 chip. That would be an important step forward in the accuracy of the emulation.

Now the next challenge is finding the keys for the other CPS2 games that have XOR files but not full tables. I have some ideas, but it doesn't look simple.
We have a lot of (E,D,k) triplets for those games, but unfortunately not many once you fix k (the 96-bit key used in the second FN), and that would be the most important part.

Note that we don't have to find the whole 192-bit key all at once. Once the second 96-bit was found, then we could easily use brute force to get the 16-bit key seed at every address, and therefore easily find the first 96-bit key.

CPS2 Fundamental Breakthrough

2007-01-08T02:16:00.000+01:00

Today I realised why I was having problems with the correlations between subkey bits, where some bits had to be derived from the others not only using XOR, but also AND and OR.

The reason was again in the s-boxes that only have 4 or 5 data inputs instead of the full 6. Those boxes contain 2 or 4 subtables, and the order of the subtables inside the box or the order of the bits inside each subtable isn't particularly important when decrypting a single address, because they can always be compensated by appropriate bits in the subkey.

However, when putting all subkeys together, those things became important. E.g. I could be finding that when using subtable #3 in a box, then two of the inputs had to be inverted. To fix this, I had to rearrange the subtables inside the s-boxes to make everything in sync.

The result was excellent. Previously, some of the correlations among the 96 bits were overly complex, taking up to 4 bits at once. Now every bit is directly correlated to another. The only exception is the bits that correspond to the "empty" inputs of s-boxes that take only 4 or 5 data inputs. What this means is that all 6 inputs of all s-boxes always receive the XOR of three sources: either a data bit, a key seed bit, and a global key bit; or two key seed bits, and a global key bit.

That's only the beginning of the good news, though. After fixing the s-boxes, I could attack again the first part on the algorithm on the assumption it was a 4-round Feistel network, and indeed it was.

So the algorithm turns out to be like this:

Take the 16-bit address and a 96-bit key and run them through the first Feistel network, to produce a 16-bit subkey.

Take the 16-bit ciphertext, 16-bit subkey, and another 96-bit key and run them through the second Feistel network, to produce the 16-bit plaintext

So now, for the first time, I would be able to produce a program that algorithmically decrypts one of the game for which we have full tables, without using any table.

It's not yet time to celebrate, though: the s-boxes for the first Feistel network still have to be properly determined, and this might require having access to some more games.

Once that is done, producing keys for games that we have complete tables for will be quite simple.

Finding keys for games for which we don't have full tables, however, is an entirely different matter. As said above, we are potentially dealing with a 192-bit key here; it's possible that the key is smaller and the bits are reused, however since we don't know how they would be, we have to treat it like a 192-bit one. For a key of that size, obviously brute force is out of the question; and while the XOR tables do provide some information, it's probably not the kind of information that would allow to use the differential cryptanalysis techniques we'd need.

CPS2 Won't Be Tamed That Easily

2007-01-07T02:16:00.000+01:00

Some people thought we were almost finished with the CPS2 algorithm, but this doesn't seem to be the case.
True, at least the 4GB tables could now be replaced with a single 128kB table, but that's still not how the hardware works, and it wouldn't be possible to generate proper keys for the games that are missing the full 8GB tables, which is the main concern.

From the full tables, we can extract a 96-bit subkey for every address.
Edit: I had a link to a file here. I've removed it since I've found an error which I'll correct soon.
These wouldn't be the actual keys used by the hardware, however I think me and Andy have agreed that they are, apart from a fixed XOR and bit permutation that wouldn't change from game to game. So we can forget about this step of the decryption for the time being, and move on.

The problem now is to understand how the hardware generates the 96-bit subkey starting from the address and from the global key.

I have determined that only 16 bits are needed to generate the 96-bit subkey; this was sort of expected, but it isn't without problems.
We can generate only 94 bits of the subkey starting from those 16 bits and using only XOR operations. The remaining 2 bits need AND/OR operations, something which I have no explaination for at this point.

That was the least of the problems anyway. The major hurdle at this point is that the mapping from address to 16-bit key seed is very far from trivial.

The scheme should be as follows:

take 16-bit address, N-bit global key, and generate a 16-bit key seed using an unknown algorithm.

take 16-bit key seed, M-bit global key, and generate 96-bit subkey using an unknown algorithm.

take 16-bit ciphertext, 96-bit subkey, and generate 16-bit plaintext using the algorithm we have discovered.

I think it would make sense for the algorithm in step 1. to be another 4-round Feistel network.
If this is the case, things are quite harder than before. To break the other Feistel network, we could rely on complete knowledge of ciphertext-plaintext relationship. Now we can't: we only have a vague idea of what the 16-bit key seed could be.

If we could rely on a 16-bit value except for a constant XOR and permutation, it wouldn't be a problem, since that wouldn't change the nature of the Feistel network. Unfortunately, we don't have that luxury.

Let's see that with an example. Let's say that the first algorithm generates a 4-bit key seed, abcd, which is expanded into the 6-bit subkey ABCDEF this way:

A = a
B = a XOR b
C = a XOR c
D = b XOR c
E = b XOR d
F = b XOR c XOR d

We don't know anything about abcd, all we see is ABCDEF, but we need to guess what abcd looks like. So we notice that

D = B XOR C
F = A XOR C XOR E

and we decide that

a' = A
b' = B
c' = C
d' = E

so we would have

A = a'
B = b'
C = c'
D = b' XOR c'
E = d'
F = a' XOR c' XOR d'

This all works as far as generating the subkey from the seed goes, the problem is that abcd and a'b'c'd' are two completely different numbers! We have that

a'b'c'd' = abcd XOR aab

so this isn't simply a XOR with a constant value, it's a variable modification of the number. And this is something that the Feistel network cannot handle.

CPS2 Subkeys

2007-01-06T14:47:00.000+01:00

I said earlier that I was going to post the program to extract subkeys from a CHD, and the subkey lists for a few games, however after extracting the subkeys I found important relationships between the subkey bits so I'll have to work on that first.

A subkey consists of 24*4 = 96 bits. There are 65536 subkeys, so the total is 786kB of data.

What I found that one bit of the subkey is constant, while 59 can be derived from the others with a XOR (which is constant for all 65536 addresses, but changes from game to game).

So this hints at a 64-bit global key, while the independent subkey bits drop for now at 96-1-59 = 36 bits.

CPS2 S-Boxes ready

2007-01-05T13:42:00.000+01:00

Andy has published his program but is reporting some problems in recreating the original tables--the values generated by his program are XORed with a constant value when compared with the original table.

I have just verified that this doesn't happen to me, so I presume this is due to a different method we used to reconstruct the Feistel function for the first two rounds.

Let's recap how this was done. The fundamental idea was published by Andy:

since R₄ = L₃ XOR F₄(L₄), if you pick (E,D) and (E',D') such that L₄ = L'₄, then

R'₄ = L'₃ XOR F₄(L'₄) = L'₃ XOR F₄(L₄) = L'₃ XOR R₄ XOR L₃

therefore

L₃ XOR L'₃ = R₄ XOR R'₄

Now if we pick (E,D) and (E',D') such that L₄ = L'₄ and E and E' differ by only one bit, we can see how flipping a single bit in the input changes the output after the third round. Andy's fundamental discovery was that flipping certain bits never affects certain other bits.

That knowledge can easily be used to determine F₄. Take (E,D) and (E',D'), where E and E' differ only by one bit which we know doesn't affect bit b in L₃. Then we know that

B_b(L₃ XOR L'₃) = 0

where B_b(x) gives me the value of bit b of x.

Therefore

B_b(R₄ XOR F₄(L₄) XOR R'₄ XOR F₄(L'₄)) = 0

that is,

B_b(F₄(L₄) XOR F₄(L'₄)) = B_b(R₄ XOR R'₄)

Do that for all b and for all E, E' pairs, and you quickly reconstruct the whole F₄ structure. I'm saying its structure and not F₄ itself, because it's all done through XOR so you need to set F₄(0) arbitrarily, then all the others are derived from it through XOR.

After F₄ is reconstructed, it can be used to undo the fourth round of the encryption. Then you repeat exactly the same process to reconstruct F₃ (still XOR an arbitrary value). Then use F₃ to undo the third round, and you are left with just two rounds.

Now things get really simple, because by definition

L₂ = L₀ XOR F₁(R₀)
R₂ = R₀ XOR F₂(L₂)

and since you know all of L₀, R₀, L₂, and R₂, F₁ and F₂ are immediately derived as

F₁(R₀) = L₀ XOR L₂
F₂(L₂) = R₀ XOR R₂

Note that here we derive F₁ and F₂ explicitly, not XOR an arbitrary value.

CPS2 is not a 4-round Feistel network (...NOT)

2007-01-03T22:00:00.000+01:00

Edit: As Andy pointed out, the following reasoning is fatally flawed by the fact that the f_n functions are not bijective.

So, given the strong evidence Andy has found, it really looks like the algorithm is a 4-round Feistel network.

This is actually good news, I have to say I am relieved ;)

Remember that

L₁ = R₀
R₁ = L₀ XOR f₁(R₀)

L₂ = R₁
R₂ = L₁ XOR f₂(R₁)

L₃ = R₂
R₃ = L₂ XOR f₃(R₂)

L₄ = R₃
R₄ = L₃ XOR f₄(R₃)

In the previous article I showed that if we take (E,D) and (E',D') such that L₀ XOR L₄ = L'₀ XOR L'₄ and R₀ = R'₀, then

R₂ = R'₂.

I'll now take a different route from the one I took yesterday, to avoid the flaw that Andy noticed.

From R₂ = R'₂ follows that

L₁ XOR f₂(R₁) = L'₁ XOR f₂(R'₁), that is

R₀ XOR f₂(R₁) = R'₀ XOR f₂(R'₁), that is (since R₀ = R'₀)

f₂(R₁) = f₂(R'₁), that is (since f2 is bijective)

R₁ = R'₁, that is

L₀ XOR f₁(R₀) = L'₀ XOR f₁(R'₀), that is (since R₀ = R'₀)

L₀ = L'₀, therefore

(E,D) = (E',D')

Therefore two different pairs with the requested property cannot exist.

When converting the 16-bit values to and from (L,R) pairs, we need to take the initial and final permutation into account. Note that we are not using R₄ in the above; we are only using L₀, R₀, and L₄. Also, we don't care about the effects of the permutation on L₀ and R₀, the only thing we care about is that when we do L₀ XOR L₄ we XOR the correct bits together. So we can arbitrarily fix the permutation on L₀ and R₀, and try all possible permutations on L₄.

So if the CPS2 algorithm were a Feistel network, for some permutation of the bits in L4 it should not be possible to select two different pairs (E,D) and (E',D') with the requested property.

This doesn't happen: for every permutation, such pairs exist. Therefore CPS2 is not just a 4-round Feistel network.

This is not to say that Andy isn't on the right track, on the contrary, the findings in CPS-2 (5) are extremely interesting, but the algorithm cannot be just a 4-round Feistel network. There's something else we are missing.

CPS2 is not a 4-round Feistel network (maybe)

2007-01-02T23:41:00.000+01:00

Edit Jan 3: Andy has pointed out a flaw in this article. The order of the bits in the L and R groups is important, so we cannot draw any conclusion yet.

Andreas Naive has been doing some very interesting observations lately.

I thought it would make sense to check if we were lucky and the algorithm was indeed structured like a 4-round Feistel network as Andy supposed.

The basic idea of a Feistel network if that you have a round function f() which operates on some bits of the data (8 in our case), and modifies them depending on a key. The function f is the same on every round, while the key changes.

We don't need to care about a key at this point, since we don't know anything about the algorithm. It's easier (and more general) to simply assume that at every round a different function f_n is used, where f_n describes a permutation of the values 0 to 255.

We have decided that there is strong evidence indicating that the 16 bits of the data should be split in two groups of 8 bits like this:
L = { 0, 1, 2, 4, 6, 7, 13, 14 }
R = { 3, 5, 8, 9, 10, 11, 12, 15 }

So a 4-round Feistel network would work like this:
Given the ciphertext E = (L₀, R₀),

L₁ = R₀
R₁ = L₀ XOR f₁(R₀)

L₂ = R₁
R₂ = L₁ XOR f₂(R₁)

L₃ = R₂
R₃ = L₂ XOR f₃(R₂)

L₄ = R₃
R₄ = L₃ XOR f₄(R₃)

and the resulting plaintext is D = (L₄, R₄)

By the properties of a Feistel network, we can also go backwards, starting from D = (L₄, R₄)

R₃ = L₄
L₃ = R₄ XOR f₄(L₄)

R₂ = L₃
L₂ = R₃ XOR f₃(L₃)

R₁ = L₂
L₁ = R₂ XOR f₂(L₂)

R₀ = L₁
L₀ = R₁ XOR f₁(L₁)

Now let's start from both sides and meet in the middle. Going from E to D we have

L₂ = R₁ = L₀ XOR f₁(R₀)

Going from D to E we have

L₂ = R₃ XOR f₃(L₃) = L₄ XOR f₃(R₂)

Putting the two together we have

L₀ XOR f₁(R₀) = L₄ XOR f₃(R₂), that is

L₀ XOR L₄ = f₁(R₀) XOR f₃(R₂)

Now remember that we know all (E,D) pairs, so we can take advantage of that.
If we take (E,D) and (E',D') such that L₀ XOR L₄ = L'₀ XOR L'₄, then it follows that

f₁(R₀) XOR f₃(R₂) = f₁(R'₀) XOR f₃(R'₂)

If additionally E and E' are such that R₀ = R'₀, then we are left with just

f₃(R₂) = f₃(R'₂)

and since f₃ is a bijective function, this implies that

R₂ = R'₂, that is

L₃ = L'₃, that is

R₄ XOR f₄(L₄) = R'₄ XOR f₄(L'₄), that is

f₄(L₄) XOR f₄(L'₄) = R₄ XOR R'₄

Now we can repeat the procedure for all (E,D) pairs, and get a large number of equations on f₄.

If the CPS2 encryption was a 4-round Feistel network, all those equations would not be contradictory, and they would allow us to reconstruct the structure of f₄.

Unfortunately, they are contradictory. E.g. you get something like this:

f₄(0xff) XOR f₄(0xfc) = 0x11
f₄(0xff) XOR f₄(0xfc) = 0x48

Therefore CPS2 is not a 4-round Feistel network.

CPS2 notes, part 5

2006-12-19T19:07:00.000+01:00

In part 1 I showed some constant values in the table that shows how many times flipping a bit in the ciphertext flips a bit in the plaintext.
But there's more than that. It seems that there are more properties which are true for all games, regardless of the key.

      0    1    2    3    4    5    6    7
 0 7FE0 75B0 8028 7AF4 6EB0 8284 734C 7420
 1 8208 7FE0 7E48 7FA4 81CC 8050 72F8 7FDC
 2 7F38 7F8C 8000 7FD0 87B0 7EF4 7BF8 8068
 3 7200 6CA0 7B00 76E0 6800 8044 B280 8180
 4 7F18 7FCC 7F84 8130 7BC4 80E4 8154 8014
 5 8980 7B80 7780 81D4 6200 7D78 7540 7DE0
 6 83C0 7E98 7F3C 831C 6CF0 8080 7BD8 7D20
 7 80B0 81B0 7EAC 8190 7DB4 8050 8364 7F68
 8 7D80 80E0 7D80 8110 78C0 7FC4 6F40 8DA0
 9 5080 7510 C000 643C 6DC0 8414 4800 72C0
10 7BE0 7A30 7F40 7F08 6A00 8110 7720 7B80
11 8040 81A0 7E80 7E2C 5680 7FFC 73C0 8020
12 7A80 8370 7100 818C 7E80 7BE8 6200 8060
13 8018 7D24 8040 7F60 7E2C 80EC 7F9C 7EA0
14 7D18 7F00 7EEC 80DC 799C 7F90 7F34 8010
15 7E80 8710 8540 8128 8200 7F50 7C40 8540

      8    9   10   11   12   13   14   15
 0 8054 7C58 7BF4 7E88 7C80 7610 7C7C 7C28
 1 8008 7FA4 80F0 8020 7FB8 7E24 7EE8 8078
 2 7FB8 7F18 7FE4 7F14 7FDC 80C0 7C3C 8130
 3 80DC 7F34 7EE0 8124 77F0 7800 5A80 7064
 4 800C 7F98 7D3C 7E60 803C 7C74 80E0 80A0
 5 8024 7BA8 79C8 8020 7A24 7E00 7F60 7AAC
 6 7F80 7E94 7B08 7FE8 7E98 6DA0 7FD4 7E50
 7 7FE8 7E20 7D6C 7F88 8004 7BD4 803C 7FCC
 8 7F4C 7FE4 7E48 7F10 7F40 7FC0 74C0 82B4
 9 812C 8064 6520 78D8 7D5C 5040 5800 8588
10 7D50 7FB8 883C 7E00 7EDC 8A00 78E0 7FDC
11 7EF8 7F64 7860 7E30 804C 6780 82C0 81E8
12 8094 7CCC 7A44 7EF0 7FC0 7C80 8100 7EF4
13 8180 7FA0 7FF4 8084 8000 8088 7F9C 8024
14 8004 8080 809C 7F44 806C 8044 7A5C 7FEC
15 7EC0 814C 7A10 7F2C 7E80 9200 7E20 8064

    are constant.

    are correlated and can be only one of 2 quadruplets.

                are all correlated and values can be taken in one of 4 "groups".

Once chosen the group:
    are correlated and can be only one of 2 pairs.
    are correlated and can be only one of 2 pairs.
    are correlated and can be only one of 4 pairs.
    are fixed by     and    .

So in total there are 2x4x2x2x4 = 128 combinations. Each combination is used by exactly 256 tables.

Note the symmetry of it all. 16 values are affected, related to 2 bits of the ciphertext and 8 bits of the plaintext.

This suggests that the algorithm might work on the data 8 bits at a time, or even only 4 bits at a time. The regular behaviour could be caused by a step, at the beginning or at the end of the algorithm, that doesn't use the key.

Another thing we can do is check which of the 128 combinations corresponds to each memory address, and look for a way to correlate the two. Unfortunately there doesn't seem to be a simple way to do that.

CPS2 notes, part 4

2006-12-19T11:17:00.000+01:00

I have to stress that there is NO progress being made in breaking the encryption. The things I am showing in these notes have been known for over a year and haven't lead to any breakthrough. Hopefully, a public discussion of these properties could generate some valuable feedback.

There also isn't any kind of competition against the people that are attacking the CPS2 encryption in hardware. On the contrary, I think that the hardware path will be the only way to gather more information about the algorithm.

In these notes I have shown several properties that are always true, regardless of the key. This means that they are properties of the algorithm itself, and therefore are hardcoded in hardware. For example, there almost surely are fixed substitution boxes which could be extracted from the custom CPU.

If an algorithm is reconstructed by studying the CPU, we can also test it against the known properties, regardless of the key. If it doesn't match, then the algorithm isn't right. Once an algorithm fitting the properties is found, we can start looking for the key.

CPS2 notes, part 3

2006-12-18T22:34:00.000+01:00

In part 1 we were flipping bits in the ciphertext, and seeing what happened to bits in the plaintext.

We can do the opposite, of course, and there's something unexpected in the results.
I'll show the total number of times the bits change (in hex) instead of percentages, to make the point more visible.

      0    1    2    3    4    5    6    7
 0 80BC 7844 7E24 7FD4 7EBC 8090 8138 8044
 1 7FB0 8138 7A90 7EB0 7D54 7F04 7FE4 8074
 2 7F20 7F30 81A4 8018 80C4 7FB4 7F08 7EF8
 3 7F30 8180 7D10 7EA0 6F40 7E30 85E0 79E0
 4 7EA8 7B1C 8240 7FD4 7DE4 7F24 7F44 80C4
 5 A2C0 6D00 6CC0 69E0 6700 7F28 5E00 4E00
 6 7F5C 7ECC 7FB8 7FF8 7C38 7FF0 7EF0 7CAC
 7 7FD0 7D80 8168 8058 8104 7FA0 7FAC 80E8
 8 71E0 B500 8E80 8020 7900 8124 7980 8240
 9 7A20 6E40 7AE0 7FA8 8080 7F84 8240 88E0
10 7930 6900 7A50 81BC 7220 7C48 7A20 6FC0
11 7950 8C00 7600 8054 6F20 806C 7CE0 89C0
12 6F40 4B00 85C0 8010 7600 809C 7E00 7E80
13 7F30 7B20 7FB8 8028 803C 80B4 7E80 8140
14 7A90 8034 7D4C 8124 80D8 7E8C 7FC8 7FC0
15 73F0 79C0 7990 80D0 9440 7D94 7AC0 6EA0

      8    9   10   11   12   13   14   15
 0 8048 7E84 7DB8 801C 80B8 80A4 62BC 7FB0
 1 803C 7FE8 7E20 81E8 80F0 7D68 8144 7FBC
 2 807C 80C4 7F80 7FFC 7F90 7EE0 82B0 80B4
 3 7EB0 80E0 7E68 7F70 7E78 8010 7580 7BBC
 4 7FF0 7F68 7FB8 7FFC 7FAC 8074 7DD4 813C
 5 7F08 6FA0 7254 6BB8 6C10 6380 6300 7AE8
 6 7FF4 7F9C 8018 7FCC 8138 8118 6E14 80BC
 7 8088 80DC 7FC0 7DB8 7F8C 7EE4 84E0 7F48
 8 7EEC 8090 84EC 7E28 8328 8960 2D00 85AC
 9 7F94 7EA4 7D6C 8080 8068 8200 5FC0 82F0
10 7AF0 80AC 80C8 7CB4 8054 8640 7100 7F8C
11 81F0 8080 7F2C 8064 7F94 82C0 6E80 7B30
12 809C 7FD0 7F98 7ED0 75C8 83C0 D300 7CE8
13 8134 8160 80A0 7F40 7D6C 809C 80E4 7F58
14 7F68 7F14 7F44 7F28 8010 7EB4 7F10 7F80
15 82E0 7D4C 78D8 804C 8000 78A0 6240 75DC

The values highlighted in orange are the only two that are constant in every table (there were four in the inverse table).

But the values highlighted in red are the most interesting. They are not constant--they can vary among a few possible values. But the sum of the two values in each column is constant, and it's always 0x10000.

Why? I have no idea.

CPS2 notes, part 2

2006-12-18T14:32:00.000+01:00

The complementation property was an important discovery--and not just because it reduces the size of the tables in half. Still, we haven't taken full advantage of it yet.

Let's recap the basics of the CPS2 encryption first.

Inputs:

16-bit value stored in ROM

16-bit address (bits 1-17 of the physical address)

key of unknown size, different for every game

Outputs:

16-bit decrypted value

Let's call D(X,A,K) the decryption of value X at address A using key K.
The complementation property says that for every A there is exactly one A₁ such that

D(X,A,K) = D'(X',A₁,K)

where x' is the complement of x.

This finding is important because it shows that A has an algorithmical effect on the encryption. In Sega's FD1094 CPU, the key for every address is just stored in a huge table. If the CPS2 CPU worked in the same way, the complementation property wouldn't happen.
This isn't too much of a surprise: with the Kabuki CPU, we had already seen that Capcom preferred a complex algorithm with a small key, while Sega preferred a simpler algorithm with a huge key.

Unfortunately we don't yet know how to calculate A₁ given A. It varies from game to game so it must be a function of the key.

The complementation property isn't unheard of, even in strong ciphers, so it isn't necessarily a weakness in the algorithm. For example, DES has it. In that case, it reads D(X,K) = D'(X',K').

In general, the complementation property indicates that there are probably XOR operations happening, which cause the complement operation to cancel out. Let's see this with an example: consider a substitution function f, and an algorithm such that

d = e XOR f(e XOR k)

if we take the complements we have

e' XOR f(e' XOR k') = e' XOR f(e XOR k) = (e XOR f(e XOR k))' = d'

of course this is a very simple example. Note that x' doesn't have to be the complement in this case: you can define it as e.g. x' = x XOR 1, and it will still work. So the CPS2 algorithm obviously isn't that simple.

A more realistic example would be a Feistel network (note that DES is an example of a Feistel network).

If you define the Feistel network as
L_i = R_i-1
R_i = L_i-1 XOR f(R_i-1 XOR K_i-1)

it should be easy to see how the complementation property would ensue.

The idea of the CPS2 encryption being a Feistel network is tempting, however I don't think this is the case, because I would expect the diffusion to be much better than what we have seen in part 1.

CPS2 notes, part 1

2006-12-17T20:38:00.000+01:00

Since the finding of the complementation property almost one year ago, there has been no progress at all on the CPS2 encryption.

I'm going to explain here some of the (remarkably few) things we know about the encryption.

A common misconception is that the decryption tables look like "random data". They may look so to the naked eye, but the most basic statistical checks show that this isn't the case.

Take an encrypted value, change a bit in it, and look at what happens to the output. For a random table, you'd expect every bit in the decrypted value to change with 50% probability. This isn't happening.
Take a look at the following statistics taken on a single table: on rows, you have the encrypted bit that changes; on columns, the frequency with which the decrypted bit changes.


       0      1      2      3      4      5      6      7 
 0 50,26% 44,09% 50,98% 49,68% 42,94% 50,81% 44,99% 43,87%
 1 49,52% 49,73% 49,87% 49,90% 49,32% 49,77% 45,37% 50,43%
 2 49,62% 50,05% 49,67% 50,25% 51,56% 49,86% 49,07% 50,07%
 3 44,53% 45,75% 48,05% 48,93% 40,63% 50,22% 69,73% 44,29%
 4 49,83% 50,19% 49,62% 49,98% 48,35% 49,88% 50,38% 50,57%
 5 50,24% 46,53% 50,78% 50,21% 28,13% 49,79% 44,63% 47,80%
 6 51,92% 49,73% 50,10% 50,17% 38,28% 50,10% 48,35% 47,86%
 7 50,29% 49,51% 49,16% 49,86% 48,35% 49,93% 50,85% 50,07%
 8 51,95% 52,51% 51,37% 48,71% 49,22% 50,07% 43,55% 46,78%
 9 31,45% 48,32% 75,00% 43,55% 46,39% 50,51% 28,13% 46,92%
10 50,20% 50,95% 51,37% 49,78% 28,13% 50,06% 47,17% 51,66%
11 45,17% 45,85% 47,66% 50,38% 25,20% 50,58% 44,43% 53,37%
12 47,85% 47,51% 44,14% 50,04% 53,03% 49,24% 38,28% 49,17%
13 49,68% 49,90% 49,43% 50,10% 50,02% 49,46% 50,05% 49,89%
14 49,35% 50,32% 49,98% 49,80% 48,29% 49,65% 49,48% 50,42%
15 48,97% 51,59% 51,07% 49,57% 67,19% 49,55% 45,70% 50,39%

    8      9     10     11     12     13     14     15
 0 50,43% 48,46% 49,02% 49,49% 49,21% 43,35% 49,05% 47,69%
 1 49,85% 49,69% 50,57% 49,76% 50,01% 49,40% 49,88% 50,15%
 2 50,14% 50,05% 49,86% 49,57% 50,25% 50,96% 48,99% 50,18%
 3 49,46% 50,18% 48,31% 50,30% 46,96% 40,63% 35,35% 44,34%
 4 49,82% 50,43% 49,70% 50,34% 49,79% 47,74% 50,16% 49,57%
 5 49,91% 48,74% 49,68% 49,88% 48,79% 28,91% 49,02% 48,36%
 6 49,74% 49,21% 50,24% 49,62% 49,40% 39,32% 49,91% 49,62%
 7 50,14% 50,03% 49,63% 50,39% 49,65% 47,67% 50,43% 49,37%
 8 49,83% 49,96% 48,57% 50,43% 49,15% 40,63% 46,97% 50,50%
 9 50,15% 49,08% 44,80% 48,27% 49,65% 50,78% 34,38% 50,81%
10 49,76% 49,92% 50,28% 49,24% 49,21% 67,97% 49,27% 49,87%
11 47,55% 50,00% 50,16% 47,17% 49,61% 25,39% 48,93% 51,68%
12 49,83% 48,97% 49,69% 49,86% 49,30% 52,93% 50,39% 49,90%
13 49,85% 50,37% 50,52% 49,94% 49,60% 51,22% 49,96% 49,92%
14 49,85% 50,18% 49,97% 49,89% 50,09% 49,84% 47,50% 49,64%
15 49,49% 49,37% 49,39% 50,09% 49,57% 38,28% 49,17% 49,57%

So there is a large number of values around 50%, which look just random, but there are also values very far from that.

This indicates that the encryption algorithm doesn't have good diffusion. This is a weakness, though it hasn't been exploited yet.

Of particular interest are the four values I highlighted in red. While the other values change from game to game and from table to table, those four values are always the same. E.g. flipping bit 9 in the encrypted value causes bit 0 in the decrypted value to flip exactly 0x5080 times out of 0x10000, for every game, at every address.

This property is quite interesting. It is the most obvious "signature" of the algorithm. Does it help? Well, it tells us that if the algorithm contains bit permutations that depend on the key, those permutations cannot affect bits 3 and 9 in the encrypted value, nor bits 0 and 14 of the decrypted data. Apart from that, however, the property doesn't tell us much, because even if we know that the bits have to change that many times, we don't know exactly when to flip them. Discovering that would be a significant advance in the understanding of the algorithm.

Katamino

2006-12-08T15:31:00.000+01:00

(This article is not MAME related)

Some time ago I was shopping looking for a set of Pentomino pieces and found this game called Katamino®.

It looked like a decent enough set of wooden pieces, so I bought it. Pentominoes are a decades old puzzle, so I didn't expect anything more than that. Instead, when I opened the box, I was blown away by how cleverly the puzzle is presented.
The idea is credited to André Perriolat, who is the owner of the company that produces the game, DJ Games.

Here is how it works: take four pentominoes, and make a 5x4 rectangle with them. After you've accomplished that, add another pentomino, and make a 5x5 square. Then add another, and make a 5x6 rectangle. And so on, until you add the final piece to make a 5x12 rectangle. The box contains a board with a moving slider to place your pieces in.

There is only one rule: when you add the I piece, you cannot place it vertically. Otherwise it would be cheating, since you could take the solution to the previous puzzle and just stick the I to the side.
For the same reason, the I piece is not used for the 5x5 puzzles, since even if you put it horizontally it would still be a 5x4 rectangle with the I stuck to the side.

In the box there's a list of 12 such sequences that you can follow, each one ending with a different piece.

This is absolutely brilliant. You start with easy puzzles wich practically anyone can solve, and then gradually increase the difficulty until you complete the full puzzle--or run out of patience, whichever comes first.

Every time you complete one of the puzzles there's a sense of achivement--and then immediately of frustration, because to add one more piece you have to throw away the perfect shape you just created, and start again from scratch.

I liked this idea so much that I started thinking about it. How many ways are there to build sequences to play the game? Are the ones provided the best possible, or can they be improved? Let's see what the goal is:

build 12 sequences, each one ending with a different piece

every combination of pieces must be used only once

Things get interesting from the start. There are only 19 ways to select 4 pieces that can form a 5x4 rectangle; but 6 of them cannot be extended to 5x5 without using the I piece. This leaves us with 13 initial choices, just one more than what we need.

How can we rate our sequences to decide which ones are better than others? The obvious answer is to look at the number of different solutions for each combination of pieces. The less the solutions, the better the puzzle is. If two sequences have the same number of solutions, then the one that contains more puzzles which have a single solution is better.
The 5x11 puzzles are obviously the same for every choice, so we don't have to count them. This leaves us with 12 sets of 7 puzzles (from 5x4 to 5x10) for a total of 84 puzzles, which we want to be as hard as possible.

Turns out that the sequences accompanying my copy of the game aren't very good: there's a total of 3084 solutions, and only 20 puzzles with a single solution. Even worse, one of the puzzles is repeated twice.
It seems that I have and old version of the game (the instructions say (c) 1992-1998). The version currently being produced uses a better list, whith 1556 solutions and 26 single solutions (and no duplicates).

Writing a program to find the best solution is a remarkably difficult task. I'm not even sure if it has been classified. If it is, I'd expect it to be as part of problems related to graph theory.

With a mix of manual pruning and computer search, I've selected this sequence which looks quite good:


L P U F [1] W [1] I [4] Z [1] T [5] N [1] V [83] Y [1277] X [786]
L Y U F [3] Z [1] I [2] N [2] T [4] X [2] V [16] P [ 508] W   "
Y N V T [1] F [1] I [3] W [1] U [5] X [1] L [ 8] P [ 371] Z   "
L Y P W [5] N [1] V [1] I [5] X [1] Z [5] F [25] U [ 216] T   "
Y P U F [1] T [1] I [2] Z [1] N [2] X [1] W [ 2] L [ 183] V   "
L Y P T [1] W [1] F [1] N [5] X [3] Z [1] I [ 8] V [ 133] U   "
L V P Z [2] Y [1] T [2] I [5] X [1] W [1] F [15] U [ 125] N   "
L Y P Z [1] W [2] T [1] V [1] X [1] U [3] N [21] I [ 116] F   "
L N P U [2] Z [2] X [1] V [1] F [1] T [2] W [14] Y [ 112] I   "
L N V Z [2] U [1] T [1] F [2] I [6] W [3] X [ 1] P [ 101] Y   "
Y N P U [1] V [1] Z [1] X [1] F [2] T [1] W [ 1] I [  59] L   "
L Y V U [2] Z [1] F [1] W [1] X [1] N [1] T [ 1] I [  14] P   "

The numbers in square brackets are the solutions for each puzzle.
The total is 331 solutions, and 45 puzzles with a single solution.

I think this should be quite close to the minimum, but I don't have a way to prove it.

Can anyone do better?

Completed, at Last

2006-08-05T14:11:00.000+02:00

As you'd probably noticed, the pics in the previous post are of the Bubble Bobble custom MCU.

Despite being one of the most popular games of all times, and having been in MAME for many years, the emulation of this game has never been perfect due to the lack of the original ROM for the MCU.

For some time, we had been using a 68705 program found in a bootleg board, believing it had been extracted from the original. However, monster behaviour was wrong and there were other problems, like the wrong behaviour of the clock item.

After some study of the program and of the game schematics, it became clear that the original MCU is not a 68705 at all (the pinout doesn't match) but looked more like a 68701.
The 68705 program had been written from scratch by the bootleggers using black box reverse engineering techniques, by running the original MCU and logging all its reads and writes from memory. Indeed, the 68705 program does a lot of reads from memory without doing anything with them--simply because the original MCU would read that memory and do some unknown action with it.

Eventually, the useless 68705 program was replaced by simulation code inside the emulator, which greatly improved the emulation accuracy. Monster behaviour was improved, the clock item behaviour fixed. However, there were still some unknown things, like how the randomisation of the EXTEND bubbles really worked.

At last, thanks to excellent work by Trinity, the original MCU ROM has been extracted. This required removing the cover from the chip, taking photographs of it under a microscope, and manually decoding the contents of the ROM bit by bit. The photo shown in the previous post confirms that it's in the 6801 class, not a 68701 however as it was conjectured, but a 6801U4.

With this ROM, we finally have the final piece of the puzzle for a 100% guaranteed perfect emulation.

Checking the original MCU program was very interesting. It was designed to provide many protection features that were eventually not used by the game, like:

process coin inputs and update the credit counter
handle the number of remaining lives for both players
handle the current round number
handle variable speed incrementing for four variables
return values from a 1280 bytes table of seemingly random data

The reasons why those features were not used are probably various. Some of them were probably awkward to use because they require to one one frame for the MCU to process the data, others weren't flexible enough like the coin input processing that wouldn't allow for coinage settings different from the ones hardcoded in the MCU (though versions of Bubble Bobble with different coinage settings don't seem to have been made anyway).

So, how close was the simulation to the real thing? Very close; "too good", actually. Let's see why.

The clock item behaviour was spot on, but off by one frame (the simulation made the counter expire one frame too late).

The EXTEND randomisation simply doesn't exist in the original MCU. While the simulation code used a RNG to provide truly random letters, the original MCU simply increases the counter every frame. This seriously affects the game, making the EXTEND letters predictable.
Since a new bubble enters the screen exactly 128 frames after the previous one, and the remainder of 128 / 6 is 2, this means that if you get consecutive letters each one will be 2 places after the previous one. So if you get 3 letters you can get either E, T, N or X, E, D. After that they will repeat. There are exceptions, though: if you create a new bubble in exactly the same frame when a new bubble should enter the screen, the bubble is delayed by one frame. So by timing the fire button exactly right you can change the bubble order. In theory you could get all 6 letters in a single level--let me know if you manage to do that! :)
Also, new bubbles will not appear if there are already 16 bubbles on the screen, so that will change the order as well.

The last, and most important, thing that the MCU does is compare the player coordinates with the monsters. The results are returned as flags indicating whether each coordinate is >, =, or <, and the absolute difference. This was done correctly in the simulation code, however there appears to be a bug in the original MCU. The code there attempts to check if the player collided with a moster and set a flag and indicate which monster in that case, but it just doesn't work. It would set the flag even if the player's Y coordinate matches one monster and the X coordinate matches a different monster!
This isn't much of a problem since the main program just ignores the flag--the collision detection is done correctly by the second Z80.
However, the MCU also completely stops processing the monster coordinates as soon as it finds a monster whose X coordinate is within 8 pixels of the player. So e.g. if you have a monster right above you three platforms up, and that monster is the first in the list, the other monsters could stop following you. This is a very subtle effect that's completely unnoticeable from what I can tell, though in theory it exists.

Good News

2006-08-03T22:47:00.000+02:00

What's inside this?

This:

Political Digression

2006-06-20T11:01:00.000+02:00

Forgive me for abusing of this space to talk about an important matter of Italian politics.

Il 25 e 26 giugno siamo chiamati alle urne per uno dei più importanti voti della storia della Repubblica. Dovremo decidere se mantenere la nostra Costituzione del 1947, o se adottarne una nuova.

Questo è l'articolo 70 nella nostra Costituzione:

"La funzione legislativa è esercitata collettivamente dalle due Camere."

Questo è l'articolo con cui verrebbe sostituito se la nuova Costituzione sarà approvata dal referendum:

"La Camera dei deputati esamina i disegni di legge concernenti le materie di cui all'articolo 117, secondo comma, fatto salvo quanto previsto dal terzo comma del presente articolo. Dopo l'approvazione da parte della Camera, a tali disegni di legge il Senato federale della Repubblica, entro trenta giorni, può proporre modifiche, sulle quali la Camera decide in via definitiva. I termini sono ridotti alla metà per i disegni di legge di conversione dei decreti-legge.
Il Senato federale della Repubblica esamina i disegni di legge concernenti la determinazione dei princìpi fondamentali nelle materie di cui all'articolo 117, terzo comma, fatto salvo quanto previsto dal terzo comma del presente articolo. Dopo l'approvazione da parte del Senato, a tali disegni di legge la Camera dei deputati, entro trenta giorni, può proporre modifiche, sulle quali il Senato decide in via definitiva. I termini sono ridotti alla metà per i disegni di legge di conversione dei decreti-legge.

La funzione legislativa dello Stato è esercitata collettivamente dalle due Camere per l'esame dei disegni di legge concernenti le materie di cui all'articolo 117, secondo comma, lettere m) e p), e 119, l'esercizio delle funzioni di cui all'articolo 120, secondo comma, il sistema di elezione della Camera dei deputati e per il Senato federale della Repubblica, nonché nei casi in cui la Costituzione rinvia espressamente alla legge dello Stato o alla legge della Repubblica, di cui agli articoli 117, commi quinto e nono, 118, commi secondo e quinto, 122, primo comma, 125, 132, secondo comma, e 133, secondo comma. Se un disegno di legge non è approvato dalle due Camere nel medesimo testo i Presidenti delle due Camere possono convocare, d'intesa tra di loro, una commissione, composta da trenta deputati e da trenta senatori, secondo il criterio di proporzionalità rispetto alla composizione delle due Camere, incaricata di proporre un testo unificato da sottoporre al voto finale delle due Assemblee. I Presidenti delle Camere stabiliscono i termini per l'elaborazione del testo e per le votazioni delle due Assemblee.
Qualora il Governo ritenga che proprie modifiche a un disegno di legge, sottoposto all'esame del Senato federale della Repubblica ai sensi del secondo comma, siano essenziali per l'attuazione del suo programma approvato dalla Camera dei deputati, ovvero per la tutela delle finalità di cui all'articolo 120, secondo comma, il Presidente della Repubblica, verificati i presupposti costituzionali, può autorizzare il Primo ministro ad esporne le motivazioni al Senato, che decide entro trenta giorni. Se tali modifiche non sono accolte dal Senato, il disegno di legge è trasmesso alla Camera che decide in via definitiva a maggioranza assoluta dei suoi componenti sulle modifiche proposte.
L'autorizzazione da parte del Presidente della Repubblica di cui al quarto comma può avere ad oggetto esclusivamente le modifiche proposte dal Governo ed approvate dalla Camera dei deputati ai sensi del secondo periodo del secondo comma.
I Presidenti del Senato federale della Repubblica e della Camera dei deputati, d'intesa tra di loro, decidono le eventuali questioni di competenza tra le due Camere, sollevate secondo le norme dei rispettivi regolamenti, in ordine all'esercizio della funzione legislativa. I Presidenti possono deferire la decisione ad un comitato paritetico, composto da quattro deputati e da quattro senatori, designati dai rispettivi Presidenti. La decisione dei Presidenti o del comitato non è sindacabile in alcuna sede. I Presidenti delle Camere, d'intesa tra di loro, su proposta del comitato, stabiliscono sulla base di norme previste dai rispettivi regolamenti i criteri generali secondo i quali un disegno di legge non può contenere disposizioni relative a materie per cui si dovrebbero applicare procedimenti diversi"

La nuova Costituzione modifica più di 50 articoli della Costituzione originale. Credo che questo articolo da solo sarebbe sufficiente per decidere quale delle due è migliore. La nostra Costituzione è elegante, essenziale, efficace. La si vuole sostituire con una cosa verbosa e incomprensibile, scritta come una leggina qualsiasi, in cui si fa riferimento all'articolo X comma Y lettera Z. E' una cosa vergognosa. Non si può. Non va bene. E' la nostra Costituzione, non è una leggina qualsiasi. E' il documento fondante della nostra Repubblica, un documento che un ragazzo della scuola media dovrebbe poter leggere e capire senza difficoltà.

Still some doubts about Bubble Bobble

2006-02-24T00:30:00.000+01:00

The emulation of Bubble Bobble is already virtually perfect, but there is still a doubt about the clock item.

Currently, when you pick it up the enemies stop but the bubbles continue moving.

It would make sense if the bubbles stopped moving too, and this idea is corroborated by the way variables are set up in the MCU shared RAM. The MCU would be responsible for stopping the bubbles and make them start again when the clock effect ends.

What we need is to verify the behaviour on an original board. Bootlegs don't count (the clock behaviour is definitely wrong in them), nor do other emulator or ports count. Only the original board matters.

Can anyone help?

Coinmaster

2006-02-04T01:11:00.000+01:00

Pierpaolo Prazzoli made me look at the encrypted question ROMs of the Coinmaster games.

It's nothing interesting, just a permutation of the address and data lines. The interesting thing, however, if how they gave away the encryption on the data lines by implementing the ROM checksum test in an unwise way.

To verify the checksum, the game reads all bytes in the ROM except the one at offset 2, and adds them with 8-bit arithmetic. It then takes the opposite of the result and compares it with the byte at offset 2, expecting them to be equal. What this actually means, however, is that adding all bytes in the ROM will always give as result 0.

Knowing that the sum of all bytes must be 0 instantly kills the data lines encryption. All one has to do is try to apply different permutations on the encrypted data, and calculate the resulting checksum. First look just at bit 0, ignoring the others. Try a permutation that leaves it in place, then one that replaces it with bit 1 of the encrypted data, then bit 2, and so on. Look at bit 0 of the resulting checksum. If it's 0 for all ROMs, then you got the right bit. So, in at most 8 tries, you'll find bit 0 of the permutation. Then move on to bit 1, and repeat the procedure. In at most 7 tries, you'll find bit 1 of the permutation. And so on.

8GB / 2 is still 4GB

2006-01-15T17:59:00.000+01:00

sfzj_049e38[x] ^ 0xffff == sfzj_05ee0c[x ^ 0xffff]

Strange that nobody noticed

2005-10-26T10:13:00.000+02:00

Check the final level of Fairyland Story ending on MamEnd.
The background graphics are quite obviously broken in the top left corner! Strange that nobody reported this bug.

Anyway, I've fixed it now.

I've also been studying what the MCU does in that game, and the programmers made some interesting choices.

First of all, the MCU can return data stored in its internal ROM. This is done with short tables that are needed at the beginning of a level, and when you die. More interestingly, the text needed for the continue screen is stored there, and since you can't continue until level 8, it would take some time for a bootlegger to notice the problem. Even more interestingly, the endgame text is stored there, so one would have to play all the 101 levels to get to the protection.

Another wicked part of the MCU protection is that before action starts in a level, the game takes three bytes, performs complicated calculations on them to convert them into an 8-byte number passed to the MCU, and the MCU then performs more complicated calculations, recovers the original bytes and sends them back. A lot of work to essentially do nothing.

Finally, during the final level, the MCU is used to calculate and update the trajectory of the dragon's fireballs. Without the MCU, the dragon doesn't fire. I just have to wonder: why bother? How many people would have reached the final level in the arcades? And would bootleggers have bothered anyway? Figure some player going to the arcade owner and asking for her quarter back because the ending was too easy :)

Snowball effect

2005-05-04T20:24:00.000+02:00

As you might already have seen on Haze's WIP, yesterday I succeeded in decrypting Gardia and Space Position.

This was an interesting case of pieces falling into place rapidly one after another.

The first piece was the decryption of Calorie Kun, thanks to a decrypted bootleg which was recently found. This didn't look like a particolarly interesting breakthrough at the moment: the encryption algorythm was already known, the key would have been difficult to find by hand but with the reference of the bootleg it could be derived automatically in a few minutes - just the time to write a program.

This renewed my interest in the remaining Sega encrypted games that use this algorithm, in particular Gardia. David Widel revealed that he had decrypted a portion of it months ago, but got stuck and put aside the results without publishing them. Believe it or not, he decrypted most of the code by comparing it with My Hero - even if that's a completely different game, it shares a lot of almost identical code with Gardia.

The data David provided was very useful to get started. Another really useful coincidence was that we have two sets of Gardia (one supposedly being a bootleg, but still encrypted). The two sets are different versions, with code shifted by a few bytes in places. This is an ideal situation when decrypting games that use simple algorithms like this one. When you have decrypted a portion of code in one set, you can use it to decrypt the same portion of code in the other set; but this way you also automatically decrypt some more code in the second set, which is still encrypted in the first set, so you can go back to the first set and decrypt even more code, and so on - you slowly build up the two keys in parallel.

While I was doing this, I rapidly noticed that the key used by the second set for opcodes was identical to the one used by the first set for data. Shortly afterwards, I also noticed that the key used by the second set for data was identical to the one used by the first set for opcodes - just shifted by one byte.

At that point I was on the lookout; I have to admit that I didn't notice it immediately, but eventually I discovered that the keys were actually the same as Calorie Kun, apart from the shift. When I found that, I just copied the whole Calorie Kun keys and I was almost finished - Gardia booted but had some problems. I just had to find a few more bytes at the end of the key to fix them.

Space Position was the easiest of all. At that point I was almost sure it would have used the same key. I checked some bytes of the partial key I had manually derived years ago, matched them with the known key, copied over the data with the appropriate shift, launched the game, and it was already working, on the first try - apart from the emulation issues which Haze later fixed.

This completes the decryption of all currently known Sega games using the "easy" Z80 encryptions. Unfortunately there are a few encrypted Z80 games left, using the suicide MC8123 CPU, which might be lost forever: all boards using the CPU seem to be dead, and the key is just about impossible to find without an hardware attack.

Easier than expected

2005-04-22T00:00:00.000+02:00

Bryan noticed that changing a single value in the Pocket Gal Deluxe decryption (related to the address scrambling) revealed some clear text in Diet Go Go. THis means that the encryption key is almost hardcoded as I expected, but with some minor variation (maybe externally to the DE102 iself).

I have isolated the variations in just two numbers, a 16-bit one for the address scrambling and an 8-bit one (or two 4-bit ones) for the data bits permutation and xor.

Fine tuning the values to correctly decrypt data in Diet Go Go was easy enough.

Double Wings required a little more works, but it was still easy. I just needed to brute force the 16-bit parameter. Doing that was easy because I just had to decrypt the ROM using each possible value for the parameter, and count how many zeros were in the decrypted data. When their number rised from a couple of thousands to tens of thousand, I had a "good enough" value for the parameter, which I could later tweak by hand.

So, data was decrypted in all four games (the other one is Boogie Wings which decrypted with the same parameters as Pocket Gal Deluxe), but opcodes were still encrypted.

However, most of the work was already done. Even if the opcodes are encrypted differently from data, the address scrambling must of course be the same, otherwise there wouldn't be a 1:1 correlation between logical address and physical address. Therefore, only the data bits permutation and xor changes.
The obvious candidate for that variation was the 8-bit parameter. A brute force search was even easier in this case. I just had to try all possible values and count how many times 4E75 (the opcode for RTS) appeared. When it increased from a couple of times to several hundreds, I had the key.

So all four known games using this CPU (Pocket Gal Deluxe, Diet Go Go, Double Wings and Boogie Wings) should now be fully decrypted.
Non of them is working; for that, the driver will have to be finished, and possibly some more protection worked around. But the first hurdle has been overcome.

DE102

2005-04-20T21:28:00.000+02:00

The recent discovery of a decrypted bootleg of Pocket Gal Deluxe was a pleasant surprise. This is one of a handful of games that use the same encrypted custom CPU - called DE102.
It is now confirmed that the CPU is a 68000.

Thanks to the bootleg, I was able to figure out the decryption algorithm. It is quite straightforward, and it involves:

Address scrambling. When the CPU wants to read a word from logical address N, it fetches it from ROM space at address N'. The scrambling of the address requires 16 conditional XORs with 16-bit values.
Data bits permutation. After reading the word from ROM, the order of its bits is altered. There are 16 possible permutations; which one to use depends trivially on the logical address.
Data XOR. After changing the bit order, the value is XORed with one of 16 other values. Which one to use depends trivially on the logical address.

While working on Pcket Gal Deluxe, I was hoping that the DE102 would use a fixed key, which would have emant free decryption of a few other games. Unfortunately, this turned out to not be the case. The algorithm surely is the same, but the key is different.

Determining the key without having a decrypted version to compare with is a lot more difficult, as you can imagine. Also, it seems that at least one of the other games encrypts data and opcodes differently, which makes things a lot more complicated.

In the next days, I'll see if I can find a way to break the key somehow.

Great Swordsman colors

2005-04-11T14:03:00.000+02:00

Sprite colors in Great Swordsman have been one of the longest standing and most elusive emulation imperfections to date.
It was hardly noticeable, because a manually crafted lookup table had been crafted in the driver, so colors looked ok.

Finally, thanks to Kold666's invaluable help, the emulation is now perfect.
As you can see in the shots, the difference is subtle but it's there. It is probably most evident on the pulsing logo, whose color changes are now slightly smoother.

The way how I achieved this is worth of mention. Kold kindly provided some pictures of the pcb (parts side and solder side). I x-flipped the solder side, overlapped them in a gfx editing program, and carefully aligned them so I could see both layers at once. Then started tracing from the color lookup PROM, to see what the board does with the data.

In the end, it turned out that the sprite palette data comes from a row of the character palette, the tricky part being that the order of the 4 bits coming out from the lookup PROM is reversed. This is something that could have been noticed before, but it always eluded me.

Panic Road

2005-04-10T03:25:00.000+02:00

I didn't have much time for MAME in the past few weeks, but tonight I could finally do something again.

This time I decrypted the graphics for Panic Road. The encryption is just a simple data and address lines swap, so it wasn't particularly hard to do - but it took some time nevertheless.

I don't have time to finish the driver, this will be a job for someone else.

How to dump a NMK004

2005-03-22T19:07:00.000+01:00

This is still at the theorical level, until one of the hardware gurus gets his hands dirty and tries to put it in practice.

The NMK004 cannot be dumped directly using the common methods, but the way it operates can probably be used to extract the internal ROM data in another way.

The external ROM contains data tables used to play the samples and music; but not only that, it contains pointers to those tables.
By changing those pointers, we can make the NMK004 use its internal ROM as if it was one of the external tables. In particular, this can be done with the table that contains the sample numbers to be played by the two OKI6295.

We can then log the commands sent by the NMK004 to the OKI6295, and this will allow us to determine which sample it is attempting to play - and therefore the value of the internal ROM byte it has just read.

So in theory there shouldn't be problems - unfortunately the hardware setup needed to get it all to work isn't trivial. But I'm confident that in due time it will be done.

NMK004 update

2005-03-17T14:39:00.000+01:00

As most of you have already seen, a few days ago Haze released an update with the first version of my NMK004 simulation code.

All NMK004 games have sound, though in some of them it's better than in others. Mustang is possibly the worst one - I have doubts about the sound ROM being a bad dump.

There were a few major problems - music stopping shortly after starting, or games completely freezing MAME. I have found a bug in the loops handling which should have caused most of these problems. Here is the fix. It doesn't improve Mustang, though.

Digital Fortress

2005-03-13T13:00:00.000+01:00

Which is the book I'm reading now.

I really don't have much time to read, as you can imagine working on MAME eats up most of my spare time. However I try to read something even if it means just a couple of pages per day.

I had read the bestseller The Da Vinci Code previously, and didn't feel any urge to read another book from the same author, especially after I noticed that all bookstores are now prominently displaying his previous works, which had went entirely unnoticed until the success of The Da Vinci Code.

Digital Fortress in particular was written in 1998. The publisher must have been unable to find any positive review to reprint on the back cover, because they resorted to quoting "Praise for The Da Vinci Code". However I was intrigued bu the theme of the book, which is cryptography - and I was able to borrow it from a friend, so I gave it a try :)

The problem with fiction is that you must be able to suspend disbelief to immerse in the story. This isn't easy if what is being thrown at you makes no sense at all. This was also a problem with The Da Vinci Code, of course, but not knowing much about art history it was easier to fool me. Mathematics is supposed to be my field, so fooling me gets a little bit harder.

Right at the beginning of the book, on page 29, the author introduces Julius Caesar as "the first code-writer in history", and talks about a "'perfect square' cipher box" he supposedly use. This is a transposition cipher, which consists of arranging the cleartext in a square and reading it by columns to get the ciphertext.

Well, I had never heard of this "Caesar's box" cipher. The encryption commonly associated with Caesar is the one called "Caesar's cipher", and it is a substitution cipher: replace every letter with the one k places after it in the alphabet, so e.g. A becomes D, B becomes E, and so on.
A transposition cipher similar to the one mentioned by Dan Brown was used in Sparta, a few centuries before Caesar's birth.

OK, never mind. After all, I might just be ignorant not knowing about the Caesar's Box. Unfortunately, on page 34 Dan Brown talks about public-key encryption, and what he says makes little sense.

The comment that modern codes are "computer-generated has functions that employed chaos theory and multiple symbolic alphabets" was also funny - it reminded me of this :)

Almost good enough

2005-03-07T01:43:00.000+01:00

I am at a point that I almost consider good enough. The FM part is supported as well. The state machine seems to produce the correct notes, the only strange thing is that the volume is extremely low - I had to push it to 2.0 gain and lower all the others to make it reasonable. There might be a bug somewhere in the way the FM parameters are set - this stuff is much more complex than the PSG.

At this point, I'm more worried about the protection in some games than by the sound, which is coming along nicely.

It has to be said that this simulation I've written was mostly for personal education and for reference. I am 99% certain the the NMK004 internal ROM can be extracted, using a technique I thought of. Theoretically it's very simple, but the process will require some hardware work.

And of course, once the ROM is extracted, we'll have to see if it can be ran in MAME. It supposedly is a TLCS-90, which is one of the few CPUs not yet supported by MAME, so an emulator for that CPU would have to be written. Which would be a good thing because it would also allow to support Mahjong If and sound in Rapid Hero.
Having the simulation code available might help while writing the CPU emulator.

Polyphony

2005-03-06T18:16:00.000+01:00

The problems with the PSG notes were just caused by a silly omission of a *2 in a table lookup. Things that happen when hacking around at 4AM ;)

The PSG part sounds quite good now. Only the FM part is missing...

Cacophony

2005-03-06T17:16:00.000+01:00

Things are going rather well with the NMK004 simulation.

The NMK004 state machine supports:

Six FM channels; each pair of them shares one of the three YM2203 voices.
Three PSG channels, each one using one of the PSG voices of the YM2203.
Eight Effects channels, which can use the total eight voices provided by the two Oki M6295 to play sample-based sounds like drums (but they are also sometimes used to play effects not music related).
Direct triggering of Oki M6295 samples (this is not strictly part of the state machine)

Current simulation status is as follows:

Not done yet.
Partially done. The state machine works and seems to play notes at the correct speed. However, the pitch of the notes is way off.
Seems to be ok.
Is mostly ok but there are some strange things here and there - difficult to say if it's a simulation error or just how it's supposed to be.

I am growing more and more convinced that the internal ROM of the NMK004 is the same in all games. A few of the games in the driver have additional protection issues, but at this point I don't think they are related to the NMK004.

Sounds Promising

2005-03-04T02:48:00.000+01:00

It looks like the Z80 sound program for Task Force Harrier, which is the only known game predating the introductionof the NMK004, uses a data format which is very similar to the one used by the NMK004.

The main command table and the sample tables are slightly different, and the music tables look very similar if not identical.

It would probably be possible to modify the Z80 program to use the different tables, but I think I'll take the longer route and rewrite the program in C - so I'll learn how a program like that works in detail, which can always be useful knowledge :)

NMK Sound

2005-03-03T09:56:00.000+01:00

One of the longest standing hurdles in MAME emulation is the sound in NMK/UPL games like Mustang, Vandyke, GunNail, etc.

Those games use an custom CPU, labelled "NMK004", to drive the sound. It is still not known what kind of CPU it is, what's known is that it has 8 or 16kB of internal ROM which cannot be directly dumped, and which contains the whole program. The external ROM only contains data.

I am convinced that that the program contained inside the NMK004 is either always the same, or it has minor difference to handle protection - but the format of the data in the external ROM is always the same.

What I'm trying to do at the moment is understand the format of the external data. I have started with the easy part, that is the Oki 6295 samples control. I have found the command table, and the mappingd from command to 6295 sample number. This allowed me to make the games play the correct samples at the correct time so e.g. in Vandyke I hear a "swoosh" when I swing the sword and a "uumph" when I jump. I still haven't understood all of the control bits, so it isn't perfect yet, but it's a good start for a night's work.

I'm hoping that other games that use a standard Z80 instead of the NMK004 will use similar logic to drive the sound (though I have already verified that they don't use the same data format as the NMK004).

Of course the YM2203 part will be much harder since it won't be just a matter of playinga few samples here and there, but I will have to fully understand how the data translates into music and drive the YM2203 accordingly. However there's nothing stopping it in principle, so I am confident that eventually I or someone else will be able to add full sound to these games.

Child's Play

2005-02-26T00:11:00.000+01:00

Well not exactly, but with the knowledge gained working on the other games decrypting Raiden Fighters Jet wasn't too hard.

Done

2005-02-24T22:00:00.000+01:00

Finished decrypting the sprites in Senkyu, E-Jan High Scool, Raiden Fighters and Viper Phase 1.

Raiden Fighters Jet is the only one left. It uses a different encryption, which might be similar to the one used by Raiden Fighters 2 2000.

Almost Done

2005-02-24T00:48:00.000+01:00

Things are beginning to look pretty good.
I still have many things to fix, especially for sprites with (tileno&0x4000) , but most of the work is done now.

Getting There

2005-02-23T01:03:00.000+01:00

I made a breakthrough yesterday night and could fill most of the gaps.

There is still a lot to do. Part of it is simple and just requires trying various combinations until the correct one is found; I should be able to do it the next night I dedicate to the encryption. The rest is less simple and requires finding the remaining (and therefore less obvious) correlations between bits. However, the closer I get to the goal, the easier it is to see if a certain formula is correct or not.

Sprites are finally good enough to show a screen shot.

13 1/2 done, 34 1/2 to go

2005-02-20T03:16:00.000+01:00

That's a strange way to report progress but it's the number of bits in SPI sprites that should be correctly decrypted at the moment. The encryption works on 48 bits at a time, and I have to decrypt each one of them.

Luckily, having decrypted Raiden Fighters 2 makes things easier because the first few sprites in Raiden Fighters are identical, so I can compare them and see where pixels should go. However, the process isn't easy because the SPI sprite encryption is quite more complex than the tile encryption. Of the 34 1/2 bits still left to do, 16 will be particularly hard because the encryption scrambles them more aggressively. The others shouldn't be too hard to do, given enough time and patience. I have plenty of the latter, but never enough of the former.

First results

2005-02-13T21:39:00.000+01:00

Decrypting the sprites was easier than expected. I've done Raiden Fighters 2 for now, which is the first game to have completely decrypted graphics. I still have to do Raiden Figthters Jet and the SPI - I don't yet know if the encryption will be similar.

The game looks good now, though there are still some graphics issues - most notably priority and alpha blending. I will probably not look at those when I've finished with the decryption, leaving to someone else to finish the driver.

And now comes the hard part

2005-02-12T21:24:00.000+01:00

Fixing the tile banking was easy, so now I can't postpone any longer the attack to the sprite encryption.
That should be significantly harder to fix than the tile encryption, I haven't even looked at the current algorithm yet so I haven't devised a strategy.

All RISE!

2005-02-12T15:36:00.000+01:00

On one side, decrypting the tiles of the RISE11 chip used by Raiden Fighters Jet was easier than I thought: after placing a few bits of the source data, it became apparent that the bit order was the same as the RISE10 chip used by Raiden Fighters 2.

On the other side, however, it wasn't that easy because a couple of pixel didn't want to decrypt correctly. Eventually, it turned out to be a carry that wraps around from bit 23 to bit 0. Nasty!

So I have finished decrypting the tile graphics in all Seibu games. What I will have to do next is fix how the tiles are rendered on the screen in the RISE games, because currently the tilemap layers show garbage most of the time. The above shot is pretty much the only place without graphics errors (caused either by tile banking, or sprite encryption).

Autopilot

2005-02-11T09:56:00.000+01:00

It's true that sometimes when you are blocked on a problem you just have to leave it aside for a while to look at it from a new perspective.

Yesterday I spent much of the night fixing the tile decryption for the RISE10 chip, which is used by Raiden Fighters 2. With the experience gained on the earlier version of the chip this was much easier, and I could fix most of the problems reasonably quickly. However, there was one bit in one layer that just didn't want to work.

The algorithm, now that it's understood, is really clean and simple, following intuitive patterns, but that bit didn't fit - to partially decrypt it, I had to use the wrong bits from the tile code, and pick a carry from the wrong bit of the encrypted data. It just didn't make sense.

I decided to leave it alone for the night, but literally a few seconds after turning off the monitor and going to bed, the obvious answer came to me: that bit had to belong to a different plane! I must have been fetching the encrypted data from the wrong place. And indeed, this morning I checked, and bit 16 of the source data was used twice, while bit 15 was not used at all. Fixing that was all that was needed to completely fix the tile graphics.

There aren't many screenshots that I can take because the driver also has problems selecting the tile bank (this is an emulation problem not related to the encryption). Plus of course, sprites are still not decrypted correctly.

I still have to decide what to do next - I could either look at the RISE11 encryption, used by Raiden Fighters Jet, which will be a bit more work than the others because the current driver only decrypts two of the six planes (for the other games, the decryption was already very close). However, now that I have a good understanding of the algorithm it shouldn't take long to do it, even starting from scratch.

The other thing I could do is fix the tile banking problems in Raiden Fighters 2. I haven't looked at the driver yet, it might be something simple.

SPI progress

2005-02-09T19:25:00.000+01:00

I started from the part that was in the best shape, the first version of the tilemap layers, and fixed the decryption errors.

This encryption is used by Senkyu, E-Jan High School, Viper Phase 1 and Raiden Fighters. I will look at the other versions of the tile encryption next. Sprites are harder to do and will be done last.

Seibu SPI encryption

2005-02-08T02:41:00.000+01:00

I'm looking at the Seibu SPI graphics encryption at the moment. For now, I'm fixing the small mistakes in the tilemap layers of Senkyu etc., after that I might look at the sprites as well.

Most of the work has already been done on the tilemap layer, but there are some mistakes. I have understood while they are happening and already fixed one of them. It's clear how the algorithm works, it's a bitswap + arithmetic calculations (additions instead of simple XORs - this is not common). Replacing the lookup table with formulas and fixing the remaining bugs is just a matter of time and patience at this point.

F3 sound

2005-02-06T13:27:00.000+01:00

The issues with F3 sound were intriguing.
These games all use essentially the same sound program, with minor variations, which appears to be a generic MIDI player.

The hardware is capable of driving a large amount of ROM data - more than the ES5505 is capable of, so the ROMs are banked, in 4 or 8 banks depending on the player version. The ROMs are actually half the amount of banks, because every ROM contains two banks (apart a couple of exception games that use smaller ROMs).

At the beginning of each bank, the ROMs contain a standard header that the program reads on startup to see what samples are available. Therefore, the order how the ROMs are loaded isn't strict - if you swap two of them, the program will still know which one is which and play the correct samples anyway.

However, there's a catch. Most of the games have one ROM containing standard samples (the same in all the games that have them) and those samples are stored differently from the others (there is no header), so the program cannot recognize them. The program just expects those standard samples to always be stored in the last bank.

Discovering this was important to fix sound in a few games - for examples Space Invaders DX, which was missing music.

However, it still wasn't enough to fix all the problems. For some reason, ROMs loaded in bank #4 were not recognized properly, so they were ignored by the program. After some studying of the ROM detection function, I finally found the not-so-obvious cause.

Usually, 68000 programs have ROM starting from address 000000, because that's where the reset vector is located. This program, however, for some reason works differently, and ROM is located higher in memory while RAM is at 000000.
The 68000 also has a special instruction to move data in its address registers, called MOVEA. It is different from MOVE because a MOVE.W will just affect the bottom 16 bits of the destination register, while MOVEA.W will sign extend the result to 32 bits. Therefore,
MOVEA.W #$7FFF,A0
will put #$00007FFF in A0, while
MoveA.W #$8000,A0
will put #$FFFF8000 in A0.

What was happening with the program was that the data read from the ROMs went to a buffer starting at around #$006000, and continuing onwards until it crossed the magic #$008000 boundary. When it did, the program would begin writing data at #$FF8000, but read it back from #$008000. This is what is called a "mirror address" - different addresses that map to the same chip on the board. The FF8000-FFFFFF area was mapped in the driver, but not as a mirror of 000000-00FFFF. Once that was fixed, the program started properly recognizing all of its ROMs.

I have checked all the games, looking at the ROMs to make sure they were in the order expected by the game, and playing them to look for obvious problems, and I couldn't find any, so now all of the F3 games should be sounding pretty good.

In the process, I also discovered that Quiz Theater was missing sound because of a bad ROM. I was able to partially repair it because most of the damage was in a portion which is common to other games, however there are still some parts missing so some sounds willnot play as they should. Ring Rage and Riding Fight still have no sound, however in this case I believe it's an emulation issue. Both of these games use a very old version of the sound program, possibly the earliest revision, so it might behave a little differently from the later ones.

Universal, part 2

2005-02-03T22:21:00.000+01:00

But the strangest thing about Mr Do's Castle board is the third Z80. This CPU has a tiny program ROM - 256 bytes, and most of them empty. It sits there, doing almost nothing. It communicates with the main CPU using the same method described in the previous article, but it doesn't send anything back.
The interesting thing is what the main CPU sends it. It's not just 9 bytes as with the second CPU. It is 0x200 bytes, and it's the sprite data. So essentially what the third CPU does is sit there, wait for the sprite data from the main CPU, and pass it over to the video hardware.
Why couldn't the main CPU just send the data to the video hardware by itself? That's the difficult question. I haven't an answer yet.

Universal

2005-02-03T09:44:00.000+01:00

Universal, best known for their Mr. Do! series, surely made original games. Their hardware isn't less original; it's actually one of the more unique and strangest ones in MAME. A lot of things in their boards were done differently from everyone else, and in non-obvious ways.
Even the style of the schematics drawings is unique and instantly recognizable - albeit not the easist to follow.

There is a long standing problem with the games Mr. Do's Castle and Do! Run Run, where the dip switch settings are not read by the game. The problem has been reported to happen even on real boards, so it is probably a timing issue (small deviations from the nominal rates of the components could throw the timing off enough to break it). For now, we'll fix it in MAME by just changing the CPU clock rate by a small amount. Kind of black magic, but it works.

Anyway, while studying the schematics I finally understood one thing that had eluded me until now: how the CPU communication happens on the real board. The two CPUs exchange bursts of 9 bytes, but there is only a single bidirectional buffer between them. How could it possibly work? Well, the Universal designers took advantage of the Z80 WAIT input. When the main CPU reads or writes the buffer, the WAIT line is asserted, so the CPU is put on hold. When the sub CPU reads of writes the buffer, the WAIT line of the main CPU is cleared, thus making it resume execution. So when the main CPU writes to the buffer, it will put the data there and pause until the sub CPU has read it. When it reads the buffer, it will pause until the sub CPU has written data to it, and resume execution (reading that new data).

Very cheap and effective. However, I wouldn't want to fly on a plane that uses this technique. :)

I wish they were all like this...

2005-02-01T01:47:00.000+01:00

I was asked to look at the encryption of a game called Super Trio, and it tunerd out to be some very basic XOR on the bottom address lines, surely done by a PAL near the 68000.
One wonders why did they even bother to encrypt it, if it was so trivial to break (moreover, surely a PAL based encryption would have posed no problem for any bootlegger).

Anyway, I don't have time to write new drivers these days, so my job is done. Hopefully the hardware won't be difficult to figure out, so we'll soon be able to revive another nice and rare game (as I'm told).

Chain reaction

2005-01-31T01:03:00.000+01:00

It seems that whenever I look at a driver, I find something to fix in it
In this case, while looking at TNZS, I noticed that some games, e.g. Insector X and Plump Pop, were quite obviously running at 30 fps instead of the normal 60. This makes a lot of difference in the smoothness, strange that nobody ever noticed. Anyway, this was caused by missing support for sprite banking, a feature of the hardware which was already supported by seta.c (the games running in this driver use Seta custom chips). It's now fixed so Insector X looks better than ever :) The improved emulation also fixed the various gfx issues with Kabuki Z.

Some bugs never die

2005-01-30T15:48:00.000+01:00

Fascinating how some bugs have stayed with us for years, even if the solution was simple and obvious.

There had been two bugs plaguing emulation of The New Zealand Story:

A hanging bug, which would make the game simply stop, while music was still playing. This happened randomly at some key points, typically the end of a level when you touched the cage. This was caused by a bug in the original program (a RET NZ instead of RET Z), which would cause no apparent problem on the real hardware, but could be deadly in MAME.
This bug had been fixed for a long time, 0.91 contains a cleaner workaround but the behaviour is the same.
A crashing bug, happening at different times in the three different versions of the game. For example, in the current main set, it would happen when the cannon-firing sheep was on the screen. This was caused by a known limitation in the MAME handling of banked ROM areas. It is not a big problem, and we know how to deal with it, and there was code in the driver to do that. Unfortunately, the code was copying the wrong data! It has been like this forever, and nobody ever noticed. But at last it has been discovered, so I can promise you, from 0.91u2 TNZS will no longer crash :)

Kram is working!

2005-01-29T16:59:00.000+01:00

I have finished the manual decryption. By that I mean that I made tables that list all addresses of encrypted instructions, and what to replace them with. The total number of entries in the tables is 7926. This is not an optimal solution but since I doubt I will manage to understand the algorithm it's the only thing I can do.

An interested thing I found out when hooking up the tables in the driver is that for two-byte opcodes, only the first byte is encrypted, the second is unencrypted. This wasn't the case with the Konami-1 CPU, where both bytes are encrypted. Odd.

Reaching a brick wall

2005-01-29T03:18:00.000+01:00

No progress on the Kram encryption algorithm. Changing even a single bit of the address changes the result in an unpredictable way. At this point I'm doubting that I'll be able to derive the algorithm.

Manual decryption of the game, instead, is proceeding. I'm at about 80%, I think. The service menus are working, while the game is still booting to a black screen.

Kram hurdles

2005-01-28T02:53:00.000+01:00

Looking for "good" keys didn't work, there are no bit permutations that show noticeably better applicability than others, the only thing I found is that a 0x22 final xor is significantly more common, which is good on one side, but not that good on the other side because it cannot be the ONLY xor - there must be others.

The manual decryption by comparison with the other sets is almost complete, CPU #2 is 100% while CPU #1 is maybe 75%. The code is different in a few places because this version doesn't have the MCU, and actually there seems to be a large chunk of code in the encrypted version that isn't in the others, so I might not be able to do a complete decryption if I don't break the encryption algorithm.

One interesting thing to note is that the code has been reassembled with a different assembler, which generates different (but equivalent) instructions in some cases. Here is an example:

not encrypted version:

D08D: CE B8 D3      LDU   #$B8D3
D090: EC 84         LDD   ,X
D092: 81 29         CMPA  #$29

encrypted version:

D082: CE B8 D3      LDU   #$B8D3
D085: EC 00         LDD $0000,X
D087: 81 29         CMPA #$29

the middle instruction does the same thing but with a different opcode.

Yesterday I verified that bytes at the same address are decrypted in the same way, and that in that case changing one bit in the encrypted value changes one bit in the decrypted value. Tomorrow I will try pairs of addresses only differing by one bit, and see if there is a similar regularity. From what I could see, however, I'm not very optimistic.

Kram progress

2005-01-26T10:31:00.000+01:00

My intuition was right: the two Kram CPUs use the same encryption. Every time there is the same encrypted value at the same address in the two CPUs, it decrypts to the same value.

Not only that but, at a given address, if N bits change in the encrypted value, then N bits change in the decrypted value. This proves that the encryption consists of a bitswap and a xor.

That was the good news. The bad news is that the encryption changes with the address, and there isn't much data to analyze. For most addresses I have only one encrypted-decrypted pair, for a few I have two. There is no way to obtain more than what I have without physical access to the CPU.

Of course, since for now we have to assume that the encryption consists of a free bitswap + free xor, this means that given a single pair it could be decrypted correctly with any of 8! = 8*7*6*5*4*3*2*1 = 40320 different keys: just pick any of the 8! possible permutations of the bits, and then select the 8-bit xor that fixes the result.

What I need to do now is try to figure out the relation between address and key, which isn't obvious at the moment. The total possible keys are 8! * 2^8 = 10321920, which isn't too much. What I plan to do is check how many values are decrypted correctly by each one of them (or better, by a subset of them). If we are lucky, some keys will show a significantly better success rate, meaning they are "good" ones. If we are not lucky, it will mean that bitswap and xor are independently affected by the address.

Kram encryption

2005-01-26T10:00:00.000+01:00

And of course, another still unsolved issue with the Qix driver is the encrypted version of Kram.

This is unusual because it's possibly the only time that Taito used encryption instead of MCU protection (off the top of my head, I can't think of any other encrypted Taito game). It is also a rare example of an encrypted 6809 game - again, the only other 6809 encrypted games that come to mind are the ones using the Konami-1 CPU.

I had looked at this encryption other times in the past, with no success. There probably isn't enough data to figure it out, but comparison with the other version of Kram will at least be enough to decrypt it, even if it will mean using a large hardcoded table - and who knows, in the process I might discover something new.

The encryption only works on opcodes, leaving data decrypted, which is good because you can easily align code from the encrypted and unencrypted versions of the game. Unlike the 68000, where everything that is fetched in the process of executing an instruction (plus PC-relative indirect memory accesess) is considered program space, and only memory accesses caused by an instuuction are considered data space, in the 6809 only the first byte of an instruction (the opcode itself) is encrypted, while the other bytes of a multibyte instruction are left unencrypted. This means that when comparing encrypted and decrypted blocks of code you have plenty of reference to align them perfectly.

The encrypted version of Kram should actually be almost identical to the other two, minus the MCU handling which isn't present in that version since it was protected in another way (Sega, anyone?). I should be able to do most of the decryption automatically and fill a couple of holes manually in the places that are different. Since both 6809 are encrypted, my hope is that they use the same encryption, so I might discover something more about it by comparing encrypted bytes at the same address on the two CPUs.

Fix one thing, discover another

2005-01-26T01:43:00.000+01:00

Electric Yo-Yo was easy to fix, it was crashing because of a synchronization issue between the two CPUs - increasing interleaving fixed the problem.

Looking at the schematics surely was interesting, for example I discovered that the video ROM bank latch (which is a late addition only present in Zookeeper) is mapped on a mirror address of the diagnostic LED / palette bank latch. This explains why they oddly mapped the ROM banking bit on data bit 2, instead of the more obvious bit 0. That's because bits 0 and 1 are the ones that control the palette bank, and since the ROM bank latch is at a mirror address of the palette bank latch, whenver the former is written to, the latter is affected as well. So whenever the game wants to set the ROM bank, it also copies the palette bank in bits 0 and 1 to avoid unwanted side effects.

Memories...

2005-01-25T09:25:00.000+01:00

I'm looking at the good old Qix driver at the moment. This was one of the first drivers in MAME, and at the time it seemed really complex, with its three CPUs and the need to synchronize them with a certain degree of accuracy.

The driver is already very well written and documented, but I'm checking the schematics again to verify that everything is correct, then I'll try to fix the Electric Yo-Yo hang during attract mode.