Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

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.

share|improve this answer
    
Thanks, but even when doing this, even the wrong last-round subkeys all give eight next-to-last round subkeys (so 32 next-to-last round subkeys in total), even when checking the differentials at both rounds. I think I am doing something wrong - do I have to feed the cipher pairs with a different differential for each round's attack? And yes I am aware this is a trivial case, but I find it useful because it allows me to see how the attack works without worrying about very small probabilities - it wasn't immediately clear to me how differential cryptanalysis was used. –  Thomas Jan 29 '12 at 3:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.