Page 1 of 1

STV & Model3 encryptions

Posted: Sat Dec 20, 2014 11:13 am
by andreasnaive
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.

Re: STV & Model3 encryptions

Posted: Sat Dec 20, 2014 11:37 am
by andreasnaive
The first step in the scheduled plan is to study the linear characteristics of the S-Boxes. In some quick code I has limited the search against characteristics using at most a couple of input bits; of course, the fewer involved bits, the better, so not all of them are equally useful. If you take all the ones that gives at least a minimum bias (the deviation against the excepted 1/2 probability of a perfectly random bit) of 1/64 there are too many, so, to give a feeling of them, here are the ones with biases at least 1/8 for the sboxes of the second Feistel network of Naomi M2 (first the 0-indexed input bits, then the output bits, then the bias):

Code: Select all

Naomi sbox #16 FN: 2 Round: 1 SB: 1 3 | 0 --> +11/64 1,3 | 0,1 --> +10/64 2,3 | 1 --> +11/64 1,5 | 0 --> +11/64 Naomi sbox #17 FN: 2 Round: 1 SB: 2 0,2 | 1 --> -9/64 3,5 | 0,1 --> +9/64 Naomi sbox #18 FN: 2 Round: 1 SB: 3 2,4 | 0 --> -11/64 Naomi sbox #19 FN: 2 Round: 1 SB: 4 0,2 | 0 --> -10/64 0,3 | 0,1 --> +9/64 4 | 0 --> +8/64 3,5 | 0,1 --> +11/64 Naomi sbox #20 FN: 2 Round: 2 SB: 1 0,2 | 0 --> -8/64 1,4 | 0 --> -8/64 1,5 | 1 --> -11/64 2,5 | 1 --> +9/64 4,5 | 0,1 --> -9/64 Naomi sbox #21 FN: 2 Round: 2 SB: 2 1,2 | 0 --> +9/64 1,4 | 0,1 --> +8/64 4,5 | 1 --> +9/64 Naomi sbox #22 FN: 2 Round: 2 SB: 3 0,2 | 0 --> +11/64 2,3 | 1 --> +10/64 1,4 | 1 --> -8/64 3,5 | 1 --> +8/64 3,5 | 0,1 --> -9/64 Naomi sbox #23 FN: 2 Round: 2 SB: 4 0,4 | 0,1 --> +9/64 1,4 | 0 --> +8/64 1,4 | 1 --> -13/64 4,5 | 0 --> +10/64 Naomi sbox #24 FN: 2 Round: 3 SB: 1 2 | 0 --> +9/64 2 | 0,1 --> -8/64 3 | 0,1 --> -10/64 3,4 | 0,1 --> -8/64 Naomi sbox #25 FN: 2 Round: 3 SB: 2 1 | 0,1 --> -8/64 1,2 | 1 --> +8/64 1,2 | 0,1 --> +8/64 0,4 | 1 --> +8/64 1,5 | 0,1 --> -8/64 Naomi sbox #26 FN: 2 Round: 3 SB: 3 [Omitted; incomplete s-box] Naomi sbox #27 FN: 2 Round: 3 SB: 4 | 0,1 --> -8/64 0 | 1 --> +8/64 2 | 1 --> -8/64 1,2 | 0,1 --> -8/64 Naomi sbox #28 FN: 2 Round: 4 SB: 1 1,3 | 1 --> -9/64 1,4 | 0 --> +11/64 3,4 | 1 --> -9/64 4,5 | 0,1 --> +8/64 Naomi sbox #29 FN: 2 Round: 4 SB: 2 2,4 | 0,1 --> +8/64 3,4 | 0 --> -9/64 Naomi sbox #30 FN: 2 Round: 4 SB: 3 3,5 | 0 --> +8/64 4,5 | 0,1 --> +11/64 Naomi sbox #31 FN: 2 Round: 4 SB: 4 0,4 | 0 --> -13/64 3,5 | 0,1 --> -10/64
Now, the inputs to the sboxes are, in general, a XOR of some intermediate data bits with some key bits; the whole point of a linear attack is to combine a number of differential characteristics in such a way that all the intermediate bits cancel, so that the only remaining bits would be input and output bits in the outer layers (the real input and output data of the decryption) together with some key bits. If you combine a number of such characteristics with biases b_i, the pilling-up lemma says that we will get a global bias for the full equation as 2^(n-1)*∏b_i. If you are really in despair for a good bias, you can run an entire automatic search for good ones but, as we have only 4 rounds here, I think I will simply do it manually.

Re: STV & Model3 encryptions

Posted: Wed Dec 24, 2014 12:36 am
by andreasnaive
In order to ease the study of the topology, I decided to take the time to create a full diagram of the second Feistel Network. It's clear from it that the implementation could be rewriten so that at most one key bit per sbox input be present. Beyond that, some relatively strong biases can be derived, and it can be seen that there is a couple of s-boxes (1-4 and 4-3) which are only affected from key bits from the game-key (and not from the sequence key or the middle result). By instance, here is 1-4:
screenshot.1.jpg (61.72 KiB) Viewed 27387 times
Using that sbox and a certain bias in another one in the third round, an attack against those 3 key bits can be engineered. I have tested it over simulated {cipherword,plainword} pairs and for, say, 10000 pairs, it works like a charm. This is the end of the good news.

