CAESAR Logo

Catalogue of Arcade Emulation Software - the Absolute Reference

Valid XHTML 1.0! Valid CSS!

X-Arcade

X-Arcade

Large CAESAR Logo

cps2.c

0.36b3 [Paul Leaman]


TODO:

- Rasters are not correctly emulated in places where more than one split happens per frame. A known place where this problem happens is during Shuma-Gorath's Chaos Dimension super move in both MSH and MSHVSF. The screen should split into around 6 or more strips and then scroll the gfx inside those strips up and down alternatly (as one stip moves gfx up the next strip moves the gfx down).

- The network adapter used in Super Street Fighter II: The Tournament Battle is not currently emulated though the ports it uses are setup in the memory map.

- Giga Wing's attract mode seems to loose sync with music. The problem seems to happen due to gfx drawing slowing to much when screen colors fade out. This problem could be due to the 68k being clocked at 11.8mhz when the hardware has a 16mhz crystal on it. Various timing loops show 11.8 being the average speed of the cpu and this does run true when comparing emulation and real hardware when timing is not based on VSync (ssf2 and ssf2t for example). It is possible that what is slowing the cpu is read/write wait states when accessing RAM areas. This would mean that in places where lots of opcodes are being used in connetion with data registers only the code would end up running to slow.

- Giga Wing's sprites are 1 frame out when compared to background scrolling. See the explanation above for the most likley cause of this problem.

- Progear slows down more than it should when compared to real hardware. See the explanation above for the most likely cause of this problem.

- Any new region sets will need full encryption tables dumped to extract the proper keys or they will need to be brute forced. XORs are no longer supported nor wanted.


NOTES:

- Driver: Thanks to Raz, Crashtest and the CPS2 decryption team for their initial work on extracting decrypted code. Thanks to Andreas Naive and Nicola Salmoria for understanding the encryption mechanism.


WIP:

- 0.113u2: Changed VSync to 59.633333 Hz.

- 0.112u2: Many more CPS2 keys added. Removed all XORs and support for them from MAME [Nicola Salmoria, Andreas Naive].

- 17th February 2007: Nicola Salmoria - CPS2 not much left to do: 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^16, 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^48, therefore leaving about 2^16 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.

- 0.111u5: Nicola Salmoria removed XORs from almost all CPS2 games in place of proper emulation of the encryption.

- 23rd January 2007: Guru - Here's a few pics of the very first custom chip that I sent to a professional Japanese IC decapping company that we (Mamedev) are using to help us with some MAME-related things. Hopefully if this is successful, more will follow and also hopefully talented hardware devs like JROK will be able to make replacements for it to repair real PCBs. You may also be wondering why we're doing this instead of using some other people who frequent the 'boards' who have offered to do this kind of thing for free? The answer is fairly simple.... apart from the amount of time it takes to get this done, the level of communication is somewhat 'sporadic' and so far offers to supply other chips to them have been ignored. We requested pics of some CPS2 ICs that were said to have been decapped and so far nothing has surfaced (over a month has passed since then). Doing it this way gives us more control over what we achieve and ensures the work is done in a timely manner. Apart from that, the plan to get this IC decapped has been in the works for several months, so we might as well use the professional IC decapping company whenever possible because the amount of ICs we need to decap is possibly too much work for someone to do in their spare time for free.

- 21st January 2007: Nicola Salmoria - CPS2 Key Bit Order: 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 and 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 and CDEFBA9823016754. Looks much better doesn't it? Though there's no way to tell how close it is to the real thing.

- 19th January 2007: Nicola Salmoria - CPS2 Moving Slowly Now: 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^16-2^17, 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.

- 17th January 2007: Nicola Salmoria - CPS2 The Fight Continues: I've finished going through all the games previously supported by MAME using XOR files, and generating keys using this attack (http://mamelife.blogspot.com/2007/01/how-to-bruteforce-cps2.html). 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 A1 such that D(X, A) = D(X ^ 0xffff, A1) ^ 0xffff. The problem is that we don't know A1. 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.

- 14th January 2007: Nicola Salmoria - CPS2 Getting Closer: 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 and 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.

- 12th January 2007: Nicola Salmoria - How to bruteforce CPS2: 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 also that the fn round functions are made of 4 s-boxes each. These are the 16 s-boxes, with their inputs and outputs. 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 224 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 26 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.

- 0.111u3: Andreas Naive and Nicola Salmoria replaced CPS2 CHDs with preliminary decryption function.

- 9th January 2007: Nicola Salmoria - CPS2 coming to MAME: I've submitted to MAMEDEV the code to replace the 4GB CHDs with 192-bit keys. 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.

