A new algebraic attack on DASTA

Abstract

As a fully homomorphic encryption friendly symmetric-key primitive, DASTA was invented by Hebborn at Fast Software Encryption 2020. A new fixed linear layer design concept is introduced in the DASTA stream cipher so that its AND depth and the number of ANDs per encrypted bit are quite small. Currently, the security of the DASTA stream cipher has received extensive attention. Note that the best-known attack (i.e., algebraic attack) on DASTA still has a very high data complexity. It appears to be an important task to reduce the data complexity of the attack on DASTA. In this article, a new algebraic attack on DASTA is proposed. More specifically, the key feed-forward operation, the properties of the nonlinear layer and the invariance from the linear layer are successfully utilized in the attack. In particular, the nonlinear relation of internal states in DASTA is linearized effectively. In this case, more secret key bit equations with low algebraic degrees are collected by fixing the bit. It is illustrated that four $(r - 1)$ -round instances of the DASTA cipher family are theoretically broken by the attack, where r is the iterative number of round operations. Compared with the results of previous algebraic attacks, our approach achieves more favorable data complexity.

Keywords

DASTA algebraic attack linearize

1. Introduction

With the emergence and rapid development of cloud computation, fog computation and edge computation, multiparty secure computation and fully homomorphic encryption [17] play vitally important roles in ciphertext data searching and processing. Correspondingly, new requirements and challenges for the performance of cryptographic algorithms have been proposed and are receiving attention. For a good cryptographic primitive, executing efficiently on software and hardware scenarios and possessing high security are essential characteristics. However, in fully homomorphic encryption, the cost of executing the AND operation is usually higher than that of the XOR operation. In this case, in addition to the traditional performance described above, the cryptographic algorithm should also realize minimizing the number of AND operations. Therefore, the design of cryptographic primitives with efficiency, high security and a bare minimum number of AND operations is a trending issue in the area of cryptography.

During the past six years, many symmetric primitives applied to fully homomorphic encryption have been proposed, such as LowMC [2], Kreyvium [5], FLIP [16], RASTA [8], Mimc [1], HADES [12], and Ciminion [9]. In particular, LowMC, Kreyvium and FLIP encryption algorithms achieve outstanding implementation and minimize the number of AND operations since the designers adopted the strategies of reducing AND depth (i.e., number of rounds) or the number of ANDs per encrypted bit. More concretely, the minimal AND depth of LowMC (or Kreyvium) is 11, and the number of ANDs per encrypted bit is only 3 or 4. On the other hand, the AND depth of FLIP is quite small, i.e., 4, but its number of ANDs per encrypted bit reaches 1072. Actually, both the minimal AND depth and the number of ANDs per encrypted bit of these encryption primitives cannot be simultaneously optimal. To trade off these two parameters, Leander designed RASTA [8], a stream cipher based on the ASASA structure [4]. Clearly, the key feed-forward operation is utilized in RASTA, and the linear layer and nonlinear layer are selected alternately. In particular, RASTA achieved d AND depth and d ANDs per bit at the same time, where $d \in {4, 5, 6}$ . Since this novel design concept can reduce these two parameters simultaneously and effectively, RASTA has received extensive attention. However, one issue is that all linear layers of RASTA are generated by KECCAK [20], which is quite time-consuming. To further solve this issue, Hebborn and Leander proposed the DASTA cipher [14], whose linear layer is replaced by a combination of an ever-changing bit-wise permutation and a deterministic linear transformation. Such a new construction has made DASTA 100× times faster than RASTA in offline settings.

DASTA is a streaming cipher, and the ciphertext stream is generated by the XORing plaintext stream and key stream. The novelty of DASTA is that the plaintext stream $m$ is divided first into N blocks: $m_{0}, m_{1}, \dots, m_{N - 1}$ ; then, the i-th ciphertext block $c_{i}$ is generated by $m_{i} \oplus Z_{i}$ , where $Z_{i}$ is the i-th key block, and the block size is denoted as n there in after. Therefore, the generating method of key block $Z_{i}$ from master key $K$ is the core technique of DASTA. As shown in Fig. 1, $K$ passes through the i-th key block generator to generate the i-th key block $Z_{i}$ which can be represented as (1). Additionally, the i-th ciphertext $c_{i} = m_{i} \oplus Z_{i}$ , $0 ⩽ i < N$ , where i refers to the block counter and N is also the number of times the master key can be used. To protect DASTA against algebraic attacks, the designers imposed a restriction that $N ⩽ ⌈ 2^{s / 2} / n ⌉$ , where s is the security level. $\begin{matrix} (1) & Z_{i} = f_{i} (K) \oplus K = L \circ P_{r, i} \circ χ \circ L \circ P_{r - 1, i} \circ \dots \circ χ \circ L \circ P_{1, i} \circ χ \circ L \circ P_{0, i} (K) \oplus K, \end{matrix}$ where $0 ⩽ i < N$ , L is a linear transformation, $P_{\cdot, i}$ is a bit-wise permutation, χ is a nonlinear transformation, and r is the number of rounds. The details of L, $P_{\cdot, i}$ , and χ are provided in Section 2.

The designers of DASTA recommend that a master key can be used to encrypt at most $⌈ 2^{s / 2} / n ⌉$ plaintext blocks, this allows DASTA to effectively resist attacks that need to collect a large number of plaintext and ciphertext pairs under a single key model, such as differential analysis and cube attack. On the other hand, since the nonlinear layer χ is a quadratic function, the designers deduced that the upper bound of the algebraic degree of r-round DASTA reaches $2^{r}$ . Correspondingly, if DASTA is analyzed by algebraic cryptanalysis, the upper bound of the number of monomials in algebraic equations is $\sum_{i = 0}^{2^{r}} (\binom{n}{i})$ . In this case, the designers believe the algebraic cryptanalysis can be effective only if the time complexity is less than $2^{s}$ , i.e., ${(\sum_{i = 0}^{2^{r}} (\binom{n}{i}))}^{2.37} ⩽ 2^{s}$ , where the exponent of the Gaussian elimination method is fixed to 2.37. However, low algebraic order equations can be further derived by combining the property of χ, the key feed-forward operation, and one bit information of $L^{- 1} \cdot K$ so that the time complexity of algebraic attack can be reduced to $2 {(\sum_{i = 0}^{2^{r - 1}} (\binom{n}{i}))}^{2.37}$ in [15]. Thus, four instances of DASTA cipher family will be broken if they are reduced to $r - 1$ round. In fact, only one algebraic equation can be attained in one block counter by the method in [15]; thus, the data complexity of this attack is very high.

