a little year-end paper on DES

It’s a time for a fourth-year of study “term paper”, given our 5-year long course of self-study of cryptography and cryptanalysis. For the first time we can outline a comprehensive theoretical model of DES, derived from the history of rotor machines. Furthermore, we can generalize the theory beyond rotors and onto quantum walks that give us a glimpse of how non-DES ciphers leverage computational graphs. These abide by the same design principles as DES but no longer necessarily showcase the older world based on earlier rotors and wheel wiring approaches to representing the theory.

We get to organize the thinking in terms of the defenses DES et al have to mount.

First and foremost, we can justify why DES has multiple rounds. Simply put, we have to drive the probability of guessing to a low level, requiring a simple product algebra. As one one the most brutish defenses, one is creating a large search space that demands time from the attacker with no knowledge whatsoever.

Next, we have to address linear cryptanalysis by engineering a notion of phase space in which all points (bit flows) are at a maximized minimum distance from all constant functions. This iterative computation requires the theory of expander graphs and zig zag products, using 3 feistel rounds.

Building on expander graphs, we have seen how subkeys parameterize the generation of a sequence of expander graphs forming a particular  family. The point is (a) to protect the fixed algorithm by indicating that it can rewrite itself, and (b) to let each round of expansion drive the pairwise distance between eigenvalues generating the graphs progressively to that final set of pairwise distances between the generators that induces maximization of the minimum distance of flows/points in phase space. The sequence of (self-generated!) expander graphs has converged to a limit, that is; or better that the resulting fluxion field has converged as a result of the expansion process.

The theory of DES is dominated by the world of depth-based cryptanalysis, since countering the use of entropy bases to analyze and predict information flow found in depth-analysis is the foundation of differential cryptanalysis countermeasures. The latter has two goals: prevent bits in keys and plaintexts (or ciphertexts) from predicting the values of neighbors by trying to excise all differentials; and use a mini-Viterbi process within the cipher in any case to deny an assumed Viterbi belief-propagation based cryptanalytical process from using min/max to search out paths based on any residual differentials. To do this we need 3 relationships between the first zig and its hyphen step, and then that hyphen step and then next zag step (each of those handoffs being two successive feistel rounds with a intervening anti-symmetry inducing swap). The point of this mini-viterbi “reactor” is to, on the first step be confusing half the forward flows, whereas on the second step be confusing the reverse belief flows, in order to formulate a unique entropy basis which has got close of the shannon limit, maximizing the improbability and leaving little gap for cryptanalysis to latch onto. In quantum uncertainty terms, the improbability comes from the fact that  the forward and reverse create changes of basis, each being conjugate to each other and thus “refining” the improbability (in the “reactor”)

What is nice about this theoretical perspective is that holds both for DES, looked at as a coded set of rotor wheels, and for PES. We see now now the correct design of sboxes and permutation encode the cayley graphs that give the mechanism for doing the above. And we see how that method is but a representation of a general theory of quantum walking that has an entirely mathematical form, though most simply as in quantum mechanism where wave functions themselves evolve. If one dumps DES and consider and more modern computational graph such as that of PES, one sees how the unitary gate acts to compute several coin flipper operators, for each weight class, in much the same way that in the rotor era different degrees (wiring fanouts) produced a walk in which its exponentially difficult to actually walk one one end of the space to the other, without knowledge of the key due to absorption properties of the design driving walks into the center of the space, and away from the solution.


About home_pw

Computer Programmer who often does network administration with focus on security servers. Sometimes plays at slot machine programming.
This entry was posted in DES. Bookmark the permalink.