[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