On Permutation Operations in Cipher Design∗Ruby B. Lee, Z. J. Shi and Y. L. YinPrinceton UniversityDepartment of Electrical EngineeringB-218, Engineering QuadranglePrinceton, NJ 08544, U.S.A.Email: {rblee,zshi,yyin}@princeton.eduRonald L. RivestM.I.T.CSAIL545 Technology SquareCambridge, MA 02139, U.S.A.Email: [email protected]. RobshawInformation Security GroupRoyal HollowayUniversity of LondonEgham, Surrey, TW20 0EX, U.K.Email: [email protected] and emerging applications can change the mix ofoperations commonly used within computer architectures.It is sometimes surprising when instruction-set architecture(ISA) innovations intended for one purpose are used forother (initially unintended) purposes. This paper consid-ers recent proposals for the processor support of familiesof bit-level permutations. From a processor architecturepoint of view, the ability to support very fast bit-level per-mutations may be viewed as a further validation of the ba-sic word-orientation of processors, and their ability to sup-port next-generation secure multimedia processing. How-ever, bitwise permutations are also fundamental operationsin many cryptographic primitives and we discuss the suit-ability of these new operations for cryptographic purposes.1. IntroductionTo support new user requirements such as digital mul-timedia processing and secure information processing, thebasic operations supported within new generation proces-sors might evolve. For a general-purpose microprocessor, itis desirable that any added instructions have multiple uses,rather than being specific to only one algorithm or to oneapplication. Since secure communications and networkinghave becomecritical features of many applications, it wouldseem to be advantageous for the architectural and crypto-graphic communities to explore the following questions.Are there instruction-set architecture (ISA) innovations thatmay occur in a widespread way that might also be used ben-eficially in the design of cryptographic algorithms? Alter-natively, are there desirable instructions, perhaps motivatedby the design of cryptographic algorithms, that might alsobe useful for other emerging applications? To begin explor-ing these questions, this paper examines recently-proposed∗This work was supported in part by NSF CCR-0105677.bit permutation operations from the perspective of cipherdesign and cryptanalysis. In addition to studying the cryp-tographic properties of such permutation operations in iso-lation, we consider their role in the design of new ciphers.The contributions of this paper are as follows. We exam-ine the cryptographic properties of bit-level permutationsin the construction of new ciphers or in strengthening ex-isting ciphers. In particular, we study the cryptographicproperties of the group operation GRP [13, 23], as well asOMFLIP [13, 27] which were recently identified for possi-ble inclusion in future processor architectures. We considerthe properties of GRP and OMFLIP and consider how theirinclusion within a cryptographic design might change theproperties of the scheme. As a detailed example, we con-sider the implications of incorporating the GRP operationinto a block cipher and discuss some of the issues that arise.Provided care is taken, it may be possible for the supportof new operations to lead to new designs offering higherperformance and reduced energy consumption; somethingwhich would be particularly important for constrained envi-ronments like hand-held devices. In Section 2, we motivatethe study of permutation operations from both an architec-tural and cryptographic viewpoint. In Section 3, we pro-vide our design goals and detailed definitions of bit permu-tation operations. We also give results on the implementa-tion complexity of GRP. In Section 5, we analyze the cryp-tographic properties of GRP and, as an example, in Sec-tion 6.2 we explore how one might use GRP in a variant ofthe block cipher RC5 [20]. Section 7 concludes the paper.2. Motivation for new permutation operationsBit-level permutation operations are very important fromboth an architectural and cryptographic point of view.Architecturally, the ability to support very fast bit-levelpermutations may be the next step in the evolution of word-oriented processors to support new multimedia and secureinformation processing workloads. Bit level computationis used in Huffman encoding and decoding, for example,and general-purpose processors are optimized for word-oriented computation. Hence, their instruction set architec-ture (ISA) provides limited support for the manipulation ofdata items smaller than a word. Currently, only simple bit-level operations like logical operations and shifts are im-plemented in microprocessors. For multimedia processing,processor architectures have already incorporated the con-cept of subword parallelism [11, 12] where subwords aretypically 8-bit pixels or 16-bit audio samples. A subword-parallel instruction performs the same operation on multi-ple pieces of data (subwords) packed in one or more reg-isters [11]. Subword-parallel arithmetic operations can ef-ficiently exploit the data parallelism in processing images,video, graphics and audio. Subword-parallel instructions—first introduced to accelerate multimedia in PA-RISC mi-croprocessors [11, 12]—have now been added to all mi-croprocessors [6, 8, 11, 12, 18, 19]. These ISA additionshave swept the microprocessor industry in a matter of fiveyears, demonstrating that new architectural features will beadded to processors if they provide significant performanceor other advantages at a very low cost. Subword permuta-tion operations are often necessary to rearrange subwordsinto proper positions in registers so that subsequent oper-ations can be applied to all subwords in parallel. As wedecrease the size of the subword, we increase the difficultyof achieving all possible permutations since the number ofitems to be permuted increases significantly. Nevertheless,recent work [13, 23, 26, 27] has examined architectural so-lutions that can achieve any arbitrary permutation of bothsingle-bit and multi-bit subwords packed in a register.Cryptographically, bit-level operations are useful in thedesign of many algorithms, particularly block ciphers,stream ciphers, and hash functions. The design of the blockcipher DES [16] is an important landmark in this regard.The security of many of these algorithms relies on whatShannon termed confusion and diffusion [22] which