After ANY's confirmation that some Sega Titan Video encrypted games (decathlete and the like) and some Model3 ones were using the same protection chip (315-5881) as Naomi M2 boards, Haze tried to brute force into the thing by looking for a bunch of decrypted zeros on the full keyspace. CaH4e3 also graciously offered his code for breaking M2 keys, but it's also a brute-force kind of thing and it depends on some suppositions about the inner structure of the encrypted data. Convinced that we could do a much finer and more systematic analysis on this, I scheduled to devote some time to it. The time has come.

So... what is the plan? Naomi M2 use a couple of Feistel Networks for decryption, in the same way than CPS-2 boards. Back in 2006 I analyzed CPS-2 sboxes' linear characteristics in order to deploy a linear attack on the scheme. While the number of required (cipherword, plainword) pairs needed for it (around 2^18-2^19) did it much less useful than the meet-in-the-middle attack implemented by Nicola, it still was usable and showed some strong linear weaknesses of the sboxes. A similar attack could help us to implement a distinguiser and, hopefully, an attack for some key bits. There are a couple of significative differences with the current case, one positive and one negative.

The negative one is that we don't currently have access to (cipherword, plainword) pairs, so at present we can only aim at statistical analysis of the data, and noise must be taken into account. On the other hand, the positive difference is that Naomi M2's key scheduling compares very badly with CPS-2's one; I'm probably being overindulgent here. That key scheduling is so bad that it ruins what is otherwise a sensible scheme. Many input bits to the s-boxes are not XORed with any key bit (and there are indeed 2 keys here; one fixed per board, and the other selected per decryption run); in the second Feistel network, the result of the first one is used as a subkey too. Now, if we are able to develop a linear attack against the second Feistel network while "dodging" the positions where the result of the first Feistel network are used, we would be indeed attacking a single Feistel Network and, so, the complexity of the attack reduces and the amount of data needed, a priori, would be reduced by a square root. Overall, we could expect to compensate the increase in data requirement due to the statistical nature of the attack with the decrease due to our attack against only one of the Feistel networks.

A couple of minor difficulties remain. First, I'm supposing we are able to discriminate where in the ROMs the encrypted data is located; fortunately, there are automatic techniques which gives us a reasonable way to do it. Second, there are still an incomplete s-box in the second Feistel network of Naomi M2; the workaround can be either avoid to touch it entirely in the linear attack or to develop attacks conditioned on the incomplete part being unused at all.

To sum up, all the pieces seem in place to develop at least a random distinguiser for Naomi M2 (some code able to distinguish Naomi M2 encrypted data from truly random data); with it, we could check whether or not those STV and Model3 sets are really using the same scheme. A negative result would not be the end of the story either; that chip doesn't only have encryption capabilities, but compression ones too. So it being used for compression rather than encryption would be a possibility too.