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.
No comments:
Post a Comment