As someone with a non-crypto background, I learned that differential cryptanalysis is mostly weak against ciphers like DES because, being a chosen plaintext attack, for a state of art complexity of $2^{47}$ there is a need for $2^{47}$ plaintext bits to conduct this attack which is realistically infeasible.
So what's the point of this attack vector at all? If it has always been known that you need a huge amount of plaintext for these to work, why did people bother?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
Differential cryptanalysis is a very powerful technique that permitted highly practical attacks on many ciphers that were not designed to resist it (e.g. FEAL-4). DES, as it turns out, was designed to be pretty resistant to it, which is why it requires an essentially impractical amount of chosen plaintexts to implement a differential attack on DES.
However, I would note that $2^{47}$ is still significantly less plaintext than a generic codebook attack requires, and moreover the attack has a time complexity of only about $2^{37}$ DES calls (which is significantly better than the generic key-guessing attack). As such, differential cryptanalysis counts as a 'break' of the cipher (anything that is better than generic attacks is a 'break'). It is only an 'academic' break, given the impracticality of so much chosen plaintext (which is why DES wasn't immediately deprecated once Biham and Shamir published their paper). But it is a break nonetheless.
In general, people 'bother' with cryptanalysis because they want to evaluate the ciphers they use to protect lives and billions of dollars against all known attacks in order to understand how secure they are. If you can show (for a cipher with sufficiently large parameters like key-size and block-size) that nothing beats generic attacks (i.e. that there are no 'breaks') then that gives people confidence in the security of the cipher.
-
$\begingroup$ Billions of dollars? The US market alone (stocks + Forex) is over $7 trillion, per day! $\endgroup$ Jul 1, 2016 at 22:50
-
$\begingroup$ @RichieFrame - trillions are merely a certain number of billions. :-) $\endgroup$– J.D.Jul 1, 2016 at 23:00
$\begingroup$
$\endgroup$
Anyone who begins to develop an attack on primitive XYZ is probably not aware beforehand of what the computational complexity of their attack will turn out to be. Then, the attack is developed and computational complexity becomes known. Just because DES isn't broken by the attack in question does not mean no other ciphers will be.
And just because the complexity requirements might subjectively appear to be unrealistic, does not mean nobody else will be interested in your research.
Nowadays, I wouldn't be surprised (but certainly don't have statistical proof) if most differential attacks are during the research/development phase of a primitives life cycle, as opposed to an in the wild attack on actual protected data.
The chosen-plaintext scenario doesn't necessarily apply in all use cases, in the same way side-channel attacks and differential power analysis might not be a realistic threat model. However, as a cipher designer, you want your primitive to be secure in all situations where it could be used.
I wonder if your question is more about how realistic a chosen-plaintext scenario is, as opposed to the effectiveness of differential cryptanalysis specifically.
Crypto is about providing certainty to those who are authorized, and uncertainty for everyone else, regardless of who-tries-what-when-and-how. Given two ciphers, one that is resistant to chosen plaintext attacks, and a second one that is not, people will prefer the former.
It does not matter if nobody was ever going to attack some given encrypted data to begin with, because proofs of security usually assume practically omnipotent adversaries that are interested in breaking everything possible.
It makes a lot stronger proof to assume your adversary is hostile and practically omnipotent, compared to an adversary that is incompetent and not interested in attacking your information to begin with.
$\begingroup$
$\endgroup$
Also, differential attacks can be useful in the design of a cipher to strike the right balance between performance (e.g., number of rounds) and security. Let's assume DES initially had 10 rounds and the designers performed a differential attack on that setup. They would have found that 10 rounds were not buying enough resistance against that type of attack and added a few more rounds.
