Let's recap the basics of the CPS2 encryption first.
- 16-bit value stored in ROM
- 16-bit address (bits 1-17 of the physical address)
- key of unknown size, different for every game
- 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 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
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.