Page 1 of 1

CPS-2 & Naomi M2 sboxes

Posted: Wed Dec 10, 2014 1:13 pm
by andreasnaive
Some time ago, after having reverse engineered Naomi-M2's crypto scheme, I ran a comparison between the s-boxes from CPS-2 and the ones from Naomi. You can see both sets here:
https://github.com/mamedev/mame/blob/ma ... cps2crpt.c
https://github.com/mamedev/mame/blob/ma ... 81_crypt.c

Comparing them made sense, as both schemes are clearly related (my guess have always been that they are derived works from the same IP core). Both schemes are comprised of a couple of 4 Feistel Networks with 4 rounds each; the first FN is applied to the address; the second is applied to the cipherword using the result of the first one in the subkeys. Being able to detect a common set of s-boxes would, ideally, allow us to fix some of the degrees of freedom in both implementations. That, at his due time, *could* give us further hints on what the Naomi keys really are.

With this context in mind, and taking into account that when I did it last time more s-boxes than now were incomplete, I recently gave another look at the issue and pushed somewhat harder at it. Specifically, I considered a couple of s-boxes identical if they were invariant under the following operations:

1) Reordering of the 2 output bits
2) XORing the output bits with a constant
3) Applying a linear invertible 6 bits to 6 bits to the input (linear in GF(2)^6)

Excluding the 2 incomplete Naomi sboxes, I have found 11 hits, I mean, 11 couples of (CPS-2 s-box, Naomi s-box) which are the same modulus the cited operations (and, thus, could be expected to be EXACTLY the same in the real hardware implementations). Every couple is comprised of sboxes situated in the same round of the same FN for his corresponding scheme; using the notation (#Feistel Network, #Round, #Sbox in round) with indexes starting at 1, they are

Code: Select all

CPS-2		NAOMI
(1,2,4)		(1,2,1)
(1,3,3)		(1,3,1)
(1,3,4)		(1,3,2)
(1,4,1)		(1,4,3)
(2,1,3)		(2,1,2)
(2,2,2)		(2,2,1)
(2,2,4)		(2,2,3)
(2,3,3)		(2,3,2)
(2,4,1)		(2,4,2)
(2,4,3)		(2,4,3)
(2,4,4)		(2,4,1)
What about the other s-boxes? A look at the table show that all but one of the s-boxes of the 4th round in the second FN are matched, so, if the underlying s-boxes are really the same, both remaining ones should be matched. That mean that CPS-2-(2,4,2) and Naomi-(2,4,4) should be in the same equivalence class. These s-boxes are:

Code: Select all

    {
        1,2,2,1,0,3,3,1,0,2,2,2,1,0,1,0,1,1,0,1,0,2,1,0,2,1,0,2,3,2,3,3,
        2,2,1,2,2,3,1,3,3,3,0,1,0,1,3,0,0,0,1,2,0,3,3,2,3,2,1,3,2,1,0,2,
    },
and

Code: Select all

    {
        0,1,2,0,3,3,0,3,2,1,3,3,0,3,1,1,3,2,3,2,3,0,0,0,3,0,2,2,3,2,2,3,
        2,2,3,1,2,3,1,2,0,3,0,2,3,1,0,0,3,2,1,2,1,2,1,3,1,0,2,3,3,1,3,2,
    },
However, no linear transformations at input and output can convert one into the other. Why the differences? Time ago I supposed they simply could have been updated in order to improve their differential and linear characteristics (which are critical parameters for the security of the scheme), but I now find it unlikely. A wilder hypothesis is this: 6-to-4 sboxes could have been popular in the epoch (due to the use of 6-to-4 sboxes in DES); if you have a stock of 6-to-4 sboxes ready but have decided to use 6-to-2 in your design (in order to use 4 sboxes rather than 2 and having a better diffusion of the input bits into the sboxes), an idea would be to join couples of those 4 output bits through XORs gates. If choosing which pairs are joined uniformly at random for every such design, we have 3 possibilities for every s-boxes. If the sboxes in our two schemes were both generated both way, the probability of match would be 1/3. Out of 30 (32 minus the 2 incomplete ones for Naomi) I have found 11... I'm just brainstorming, so take all this with a grain of salt.

Whatever the case, I have no data to check anything, so I'm stopping here. Developing an attack against the STV and Model3 sets using the 315-5881 chip is awaiting, and that is way more interesting, and probably more doable.