Boomerang Attack on FEAL-6

Now that we've broken FEAL-4 via differential cryptanalysis, we'll extend the method a bit and go after FEAL-6. However, we will not be recovering any part of the key. You are certainly asking yourself "Then what's the point?". Instead of performing key recovery, we will be building a distinguishing attack. The end goal is that we can distinguish FEAL-6 from a random permutation. To make it more clear, imagine the following...You are a spy for Toon Town. The foreign intelligence service of your enemy Coolworld encrypts their communications using a magic sealed box. You steal one of the boxes but must return it quickly before they notice. Because the Coolworld Intelligence Agency is staffed by inferior cartoon characters, you suspect that the magic boxes may be running the very weak FEAL-6 algorithm. You quickly encrypt a couple of blocks with it, modify the ciphertext, and decrypt it back. By making a simple check on the resulting plaintext, you determine that the magic box is using FEAL-6. You return the box and exfill back to Toon Town. You inform the TTSA (Toon Town Security Agency) of your findings so that they can focus their cryptanalytic efforts knowing that the target algorithm is FEAL-6. The remainder of this page will describe what blocks you fed the box, how you modified them, and how you checked the result to identify the cipher.

Source Code

Here is the code I wrote that demonstrates the technique described on this page. Writing clear code that is easy to understand by humans is not a strong point of mine. Be sure that you have the diagrams on this page in front of you (preferably printed out) while reading the code. Enjoy!

FEAL-6 Boomerang Attack Code - [boom.c]

FEAL-6

We will not discuss the algorithm much here. Check out the FEAL-4 page for a description of the algorithm in general. Just insert 2 additional rounds in the middle of the path and you'll have the 6 round variant. Recall that 64 bit plaintext blocks are encrypted using 8 32 bit subkeys to produce 64 bit ciphertext blocks. The overall structure is a Feistel cipher.

Finding a 3 Round Differential

Before we go into the specifics of boomerang attacks, we need to find a full differential characteristic that holds true with high probability through 3 rounds of FEAL. During our differential analysis last time, all I found was a 2.5 round differential. The Feistel structure allowed us to use this to recover the last subkey of the 4 round variant. Boomerang attacks require us to find differentials that can cover half the cipher; that is why we need one that covers 3 rounds. Luckily, there is one that fits this requirement that holds 100% of the time. As you'll see, this is devastating.

A good place is start looking for a longer differential is inside the round function itself. Recall that FEAL's round function consists of only a couple of operations: XOR and G-boxes. We can predict the behavior of differentials through the XOR operations, but the G-boxes give us a bit more trouble because they aren't entirely linear. I wanted to find out what differentials hold through the G-boxes with 100% probability. Rather than fiddle around trying to figure out how the bitwise rotations and modular addition inside the boxes respond, I wrote a little code. The G-boxes take two 8 bit inputs and produce an 8 bit output. So we can just try every combination of the two inputs vs. every other combination of two inputs (comparing the outputs that come out). We are basically brute forcing the search for 100% differential characteristics in the G-boxes. Once you do this for G0 and G1, you quickly find that only a few differentials hold for every case:

Armed with this knowledge, you can manually plug in the values 0x00 and 0x80 into each of the 4 bytes that make up the input to the round function. Doing this by hand (trying every permutation) doesn't take very long and you'll get a feal for what's going on if you do it yourself. Just remember that if anything other than 0x00 or 0x80 enters a G-box, we cannot predict the cooresponding output differential. The end result of all of this fiddling is that you'll find the following differential characteristics hold 100% of the time through the F-box:

That isn't much to work with to build a 3 round differential, but it turns out that its a enough. By doing some clever trickery using the XORs in the Feistel structure we can stretch out what we have to cover 3 rounds. Your best bet is to examine the diagram on the left a work through why those differentials form the path that they do. You can easily use this 3 round path to do last subkey recovery against FEAL-5, but our goal is this distinguishing attack against the 6 round version.




The Details

As you read this, watch the diagram of the differential to the left. We start by choosing two plaintexts that when XOR'd together produce 0x02000002 in the left half and 0x82808082 in the right half. Both halves pass through the first pre-rounds subkeys unaffected because the subkeys stay the same between encryptions (differential of 0x00000000). Next the right half XORs with the left half to produce 0x80808080. This value becomes the left input to round 2 and also feeds into the first round function. As we found above, in the FEAL round function, 0x80808080 always results in an output differential of 0x02000002. This output XORs with the left input (0x02000002) to produce a differential of 0x00000000 which becomes the right half of the round 2 input.

