1. Introduction
1.1 Background
The differential attack, first introduced by Biham and Shamir [1], is widely regarded as one of the most important cryptanalytic techniques for symmetric-key primitives [2]-[4]. New designs for symmetric-key primitives must be able to be secure against this type of attack as it is considered a crucial security requirement. However, evaluating the security against differential attacks can be computationally demanding, as the designer needs to exhaustively evaluate the space that an attacker can exploit. To address this issue, in many cases the designers take the aid of mathematical solvers, such as an MILP (Mixed Integer Linear Programming) [5]-[8] and SAT (Boolean Satisfiability Problem) [9]-[12].
At CT-RSA 2022, Bossert et al. proposed an efficient large-state tweakable block cipher called Pholkos [13]. With support for 256-bit keys, Pholkos offers 128-bit security against quantum key-recovery attacks. Moreover, even if Pholkos is used in modes having birthday security the scheme has practically sufficient security. In order to evaluate the security of differential attacks on Pholkos, designers obtained the lower bounds for the number of active S-boxes using MILP tools. Based on it, they claimed that Pholkos family is secure against differential attacks. However, they only gave rough security bounds in both of related-tweak and related-tweakey settings due to the computational hardness of the security evaluation that comes from the large internal state. To be more precise, they estimated the lower bounds of the number of active S-boxes for relatively-large number of steps by just summing those in the small number of steps.
1.2 Our Contribution
In this paper, we utilize efficient search methods based on MILP to obtain lower bounds for the number of active S-boxes in a larger number of steps. For the first time, we derive the exact minimum number of active S-boxes of each variant up to the steps where the security against differential attacks can be ensured in related-tweak and related-tweakey settings. Our results indicate that Pholkos-256-128/256-256/512/1024 is secure after 4/5/3/4 steps in the related-tweak setting, and after 5/6/3/4 steps in the related-tweakey setting, respectively. Our results enable reducing the required number of steps to be secure against differential attacks of Pholkos-256-256 in related-tweak setting, and Pholkos-256-128/256 and Pholkos-1024 in the related-tweakey setting by one step, respectively. A summary of our results is shown in Table 1. The details of our contributions in each setting are summarized as follows:
Table 1 Summary of the required number of steps to be secure against differential attacks for Pholkos family in each setting. |
 |
