Edit: As Andy pointed out, the following reasoning is fatally flawed by the fact that the fn functions are not bijective.
So, given the strong evidence Andy has found, it really looks like the algorithm is a 4-round Feistel network.
This is actually good news, I have to say I am relieved ;)
Remember that
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)
In the previous article I showed that if we take (E,D) and (E',D') such that L0 XOR L4 = L'0 XOR L'4 and R0 = R'0, then
R2 = R'2.
I'll now take a different route from the one I took yesterday, to avoid the flaw that Andy noticed.
From R2 = R'2 follows that
L1 XOR f2(R1) = L'1 XOR f2(R'1), that is
R0 XOR f2(R1) = R'0 XOR f2(R'1), that is (since R0 = R'0)
f2(R1) = f2(R'1), that is (since f2 is bijective)
R1 = R'1, that is
L0 XOR f1(R0) = L'0 XOR f1(R'0), that is (since R0 = R'0)
L0 = L'0, therefore
(E,D) = (E',D')
Therefore two different pairs with the requested property cannot exist.
When converting the 16-bit values to and from (L,R) pairs, we need to take the initial and final permutation into account. Note that we are not using R4 in the above; we are only using L0, R0, and L4. Also, we don't care about the effects of the permutation on L0 and R0, the only thing we care about is that when we do L0 XOR L4 we XOR the correct bits together. So we can arbitrarily fix the permutation on L0 and R0, and try all possible permutations on L4.
So if the CPS2 algorithm were a Feistel network, for some permutation of the bits in L4 it should not be possible to select two different pairs (E,D) and (E',D') with the requested property.
This doesn't happen: for every permutation, such pairs exist. Therefore CPS2 is not just a 4-round Feistel network.
This is not to say that Andy isn't on the right track, on the contrary, the findings in CPS-2 (5) are extremely interesting, but the algorithm cannot be just a 4-round Feistel network. There's something else we are missing.
2 comments:
Sorry, but i have to refute again your experiment. ;)
I had indeed to have mentioned yesterday, but i have to recognize i haven't payed attention till now. Sorry again. :P
The (very evident) flaw is this:
>(since f2 is bijective)
False. A Feistel function is not required to be biyective; indeed, i think that FN with only biyective functions would be weaker than the general case... the Feistel function is the responsible for confusion in the encryption, and it should be such non-linear as possible (of course, a good Feistel function will change approximately half the bits in his output when you flip a bit in his input), but, definitively, it is not needed that it be a bijection.
LOL, you are absolutely right.
Excellent news actually :)
Post a Comment