tag:blogger.com,1999:blog-10457042.post116778131567234062..comments2015-03-29T12:49:01.298+02:00Comments on Nicola's MAME Ramblings: CPS2 is not a 4-round Feistel network (maybe)Nicola Salmorianoreply@blogger.comBlogger3125tag:blogger.com,1999:blog-10457042.post-1167813399874284892007-01-03T09:36:00.000+01:002007-01-03T09:36:00.000+01:00I have just seen your comment, but, as i had yet w...I have just seen your comment, but, as i had yet written this, here it goes:<BR/>--------------------<BR/><BR/>OK, now that i have more time i will give you a clearer example (i was somewhat sleepy when writing the previous comment :P ), for the shake of clarity.<BR/><BR/>Let's suppose we have a 4 bit version, with Ln and Rn 2 bits long, and the FN's encryption is such that R4=R0 and the bits of L4 are the same than in L0 but permuted. So the input to the FN is (L0, R0) and the output is (R4, L4). We can understand those pairs like 4-bit numbers.<BR/><BR/>Now lets add a permutation P before the first round and his corresponding P^-1 at the end. So the entry to the algorithm is now P^-1((L0, R0)) (that i will write, abusing of the notation, as (P^-1(L0), P^-1(R0)) and the output is P((R4, L4)) (that i will write as (P(R4), P(L4)). <BR/><BR/>The problem with this condition: <BR/>>If we take (E,D) and (E',D') such that L0 XOR L4 = L'0 XOR L'4<BR/><BR/>is that what you can look in the tables are not L0, L4, L'0 and L'4 but, instead, P^-1(L0), P(L4), and so...<BR/><BR/>And your condicion can not be deduced from there, i mean, P^-1(L0) XOR P(L4) = P^-1(L'0) XOR P(L'4) doesn't imply L0 XOR L4 = L'0 XOR L'4. To see it, considere these couple of alternative permutations:<BR/><BR/>P1:<BR/>0 -> 0<BR/>1 -> 1<BR/>2 -> 2<BR/>3 -> 3<BR/><BR/>and <BR/>P2:<BR/>0 -> 0<BR/>1 -> 1<BR/>2 -> 3<BR/>3 -> 2<BR/><BR/>If the first permutation is used, then all is OK, as the condition about the P^-1(Ln) imply the other one. But, if the permutation P2 is used, you are in a problem... Consider what happens if P2^-1(L0, R0) is (1,0,0,0) and P2^-1(L'0, R'0) is (1,1,0,0) ; then, (L0, R0) = P2(P^-1(L0, R0)) = P2((1,0,0,0)) = (1,0,0,0) and (L'0, R'0) = P2((1,1,0,0)) = (0,1,0,0); then, due to the way the FN works, (R4, L4) = (0,0,0,1) and (R'4, L'4) = (0,0,1,1), so, finally, P2((R4, L4))=(0,0,1,0) and P2((R'4, L'4))=(0,0,1,1).<BR/><BR/>To sum up, we have L0=(1,0), L4=(0,1), L'0=(1,1), L'4=(1,1), P2^-1(L0)=(1,0), P2(L4)=(1,0), P2^-1(L'0)=(1,1) and P2(L'4)=(1,1) and, although<BR/>P2^-1(L0) XOR P2(L4) = (0,0) = P2^-1(L'0) XOR P2(L'4), L0 XOR L4 is (1,1) while L'0 XOR L'4 is (0,0). In general, only half the times when the first condition holds the second one holds too.<BR/><BR/>The point of this refutation, then, is that while your argument can be right, you cannot run a test to verify it unless you know the structure of the permutation.Andreas Naivehttp://www.blogger.com/profile/02852453973867816281noreply@blogger.comtag:blogger.com,1999:blog-10457042.post-1167812680317697792007-01-03T09:24:00.000+01:002007-01-03T09:24:00.000+01:00Point taken. I did try swapping L and R but hadn't...Point taken. I did try swapping L and R but hadn't considered that in that case the permutations become important.Nicola Salmoriahttp://www.blogger.com/profile/06048642443376701628noreply@blogger.comtag:blogger.com,1999:blog-10457042.post-1167789238701666412007-01-03T02:53:00.000+01:002007-01-03T02:53:00.000+01:00As i understand your argument, you have done a tes...As i understand your argument, you have done a test over a table to verify whether or not those formulaes are not contradictory. The argument seems to be OK, but you have missed the effect of the initial and final permutations. Let's see:<BR/><BR/>Forget by a moment the permutations. Then, we have a 4-round FN that have as input (L0, R0) and produces as output (L4, R4). Right? Well, not really; what the FN produces is (R4, L4), and that makes a big difference, because, when we add a permutation P at the beggining and P^-1 at the end, the part of the permutation that affect L0 is the part of the permutation involving the bits of the block L, while the part of the permutation that affect L4 is the part involving the bits of the block R, and both semi-permutations don't work the same way.<BR/><BR/>What i try to say with that? That you can not know when this condition:<BR/><BR/>>If we take (E,D) and (E',D') such that L0 XOR L4 = L'0 XOR L'4<BR/><BR/>holds unless you know how the semi-permutations affecting L and R work, and i'm supposing you don't have such information. ;)<BR/><BR/>AndreasAndreas Naivehttp://www.blogger.com/profile/02852453973867816281noreply@blogger.com