(1) Single-key setting
Although the required number of rounds for differential attacks is not changed from the designer’s evaluation, we show the exact lower bounds for the number of active S-boxes over all rounds for Pholkos-512 for the first time and those for more steps for Pholkos-1024 than the designer’s evaluation [13].
(2) Related-tweak setting
We reveal the lower bounds for the number of active S-boxes over all rounds for Pholkos-256-128/256-256 in the related-tweak setting. We show that Pholkos-256-128 can be secure against differential attacks after 4 steps, which improves the designer’s result by one round. For Pholkos-512 we derive the bounds up to 7 steps while the designer’s evaluation [13] can obtain it only up to 4 steps. For Pholkos-1024, we update the number of lower bounds of active S-boxes in 5 steps.
(3) Related-tweakey setting
We update the lower bounds for the number of active S-boxes in 3 steps of Pholkos-256-256. Moreover, we first derived the lower bounds for the number of active S-boxes over all rounds for Pholkos-256-128 in the related-tweakey setting. Our results show that for Pholkos-256-128/256-256/1024, 5/6/4 steps are sufficient to be secure against differential attacks, respectively, which update the designer’s result of 6/7/5 steps, respectively.
1.3 Organization
This paper is organized as follows. Section 2 provides the differential attack and how to evaluate the security against this attack with an MILP. Section 3 describes the specification of Pholkos-256-128/256-256/512/1024. In Sect. 4, we explain our method to evaluate the security of Pholkos in the single-key, related-tweak, and related-tweakey settings. In Sect. 5, we show our evaluation results and Sect. 6 discusses them. Finally, we conclude this paper in Sect. 7.
2. Preliminaries
This section describes differential attacks and the method to evaluate active S-boxes with MILP.
2.1 Differential Attack
The differential attack [1] is one of the most popular cryptanalysis techniques for block ciphers. In order to evaluate the resistance against differential attacks, we evaluate its differential probability \(DP_{f_b}\) for all possible differences and obtain the maximum one called maximum differential probability \(DP_{f_{b}max}\). Let \(f_b\), \(\Delta x_0\), and \(\Delta x_r\) be the \(b\)-bit block cipher, differences of plaintexts, and differences of ciphertexts, respectively. \(DP_{f_b}\) is defined as follows:
| \[DP_{f_{b}}(\Delta x_0, \Delta x_r) = \frac{\#\{x \in \{0,1\}^{b} | f_{b}(x) \oplus f_{b}(x \oplus \Delta x_0) = \Delta x_r\}}{2^{b}}.\] |
If \(b\) is small, calculating \(DP_{f_{b}max}\) is feasible. However, this is not the case for ciphers having more than a 64-bit block due to computational hardness. Therefore, the maximum differential characteristic probability \(DCP_{f_{b}max}\) is utilized to approximate \(DP_{f_{b}max}\). \(DCP_{f_{b}max}\) is defined as a product of the differential characteristic probability \(DCP_{f_b}\) for each round as follows:
| \[DCP_{f_{b}} = \prod^{r}_{R=1} DP_{f_{b}}(\Delta x_{R}, \Delta x_{R+1}),\] |
| \[DCP_{f_{b}max} = \max_{\substack{\Delta x_{1} \neq 0 \\ \Delta x_{2},\ldots,\Delta x_{r+1}}} DCP_{f_{b}},\] |
where \(r\) is the number of rounds. For block ciphers whose non-linear layer consists of only an S-box, \(DCP_{f_{b}max}\) can be calculated by multiplication of \(DP_{smax}\) for all active S-boxes under a well-known Markov cipher assumption, i.e. \(DCP_{f_{b}max} = (DP_{smax})^{AS_{lbD}}\) where \(DP_{smax}\) and \(AS_{lbD}\) are the maximum differential probability of the S-box and the lower bound for the number of active S-boxes, respectively.
2.2 MILP-Aided Security Evaluation
MILP (Mixed Integer Linear Programming) is one of the methods for efficiently finding variables to maximize or minimize a particular objective function under some constraints expressed by a linear inequality. Mouha et al. introduced MILP into the field of symmetric-key cryptography to efficiently evaluate the lower bound for the number of active S-boxes [5]. In their evaluation, we need to express all operations in a symmetric-key primitive as linear inequalities and assign them to the MILP model as constraints. Then, the total number of active S-boxes is assigned to the MILP model as the objective function. After constructing the MILP model, we can obtain the lower bound for the number of active S-boxes by giving it to an MILP solver. In this study, we employ the Gurobi Optimizer [14] as the MILP solver.
3. Specification of Pholkos
The family of Pholkos was proposed by Bossert et al. at CT-RSA 2022 [13]. Algorithm 1 shows the encryption procedures of Pholkos-\(n\)-\(t\). Pholkos is specified as four variants by the length of the plaintext and the tweak. Table 2 shows each variant and its security level (claimed security) in the single-key, related-tweak, and related-tweakey settings.
Table 2 Parameters of Pholkos. \(n\) and \(t\) denote the size of the plaintext and tweak, respectively. |
 |
3.1 Notations
-
\(r\) - the number of rounds.
-
\(s\) - the number of steps. One step proceeds two rounds of AES round function and 2 tweakey XORs, i.e. \(s = r/2\).
-
\(P\) - the plaintext of Pholkos. The plaintext is divided into 128-bit substates, i.e. \(P = P[0], P[1], \ldots, P[(n/128)-1]\). It is also divided into eight 32-bit words. i.e. \(P = (P_0, P_1, \ldots, P_{(n/32)-1})\).
-
\(IK\) - 256-bit initial key. It is expressed as follows:
\[\begin{aligned} &IK = IK_0, IK_1, \ldots, IK_7.& \end{aligned}\] -
\(K^i\) - \(n\)-bit \(i\)-th round expanded key (\(0 \leq i \leq r\)). It is expressed as follows:
\[\begin{aligned} &K^i = K^i_0, K^i_1, \ldots, K^i_{(n/32)-1}, &\\ &K^i = K^i[0], K^i[1], \ldots, K^i[(n/128)-1].& \end{aligned}\] -
\(T^i\) - \(t\)-bit \(i\)-th round tweak (\(0 \leq i \leq r\)). It is expressed as follows:
\[\begin{aligned} &T^i = T^i_0, T^i_1, \ldots, T^i_{(n/32)-1}, &\\ &T^i = T^i[0], T^i[1], \ldots, T^i[(t/128)-1].& \end{aligned}\] -
\(RTK^i\) - \(n\)-bit \(i\)-th round tweakey (\(0 \leq i \leq r\)). It is expressed as follows:
\[\begin{aligned} &RTK^i = RTK^i[0], RTK^i[1], \ldots, RTK^i[(n/128)-1].& \end{aligned}\] -
\(RC^i\) - The 128-bit \(i\)-th round constant (\(0 \leq i \leq r\)), which is defined as in [13].
-
\(\pi_n\) - The 32-bit-wise permutation shown in Table 3, where \(n\) is the length of input. For \(n = 1024\), there are two type permutations \(\pi_{1024,0}\) and \(\pi_{1024,1}\), which are applied alternatingly, starting with \(\pi_{1024,0}\).
-
\(\pi_{\tau}\) - The byte-wise permutation shown in Table 4. \(\pi_{\tau}\) is used to update subkeys and tweaks.
-
\(\mbox{A}(X)\) - one AES round function applied to the substate \(X\), is defined as follows:
where MixColumns, ShiftRows, and SubBytes are the same operations as in AES.\[\mbox{A}(X) = \mbox{MixColumns}~\circ~\mbox{ShiftRows}~\circ~\mbox{SubBytes}(X), \\\] -
\(\mbox{A}_{last}(X)\) - last AES round function applied to the substate \(X\), as defined follows:
\[\mbox{A}_{last}(X) = \mbox{ShiftRows}~\circ~\mbox{SubBytes}(X).\]
Table 3 32-bit-wise permutation \(\pi_n\), where \(n\) is input length. |
 |
Table 4 Byte-wise permutation \(\pi_{\tau}\). |
 |
3.2 Step Function
Figure 1 illustrates the first step of Pholkos-512 as an example of the step function of Pholkos family. At the beginning of the first step, the plaintext is first XORed to the pre-whitening \(RTK^0\). Then, it will proceed into the step function. One step consists of two rounds and the application of \(\pi_n\). Each round consists of \(\mbox{A}(X)\) and XORed \(RTK^i\). The final step excludes the final \(\pi_n\) and employs \(\mbox{A}_{last}(X)\) instead of \(\mbox{A}(X)\).
 |
Fig. 1 First step of Pholkos-512 including pre-whitening \(RTK^0\). The \(\mbox{A}\) denotes \(\mbox{A}(X)\). |
3.3 Tweakey Scheduling
We show the overview of the tweakey scheduling function in Fig. 2. The detailed procedure is described as follows.
 |
Fig. 2 Tweakey schedule of Pholkos. |
(1) Key Expansion
For variants with \(n > 256\), the key expansion \(\varphi\) shown in Fig. 3 is first applied to the initial key. Function \(\varphi\) expand \(K\) using \(IK\) and binary circulant matrices \(\mathbf{M}_A\), \(\mathbf{M}_B\), and \(\mathbf{M}_C\) \(\in (\mathbb{F}_{2^{32}})^{8 \times 8}\) with branch numbers of four:
| \[\begin{aligned} &\mathbf{M}_A = \mathsf{circ}(11001000),&\mathbf{M}_B = \mathsf{circ}(10101000),\\ &\mathbf{M}_C = \mathsf{circ}(10011000).& \end{aligned}\] |
For Pholkos-512, the expanded key \(\mathbf{K}\) meets the following conditions:
| \[\mathbf{K} = \mathbf{IK}~\|~\mathbf{M}_A \cdot \mathbf{IK}^\top.\] |
For Pholkos-1024, the expanded key \(\mathbf{K}\) meets the following conditions:
| \[\mathbf{K} = \mathbf{IK}~\|~\mathbf{M}_A \cdot \mathbf{IK}^\top~\|~\mathbf{M}_B \cdot \mathbf{IK}^\top~\|~\mathbf{M}_C \cdot \mathbf{IK}^\top.\] |
 |
Fig. 3 Key expansion function \(\varphi\). |
(2) Generation of Tweakey
In order to generate the tweakey schedule, we need to obtain the tweak and key schedule from the initial tweak \(T^0\) and (expanded) key \(K^0\). The function \(\theta\) and \(\kappa\) provide \(T^i\) and \(K^i\) from \(T^{i-1}\) and \(K^{i-1}\) in Figs. 4(a) and 4(b), respectively. Subsequently, \(RTK^i\) is generated using the function \(\gamma\) that combines \(T^i\), \(K^i\) and \(RC^i\) as shown in Fig. 4(c). Each function is performed as below:
-
θ (Fig. 4(a)) : The function \(\theta\) obtains \(T^i\) from \(T^{i-1}\), i.e. \(T^i = \theta(T^{i-1})\). If \(t = 128\), \(\theta\) processes \(\pi_{\tau}\). When \(t = 256\), \(\theta\) first executes \(T^{i-1}\) using \(\pi_{256}\) and generates intermediate tweak \(T^{i-1\prime}\). Next, \(T^{i-1\prime}\) is split into 128-bit substates, and \(\pi_{\tau}\) is processed on each substate.
-
κ (Fig. 4(b)) : The function \(\kappa\) obtains \(K^I\) from \(K_{I-1}\), I.e, \(K^i = \kappa(K^{i-1})\). For the variant has an n-bit plaintext, \(\pi_n\) is first applied to \(K^{I-1}\), and then the output of \(\pi_n\) is divided into 128-bit states, I.e, \(\pi_n(K^{I-1}) = (K^{I-1\prime}[0]||K^{I-1\prime}[1]|| \dots || K^{I-1\prime}[(n/128)-1])\) where \(K^{I-1\prime}[j] \in GF(2)\). Lastly, \(\pi_{\tau}\) is applied to each \(K^{I-1\prime}[j]\).
-
γ (Fig. 4(c)) : The function \(\gamma\) obtains \(RTK^i\) from \(T^i\), \(K^i\), and \(RC^i\), i.e. \(RTK^i = \gamma(T^{i},K^{i},RC^{i})\). If \(t = 128\), let \(j\) be the index of substate, \(\gamma\) has been computed as follows:
When \(t = 256\), \(\gamma\) has been computed as follows:\[\begin{aligned} & RTK^i[j]= \begin{cases} T^i[0] \oplus K^i[j] \oplus RC^i~~\mbox{if}~j = 0, \\ T^i[0] \oplus K^i[j]~~~~~~~~~~~~~~~\mbox{otherwise}. \end{cases}& \end{aligned}\] \[\begin{aligned} & RTK^i[j]= \begin{cases} T^i[j] \oplus K^i[j] \oplus RC^i~~\mbox{if}~j = 0, \\ T^i[j] \oplus K^i[j]~~~~~~~~~~~~~~~\mbox{otherwise}. \end{cases}& \end{aligned}\]
These functions are iterated until generating \(RTK^r\).
 |
Fig. 4 Components of the tweakey generated functions. |
4. Our MILP Model for Security Evaluation
In this section, we describe how to evaluate the lower bound for the number of active S-box in Pholkos. We evaluate it based on a byte-wise truncated difference, as Pholkos is constructed by the byte-wise operations. To guarantee 256-bit security against the distinguishing attack, more than 42 active S-boxes are needed, as the maximum differential probability of an S-box in AES is \(2^{-6}\). In order to assign the byte-wise MILP model, we first need to define byte-wise truncated difference vector \(\Delta \mathbf{x} = (\Delta x_0, \Delta x_1, \ldots, \Delta x_7)\) as follows:
| \[\Delta x = \left\{ \, \begin{aligned} & 0 ~~~~\text{if}~~\sum_{i=0}^{7} \Delta x_i = 0, \\ & 1 ~~~~\text{otherwise}. \end{aligned} \right.\] |
Based on this, we give the constraints to express the differential propagation of each operation and the objective function according to [5]. In the following sections, we denote \(\mathcal{M}_{var}\), \(\mathcal{M}_{con}\), and \(\mathcal{M}_{obj}\) as the set of variables, the set of constraints, and the objective function in an MILP model, respectively.
4.1 Basic MILP Model for Pholkos Family
(1) Constraints
As Pholkos consists of an XOR, Linear transformation, and S-box, we describe the model of the differential propagation.
-
XOR : Let input difference vectors be \(x_1, x_2\). An output difference vector \(y = x_1 \oplus x_2\) is expressed as follows:
Remarks. In the evaluation of the truncated differences, we have to consider the case of \(1 \oplus 1 = 1\) with the case of \(1 \oplus 1 = 0\), i.e., \(1 \oplus 1 = 0 \mbox{ or } 1\).\[\left\{ \, \begin{aligned} & \mathcal{M}_{var} \leftarrow x_1, x_2, y~\text{as binary}, \\ & \mathcal{M}_{con} \leftarrow - x_1 + x_2 + y \geq 0,\\ & \mathcal{M}_{con} \leftarrow x_1 - x_2 + y \geq 0,\\ & \mathcal{M}_{con} \leftarrow x_1 + x_2 - y \geq 0. \end{aligned} \right.\] -
Copy : Let an input difference vector be \(x\). Output difference vectors \((y_1, y_2) = (x, x)\) are expressed as follows:
\[\left\{ \, \begin{aligned} & \mathcal{M}_{var} \leftarrow x, y_1, y_2~\text{as binary}, \\ & \mathcal{M}_{con} \leftarrow x = y_1 = y_2. \end{aligned} \right.\] -
Linear transformation : Let input difference vectors be \(x_0, x_1, \ldots, x_n\), output difference vectors be \(y_0, y_1, \ldots, y_n\), and the branch number be \(\mathcal{B}\). The linear transformation is assigned as follows:
where \(d\) is A binary dummy variables.\[\left\{ \, \begin{aligned} & \mathcal{M}_{var} \leftarrow x_0, x_1, \ldots, x_n, y_0, y_1, \ldots, y_n~\text{as binary}, \\ & \mathcal{M}_{con} \leftarrow \sum_{i=0}^{n} x_i + \sum_{i=0}^{n} y_i \geq \mathcal{B} \cdot d, \\ & \mathcal{M}_{con} \leftarrow d \geq x_i(0 \leq i \leq n), \\ & \mathcal{M}_{con} \leftarrow d \geq y_i(0 \leq i \leq n), \\ \end{aligned} \right.\] -
S-box : Let an input difference vector be \(x\). An output difference vector \(y = \mbox{SubBytes}(x)\) is expressed as follows:
\[\left\{ \, \begin{aligned} & \mathcal{M}_{var} \leftarrow x, y~\text{as binary}, \\ & \mathcal{M}_{con} \leftarrow x = y. \end{aligned} \right.\]
(2) Objective Function
The objective function is defined as the total number of active S-boxes. Let the S-box input difference vectors be \(s_0, s_1, \ldots, s_n\), the objective function is expressed as follows:
| \[\mathcal{M}_{obj} \leftarrow \mbox{Minimize} \left (\sum_{i=0}^{n} s_i \right ). \] |
If it is more than 42, the variant guarantees 256-bit security against the differential attack. We evaluate the resistance of Pholkos against differential attacks by assigning the above constraints in accordance with the encryption scheme of it in Algorithm 1.
 |
In this paper, we evaluate it in the single-key, related-tweak, related-tweakey settings. The condition of these settings are as follows:
4.2 MILP Model for Each Attack Scenario
We need to give additional constraints to the input difference depending on the attack scenarios. In this paper, we evaluate the security against differential attacks in the single and related-tweak, and related tweakey settings. Hence, we show additional constraints about these settings one by one.
(1) Single-key Setting
The adversary can require a ciphertext corresponding to arbitrary plaintext to an encryption oracle. Therefore, the attacker can exploit arbitrary differences in a plaintext. We assign the setting to the constraint in MILP. Let input message differences be \(x_0, x_1, \ldots, x_n\), we assign the constraint as follows:
| \[\left\{ \, \begin{aligned} & \mathcal{M}_{var} \leftarrow x_0, x_1, \ldots, x_n~\text{as binary}, \\ & \mathcal{M}_{con} \leftarrow \sum_{a=0}^{n} x_a \geq 0. \end{aligned} \right.\] |
(2) Related-tweak Setting
The adversary can require a ciphertext corresponding to arbitrary plaintext and tweak to an encryption oracle. Therefore, the attacker can exploit arbitrary differences in a plaintext and tweak. We assign the setting to the constraint in MILP. Let input message differences be \(x_0, x_1, \ldots, x_m\) and input tweak differences be \(t_0, t_1, \ldots, t_n\), we assign the constraint as follows:
| \[\left\{ \, \begin{aligned} & \mathcal{M}_{var} \leftarrow x_0, x_1, \ldots, x_m, t_0, t_1, \ldots, t_n~\text{as binary}, \\ & \mathcal{M}_{con} \leftarrow \sum_{a=0}^{m} x_a + \sum_{b=0}^{n} t_b \geq 0. \end{aligned} \right.\] |
(3) Related-tweakey Setting
The adversary can require a ciphertext corresponding to arbitrary plaintext, tweak, and key to an encryption oracle. Therefore, the attacker can exploit arbitrary differences in a plaintext, tweak, and key. We assign the setting to the constraint in MILP. Let input message differences be \(x_0, x_1, \ldots, x_l\), input tweak differences be \(t_0, t_1, \ldots, t_m\), and input key differences be \(k_0, k_1, \ldots, k_n\), we assign the constraint as follows:
| \[\left\{ \, \begin{aligned} &\! \mathcal{M}_{var} \!\leftarrow\! x_0, x_1, \ldots, x_l, t_0, t_1, \ldots, t_m, k_0, k_1, \ldots, k_n~\text{as binary}, \\ &\! \mathcal{M}_{con} \!\leftarrow\! \sum_{a=0}^{l} x_a + \sum_{b=0}^{m} t_b + \sum_{c=0}^{n} k_c \geq 0. \end{aligned} \right.\] |
The byte-wise evaluation in this setting causes the problem that the number of active S-boxes is zero. If all bytes of the initial plaintext are inactive and all bytes of both the initial key and the initial tweak are active, all S-boxes are always inactive because all differences in the tweakey scheduling function are canceled. However, this never happens in the actual attack because a bit rotation in each word is applied in the function \(\kappa\). Hence, we have to add constraints to avoid the case of all S-boxes being inactive. In this paper, as well [13], we apply the assumption that each active byte in RTKs are only canceled at most once. Based on this, we add constraints that the RTK through a one-byte active key path is canceled at most once. Specifically, focusing on the RTK generation process, if an input key is active, the total number of active RTKs by XORed operations of keys and tweaks is greater than or equivalent to the number of rounds multiplied by the input key minus one. We assign it to the MILP model as constraints. We show the example of Pholkos-256 in 2 steps in Algorithm 2.
 |
5. Our Result by MILP-Based Search
In this section, we show the result for the lower bound on the number of active S-boxes for Pholkos family in each setting by MILP-based search. Our evaluations totally required three weeks with three computers equipped with AMD Ryzen Threadripper 3990X (64-Core) with 256 GB RAM.
Table 5 Lower bounds for the number of active S-boxes of Pholkos family over 1-10 steps. Bold is the minimum secure number of steps against differential attacks. Gray is the bounds derived for more steps from those results. Values in parentheses are the results of [13]. |
 |
Table 5 summarizes our results of lower bounds of active S-boxes for Pholkos.
-
Single-key Setting: Our results show that Pholkos-256-128/256-256/512/1024 required 4/4/3/4 steps to be secure against differential attacks in the single-key setting, respectively, i.e. after these steps, each variant has more than 42 active S-boxes.
-
Related-tweak Setting: We show that Pholkos-256-128/256-256/512/1024 require 4/5/3/4 steps, respectively, to be secure against differential attacks in the related-tweak setting. We derived the lower bounds for the number of active S-boxes of Pholkos-256-128/256-256/512/1024 up to 8/9/7/5 steps, respectively.
-
Related-tweakey Setting: We show that the required number of steps is estimated as 5/6/3/4 steps for Pholkos-256-128/256-256/512/1024 against differential attacks in the related-tweakey setting.
6. Updating Security Bounds
In this section, we explain how our new bounds of the number of active S-boxes affect the security of Pholkos. For the first time, we derive the exact minimum number of active S-boxes of each variant up to the steps where the security against differential attacks can be ensured in related-tweak and related-tweakey settings, while previous results estimated the lower bounds of the number of active S-boxes for relatively-large number of steps by just summing those in the small number of steps.
6.1 Single-Key Setting
While existing results [13] presented the exact lower bounds for the number of active S-boxes for 8 steps for Pholkos-256-128/256-256/512 and those for 7 steps for Pholkos-1024, respectively, we show the lower bounds of Pholkos-256-128/256-256/512/1024 up to 10 steps for the first time. Although our results cannot reduce the number of required steps against differential attacks, it reveals the fine-grained security of Pholkos against differential attacks. We believe that these results are helpful for estimating the security against known-key and hash function settings.
6.2 Related-Tweak Setting
In [13], the lower bounds for 4/7/5/6 or more steps for Pholkos-256-128/256-256/512/1024 was obtained indirectly by summing lower bounds of some previous steps, instead of using the exact MILP-aided approach, respectively. We reveal the lower bounds for the number of active S-boxes over all rounds for Pholkos-256-128/256-256 in the related-tweak setting. Our results updates the number of required steps for Pholkos-256-128 against differential attacks from 5 to 4. For Pholkos-1024, we update the number of lower bounds of active S-boxes in 5 steps.
6.3 Related-Tweakey Setting
In [13], the lower bounds for 4/5/4/4 or more steps for Pholkos-256-128/256-256/512/1024 was also derived by summing lower bounds of some previous steps. We show the lower bounds of Pholkos-256-128/256-256/1024 can be found up to 8/7/5 steps, respectively. As a result, we successfully update the number of required steps for Pholkos-256-128/256-256/1024 against differential attacks from 6/7/5 steps to 5/6/4 steps, respectively. Besides, we reveal that the number of active S-boxes of 3 steps of Pholkos-256-256 is smaller than the results reported in [13]. Table 6 shows an example of the active input bytes in 3 steps for Pholkos-256-256, where 0 and 1 are defined as a non-active byte and an active byte, respectively.
Table 6 Example of active input bytes of minimum #active S-boxes in 3 steps for Pholkos-256-256 in the related-tweakey setting. |
 |
7. Conclusion
In this paper, we developed efficient search methods based on MILP to obtain tighter lower bounds for the number of active S-boxes in a larger number of steps. For the first time, we derived the exact minimum number of active S-boxes of each variant up to the steps where the security against differential attacks can be ensure in related-tweak and related-tweakey settings. Our results indicate that Pholkos-256-128/256-256/512/1024 is secure after 4/5/3/4 steps in the related-tweak setting, and after 5/6/3/4 steps in the related-tweakey setting, respectively. Our results enable reducing the required number of steps to be secure against differential attacks of Pholkos-256-256 in related-tweak setting, and Pholkos-256-128/256 and Pholkos-1024 in the related tweakey setting by one step, respectively.
Acknowledgments
This research comprises a part of the results of “Research and Development of New Generation Cryptography for Secure Wireless Communication Services,” which was commissioned by the Ministry of Internal Affairs and Communications of Japan under the “Research and Development for Expansion of Radio Resources” grant (grant no.JPJ000254)”. This work was supported by JST PRESTO (grant no. JPMJPR2031).
References
[1] E. Biham and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,” J. Cryptology, vol.4, no.1, pp.3-72, 1991.
CrossRef
[2] E. Biham, “New types of cryptanalytic attacks using related keys,” J. Cryptology, vol.7, no.4, pp.229-246, 1994.
CrossRef
[3] L.R. Knudsen, “Truncated and higher order differentials,” Fast Software Encryption: Second International Workshop, Leuven, Belgium, Proceedings, B. Preneel, ed., Lecture Notes in Computer Science, vol.1008, pp.196-211, Springer, 1994.
CrossRef
[4] E. Biham and A. Shamir, “Differential cryptanalysis of the full 16-round DES,” Advances in Cryptology - CRYPTO’92, 12th Annual International Cryptology Conference, Santa Barbara, California, USA, Proceedings, E.F. Brickell, ed., Lecture Notes in Computer Science, vol.740, pp.487-496, Springer, 1992.
CrossRef
[5] N. Mouha, Q. Wang, D. Gu, and B. Preneel, “Differential and linear cryptanalysis using mixed-integer linear programming,” Information Security and Cryptology - 7th International Conference, Inscrypt 2011, Beijing, China, Revised Selected Papers, C. Wu, M. Yung, and D. Lin, eds., Lecture Notes in Computer Science, vol.7537, pp.57-76, Springer, 2011.
CrossRef
[6] Z. Xiang, W. Zhang, Z. Bao, and D. Lin, “Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers,” Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, Proceedings, Part I, J.H. Cheon and T. Takagi, eds., Lecture Notes in Computer Science, vol.10031, pp.648-678, 2016.
CrossRef
[7] S. Sun, L. Hu, P. Wang, K. Qiao, X. Ma, and L. Song, “Automatic security evaluation and (related-key) differential characteristic search: Application to simon, present, lblock, DES(L) and other bit-oriented block ciphers,” Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., Proceedings, Part I, P. Sarkar and T. Iwata, eds., Lecture Notes in Computer Science, vol.8873, pp.158-178, Springer, 2014.
CrossRef
[8] Y. Sasaki and Y. Todo, “New impossible differential search tool from design and cryptanalysis aspects: Revealing structural properties of several ciphers,” Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, Proceedings, Part III, J. Coron and J.B. Nielsen, eds., Lecture Notes in Computer Science, vol.10212, pp.185-215, 2017.
CrossRef
[9] L. Sun, W. Wang, and M. Wang, “More accurate differential properties of LED64 and Midori64,” IACR Trans. Symmetric Cryptol., vol.2018, no.3, pp.93-123, 2018.
CrossRef
[10] L. Sun, W. Wang, and M. Wang, “Accelerating the search of differential and linear characteristics with the SAT method,” IACR Trans. Symmetric Cryptol., vol.2021, no.1, pp.269-315, 2021.
CrossRef
[11] J. Guo, G. Liu, L. Song, and Y. Tu, “Exploring SAT for cryptanalysis: (Quantum) collision attacks against 6-round SHA-3,” Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, Proceedings, Part III, S. Agrawal and D. Lin, eds., Lecture Notes in Computer Science, vol.13793, pp.645-674, Springer, 2022.
CrossRef
[12] J. Erlacher, F. Mendel, and M. Eichlseder, “Bounds for the security of ascon against differential and linear cryptanalysis,” IACR Trans. Symmetric Cryptol., vol.2022, no.1, pp.64-87, 2022.
CrossRef
[13] J. Bossert, E. List, S. Lucks, and S. Schmitz, “Pholkos - Efficient large-state tweakable block ciphers from the AES round function,” Topics in Cryptology - CT-RSA 2022 - Cryptographers’ Track at the RSA Conference 2022, Virtual Event, Proceedings, S.D. Galbraith, ed., Lecture Notes in Computer Science, vol.13161, pp.511-536, Springer, 2022.
CrossRef
[14] G.O. Inc., “Gurobi optimizer 6.5,” Official webpage, http://www.gurobi.com/, 2015.
URL
Authors
University of Hyogo
received the B.E. and M.E. degree from University of Hyogo, Japan, in 2021 and 2023, respectively. His research interest had been cryptography. He has worked at SECOM CO., LTD. from 2023.
 |
Mitsubishi Electric Corporation
received the B.E., M.E., and Ph.D. degrees from Kansai University, Japan, in 2017, and University of Hyogo, Japan, in 2020 and 2023, respectively. He has worked at Mitsubishi Electric Corporation from 2023. His current research interests include information security and cryptography.
 |
University of Hyogo
received the B.E. degree from University of Hyogo, Japan, in 2022. He is currently a M.E. student at University of Hyogo, Japan. His research interest is cryptography.
 |
University of Hyogo,National Institute of Information and Communications Technology
received the B.E., M.E., and Ph.D. degrees from Kobe University, Japan, in 2006, 2008, and 2013, respectively. From 2008 to 2017, he worked at the Sony Corporation. From 2017 to 2022, he has been an Associate Professor at University of Hyogo. Since 2023, he has been a Professor at University of Hyogo. His current research interests include information security and cryptography.
 |