In this article, an algebraic attack on the DASTA cipher with lower data complexity is proposed. The key feed forward operation, the properties of the nonlinear layer and the invariance of the linear transformation in the linear layer are successfully utilized in our attack. In particular, one bit of $L^{- 1} \cdot K$ is first fixed and then combined with three relations between the input and output of the χ operation [13,15,19], two or three equations can be collected. Since more equations are attained from one plaintext–ciphertext pair $(m_{i}, c_{i})$ , the data complexity is effectively reduced. Based on this method, three different attack models are proposed, namely, Model 1, Model 2, and Model 3.

Model 1. In the counter where the fixed bit of $L^{- 1} \cdot K$ is not equivalent to $L^{- 1} \cdot (m_{i} \oplus c_{i})$ , three linearly independent equations in terms of $k_{0}, k_{1}, \dots, k_{n - 1}$ can be attained from the relations between the input and output of the last χ operation. An equation system will be formed by such equations that are obtained in these kinds of counters so that an algebraic attack on DASTA can be implemented.

Model 2. Note that in the counter where the fixed bit of $L^{- 1} \cdot K$ is equivalent to $L^{- 1} \cdot (m_{i} \oplus c_{i})$ , one of the relations between the input and output of the last χ operation is invalid; however, other relations are always valid. In Model 2, the invalid relation is abandoned, and two linearly independent equations in terms of $k_{0}, k_{1}, \dots, k_{n - 1}$ can be attained from other two relations in any counter. This means that there is no constraint condition on the plaintext–ciphertext pair in Model 2.

Model 3. A flexible strategy is adopted in Model 3. Specifically, in the counter where the fixed bit of $L^{- 1} \cdot K$ is not equivalent to $L^{- 1} \cdot (m_{i} \oplus c_{i})$ , three linearly independent equations in terms of $k_{0}, k_{1}, \dots, k_{n - 1}$ are attained from the three relations between the input and output of the last χ operation; in the counter where the fixed bit of $L^{- 1} \cdot K$ is equivalent to $L^{- 1} \cdot (m_{i} \oplus c_{i})$ , two linearly independent equations are collected from the always valid relations. Note that there is also no constraint condition on the plaintext–ciphertext pair in Model 3. However, compared to Model 2, the relations between the input and output of the last χ operation are utilized more effectively in Model 3.

Under the assumption that the plaintext–ciphertext pair satisfies the constraint condition, the data complexity of our attack model named Model 1 is 66.67% less compared to that of [15]. Under the assumption that plaintext–ciphertext pair is arbitrary, the data complexities of our attack models named Model 2 and Model 3 can be respectively decreased to $50 %$ and $41.67 %$ . It is illustrated that four $(r - 1)$ -round instances of DASTA cipher family are broken, two $(r - 2)$ -round instances and one $(r - 3)$ -round instance are broken by our attack, where r is the iterative number of round operations.

The structure of this paper is given below. In Section 2, the concept of algebraic attack and the details of DASTA are introduced. In Section 3, the method that attains more algebraic equations with low algebraic degrees is investigated. Based on this method, different algebraic attack models on DASTA are proposed in Section 4 and Section 5. Section 6 offers a summary.

Fig. 1.

Generation of key stream of DASTA.

2. Preliminaries

2.1. Algebraic attack

