Lightweight Cryptography for Security and Privacy

The last several years have witnessed a surge of activity in lightweight cryptographic design. Many lightweight block ciphers have been proposed, targeted mostly at hardware applications. Typically software performance has not been a priority, and consequently software performance for many of these algorithms is unexceptional. Simon and Speck are lightweight block cipher families developed by the U.S. National Security Agency for high performance in constrained hardware and software environments. In this paper, we discuss software performance and demonstrate how to achieve high performance implementations of Simon and Speck on the AVR family of 8-bit microcontrollers. Both ciphers compare favorably to other lightweight block ciphers on this platform. Indeed, Speck seems to have better overall performance than any existing block cipher — lightweight or not.

A generic way to design lightweight cryptographic primitives is to construct simple rounds using small nonlinear components such as 4\(\,\times \,\)4 S-boxes and use these iteratively (e.g., PRESENT [1] and SPONGENT [2]). In order to efficiently implement the primitive, efficient implementations of its internal components are needed. Multiplicative complexity of a function is the minimum number of AND gates required to implement it by a circuit over the basis (AND, XOR, NOT). It is known that multiplicative complexity is exponential in the number of input bits \(n\). Thus it came as a surprise that circuits for all \(65 536\) functions on four bits were found which used at most three AND gates [3]. In this paper, we verify this result and extend it to five-variable Boolean functions. We show that the multiplicative complexity of a Boolean function with five variables is at most four.

SIMON is a recent, light-weight block cipher developed by NSA. Previous work on SIMON shows that it is a very promising alternative of AES for resource-constrained platforms. While SIMON offers a range of block sizes and key lengths, a straightforward implementation would select fixed values in order to achieve a compact design. In contrast, we propose a flexible hardware architecture on FPGAs that still preserves the compactness of SIMON. The proposed implementation can execute all configurations of SIMON, and thus provides a versatile architecture that enables adaptive security using a variable key-size. Moreover, it also reduces the inefficiency of encrypting slightly longer messages by supporting a variable block-size. The implementation results show that the proposed architecture occupies 90 and 32 slices on Spartan-3 and Spartan-6 FPGAs, respectively. To our best knowledge, these area results are smaller than other block ciphers of similar security level. Furthermore, we also quantify the cost of flexibility and show the trade-off between the security level, throughput and area.

This paper explores state-of-the-art software implementations of “size-minimum” AES on low-end microcontrollers. In embedded environments, reducing memory size often has priority over achieving faster speed. Some recent lightweight block ciphers can be implemented in 200 to 300 ROM bytes, while the smallest software implementation of AES including key scheduling, encryption and decryption is, as far as we know, around 1 K ROM bytes.

The first purpose of this study is to see how small AES could be. To do this, we aggressively minimize code and data size of AES by introducing a ring multiplication for computing the S-box without any lookup table, a compact algorithm for embedding MixColumns into InvMixColumns, and a tiny loop for processing AddRoundKey, ShiftRows and SubBytes at the same time. As a result, we achieve a 192-byte AES encryption-only code and a 326-byte AES encryption-decryption code on the RL78 microcontroller. We also show that an AES-GCM core can be implemented in 429 bytes on the same microcontroller. These codes include on-the-fly key scheduling to minimize RAM size and their running time is independent of secret information, i.e. timing-attack resistant.

The second purpose of this research is to see what processor hardware architecture is suitable for implementing lightweight ciphers from a minimalist point of view. A simple-looking algorithm often results in very different size and speed figures on different low-end microcontrollers in practice, even if their instruction sets consist of similar primitive operations. We show concrete code examples implemented on four low-end microcontrollers, RL78, ATtiny, Cortex-M0 and MSP430 to demonstrate that slight differences of processor hardware, such as carry flag treatment and branch timing, significantly affect size and speed of AES.

A differential attack tries to capture the round keys corresponding to the S-boxes activated by a differential. In this work, we show that for a fixed output difference of an S-box, it may not be possible to distinguish the guessed keys that have a specific difference. We introduce these differences as differential factors. Existence of differential factors can reduce the time complexity of differential attacks and as an example we show that the \(10\), \(11\), and \(12\)-round differential-linear attacks of Dunkelman et al. on Serpent can actually be performed with time complexities reduced by a factor of 4, 4, and 8, respectively.

