One defining trend of this century’s IT landscape will be the extensive deployment of tiny computing devices. Not only will these devices feature routinely in consumer items, but they will form an integral part of a pervasive — and unseen
— communication infrastructure. It is already recognized that such deployments bring a range of very particular security risks. Yet at the same time the cryptographic solutions, and particularly the cryptographic primitives, we have at hand are unsatisfactory for extremely resource-constrained environments.
In this paper, we propose a new hardware-optimized block cipher that has been carefully designed with area and power constraints uppermost in our mind. Yet, at the same time, we have tried to avoid a compromise in security. In achieving this we have looked back at the pioneering work embodied in the DES and complemented this with features from the AES finalist candidate Serpent which demonstrated excellent performance in hardware.
At this point, it would be reasonable to ask why we might want to design a new block cipher. After all, it has become an “accepted” fact that stream ciphers are, potentially, more compact. Indeed, renewed efforts to understand the design of compact stream ciphers are underway with the eSTREAMproject and several promising proposals offer appealing performance profiles. But we note a couple of reasons why we might want to consider a compact block cipher. First, a block cipher is a versatile primitive and by running a block cipher in counter
mode (say) we get a stream cipher. But second, and perhaps more importantly, the art of block cipher design seems to be a little better understood than that of stream ciphers. For instance, while there is a rich theory underpinning the use of linear feedback shift registers it is not easy to combine these building blocks to give a secure proposal. We suspect that a carefully designed block cipher could be a less risky undertaking than a newly designed stream cipher. Thus, we feel that a block cipher that requires similar hardware resources as a compact stream cipher could be of considerable interest.
It is important to realize that in developing a new block cipher, particularly one with aggressive performance characteristics, we are not just looking for innovative implementation. Rather, the design and implementation of the cipher go hand-in-hand and this has revealed several fundamental limits and inherent contradictions. For instance, a given security level places lower bounds on the block length and key length. Just processing a 64-bit state with an 80-bit key places fundamental lower limits on the amount of space we require. We also observe that hardware implementation — particularly compact hardware implementation — favors repetition. Even minor variations can have an unfortunate effect on the space required for implementation. Yet, at the same time, the cryptanalyst also favors repetition and seeks mathematical structures that propagate easily across many rounds. How much simple, the repetitive structure can we include without compromising its security?
In this paper, we describe the compact block cipher1 present. After a brief
survey of the existing literature, the rest of the paper is organized in a standard way. the present is described in Section 3 with the design decisions described in Section 4. The security analysis follows in Section 5 along with detailed performance analysis in Section 6. We close the paper with our conclusions.
While there is a growing body of work on low-cost cryptography, the number of papers dealing with ultra-lightweight ciphers is surprisingly limited. Since our focus is on algorithm design we won’t refer to work on low-cost communication and authentication protocols. Some of the most extensive work on compact implementation is currently taking place within the stream project. As part of that initiative, new stream ciphers suitable for efficient hardware implementation have been proposed. While this work is ongoing, some promising candidates are emerging. While the trade-offs are complex, implementation papers suggest that around 1300-2600 gate equivalents (GE) would be required for the more compact ciphers within the eSTREAM project.
With regards to block ciphers, it is well-known that DES was designed with hardware efficiency in mind. Given the very limited state of semiconductor circuits in the early 1970s, it is not surprising that DES possesses very competitive implementation properties. Work on DES reveals an implementation of around 3000 GE while a serialized implementation can be realized with around 2300 GE. The key length of DES limits its usefulness in many applications and makes proposals such as DESXL (2168 GE) of some considerable interest.
For modern block ciphers, the landmark paper gives a very thorough analysis of a low-cost implementation of the AES. However, the resources required for this cipher are around 3600 GE, which is an indirect consequence of the fact that Rijndael was designed for software efficiency on 8- and 32- bit processors. Implementation requirements for the Tiny Encryption Algorithm tea are not known, but a crude estimate is that tea needs at least 2100 GE and xtea needs2 at least 2000 GE. Four dedicated proposals for low-cost implementation are Crypton, hight, sea, and cgen, though the latter is not primarily intended as a block cipher. Crypton has a precise hardware assessment and requires 2949 GE, hight requires around 3000 GE while sea with parameters comparable to present requires around 2280 GE.