The algebraic attack is a classic method used to analyze the security of stream ciphers, and its core concept can be described as follows. Let the master key of a given cipher be $K = (k_{0}, k_{1}, \dots, k_{n - 1})$ . Assume the opponent can establish an equation system in terms of $k_{0}, k_{1}, \dots k_{n - 1}$ below: $\begin{matrix} (2) & \{\begin{matrix} F_{0} (k_{0}, k_{1}, \dots, k_{n - 1}) = z_{0} \\ F_{1} (k_{0}, k_{1}, \dots, k_{n - 1}) = z_{1} \\ ⋮ \end{matrix} \end{matrix}$ where $F_{i} (k_{0}, k_{1}, \dots k_{n - 1})$ is polynomial in terms of $k_{0}, k_{1}, \dots k_{n - 1}$ . Clearly, once this multiple polynomial system is solved, then $K$ will be attained. Note that if the algebraic degree of a multiple polynomial system with n variables is d, then there are at most $\sum_{i = 0}^{d} (\binom{n}{i})$ monomials in this system.

During the past two decades, many techniques looking for the solution of multiple polynomial systems have been discussed since algebraic attacks were proposed, e.g., the linearization method [3], the guessing and determination method [18], the F4/F5 algorithm [10,11] and the XL algorithm [6]. Due to its convenience in implementation and evaluation, the linearization method has been widely used in the analysis of various classic cryptographic algorithms [7,13,19]. In fact, there are two important steps in the linearization method. First, each monomial in system (2) is renamed with a new variable, which can convert system (2) into a linear system. Moreover, the Gaussian elimination method is utilized to solve the new linear system. Essentially, the complexity of attack is determined by the complexity of the Gaussian elimination to solve the linear system. Let the exponent of Gaussian elimination be ω, the number of new variables be U, and the number of binary operations required to encrypt a plaintext be denoted by V. Then, there are two approaches for evaluating the time complexity T of attack, i.e., $T = U^{ω}$ (if $ω = 2.37$ ) and $T = U^{ω} / V$ (if $ω = 2.8$ ).

2.2. The components of DASTA

The basic structure of DASTA is depicted in Section 1, the components of $f_{i}$ in the key stream generator are introduced below. As described in (1), $f_{i}$ is a composition of round functions, $0 ⩽ i < N$ . Specifically, $\begin{matrix} f_{i} (x) = L \circ P_{r, i} \circ χ \circ L \circ P_{r - 1, i} \circ \dots \circ χ \circ L \circ P_{1, i} \circ χ \circ L \circ P_{0, i} (x), x \in F_{2}^{n} \end{matrix}$ where L is a linear transformation, $P_{\cdot, i}$ is a bite-wise permutation, and χ is a nonlinear transformation.

The matrix of L is the transposition of the generation matrix of the BCH code, and since the details of L do not affect the effect of our attack, they will not be repeated here. The nonlinear transformation χ is the nonlinear component used in KECCAK, and the relationship between the input ( $x_{0}, x_{1}, \dots, x_{n - 1}$ ) and the output ( $y_{0}, y_{1}, \dots, y_{n - 1}$ ) of χ can be described as follows: $\begin{matrix} (3) & y_{i} = x_{i} \oplus x_{i + 1} x_{i + 2} \oplus x_{i + 2}, \end{matrix}$ where the indices are considered within modulo n. χ is reversible only if the number of input variables is odd, which implies that the block size of DASTA should also be odd.

The bit-wise permutations adopted in DASTA can be represented as the multiplication of mutually disjoint rotations. In particular, the types of these rotations are consistent, which can be described via an instance $φ (1) = 2, φ (2) = 3, \dots, φ (k) = 1$ . The designers of DASTA represented the bit-wise permutation as product of cycles. For example, $\begin{array}{rcl} τ (1) = 2, τ (2) = 1, τ (3) = 4, τ (4) = 5, τ (5) = 3 . \end{array}$ Such a bit-wise permutation is denoted as $τ = (1 2) (3 4 5)$ , and simplified further as $g (2, 3)$ in [14]. (Note that τ is not the bit-wise permutation used in DASTA.)

There are seven DASTA instances in total, and the parameters are represented as $(n, r, s)$ , where n is the block size, r is the number of iterations for each key block generator, and s is the security level. The designers specified that the master key $K$ can encrypt up to $⌈ 2^{s / 2} / n ⌉$ plaintext blocks and denote $⌈ 2^{s / 2} / n ⌉$ as N. The parameters and bit-wise permutations of seven instances are provided in the Appendix.

3. Linearization and algebraic attack on DASTA

The states of the master key $K = (k_{0}, k_{1}, \dots k_{n - 1})$ in the i-th block counter can be illustrated below: $\begin{matrix} K : = α^{0} \overset{P_{0, i}}{\to} β^{0} \overset{L}{\to} γ^{0} \overset{χ}{\to} α^{1} \overset{P_{1, i}}{\to} β^{1} \overset{L}{\to} γ^{1} \overset{χ}{\to} \dots \overset{L}{\to} γ^{r - 1} \overset{χ}{\to} α^{r} \overset{P_{r, i}}{\to} β^{r} \overset{L}{\to} γ^{r} \end{matrix}$ Clearly, χ is the only nonlinear operation in the encryption function. Note that the low-degree algebraic equations derived from χ will be successfully exploited in the attack. Let $γ^{r - 1} = (a_{0}, a_{1}, \dots, a_{n - 1})$ be the input of χ in the $(r - 1)$ -th round, where $a_{i}$ is polynomial in terms of $k_{0}, k_{1}, \dots, k_{n - 1}$ with $2^{r - 1}$ algebraic degree. Similarly, let $α^{r} = (b_{0}, b_{1}, \dots, b_{n - 1})$ be the output of χ in the $(r - 1)$ -th round. The i-th key block can be derived by (1), i.e., $Z_{i} = γ^{r} \oplus K$ . On the other hand, $Z_{i} = m_{i} \oplus c_{i}$ , and thus $γ^{r} = K \oplus m_{i} \oplus c_{i}$ , where $m_{i}$ is the i-th plaintext block and $c_{i}$ is the i-th ciphertext block. Since L is linear, we have $\begin{matrix} (4) & α^{r} = P_{r, i}^{- 1} (L^{- 1} \cdot K \oplus L^{- 1} \cdot (m_{i} \oplus c_{i})) . \end{matrix}$ Moreover, $b_{i}$ is a linear function in terms of $k_{0}, k_{1}, \dots, k_{n - 1}$ since $m_{i} \oplus c_{i}$ is a constant and $P_{r, i}^{- 1}$ is a bit-wise permutation $(i = 0, 1, \dots, n - 1)$ .

Fig. 2.

The input and output of χ in the $(r - 1)$ -th round.

In brief, based on the key feed-forward operation in DASTA, the nonlinear component χ in the $(r - 1)$ -th round is utilized to attain Equation $χ (a_{0}, a_{1}, \dots, a_{n - 1}) = (b_{0}, b_{1}, \dots, b_{n - 1})$ , where $a_{j}$ is a polynomial in terms of $k_{0}, k_{1}, \dots, k_{n - 1}$ with $2^{r - 1}$ algebraic degree, $b_{j}$ is a linear function in terms of $k_{0}, k_{1}, \dots k_{n - 1}$ , $j = 0, 1, \dots, n - 1$ .

In the implementation of an algebraic attack on DASTA, Liu observed that there is a relation between bit $a_{j}$ of input $(a_{0}, a_{1}, \dots, a_{n - 1})$ of χ and bit $b_{j}$ of output $(b_{0}, b_{1}, \dots, b_{n - 1})$ as follows [15]: $\begin{matrix} (5) & b_{j} \oplus a_{j} \oplus b_{j + 1} a_{j + 2} \oplus a_{j + 2} = 0, \end{matrix}$ where the indices are considered within modulo n.

In practical collision attacks against round-reduced SHA-3 (χ is also the core component of the round function of SHA-3), Guo adopted the relation between $a_{j}$ and $b_{j}$ as follows [13]: $\begin{matrix} (6) & b_{j + 1} (b_{j} b_{j - 1} \oplus b_{j} \oplus b_{j - 2} \oplus a_{j - 2}) = 0 . \end{matrix}$

When researching the inverse operation of χ, Rajasree found another relation between $a_{j}$ and $b_{j}$ [19]: $\begin{matrix} (7) & a_{j - 3} \oplus b_{j - 3} \oplus b_{j - 1} \oplus b_{j + 1} \oplus b_{j - 2} b_{j - 1} \oplus b_{j - 2} b_{j + 1} \oplus b_{j} b_{j + 1} \oplus b_{j - 2} b_{j} b_{j + 1} = 0 . \end{matrix}$

Note that if $r > 2$ , then the upper bounds of the algebraic degrees of (5) and (6) are $2^{r - 1} + 1$ ; and if $r > 3$ , then the upper bound of the algebraic degree of (7) is $2^{r - 1}$ .

While generating the key stream, the same linear transformation L is used for different counters; thus, $L^{- 1} \cdot K$ is invariant. Let $L^{- 1} \cdot K = (σ_{0}, σ_{1}, \dots, σ_{n - 1})$ ; then, $σ_{i}$ is a linear combination of $k_{0}, k_{1}, \dots, k_{n - 1}$ and $0 ⩽ i < n - 1$ . According to (4) and Fig. 2, $β_{i}^{r} = σ_{i} \oplus L^{- 1} \cdot (m_{i} \oplus c_{i})$ , $0 ⩽ i < n - 1$ . Therefore, if the $j^{*}$ -th bit $σ_{j^{*}}$ of σ is fixed, then the $j^{*}$ -th bit $β_{j^{*}}^{r}$ of $β^{r}$ is fixed correspondingly, and the value of $β_{j^{*}}^{r}$ can be determined via the plaintext–ciphertext pair $(m_{i}, c_{i})$ in the i-th block counter. Furthermore, the corresponding fixed bit of $α^{r}$ can be determined by permutation $P_{r, i}^{- 1}$ . Assuming that the fixed bit of $α^{r}$ is the $(j + 1)$ -th bit $b_{j + 1}$ , then $b_{j + 1} = β_{j^{*}}^{r}$ i.e. $b_{j + 1}$ is fixed and its value can be calculated by $(m_{i}, c_{i})$ . It is not difficult to find that if $b_{j + 1} = 1$ , then the upper bounds of the algebraic degrees of (5), (6) and (7) are reduced to $2^{r - 1}$ ; if $b_{j + 1} = 0$ , then the upper bounds of the algebraic degrees of (5) and (7) are reduced to $2^{r - 1}$ , but (6) is invalid. In summary, by fixing one bit of $L^{- 1} \cdot K$ , the equations in terms of $k_{0}, k_{1}, \dots, k_{n - 1}$ can be attained from (5), (6) and (7) except when (6) is invalid, and the algebraic degrees of these equations are at most $2^{r - 1}$ . When enough equations are obtained in different counters, they can form an equation system with an algebraic degree of at most $2^{r - 1}$ , and then an algebraic attack can be implemented by linearizing this equation system. It is the core technique adopted in Model 1, Model 2 and Model 3.

4. The algebraic attack for certain plaintext–ciphertext pairs

Based on the method described in Section 3, an algebraic attack for certain plaintext–ciphertext pairs is proposed, namely, Model 1. The core concept of Model 1 is choosing the proper plaintext–ciphertext pair $(m_{i}, c_{i})$ to ensure the validity of (6) and obtaining an equation in terms of $k_{0}, k_{1}, \dots, k_{n - 1}$ with $2^{r - 1}$ degree from (5), (6) and (7). Note that (6) will be invalid if $b_{j + 1} = 0$ , and $b_{j + 1} = 0$ if and only if $σ_{j^{*}} = L^{- 1} \cdot (m_{j^{*}} \oplus c_{j^{*}})$ . Thus, if the plaintext–ciphertext pair $(m_{j^{*}}, c_{j^{*}})$ satisfies $σ_{j^{*}} \neq L^{- 1} \cdot (m_{j^{*}}, c_{j^{*}})$ , then we have $b_{j + 1} = 1$ . We choose the proper counters to ensure that the plaintext–ciphertext pair satisfies this constraint condition; then, three linearly independent equations can be obtained by (5), (6) and (7) as follows: $\begin{array}{l} b_{j} \oplus a_{j} = 0, \\ b_{j} b_{j - 1} \oplus b_{j} \oplus b_{j - 2} \oplus a_{j - 2} = 0, \\ a_{j - 3} \oplus b_{j - 3} \oplus b_{j - 1} \oplus b_{j - 2} b_{j - 1} \oplus b_{j - 2} \oplus b_{j} \oplus b_{j - 2} b_{j} = 1 . \end{array}$ When $r ⩾ 2$ , the upper bounds of the algebraic degrees of equations above are all $2^{r - 1}$ ; thus, there are at most $\sum_{i = 0}^{2^{r - 1}} (\binom{n}{i})$ monomials, i.e., at most $\sum_{i = 0}^{2^{r - 1}} (\binom{n}{i})$ new variables will exist in the linearized equations. In this case, the attacker has to collect at least $\sum_{i = 0}^{2^{r - 1}} (\binom{n}{i})$ equations, denoted by $\sum_{i = 0}^{2^{r - 1}} (\binom{n}{i}) = U$ . Although a large number of equations can be obtained by this method, we only discuss the case in which the number of equations is equal to the number of new variables, which implies storage complexity $M = U^{2}$ . Note that three linearly independent equations can be obtained in the block counter where $b_{j + 1} = 1$ , and the probability of $b_{j + 1} = 1$ is 0.5; thus, the data complexity $D = 2 U / 3$ . Since only one bit of $σ$ is guessed, if $ω = 2.37$ , then the time complexity $T = 2 U^{2.37}$ ; if $ω = 2.8$ , then $T = 2 U^{2.8} / ((R + 1) n^{2})$ , where R is the number of attacked rounds. The designers of DASTA recommend that the master key can encrypt up to $⌈ 2^{s / 2} / n ⌉$ plaintext blocks; thus, $2 U / 3 < ⌈ 2^{s / 2} / n ⌉$ is the necessary condition that the attack can be implemented. According to this rule, at most $2^{s / 2}$ equations can be collected; if the time complexity is $T < {(2^{s / 2})}^{2}$ , then the cipher is not secure. More concretely, for the standard r-round DASTA, four $(r - 1)$ -round instances will be broken, two $(r - 2)$ -round instances will be broken, and one $(r - 3)$ -round instance will also be broken by utilizing this attack model (see Table 1).

Table 1
The data complexity of attack Model 1 (for certain plaintext–ciphertext pairs)

Instance R ${log}_{2} U$ ${log}_{2} M$ ${log}_{2} D$ ${log}_{2} T$ ω Ref.

DASTA80-6 3 27 54 27 65 2.37 [15]

26.4 Our

27 59.1 2.8 [15]

26.4 Our

DASTA80-4 3 29 58 29 69.8 2.37 [15]

28.4 Our

29 62.5 2.8 [15]

28.4 Our

DASTA128-6 4 53 106 53 126.6 2.37 [15]

52.4 Our

53 * 2.8 [15]

52.4 Our

DASTA128-5 3 32 64 32 76.9 2.37 [15]

31.4 Our

32 70.6 2.8 [15]

31.4 Our

DASTA128-4 3 39 78 39 93.5 2.37 [15]

38.4 Our

39 87.2 2.8 [15]

38.4 Our

DASTA256-6 5 107 214 107 254.6 2.37 [15]

106.4 Our

107 * 2.8 [15]

106.4 Our

DASTA256-5 4 80 160 80 190.7 2.37 [15]

79.4 Our

80 200 2.8 [15]

79.4 Our

Instance	R	${log}_{2} U$	${log}_{2} M$	${log}_{2} D$	${log}_{2} T$	ω	Ref.
DASTA80-6	3	27	54	27	65	2.37	[15]
26.4	Our
27	59.1	2.8	[15]
26.4	Our
DASTA80-4	3	29	58	29	69.8	2.37	[15]
28.4	Our
29	62.5	2.8	[15]
28.4	Our
DASTA128-6	4	53	106	53	126.6	2.37	[15]
52.4	Our
53	*	2.8	[15]
52.4	Our
DASTA128-5	3	32	64	32	76.9	2.37	[15]
31.4	Our
32	70.6	2.8	[15]
31.4	Our
DASTA128-4	3	39	78	39	93.5	2.37	[15]
38.4	Our
39	87.2	2.8	[15]
38.4	Our
DASTA256-6	5	107	214	107	254.6	2.37	[15]
106.4	Our
107	*	2.8	[15]
106.4	Our
DASTA256-5	4	80	160	80	190.7	2.37	[15]
79.4	Our
80	200	2.8	[15]
79.4	Our

R, M, D and T denote the number of attacked rounds, memory complexity, data complexity and time complexity, respectively.

* means that the corresponding time complexity exceeds the claimed security level.

Similar to the discussion proposed in [15], the time complexity and storage complexity of attack Model 1 are the same as those of attack in [15] (the same results can be applied to Model 2 and Model 3). However, the data complexity of our attack can be further decreased to $66.67 %$ of the data complexity of the attack in [15] (also see Table 1). Actually, $0.6667 \approx 2^{- 0.6}$ ; if the data complexity of [15] is $2^{ϵ}$ , then the data complexity of this model will be $2^{ϵ - 0.6}$ . It is illustrated that the data complexity can be effectively reduced by choosing proper plaintext–ciphertext pairs (i.e., choosing a proper block counter).

Algorithm 1 (Attack Model 1 (for certain plaintext–ciphertext pairs)).

Let $u = 0$ ;

In the i-th block counter (i starts at 0), fix the $j^{*}$ -th bit $σ_{j^{*}}$ of $σ$ ;

Compute the value of the fixed bit $b_{j + 1}$ of $α^{r} = P_{r, i}^{- 1} (L^{- 1} \cdot K \oplus L^{- 1} \cdot (m_{i} \oplus c_{i}))$ ;

If $b_{j + 1} = 0$ , then $i = i + 1$ , and repeat 2, 3;

If $b_{j + 1} = 1$ , then three equations can be obtained:

$b_{j} + a_{j} = 0$ ,

$b_{j} b_{j - 1} \oplus b_{j} \oplus b_{j - 2} \oplus a_{j - 2} = 0$ ,

$a_{j - 3} \oplus b_{j - 3} \oplus b_{j - 1} \oplus b_{j - 2} b_{j - 1} \oplus b_{j - 2} \oplus b_{j} \oplus b_{j - 2} b_{j} = 1$ ;

$i = i + 1$ , $u = u + 3$

If $u < \sum_{i = 0}^{2^{r - 1}} (\binom{n}{i})$ , then repeat 2 to 4;

If $u ⩾ \sum_{i = 0}^{2^{r - 1}} (\binom{n}{i})$ , then combine these equations into a system, and solve this system.

5. Algebraic attacks for arbitrary plaintext–ciphertext pairs

The core concept of Model 1 is to obtain equations in terms of $k_{0}, k_{1}, \dots, k_{n - 1}$ only when $b_{j + 1} = 1$ . As described in Section 4, $b_{j + 1} = 1$ if and only if the plaintext–ciphertext pair satisfies $σ_{j^{*}} \neq L^{- 1} \cdot (m_{j^{*}} \oplus c_{j^{*}})$ ; this restriction results in the data complexity of Model 1 being less than 66.67% compared to that of [15]. In this section, two different attack models are adopted to eliminate this restriction, and the data complexity is further reduced.

Model 2

The implementation of Model 2 is also based on the method described in Section 3; however, (6) is abandoned in this model, and only (5) and (7) are used to obtain equations in terms of

k_{0}, k_{1}, \dots, k_{n - 1}

. Specifically, if

b_{j + 1} = 0

, then two linearly independent equations can be derived below.

\begin{array}{l} b_{j} \oplus a_{j} \oplus a_{j + 2} = 0, \\ a_{j - 3} \oplus b_{j - 3} \oplus b_{j - 1} \oplus b_{j - 2} b_{j - 1} = 0 . \end{array}

b_{j + 1} = 1

, then there are another two linearly independent equations:

\begin{array}{l} b_{j} \oplus a_{j} = 0, \\ a_{j - 3} \oplus b_{j - 3} \oplus b_{j - 1} \oplus b_{j - 2} b_{j - 1} \oplus b_{j - 2} \oplus b_{j} \oplus b_{j - 2} b_{j} = 1 . \end{array}

Similar to the discussion in attack Model 1, the attacker has to obtain at least

\sum_{i = 0}^{2^{r - 1}} (\binom{n}{i})

equations. Since two linearly independent equations can be collected in one block counter, the data complexity

D = U / 2

. Only one bit of

σ

is guessed; if

ω = 2.37

, then the time complexity

T = 2 U^{2.37}

; if

ω = 2.8

, then

T = 2 U^{2.8} / ((R + 1) n^{2})

, where R is the number of attacked rounds. The designers of DASTA recommend that the master key can encrypt up to

⌈ 2^{s / 2} / n ⌉

plaintext blocks; thus,

U / 2 < ⌈ 2^{s / 2} / n ⌉

is the necessary condition under which the attack can be implemented. According to this rule, at most

2^{s / 2}

equations can be collected; if the time complexity

T < {(2^{s / 2})}^{2}

, then the cipher is not secure. It is illustrated that for the standard r-round DASTA, four

(r - 1)

-round instances(DASTA80-4, DASTA128-4, DASTA256-6, DASTA256-5) will be broken, two

(r - 2)

-round instances (DASTA128-6, DASTA128-5) will be broken, and one

(r - 3)

-round instance(DASTA80-6) will also be broken by utilizing this attack model.

Note that two equations can be collected from arbitrary plaintext–ciphertext pairs; thus, the data complexity can be further decreased to $50 %$ of the data complexity in [15] (see Table 2). Since $1 / 2 = 2^{- 1}$ , if the data complexity in [15] is $2^{ϵ}$ , then the data complexity of this model will be $2^{ϵ - 1}$ . It is illustrated that the data complexity can be further reduced by utilizing equations that are always effective. The specific procedure is shown in Algorithm 2.

Algorithm 2 (Attack Model 2 (for arbitrary plaintext–ciphertext pair)).

Let $u = 0$ ;

In the i-th block counter (i starts at 0), fix the $j^{*}$ -th bit $σ_{j^{*}}$ of $σ$ ;

Compute the value of fixed bit $b_{j + 1}$ of $α^{r} = P_{r, i}^{- 1} (L^{- 1} \cdot K \oplus L^{- 1} \cdot (m_{i} \oplus c_{i}))$ ;

If $b_{j + 1} = 0$ , then two equations can be obtained:

$b_{j} \oplus a_{j} \oplus a_{j + 2} = 0$ ,

$a_{j - 3} \oplus b_{j - 3} \oplus b_{j - 1} \oplus b_{j - 2} b_{j - 1} = 0$ ;

If $b_{j + 1} = 1$ , then another two equations can be obtained:

$b_{j} + a_{j} = 0$ ,

$a_{j - 3} \oplus b_{j - 3} \oplus b_{j - 1} \oplus b_{j - 2} b_{j - 1} \oplus b_{j - 2} \oplus b_{j} \oplus b_{j - 2} b_{j} = 1$ ;

$i = i + 1$ , $u = u + 2$

If $u < \sum_{i = 0}^{2^{r - 1}} (\binom{n}{i})$ , then repeat 2 to 4;

If $u ⩾ \sum_{i = 0}^{2^{r - 1}} (\binom{n}{i})$ , then combine these equations into a system, and solve this system.

Model 3

This model is still basesd on the method described in Section 3, differing from Model 2, a flexible strategy to use (5), (6) and (7) is adopted in Model 3. Specifically, we only use (5) and (7) if

b_{j + 1} = 0

, since (6) is invalid in this kind of counter. We use (5), (6) and (7) if

b_{j + 1} = 1

, since they are always valid. Specifically, if

b_{j + 1} = 0

, then two linearly independent equations can be derived:

\begin{array}{l} b_{j} \oplus a_{j} \oplus a_{j + 2} = 0, \\ a_{j - 3} \oplus b_{j - 3} \oplus b_{j - 1} \oplus b_{j - 2} b_{j - 1} = 0 . \end{array}

b_{j + 1} = 1

, then there are another three linearly independent equations:

\begin{array}{l} b_{j} \oplus a_{j} = 0, \\ b_{j} b_{j - 1} \oplus b_{j} \oplus b_{j - 2} \oplus a_{j - 2} = 0, \\ a_{j - 3} \oplus b_{j - 3} \oplus b_{j - 1} \oplus b_{j - 2} b_{j - 1} \oplus b_{j - 2} \oplus b_{j} \oplus b_{j - 2} b_{j} = 1 . \end{array}

Table 2
The data complexity of attack Model 2 (for arbitrary plaintext–ciphertext pair)

DASTA 80-6 80-4 128-6 128-5 128-4 256-6 256-5 Ref.

${log}_{2}^{D}$ 27 29 53 32 39 107 80 [15]

${log}_{2}^{D}$ 26 28 52 31 38 106 79 Our

DASTA	80-6	80-4	128-6	128-5	128-4	256-6	256-5	Ref.
${log}_{2}^{D}$	27	29	53	32	39	107	80	[15]
${log}_{2}^{D}$	26	28	52	31	38	106	79	Our

Similarly, the attacker has to obtain at least $\sum_{i = 0}^{2^{r - 1}} (\binom{n}{i})$ equations. Since two linearly independent equations can be collected in the block counter where $b_{j + 1} = 0$ , three linearly independent equations can be collected in the block counter where $b_{j + 1} = 1$ , and the probabilities of $b_{j + 1}$ being either 0 or 1 are 0.5; thus, the data complexity $D = (1 / 2) \times (U / 2) + (1 / 2) \times (U / 3) = 5 U / 12$ . Since only one bit of $σ$ is guessed; if let $ω = 2.37$ , then the time complexity $T = 2 U^{2.37}$ ; if let $ω = 2.8$ , then $T = 2 U^{2.8} / ((R + 1) n^{2})$ , where R is the number of attacked rounds. The designers of DASTA recommend that the master key can encrypt up to $⌈ 2^{s / 2} / n ⌉$ plaintext blocks; thus, $5 U / 12 < ⌈ 2^{s / 2} / n ⌉$ is the necessary condition under which the attack can be implemented. According to this rule, at most $2^{s / 2}$ equations can be collected; if the time complexity $T < {(2^{s / 2})}^{2}$ , then the cipher is not secure. It is illustrated that for the standard r-round DASTA, four $(r - 1)$ -round instances (DASTA80-4, DASTA128-4, DASTA256-6, DASTA256-5) will be broken, two $(r - 2)$ -round instances (DASTA128-6, DASTA128-5) will be broken, and one $(r - 3)$ -round instance (DASTA80-6) will also be broken by utilizing this attack model.

To summarize, by collecting two equations in the block counter where $b_{j + 1} = 0$ and three equations in the block counter where $b_{j + 1} = 1$ , the data complexity can be further decreased to $41.67 %$ of the data complexity of attack in [15] (see Table 3). Since $5 / 12 \approx 2^{- 1.3}$ , if the data complexity in [15] is $2^{ϵ}$ , then the data complexity of this attack model will be $2^{ϵ - 1.3}$ . The data complexity can be significantly reduced by using this flexible collecting strategy. The specific procedure is shown in Algorithm 3.

Table 3

The data complexity of attack Model 3 (for arbitrary plaintext–ciphertext pair)

DASTA	80-6	80-4	128-6	128-5	128-4	256-6	256-5	Ref.
${log}_{2}^{D}$	27	29	53	32	39	107	80	[15]
${log}_{2}^{D}$	25.7	27.7	51.7	30.7	37.7	105.7	78.7	Our

Algorithm 3 (Attack Model 3 (for arbitrary plaintext–ciphertext pair)).

Let $u = 0$ ;

In the i-th block counter (i starts at 0), fix the $j^{*}$ -th bit $σ_{j^{*}}$ of $σ$ ;

Compute the value of fixed bit $b_{j + 1}$ of $α^{r} = P_{r, i}^{- 1} (L^{- 1} \cdot K \oplus L^{- 1} \cdot (m_{i} \oplus c_{i}))$ ;

If $b_{j + 1} = 0$ , then two equations can be obtained:

$b_{j} \oplus a_{j} \oplus a_{j + 2} = 0$ ,

$a_{j - 3} \oplus b_{j - 3} \oplus b_{j - 1} \oplus b_{j - 2} b_{j - 1} = 0$ ;

If $b_{j + 1} = 1$ , then three equations can be obtained:

$b_{j} + a_{j} = 0$ ,

$b_{j} b_{j - 1} \oplus b_{j} \oplus b_{j - 2} \oplus a_{j - 2} = 0$ ,

$a_{j - 3} \oplus b_{j - 3} \oplus b_{j - 1} \oplus b_{j - 2} b_{j - 1} \oplus b_{j - 2} \oplus b_{j} \oplus b_{j - 2} b_{j} = 1$ ;

$i = i + 1$ , if $b_{j + 1} = 0$ , then $u = u + 2$ ; if $b_{j + 1} = 1$ , then $u = u + 3$ .

If $u < \sum_{i = 0}^{2^{r - 1}} (\binom{n}{i})$ , then repeat 2 to 4;

If $u ⩾ \sum_{i = 0}^{2^{r - 1}} (\binom{n}{i})$ , then combine these equations into a system, and solve this system.

6. Conclusions

In this article, the security of fully homomorphic encryption friendly symmetric-key primitives DASTA is evaluated by using a new algebraic attack with three different models. The key feed-forward operation, the properties of the nonlinear layer and the invariance of the linear transformation in the linear layer are successfully utilized in this attack. In particular, the data complexity of this attack can be effectively reduced. Compared with the previous best known result, the data complexity of our attack Model 1 is reduced by $33.33 %$ ; the data complexity of our attack Model 2 is reduced by $50 %$ ; and the data complexity of our attack Model 3 is reduced by $58.33 %$ . It is illustrated that four $(r - 1)$ -round instances of the seven instances in the DASTA cipher family are broken, two $(r - 2)$ -round instances and one $(r - 3)$ -round instance are also broken by this attack.

Conflict of interest

None to report.

Footnotes

DASTA instances

Table 4

The DASTA cipher family

Instance	$(n, r, s)$	Permutation	$(P_{0, i}, P_{1, i}, \dots, P_{r, i})$
DASTA 80-6	$(219, 6, 80)$	$π = g (5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 27)$	$(π^{i}, π^{i_{0}}, π^{i_{1}}, π^{i_{0}}, π^{i_{1}}, π^{i_{0}}, π^{i_{1}})$
DASTA 80-4	$(327, 4, 80)$	$π_{0} = g (13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 27)$ $π_{1} = g (17, 19, 23, 29, 31, 37, 41, 43, 47, 40)$	$(π^{i}, π^{i_{0}}, π^{i_{1}}, π^{i_{0}}, π^{i_{1}}, π^{i_{0}}, π^{i_{1}})$
DASTA 128-6	$(351, 6, 128)$	$π = g (3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 25)$	$(π^{i}, π^{i_{0}}, π^{i_{1}}, π^{i_{0}}, π^{i_{1}}, π^{i_{0}}, π^{i_{1}})$
DASTA 128-5	$(525, 5, 128)$	$π_{0} = g (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 24)$ $π_{1} = g (29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 57)$	$(π_{0}^{i}, π_{0}^{i}, π_{1}^{i_{0}}, π_{1}^{i_{1}}, π_{1}^{i_{0}}, π_{1}^{i_{1}})$
DASTA 128-4	$(1877, 4, 128)$	$π = g (19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 84)$	$(π^{i}, π^{i}, π^{i}, π^{i}, π^{i})$
DASTA 256-6	$(703, 6, 256)$	$π_{0} = g (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 49)$ $π_{1} = g (19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 71, 73, 49)$	$(π_{0}^{i_{0}}, π_{0}^{i_{1}}, π_{1}^{j_{0}}, π_{1}^{j_{1}}, π_{1}^{j_{2}}, π_{0}^{i_{0}}, π_{0}^{i_{1}})$
DASTA 256-5	$(3543, 5, 256)$	$π = g (71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 85)$	$(π^{i}, π^{i}, π^{i}, π^{i}, π^{i}, π^{i})$

i, $i_{0}$ , $i_{1}$ , $j_{0}$ , $j_{1}$ , $j_{2}$ are determined by N: $i = ⌈ \sqrt{N} ⌉ i_{1} + i_{0} = {⌈ \sqrt[3]{N} ⌉}^{2} j_{2} + ⌈ \sqrt[3]{N} ⌉ j_{1} + j_{0}$ , where $0 ⩽ i_{0}$ , $i_{1} < \sqrt{N}$ .

References

M.R.

Albrecht,

Grassi,

Rechberger et al., Mimc: Efficient encryption and cryptographic hashing with minimal multiplicative complexity, in: ASIACRYPT 2016, Springer, 2016, pp. 191–219. doi:10.1007/978-3-662-53887-6_7.

M.R.

Albrecht,

Rechberger,

Schneider et al., Ciphers for MPC and FHE, in: EUROCRYPT 2015, Springer, 2015, pp. 46–48.

Armknecht, A linearization attack on the bluetooth key stream generator, 13 December 2002, http://eprint.iacr.org/2002/191/.

Biryukov,

Bouillaguet and

Khovratovich, Cryptographic schemes based on the ASASA structure: Black-box, white-box, and public-key (extended abstract), in: ASIACRYPT 2014, Springer, 2014, pp. 63–84.

Canteaut,

Carpov,

Fontaine et al., Stream ciphers: A practical solution for efficient homomorphic-ciphertext compression, in: The 23rd International Conference on Fast Software Encryption, Springer, 2016, pp. 313–333. doi:10.1007/978-3-662-52993-5_16.

N.T.

Courtois,

Klimov,

Patarin et al., Efficient algorithms for solving overdefined systems of multivariate polynomial equations, in: EUROCRYPT 2000, Springer, 2000, pp. 14–18.

N.T.

Courtois and

Meier, Algebraic attacks on stream ciphers with linear feedback, in: EUROCRYPT 2003, Springer Press, Warsaw, 2003, pp. 345–359.

Dobraunig,

Eichlseder,

Grassi et al., RASTA: A cipher with low ANDdepth and few ANDs per bit, in: CRYPTO 2018, Springer, 2018, pp. 662–692. doi:10.1007/978-3-319-96884-1_22.

Dobraunig,

Grassi,

Guinet et al., Ciminion: Symmetric encryption based on Toffoli-gates over large finite fields, in: EUROCRYPT 2021, Springer, 2021, pp. 3–34. doi:10.1007/978-3-030-77886-6_1.

10.

J.C.

Faugere, A new efficient algorithm for computing Gröbner bases (F4), Journal of Pure and Applied Algebra 139 (1999), 61–88. doi:10.1016/S0022-4049(99)00005-5.

11.

J.C.

Faugere, A new efficient algorithm for computing Gröbner bases without reduction to zero F5, in: International Symposium on Symbolic and Algebraic Computation Symposium – ISSAC 2002, ACM, 2002, pp. 75–83. doi:10.1145/780506.780516.

12.

Grassi,

Lüftenegger,

Rechberger et al., On a generalization of substitution-permutation networks: The HADES design strategy, in: EUROCRYPT 2020, Springer, 2020, pp. 674–704. doi:10.1007/978-3-030-45724-2_23.

13.

Guo,

G.H.

Liao,

G.Z.

Liu et al., Practical collision attacks against round-reduced SHA-3, Journal of Cryptology 33 (2019), 228–270. doi:10.1007/s00145-019-09313-3.

14.

Hebborn and

Leander, DASTA – Alternative linear layer for RASTA, IACR Transactions on Symmetric Cryptology 3 (2020), 46–86. doi:10.13154/tosc.v2020.is.46-86.

15.

F.K.

Liu,

Isobe and

Meier, Algebraic attacks on RASTA and DASTA using low-degree equations, in: ASIACRYPT 2021, Springer, 2021, pp. 214–240. doi:10.1007/978-3-030-92062-3_8.

16.

Meaux,

Journault,

Standaert et al., Towards stream ciphers for efficient FHE with low-noise ciphertexts, in: EUROCRYPT 2016, Springer, 2016, pp. 311–343. doi:10.1007/978-3-662-49890-3_13.

17.

Mittal and

K.R.

Ramkumar, Research perspectives on fully homomorphic encryption models for cloud sector, Journal of Computer Security 29 (2021), 135–160. doi:10.3233/JCS-219001.

18.

Pasalic, On guess and determine cryptanalysis of LFSR-based stream ciphers, IEEE Transactions on Information Theory 55 (2009), 3398–3406. doi:10.1109/TIT.2009.2021316.

19.

M.S.

Rajasree, Cryptanalysis of round-reduced KECCAK using non-linear structures, in: INDOCRYPT 2019, Springer, 2019, pp. 175–192. doi:10.1007/978-3-030-35423-7_9.

20.

SHA-3 standard: Permutation-based hash and extendable-output functions, (NIST FIPS)-202, 2014.

A new algebraic attack on DASTA

Abstract

Keywords

1. Introduction

2.1. Algebraic attack

2.2. The components of DASTA

3. Linearization and algebraic attack on DASTA

5. Algebraic attacks for arbitrary plaintext–ciphertext pairs

Algorithm 2 (Attack Model 2 (for arbitrary plaintext–ciphertext pair)).

Table 2 The data complexity of attack Model 2 (for arbitrary plaintext–ciphertext pair) DASTA 80-6 80-4 128-6 128-5 128-4 256-6 256-5 Ref. log 2 D 27 29 53 32 39 107 80 [15] log 2 D 26 28 52 31 38 106 79 Our

6. Conclusions

Conflict of interest

Footnotes

DASTA instances

References

Table 2
The data complexity of attack Model 2 (for arbitrary plaintext–ciphertext pair)

DASTA 80-6 80-4 128-6 128-5 128-4 256-6 256-5 Ref.

${log}_{2}^{D}$ 27 29 53 32 39 107 80 [15]

${log}_{2}^{D}$ 26 28 52 31 38 106 79 Our