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

_{1}such that

D(X,A,K) = D'(X',A

_{1},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

_{1}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.

## No comments:

Post a Comment