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 _______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
