Well, it looks like I hadn't been here for some time.
I'd like to thank all the people that are still coming over to this blog, even if it hadn't been updated for several years.
I couldn't even find the password to access the admin pages, but I recovered it eventually, so I could finally remove a lot of spam that had piled up among the comments to the previous post. While I was there, I also updated the blog template.
I'm afraid I don't have much to say about MAME now, because I haven't been involved in its development for quite some time. Sorry! MAME was an endless source of stimulating challenges, but required too much time and dedication for a hobby.
As some of you might have guessed from my contributions to decryption of arcade games, I've always had a strong interest for mathematical and logic puzzles. Mobile devices are the ideal platform for this kind of games, so that's where my main focus is at the moment.
In 2012 I released my first game for iPhone/iPod: Twin Beams. I'm now working on a new game.
I've also started a new blog: Nontrivial Games. It is dedicated to reviews of logic puzzles for iPhone and iPad. So if you share my interest for puzzles, hopefully you'll like to follow my ramblings over there.
Kind Regards,
Nicola
Monday, February 18, 2013
Saturday, February 17, 2007
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 216, 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 248, therefore leaving about 216 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.
Each (E,D) pair reduces the key space by a factor of about 216, 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 248, therefore leaving about 216 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.
Sunday, January 21, 2007
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
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.
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.
Subscribe to:
Posts (Atom)