Lightweight Cryptography - Cryptographic Engineering for a Pervasive World

Increasingly, everyday items are enhanced to pervasive devices by embedding computing power and their interconnection leads to Mark Weiser’s famous vision of ubiquitous computing (ubicomp), which is widely believed to be the next paradigm in information technology. The mass deployment of pervasive devices promises on the one hand many benefits (e.g. optimized supply-chains), but on the other hand, many foreseen applications are security sensitive (military, financial or automotive applications), not to mention possible privacy issues. Even worse, pervasive devices are deployed in a hostile environment, i.e. an adversary has physical access to or control over the devices, which enables the whole field of physical attacks. Not only the adversary model is different for ubicomp, but also its optimisation goals are significantly different from that of traditional application scenarios: high throughput is usually not an issue but power, energy and area are sparse resources. Due to the harsh cost constraints for ubicomp applications only the least required amount of computing power will be realized. If computing power is fixed and cost are variable, Moore’s Law leads to the paradox of an increasing demand for lightweight solutions. In this Thesis different approaches are followed to investigate new lightweight cryptographic designs for block ciphers, hash functions and asymmetric identification schemes. A strong focus is put on lightweight hardware implementations that require as few area (measured in Gate Equivalents (GE)) as possible. We start by scrutinizing the Data Encryption Standard (DES)—a standardized and well-investigated algorithm—and subsequently slightly modify it (yielding DESL) to decrease the area requirements. Then we start from scratch and design a complete new algorithm, called PRESENT, where we could build upon the results of the first step. A variety of implementation results of PRESENT—both in software and hardware—using different design strategies and different platforms is presented. Our serialized ASIC implementation (1, 000 GE) is the smallest published and enabled PRESENT to be considered as a suitable candidate for the upcoming ISO/IEC standard on lightweight cryptography (ISO/IEC JTC1 SC27 WG2). Inspired by these implementation results, we propose several lightweight hash functions that are based on PRESENT in Davies-Meyer-mode (DM-PRESENT-80, DM-PRESENT-128) and in Hirose-mode (H-PRESENT-128). For their security level of 64 (DM-PRESENT-80, DMPRESENT-128) and 128 bits (H-PRESENT-128) the implementation results are the smallest published. Finally, we use PRESENT in output feedback mode (OFB) as a pseudo-random number generator within the asymmetric identification scheme crypto-GPS. Its design trade-offs are discussed and the implementation results of different architectures (starting from 2, 181 GE) are backed with figures from a manufactured prototype ASIC. We conclude that block ciphers drew level with stream-ciphers with regard to low area requirements. Consequently, hash functions that are based on block ciphers can be implemented efficiently in hardware as well. Though it is not easy to obtain lightweight hash functions with a digest size of greater or equal to 160 bits. Given the required parameters, it is very unlikely that the NIST SHA-3 hash competition will lead to a lightweight approach. Hence, lightweight hash functions with a digest size of greater or equal to 160 bits remain an open research problem.