Triathlon of Lightweight Block Ciphers for the Internet of Things

in Journal of Cryptographic Engineering (2019), 9(3), 283-302

In this paper, we introduce a framework for the benchmarking of lightweight block ciphers on a multitude of embedded platforms. Our framework is able to evaluate the execution time, RAM footprint, as well ... [more ▼]

In this paper, we introduce a framework for the benchmarking of lightweight block ciphers on a multitude of embedded platforms. Our framework is able to evaluate the execution time, RAM footprint, as well as binary code size, and allows one to define a custom "figure of merit" according to which all evaluated candidates can be ranked. We used the framework to benchmark implementations of 19 lightweight ciphers, namely AES, Chaskey, Fantomas, HIGHT, LBlock, LEA, LED, Piccolo, PRESENT, PRIDE, PRINCE, RC5, RECTANGLE, RoadRunneR, Robin, Simon, SPARX, Speck, and TWINE, on three microcontroller platforms: 8-bit AVR, 16-bit MSP430, and 32-bit ARM. Our results bring some new insights into the question of how well these lightweight ciphers are suited to secure the Internet of things. The benchmarking framework provides cipher designers with an easy-to-use tool to compare new algorithms with the state of the art and allows standardization organizations to conduct a fair and consistent evaluation of a large number of candidates. [less ▲]

State of the Art in Lightweight Symmetric Cryptography

E-print/Working paper (2017)

Lightweight cryptography has been one of the ``hot topics'' in symmetric cryptography in the recent years. A huge number of lightweight algorithms have been published, standardized and/or used in ... [more ▼]

Lightweight cryptography has been one of the ``hot topics'' in symmetric cryptography in the recent years. A huge number of lightweight algorithms have been published, standardized and/or used in commercial products. In this paper, we discuss the different implementation constraints that a ``lightweight'' algorithm is usually designed to satisfy. We also present an extensive survey of all lightweight symmetric primitives we are aware of. It covers designs from the academic community, from government agencies and proprietary algorithms which were reverse-engineered or leaked. Relevant national (\nist{}...) and international (\textsc{iso/iec}...) standards are listed. We then discuss some trends we identified in the design of lightweight algorithms, namely the designers' preference for \arx{}-based and bitsliced-S-Box-based designs and simple key schedules. Finally, we argue that lightweight cryptography is too large a field and that it should be split into two related but distinct areas: \emph{ultra-lightweight} and \emph{IoT} cryptography. The former deals only with the smallest of devices for which a lower security level may be justified by the very harsh design constraints. The latter corresponds to low-power embedded processors for which the \aes{} and modern hash function are costly but which have to provide a high level security due to their greater connectivity. [less ▲]

Summary of an Open Discussion on IoT and Lightweight Cryptography

in Proceedings of Early Symmetric Crypto workshop, 2017 (2017, April)

This is a summary of the open discussion on IoT security and regulation which took place at the Early Symmetric Crypto (ESC) seminar. Participants have identified that IoT poses critical threat to ... [more ▼]

This is a summary of the open discussion on IoT security and regulation which took place at the Early Symmetric Crypto (ESC) seminar. Participants have identified that IoT poses critical threat to security and privacy. It was agreed that government regulation and dialogue of security researchers with engineers and manufacturers is necessary in order to find proper control mechanisms. [less ▲]

Design Strategies for ARX with Provable Bounds: SPARX and LAX

in Cheon, Jung Hee; Takagi, Tsuyoshi (Eds.) Advances in Cryptology --- ASIACRYPT 2016, 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I (2016, December)

We present, for the first time, a general strategy for designing ARX symmetric-key primitives with provable resistance against single-trail differential and linear cryptanalysis. The latter has been a ... [more ▼]

