Design of Lightweight Linear Layers

Confusion and Diffusion

Confusion and diffusion introduced by Shannon are widely used two fundamental principles in the design of symmetric key primitives. Most modern block ciphers and hash functions have well-designed confusion and diffusion layers. Among many design strategies, substitution-permutation networks (SPN) have been popular in the design of block ciphers and hash functions. The best understood structure of SPN round function probably consists of a brick layer of local nonlinear permutations (usually S-boxes) followed by a multiplication with a diffusion matrix over a finite field (linear diffusion). Diffusion layers play a crucial role in providing resistance against two most powerful statistical attacks differential attack and linear attack .

AES, the most prominent example of SPNs, uses Maximum Distance Separable (MDS) matrix in the MixColumns operation. The MixColumns step employs the following circulant MDS matrix $$\small \left(\begin{array}{cccc} 2 & 3 & 1 & 1\\ 1 & 2 & 3 & 1\\ 1 & 1 & 2 & 3\\ 3 & 1 & 1 & 2 \end{array} \right)$$ where $1,2,3$ are element in the finite field GF($2^8$). It is shown that linear diffusion layers based on MDS matrices have optimal branch numbers and hence provide optimal diffusion properties for any AES-like ciphers in principle.

Lightweight Cryptography

The development of ubiquitous computing such as the Internet of Things (IoT) brings up the relevant security requirements. Specifically, the need for lightweight cryptography emerged from the lack of primitives that are suitable for constrained environments (e.g. RFID tags). Recent years have witnessed the development of various lightweight cipher designs. For more details on lightweight ciphers, the readers can refer to the blogpost Lightweight Cryptography by Ralph. In this post, we will focus on the design of the lightweight linear layer, i.e., lightweight diffusion matrices. We will show how the designers manage to achieve the tradeoff between security and performance.

Lightweight Recursive MDS Matrices

To reduce the hardware cost of MDS matrices, Guo et al. propose a novel design approach of recursive (or serial) MDS matrices. These matrices have been exploited in hardware-oriented lightweight block cipher LED and lightweight hash function PHOTON. The main idea of recursive MDS matrices is to represent an MDS matrix as a power of a very sparse matrix such as a companion matrix. In this way, the MDS matrix can be implemented by iterating the sparse matrix many times. A notable example is the PHOTON MDS matrix. $$\small M= \left(\begin{array}{cccc} 1 & 2 & 1 & 4\\ 4 & 9 & 6 & 17\\ 17 & 38 & 24 & 66\\ 66 & 149 & 100 & 11 \end{array} \right)= \left(\begin{array}{cccc} 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 2 & 1 & 4 \end{array} \right)^4$$ where the entries are elements in GF($2^4$). Compared to direct constructions, recursive MDS matrices have a substantially lower hardware area at the cost of additional clock cycles. Therefore, recursive MDS matrices are not suitable for low-latency applications.

Optimizing Entries in the Matrices

In the last five years, many constructions of lightweight MDS have been proposed. Most of them are based on matrices in some special classes, such as circulant, Hadamard, or Toeplitz matrices, with entries that can be efficiently computed. A novel idea by Li and Wang is to construct MDS matrix with elements in the form of binary matrices instead of elements in a finite field. Consider the following MDS matrix $$\small \left(\begin{array}{cccc} A & I & I & I\\ I & I & B & A\\ I & A & I & B \\ I & B & A & I \end{array} \right),\,\,{\rm where}\,\,\,\tiny A=\left(\begin{array}{cccccccc} 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right)$$ and $B=A^{-2}$. This matrix can be implemented with only $106$ bitwise XOR, while a naive implementation of AES MDS matrix needs $152$ bitwise XOR.

Recent Works on Global Optimization

Most of the previous works consider the cost of an MDS matrix as the sum of costs of each coefficient and the cost of $nm(m-1)$ bit XOR operations, where the matrices are of order $n$ with entries from GF($2^m$). Actually this local optimization approach always overestimates the real cost. Indeed, many common intermediate values can be computed and then reused. In hardware implementations this can be done with merely wires. This implies that a globally optimized implementation can be significantly cheaper. Recently, Kranz et al. used Shorter Linear Straight-Line Programs to optimize hte previously proposed MDS matrices. They found a $4\times 4$ MDS matrix over GF($2^8$) (i.e., the same size of AES MDS matrix) that can be implemented with $72$ bitwise XORs. This number has been further reduced to $67$ in a recent work by Duval and Leurent following similar global optimization approach.

Near-MDS Matrices

