[cryptography] DES history

Marcus Brinkmann marcus.brinkmann at ruhr-uni-bochum.de
Mon May 5 16:37:48 EDT 2014


On 05/05/2014 09:08 PM, Givon Zirkind wrote:
> A question about DES.  Did anyone ever try & map or graph the routes
> through the S-boxes?  I mean pictorially.  Do the routes produce some
> kind of wave or path, that have (or have not) relationships with the
> other routes?

This is a vague question, but here is a somewhat specific answer that 
may entirely miss what you are asking.

Any wave or path in the output would suggest (to me anyway) that linear 
pieces of the input are mapped to more or less linear pieces in the 
output (because any "curve" is just a number of connected straight 
"lines", as far as these concepts transfer to discrete spaces).

Such dependencies in the S-Box would suggest a high linearity, which 
makes the cipher weak to differential cryptanalysis [1].  This is highly 
undesirable, and must be avoided.

It is well known that the DES S-Boxes were specifically designed (by the 
NSA, no less, back in the good ol' days) to protect against that attack.

This means that any trivial plotting of the DES S-Boxes should show a 
highly non-linear output dependency from the input.

As for the inter-dependencies between the different routes: S-Boxes (in 
general) can be pairwise equivalent modulo some trivial transformation 
(linear, affine, CCZ), and such equivalent could be plotted showing an 
interesting (in this case even linear, affine or CCZ) relationship.

You can find an analysis of the interdependency of the S-Boxes used in 
various ciphers in [2] "A Toolbox for Cryptanalysis: Linear and Affine 
Equivalence Algorithms" (Biryukov et al), Section 5.  Specifically, for 
(DES (Section 4.2, 5.3): "The algorithm showed that no affine 
equivalences exist between any pair of S-boxes, with the single 
exception of S4 with itself.", which was apparently already derived by 
"looking at patterns in the lookup table" in a 1976 paper by Hellman et 
al, "Results of an initial attempt to cryptanalyze the NBS Data 
En-cryption Standard".

I don't know (but also haven't checked) of any low-degree (quadratic, 
cubic) versions of the linear (or affine) analysis mentioned.

[1] http://en.wikipedia.org/wiki/Differential_cryptanalysis
[2] http://www.cosic.esat.kuleuven.be/publications/article-16.pdf

Does this answer your question?

Thanks,
Marcus




More information about the cryptography mailing list