Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I've been going through DES, and I find that most of the blocks simply Reshuffle the input, which may be termed as "Cross Wiring". This include IP, IP-1, PC-1, PC-2 and even Expansion (although this seems to be more useful than the rest).
Why does DES do it? Is it for a reason, or just for fun maybe?
Permutations IP and PC-1 are near-transpositions, and play no cryptographic role. IP-1 is simply IP reversed. The best theory about why they are here is: as a technical by-product of the 8-bit interface used by early DES ICs, translated into the same formalism as the rest when writing the DES standard. They make wiring of hardware implementations simple when using eight 8-bit shift registers for data input and output, and eight 7-bit shift registers for key input (the later being re-grouped as two 28-bit shift registers after key loading).
Expansion E (from 32 to 48 bits, before the XOR with keys bits leading to S-boxes inputs) is very regular; it is here to compensate the S-boxes going from 6 to 4 bits. That geometry of S-boxes is itself a compromise between security and silicon area.
Permutation P (of 32 bits, at the output of S-boxes) is quite irregular, plays a central role in the diffusion from round to round, and was carefully optimized for that purpose (the combination of E, P, and the S-tables makes DES quite resistant to differential cryptanalysis). Notice that the additional silicon cost of such arbitrary permutation is low (especially when compared to alternatives giving some diffusion, and considering 1970's technology). In software, E has a sizable performance cost, especially on less than 32-bit CPUs: typical implementations use S-tables with 32-bit wide output, requiring either more memory than would otherwise be needed, or a masking operation per S-box, with 8 of these per round.
Permutation PC-2 (between key shift registers and the XOR before the S-boxes) plays a role in making the 16 DES subkeys "good", that is without too much exploitable correlation from one round to another. It is such that the 8 bits (out of the 56 actually used key bits) that are not used in a round subkey, are used in the subkey for the next round. Other than that, it is rather arbitrary, as far as I know.
I do not buy the theory that the permutations in DES have been introduced for the purpose of making software implementations slow: IP, IP-1, and PC-1 represent a small fraction of a software DES computation time, since they are outside of the round loop; and are not arbitrary, so much that some software implementations of these three tables take advantage of the fact that they are near-transpositions. Other bit massaging is either as simple as can be (E), or with a cryptographic role: a major one for P; a lesser one for PC-2, but the later introduces very low software overhead for bulk encryption. Further, I know no historical evidence supporting that theory; when evidence has already surfaced (see end of this answer) supporting that the 56-bit key size of DES was deliberately introduced to weaken it, and result from a compromise between the designers willing to have 64 or 128 bits (as in some Lucifer variants); and US authorities pushing for 48 bits.
Inside each round, DES has a permutation that is used for diffusion and is crucial for security. However, you rightly point out that the initial and final permutations on the block of input/output and on the key have no effect whatsoever on security. Formally, it's not difficult to show that if you have an attack on DES without these initial and final permutations, then the attack also works when you do have.
So why does DES do this? Well, we can only guess. However, the assumption in the cryptographic community is that permutations are really really fast in hardware and really really slow in software. (In fact, a good percentage of the encryption time in software goes on these permutations. In hardware, it's just a matter of moving wires so it's almost zero cost.) This therefore slows down brute force search in software, relative to what can be done in hardware.
Why was this done? My guess is that this gives an advantage to certain very large organizations who have the resources to build special-purpose hardware. One such organization was instrumental in making DES secure (helping in the design of the S-boxes). However, they also pushed to make the key 56 bits long instead of 64 bits long. I guess that by making the software implementation slow, they felt that this could enough security (since most of the world would only have software) while enabling them to do brute force searches.
One could of course go for a less exciting theory which is that this was an additional level of security to slow down brute force searches in the future. But, I don't really buy it since if this was the concern at the time, then a bigger key would have been the right solution.
There's a paper by Miles E. Smid and Dennis K. Branstad of the National Institute of Standards and Technology (NIST) entitled The Data Encryption Standard Past and Future, first appearing in Proceedings of the IEEE, vol. 76, no. 5, pp. 550-559, May 1988 (and not copyright eligible as a a U.S. government work), which makes the distinction between Basic standards, Interoperability standards, Interface standards and Implementation standards and points out that the DES is an interoperability standard. It describes how to interconnect an 8 bit interface to the Initial Permutation, Inverse Initial Permutation and Permuted Choice 1 as well describing which bits are association in time ordered hardware operations.
Note this is excerpted from an answer that shows Permuted Choice 1 is only 8 wires in hardware.
IP and IP-1 can be shown to be similarly as 8 wires:
