6
$\begingroup$

I understand from the literature that the DES S-boxes were very carefully designed with the process involving exhaustive search, trial and error, and an anticipation (by 15 years) of "differential cryptanalysis".

The AES S-box on the other hand is given by a relatively simple mathematical formula (inversion in a finite field).

How can it be that this is "equally secure" ? Resorting to inversion looks like the next thing that comes to mind when something nonlinear is sought, but what about all the other criteria including possibly secret ones ?

$\endgroup$
  • $\begingroup$ I don't understand your question. $\endgroup$ – Biv Apr 3 '17 at 14:33
  • 4
    $\begingroup$ "How can it be that this is "equally secure" ? They aren't, the AES sbox (in the context of AES) is more secure than the DES sboxes (in the context of DES); DES is known to have a weakness against linear cryptanalysis, which AES does not. $\endgroup$ – poncho Apr 3 '17 at 15:06
10
$\begingroup$

A good source for this kind of questions is the book The Design of Rijndael by Joan Daemen and Vincent Rijmen. On page 35 they write about their choice for the used S-box $S_{RD}$:

Design criteria for $S_{RD}$. We have applied the following design criteria for $S_{RD}$, appearing in order of importance:

  1. Non-linearity.

    a) Correlation. The maximum input-output correlation amplitude must be as small as possible.

    b) Difference propagation probability. The maximum difference propagation probability must be as small as possible.

  2. Algebraic complexity. The algebraic expression of $S_{RD}$ in $GF(2^8)$ has to be complex.

They then go on explaining that they chose one of the best alternatives for invertible S-boxes operating on bytes from Differentially uniform mappings for cryptography by K. Nyberg (Eurocrypt'93, LNCS 950).

One big difference between the times when the DES was designed and when the AES was chosen is that at the beginning of the 1970s not many scientific papers about crypto were published at all, whereas around 2000 a lot of theory already existed.

$\endgroup$
  • $\begingroup$ Hi, thank you for pointing me to the Rijndael book which is indeed a valuable source. However, I am not convinced by your (or rather their) answer. These kind of criteria are classic and I believe were also in the minds of the DES developers. This morning I had the idea for another answer, see below ... $\endgroup$ – Martin Hofmann Apr 4 '17 at 12:00
  • $\begingroup$ @MartinHofmann I would strongly urge you to reconsider your answer compared to itsme's answer. While wikipedia can be a good starting point in researching things, it isn't a reputable source. itsme has given a great answer addressing your question, and used a credible source in the process. $\endgroup$ – nonce Apr 4 '17 at 18:11
-1
$\begingroup$

This morning I saw that de.wikipedia.org writes that the short key length of DES was chosen deliberately because already in the 70s the NSA had sufficient computational power to break this cipher ("Es gibt die Vermutung, dass diese kleine Schlüssellänge absichtlich gewählt wurde, weil die NSA bereits in den 1970er-Jahren genug Rechnerkapazität besaß, um diese Verschlüsselung zu brechen."). Oddly, there is no citation.

Thus, perhaps the AES S-box is less "secure" (whatever that means exactly) than the DES S-box but that doesn't really matter because AES has such long keys.

The S-boxes of DES, OTOH, had to be crafted in such an elaborate way that no attacks other than brute force are possible given the current state-of-the-art. This then would allow the NSA with their exceptional computing power to break the cipher by exhaustive search if they really needed to but nobody else could possibly pull that off (at the time!). Any other backdoor, based on some deliberately (or accidentally) injected weakness would be likely to be found by other smart people after some time and would have resulted in a practically feasible attack due to the small key length and hence small safety margin of DES.

The existing attacks on AES (as yet not completely confirmed) on the other hand, even if they shave off 20 or so bits of key size do not result in any practical weakness.

$\endgroup$
  • 2
    $\begingroup$ "Thus, perhaps the AES S-box is less "secure" (whatever that means exactly) than the DES S-box" - We know how to measure the security of an s-box against (known) cryptanalysis. We are not guessing/hoping about the security of the two mappings. We can quantify their exact differences (though they are different sizes, so a comparison is not 100% straight-forward). A big key is there to thwart brute force, and has literally no effect in regards to improving security against differential cryptanalysis (using xor differences with a xor key addition layer, anyways). $\endgroup$ – Ella Rose Apr 4 '17 at 15:18
  • 2
    $\begingroup$ "The S-boxes of DES, OTOH, had to be crafted in such an elaborate way that no attacks other than brute force are possible given the current state-of-the-art." This is not true; DES can be broken by linear cryptanalysis because of the s-box; AES resists this attack better because of the s-box. $\endgroup$ – Ella Rose Apr 4 '17 at 15:18
  • 2
    $\begingroup$ "...break the cipher by exhaustive search if they really needed to but nobody else could possibly pull that off (at the time!)" This is not true; In 1977, Diffie and Hellman proposed a machine costing an estimated US$20 million which could find a DES key in a single day. I apologize for leaving so many comments, but certain things needed to be addressed. I have left -1 on this point for the aforementioned reasons; Please consider providing links to source your claims in the future. $\endgroup$ – Ella Rose Apr 4 '17 at 15:19
  • $\begingroup$ I did refer to de.wikipedia.org as a "source". Admittedly, the claim in de.wikipedia.org is itself not sourced. $\endgroup$ – Martin Hofmann Apr 4 '17 at 15:37
  • 1
    $\begingroup$ I don't know what you mean by unconfirmed attacks on AES. I have a feeling the attacks you mention on AES-192 and AES-256 are the related key attacks; If so, the attack model is the related key model, which is completely unrealistic and not really a break against the confidentiality of the cipher. Either way, I disagree with the factual truth of certain points that you made, for reasons that I made explicit. I was explaining why I voted -1; I did my best to link to my reasoning for why I disagree. If my complaints are unwarranted, the -1 vote will be offset by other users.... $\endgroup$ – Ella Rose Apr 4 '17 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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