LowMC is a family of block ciphers proposed by Albrecht et al. at EUROCRYPT 2015, which is tailored specifically for FHE and MPC applications. At ToSC 2018, a difference enumeration attack was given for the cryptanalysis of low-data instances of full LowMCv2 with few applied S-boxes per round. Recently at CRYPTO 2021, an efficient algebraic technique was proposed to attack 4-round LowMC adopting a full S-box layer. Following these works, we present a new difference enumeration attack framework, which is based on our new observations on the LowMC S-box, to analyze LowMC instances with a full S-box layer. As a result, with only 3 chosen plaintexts, we can attack 4-round LowMC instances which adopt a full S-box layer with block size of 129, 192, and 255 bits, respectively. We show that all these attacks have either a lower time complexity or a higher success probability than those reported in the CRYPTO paper.
Notes
Communicated by S. D. Galbraith.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
The LowMC family of block ciphers [1] was first proposed by Albrecht et al. at EUROCRYPT 2015 and was designed to achieve low multiplicative complexity, which is tailored specifically for MPC [16, 18, 24, 29, 30] and FHE [7, 15] applications. LowMC uses flexible Substitution–Permutation-Network (SPN) constructions, where instantiations can be created by independently choosing the block size n, the key size k, the number of S-boxes m in the substitution layer and the allowed data complexity d of attacks. Especially, some of the instances adopt the so-called partial Substitution–Permutation Network (P-SPN), i.e. in which the S-boxes are applied over only partial state bits of the cipher.
LowMC has been utilized as the underlying block cipher of the post-quantum signature scheme Picnic [9], which is an alternative candidate in the third round NIST’s Post-Quantum Cryptography competition [25]. Recently, alternative parameters of LowMC were chosen for Picnic3 [17]. Different from Picnic2 where a partial S-box layer is adopted when instantiating LowMC, a full S-box layer is used when generating the three instances of LowMC in Picnic3. In Picnic3, 4-round LowMC is recommended and 5-round LowMC is treated as an alternative.
Advertisement
The proposal of LowMC not only starts a new trend to design symmetric-key primitives, like FLIP [23], MiMC [2], Kreyvrium [8], Rasta [13], GMiMC [3], and Ciminion [14], but also raises new challenges for cryptanalysis to evaluate its security. Soon after its publication, a higher-order differential attack (ICISC 2015, Dobraunig et al. [12]) and an optimized interpolation attack (ASIACRYPT 2015, Dinur et al. [11]) were given, which directly made LowMC move to LowMC v2, although with a high data complexity. Later at FSE 2018, Rechberger et al. [27] proposed the so-called difference enumeration technique to analyse LowMC instances with a few S-boxes in each round. Rechberger et al.’s approach requires very little data—as little as 3 chosen plaintext–ciphertext pairs. To resist such attack, LowMC was further updated to LowMC v3.1 At CRYPTO 2021, Liu et al. [19] revisited the difference enumeration technique for LowMC and showed that some important LowMC instances are still insecure. They achieved efficient key recovery attacks on 3 instances of 4-round LowMC, with only 2 chosen plaintexts. Recently, Liu et al. [22] proposed an algebraic meet-in-the-middle (MITM) technique to analyze LowMC with a partial S-box layer. As a result, the attacks on LowMC and LowMC-M [26] published at CRYPTO 2021 are further improved and some LowMC instances could be broken for the first time.
In another direction, cryptanalysis of the LowMC block cipher when the attacker has access to a single known plaintext/ciphertext pair is particularly relevant while arguing the security of the Picnic digital signature scheme. In Picnic, the plaintext/ciphertext pair generated by the LowMC block cipher serves as the public (verification) key and the corresponding LowMC encryption key also serves as the secret (signing) key of the signature scheme. Therefore, a data complexity one key recovery attack on LowMC block cipher will lead to a signature forgery on Picnic. Until now, there have been several attacks on LowMC in such scenario [4‐6, 10, 20, 21]. At ToSC 2020, Banik et al. [4] proposed guess-and-determine attacks on reduced 2-round LowMC in the Picnic setting. Following this work, at ASIACRYPT 2021, Banik et al. [5] proposed 2-stage Meet-in-the-Middle (MITM) attack with gray-code based approach, which reduced the computational complexity of 2 rounds and extended the number of attacked round to 3 rounds. A parallel work [10] also shows that 2 out of 3 instances of the 4-round LowMC in the Picnic3 setting can be broken, but it requires a huge amount of memory. Later, Banik et al. [6] combine the linearization techniques of [4, 5] and the equation solving methods of [10] to analyse LowMC instances with complete non-linear layers, which yields a drastic reduction in terms of memory complexity. At ToSC 2022, Liu et al. [21] significantly improve the attacks on LowMC in the Picnic Setting by using better time-memory tradeoffs. For a survey of key recovery attacks on LowMC in such attack scenario, readers may check the work done by Grassi et al. [31].
In this paper, we study the security of LowMC with low data complexity and we are most interested in Rechberger et al.’s work [27] and Liu et al.’s work [19]. In [27], Rechberger et al. presented a difference enumeration attack to analyse LowMC instances with a partial S-box layer. The difference enumeration attack is a chosen-plaintext attack, which consists of two steps. The first step is to encrypt a pair (or more) of chosen plaintexts and then recover the difference evolutions between the plaintexts through each component in each round with a meet-in-the-middle method, i.e. to recover the differential trail. This step is called the difference enumeration phase. The second step is to derive the secret key from the recovered differential trail. This step is called the key-recovery phase. As a result, the number of the required plaintexts can be as small as 4. Furthermore, the authors showed that it is more effective to consider d-differences instead of simple differences.
However, the original difference enumeration attack [27] doesn’t fit well with LowMC instances with a full S-box layer. At CRYPTO 2021, Liu et al. [19] showed a new difference enumeration attack framework to attack the constructions adopting a full S-box layer with 2 chosen plaintexts.
Advertisement
1.1 Our contributions
We propose a new difference enumeration attack framework for LowMC instances with a full S-box layer. Instead of considering the traditional difference, we turn to consider the 2-difference and give some new observations on the LowMC S-box which can be exploited in our attack. We then enumerate 2-differences with algebraic techniques and efficiently derive the master key from the recovered 2-differential trails with the linearization technique. Finally, we apply our attack framework to 4-round LowMC with block size of 129, 192, 255 bits, respectively. Our results are summarized in Table . Our attacks have a quite low data complexity, which is only 3 chosen plaintexts. And all these attacks have either a lower time complexity or a higher success probability than those reported by Liu et al. in the previous CRYPTO paper.
Table 1
A summary of the results for 4-round LowMC instances with a full S-box layer, where the time complexity is estimated in units which equal to a single encryption operation of the relevant 4-round LowMC
For the case of \((n,k,m)=(129,129,43)\), our attack has a higher success probability; for \((n,k,m)=(192,192,64)\), our attack is \(2^2\) times faster than that proposed in [19] when limiting the success probability to 0.99 or more; for \((n,k,m)=(255,255,85)\), our attack is \(2^{4.6}\) times faster than that proposed in [19] when limiting the success probability to 0.986 or more
\(^a\)Success probability recalculated is higher than that reported in [19]
1.2 Organization of the paper
We give a brief introduction of LowMC and some definitions in Sect. 2. In Sect. 3, we revisit the difference enumeration techniques. In Sect. 4, we introduce our approach in a high level and show some new observations on LowMC S-box. In Sect. 5, we introduce how to find all valid 4-round compact 2-differential trials in our attack by solving linear equations. In Sect. 6, we show how to recover the master key with the algebraic method. The analysis and experimental results of our attack on 4-round LowMC instances are given in Sect. 7. Finally, we conclude the paper in Sect. 8.
2 Preliminaries
2.1 A brief description of LowMC
LowMC [1] is a family of block ciphers with flexible SPN constructions. When instantiating LowMC, users can independently choose the parameters: the block size n, the key size k, the number of S-boxes m in each round and the allowed data complexity \(2^D\) of attacks. The number of rounds R needed to reach the security against several known attacks with reasonable security margins is then derived from these parameters. The block cipher uses a 3-bit S-box which is the only non-linear transformation in the construction. Both the linear layers and the round key generation are done by multiplying with full rank matrices over GF(2) of appropriate dimensions.
The encryption procedure of LowMC starts with a key whitening (WK), and then iterates the round function (as depicted in Fig. ) R times, which consists of four operations in the following order.
1.
SBoxLayer(SB): A 3-bit S-box \((y_0,y_1,y_2)=S(x_0,x_1,x_2)\) with \((y_0,y_1,y_2)=(x_0\oplus x_1x_2, x_0\oplus x_1\oplus x_0x_2, x_0\oplus x_1\oplus x_2\oplus x_0x_1)\) is applied to the first 3m bits of the state in parallel. For the remaining \(n-3m\) bits, an identity mapping is applied.
2.
LinearLayer(L): The n-bit state is multiplied with an invertible \(n\times n\) matrix \(L_i\) in GF(2). The matrix \(L_i\) is randomly chosen from all invertible binary \(n\times n\) matrices.
3.
ConstantAddition(AC): The n-bit state is XORed with an n-bit binary round constant \(RC_i\). The round constant \(RC_i\) is randomly chosen from all binary vectors of length n.
4.
KeyAddition(AK): The n-bit state is XORed with the n-bit round key \(K_{i+1}\). To generate \(K_{i+1}\), a matrix \(U_{i+1}\) is randomly chosen from all full rank \(n\times k\) binary matrices, and then the \(K_{i+1}\) is obtained by multiplying the k-bit master key with \(U_{i+1}\).
The whitening key \(K_0\) is also calculated by multiplying the master key with a random full-rank \(n\times k\) binary matrix \(U_0\).
Fig. 1
The LowMC Round Function
×
2.2 Definitions
Definition 1
(d-Difference [28]) For a tuple of \((d+1)\) texts \((s_0, s_1,\dots , s_d)\), the corresponding d-difference is defined as \((\Delta ^1,\)\( \Delta ^2, \cdots ,\Delta ^d)=(s_0\oplus s_1, s_0\oplus s_2, \dots , s_0\oplus s_d)\). And the reference text \(s_0\) is called the anchor of the d-difference.
We denote the plaintext by p and the ciphertext by c. The state after WK is denoted by \(X_0\). In the i-th round, the input state of SB is denoted by \(X_i\) and the output state of SB is denoted by \(X_{i\_S}\), as shown below:
In particular, the 1-difference of plaintexts is denoted by \(\Delta _p\). In the i-th round, we denote the 1-difference of the input state of SB by \(\Delta _{i}\), and the 1-difference of the output state of SB by \(\Delta _{i\_S}\), as shown below:
(Compact 1-Differential Trail [19]) Let \(\Delta _0\rightarrow \Delta _1\rightarrow \cdots \rightarrow \Delta _r\) be a 1-differential trail, in which we may not know all \(\Delta _i (0\le i\le r)\). If all \((\Delta _j, \Delta _{j\_S})\)\((0\le j\le r-1)\) and \(\Delta _r\) are known, we call it an r-round compact 1-differential trail.
Definition 3
(Compactd-Differential Trail (\(d>1\))) Let \(\alpha _0\rightarrow \alpha _{0\_S}\)\(\rightarrow \alpha _1\rightarrow \cdots \rightarrow \alpha _r\) where \(\alpha _i=(\Delta _i^1,\Delta _i^2, \cdots , \Delta _i^d)\) with \((0\le i\le r)\) and \(\alpha _{j\_S}=(\Delta _{j\_S}^1,\Delta _{j\_S}^2, \cdots , \Delta _{j\_S}^d)\) with \((0\le j\le r-1)\) be a d-differential trail, in which we may not know all \((\alpha _j, \alpha _{j\_S})\)\((0\le j\le r-1)\) and \(\alpha _r\). If all \((\alpha _j, \alpha _{j\_S})\)\((0\le j\le r-1)\) and \(\alpha _r\) are known, we call it an r-round compact d-differential trail.
3 The difference enumeration attack framework
In this section, we briefly revisit the original difference enumeration attack [27] on instances with a partial S-box layer and the extended difference enumeration attack [19] on instances with a full S-box layer.
At ToSC 2018, the LowMC team proposed a difference enumeration attack [27] to analyze the security of LowMCv2 with a low data complexity. The difference enumeration attack consists of two phases. The first phase is called the difference enumeration phase, which is to recover internal d-differences for a chosen \((d+1)\)-tuple of plaintexts and the corresponding ciphertexts. In this phase, a meet-in-the-middle approach is applied. The second phase is the key-recovery phase, which is to derive the secret key from the recovered compact d-differential trail.
However, the original difference enumeration attack [27] is not quite efficient when it comes to a full S-box layer. To refine the original difference enumeration attack, in the difference enumeration phase, Liu et al. [19] consider to choose a desirable input difference such that it will activate as few S-boxes as possible in the first two rounds. Moreover, they consider to enumerate the solutions of a linear equation system. In the key-recovery phase, for a retrieved 4-round compact 1-differential trail, they recover the full key by solving linear equations with k-bit master key and some internal variables.
The algebraic techniques used in this extended attack are based on the following observations on LowMC S-box.
Observation 1
[19] For each valid non-zero 1-difference transition \((\Delta x_0, \Delta x_1,\)\( \Delta x_2)\)\( \rightarrow (\Delta y_0, \Delta y_1, \Delta y_2)\), the inputs conforming to such a difference transition will form an affine space of dimension 1. In addition, \((y_0, y_1, y_2)\) becomes linear in \((x_0, x_1, x_2)\). A similar property also applies to the inverse of the S-box.
Observation 2
[19] For each non-zero input 1-difference \((\Delta x_0, \Delta x_1, \Delta x_2)\), its valid output 1-differences form an affine space of dimension 2. A similar property also applies to the inverse of the S-box.
Observation 3
[19] For an inactive S-box, the input becomes linear in the output after guessing two output bits, and the output becomes linear in the input after guessing two input bits. The same property holds for its inverse.
4 Approach overview and new observations on the LowMC S-box
In this section, we give an overview of our new difference enumeration attack on LowMC with a full S-box layer, and show our new observations on LowMC S-box.
4.1 Overview of our approach
In our new difference enumeration attack, we consider the 2-difference, and we call it 2-difference enumeration attack in the following. It also consists of two phases, i.e. the 2-difference enumeration phase and the key-recovery phase.
First, for the construction with a full S-box layer, the cost of enumerating d-differences in the original difference enumeration attack [27] is rather high, especially when \(d>1\). And if we enumerate 2-differences for more than one round, the time complexity will be higher than that of the brute force attack. In order to overcome this obstacle, we choose a desirable input 2-difference such that the number of inactive S-boxes in the 0th round is maximized, as depicted in Fig. . Moreover, based on the algebraic techniques used in [19], we introduce some variables to represent internal 2-differences, and then construct and solve linear equations to find the valid 2-differences in the middle 2 rounds.
Fig. 2
The framework of the 2-difference enumeration attack
×
Second, for a recovered 4-round compact 2-differential trail, we can derive the master key by some algebraic techniques. Specifically, by exploiting the special property of the LowMC S-box, we can linearize the S-box. And if a S-box is active, the input and output will satisfy some linear equations. Finally, we can obtain a linear equation system in terms of the master key and some internal variables. Each solution of this equation system corresponds to a candidate master key, and check its correctness via a plaintext-ciphertext pair.
4.2 New observations on the LowMC S-box
Before introducing the details of our attacks on LowMC, it is necessary to describe our new observations on the LowMC S-box with respect to 2-differences. Denote a tuple of 3 input states of the S-box by \((X_0, X_1, X_2)\) and the corresponding 6-bit input 2-difference \((X_0\oplus X_1, X_0\oplus X_2)\) of which the anchor is \(X_0\) by \( (\Delta x_0^1, \Delta x_1^1, \Delta x_2^1, \Delta x_0^2, \Delta x_1^2, \Delta x_2^2)\). Also, denote a tuple of 3 output states of the S-box by \((Y_0, Y_1, Y_2)\) where \(Y_i=S(X_i) (0\le i\le 2)\) and the corresponding 6-bit output 2-difference \((Y_0\oplus Y_1, Y_0\oplus Y_2)\) of which the anchor is \(Y_0\) by \( (\Delta y_0^1, \Delta y_1^1, \Delta y_2^1, \Delta y_0^2, \Delta y_1^2, \Delta y_2^2)\).
Observation 4
For each non-zero input 2-difference \((\Delta x_0^1, \Delta x_1^1, \Delta x_2^1, \Delta x_0^2, \Delta x_1^2, \)\(\Delta x_2^2)\):
1.
if \((\Delta x_0^1, \Delta x_1^1, \Delta x_2^1)=(\Delta x_0^2, \Delta x_1^2, \Delta x_2^2),\) or \((\Delta x_0^1, \Delta x_1^1, \Delta x_2^1)=(0,0,0)\), or \((\Delta x_0^2, \Delta x_1^2, \Delta x_2^2)=(0,0,0)\), its valid output 2-differences will form an affine space of dimension 2.
2.
else, its valid output 2-differences will form an affine space of dimension 3.
A similar property also applies to the inverse of the S-box.
Example When the input 2-difference is (0, 0, 1, 0, 0, 1), the corresponding output 2-difference \((\Delta y_0^1, \Delta y_1^1, \Delta y_2^1, \Delta y_0^2, \Delta y_1^2, \Delta y_2^2)\) satisfies
if \((\Delta x_0^1, \Delta x_1^1, \Delta x_2^1)=(\Delta x_0^2, \Delta x_1^2, \Delta x_2^2),\) or \((\Delta x_0^1, \Delta x_1^1, \Delta x_2^1)=(0,0,0)\), or \((\Delta x_0^2, \Delta x_1^2, \Delta x_2^2)=(0,0,0)\), we call the S-box special-active (with respect to the 2-difference);
2.
else, we call the S-box non-special-active (with respect to the 2-difference).
For the 2-difference transition \((0,0,0,0,0,0)\rightarrow (0,0,0,0,0,0)\), we call the S-box inactive (with respect to the 2-difference).
Observation 5
For each valid non-zero 2-difference transition \((\Delta x_0^1, \Delta x_1^1, \Delta x_2^1,\)\( \Delta x_0^2, \Delta x_1^2, \Delta x_2^2)\rightarrow (\Delta y_0^1, \Delta y_1^1, \Delta y_2^1, \Delta y_0^2, \Delta y_1^2, \Delta y_2^2)\), if the S-box is non-special-active (with respect to the 2-difference), the value of anchor \(X_0\) will be determined.
Example If the 2-difference transition \((\Delta x_0^1, \Delta x_1^1, \Delta x_2^1, \Delta x_0^2, \Delta x_1^2, \Delta x_2^2)\rightarrow (\Delta y_0^1, \Delta y_1^1,\)\( \Delta y_2^1, \Delta y_0^2, \Delta y_1^2, \Delta y_2^2)\) is \((0,1,1,1,0,1)\rightarrow (0,1,0,0,0,1)\), the value of anchor \(X_0\) will be determined, i.e. \(X_0=(0,1,0)\).
4.2.1 Generalization
The above Observations 4 and 5 hold for all 3-bit almost perfect nonlinear (APN) S-boxes. As for Observation 5, this generalization is trivial. As for Observation 4, a simplified proof for this generalization can be referred to Appendix 1.
5 2-Difference enumeration
In this section, we first introduce how to enumerate 2-differences in the middle 2 rounds by solving linear equations, and then describe the procedure of 2-difference enumeration phase in our attack. Since we only consider 2-differences in the following, we will omit the phrase “with respect to the 2-difference” for simplicity.
5.1 Enumerating 2-differences via solving equations
Assume that \(\alpha _i=(\Delta _i^1, \Delta _i^2)\) and \(\alpha _{(i+1)\_S}=(\Delta _{(i+1)\_S}^1, \Delta _{(i+1)\_S}^2)\) are known in the i-th round and \((i+1)\)-th round. We aim to enumerate all values of \(\alpha _{i\_S}=(\Delta _{i\_S}^1, \Delta _{i\_S}^2)\) such that the 2-difference transition \(\alpha _i\rightarrow \alpha _{i\_S}\rightarrow \alpha _{(i+1)\_S}\) is valid. Consider the general case: there are a inactive S-boxes and b special-active S-boxes in the i-th round, and there are c inactive S-boxes and d special-active S-boxes in the \((i+1)\)-th round.
First, we introduce some variables to represent internal 2-differences in the i-th round. For the input 2-difference \(\alpha _i\), we can introduce at most 6m variables to represent the 6m-bit output 2-difference \(\alpha _{i\_S}=(\Delta _{i\_S}^1, \Delta _{i\_S}^2)\). However, by exploiting Observation 4, we could introduce \(3m-3a-b\) variables to represent \(\alpha _{i\_S}=(\Delta _{i\_S}^1, \Delta _{i\_S}^2)\). Specifically, 1) for an inactive S-box, the output 2-difference is determined, i.e. (0, 0, 0, 0, 0, 0), so there is no need to introduce variables to represent them. 2) For a special-active S-box, the valid output 2-differences form an affine space of dimension 2, so we need to introduce 2 variables to represent them. Thus, we need introduce 2b variables \((v_0,v_1,\dots ,v_{2b-1})\) to represent the output 2-differences of the b special-active S-boxes. 3) For a non-special-active S-box, the valid output 2-differences form an affine space of dimension 3, so we need to introduce 3 variables to represent them. Thus, we need introduce \(3(m-a-b)\) variables \((v_{2b},v_{2b+1},\dots ,v_{2b+3(m-a-b)-1})\) to represent the output 2-differences of the \((m-a-b)\) non-special-active S-boxes. As a result, we only need to introduce \(2b+3(m-a-b)=3m-3a-b\) variables \((v_0,v_1,\dots , v_{3m-3a-b-1})\) to denote the valid output 2-difference \(\alpha _{i\_S}\). In this way, each bit of \(\alpha _{i+1}=(\Delta _{i+1}^1, \Delta _{i+1}^2)\) can be written as a linear expression with variables \((v_0,v_1,\dots , v_{3m-3a-b-1})\).
Then, in the \((i+1)\)-th round, the output 2-difference \(\alpha _{(i+1)\_S}\) is known, so we can construct an equation system with the above variables \((v_0,v_1,\dots , v_{3m-3a-b-1})\) based on Observation 4. Specifically, (1) for an inactive S-box, the input 2-difference is (0, 0, 0, 0, 0, 0), i.e. in \(\alpha _{i+1}\) the values of 6 bits which are linear in the above variables are known. Thus, six linear equations with the above variables can be obtained. (2) For a special-active S-box, its valid input 2-differences form an affine space of dimension 2, i.e. the value of 6-bit input 2-difference satisfies 4 linear equations. Thus, four linear equations with the above variables can be obtained. (3) For a non-special-active S-box, its valid input 2-differences form an affine space of dimension 3, i.e. the value of 6-bit input 2-difference satisfies 3 linear equations. Thus, three linear equations with the above variables can be obtained. Therefore, we can obtain \(6c+4d+3(m-c-d)=3m+3c+d\) linear equations with the above \(3m-3a-b\) variables. Since \(3m-3a-b\le 3m\le 3m+3c+d\), we can expect the equation system has at most one solution. And the solution will correspond to a valid value of \(\alpha _{i\_S}\).
5.1.1 Complexity evaluation
The time complexity of solving the above \(3m+3c+d\) linear equations with \(3m-3a-b\) variables is estimated as \(n^3+2n^2\) bit operations. Specifically, we first solve \(3m-3a-b\) linear equations among them by Gaussian elimination (GE), which costs around \(n^3\) bit operations. And we can expect the number of solutions is one. Then we check the correctness of this solution by the remaining \((3m+3c+d)-(3m-3a-b)\) linear equations, which costs \(((3m+3c+d)-(3m-3a-b))(3m-3a-b)\le 2n^2\) bit operations. Since performing a LowMC encryption costs around \(2n^2R\) bit operations, the time complexity of solving the above equation system is equivalent to \(\frac{n^3+2n^2}{2n^2R}\approx \frac{n^3}{2n^2R}\) encryptions.
5.2 Recovering valid 2-differential trails
Now we introduce the 2-difference enumeration phase of our attack on 4-round LowMC with a full S-box layer in detail. As depicted in Fig. , our 2-difference enumeration phase consists of the following 4 steps:
1.
We choose a desirable input 2-difference \(\alpha _0\) such that there are 1 non-special-active S-box and \(m-1\) inactive S-boxes in the 0th round.
2.
Encrypt 3 plaintexts \((p_0, p_1, p_2)\) whose 2-difference is \(\alpha _0\), and obtain the corresponding ciphertexts \((c_0, c_1, c_2)\). Then we compute the 2-difference \(\alpha _4\) of \((c_0, c_1, c_2)\) and \(\alpha _{3\_S}\).
3.
For each of 8 possible values of \(\alpha _{0\_S}\), we compute the value of \(\alpha _1\) from \(\alpha _{0\_S}\) and introduce \(3m-3a-b\) variables \((v_0,v_1,\dots , v_{3m-3a-b-1})\) to represent \(\alpha _2\) using the method described in 5.1, where there are a inactive S-boxes and b special-active S-boxes in the 1st round. Then go to the next step.
4.
Enumerate 2-differences backwards for 1 round from \(\alpha _{3\_S}\) to \(\alpha _{2\_S}\). According to each value of \(\alpha _{2\_S}\), by the method described in 5.1, we obtain \(3m+3c+d\) linear equations with the \(3m-3a-b\) variables \((v_0,v_1,\dots , v_{3m-3a-b-1})\), where there are c inactive S-boxes and d special-active S-boxes in the 2nd round. Solve this equation system and we can expect it has at most one solution. For each solution, a valid 4-round compact 2-differential trail is found.
Fig. 3
The procedure of the 2-difference enumeration phase
×
5.2.1 Complexity evaluation
As in [19], we compute the expected number of iterations to enumerate the 2-differences backwards in the 2-difference enumeration phase. In our attack using 3 chosen plaintexts, \(\alpha _{3\_S}\) is a random fixed value. We assume that there are t inactive S-boxes and j special-active S-boxes in the 3rd round. In this phase, for each possible value of \(\alpha _{0\_S}\), the expected number of iterations to enumerate the 2-differences backwards is
As in 5.1, we simply estimate the cost of solving the equation system as \(\frac{n^3}{2n^2R}=\frac{n}{2R}\) when enumerating 2-differences backwards each time. Thus, the expected time complexity of solving the equation systems in this phase is
In this section, we show the algebraic techniques which are used to derive the full key when a 4-round compact 2-differential trail is recovered in our attack. For each compact 2-differential trail we find, there are 1 non-special-active S-box and \(m-1\) inactive S-boxes in the 0th round. And we consider the general case: there are a inactive S-boxes and b special-active S-boxes in the 1st round, c inactive S-boxes and d special-active S-boxes in the 2nd round, and t inactive S-boxes and j special-active S-boxes in the 3rd round.
Now we consider the encryption path from \(p_0\) to \(c_0\). The procedure starts from the 3rd round and can be divided into the following steps (as depicted in Fig. ):
1.
Denote the round key bits used in the 3rd round by \((e_0, e_1, \dots , e_{3m-1})\). Then \(X_{3\_S}\) becomes linear in \((e_0,\dots ,\)\(e_{3m-1})\). For the t inactive S-boxes, introduce extra 3t variables \((v_0,v_1,\dots ,v_{3t-1})\) to represent their input bits. Based on Observation 1, for the j special-active S-boxes, we obtain 2j linear equations with the output bits of these S-boxes, and the input bits become linear in the output bits for these S-boxes. Based on Observation 5, for the \(m-t-j\) non-special-active S-boxes, we obtain \(3(m-t-j)\) linear equations with the output bits of these S-boxes, and the input bits of these S-boxes are determined. Then we obtain \(2j+3(m-t-j)=3m-3t-j\) linear equations with \((e_0, e_1, \dots , e_{3m-1})\) and \(X_3\) becomes linear in \((v_0, v_1,\dots ,v_{3t-1}, e_0, e_1, \dots , e_{3m-1})\).
2.
Move to the 2nd round, and denote the round key bits used in this round by \((e_{3m}, e_{3m+1}, \dots , e_{6m-1})\). Then \(X_{2\_S}\) becomes linear in \((v_0, v_1,\dots ,v_{3t-1}, e_0,\dots ,e_{6m-1})\). For each inactive S-box, we guess 2 bits for its output and then its input bits become linear in the output bits according to Observation 3. From the 2 guessed bits, we obtain 2 linear equations with the output bits of the inactive S-box. Similarly to that in the 3rd round, for each special-active S-box, we obtain 2 linear equations with its output bits and its input bits become linear in the output bits. For each non-special-active S-box, we obtain 3 linear equations with its output bits and its input bits are determined. Then we obtain \(2c+2d+3(m-c-d)\ge 2m\) linear equations with \((v_0, v_1,\dots ,v_{3t-1}, e_0,\dots ,\)\(e_{6m-1})\) and \(X_2\) becomes linear in these variables.
3.
Move to the 1st round, and denote the round key bits used in this round by \((e_{6m}, e_{6m+1},\dots , e_{9m-1})\). Then \(X_{1\_S}\) becomes linear in \((v_0, v_1, \dots , v_{3t-1},e_0,\dots ,\)\(e_{9m-1})\). Similarly to that in the 2nd round and 3rd round, for the special-active S-boxes and non-special-active S-boxes, we obtain \(2b+3(m-a-b)=3m-3a-b\) linear equations with \((v_0, v_1, \dots , v_{3t-1},e_0,\dots ,e_{9m-1})\).
4.
Move to the 0th round. For the non-special-active S-box, there are 3 linear equations in terms of the plaintext and the whitening key.
5.
Since each round key bit is linear in the k-bit master key, we obtain \((3m-3t-j)+2m+(3m-3a-b)+3=8m+3-3a-b-3t-j\) linear equations with \((v_0, v_1, \dots , v_{3t-1})\) and k-bit master key. For each solution of the equation system, we get a candidate master key and check it via the plaintext-ciphertext pair. Then try another guess in the 2nd round and repeat the same procedure until all possible guesses are traversed.
Fig. 4
Introduce extra variables and extract linear equations in the i-th round \((1\le i\le 3)\), where inactive S-boxes are colored in orange, special-active S-boxes are colored in green and non-special-active S-boxes are colored in black. Note that \(j_i=(9-3i)m\)
×
6.1 Complexity evaluation
Assume that there are t inactive S-boxes and j special-active S-boxes in the 3rd round. For the valid value of \(\alpha _{0\_S}\) with a inactive S-boxes and b special-active S-boxes in the 1st round, when recovering a compact 2-differential trail each time, we derive the master key by constructing \(8m+3-3a-b-3t-j\) linear equations with \(k+3t\) variables after guessing some bits. If \(k+3t\le 8m+3-3a-b-3t-j\), i.e. \(6t+j\le 5m+3-3a-b\), then it can be expected that the equation system has at most 1 solution. The expected time complexity of retrieving the master key for this case is
If \(k+3t>8m+3-3a-b-3t-j\), i.e. \(6t+j>5m+3-3a-b\), then it can be expected that the equation system has \(2^{6t+j-5m-3+3a+b}\) solutions. The expected time complexity of retrieving the master key for this case is
A detailed explanation for the complexity \(T_3\) can be referred to Appendix 2.
7 Attacks on LowMC with a full S-box layer
Combining the two phases in Sects. 5 and 6, we now apply our attack framework (as shown in Algorithms 1 and 2) to analyse three 4-round LowMC instances with parameters \((n, k, m, D)\in \)\(\{(129,129,43,2)\), (192, 192, 64, 2), \((255, 255, 85, 2)\}\). The results are summarized in Table 1.
×
×
Now we calculate the time complexity and success probability of our attack, which needs a negligible memory. In our attack with 3 chosen plaintexts, \(\alpha _{3\_S}\) is a random fixed value. For each S-box in the 3rd round, the probability that this S-box is inactive is \(\frac{1}{64}\), the probability that this S-box is special-active is \(\frac{21}{64}\), and the probability that this S-box is non-special-active is \(\frac{42}{64}\). In the following, we denote the probability of event w happening by \(\text {Pr}[w]\).
Attack on (129, 129, 43, 2). For \((n, k, m, D, R)=(129, 129, 43, 2, 4)\), as \(\text {Pr}[3t+j\ge 13]\approx 0.83\), we conclude that with the success probability 0.83, the total time complexity to enumerate 2-differences will be \(2^{3m+3-3t-j}\times \frac{n}{2R}\le 2^{123}\) based on Eq. 4, and the total time complexity to retrieve the master key will not exceed \(8\times max\{2^{2.73m-3t-j}, 2^{3t-2.27m-3}\}\le 2^{107.4}\) based on Eqs. 5 and 6. Thus, we can break the parameter \((n, k, m, D, R)=(129, 129, 43, 2, 4)\) with time complexity less than \(2^{123}\) and success probability 0.83.
Attack on (192, 192, 64, 2). For \((n, k, m, D, R)=(192, 192, 64, 2, 4)\), as \(\text {Pr}[3t+j\ge 14]\approx 0.994\), we conclude that with success probability 0.994, the total time complexity to enumerate 2-differences will be \(2^{3m+3-3t-j}\times \frac{n}{2R}\le 2^{185.6}\) based on Eq. 4, and the total time complexity to retrieve the master key will not exceed \(8\times max\{2^{2.73m-3t-j}, 2^{3t-2.27m-3}\}\le 2^{163.7}\) based on Eqs. 5 and 6. Thus, we can break the parameter \((n, k, m, D, R)=(192, 192, 64, 2, 4)\) with time complexity less than \(2^{185.6}\) and success probability 0.994.
Attack on (255, 255, 85, 2). For \((n, k, m, D, R)=(255, 255, 85, 2, 4)\), as \(\text {Pr}[3t+j\ge 20]\approx 0.994\), we conclude that with success probability 0.994, the total time complexity to enumerate 2-differences will be \(2^{3m+3-3t-j}\times \frac{n}{2R}\le 2^{243}\) based on Eq. 4, and the total time complexity to retrieve the master key will not exceed \(8\times max\{2^{2.73m-3t-j}, 2^{3t-2.27m-3}\}\le 2^{215}\) based on Eqs. 5 and 6. Thus, we can break the parameter \((n, k, m, D, R)=(255, 255, 85, 2, 4)\) with time complexity less than \(2^{243}\) and success probability 0.994.
In addition, as \(\text {Pr}[3t+j\ge 21]\approx 0.989\), we conclude that with success probability 0.989, the total time complexity to enumerate 2-differences will be \(2^{3m+3-3t-j}\times \frac{n}{2R}\le 2^{242}\) based on Eq. 4, and the total time complexity to retrieve the master key will not exceed \(8\times max\{2^{2.73m-3t-j}, 2^{3t-2.27m-3}\}\le 2^{214}\) based on Eqs. 5 and 6. Thus, we can break the parameter \((n, k, m, D, R)=(255, 255, 85, 2, 4)\) with time complexity less than \(2^{242}\) and success probability 0.989.
7.1 Experiments
In order to confirm the correctness of our methods, similarly to that in [19], we performed experiments on the toy LowMC instance with parameter \((n, k, m, D, R)=(21, 21,\) 7, 2, 4). We provide our code at https://github.com/wxqiao/LowMC_new_attack_2diff.
By choosing different desirable input 2-differences, we performed several experiments with 100 random tests each. In each test, for every valid \(\alpha _{0\_S}\), the number of iterations to enumerate 2-differences backwards is equal to the value computed based on Eq. 1 and the number of iterations to enumerate all compact 2-differential trails is much smaller than it. As for the guessing times to recover the master key, it is found that the obtained value indeed matches well with the theoretical value computed based on Eqs. 5 or 6.
8 Conclusion
In this paper, we present a 2-difference enumeration attack framework to analyze 4-round LowMC with a full S-box layer. With only 3 chosen plaintexts, we attack the 4-round LowMC instances adopting a full S-box layer with block size of 129, 192, and 255 bits, respectively. All these attacks have either a lower time complexity or a higher success probability than those proposed in the previous CRYPTO paper [19].
Acknowledgements
We thank anonymous referees for their insightful comments. This work was supported by the National Key Research and Development Program of China (Grant Nos. 2022YFB2701900, 2018YFA0704704), the National Natural Science Foundation of China (Grant Nos. 62032014, 62202444), the Fundamental Research Funds for the Central Universities.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
where \(\phi _i(x_0, x_1, x_2) (0\le i\le 2)\) are linear boolean functions and \(a_j\in {\mathrm{F_2}}(0\le j\le 8)\), \(c_j\in {\mathrm{F_2}}(0\le j\le 2)\).
Since Observation 2 holds for all 3-bit APN S-box [19], the generalization holds for the case when \((\Delta x_0^1, \Delta x_1^1, \Delta x_2^1)=(\Delta x_0^2, \Delta x_1^2, \Delta x_2^2),\) or \((\Delta x_0^1, \Delta x_1^1, \Delta x_2^1)=(0,0,0)\), or \((\Delta x_0^2, \Delta x_1^2, \Delta x_2^2)=(0,0,0)\).
For the other case, we can write the accurate 8 valid output 2-differences, and it can be found that the 8 valid output 2-differences form an affine space of dimension 3.
For example, when input 2-difference is (0, 0, 1, 1, 0, 1), the possible output 2-differences are listed below:
where we denote \(\phi _i(0,0,1)\) by \(\Delta \phi _i (0\le i\le 2)\) and \(\phi _i(1,0,1)\) by \(\widetilde{\Delta \phi _i} (0\le i\le 2).\)
As \(\{(0,0,0,0,0,0), (0,0,0,a_1,a_4,a_7), (a_2,a_5,a_8,a_0\oplus a_1\oplus a_2,a_3\oplus a_4\oplus a_5,a_6\oplus a_7\oplus a_8),\)\((a_1,a_4,a_7,0,0,0), (a_2,a_5,a_8,a_0\oplus a_2, a_3\oplus a_5, a_6\oplus a_8), (a_1,a_4,a_7,a_1,a_4,a_7),(a_1\oplus \)\(a_2, a_4\oplus a_5, a_7\oplus a_8, a_0\oplus a_2, a_3\oplus a_5, a_6\oplus a_8), (a_1\oplus a_2, a_4\oplus a_5, a_7\oplus a_8, a_0\oplus a_1\oplus a_2, a_3\oplus \)\(a_4\oplus a_5, a_6\oplus a_7\oplus a_8)\}\) is a linear subspace of dimension 3 of \(\mathrm{F_2^6}\), the 8 possible output 2-differences form an affine space of dimension 3.
Appendix B: A detailed explanation for the complexity \(T_3\)
In our attack using 3 chosen plaintexts, assume that there are t inactive S-boxes and j special-active S-boxes in the 3rd round. For each valid value of \(\alpha _{0\_S}\) with a inactive S-boxes and b special-active S-boxes in the 1st round, the number of values of \(\alpha _2\) such that the 2-difference transition \(\alpha _{0\_S}\rightarrow \alpha _2\) is valid equals
When enumerating 2-differences backwards, the number of valid values of \(\alpha _{2\_S}\) which satisfies there are c inactive S-boxes and d special-active S-boxes in the 2nd round is
And for each valid \(\alpha _{2\_S}\) which satisfies there are c inactive S-boxes and d special-active S-boxes in the 2nd round, the number of values of \(\alpha _2\) such that the 2-difference transition \(\alpha _2\leftarrow \alpha _{2\_S}\) is valid equals
For each valid 4-round compact 2-differential trail where there are c inactive S-boxes and d special-active S-boxes in the 2nd round, we need to iterate \(2^{2c}\) times to guess 2 bits for each inactive S-box in the 2nd round. In each iteration, we construct \(8m+3-3a-b-3t-j\) linear equations with \(k+3t\) variables. If \(k+3t\le 8m+3-3a-b-3t-j\), i.e. \(6t+j\le 5m+3-3a-b\), then it can be expected that the equation system has at most 1 solution. The cost equals 1. If \(k+3t>8m+3-3a-b-3t-j\), i.e. \(6t+j>5m+3-3a-b\), then it can be expected that the equation system has \(2^{6t+j-5m-3+3a+b}\) solutions. The cost equals \(2^{6t+j-5m-3+3a+b}\).
Thus, if \(k+3t\le 8m+3-3a-b-3t-j\), i.e. \(6t+j\le 5m+3-3a-b\), the expected time complexity to retrieve the master key is