The bad news is that apparently I was too optimistic about the amount of data available in the roms. Given that I don't have the plaintext, just some expected (but not provably present) biases in it, I would need much more data that what I can gather. It's a catch-22 kind of situation; if I aggressively filter the roms in order to get the encrypted data with little false positives, I end with no enough data; if I relax the requirements, noise makes his appearance. Decathlete have some nice chunks of encrypted data, but they seem insufficient for this; the results are unconvincing, to say the least.

Re: STV & Model3 encryptions

Posted: Fri Dec 26, 2014 11:32 pm
by andreasnaive
After seeing as the automatic extraction idea didn't really worked, I have switched to a per-game study of the sets. Thanks to Haze and CaH4e3, I now have some pairs both from STV sets (with the decrypted data coming from the Saturn sets) and from Model3 (for some chunks for which the plaintext is contained within the ROMs).

The first set I'm studying is Astra Super Stars. There are ~36K pairs of data. I have tried a couple of partial attacks on some limited number of key bits affecting a couple of sboxes in the first round. The good news is that both work fine, and this represent the first serious confirmation that these protected STV games are using the same scheme than Naomi-M2. Indeed, as the current Naomi implementation is probably incomplete, I'm being more systematic that what would be probably needed. In the current implementation, only 5 bits out of the 12 inputs bits for SB13 & SB14 use bit keys; my attacks try to recover all the 12 ones, just in case something is missing in the current implementation (which is probable, as we are using a strange bit count: 26). The bits set for Astra Super Stars in the results of the attacks are indeed a subset of those 5 ones used in the implementation, so all is clicking fine right now. I will try to develop more partial attacks in the next days.

Re: STV & Model3 encryptions

Posted: Mon Jan 05, 2015 1:42 am
by andreasnaive
Time for an update. After the last post, I spent several days developing some partial attacks and testing them on Astra Super Stars; most of that just consist on trying to get as big biases as possible involving a certain key bit by using the information on the topology of the network and on the linear characteristics of the sboxes; boring stuff.

I developed around 20 partial attacks; at that point I stopped due to that, well, the value of it was unclear... To be more precise, the attacks worked fine on simulated data (basically, using 36K of simulated {cipherword,plainword} pairs), and mostly worked for Astra Super Stars. Why "mostly"? That's the big question at this point. Skipping the technicalities of the issues, most attacks which try to guess key bits used in the first round and simply involve some plainword bits in the formulae seem to work fine. The statistical attacks show clear peaks pointing to what should be the right choices.

However, some of the attacks didn't worked at all, while working fine on the simulations. On closer examination, the failing ones are some of those which do the opposite to the ones described above; I mean, attacks which try to guess key bits used in the last round of the cipher and just involve some bits of the cipherword in the formulae.

My first hypothesis to explain the issues was to suppose that, simply, the data is not that well matched as we expected. After all, we are trying to match the encrypted data from the STV sets with the plain data from the Saturn set; it could be conceivable that the data was not an exact match, just approximately; maybe there could be regions inside that 36KWords chunk slightly shifted or something so. That could explain why the attacks in one direction fail (because, if the pairs are not properly matched, the cipherwords for a certain plainword would be mostly random) while the other ones still work (because, even if we mismatch them, the statisticals on the plaintext are strong enough —there are lots of zeros there— for it to work even then) .

That's not the only explanation, though. A more subtle problem would be that the bits in the plainwords used a different ordering; the difference would have to be just in the plainword ones, not in the cipherword bits. Otherwise the apparently working attacks shouldn't work at all. Supposing that, in relation with Naomi, one ending has changed his ordering and the other has not could seem an unnatural hypothesis, but there could be a simple explanation for that: the header. The Naomi scheme use a 18 bits header comprised of 2 bits flagging the mode of operation and another 16 bits which could be related with the size of the region to be processed (this is unclear). The existence of a different header in the STV games (by instance, the disappearance of the 2 mode bits) could explain such reordering.

I have run some tests trying to locate such possible reordering, but the results are inconclusive. I can neither claim nor reject the hypothesis by now.

In that state of things, I switched to the data for Steep Slope Slider, the other set for which there are a good bunch of pairs. And, to my desolation, the results were totally disappointing; no attack worked on that data, literally.

And that could be it but, fortunately, Deunan Knute gave me the (obvious, but embarrassingly missed) solution to the conundrum: if the security modules are compatible, why not transplant one of them to a Naomi board and use DK's interface to recover information from it? We will probably know what happens in the next weeks, after ANY solve some issues with failing electronic parts and the like. :)

Re: STV & Model3 encryptions

Posted: Wed Jan 14, 2015 12:04 am
by andreasnaive
Quick update: ANY solved the problems and dumped some data from a 315-5881 module from a Tecmo World Cup '98 board (STV) soldered on a Virtua NBA Naomi cart. The analysis of the data show that it first perfectly into the current implementation, being the key needed equal to 0x01200913.

Besides, Guru confirms that these modules are used too in some Model2 and Hikaru games, so they were used in boards from at least 7 SEGA systems: Model2, Model3, S-TV, Naomi, Hikaru, Naomi2 and SP/Aurora.