Bit permutation instructions: Architecture, implementation, and cryptographic properties

Bit permutation operations are interesting and important from both cryptographic and architectural points of view. Cryptographically, bit-level permutations naturally provide certain effects which are not easily obtained through word-level operations. Architecturally, the ability to support very fast bit permutations may be the next step in the evolution of word-oriented processors to support new multimedia and secure information processing workloads, which frequently manipulate data items smaller than a word. Any new instructions introduced into a general-purpose processor should ideally be useful in many applications; and their impact on the cycle time, and datapath and control complexity evaluated in terms of cost versus benefit.; This thesis investigates the benefits and cost of architectural support for fast bit permutations in programmable processors. The new permutation methods presented in the thesis reduce the number of instructions required to permute n bits from O(n) to O(log₂(n)). This both accelerates existing block ciphers and enables new ciphers that use arbitrary data-dependent permutations. The thesis also demonstrates that the bit permutation instructions can be used to achieve significant speedup in other applications, such as sorting bytes. The cost of the bit permutation instructions is studied in terms of their implementation complexity and their impact on a processor's cycle time.; The cryptographic properties of the bit permutation instructions are studied with respect to the two most effective cryptanalytic attacks, linear and differential cryptanalysis. The results show that the new bit permutation operations can enhance the cryptographic strength of the round function in block ciphers, so fewer rounds can achieve the same level of security. This leads to significant improvements in performance and energy consumption.; This thesis is a detailed example of a more general exploration of new instruction-set architecture features motivated by cryptographic algorithms, as well as of architectural features occurring for other reasons, e.g., multimedia, that may influence the design of cryptographic algorithms. We hope to have initiated a continuing dialog between cipher designers and processor architects. Future research in this direction will lead to more architectural and algorithmic innovations helpful for achieving pervasive security in information processing, networking, and storage.