Edit Jan 3: Andy has pointed out a flaw in this article. The order of the bits in the L and R groups is important, so we cannot draw any conclusion yet.
Andreas Naive has been doing some very interesting observations lately.
I thought it would make sense to check if we were lucky and the algorithm was indeed structured like a 4-round Feistel network as Andy supposed.
The basic idea of a Feistel network if that you have a round function f() which operates on some bits of the data (8 in our case), and modifies them depending on a key. The function f is the same on every round, while the key changes.
We don't need to care about a key at this point, since we don't know anything about the algorithm. It's easier (and more general) to simply assume that at every round a different function fn is used, where fn describes a permutation of the values 0 to 255.
We have decided that there is strong evidence indicating that the 16 bits of the data should be split in two groups of 8 bits like this:
L = { 0, 1, 2, 4, 6, 7, 13, 14 }
R = { 3, 5, 8, 9, 10, 11, 12, 15 }
So a 4-round Feistel network would work like this:
Given the ciphertext E = (L0, R0),
L1 = R0
R1 = L0 XOR f1(R0)
L2 = R1
R2 = L1 XOR f2(R1)
L3 = R2
R3 = L2 XOR f3(R2)
L4 = R3
R4 = L3 XOR f4(R3)
and the resulting plaintext is D = (L4, R4)
By the properties of a Feistel network, we can also go backwards, starting from D = (L4, R4)
R3 = L4
L3 = R4 XOR f4(L4)
R2 = L3
L2 = R3 XOR f3(L3)
R1 = L2
L1 = R2 XOR f2(L2)
R0 = L1
L0 = R1 XOR f1(L1)
Now let's start from both sides and meet in the middle. Going from E to D we have
L2 = R1 = L0 XOR f1(R0)
Going from D to E we have
L2 = R3 XOR f3(L3) = L4 XOR f3(R2)
Putting the two together we have
L0 XOR f1(R0) = L4 XOR f3(R2), that is
L0 XOR L4 = f1(R0) XOR f3(R2)
Now remember that we know all (E,D) pairs, so we can take advantage of that.
If we take (E,D) and (E',D') such that L0 XOR L4 = L'0 XOR L'4, then it follows that
f1(R0) XOR f3(R2) = f1(R'0) XOR f3(R'2)
If additionally E and E' are such that R0 = R'0, then we are left with just
f3(R2) = f3(R'2)
and since f3 is a bijective function, this implies that
R2 = R'2, that is
L3 = L'3, that is
R4 XOR f4(L4) = R'4 XOR f4(L'4), that is
f4(L4) XOR f4(L'4) = R4 XOR R'4
Now we can repeat the procedure for all (E,D) pairs, and get a large number of equations on f4.
If the CPS2 encryption was a 4-round Feistel network, all those equations would not be contradictory, and they would allow us to reconstruct the structure of f4.
Unfortunately, they are contradictory. E.g. you get something like this:
f4(0xff) XOR f4(0xfc) = 0x11
f4(0xff) XOR f4(0xfc) = 0x48
Therefore CPS2 is not a 4-round Feistel network.
3 comments:
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:
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.
What i try to say with that? That you can not know when this condition:
>If we take (E,D) and (E',D') such that L0 XOR L4 = L'0 XOR L'4
holds unless you know how the semi-permutations affecting L and R work, and i'm supposing you don't have such information. ;)
Andreas
Point taken. I did try swapping L and R but hadn't considered that in that case the permutations become important.
I have just seen your comment, but, as i had yet written this, here it goes:
--------------------
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.
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.
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)).
The problem with this condition:
>If we take (E,D) and (E',D') such that L0 XOR L4 = L'0 XOR L'4
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...
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:
P1:
0 -> 0
1 -> 1
2 -> 2
3 -> 3
and
P2:
0 -> 0
1 -> 1
2 -> 3
3 -> 2
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).
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
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.
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.
Post a Comment