Monday, January 08, 2007

CPS2 Fundamental Breakthrough

Today I realised why I was having problems with the correlations between subkey bits, where some bits had to be derived from the others not only using XOR, but also AND and OR.

The reason was again in the s-boxes that only have 4 or 5 data inputs instead of the full 6. Those boxes contain 2 or 4 subtables, and the order of the subtables inside the box or the order of the bits inside each subtable isn't particularly important when decrypting a single address, because they can always be compensated by appropriate bits in the subkey.

However, when putting all subkeys together, those things became important. E.g. I could be finding that when using subtable #3 in a box, then two of the inputs had to be inverted. To fix this, I had to rearrange the subtables inside the s-boxes to make everything in sync.

The result was excellent. Previously, some of the correlations among the 96 bits were overly complex, taking up to 4 bits at once. Now every bit is directly correlated to another. The only exception is the bits that correspond to the "empty" inputs of s-boxes that take only 4 or 5 data inputs. What this means is that all 6 inputs of all s-boxes always receive the XOR of three sources: either a data bit, a key seed bit, and a global key bit; or two key seed bits, and a global key bit.


That's only the beginning of the good news, though. After fixing the s-boxes, I could attack again the first part on the algorithm on the assumption it was a 4-round Feistel network, and indeed it was.

So the algorithm turns out to be like this:

  1. Take the 16-bit address and a 96-bit key and run them through the first Feistel network, to produce a 16-bit subkey.

  2. Take the 16-bit ciphertext, 16-bit subkey, and another 96-bit key and run them through the second Feistel network, to produce the 16-bit plaintext


So now, for the first time, I would be able to produce a program that algorithmically decrypts one of the game for which we have full tables, without using any table.

It's not yet time to celebrate, though: the s-boxes for the first Feistel network still have to be properly determined, and this might require having access to some more games.

Once that is done, producing keys for games that we have complete tables for will be quite simple.

Finding keys for games for which we don't have full tables, however, is an entirely different matter. As said above, we are potentially dealing with a 192-bit key here; it's possible that the key is smaller and the bits are reused, however since we don't know how they would be, we have to treat it like a 192-bit one. For a key of that size, obviously brute force is out of the question; and while the XOR tables do provide some information, it's probably not the kind of information that would allow to use the differential cryptanalysis techniques we'd need.

4 comments:

Andreas Naive said...

Nice. The way of constructing the special s-boxes worried me from the beggining. My insight about a bad construction hiding the correlations was true, as it seems...

>and while the XOR tables do provide some information, it's probably not the kind of information that would allow to use the differential cryptanalysis techniques we'd need.

I disagree. My opinion is that the s-boxes show more than enough weaknesses to do the cryptanalysis easy. I'm supposing that we have around 5E5 triples (E,D,k). When you have determined the s-boxes for the first FN, contact me back if you want me to take a try at it.

And my most sincere congratulations. ;)

Parthoris said...

¿ isn't there any relationship between the 96-bit key used in the first FN with the 96-bit key used in the second FN ?

¿ and what about the relationship between the bits of the one of the 96-bit key ? ¿ isn't it useful anymore ?

Firewave said...

FYI

http://www.mame.net/cgi-bin/wwwthreads/showpost.pl?Board=mamegeneral&Number=201381&page=0&view=expanded&mode=threaded&sb=7#Post201381

"I can also provide the full xors (without the parts not needed blanked out) if it will help, lets see what happens first."

Would those be helpful for games without full tables?

Nicola Salmoria said...

> isn't there any relationship between the 96-bit key used in the first FN with the 96-bit key used in the second FN?

There might be, but we don't have enough information to know.

> and what about the relationship between the bits of the one of the 96-bit key ? isn't it useful anymore ?

that information is accounted for when feeding the 16-bit result of the first FN into the second FN. The 96-bit key used used at this point is a different thing--it's a global 96-bit key, not a 96-bit key that changes at every address.