Differential cryptanalysis - breaking the last round of FEAL4?

Question

I've been trying to learn cryptanalysis. I've come across this resource which proved very helpful:

http://theamazingking.com/crypto-feal.php

So far I've been almost successful in breaking FEAL4 using differential cryptanalysis - I've got three of four rounds down and working on the last one. Basically the method (as I understand it, anyway) uses differential characteristics to isolate a particular subkey, allowing one to brute-force it independently of the others.

But apparently, for instance breaking the last round (as done on the webpage) yields 4 subkeys which are, from the attack's point of view, equally valid. This means the complexity of breaking the next round increases by a factor of 4, which in turn increases exponentially as more rounds are broken.

So my question is - is the method shown on the webpage "flawed" in some way, or is this result simply a consequence of the key space being so much larger than the block space (2^192 vs 2^64), which means there are many equivalent keys for a given ciphertext?

Answer 1

No, it's not flawed. You're just running into a fact of life; differential cryptanalysis generally doesn't just give you the entire key (or even subkey) in one shot. It generally gives you partial information about the key, and if you want the entire key, well, you need to work at it more.

In this phase of the attack, you know that the last round subkey is one of four possibilities. Here's one obvious way to continue the attack on the next-to-last (penultimate) round subkey: you introduce the same set of differentials advanced one round (so that it has a probability 1 of surviving the first round, and fails on round 2). In the example they gave, this would be an input differential of 0x00000000 on the left side, and 0x80000000 on the right.

Then, for the output of each differential, reverse the last round operation (using each of the 4 possible last round subkeys), and see if there is a possible next-to-last round subkey that makes that differential work, and if so, what is that next-to-last round subkey is.

If you do this is a number of differential pairs, it is quite likely that an incorrect guess to the last round subkey will not allow any next-to-last round subkey work for at least one of the differentials; that is, for one of the differential outputs you'll have in hand, there will be no value that the round 3 subkey can take on that would make that a possible output. That means that you can eliminate the three incorrect guesses of the last subround key. In addition, that also gives you four possible values for the round 3 subkey.

So, to recap, this next phase of the attack verified the last round subkey, and also gave us most of the next-to-last round subkey. It should be fairly obvious how this attack continues. Note that continuing this attack doesn't cause any exponential blow-up, as we are able to verify the remaining subround key bits left unverified by the previous attack.

Now, if there is a problem with this example of differential cryptography, it is that it is somewhat atypical of how differential cryptanalysis usually works; it's not really misleading, but it is rather simpler in this case. There is almost never a probability 1 differential through most of the cipher. Instead, we generally need to work with differentials with a considerably lower probability of holding, and use statistical methods to figure out when the differential holds.