We present, for the first time, a general strategy for designing ARX symmetric-key primitives with provable resistance against single-trail differential and linear cryptanalysis. The latter has been a long standing open problem in the area of ARX design. The Wide-Trail design Strategy (WTS), that is at the basis of many S-box based ciphers, including the AES, is not suitable for ARX designs due to the lack of S-boxes in the latter. In this paper we address the mentioned limitation by proposing the Long-Trail design Strategy (LTS) -- a dual of the WTS that is applicable (but not limited) to ARX constructions. In contrast to the WTS, that prescribes the use of small and efficient S-boxes at the expense of heavy linear layers with strong mixing properties, the LTS advocates the use of large (ARX-based) S-Boxes together with sparse linear layers. With the help of the so-called long-trail argument, a designer can bound the maximum differential and linear probabilities for any number of rounds of a cipher built according to the LTS. To illustrate the effectiveness of the new strategy, we propose Sparx -- a family of ARX-based block ciphers designed according to the LTS. Sparx has 32-bit ARX-based S-boxes and has provable bounds against differential and linear cryptanalysis. In addition, Sparx is very efficient on a number of embedded platforms. Its optimized software implementation ranks in the top-6 of the most software-efficient ciphers along with Simon, Speck, Chaskey, LEA and RECTANGLE. As a second contribution we propose another strategy for designing ARX ciphers with provable properties, that is completely independent of the LTS. It is motivated by a challenge proposed earlier by Wallen and uses the differential properties of modular addition to minimize the maximum differential probability across multiple rounds of a cipher. A new primitive, called LAX is designed following those principles. LAX partly solves the Wallen challenge. [less ▲]

Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1

in Fischlin, Marc, Coron, Jean-Sébastien (Ed.) Advances in Cryptology – EUROCRYPT 2016 (2016, April 28)

The Russian Federation's standardization agency has recently published a hash function called Streebog and a 128-bit block cipher called Kuznyechik. Both of these algorithms use the same 8-bit S-Box but ... [more ▼]

The Russian Federation's standardization agency has recently published a hash function called Streebog and a 128-bit block cipher called Kuznyechik. Both of these algorithms use the same 8-bit S-Box but its design rationale was never made public. In this paper, we reverse-engineer this S-Box and reveal its hidden structure. It is based on a sort of 2-round Feistel Network where exclusive-or is replaced by a finite field multiplication. This structure is hidden by two different linear layers applied before and after. In total, five different 4-bit S-Boxes, a multiplexer,two 8-bit linear permutations and two finite field multiplications in a field of size $2^{4}$ are needed to compute the S-Box. The knowledge of this decomposition allows a much more efficient hardware implementation by dividing the area and the delay by 2.5 and 8 respectively. However, the small 4-bit S-Boxes do not have very good cryptographic properties. In fact, one of them has a probability 1 differential. We then generalize the method we used to partially recover the linear layers used to whiten the core of this S-Box and illustrate it with a generic decomposition attack against 4-round Feistel Networks whitened with unknown linear layers. Our attack exploits a particular pattern arising in the Linear Approximations Table of such functions. [less ▲]

Algebraic Insights into the Secret Feistel Network

in Peyrin, Thomas (Ed.) Fast Software Encryption - 23rd International Workshop, FSE 2016, Bochum, March 20-23, 2016 (2016)

We introduce the high-degree indicator matrix (HDIM), an object closely related with both the linear approximation table and the algebraic normal form (ANF) of a permutation. We show that the HDIM of a ... [more ▼]

We introduce the high-degree indicator matrix (HDIM), an object closely related with both the linear approximation table and the algebraic normal form (ANF) of a permutation. We show that the HDIM of a Feistel Network contains very specific patterns depending on the degree of the Feistel functions, the number of rounds and whether the Feistel functions are 1-to-1 or not. We exploit these patterns to distinguish Feistel Networks, even if the Feistel Network is whitened using unknown affine layers. We also present a new type of structural attack exploiting monomials that cannot be present at round r-1 to recover the ANF of the last Feistel function of a r-round Feistel Network. Finally, we discuss the relations between our findings, integral attacks, cube attacks, Todo's division property and the congruence modulo 4 of the Linear Approximation Table. [less ▲]

On Reverse-Engineering S-Boxes with Hidden Design Criteria or Structure

in Gennaro, Rosario; Robshaw, Matthew (Eds.) Advances in Cryptology -- CRYPTO 2015, (2015, August)

S-Boxes are the key components of many cryptographic primitives and designing them to improve resilience to attacks such as linear or differential cryptanalysis is well understood. In this paper, we ... [more ▼]

S-Boxes are the key components of many cryptographic primitives and designing them to improve resilience to attacks such as linear or differential cryptanalysis is well understood. In this paper, we investigate techniques that can be used to reverse-engineer S-box design and illustrate those by studying the S-Box $F$ of the Skipjack block cipher whose design process so far remained secret. We first show that the linear properties of $F$ are far from random and propose a design criteria, along with an algorithm which generates S-Boxes very similar to that of Skipjack. Then we consider more general S-box decomposition problems and propose new methods for decomposing S-Boxes built from arithmetic operations or as a Feistel Network of up to 5 rounds. Finally, we develop an S-box generating algorithm which can fix a large number of DDT entries to the values chosen by the designer. We demonstrate this algorithm by embedding images into the visual representation of S-box's DDT. [less ▲]