It is well-known that any element of an MDS matrix over a finite field must be nonzero. Thus MDS matrices are very dense and hence costly in hardware implementation. MDS and recursive MDS matrices might not offer an optimal trade-off between security and efficiency. Near-MDS have sub-optimal branch numbers while they require less area than MDS matrices and they do not need additional clock cycles. Indeed, some diffusion layers constructed from near-MDS matrices outperform those based on MDS or recursive MDS matrices in terms of the FOAM framework proposed by Khoo et al.. Recently, near-MDS matrices have been adopted in some lightweight block ciphers, including PRINCE, PRIDE, and Midori. However, there is insufficient research on the construction and security properties of near-MDS matrices. These motivate us to present novel results on near-MDS matrices. Actually, We propose new designs of lightweight near-MDS matrices of order $5\sim9$. Further, it is shown that our linear layers with a well-chosen nonlinear layer can provide sufficient security against differential and linear cryptanalysis. The results have been published in ToSC 2017(1).

In sum, we already have pretty good solutions for various requirements in the design of lightweight diffusion matrices. Nevertheless, it remains open to achieve optimal implementation of linear layers in a specific cipher. It is also interesting to further investigate the impact of security on the adoption of non-MDS matrices.

Symmetric Key Ciphers for FHE

In recent years, small devices with limited storage and computing power have acquired more and more popularity. This phenomenon, together with the appearance of cloud services that offer extensive storage and high computing power, has made computation outsourcing a key application to study. This setting, where a user with limited resources stores data on a remote server and also asks this server to make some computation on his behalf, comes together with new challenges and concerns related to privacy and security.

A simple scenario

The user Alice encrypts her data under a homomorphic encryption scheme and sends the ciphertexts to the server (eg. cloud). Now the server computes some function (eg. mean value) on Alice's encrypted data and sends back an encryption of the result, which can be decrypted by Alice with the appropriate key. Despite its simplicity, this model still requires a lot of effort from the user. In fact, all the FHE schemes that we know of have very large keys and heavy encryption overhead. The most natural approach is then trying to free the user from the burden of complex homomorphic computations, by asking her to do only the key generation part, the symmetric encryption and the final decryption, while leaving all the rest to the powerful server.

A hybrid framework

The user Alice generates a secret key $sk^S$ for a symmetric encryption scheme, a pair $(pk^H, sk^H)$ for a homomorphic public key encryption scheme, and sends $pk^H$ to the server together with an encryption of $sk^S$ under $pk^H$. Then, Alice encrypts her data under the symmetric encryption scheme and sends the resulting ciphertexts to the server, which homomorphically evaluates the decryption circuit of the symmetric encryption scheme, thus obtaining ciphertexts under the homomorphic scheme. This last operation can be seen as a sort of bootstrapping (from one scheme to another one), but does not involve any circular security assumption. At this point, the server can homomorphically compute a certain function $f$ on the resulting ciphertexts and send back the result, encrypted under the homomorphic encryption scheme. Alice can finally recover the result thanks to her $sk^H$.

Despite numerous improvements in recent years FHE remains highly unpractical, and one of the main problems is limited homomorphic capacity. In fact, all the FHE schemes we know of contain a noise term that grows with homomorphic operations. The homomorphic capacity corresponds to the amount of computation that can be performed before having to ``refresh'' the ciphertext via the expensive operation of bootstrapping. It is thus of vital importance to manage the error growth during homomorphic operations.

State-of-the-art ciphers

AES is a natural benchmark for FHE implementations. The homomorphic evaluations of some lightweight block ciphers such as SIMON have been investigated by Lepoint and Naehrig as well. It turns out that there is much room for improvement in optimizing the multiplicative depth. In this direction, many dedicated symmetric key ciphers with low-noise ciphertexts have been proposed.

• In 2015, Albrecht et al presented a flexible block cipher LowMC, which is based on an SPN structure with $80,128$ and $256$-bit key variants. The design philosophy is to minimize the multiplicative complexity, which is more relevant in the multi-party computation context. It also has very low multiplicative depth compared with existing block ciphers.

  Later, Dinur et al mounted optimized interpolation attacks against some instances of LowMC. More precisely, some $80$-bit key instances could be broken $2^{23}$ times faster than exhaustive search and all instances that are claimed to provide $128$-bit security could be broken about $1000$ times faster than exhaustive search. These attacks show that the ciphers do not provide the expected security level. The cryptanalysis also led to a revised version of LowMC.
• Keyvrium was designed by Canteaut et al and is a stream cipher aiming at $128$-bit security. It is based on the lightweight stream cipher Trivium, which has $80$-bit security. Trivium and Keyvrium both achieve similar multiplicative depth compared to instances of LowMC. They have a smaller latency than LowMC, but have a slightly smaller throughput.
• The FLIP family stream ciphers proposed by Méaux et al have the lowest depth compared with previous ciphers. Several versions are provided including $80$-bit and $128$-bit security instantiations. The main design principal is to filter a constant key register with a time-varying public bit permutation, which allows for small and constant noise growth. However, FLIP has a much higher number of ANDs per encrypted bit than the above ciphers.

To sum up, blending symmetric ciphers and FHE is definitely an interesting idea that could prove fundamental for bringing homomorphic encryption in the real world.

The other fellows also made contributions to this blog post.

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.