How to bruteforce CPS2

I couldn't devise an attack using differential cryptanalysis and the XOR files. The fact that the second 96-bit key changes with the address makes thing more difficult, and I couldn't think of a way to effectively use data from different addresses.

The XOR files give us no more than 8-16 (E,D) pairs at a given address (remember that the encryption only uses the low 16 bits of the address). We have no choice of what data we have, so we have to make the best of it.

So the idea I had is to use a meet in the middle brute force attack which exploits a weakness in the s-boxes.

Remember that

L₁ = R₀
R₁ = L₀ XOR f₁(R₀)

L₂ = R₁
R₂ = L₁ XOR f₂(R₁)

L₃ = R₂
R₃ = L₂ XOR f₃(R₂)

L₄ = R₃
R₄ = L₃ XOR f₄(R₃)

Remember also that the f_n round functions are made of 4 s-boxes each.
These are the 16 s-boxes, with their inputs and outputs:

f1b1  03457- 67
f1b2  12346- 35
f1b3  124567 14
f1b4  023567 02

f2b1  0246-- 46
f2b2  134567 03
f2b3  013457 17
f2b4  123567 25

f3b1  2346-- 35
f3b2  01357- 02
f3b3  012357 16
f3b4  024567 47

f4b1  01367- 03
f4b2  012456 47
f4b3  023457 12
f4b4  234567 56

f2b1 is the weakest link. It has only four inputs, 0246. To get those four inputs, we need just three boxes in round 1: f1b1, which outputs 67, f1b3, which outputs 14, and f1b4, which outputs 02. We don't need f1b2, which outputs 35.

So if we start from the ciphertext and run it through the first two rounds of the Feistel network, scanning all 2²⁴ possible keys for f1b1, f1b3, f1b4, and f2b1, we'll get all possible values for bits 46 of R2.

Now let's start from the plaintext instead, and go up. If we scan all 2⁶ keys for f4b2, we'll get all possible values for bits 47 of R2 again.

Now we impose that bit 4 calculated in these two ways is the same, and given enough (E,D) pairs we have a huge pruning of the valid keys. From experiments, at least 8 pairs are needed for the attack to work effectively, but with 12 it's faster.

When we have a match on bit 4, we start adding more key bits, 6 or 12 at a time. First f4b4, to match bit 6 of R2. Then f1b2 and f2b3, to match bit 7 of R2. At this point, we are most likely already left with a single key, so adding more key bits doesn't increase the computation time. The important thing is to do it 6 bits at a time, in order to avoid unnecessary calculations. Soon enough, we have reconstructed the whole 96-bit key.

This will be the key at a specific address--of course, before running the search we'd have scanned the whole data and selected the address with most different pairs, in order to make the attack more effective.

After the 96-bit key at one address is found, the rest is easy. Since the 96-bit key is modified by the 16-bit result of the first FN in a fixed way, we just use brute force to find the correct 16-bit value at every address, and then we have a full subkey table as when we had the full 8GB tables at the beginning.

The process is working reasonably well, it's taking me 20-40 minutes to find the 192-bit key for a game. It could be made faster, probably. I've done some games for which I had more data, and Razoola was kind enough to provide additional data that will help with many other games. I'm not yet sure that the attack will work on all games, but it surely will on a good percentage.

Some very good news after obtaining more keys is that I found strong correlations between the first and second 96-bit keys, so they are effectively the same key, just permuted. This will also allow to fix the order of the subtables in the s-boxes of the first FN, in the same way I did for the second.

Should we consider ourselves finished after that?

Not yet: whether it will be possible to generate keys for games for which we lack XOR data is an open problem. In that case, the best we can expect to do is to match the startup code from a different version of the game, so we'll have several (E,D) pairs at consecutive addresses, and no more than one pair at a given address. A new attack will have to be devised in order to use that kind of information. Hopefully the discovery that the first and second 96-bit keys are correlated will help.