FELICS - Fair Evaluation of Lightweight Cryptographic Systems

Scientific Conference (2015, July)

In this paper we introduce FELICS, a free and open-source benchmarking framework designed for fair and consistent evaluation of software implementations of lightweight cryptographic primitives for ... [more ▼]

In this paper we introduce FELICS, a free and open-source benchmarking framework designed for fair and consistent evaluation of software implementations of lightweight cryptographic primitives for embedded devices. The framework is very flexible thanks to its modular structure, which allows for an easy integration of new metrics, target devices and evaluation scenarios. It consists of two modules that can currently asses the performance of lightweight block and stream ciphers on three widely used microcontrollers: 8-bit AVR, 16-bit MSP and 32-bit ARM. The metrics extracted are execution time, RAM consumption and binary code size. FELICS has a simple user interface and is intended to be used by cipher designers to compare new primitives with the state of the art. The extracted metrics are very detailed and assist embedded software engineers in selecting the best cipher to match the requirements of a particular application. The tool aims to increase the transparency and trust in benchmarking results of lightweight primitives and facilitates a fair comparison between different primitives using the same evaluation conditions. [less ▲]

Differential Analysis and Meet-in-the-Middle Attack against Round-Reduced TWINE

in Leander, Gregor (Ed.) Fast Software Encryption - 22nd International Workshop, FSE 2015, Istanbul, March 8-11, 2015 (2015, March)

TWINE is a recent lightweight block cipher based on a Feistel structure. We first present two new attacks on TWINE-128 reduced to 25 rounds that have a slightly higher overall complexity than the 25-round ... [more ▼]

TWINE is a recent lightweight block cipher based on a Feistel structure. We first present two new attacks on TWINE-128 reduced to 25 rounds that have a slightly higher overall complexity than the 25-round attack presented by Wang and Wu at ACISP 2014, but a lower data complexity. Then, we introduce alternative representations of both the round function of this block cipher and of a sequence of 4 rounds. LBlock, another lightweight block cipher, turns out to exhibit the same behaviour. Then, we illustrate how this alternative representation can shed new light on the security of TWINE by deriving high probability iterated truncated differential trails covering 4 rounds with probability $2^{-16}$. The importance of these is shown by combining different truncated differential trails to attack 23-rounds TWINE-128 and by giving a tighter lower bound on the high probability of some differentials by clustering differential characteristics following one of these truncated trails. A comparison between these high probability differentials and those recently found in a variant of LBlock by Leurent highlights the importance of considering the whole distribution of the coefficients in the difference distribution table of a S-Box and not only their maximum value. [less ▲]

Collision Spectrum, Entropy Loss, T-Sponges, and Cryptanalysis of GLUON-64

in Fast Software Encryption - 21th International Workshop, FSE 2014, London, March 3-5, 2014 (2014, March)

In this paper, we investigate the security provided by iterative non-injective functions. We introduce the Collision Probabilities Spectrum (CPS) to quantify how far from a permutation a function is. In ... [more ▼]

In this paper, we investigate the security provided by iterative non-injective functions. We introduce the Collision Probabilities Spectrum (CPS) to quantify how far from a permutation a function is. In particular, we show that the size of the iterated image of such a function decreases linearly with the number of iterations and that collision trees of quadratic size appear. We discuss the influence of the CPS over collision search efficiency by connecting it with the function's balance. We then show that the security of a so-called T-Sponge is only marginally impacted by the number of collisions occurring because of the update function. However, the loss of entropy in the update function can lead to a greatly simplified preimage search for a particular family of messages if the rate is small. Consequences of the entropy loss when duplexing the sponge to provide one-pass authenticated encryption and for Davies-Meyer construction are also studied. Finally, we use a heuristic method to estimate the CPS of the update function of GLUON-64. Applying our results, we prove for instance that if a message is only known to end with a sequence of 1 Mb (respectively 1 Gb) of zero bytes, then it is possible to find a preimage for its digest in time $2^{115.3}$ (respectively $2^{105.3}$) instead of $2^{128}$. [less ▲]