CPS2 notes, part 1

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.