Sunday, December 18, 2016

Lightweight Cryptography

The need for lightweight cryptography emerged from the lack of primitives that are capable to run in constrained environments (e.g. embedded systems). In recent years, there has been an increased focus on development of small computing devices that have limited resources. Current state-of-art cryptographic primitives provide the necessary security conditions when put into constraint environments, but their performance may not be acceptable.  
Over the last decade, numerous lightweight cryptographic primitives have been proposed providing performance advantage over conventional cryptographic primitives. These primitives include block ciphers, hash functions, stream ciphers and authenticated ciphers.

Lightweight Block Ciphers

A block cipher provides a keyed pseudo-random permutation that can be used in a more complex protocol. It should be impossible for an adversary with realistic computing power to retrieve the key even if the adversary has access to a black-box model of the cipher where she is able to encrypt/decrypt plaintext of her choice. Block ciphers are normally based on either Substitution-Permutation Networks or Feistel-Networks.

The components and operations in a lightweight block cipher are typically simpler than in normal block ciphers like AES. In contrast to simplifying the round functions, the number of rounds simply increases to achieves the same security. As memory is very expensive the implementation of a S-Box as look-up table can lead to a large hardware footprint. Therefore, lightweight block ciphers have usually small (e.g. 4-bit) S-Boxes. To save further memory, lightweight block ciphers are using small block sizes (e.g. 64 or 80 bits, rather then 128). Another option is to reduce the key sizes used to sizes less than 96 bits for efficiency. Simpler key schedules improve the memory, latency and power consumption of lightweight block ciphers.

Recently, Banik et. al. showed an implementation of AES requiring just 2227 GE and latency of 246/326 cycles per byte for encryption and decryption respectively. In 2007 Bogdanov et. al. proposed PRESENT, an ultra-lightweight block cipher based on a Substitution-Permutation Network that is optimized for hardware and can be implemented with just 1075 GE. PRESENT is bit-oriented and has a hardwired diffusion layer. In 2011, Guo et. al. designed LED, an SPN cipher that is heavily based on AES. Interesting in that design is the lack of the key schedule, as it  applies the same 64-bit key every four rounds to the state for LED-64. The 128-bit version simply divides the key in two 64-bit sub-keys and then alternately adds them to the state. Reducing the latency is the main goal of the block cipher PRINCE. There is no real key schedule in PRINCE, as it derives three 64-bit keys from a 128-bit master key. PRINCE is a reflection cipher, meaning that the first rounds are the inverse of the last rounds, so that the decryption of a key $k$ is identical to an encryption with key $k\oplus\alpha$ where $\alpha$ is a constant based on $\pi$. The block cipher Midori was designed for reducing the energy consumption when implemented in hardware. It has an AES-like structure and a very lightweight almost-MDS involution matrix M in the MixColumn step. In 2013, Simon and Speck have been designed by NSA. Both ciphers perform exceptionally well in both hardware and software and were recently considered for standardization. Compared to all other ciphers, no security analysis or design rational was given by the designers. Simon is hardware-oriented and based on a Feistel-Network with only the following operations: and, rotation, xor. Speck is software oriented and based on an ARX construction with the typical operations: addition, rotation, xor. Very recently, SKINNY has been published to compete with Simon. The main idead behind the design is to be efficient as possible but without sacrificing security. SKINNY is a tweakable block cipher based on the Tweakey framework with the components chosen because of the good compromise the provide between cryptographic properties and hardware costs.

Lightweight Hash Functions

The desired properties of a hash function are:
  •  Collision resistance: it should be not feasible to find $x$ and $y$, such that $H(x) = H(y)$
  •  Preimage resistance: given a hash $h$, it should be infeasible to find a message $x$ such that $H(x) =  h$
  •  Second preimage resistance: given a message $y$, it should be infeasible to find $x\neq y$ such that $H(x) = H(y)$
Conventional hash functions such as SHA1, SHA2 (i.e. SHA-224, SHA-256, SHA-384, SHA-512, SHA-512-224 and SHA-512-256) and SHA3 (i.e. Keccak) may not be suitable for constraint environments due to their large internal state sizes and high power consumption. Lightweight hash functions differ in various aspects as they are optimized for smaller message sizes and/or have smaller internal states and output sizes.

PHOTON is a P-Sponge based AES-like hash function, with an internal state size of 100 to 288 bits and an output of 80 to 256 bits. The state update function is close to the LED cipher. In 2011, Bogdanov et. al. designed SPONGENT, a P-Sponge where the permutation is a modified version of the block cipher PRESENT. SipHash has a ARX structure and is inspired by BLAKE and Skein and has a digest size of 64-bits.

Lightweight Stream Ciphers

A stream cipher generates a key stream from a given key $k$ and an initialization vector $IV$, which is then simply xored with the plaintext to generate a ciphertext. It must be infeasible for an attacker to retrive the key, even if a large part of the keystream is available to the attacker. In 2008, the eSTREAM competition aimed to identify a portfolio of stream ciphers that should be suitable for widespread adoption. Three of the finalists are suitable for hardware applications in a restricted environment.

Grain was designed by Hell et. al. and is based on two finite state registers whose clocking influence each others update function to make it non linear. Grain requires 3239 GE in hardware. MICKEY v2 is based on two LFSR (linear feedback shift registers) that are irregularly clocked. MICKEY v2 requires 3600 GE in hardware. Trivium is also a finalist from the eSTREAM competition that has three LFSR's with different length. Trivium requires 3488 GE in hardware.

Lightweight Authenticated Ciphers

The aim of authenticated encryption is to provide confidentiality and integrity (i.e. data authenticity) simultaneously. In 2014, the CAESAR (Competition for Authenticated Encryption: Security, Applicability and Robustness) competition started with the aim to identify a portfolio of authenticated ciphers that offer advantages over AES-GCM and are suitable for widespread adoption.

ACORN is based on 6 LFSR's and has a state size of 293 bits. ACORN provides full security, for both, encryption and authentication. The hardware costs should be close to that of Trivium according to the designers. SCREAM is a tweakable block ciphers in the TAE (Tweakable Authenticated Encryption) mode. SCREAM is based on LS designs Robin and Fantomas. Bertoni et. al. designed Ketje that is a lightweight variant of SHA3 (i.e. Keccak). Ketje relies on the sponge construction in the MonkeyWrap mode. The internal state size is only 200 bits for Ketje-Jr and 400 bits for Ketje-Sr. Ascon is an easy to implement, sponge-based authenticated cipher with a custom tailored SPN network. It is fast in both, hardware and software even with added countermeasures against side-channel attacks. Another CAESAR candidate is the 64-bit tweakable block cipher Joltik, that is based on the Tweakey framework. Joltik is AES-like and uses the S-Box of Piccolo and the round constants of LED. The MDS matrix is involutory and non-circulant.

No comments:

Post a Comment