- 8th January 2007: Razoola - Nicola Salmoria of MAME Dev seems to have worked out the rest of the CPS2 algo (though there is still some s-boxes to complete), to quote his blog... * 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. Our congratulations go out to him, again to Andreas Naive and also Charles MacDonald who all played a role to get to this point today. Looking back at the way things have gone from the first XOR release some six years ago (after the discovery of the main weakness in the system), we know some people were quite unhappy at our unwillingness to have this algo known for emulation (Statement of 7th Janurary 2001). It was always our intention to hold back information to help achieve this until the system was commercially dead (our view was 3 years after the last game released). It is very satisfying to know we achieved this as believe it or not Janurary 2007 is just past that three year mark (Hyper Street Fighter II was released in December 22nd 2003). I will update the encryption page with the details once Nicola has fully documented the Algo within MAME.

- 8th January 2007: Nicola Salmoria - CPS2 Fundamental Breakthrough: 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.

- 7th January 2007: Nicola Salmoria - CPS2 Won't Be Tamed That Easily: 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. 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.

- 6th January 2007: Nicola Salmoria - CPS2 Subkeys: 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.

- 19th December 2006: Nicola Salmoria - CPS2 notes, part 5: 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 (see table). 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.

- 19th December 2006: Nicola Salmoria - CPS2 notes, part 4: 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.

- 18th December 2006: Nicola Salmoria - CPS2 notes, part 3: 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 (see table). 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.

