Tuesday, December 19, 2006

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.

      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.

5 comments:

Rodimus Prime said...

Hey Nicola...

I haven't posted anything in a long, long time and I'm about to totally show my ignorance in what's going on with the CPS2 decryption stuff, but I have a question/request..

I see you posting a lot of tables of information, but do you have a pair of games in 'encrypted' and 'decrypted' form so that a comparison could be run? I've been trying to make heads or tails of the whole thing. I've seen the XOR tables, I've seen the CHD's, but I don't really see a X -> Y comparison. Could you post a small zip file with an original single rom with its decrypted counterpart for some analysis?

We may not have the exact methodology, but apparently we know enough to get the games to decrypt and run using the XOR or CHD methods.

So, with that, is it possible to generate a 'decrypted' rom that I or someone else could use to compare back to the original?

Or am I missing something about how the XOR's and/or CHD's are being used?

Rodimus (from those way back days of AMame and PMame)

Nicola said...

The CHDs contain complete X->Y mappings for every X at every address.

robiza said...

hey nicola (and sorry for my english)

in a single 0x10000 table (one address i.e. 00000000 00000000) are there two identical value?
or every value is different and there are all the 0xabcd possibilities?

robiza said...

and only a curiosity:

have you tried complementation with others 0xabcd value?


sfzj_addr1[x] ^ 0xabcd] == sfzj_addr2[x ^ 0xabcd]

Andreas Naive said...

Oh, I have just discovered you were talking about that...
It seems we both have reached the same conclusions... read my last posts here (i suppose you understand spanish):

http://andreasnaive.blogspot.com/

My best bet is a 4-round Feistel Network; i even have some clues about how the initial and final permutations works(read carefully CPS-2(2) and CPS-2(3)) and on how the 16 bits are separated in two 8 bits groups to feed the Feistel Network.

I have devised a test to try to discover the structure of the Feistel function (in the hypothesis that S-Boxes are being used); i should prepare the test in the next days. (i'm waiting for the data that Charles MacDonald is sending me through Lord Nightmare); it will only work if more than one S-Box is used.

My state of mind about this is that the only possibility for RE the algorithm by examining the data will come if we are able to discover how the Feistel function work. Given that, we *could* discover the structure of the algorith and, then, the statistical regularities it show are so big that we should be able to obtain all the keys through a pretty direct cryptanalysis.

Of course, the algorithm could not be a Feistel network, but by now i will maintain it as my work hypothesis. About your doubts regarding the diffusion of the FN, i don't agree with you; as told in CPS-2(2), i found in one of my experiments that a 4-round FN that used sums in Z/65536Z as part of the feistel function (plus a couple of 4-bit S-Boxes) have not-so-disimilar properties.