Andy has published his program but is reporting some problems in recreating the original tables--the values generated by his program are XORed with a constant value when compared with the original table.
I have just verified that this doesn't happen to me, so I presume this is due to a different method we used to reconstruct the Feistel function for the first two rounds.
Let's recap how this was done. The fundamental idea was published by Andy:
since R4 = L3 XOR F4(L4), if you pick (E,D) and (E',D') such that L4 = L'4, then
R'4 = L'3 XOR F4(L'4) = L'3 XOR F4(L4) = L'3 XOR R4 XOR L3
therefore
L3 XOR L'3 = R4 XOR R'4
Now if we pick (E,D) and (E',D') such that L4 = L'4 and E and E' differ by only one bit, we can see how flipping a single bit in the input changes the output after the third round. Andy's fundamental discovery was that flipping certain bits never affects certain other bits.
That knowledge can easily be used to determine F4. Take (E,D) and (E',D'), where E and E' differ only by one bit which we know doesn't affect bit b in L3. Then we know that
Bb(L3 XOR L'3) = 0
where Bb(x) gives me the value of bit b of x.
Therefore
Bb(R4 XOR F4(L4) XOR R'4 XOR F4(L'4)) = 0
that is,
Bb(F4(L4) XOR F4(L'4)) = Bb(R4 XOR R'4)
Do that for all b and for all E, E' pairs, and you quickly reconstruct the whole F4 structure. I'm saying its structure and not F4 itself, because it's all done through XOR so you need to set F4(0) arbitrarily, then all the others are derived from it through XOR.
After F4 is reconstructed, it can be used to undo the fourth round of the encryption. Then you repeat exactly the same process to reconstruct F3 (still XOR an arbitrary value). Then use F3 to undo the third round, and you are left with just two rounds.
Now things get really simple, because by definition
L2 = L0 XOR F1(R0)
R2 = R0 XOR F2(L2)
and since you know all of L0, R0, L2, and R2, F1 and F2 are immediately derived as
F1(R0) = L0 XOR L2
F2(L2) = R0 XOR R2
Note that here we derive F1 and F2 explicitly, not XOR an arbitrary value.
13 comments:
OK. I also took F4(0)=F3(0)=0; i have done the calculus for F2 and F1 using the same ideas than you, but i didn't notice i was leaving the FN(0)=0 initialization code (the problems of reusing code :P). And, doing it so, you are into problems... ;)
By the way, i was thinking on this this morning, and i was not very sure of the validity, but, now that i see you have reached the same conclusions, i will share it:
once you have explicitly reconstructed F1 and F2, you can obtain the exacts L2 and R2, so you can go back and reconstruct explicitly F3 and F4 by using the same ideas with L2, R2, L4 and R4. ;)
Edited: thinking on it again, i still have the same doubts: as you only have a "differential" version of F3 and F4, you can only obtain a differential reconstruction of L2 and R2, so it's not true than you can reconstruct explictly F1 and F2. Simply, you obtain the F1 and F2 that make the whole thing work. (and that is to say a lot ;) ). Am i missing anything?
That's correct, you obtain F1 and F2 explicitly because there's only one way to make it work after the arbitrary choices for F3 and F4. If you make a different choice for F3 and F4, F1 and F2 will be different.
Essentially, if you XOR F4 with a value, then F2 needs to be XORed with the same value, and the subkey for F3 has to be adjusted as well.
If you XOR F3 with a value then you need to XOR F1 with the same value and adjust the subkey for F2.
Oooops. 8(
I now have access to the sources and i have just reviewed what i did with F1 and F2 and, i was, indeed, using a differential method, so i was wrong about that.
But, when i was thinking on how to change my files, i have noticed what we are really doing... i said that "you obtain the F1 and F2 that make the whole thing work" and that's can be indeed a very bad thing...
Because, seeing it from another point of view, what you are doing is FORCING the values of F1 or F2 so that "things looks beautiful", but i have serious doubts about if you are unveiling the structure or you are mangling it...
Because, by one side, maybe the form you choose F4 and F3 is not so equivalent as i had thought to the "real" one; and, more important, if you are not selecting the correct permutation (excuse me if i'm becoming repetitive about this), then doing L0 XOR L2 or R0 XOR R2 is indeed a very bad thing... by the same reason that we discussed two post ago: both numbers would be showing the effect of different parts of the permutation...
The effect of that forcing heavily worry me, because if we are mixing things, that could be an effect hidding the regularities of the subkeys associated with F1 and F2...
I think i will continue with the differential method; maybe my initial idea was right and we can obtain some additional info about the F_N's by examining the b_n numbers...
Whatever path you take, please be sure that you are selecting a good permutation (as i said in the comments to my post), because, if not, i'm absolutely sure than you will be messing things up due to the way you are calculating F1 and F2.
I am using a good permutation so that is not a problem.
As I understand it, the arbitrariety in selecting the F3 and F4 s-boxes should not change the subkeys in a relevant way. The only effect on the subkeys should be a constant XOR in the 2nd and 3rd round subkeys--therefore not relevant for our analysis. 1st and 4th round subkeys should not change at all.
>I am using a good permutation so that is not a problem.
Nice to know it. :)
>As I understand it, the arbitrariety in selecting the F3 and F4 s-boxes should not change the subkeys in a relevant way. The only effect on the subkeys should be a constant XOR in the 2nd and 3rd round subkeys--therefore not relevant for our analysis. 1st and 4th round subkeys should not change at all.
Ummm, i'm more willing to accept that the subkeys from round #4 won't change in relevant ways than to accept that; i'm not sure, however. And... well, possibly if only some of the subkeys change in complex ways we can discover it by comparing the statistical regularities of the subkeys in different positions. ;) Go ahead, we will solve problems as they appear. :P But i want you to notice that it's not only by XORing the input to the S-boxes how this could change... you could, by example, also have XORs at the output of the S-Boxes at round #4, and that would modify the subkeys for the other rounds (including round #1).
I will thought a little whether it's possible to obtain more information from the differential Fn's.
Forget the comment about the XOR's. ;) I need to meditate on this.
>As I understand it, the arbitrariety in selecting the F3 and F4 s-boxes should not change the subkeys in a relevant way. The only effect on the subkeys should be a constant XOR in the 2nd and 3rd round subkeys--therefore not relevant for our analysis. 1st and 4th round subkeys should not change at all.
OK. After some paper & pencil work, now i fully follow and agree with you. However, even in the 1st and 4th round the subkeys will be XORed: a XOR must appear depending of which one of the equivalente S-Boxes you choose (that is to say, depending on to which table you assign the subkey = 0). But it seems OK.
>Essentially, if you XOR F4 with a value, then F2 needs to be XORed with the same value, and the subkey for F3 has to be adjusted as well.
Yes, i now see it perfectly, but... have you noticed that that value that is XORed depends on the table (i.e., depend on the address)? This suppose a difficulty to recover the subkeys, as i see it.
> However, even in the 1st and 4th round the subkeys will be XORed: a XOR must appear depending of which one of the equivalente S-Boxes you choose (that is to say, depending on to which table you assign the subkey = 0).
Yes, but I wasn't even considering this, since it's just a fixed XOR in the s-box input, while XORing the s-box with a constant affects other s-boxes as well.
> Yes, i now see it perfectly, but... have you noticed that that value that is XORed depends on the table (i.e., depend on the address)? This suppose a difficulty to recover the subkeys, as i see it.
I don't understand what you mean, the address should have nothing to do with it. Of course the address changes the subkeys, but that's all. Can you make an example?
One important thing which took some time to iron out tonight is that the arbitrariety in the F3 and F4 s-boxes selection allows for ONE XOR on the whole box. Boxes that don't have 6 data inputs, and therefore would seem to be made of 2 or 4 independent blocks, need to have those blocks "aligned", otherwise the F1/F2 blocks wouldn't match.
>I don't understand what you mean, the address should have nothing to do with it. Of course the address changes the subkeys, but that's all. Can you make an example?
I was thinking on the way to choose F3(0) and F4(0) but, once we have selected a definition for the s-boxes from one table (two or four for the special ones), all are referred to those, so we have, indeed, only one. I needed to sleep when i wrote that. ;)
>One important thing which took some time to iron out tonight is that the arbitrariety in the F3 and F4 s-boxes selection allows for ONE XOR on the whole box. Boxes that don't have 6 data inputs, and therefore would seem to be made of 2 or 4 independent blocks, need to have those blocks "aligned", otherwise the F1/F2 blocks wouldn't match.
Yes, there is a problem with special s-boxes. I supposed those special s-boxes would have to be properly created to avoid artifacts... You can visualize the problems as i have said: you need to know which relation there are between F3(0) and F4(0) between all the tables from you are extracting the s-boxes...
BTW, after thinking on it, i believe that the differential method could allow me to discriminate F4(0) and F3(0) for a given table, giving us the correct F_N's, no longer differential ones. I think i can filter out incorrect selections of F3(0) and F4(0), although i'm not sure at this point if i could reach THE real solution or only a big amount of possible combinations. I haven't tested this in practice, however...
Besides working a little on it to try to obtain F3(0) and F4(0), i don't know if i'm longer needed here; as i see it, this is pretty much done and, as you seem nearer to have a program to extract easily the subkeys (my programs need to be cleaned and unified and the permutation has to be fixed), i will leave the work of RE the key scheduling to you and i will move to another projects. If at some point you need somebody to give you a second opinion or to verify something, contact me (but i think it won't be necessary ;) ).
> I think i can filter out incorrect selections of F3(0) and F4(0), although i'm not sure at this point if i could reach THE real solution or only a big amount of possible combinations.
As I see it, there isn't ONE correct solutions, there is a class of solutions modulo arbitrary XORs. Only the key scheduling will give more elements to discriminate among them (e.g. if the scheuling involves additions, we could make the subkey bits such that the carry works as expected without additional XORs).
Please don't move on to something else yet, your help is still needed here. The basic encryption is now understood and working, but the key scheduling doesn't seem to be simple at all.
I'm now in the process of extracting key tables for the three CHDs I have on my HD, then I'll publish the program and tables for further analysis.
>As I see it, there isn't ONE correct solutions, there is a class of solutions modulo arbitrary XORs. Only the key scheduling will give more elements to discriminate among them (e.g. if the scheuling involves additions, we could make the subkey bits such that the carry works as expected without additional XORs).
I have reached the same conclusion after some work; i only needed some time to meditate on that. ;) I use to work in a slower way, and the pace this has been moving the last days make my state of mind change quickly. It's funny, but sometimes i can be losing the track until i do more work. Sorry for that.
>the key scheduling doesn't seem to be simple at all.
OK. I will take a look at that when you publish the tables and your findings about the subkeys.
Post a Comment