CPS2 notes, part 2

The complementation property was an important discovery--and not just because it reduces the size of the tables in half. Still, we haven't taken full advantage of it yet.

Let's recap the basics of the CPS2 encryption first.

Inputs:

• 16-bit value stored in ROM


• 16-bit address (bits 1-17 of the physical address)


• key of unknown size, different for every game

Outputs:

• 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 A₁ such that

D(X,A,K) = D'(X',A₁,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 A₁ 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
L_i = R_i-1
R_i = L_i-1 XOR f(R_i-1 XOR K_i-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.