- 18th December 2006: Nicola Salmoria - CPS2 notes, part 2: 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 A1 such that D(X,A,K) = D'(X',A1,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 A1 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 (http://en.wikipedia.org/wiki/Data_Encryption_Standard#Minor_cryptanalytic_properties) 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 Li = Ri-1 and Ri = Li-1 XOR f(Ri-1 XOR Ki-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.

- 17th December 2006: Nicola Salmoria - CPS2 notes, part 1: Since the finding of the complementation property (sfzj_049e38[x] ^ 0xffff == sfzj_05ee0c[x ^ 0xffff] => 8GB / 2 is still 4GB) 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 (see http://mamelife.blogspot.com/): on rows, you have the encrypted bit that changes; on columns, the frequency with which the decrypted bit changes. 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.

- 0.110u4: CPS2 updates [David Haywood]: Added table for Jyangokushi (from Guru). Note that GFX/Sound roms aren't dumped on this one. Removed old 'handcrafted' XORs for games which we have CHDs for and replaced them with XORs generated from MAME using the CHD. This means anyone with the CHD can easily generate the XORs (using the code I've left in there) if they need to be able to run the games with a shorter startup time. Disabled the loading of the XORs by default for all sets with a CHD. Now only the CHD is loaded, unless the #define is changed at the top in which case only the XORs generated from the CHD are loaded.

- 0.110u3: David Haywood added raw decryption table to choko. Enabled the use of the large CHD-based tables by default.

- 0.110u2: David Haywood added support for using CHDs to decrypt CPS2 games. This code is disabled for the moment, but will be enabled in the future. Only a handful of games have complete tables so far. These tables are huge (~4GB) and uncompressable until the encryption algorithm is understood.

- 19th September 2006: Charles MacDonald - With the success of the Choko dump from a while ago, I'm working to get the CPS-2 dumping tools and instructions updated. Changes were made from the last version, mostly bugfixes and speed-ups to decrease the amount of time it takes to dump a full table set. There's also a minor modification that needs to be done to the PCB, to ensure stability, though now that it's known which features are absolutely needed, I might redesign it. Admittedly not many people have been interested in getting more of the games dumped, probably because all the popular ones we wasted tons of quarters on are already emulated!

- 0.105u3: Aaron Giles uncommented/added missing undumped ROMs/XORs in the CPS2 games.

- 0.105u1: David Haywood updated CPS driver to more accurately draw tilemaps, based on evidence from a board with mixed ROMs.

- 14th February 2006: Guru - A CPS2 USB adapter arrived, thanks to Charles MacDonald. The adapter plugs into the 64-pin CN7 on the B board. The chips on the bench are the original ROMs and PALs. ROM3 is changed and ROM10 is added. Plus 1 PAL on the A board is changed and 2 PALs on the B board are changed. Unfortunately, none of the PALs were socketed and this particular B board didn't have a CN7 connector! So I had to desolder a CN7 connector from another dead CPS2 board and solder it to this board and desolder and socket the 3 PALs as well! Luckily she still works! It's not that exciting to look at though.

- 15th January 2006: Razoola - Nicola Salmoria has reported on his blog some progress in understanding the CPS2 algo. He has managed to shrink the current 8gig table of SFZ down to 4gig. This is the first breakthrough in understanding the encryption used. For more information visit his blog.

- 11th January 2006: Charles MacDonald - I've tried to package and clean up all the CPS-2 related development stuff I have that was used for table dumping. This can be used for writing CPS-2 software, running tests on the system, and dumping table data so we can hopefully figure out the encryption at some point. I will definitely include more sample programs, documentation, and hardware information in future updates to the package, but I wanted to get this off my to-do list.

- 5th January 2006: Razoola - While playing around coding on a dead CPS-2 board I have today I found that the encryption algo is still fully in place even after the CPS-2 board has suicided. That said, on examining values the number do not match those of the expected game. This almost certainly confirms that their is only _one_ algo over all CPS-2 games with the only difference being key data (like Kabuki on CPS-1). I passed some test code onto Charles MacDonald so that he can check the values he gets there (on his dead SFA3 board). Those should match what I see here and to be honest it looks just a formality. When you consider the watchdog on a suicide board is 0xFFFF,0xFFFF,0xFFFF (example opcode, CMPI.L #$FFFFFFFF,$FFFF0000) everything starts to make sence. There was a big debate over this going back to when we first broke past the protection. The worry voiced by some DEVs was that all boards would be needed again to get the algo for each game. This new discovery certainly confirms that once the algo is known for one game all the others can be brute forced using the XOR tables. As for figuring out the algo itsself whats needed now is a complete dump of tables (8gig) of the algo executing in this default state. Using this the algo should be easier to understand because any key data used for math should be 0xFFFF. I have quickly dumped a complete table for a couple of addresses and while it still looks a mess there are certinally more patterns compared to a normal game. Update: I've got word back from Charles and after some work (over irc) he has managed to get the same data I was seeing. This basically confirms what I mentioned above. There were some initial problems with his transfer system (which is far superior to mine) giving different results. It turned out that at some point during the process the protected RAM was being reprogrammed!!! The exact way this is happening is not yet known but it opens up some large posibilities if the cause can be found and understood. This situation did not happen when he was dumping games that were non suicide. It currently looks like there is no way to get a full 8gig table because the protected region in a suicide state seems to be only 0x10000 bytes where a complete table covers 0x20000 bytes. Hopefully we can get around this.

- 4th January 2006: Razoola - I have written a small tool that can be programmed onto EPROM and used to test if a CPS2 board has suicided.

- 19th November 2005: Charles MacDonald - Thanks to a generous donation from Razoola and the CPS2Shock team, I've been given B-boards for the following games: sfzj, csclubj and sfz3. I have dumped complete table sets from the first two and am doing tests on the latter. It has no battery, so I can see how the hardware works when the battery-backed SRAM is erased. With a much larger data set (32 GB) spanning four games, hopefully some patterns will be discovered. I'm still interested in dumping a regional variant for one of the currently dumped games to see what kinds of similarities might exist between the two. Most likely I will revise and release the tools and specifications for my CPS-2 development setup in the future. Then other people could dump table sets from their games and contribute to this project. There are so many CPS-2 games out there that I couldn't possibly do it all myself, nor would I want to.

- 12th October 2005: Charles MacDonald - Getting a bunch of PCBs to work with in the next few weeks: three CPS-2 'B' boards (more on those next update), Shanghai for HD63484 tests, and a Quartet 2 board. I'll continue my CPS-2 research once the other games arrive. One of them has no battery so I can skip the annoying encryption and run tests directly, which will be a huge convenience. I think right now all the useful data that can be extracted from xmcota and pzloop2j has been obtained.

- 30th September 2005: Charles MacDonald - I've been doing some research on the CPS-2 hardware in the last few months, starting as soon as the System 32 work was put on hold. I'll give a basic overview of the encryption, however I should point out I'm just elaborating on the findings that Razoola originally made, which are at CPS-2 Shock. As you can imagine the results of his prior experiments have been absolutely essential to this project. The CPS-2 hardware uses a custom 68000 CPU running at 16MHz, though the effective speed is lower due to video DMA. Out of the 16MB address range, the lower 4MB is allocated for ROMs storing program code and data. The first 1MB of this area is where decryption is enabled, though the exact boundary under the 4MB point may change from game to game. In addition to the address range check, there is a timer that expires after a certain amount of time has passed. When this happens, decryption is turned off and the 68K will execute code exactly as it is read from memory. A sequence of one or more specific instructions, changing on a per-game basis, will reset the timer and enable encryption again. The timer can be restarted after any duration from when it has expired. The decryption logic uses bits A16 through A1 of the 68K address bus, meaning the encryption wraps every 128K. For each encrypted word at a given address there is exactly one unique output; in contrast to the FD1094 there are no disabled opcodes or 'blanked' data that resolve to the same decrypted value. Data read from the supervisor or user code space is decrypted (e.g. opcodes and operands) and data from the supervisor or user data space is not. The size of a complete set of decrypted data for one game quite large, totalling 8GB - it takes forever to dump. There are no duplicate tables within a game's table set or between sets for different games, though I've only examined tables dumped from the two 'B' boards I have. I've discussed analysis of the table data with a few other people and so far the encryption seems to be pretty tough to solve. As a result, I think progress will depend on additional help. If you have skill in this type of thing (strong mathematics background and familiarity with encryption) and would like to lend a hand, then please get in contact with me. Working with the CPS-2 hardware has been challenging due to the large amount of custom parts involved. I designed a communications board with a USB adapter, DTACK generator, and interface to the CPS-2 video and peripheral bus to run software on it, as well as several adapters to replace the 16V8 GALs with more capable 22V10 GALs that have their own shared I/O bus. Small update for some common questions: The two games I've dumped are xmcota and pzloop2j, which are both already emulated in MAME. The ETA for a complete table dump (65,536 files) is 9 hours, and it's fully automated. Sometimes the system locks up randomly and has to be reset which slows things down, this occured quite a lot for pzloop2j and not at all for xmcota. They have different types of B boards, perhaps that has something to do with it. Many people are suggesting to look at Street Fighter Zero and it's variants, as well as Rockman which had a less common CPS-2 release but is very similar to the CPS-1 version. The only thing that would be really useful is to find two games that are encrypted with the same or similar keys, so unless Rockman has an identical key as another game it's not that useful. I would be interested in getting data out of another variant of xmcota.

- 0.94u2: Aaron Giles fixed QSound routing in cps1/2.c.

- 27th October 2004: Razoola - There seems to be someone making quick hacks of XOR files we have released in the past to get games running which don't currently have XORs. While this sounds a good thing it's actually no different than using the region switch option in kawaks for example. The big problem is that these new XOR's contain incorrect information in relation to what the real encryption would return for many addresses when compared to real hardware. It also makes it less likely for these games to be donated in the future so good XOR's can be created as people will think they already have good XOR's. The reality is these new hacked XOR's are prone to all the bugs that come with using region switching in CPS2 games. It's for these reasons that I want it known I have nothing to do with these hacks and I would advise against them being used officially in any emulator as they cannot guarantee an accurate game.

- 0.71u2: ShiRiRu fixed CPS2 raster effect.

- 19th January 2003: Shiriru's updates to the CPS-2 driver fixing raster effects.

- 8th December 2002: Barry Rodewald submitted a bug fix for resetting the Z80 in the CPS-2 driver, and smf improved the fix.

- 19th November 2002: Shiriru's updates containing fixed sprite masking in the CPS-2 driver and fixed sprite delay in Battle Bakraid were also forwarded.

- 13th September 2002: Barry Rodewald submitted a fix for the CPS-2 driver to reset the Z80 properly after exiting service mode.

- 6th September 2002: Barry Rodewald submitted an improvement to the CPS-2 driver raster effects' emulation, improving many cases, however it still causes flicker from time to time.

- 11th August 2002: Two of Shiriru's old updates were forwarded, which fix background colors and BG/sprite sync in the Cave driver and sprite masking in the CPS-2 driver.

- 12th May 2002: Barry Rodewald submitted an update to the CPS-2 driver supporting raster effects, but it unfortunately causes the background / sprite sync to be broken.

- 25th August 2001: Aaron Giles fixed a decryption problem which caused CPS-2 not to work.

- 0.54: Aaron Giles made major changes to the CPU interface. As a result of this, some games are temporarily broken, most notably CPS2.

- 0.37b16: Shiriru fixed sprite priorities in CPS2 games. Fixed user1 roms addresses.

- 16th June 2001: Shiriru fixed sprite priority and added sprite transparency in the CPS-2 games.

- 1st June 2001: Nicola Salmoria fixed CPS-2 games from crashing when resetting them.

- 0.37b14: Changed 68000 CPU1 clock speed to 11.8MHz and changed VSync to 59.633331 Hz.

- 0.37b13: Changed 68000 CPU1 clock speed to 12MHz.

- 16th February 2001: Nicola Salmoria fixed the input ports for third and fourth player in the CPS-2 games

- 10th January 2001: Paul Leaman added the necessary modifications to the CPS-1 driver to allow CPS-2 emulation, and he added support for Street Fighter Zero.

- 27th January 2001: Paul Leaman added Vampire: The Night Warriors to the CPS-2 driver, and like Vampire Savior, it will not work before some important 68k core changes are made.

- 26th January 2001: Paul Leaman added Vampire Savior to the CPS-2 driver, but it needs some 68k core changes to get it working properly.

- 0.36b3: Added cps2.c driver.