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.

7 comments:

Knarfian said...

I was thinking the same thing about 0123456789ABCDEF, but I didn't realize so many keys had exactly 31 ones. Do any of the other keys look better with this same permutation? I wondered if any "birthdays" or whatever pop out.

Nicola Salmoria said...

The other keys don't look much better. The problem is that there are countless permutations that would produce similar effects on those 6 keys, so no way to tell which one is correct.

blib said...

I know squat about encryption, so pardon my ignorance. Are you saying EVERY key has 32/32 1/0's? Could that be part of the suicide routines? IE if a key is encountered that isn't 32/32 the board instantly suicides itself? Perhaps the numbers are still random, but simply created with an absolute rule that they must be 32/32?

blib said...

I remember alot of "random" number generators for early cpu's needed a seed. Perhaps when you think you are seeing dates or possible other paterns you're just seeing the seed?

Thanks for documenting all this Nicola. I must admidt that 90% flies over my head, but it still damned interesting reading!

Nicola Salmoria said...

No, not every key has 32 1s. But all the keys for SOME games, like ssf2, have 32 1s. ssf2 was the first game made for this hardware, and it seems to use particularly simple keys. The other games don't.

Parthoris said...

What about those games with revisions with different number of 1s ?

Child Of Fire said...

Nic,

It looks as though you're doing a great job with the keys. I know alot of this is over my head but it's fascinating what you and the team are able to provide to the end-users after the big fight.

Blessed Be Nic. Sending energies your way to you and the rest of the MAMEdevs