DES revisited, yet again

Being congenitally stupid means, till now, I’ve been unable to see something simple about DES – even though a 30 year old book on the topic and the subject in in particular outlined the point completely and obviously. I was bamboozled by what all the modern American textbook-grade presentations on crypto theory of DES say, intending to divert attention (from what the likes of the 1970s-era original book were saying).

Davis and co showed that the E and P functions in the DES “Computation-graph representation” use a cute “compact-coding method ” to specify how output bits from such as s-box #1 flow to the inputs of other sboxes. Three “wheels” – represented by the method as the E and P functions – specify the “program code” orchestrating this flow.

Its now obvious that to achieve the goal that there be a path from any one sbox to all the others in at most 3 steps on the “cayley graph random walk” (or 3 rounds of DES, equivalently) we see how the wirings of the these virtual-specification-wheels ensure that from 1 node two generators (graph edge or wirings on 1950-era wheels) get you to, guess what, 2 nodes; each of which also have two generators, which mean our reach (after 2 walks) is 4 nodes; which after 2 further generator-induced edge walks gets us in 3 hops to all 8 sboxes. That’s each and every one of the 8 sboxes, not just some 8 boxes from the set of 8.

So, the notion of “expansion” in 3-rounds can and should be separated from the “representation” in such virtual wheels of the “expansion inducer circuit” from its function – which we know to be about helping induce the “avalanche effect”. That is, for 2 plaintexts differing by 1 bit, after 3 rounds the difference in the ciphertext of the two halves of the round output will be ~half the distance of the desired codebook (i.e. 32 bits), on average.

Lets assume that the expansion can be related to expander graphs, in the sense that each of the 3 virtual wheels relate to the zig-zag product, where the 2 outer virtual-wheels of EP correspond to the zig and the zag walks on the 2-instances of the smaller graph involved in the semi-direct product with the larger graph, corresponding to the middle virtual-wheel. The latter is responsible for conducting entropy induced by zig into the virtual channel (if capacity exists), at which point zag adds further uncertainty, possibly redundantly.

Now lets recall the special edge construction of the middle virtual-wheel, in DES EP. Its two sub-wheel overlayed, each laid out for either the even or odd numbers. There are 4 hamiltonian circuits, 2 per parity. Considering each in turn, the first simply goes around the numbers, from 2, 4, 6….  (or 1,3,5… in the other parity) The second goes between nodes, nominally causing a wire to crossing the mid-section of the wheel (physically) rather than go to a neighbor, along the wheels edge. However, unlike the zig and zag wheels, these “wire-crossings” can actually be parallel to those writes going along the wheel edge between neighbors. Flows are allowed to pass between these systems at node 4, allowing a n-flow presumably to randomly pass, 1 in eight walks, between the parities. OF course, this all feels very much like Turings “alternating group” application, as relevant of course to expander graphs on symmetric groups whose analysis was (secretly) perfected (as CI) by those in the 1950s crypto world doing wheels-based crypto.

Finally, lets view the two halves of the DES state (R and L) each as 32-dimensional qubits, subject to a unitary operation – conditional NOT (implementing generalized xor) from the quantum boolean network theory (vs binary boolean network theory, of classical teaching). Rather than think in terms of a classical compression function acting on L to produce a mask for R (and vice versa in the next round), we think of the R as providing the generalized-quantum xor mask that conditions the quantum CNOT gate (in 32d). Of course, the net result is the xor of the two. But now we are “thinking” and doing (component-level) workings in 32d outer-product (tensored) configuration space. This if course gets to the heart of the “feistel circuit”.

Now we also have to remember from quantum circuit theory – reduced to what can be expressed on enigma-era wheel wiring “calculators” – is that 3 conditional-NOTs suitably oriented, in much the same manner as zig-zag product works and conjugation works, specify a swap operation, thinking of the swap as being a nominal relabeling of the sboxes’ inputs and output wires

Now we see a clear link to expander theory. Assuming the parameters of the expander graph are such that the second eigen value is only 1 dit per (32) component of the 32d-qbit away from eigenvalue 1 (i.e. d, or degree, normalized) I can see how reaching a limiting distribution, or filling of entropy capacity, after 3 rounds, say, gets us to quotient space in which most cosets have zero as their distribution, leaving 1 that is continuous, transitive and for which a 1 bit change in inputs induces the conjugate to be in the coset – which represents a certain weight range around 32, with mean at 32.

Hmm. The last part is a bit woolly.



Computer Programmer who often does network administration with focus on security servers. Very strong in Microsoft Azure cloud!
This entry was posted in DES. Bookmark the permalink.