Friday, January 12, 2007

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

L1 = R0
R1 = L0 XOR f1(R0)

L2 = R1
R2 = L1 XOR f2(R1)

L3 = R2
R3 = L2 XOR f3(R2)

L4 = R3
R4 = L3 XOR f4(R3)

Remember also that the fn 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 224 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 26 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.


Andreas Naive said...

I was devising a linear cryptanalysis attack against the first bits of K1. Should i continue with it, or do you think the meet in the middle attack will work for all the games?

Nicola said...

For some games we might not have enough data to perform this attack. If you can devise an attack that needs less data, or that uses data from several addresses, that would surely help (also for games that we don't have a XOR for).

Andreas Naive said...

OK. I suppose i could make some experiments to see how far i can go with this... The attack works without considering whether or not the addresses are the same, but i'm not sure if it will finally need less data (BTW, how many triplets do you consider it should use to become "useful"? How many triplets will we have for the games without XOR files?).

Real life issues will get me away for the weekend, but i will try to resume the work next week. As a last note, the correlations between the 192 bits could have a positive impact, so i would like to see any conclusions you reach regarding that.

p0ng said...

You've been doing an incredible work! Keep up!

see ya