So, heading into the second round, we have 0x80808080 on the left and 0x00000000 on the right. The zero differential passes through the second round function to produce a zero differential in the output. This happens with any deterministic function; if you make zero change to the input, you will get zero change in the output. This 0x00000000 XORs with the 0x80808080 to produce the right-side input to round 3: 0x80808080. Meanwhile the left side input to round 3 is 0x00000000.

Round 3 begins with 0x00000000 on the left and 0x80808080 on the right. The right side pushes through the round function to produce our old friend 0x02000002. This output differential gets XOR'd with the left side differential (0x00000000) to produce 0x02000002 on the left side of the round 3's output. The right side output takes the value: 0x80808080. So we find the following 3 round differential characteristic for FEAL that always holds true:












The Boomerang Attack

The boomerang attack was discovered by David Wagner as a way to extend the power of normal differential cryptanalysis. It allows the analysis to use two unrelated differential characteristics to attack the same cipher. By using one differential to defeat the first half and another to defeat the second half, he can beat the full cipher. There is no requirement that the differentials share an intermediate value. The effect of this discovery on cipher design is that the number of rounds that must be secure against differential attacks effectively doubles. Whereas normal differential cryptanalysis is a chosen-plaintext attack, the boomerang technique is an adaptive-chosen ciphertext attack. The analyst chooses two plaintext blocks which differ by some input differential value. Next, he encrypts them using the target cipher (and its secret keys, of course). He then takes each of the cooresponding ciphertexts and XORs them with another differential to produce two new adaptive-chosen ciphertexts. Next, he decrypts each of those new ciphertexts and decrypts them using the target algorithm (with secret keys) to produce two new plaintexts. Finally, the analyst must XOR those new plaintexts together. If the differential produced matches the differential that was used to produce the original plaintexts, it is almost certain that the encrypt/decrypt functions used are identified (as FEAL-6 in this case).

The way this works will likely blow your mind for a bit (it scrambled mine up pretty good for a while). The cipher is broken into two halves. When you do the encryption (using your chosen-plaintexts), you are expecting that the 3 round differential we found earlier will occur. Now, this only gets us halfway through the cipher; after that 3 round mark, we cannot predict anything. When we XOR the resulting ciphertexts with another differential to create new ciphertexts for decrypting, we are setting up two decryption paths that should follow this second differential. Sure enough, they follow the differential and end up back at the midway point with a known differential. Again, we cannot predict anything in these paths after that point (because the characteristic only covers 3 rounds).

However, now we have an interesting situation. P0 gets encrypted to create a midpoint value of M0 (the same thing goes for P1 and M1). Although we cannot know the values of M0 and M1, we do know that they differ by some known output differential(X). When we decrypt the adaptive-chosen ciphertexts (C2 and C3), we generate M2 and M3 after 3 rounds of decryption. Once again, we cannot know these values, but we do know that the difference between M0 and M2 is some output differential(Y). More importantly, because used the same differential(Z) to generate M2 and M3; the difference between M1 and M3 is the same output differential(Y). If M0 and M1 differ by X, M0 and M2 differ by Y, M1 and M3 differ by Y, then M2 and M3 must differ by X as well. If M2 and M3 differ by X, then they're cooresponding plaintexts (after full decryption) must differ by the input differential that produced X. This is the original differential that was used to choose the plaintexts that started this whole process.

So for FEAL-6, we choose two plaintexts that differ by 0x0200000282808082. Then we encrypt these to produce a midpoint differential(X) of 0x0200000280808080. When the cooresponding ciphertexts pop out as C0 and C1, we XOR each of them by 0x0200000282808082 to produce C2 and C3. Next we send these values back into the magic box for decryption. This generates two identical midpoint differentials(Y) of 0x0200000282808082. This arrangement causes the difference between M2 and M3 to be 0x0200000282808082 as well. We know that an input differential of 0x0200000282808082 always results in this midpoint differential. So we check for that input difference in the resulting plaintext (after decryption).

That cool arrangement in which the midpoint differentials X and Y occur is called a quartet. If it doesn't happen, the deccrypted plaintext differential will not match the chosen-plaintext differential. When these do not match, it indicates that the suspect encryption algorithm is not FEAL-6. In this particular implementation of the boomerang attack I used the same differential for each half of the cipher but this is not necessary. A result of this is that X and Y are equal to each other. This is not necessary, however; We can use a different differential characteristic for the last 3 rounds if we want.















What's next?

The next logical step is to try extending this to recover the last round subkey. My head cannot comprehend how this can be done at the moment, but that may change. Let me know if you find this page useful, mistake-ridden, confusing or enlightening. Good luck...