In this work, we introduce fault attacks on PRESENT with faulty ciphertexts-only. In contrast to current differential fault attacks on PRESENT, which are mostly chosen-plaintext attacks, our fault attacks do not require the knowledge of the plaintexts to recover the secret key. This is a typical scenario when plaintexts are not easily accessible for the attacker, like in the case of smart devices for the upcoming Internet-of-Things (IoT) era where input data are mostly assembled within the cryptographic device, or when protocol-level countermeasures are deployed to prevent chosen-plaintext attacks explicitly. Our attacks work under the assumption that the attacker is able to bias the (nibble-wise) distribution of intermediate states in the final rounds of PRESENT by careful fault injections. To support our statements, we provide a detailed simulation analysis to estimate the practical attack complexities of (faulty) ciphertext-only fault attacks on PRESENT-80 discussing different fault injection scenarios. In the best case analysis (worst-case security scenario), only two faulty ciphertexts and negligible computational time are required to recover the entire secret key.

Recently it was observed that for a particular nonzero input difference to an S-Box, some bits in all the corresponding output differences may remain invariant. These specific invariant bits are called undisturbed bits. Undisturbed bits can also be seen as truncated differentials with probability \(1\) for an S-Box. The existence of undisturbed bits was found in the S-Box of Present and its inverse. A 13-round improbable differential attack on Present was provided by Tezcan and without using the undisturbed bits in the S-Box an attack of this type can only reach 7 rounds. Although the observation and the cryptanalytic application of undisturbed bits are given, their relation with other properties of an S-Box remain unknown. This paper presents some results on mathematical properties of S-Boxes having undisturbed bits. We show that an S-Box has undisturbed bits if any of its coordinate functions has a nontrivial linear structure. The relation of undisturbed bits with other cryptanalytic tools such as difference distribution table (DDT) and linear approximation table (LAT) are also given. We show that autocorrelation table is proven to be a more useful tool, compared to DDT, to obtain all nonzero input differences that yield undisturbed bits. Autocorrelation table can then be viewed as a counterpart of DDT for truncated differential cryptanalysis. Given an \(n \times m\) balanced S-Box, we state that the S-Box has undisturbed bits whenever the degree of any of its coordinate function is quadratic.

In this paper, we propose a modified approach for the basic meet-in-the-middle attack which we call differential sieving for 2-step matching. This technique improves the scope of the basic meet in the middle attack by providing means to extend the matching point for an extra round through differential matching and hence the overall number of the attacked rounds is extended. Our approach starts by first reducing the candidate matching space through differential matching, then the remaining candidates are further filtered by examining non shared key bits for partial state matching. This 2-step matching reduces the total matching probability and accordingly the number of remaining candidate keys that need to be retested is minimized. We apply our technique to the light weight block cipher LBlock and present a two known plaintexts attack on the fifteen round reduced cipher. Moreover, we combine our technique with short restricted bicliques and present a chosen plaintext attack on Lblock reduced to eighteen rounds.

SIMON is a family of lightweight block ciphers designed by the U.S National Security Agency in 2013. In this paper, we analyze the resistance of the SIMON family of block ciphers against the recent match box meet-in-the-middle attack which was proposed in FSE 2014. Our attack particularly exploits the weaknesses of the linear key schedules of SIMON. Since the data available to the adversary is rather limited in many concrete applications, it is worthwhile to assess the security of SIMON against such low-data attacks.

Yoking-proof in a Radio Frequency Identification (RFID) system provides the evidence that two RFID tags are simultaneously scanned by the RFID reader. Though there are numerous yoking-proof protocols, vulnerabilities related to security and privacy are found in many prior works. We introduce a new security definition that covers the man-in-the-middle (MIM) attack, and a privacy definition based on an indistinguishability framework. We also provide a simple construction of a provably secure offline yoking-proof protocol based on the pseudorandom function.