Feistel Ciphers Based on a Single Primitive

Kento TSUJI, Tetsu IWATA

Summary :

We consider Feistel ciphers instantiated with tweakable block ciphers (TBCs) and ideal ciphers (ICs). The indistinguishability security of the TBC-based Feistel cipher is known, and the indifferentiability security of the IC-based Feistel cipher is also known, where independently keyed TBCs and independent ICs are assumed. In this paper, we analyze the security of a single-keyed TBC-based Feistel cipher and a single IC-based Feistel cipher. We characterize the security depending on the number of rounds. More precisely, we cover the case of contracting Feistel ciphers that have d ≥ 2 lines, and the results on Feistel ciphers are obtained as a special case by setting d = 2. Our indistinguishability security analysis shows that it is provably secure with d + 1 rounds. Our indifferentiability result shows that, regardless of the number of rounds, it cannot be secure. Our attacks are a type of a slide attack, and we consider a structure that uses a round constant, which is a well-known countermeasure against slide attacks. We show an indifferentiability attack for the case d = 2 and 3 rounds.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E107-A No.8 pp.1229-1240
• Publication Date: 2024/08/01
• Publicized: 2024/03/29
• Online ISSN: 1745-1337
• DOI: 10.1587/transfun.2024EAP1006
• Type of Manuscript: PAPER
• Category: Cryptography and Information Security

1.  Introduction

(1) Background.

A Feistel structure is one of the widely used structures of a block cipher, and its security proof was given by Luby and Rackoff [2]. It is shown that the 3-round Feistel structure instantiated with 3 independent pseudorandom functions (PRFs), which we call the Feistel cipher, is a pseudorandom permutation (PRP), a block cipher that is indistinguishable from a random permutation against adversaries in a chosen plaintext attack (CPA) setting. Similarly, the 4-round Feistel cipher is a strong PRP (SPRP), where the adversary is in a chosen ciphertext attack (CCA) setting.

A question of whether one can securely reduce the number of independent PRFs has been studied, as reducing the number of PRFs implies the reduction of the key length, and hence it reduces the cost of maintaining, exchanging, and updating the secret key. Let \(\mathrm{\Phi}[F_1, F_2, \ldots, F_r]\) be the \(r\)-round Feistel cipher, where the PRF \(F_i\) is used in the \(i\)-th round. The structure that simply replaces all the PRFs with a single-keyed PRF \(F\), i.e., \(\mathrm{\Phi}[F, F, \ldots, F]\), is easily distinguishable from a random permutation regardless of the number of rounds [3]. Pieprzyk showed that \(\mathrm{\Phi}[F_1, F_1, F_1, F_2]\) and \(\mathrm{\Phi}[F_1, F_1, F_1, F_1 \circ F_1]\) are PRPs [4]. Patarin showed that \(\mathrm{\Phi}[F_1, F_2, F_1, F_2]\) is an SPRP [5]. Additionally, Patarin pointed out that \(\mathrm{\Phi}[F, F, F, F \circ \zeta \circ F]\) is an SPRP, where it uses 1-bit cyclic rotation \(\zeta\). Nandi proved that \(\mathrm{\Phi}[\zeta \circ F, F, F, F]\) is an SPRP and has the optimal number of PRF calls [6]. See also [7] for a related result that uses a mask.

A tweakable block cipher (TBC), formalized by Liskov et al. [8], is the generalization of a block cipher to take an additional input called a tweak. Minematsu pointed out that TBCs can be used as a primitive for constructing block ciphers, and instantiated a concrete structure by combining TBCs and universal hash functions [9]. By replacing the PRFs and XORs in the Feistel cipher with TBCs, Coron et al. formalized a TBC-based Feistel cipher and proved its indistinguishability security [10].

Indifferentiability, formalized by Maurer et al. [11], is one of the security definitions for cryptographic permutations, a key-less permutation. This definition captures the hardness to distinguish a cryptographic permutation from a random permutations, where the cryptographic permutation makes oracle calls to an ideal primitive. Some instances of random oracle (RO) based Feistel ciphers are analyzed with the indifferentiability notion. See [12]-[14] for the results on this line of research. The TBC-based Feistel cipher [10] can be seen as a cryptographic permutation by regarding the TBC as the ideal cipher (IC), which models an ideally secure block cipher, and its indifferentiability analysis is presented in [10], where independent ICs are used in the construction. Bhaumik et al. later improved the security bound [15].

Contracting Feistel structures are derivations of the Feistel structure, and we consider the TBC-based counterpart [16]. These structures have \(d\) lines, where \(d \ge 2\), and \(d-1\) lines are used as the tweak of the TBC to update the remaining line. See Fig. 1 for the structure. The security of the structure is known in the indistinguishability notion [16], [17], and in the indifferentiability notion [18], [19], where we consider the IC with key length of \(d-1\) lines instead of a TBC.

Fig. 1  (a) \(\mathrm{\phi}[\widetilde{E}_K](X^{[1..d]}) = X^{[2..d]} \mathbin{\|}Y\), where \(Y = \widetilde{E}_K(X^{[2..d]}, X^1)\), (b) \(\mathrm{\phi}[{\widehat{E}}](X^{[1..d]}) = X^{[2..d]} \mathbin{\|}Y\), where \(Y = {\widehat{E}}(X^{[2..d]}, X^1)\), and (c) \(\mathrm{\phi}_i[{\widehat{E}}](X^{[1..d]}) = X^{[2..d]} \mathbin{\|}Y\), where \(Y = {\widehat{E}}(X^{[2..d]} \oplus c_i^{[2..d]}, X^1)\).

(2) Our Contributions.

The indistinguishability results on the TBC-based Feistel ciphers [10] and on the TBC-based contracting Feistel ciphers [16], [17] assume independent TBCs, and the indifferentiability results on the IC-based Feistel ciphers [10], [15] and on the IC-based contracting Feistel ciphers [18], [19] assume independent ICs. In this paper, we investigate the security of the single primitive-based counter parts, which replace the TBCs or the ICs with a single primitive, i.e., a single-keyed TBC or a single IC. Our target is the \(n\)-bit block and \((d-1)n\)-bit tweak single-keyed TBC-based Feistel cipher for indistinguishability, and the \(n\)-bit block, \((d-1)n\)-bit key single IC-based Feistel cipher for indifferentiability. We remark that by setting \(d=2\), our results cover the case of regular Feistel ciphers of \(2\) lines. We present the following results:

(3) Indistinguishability Results.

Let \(\mathrm{\Phi}_r\) be the \(r\)-round single-keyed TBC-based Feistel cipher with \(d\) lines. We show that for any \(r\le d\), \(\mathrm{\Phi}_r\) can be distinguished from a random permutation with \(O(1)\) queries. We then show that \(\mathrm{\Phi}_{d+1}\) is secure in the indistinguishability notion, where the security bound is \(O(q^2/2^n)\) for adversaries making \(q\) queries. This makes a sharp difference to the PRF-based Feistel cipher, which is insecure regardless of the number of rounds. Next, for any \(r\ge d+1\), we show that \(\mathrm{\Phi}_r\) can be distinguished from a random permutation with \(O(2^{n/2})\) queries, with a type of slide attack [20]. On one hand, this shows the tightness of the security bound of the case \(r=d+1\), i.e., it is impossible to show a better security bound for this case. This also shows that, even if we increase the number of rounds beyond \(d+1\) rounds, the security of \(\mathrm{\Phi}_r\) does not improve, showing an impossibility of improving the security by increasing the number of rounds.

These results show that the \((d+1)\)-round structure can be practically used in applications that are sufficient with \(O(2^{n/2})\) security, however, it cannot be used if higher security is needed, regardless of the number of rounds.

(4) Indifferentiability Results.

Let \(\mathrm{\widehat{\Phi}}_r\) be the \(r\)-round single IC-based Feistel cipher with \(d\) lines. We show that for any \(r\), \(\mathrm{\widehat{\Phi}}_r\) is not secure in the indifferentiability notion. The attack is the straightforward application of the attacks against \(\mathrm{\Phi}_r\), and they work with \(O(1)\) queries. The attack can be seen as a type of slide attack [20]. Using a round constant is a well-known countermeasure, and one may hope that a round constant can prevent the attack. We consider a variant of \(\mathrm{\widehat{\Phi}}_r\) that uses a round constant, and demonstrate that the round constant cannot prevent the indifferentiability attack for the case \(r=2d-1\).

These results show that single IC based structures should not be used in practice.

Table 1 and Table 2 summarize the previous results and our results. Table 1 shows the results for \(d=2\) and Table 2 shows the results for \(d\ge 2\).

Table 1  Summary of previous results and our results (\(d=2\)) on Feistel ciphers.

Table 2  Summary of previous results and our results on contracting Feistel ciphers. \(d\) denotes the number of lines, \(l\) is a constant value s.t. \(1 \le l \le d-1\). In “Security”, the maximum number of queries is additionally noted if exists.

(5) Further Related Works.

A problem of whether one can securely reduce the number of independent keys/primitives has been studied in various other constructions. See, e.g., [21]-[26]. With respect to slide attacks, key-reduced Feistel ciphers have been actively analyzed. See, e.g., [27]-[31]. Compared to these results, our attacks follow a fundamentally similar approach, while our targets employ stronger primitives, TBCs/ICs, instead of PRFs/ROs.

2.  Preliminaries

2.1  Notation

For a positive integer \(n\), let \(\{0, 1\}^n\) be the set of all \(n\)-bit strings. For two strings \(X\) and \(Y\), let \(X \mathbin{\|}Y\) denote their concatenation. For \(d\) string \(X^1,X^2,\ldots,X^d\), we denote their concatenation \(X^1 \mathbin{\|}X^2 \mathbin{\|}\dots \mathbin{\|}X^d\) by \(X^{[1..d]}\). For a finite set \(S\), \(s \xleftarrow{＄}S\) is the operation of uniformly sampling an element from \(S\) and assigning it to \(s\).

2.2  (Tweakable) Block Cipher

A block cipher \(E: \mathcal{K} \times \mathcal{M} \rightarrow \mathcal{M}\) is a keyed permutation. For key \(K \in \mathcal{K}\), plaintext \(M \in \mathcal{M}\), and ciphertext \(C \in \mathcal{M}\), we write the encryption as \(C = E_K(M)\) and the decryption as \(M = E_K^{-1}(C)\). If \(\mathcal{M} = \{0, 1\}^n\), we say that it is an \(n\)-bit block cipher. Let \(\mathrm{Perm}(n)\) be the set of all \(n\)-bit permutations, and a random permutation is an element selected from \(\mathrm{Perm}(n)\) uniformly at random.

A tweakable block cipher \(\widetilde{E}: \mathcal{K} \times \mathcal{T} \times \mathcal{M} \rightarrow \mathcal{M}\) is a keyed permutation that takes an additional input called a tweak [8]. For key \(K \in \mathcal{K}\), tweak \(T \in \mathcal{T}\), plaintext \(M \in \mathcal{M}\), and ciphertext \(C \in \mathcal{M}\), we write the encryption as \(C = \widetilde{E}_K(T, M)\) and the decryption as \(M = \widetilde{E}_K^{-1}(T, C)\). If \(\mathcal{T} = \{0, 1\}^t\) and \(\mathcal{M} = \{0, 1\}^n\), we say that it is an \((t, n)\)-bit TBC. Let \(\widetilde{\mathrm{Perm}}(t, n)\) be the set of all the functions \(\widetilde{P}: \{0, 1\}^t \times \{0, 1\}^n \rightarrow \{0, 1\}^n\) s.t. for any \(T \in \{0, 1\}^t\), \(\widetilde{P}(T, \cdot) \in \mathrm{Perm}(n)\), and a tweakable random permutation (TRP) is an element selected from \(\widetilde{\mathrm{Perm}}(t, n)\) uniformly at random, which we call an \((t, n)\)-bit TRP.

The ideal cipher \({\widehat{E}}: \mathcal{K} \times \mathcal{M} \rightarrow \mathcal{M}\) is the set of random permutations that idealizes a block cipher. For each \(K\), \({\widehat{E}}(K,\cdot)\) is a random permutation over \(\mathcal{M}\). For key \(K \in \mathcal{K}\), plaintext \(M \in \mathcal{M}\), and ciphertext \(C \in \mathcal{M}\), we write the encryption as \(C = {\widehat{E}}(K,M)\) and the decryption as \(M = {\widehat{E}}^{-1}(K,C)\). If \(\mathcal{K} = \{0, 1\}^k\) and \(\mathcal{M} = \{0, 1\}^n\), we say that it is an \((k, n)\)-bit IC.

2.3  Security Definitions

We consider the security of block cipher \(E\) as a keyed primitive and as a cryptographic permutation. As a keyed primitive, we consider the indistinguishability notion [2], i.e., the notion of a pseudorandom permutation (PRP) and a strong pseudorandom permutation (SPRP). A PRP-adversary has oracle access to a cryptographic permutation oracle \(E_K\) in the real world, and random permutation \(\pi\) in the ideal world. For an adversary \(\mathcal{A}\) that makes a maximum of \(q\) oracle queries, we define the PRP-advantage and SPRP-advantage as follows:

\[\begin{aligned} &\mathbf{Adv}^\mathrm{prp}_E(\mathcal{A}) = |\Pr[\mathcal{A}^{E_K(\cdot)} \Rightarrow 1] - \Pr[\mathcal{A}^{\pi(\cdot)} \Rightarrow 1]|\\ &\mathbf{Adv}^\mathrm{sprp}_E(\mathcal{A})\\ &= |\Pr[\mathcal{A}^{E_K(\cdot), E^{-1}_K(\cdot)} \Rightarrow 1] - \Pr[\mathcal{A}^{\pi(\cdot), \pi^{-1}(\cdot)} \Rightarrow 1]| \end{aligned}\]

Next, as a cryptographic permutation, we consider the indifferentiability notion [11]. Let \(C\) be a cryptographic permutation that is built on the ideal cipher \({\widehat{E}}\), i.e., \(C\) makes oracle calls to \({\widehat{E}}\) to compute its output, and we write \(C^{\widehat{E}}\) for this. In the real world, an adversary \(\mathcal{A}\) has oracle access to \({\widehat{E}}\) and \(C^{\widehat{E}}\). In the ideal world, \(\mathcal{A}\) makes queries to a random permutation \(\pi\) and a simulator \(\mathrm{Sim}^\pi\), where the simulator \(\mathrm{Sim}\) has oracle access to \(\pi\). We call a query to \(C^{\widehat{E}}\) or \(\pi\) as a construction query, and a query to \(E\) or \(\mathrm{Sim}^\pi\) as a primitive query. For an adversary \(\mathcal{A}\) that makes a maximum of \(q\) oracle queries in total, we define the advantage as follows:

\[\begin{aligned} &\mathbf{Adv}^{\mathrm{indiff}}_{C, \mathrm{Sim}}(\mathcal{A})\\ &= |\Pr[\mathcal{A}^{C^{{\widehat{E}}}(\cdot), {\widehat{E}}(\cdot)} \Rightarrow 1] - \Pr[\mathcal{A}^{\pi(\cdot), \mathrm{Sim}^\pi(\cdot)} \Rightarrow 1]| \end{aligned}\]

2.4  Coefficient-H Technique [32], [33]

Our security proof is based on the coefficient-H technique. Let \(\mathcal{R}\) and \(\mathcal{R}^{-1}\) be the real world oracles that internally call a block cipher \(E_K\) and its inverse \(E^{-1}_K\). Similarly, let \(\mathcal{I}\) and \(\mathcal{I}^{-1}\) be the ideal world oracles that internally call a random permutation \(\pi\) and its inverse \(\pi^{-1}\). For an adversary \(\mathcal{A}\) that makes a maximum of \(q\) oracle queries, a transcript \(\theta\) denotes a tuple that records all the interactions between \(\mathcal{A}\) and the oracles. Let \(\Theta_\mathcal{R}\) be the random variable of \(\theta\) when \(\mathcal{A}\) interacts with \(\mathcal{R}\) and \(\mathcal{R}^{-1}\), and \(\Theta_\mathcal{I}\) be the random variable of \(\theta\) when \(\mathcal{A}\) interacts with \(\mathcal{I}\) and \(\mathcal{I}^{-1}\). An attainable transcript is a transcript \(\theta\) such that \(\Pr[\Theta_\mathcal{I}= \theta] > 0\). Then, the coefficient-H technique states the following result:

Lemma 1: Consider a deterministic adversary \(\mathcal{A}\). Partition all the attainable transcripts into two disjoint sets \(\mathcal{T}_\mathrm{good}\) and \(\mathcal{T}_\mathrm{bad}\). Suppose that there exists \(\epsilon_1\) such that \(\Pr[\Theta_\mathcal{I}\in \mathcal{T}_\mathrm{bad}] \le \epsilon_1\), and there exists \(\epsilon_2\) such that, for all \(\theta \in \mathcal{T}_\mathrm{good}\), \(\Pr[\Theta_\mathcal{R}= \theta]/\Pr[\Theta_\mathcal{I}= \theta] \ge 1 - \epsilon_2\). Then we have \(\mathbf{Adv}^\mathrm{sprp}_E(\mathcal{A}) \le \epsilon_1 + \epsilon_2\).

We remark that although Lemma 1 is modified specifically for an SPRP adversary, the coefficient-H technique can be applied to general security definitions. See e.g., [32], [33].

3.  Constructions

3.1  Block Ciphers

Fix \(d\ge 2\). Let \(\widetilde{E}\) be a \(((d-1)n, n)\)-bit TBC and \(K\) be a key of \(\widetilde{E}\). First, we define an encryption round function \(\mathrm{\phi}\) as

\[\begin{aligned} \mathrm{\phi}[\widetilde{E}_K](X^{[1..d]}) = X^{[2..d]} \mathbin{\|}\widetilde{E}_K(X^{[2..d]}, X^1)\,, \end{aligned}\]

where \(X^{[1..d]} \in \{0, 1\}^{dn}\) is the input. See Fig. 1(a). Then, the \(r\)-round single-keyed TBC-based Feistel cipher \(\mathrm{\Phi}_r\) is defined by iterating the round function \(\mathrm{\phi}\) for \(r\) times as follows:

\[\begin{aligned} &\mathrm{\Phi}_r[\widetilde{E}_K](M^{[1..d]})\\ &= \underbrace{\mathrm{\phi}[\widetilde{E}_K] \circ \mathrm{\phi}[\widetilde{E}_K] \circ \dots \circ \mathrm{\phi}[\widetilde{E}_K]}_{\text{$r$ times}}(M^{[1..d]}) \end{aligned}\]

It takes \(M^{[1..d]} \in \{0, 1\}^{dn}\) as input.

Likewise, we define a decryption round function \(\mathrm{\phi}^{-1}\) as

\[\begin{aligned} \mathrm{\phi}^{-1}[\widetilde{E}_K](X^{[1..d]}) = \widetilde{E}^{-1}_K(X^{[1..d-1]}, X^d) \mathbin{\|}X^{[1..d-1]}\,, \end{aligned}\]

where \(X^{[1..d]} \in \{0, 1\}^{dn}\) is the input. Next, the decryption of \(\mathrm{\Phi}_r\), which we write \(\mathrm{\Phi}^{-1}_r\), is defined by repeating \(\mathrm{\phi}^{-1}\) for \(r\) times as follows:

\[\begin{aligned} &\mathrm{\Phi}_r^{-1}[\widetilde{E}_K](C^{[1..d]})\\ &= \underbrace{\mathrm{\phi}^{-1}[\widetilde{E}_K] \circ \mathrm{\phi}^{-1}[\widetilde{E}_K] \circ \dots \circ \mathrm{\phi}^{-1}[\widetilde{E}_K]}_{\text{$r$ times}}(C^{[1..d]}) \end{aligned}\]

It takes \(C^{[1..d]} \in \{0, 1\}^{dn}\) as input.

3.2  Cryptographic Permutations

Let \({\widehat{E}}\) be a \(((d-1)n, n)\)-bit IC. Cryptographic permutations can be defined from an ideal cipher similarly to block ciphers.

With round functions \(\mathrm{\phi}[{\widehat{E}}]\) and \(\mathrm{\phi}^{-1}[{\widehat{E}}]\) shown in Fig. 1(b), where the key of \({\widehat{E}}\) is regarded as a tweak of \(\widetilde{E}_K\) in \(\mathrm{\phi}[\widetilde{E}_K]\), the \(r\)-round single IC-based Feistel cipher, which we write \(\mathrm{\widehat{\Phi}}_r\), is defined as follows:

\[\begin{aligned} &\mathrm{\widehat{\Phi}}_r[{\widehat{E}}](M^{[1..d]}) = \underbrace{\mathrm{\phi}[{\widehat{E}}] \circ \mathrm{\phi}[{\widehat{E}}] \circ \dots \circ \mathrm{\phi}[{\widehat{E}}]}_{\text{$r$ times}}(M^{[1..d]})\\ &\mathrm{\widehat{\Phi}}_r^{-1}[{\widehat{E}}](C^{[1..d]})\\ &= \underbrace{\mathrm{\phi}^{-1}[{\widehat{E}}] \circ \mathrm{\phi}^{-1}[{\widehat{E}}] \circ \dots \circ \mathrm{\phi}^{-1}[{\widehat{E}}]}_{\text{$r$ times}}(C^{[1..d]}) \end{aligned}\]

Cryptographic permutations with round constants are defined by introducing round constants to the key of \(\mathrm{\phi}\). We define an encryption round function \(\mathrm{\phi}_i\) and a decryption round function \(\mathrm{\phi}^{-1}_i\) as follows:

\[\begin{aligned} &\mathrm{\phi}_i[{\widehat{E}}](X^{[1..d]}) = X^{[2..d]} \mathbin{\|}{\widehat{E}}(X^{[2..d]} \oplus c_i^{[2..d]}, X^1)\\ &\mathrm{\phi}^{-1}_i[{\widehat{E}}](X^{[1..d]})\\ &= {\widehat{E}}^{-1}(X^{[1..d-1]} \oplus c_i^{[2..d]}, X^d) \mathbin{\|}X^{[1..d-1]}\,, \end{aligned}\]

where \(c_i^2, \dots, c_i^d\) is an \(n\)-bit constant. See Fig. 1(c). Then the \(r\)-round single IC-based Feistel cipher with round constants \(\mathrm{\widehat{\Phi}}'_r\) is defined as follows:

\[\begin{aligned} &\mathrm{\widehat{\Phi}}'_r[{\widehat{E}}](M^{[1..d]})\\ &= \mathrm{\phi}_r[{\widehat{E}}] \circ \mathrm{\phi}_{r-1}[{\widehat{E}}] \circ \dots \circ \mathrm{\phi}_1[{\widehat{E}}](M^{[1..d]})\\ &\mathrm{\widehat{\Phi}}'^{-1}_r[{\widehat{E}}](C^{[1..d]})\\ &= \mathrm{\phi}^{-1}_1[{\widehat{E}}] \circ \mathrm{\phi}^{-1}_2[{\widehat{E}}] \circ \dots \circ \mathrm{\phi}^{-1}_r[{\widehat{E}}](C^{[1..d]}) \end{aligned}\]

4.  Security of \(\mathrm{\Phi}_r\)

We present three results on \(\mathrm{\Phi}_r\). In Theorem 1, we first show an efficient distinguisher on \(\mathrm{\Phi}_r\) with \(r\le d\). Next, with an additional round, in Theorem 2, we prove that \(\mathrm{\Phi}_r\) with \(r=d\) is provably secure up to \(O(2^{n/2})\) queries. Finally, in Theorem 3, we present a distinguisher that makes \(O(2^{n/2})\) queries against \(\mathrm{\Phi}_r\) for any \(r \ge d+1\). This shows the tightness of Theorem 2, and this also shows that increasing the number of rounds beyond \(r=d+1\) does not increase the security.

We remark that we use a TRP \(\widetilde{E}\) as the underlying TBC, and we thus omit writing the key \(K\), while \(\widetilde{E}\) and \(\mathrm{\Phi}_r = \mathrm{\Phi}_r[\widetilde{E}]\) are still keyed primitives.

4.1  Attack on \(\mathrm{\Phi}_r\) for \(r \le d\)

We have the following theorem for \(\mathrm{\Phi}_r\) for \(r \le d\).

Theorem 1: Fix \(d \ge 2\). Let \(\widetilde{E}\) be the \(((d-1)n, n)\)-bit TRP, and \(\mathrm{\Phi}_r = \mathrm{\Phi}_r[\widetilde{E}]\) be the \(r\)-round single-keyed TBC-based Feistel cipher. Then there exists an adversary \(\mathcal{A}\) against \(\mathrm{\Phi}_r\) with \(r \le d\) such that \(\mathbf{Adv}^\mathrm{prp}_{\mathrm{\Phi}_r}(\mathcal{A})=O(1)\), where \(\mathcal{A}\) makes \(O(1)\) queries.

Proof: Let \(O\) be the oracle, which is either the block cipher \(\mathrm{\Phi}_r\) or the random permutation \(\pi\).

(1) The Attack on \(\mathrm{\Phi}_r\) for \(r \le d-1\).

We first introduce \(\mathcal{A}\) on \(\mathrm{\Phi}_r\) for \(r \le d-1\).

\(\mathcal{A}\) makes an encryption query using an arbitrary message \(M^{[1..d]}\in \{0, 1\}^{dn}\) to obtain the corresponding ciphertext \(C^{[1..d]}\in \{0, 1\}^{dn}\), and returns \(1\) iff \(C^{d-r}=M^d\). In \(\mathrm{\Phi}_r\), \(M^d\) never goes through \(\widetilde{E}\), and it directly appears as \(C^{d-r}\). In \(\pi\), \(C^{d-r}\) is a part of a uniformly random output of \(\pi\), thus \(\mathcal{A}\) outputs \(0\) except for a negligible probability of an \(n\)-bit collision. Therefore \(\mathcal{A}\) can distinguish \(\mathrm{\Phi}_r\) from \(\pi\) with \(1\) query.

An example of \(\mathrm{\Phi}_4\) with \(d=5\) is shown in Fig. 2.

Fig. 2  Structure of \(\mathrm{\Phi}_4\) for \(d = 5\). \(M^5\) directly appears as \(C^1\).

(2) The Attack on \(\mathrm{\Phi}_d\).

We introduce our adversary \(\mathcal{A}\) on \(\mathrm{\Phi}_d\).

\(\mathcal{A}\) first makes an encryption query \(M\) to obtain \(C\), and then makes an encryption query \(M'\) to obtain \(C'\), where \(M'=M^{[1..d-1]}\mathbin{\|}C'^1\). Then \(\mathcal{A}\) outputs \(1\) iff \(C^{[2..d]}=C'^{[1..d-1]}\). In \(\mathrm{\Phi}_d\), the first round of the second query reproduces the second round of the first query. This state collision continues in the subsequent rounds, and eventually, \(C^{[2..d]} = C'^{[1..d-1]}\) always holds. In \(\pi\), \(C^{[2..d]}\) and \(C'^{[1..d-1]}\) are the outputs of random permutation \(\pi\), and hence \(\mathcal{A}\) outputs \(0\) except for a negligible probability of a \((d-1)n\)-bit collision. Therefore, \(\mathcal{A}\) can distinguish \(\mathrm{\Phi}_d\) from \(\pi\) with \(O(1)\) queries.

An example of \(\mathrm{\Phi}_5\) with \(d=5\) is shown in Fig. 3. \(\tag*{◻}\)

Fig. 3  Structure of \(\mathrm{\Phi}_5\) for \(d = 5\). (a) step 1, (b) step 2.

4.2  Security of \(\mathrm{\Phi}_{d+1}\)

We have the following theorem for \(\mathrm{\Phi}_{d+1}\).

Theorem 2: Fix \(d \ge 2\). Let \(\widetilde{E}\) be the \((n, (d-1)n)\)-bit TRP, and \(\mathrm{\Phi}_{d+1} = \mathrm{\Phi}_{d+1}[\widetilde{E}]\) be the \(r\)-round single-keyed TBC-based Feistel cipher, where \(r=d+1\). Then for any adversary \(\mathcal{A}\) that makes at most \(q\) queries, we have

\[\begin{aligned} \mathbf{Adv}^\mathrm{sprp}_{\mathrm{\Phi}_{d+1}}(\mathcal{A}) \le \frac{(4d+1)q^2}{2^n} + \frac{0.5q^2}{2^{dn}}\,. \end{aligned}\]

We present the outline of the proof. The detailed proof is given in Appendix.

Outline of Proof 1: In \(\mathrm{\Phi}_{d+1} = \mathrm{\Phi}_{d+1}[\widetilde{E}]\), we use a single TRP \(\widetilde{E}\), and we write \(\widetilde{E}^i\) to indicate \(\widetilde{E}\) in the \(i\)-th round. Note that \(\widetilde{E}^i = \widetilde{E}\) for all \(i\).

Let \(S=\widetilde{E}^1(M^{[2..d]}, M^1)\), an output of the TRP in the 1st round. We regard \(S\) as the internal state, and we see that, for each of the TRP calls, \(S\) appears as the output block of the TRP (as \(\widetilde{E}^1\)), or as a tweak (as \(\widetilde{E}^2,\ldots,\widetilde{E}^{d}\)), or as the input block (as \(\widetilde{E}^{d+1}\)). See Fig. 4 for an example of \(\mathrm{\Phi}_6\) for \(d=5\).

Fig. 4  Structure of \(\mathrm{\Phi}_6\) for \(d = 5\). \(S\) appears in all the tweaks from \(\widetilde{E}^2\) to \(\widetilde{E}^5\), and is used as an output in \(\widetilde{E}^1\) and an input in \(\widetilde{E}^6\).

Our proof is based on the coefficient-H technique. Let \(M_i^{[1..d]}\), \(S_i\), and \(C_i^{[1..d]}\) be the message, internal state, and the ciphertext of the \(i\)-th query, respectively. We define the bad conditions as follows:

1. \(\{M_1^1, \dots, M_1^d, \dots, M_q^1,\dots , M_q^d\} \cap \{S_1, \dots, S_q\} \ne \emptyset\)

2. \(\{C_1^1, \dots, C_1^d, \dots, C_q^1, \dots, C_q^d\} \cap \{S_1, \dots, S_q\} \ne \emptyset\)

3. \(|\{S_1, \dots, S_q\}| < q\)

Namely, if any of the \(S_i\) collides with other variables, then the transcript is bad.

If \(S_i\) is a unique value, then all the tweaks of \(\widetilde{E}^2, \dots, \widetilde{E}^d\) in the \(i\)-th query are unique. For example, in \(\widetilde{E}^2\) in Fig. 4, \(S_i\) appears in the 4th line of the tweak. It never appears on the same line in other TRPs. Because of this, if \(S_i\) is unique, the tweak of \(\widetilde{E}^2\) never collides with other tweaks. Furthermore, an output of \(\widetilde{E}^1\) and an input of \(\widetilde{E}^{d+1}\) are clearly unique.

Intuitively, without the bad conditions and with an assumption that the adversary does not make redundant queries, we can show that every TRP has at least one unique element in the output block, tweak, or in the input block. This is sufficient to show that all the TRPs, which is actually a single TRP, can interpolate them with a non-zero probability.

The good probabilities are almost the same in \(\mathrm{\Phi}_{d+1}\) and \(\pi\), and from the coefficient-H technique, we obtain the upper bound of the distinguishing advantage.

4.3  Attack on \(\mathrm{\Phi}_r\) for \(r \ge d+1\)

We have the following theorem for \(\mathrm{\Phi}_r\) for \(r \ge d+1\).

Theorem 3: Fix \(d \ge 2\). Let \(\widetilde{E}\) be the \(((d-1)n, n)\)-bit TRP, and \(\mathrm{\Phi}_r = \mathrm{\Phi}_r[\widetilde{E}]\) be the \(r\)-round single-keyed TBC-based Feistel cipher. Then there exists an adversary \(\mathcal{A}\) against \(\mathrm{\Phi}_r\) with \(r \ge d+1\) such that \(\mathbf{Adv}^\mathrm{prp}_{\mathrm{\Phi}_r}(\mathcal{A})=O(1)\), where \(\mathcal{A}\) makes \(O(2^{n/2})\) queries.

Proof: We present our adversary \(\mathcal{A}\) for \(d \ge 3\) and \(r \ge d+1\). We later cover the case \(d=2\).

1. Fix \(M^{[2..d]}\in \{0, 1\}^{(d-1)n}\) arbitrarily.

2. For \(i = 1, \dots, 2^{n/2}\), choose \(M_i^1\) uniformly at random without overlaps, i.e., \(M_i^1\neq M_{i'}^1\) holds for any \(1\le i<i'\le 2^{n/2}\). Then make \(2^{n/2}\) encryption queries \(C_i^{[1..d]} \leftarrow O(M_i^1 \mathbin{\|}M^{[2..d]})\) for \(i = 1, \dots, 2^{n/2}\).

3. For \(j = 1, \dots, 2^{n/2}\), choose \(S'_j\) uniformly at random without overlaps. Then make \(2^{n/2}\) encryption queries \(C'^{[1..d]}_j \leftarrow O(M^{[2..d]} \mathbin{\|}S'_j)\) for \(j = 1, \dots, 2^{n/2}\).

4. If there exists \((i, j)\) s.t. \(C^{[2..d]}_i = C'^{[1..d-1]}_j\), then output 1, else output 0.

This algorithm adopts the same approach as the one for \(\mathrm{\Phi}_d\). However, the internal states \(S_i = \widetilde{E}(M^{[2..d]}, M_i)\) cannot be directly observed. We make \(O(2^{n/2})\) queries so that we have the \(dn\)-bit state collision with a high probability. Let \(q=2^{n/2}\). The collision probability among the \(q\) values of \(S_i\) and \(q\) values of \(S'_j\) can be evaluated as follows:

\[\begin{aligned} &\Pr[\{S_1, \dots, S_q\} \cap \{S'_1, \dots, S'_q\} \ne \emptyset]\\ &\ge \left( 1 - \frac{1}{e} \right) \frac{q(q-1)}{2^n} \approx 0.632 \end{aligned}\]

Here, \(e\) is the base of the natural logarithm and the last approximation follows from \(q = 2^{n/2}\).

As for the random permutation, the probability of the collision among \(C^{[2..d]}_i\) and \(C'^{[1..d-1]}_j\) can be evaluated in a similar way by regarding them as \((d-1)n\)-bit random values. We obtain

\[\begin{aligned} &\Pr[\{C^{[2..d]}_1, \dots, C^{[2..d]}_q\}\\ &\cap \{C'^{[1..d-1]}_1, \dots, C'^{[1..d-1]}_q\} \ne \emptyset]\\ &\le\frac{0.5q^2}{2^{(d-1)n}} =\frac{0.5}{2^{(d-2)n}}\,, \end{aligned}\]

where we used \(q = 2^{n/2}\) for the last equality.

From the discussion above, we obtain the lower bound of the distinguishing advantage as

\[\begin{aligned} \mathbf{Adv}^\mathrm{prp}_{\mathrm{\Phi}_r}(\mathcal{A}) \gtrapprox 0.5 \left( 1 - \frac{1}{2^{(d-2)n}} \right)\,. \end{aligned}\]

An example of \(\mathrm{\Phi}_6\) for \(d=5\) is shown in Fig. 5.

Fig. 5  Structure of \(\mathrm{\Phi}_6\) for \(d = 5\). (a): \(i\)-th query, (b) \(j\)-th query satisfying \(S'_j = S_i\).

If \(d=2\), this algorithm does not work because in \(\pi\), we have an \(n\)-bit output collision in step 4 with a high probability. To deal with this problem, we modify the algorithm as follows:

• 4'  If there exists no \((i, j)\) satisfying \(C^2_i = C'^1_j\), then output 0.

• 5'  For \((i, j)\) s.t. \(C^2_i = C'^1_j\), make encryption queries \(X^{[1..2]} \leftarrow O(C_i^{[1..2]})\) and \(X'^{[1..2]} \leftarrow O(C'^{[1..2]}_j)\).

• 6'  If \(X^2 = X'^1\) holds, then output 1, else output 0.

Steps with a prime symbol are modified or added for \(d=2\). In both \(\mathrm{\Phi}_r\) and \(\pi\), this algorithm aborts in step 4 with almost the same probability, and we see that the algorithm proceeds to steps \(5'\) and \(6'\) with a high probability.

Extra steps (steps \(5'\) and \(6'\)) are based on the distinguisher on \(\mathrm{\Phi}_d\). If \(S_i = S'_j\) holds for some (\(i, j\)) in \(\mathrm{\Phi}_r\), then we see that \(C_i^{[1..2]}\) and \(C'^{[1..2]}_j\) in step \(5'\) are the input and output of the \(r\)-th round of the encryption of \((M^2,S_j')\). Therefore, this algorithm outputs 1 with a high probability in \(\mathrm{\Phi}_r\) and outputs 0 in \(\pi\) with a similar discussion for \(\mathrm{\Phi}_d\). \(\tag*{◻}\)

5.  Security of \(\mathrm{\widehat{\Phi}}_r\)

We have the following theorem for \(\mathrm{\widehat{\Phi}}_r\).

Theorem 4: Fix \(d\ge 2\). Let \({\widehat{E}}\) be the \(((d-1)n,n)\)-bit IC, and \(\mathrm{\widehat{\Phi}}_r=\mathrm{\widehat{\Phi}}_r[{\widehat{E}}]\) be the \(r\)-round single IC-based Feistel cipher. Then for any \(r\ge 1\), \(\mathrm{\widehat{\Phi}}_r\) is not indifferentiable from a random permutation.

Proof: We first consider the case \(r\le d\). Now we see that the same adversary against \(\mathrm{\Phi}_r\) for \(r \le d\) in Sect. 4.1 works as the adversary against \(\mathrm{\widehat{\Phi}}_r\), since the adversary against \(\mathrm{\Phi}_r\) can be regarded as the adversary against \(\mathrm{\widehat{\Phi}}_r\) in the indifferentiability notion that makes only construction queries without making any primitive queries. Although the simulator can make queries to a random permutation \(\pi\), the simulator cannot control \(\pi\)’s entries at all, so that any simulator does not affect the success probability of the adversary.

Next, we consider the case \(r\ge d+1\). We take the approach of the adversary against \(\mathrm{\Phi}_r\) with \(r \ge d+1\) presented in Sect. 4.3. For an arbitrary message \(M^{[1..d]} \in \{0, 1\}^{dn}\), \(\mathcal{A}\) first obtains the output of the 1st round IC by using a primitive query \(S \leftarrow {\widehat{E}}(M^{[2..d]}, M_1)\). Next, \(\mathcal{A}\) makes two construction queries with messages \(M^{[1..d]}\) and \(M^{[2..d]} \mathbin{\|}S\) to obtain ciphertexts \(C^{[1..d]}\) and \(C'^{[1..d]}\). Then \(\mathcal{A}\) outputs \(1\) if \(C^{[2..d]} = C'^{[1..d-1]}\). Otherwise, \(\mathcal{A}\) outputs \(0\).

In \(\mathrm{\widehat{\Phi}}_r\), the ciphertexts \(C^{[1..d]}\) and \(C'^{[1..d]}\) always satisfy \(C^{[2..d]} = C'^{[1..d-1]}\). Observe that the complexity to search for the internal state \(S\) is replaced with a primitive query, and hence \(\mathcal{A}\) runs with \(O(1)\) queries. On the other hand, in \(\pi\), the simulator has to find \(S\) such that the last \((d-1)n\) bits of \(\pi(M^{[1..d]})\) collides with the first \((d-1)n\) bits of \(\pi(M^{[2..d]} \mathbin{\|}S)\). However, finding such \(S\) needs approximately \(O(2^{(d-1)n})\) queries, or there does not exist such \(S\). Therefore, \(\mathcal{A}\) can distinguish \(\mathrm{\widehat{\Phi}}_r\) from \(\pi\) with a high probability. \(\tag*{◻}\)

6.  Indifferentiability of Feistel Cipher with Constants

We have seen in the previous section that for any \(r\ge 1\), \(\mathrm{\widehat{\Phi}}_r[{\widehat{E}}]\) cannot be secure in the indifferentiability notion. The attack can be seen as a type of slide attacks [20], and introducing a round constant is a well-known countermeasure against the attack. In this section, we consider a variant of \(\mathrm{\widehat{\Phi}}_r\) that uses a round constant. One may hope that the round constant prevents the slide attacks. However, we show that this is not the case for \(r=2d-1\) in the indifferentiability notion.

We have the following theorem for \(\mathrm{\widehat{\Phi}}'_{2d-1}\).

Theorem 5: Fix \(d\ge 2\). Let \({\widehat{E}}\) be the \(((d-1)n,n)\)-bit IC, \(c_1^2, \dots, c_1^d, \dots, c_{2d-1}^2, \dots, c_{2d-1}^d\) be the \(n\)-bit round constants, and \(\mathrm{\widehat{\Phi}}'_{2d-1}=\mathrm{\widehat{\Phi}}'_{2d-1}[{\widehat{E}}]\) be the \(r\)-round single IC-based Feistel cipher with round constants, where \(r = 2d-1\). Then \(\mathrm{\widehat{\Phi}}_{2d-1}\) is not indifferentiable from a random permutation.

Proof: We show that \(\mathrm{\widehat{\Phi}}'_{2d-1}\) can be distinguished from \(\pi\) with \(O(1)\) queries.

1. Fix \(S^1_1 = \dots = S^{d-1}_1 = C^1_1 = 0^n\).

2. Obtain \(M^d_1\) by a primitive query of \(\phi_d^{-1}\) with \(S^1_1, \dots, S^{d-1}_1, C^1_1\).

3. Obtain \(C^2_1, \dots, C^d_1\) by primitive queries of \(\phi_{d+1}, \dots, \phi_{2d-1}\) with \(S^1_1, \dots, S^{d-1}_1, C^1_1\).

4. Fix \(S^1_2 = M^d_1 \oplus c^2_{d-1} \oplus c^2_d, S^2_2 = c^3_{d-1} \oplus c^3_d, \dots, S^{d-1}_2 = c^d_{d-1} \oplus c^d_d\), and \(C^1_2 = 0^n\).

5. Obtain \(C^2_2, \dots, C^d_2\) by primitive queries of \(\phi_{d+1}, \dots, \phi_{2d-1}\) with \(S^1_2, \dots, S^{d-1}_2, C^1_2\).

6. Make a construction query \(M^{[1..d]}_1 \leftarrow O^{-1}(C^{[1..d]}_1)\).

7. Make a construction query \(M^{[1..d]}_2 \leftarrow O^{-1}(C^{[1..d]}_2)\).

8. If \(M^{d-1}_1 = M^d_2\) holds, then output 1, else output 0.

An example of \(\mathrm{\widehat{\Phi}}'_7\) with \(d=4\) is shown in Fig. 6.

Fig. 6  Structure of \(\mathrm{\widehat{\Phi}}'_7\). Hatched ICs have the same input block, key, and output block. (a) step 6, (b) step 7.

Figure 7 focuses on \(\phi_{d-1}\) and \(\phi_d\) of the construction. We first fix all the \(d\)-line output of \(\phi_d\) in the 1st query to all zero. At this point, the output of IC in \(\phi_{d-1}\) is also fixed as \(0^n\), which is the hatched IC in Fig. 7(a). The 2nd construction query reproduces the input and output of the hatched IC in the 1st query. Therefore, the bottommost dash-dotted line of the \(\phi_d\) outputs in the 1st and 2nd queries collide. We observe these values as output lines of \(\mathrm{\widehat{\Phi}}'_{2d-1}\) even when \(d-1\) extra rounds are appended to an output side of \(\phi_d\). Furthermore, the inputs of the hatched ICs, namely, the bottommost dashed line of the \(\phi_{d-1}\) input in the 1st query and the penultimate dashed line of the \(\phi_{d-1}\) input in the 2nd query are equal. This collision occurs even when we append \(d-2\) additional rounds to an input side of \(\phi_{d-1}\).

Fig. 7  \(\phi_{d-1}\) and \(\phi_d\) of \(\mathrm{\widehat{\Phi}}'_{2d-1}\). Hatched ICs have the same input block, key, and output block. (a) step 6, (b) step 7.

Now we observe that \(n\)-bit simultaneous collisions on the input and output of the construction. We see that finding such a collision in \(\pi\) is not possible if we consider efficient simulators. Therefore, the probability of \(M^{d-1}_1 = M^d_2\) is negligible in \(\pi\). \(\tag*{◻}\)

As a remark, this algorithm never makes primitive queries once a construction query is made. This implies that \(\mathrm{\widehat{\Phi}}'_{2d-1}[{\widehat{E}}]\) does not achieve the sequential indifferentiability notion [34] which is a weaker notion of indifferentiability.

7.  Conclusions

In this paper, we analyzed the security of the single-keyed TBC-based Feistel ciphers in the indistinguishability notion, and the single IC-based Feistel ciphers in the indifferentiability notion. We completed the security characterization depending on the number of rounds. We also considered a structure that employs a round constant, and showed that this does not work for the case \(r=2d-1\) in the indifferentiability notion.

As open problems, there have been various proposals to modify the PRF-based Feistel cipher so that the security is maintained [4]-[7], and it would be interesting to see how one can modify the single-keyed TBC-based/single IC-based Feistel ciphers to improve the security. With respect to the construction with a round constant, we have only covered the indifferentiability notion of the case \(r=2d-1\), and it would be interesting to see the security with other parameters and/or in the indistinguishability notion.

Acknowledgments

This work was supported by JSPS KAKENHI JP20K11675. The authors thank the anonymous reviewers for careful reading of the paper.

References

[1] K. Tsuji and T. Iwata, “Feistel ciphers based on a single primitive,” Cryptography and Coding - 19th IMA International Conference, IMACC 2023, London, UK, Proceedings, E.A. Quaglia, ed., Lecture Notes in Computer Science, vol.14421, pp.57-79, Springer, 2023.

[2] M. Luby and C. Rackoff, “How to construct pseudorandom permutations from pseudorandom functions,” SIAM J. Comput., vol.17, no.2, pp.373-386, 1988.

[3] Y. Zheng, T. Matsumoto, and H. Imai, “Impossibility and optimality results on constructing pseudorandom permutations (extended abstract),” Advances in Cryptology - EUROCRYPT ’89, Workshop on the Theory and Application of of Cryptographic Techniques, Houthalen, Belgium, Proceedings, J. Quisquater and J. Vandewalle, eds., Lecture Notes in Computer Science, vol.434, pp.412-422, Springer, 1989.

[4] J. Pieprzyk, “How to construct pseudorandom permutations from single pseudorandom functions,” Advances in Cryptology - EUROCRYPT’90, Workshop on the Theory and Application of of Cryptographic Techniques, Aarhus, Denmark, Proceedings, I. Damgård, ed., Lecture Notes in Computer Science, vol.473, pp.140-150, Springer, 1990.

[5] J. Patarin, “How to construct pseudorandom and super pseudorandom permutations from one single pseudorandom function,” Advances in Cryptology - EUROCRYPT’92, Workshop on the Theory and Application of of Cryptographic Techniques, Balatonfüred, Hungary, Proceedings, R.A. Rueppel, ed., Lecture Notes in Computer Science, vol.658, pp.256-266, Springer, 1992.

[6] M. Nandi, “The characterization of luby-rackoff and its optimum single-key variants,” Progress in Cryptology - INDOCRYPT 2010 - 11th International Conference on Cryptology in India, Hyderabad, India, Proceedings, G. Gong and K.C. Gupta, eds., Lecture Notes in Computer Science, vol.6498, pp.82-97, Springer, 2010.

[7] M. Nandi, “On the optimality of non-linear computations of length-preserving encryption schemes,” Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, Proceedings, Part II, T. Iwata and J.H. Cheon, eds., Lecture Notes in Computer Science, vol.9453, pp.113-133, Springer, 2015.

[8] M.D. Liskov, R.L. Rivest, and D.A. Wagner, “Tweakable block ciphers,” J. Cryptol., vol.24, no.3, pp.588-613, 2011.

[9] K. Minematsu, “Beyond-birthday-bound security based on tweakable block cipher,” Fast Software Encryption, 16th International Workshop, FSE 2009, Leuven, Belgium, Revised Selected Papers, O. Dunkelman, ed., Lecture Notes in Computer Science, vol.5665, pp.308-326, Springer, 2009.

[10] J. Coron, Y. Dodis, A. Mandal, and Y. Seurin, “A domain extender for the ideal cipher,” Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, Proceedings, D. Micciancio, ed., Lecture Notes in Computer Science, vol.5978, pp.273-289, Springer, 2010.

[11] U.M. Maurer, R. Renner, and C. Holenstein, “Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology,” Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, Proceedings, M. Naor, ed., Lecture Notes in Computer Science, vol.2951, pp.21-39, Springer, 2004.

[12] J. Coron, T. Holenstein, R. Künzler, J. Patarin, Y. Seurin, and S. Tessaro, “How to build an ideal cipher: The indifferentiability of the feistel construction,” J. Cryptol., vol.29, no.1, pp.61-114, 2016.

[13] D. Dachman-Soled, J. Katz, and A. Thiruvengadam, “10-round feistel is indifferentiable from an ideal cipher,” Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, Proceedings, Part II, M. Fischlin and J. Coron, eds., Lecture Notes in Computer Science, vol.9666, pp.649-678, Springer, 2016.

[14] Y. Dai and J.P. Steinberger, “Indifferentiability of 8-round feistel networks,” Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, Proceedings, Part I, M. Robshaw and J. Katz, eds., Lecture Notes in Computer Science, vol.9814, pp.95-120, Springer, 2016.

[15] R. Bhaumik, M. Nandi, and A. Raychaudhuri, “Improved indifferentiability security proof for 3-round tweakable luby-rackoff,” Des. Codes Cryptogr., vol.89, no.10, pp.2255-2281, 2021.

[16] K. Minematsu, “Building blockcipher from small-block tweakable blockcipher,” Des. Codes Cryptogr., vol.74, no.3, pp.645-663, 2015.

[17] R. Nakamichi and T. Iwata, “Iterative block ciphers from tweakable block ciphers with long tweaks,” IACR Trans. Symmetric Cryptol., vol.2019, no.4, pp.54-80, 2019.

[18] C. Guo and D. Lin, “Improved domain extender for the ideal cipher,” Cryptogr. Commun., vol.7, no.4, pp.509-533, 2015.

[19] R. Nakamichi and T. Iwata, “Beyond-birthday-bound secure cryptographic permutations from ideal ciphers with long keys,” IACR Trans. Symmetric Cryptol., vol.2020, no.2, pp.68-92, 2020.

[20] A. Biryukov and D.A. Wagner, “Slide attacks,” Fast Software Encryption, 6th International Workshop, FSE’99, Rome, Italy, Proceedings, L.R. Knudsen, ed., Lecture Notes in Computer Science, vol.1636, pp.245-259, Springer, 1999.

[21] E. Andreeva, A. Bogdanov, Y. Dodis, B. Mennink, and J.P. Steinberger, “On the indifferentiability of key-alternating ciphers,” Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, Proceedings, Part I, R. Canetti and J.A. Garay, eds., Lecture Notes in Computer Science, vol.8042, pp.531-550, Springer, 2013.

[22] S. Chen, R. Lampe, J. Lee, Y. Seurin, and J.P. Steinberger, “Minimizing the two-round even-mansour cipher,” Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, Proceedings, Part I, J.A. Garay and R. Gennaro, eds., Lecture Notes in Computer Science, vol.8616, pp.39-56, Springer, 2014.

[23] I. Dinur, O. Dunkelman, N. Keller, and A. Shamir, “Cryptanalysis of iterated even-mansour schemes with two keys,” 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.439-457, Springer, 2014.

[24] B. Cogliati and Y. Seurin, “On the provable security of the iterated even-mansour cipher against related-key and chosen-key attacks,” Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, Proceedings, Part I, E. Oswald and M. Fischlin, eds., Lecture Notes in Computer Science, vol.9056, pp.584-613, Springer, 2015.

[25] S. Xu, Q. Da, and C. Guo, “Minimizing even-mansour ciphers for sequential indifferentiability (without key schedules),” Progress in Cryptology - INDOCRYPT 2022 - 23rd International Conference on Cryptology in India, Kolkata, India, Proceedings, T. Isobe and S. Sarkar, eds., Lecture Notes in Computer Science, vol.13774, pp.125-145, Springer, 2022.

[26] S. Xu, Q. Da, and C. Guo, “Chosen-key secure even-mansour cipher from a single permutation,” IACR Trans. Symmetric Cryptol., vol.2023, no.1, pp.244-287, 2023.

[27] J. Daemen, L.R. Knudsen, and V. Rijmen, “The block cipher square,” Fast Software Encryption, 4th International Workshop, FSE’97, Haifa, Israel, Proceedings, E. Biham, ed., Lecture Notes in Computer Science, vol.1267, pp.149-165, Springer, 1997.

[28] A. Biryukov and A. Shamir, “Structural cryptanalysis of SASAS,” J. Cryptol., vol.23, no.4, pp.505-518, 2010.

[29] I. Dinur, O. Dunkelman, and A. Shamir, “Improved attacks on full GOST,” Fast Software Encryption - 19th International Workshop, FSE 2012, Washington, DC, USA, Revised Selected Papers, A. Canteaut, ed., Lecture Notes in Computer Science, vol.7549, pp.9-28, Springer, 2012.

[30] T. Isobe and K. Shibutani, “Generic key recovery attack on feistel scheme,” Advances in Cryptology - ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, Proceedings, Part I, K. Sako and P. Sarkar, eds., Lecture Notes in Computer Science, vol.8269, pp.464-485, Springer, 2013.

[31] A. Bar-On, E. Biham, O. Dunkelman, and N. Keller, “Efficient slide attacks,” J. Cryptol., vol.31, no.3, pp.641-670, 2018.

[32] J. Patarin, “The “Coefficients H” technique,” Selected Areas in Cryptography, 15th International Workshop, SAC 2008, Sackville, New Brunswick, Canada, Revised Selected Papers, R.M. Avanzi, L. Keliher, and F. Sica, eds., Lecture Notes in Computer Science, vol.5381, pp.328-345, Springer, 2008.

[33] S. Chen and J.P. Steinberger, “Tight security bounds for key-alternating ciphers,” Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, Proceedings, P.Q. Nguyen and E. Oswald, eds., Lecture Notes in Computer Science, vol.8441, pp.327-350, Springer, 2014.

[34] A. Mandal, J. Patarin, and Y. Seurin, “On the public indifferentiability and correlation intractability of the 6-round feistel construction,” Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, Proceedings, R. Cramer, ed., Lecture Notes in Computer Science, vol.7194, pp.285-302, Springer, 2012.

Appendix: Security Proof of \(\mathrm{\Phi}_{d+1}\)

We show the detailed proof of Theorem 2. We recall the theorem.

Theorem 2: Fix \(d \ge 2\). Let \(\widetilde{E}\) be the \((n, (d-1)n)\)-bit TRP, and \(\mathrm{\Phi}_{d+1} = \mathrm{\Phi}_{d+1}[\widetilde{E}]\) be the \(r\)-round single-keyed TBC-based Feistel cipher, where \(r=d+1\). Then for any adversary \(\mathcal{A}\) that makes at most \(q\) queries, we have

\[\begin{aligned} \mathbf{Adv}^\mathrm{sprp}_{\mathrm{\Phi}_{d+1}}(\mathcal{A}) \le \frac{(4d+1)q^2}{2^n} + \frac{0.5q^2}{2^{dn}}\,. \end{aligned}\]

We first define the transcripts followed by two oracles, the real world oracle based on \(\mathrm{\Phi}_{d+1}\) and the ideal world oracle based on the random permutation \(\pi\), and the bad conditions. Next, we compute the bad probability in Lemma 2 and the good probability ratio in Lemma 3. The security bound is obtained from these lemmas and the coefficient-H technique in Lemma 1.

A.1 Transcripts

The adversary \(\mathcal{A}\) is given access to the encryption and decryption oracles. If the \(i\)-th query is an encryption query \(M_i^{[1..d]}\), then \(\mathcal{A}\) obtains the corresponding ciphertext \(C_i^{[1..d]}\). If the \(i\)-th query is a decryption query \(C_i^{[1..d]}\), then \(\mathcal{A}\) obtains \(M_i^{[1..d]}\). Without loss of generality, we assume that \(\mathcal{A}\) makes exactly \(q\) queries, does not repeat a query, and does not make a redundant query, i.e., if \(\mathcal{A}\) obtains \(C_i^{[1..d]}\) for an encryption query \(M_i^{[1..d]}\), then it does not use \(C_i^{[1..d]}\) in the subsequent decryption queries, and vice versa. As we detail below, after making \(q\) queries and before returning the decision bit, \(\mathcal{A}\) is given all the internal state values \(S_1,\ldots,S_q\). Since it is only beneficial to \(\mathcal{A}\), there is no loss of generality of giving the additional input to \(\mathcal{A}\). Then the transcript is defined as follows:

\[\begin{align} ((M_1^{[1..d]},C_1^{[1..d]}),\ldots,(M_q^{[1..d]},C_q^{[1..d]}),S_1,\ldots,S_q) \tag{A$\cdot $1} \end{align}\]

A.2 Definition of the Oracles

The real world oracles \(\mathcal{R}, \mathcal{R}^{-1}\) internally make use of the block cipher \(\mathrm{\Phi}_{d+1}\) and its inverse \(\mathrm{\Phi}_{d+1}^{-1}\). After making \(q\) queries, the oracles \(\mathcal{R}, \mathcal{R}^{-1}\) give \(\mathcal{A}\) all the internal states \(S_1, \dots, S_q\). Fig.A⋅1 shows the algorithms of \(\mathcal{R}, \mathcal{R}^{-1}\).

Fig. A⋅1  Algorithm of \(\mathcal{R}\) and \(\mathcal{R}^{-1}\).

The ideal world oracles \(\mathcal{I}, \mathcal{I}^{-1}\) internally make use of the random permutation \(\pi\) and its inverse \(\pi^{-1}\). After \(q\) queries, \(\mathcal{I}, \mathcal{I}^{-1}\) generate dummy internal states \(S_1, \dots, S_q\) with the same probability distribution as TRP \(\widetilde{E}\). For this, for an encryption query, the oracle simulates the 1st round TRP. For a decryption query, the oracle simulates the \((d+1)\)-st round TRP. After completing the simulation, \(S_1, \dots, S_q\) are given to \(\mathcal{A}\). Fig. A⋅2 shows the algorithms of \(\mathcal{I}, \mathcal{I}^{-1}\).

Fig. A⋅2  Algorithm of \(\mathcal{I}\) and \(\mathcal{I}^{-1}\), where \(\mathrm{Dom}(T)\) and \(\mathrm{Ran}(T)\) are defined as \(\mathrm{Dom}(T) = \{x \mid \widetilde{E}(T, x) = y \mbox{ is defined for some } y\}\) and \(\mathrm{Ran}(T) = \{y \mid \widetilde{E}(T, x) = y \mbox{ is defined for some } x\}\).

A.3 Bad Conditions

For the TRP \(\widetilde{E}\) in the real world, the tweak determines the permutation between the input and output of the TRP. Accordingly, if the tweaks are the same, the TRP does not output distinct outputs from the same inputs or distinct inputs from the same outputs. By applying this to all the combinations of the TRPs in \(\mathrm{\Phi}_{d+1}\), we obtain the bad conditions of the whole structure of \(\mathrm{\Phi}_{d+1}\) as follows:

1. \(\{M_1^1, \dots, M_1^d, \dots, M_q^1,\dots , M_q^d\} \cap \{S_1, \dots, S_q\} \ne \emptyset\)

2. \(\{C_1^1, \dots, C_1^d, \dots, C_q^1, \dots, C_q^d\} \cap \{S_1, \dots, S_q\} \ne \emptyset\)

3. \(|\{S_1, \dots, S_q\}| < q\)

Recall that a transcript is defined as (A\(\cdot\)1), and let \(\mathcal{T}_\mathrm{bad}\) be the set of all the transcripts that satisfy at least one of the conditions above. Let \(\mathcal{T}_\mathrm{good}\) be the set of all the transcripts that does not satisfy any of the conditions above.

In what follows, we discuss the correctness of the above bad conditions, i.e., without the bad conditions, we show that the underlying TRP \(\widetilde{E}\) can interpolate all the relevant inputs, tweaks, and the outputs with a non-zero probability. See Fig. 4 for an example of \(\mathrm{\Phi}_6\).

First, observe that the absence of the above three conditions guarantees that all the tweaks in \(\widetilde{E}^2\), …, \(\widetilde{E}^d\) are distinct. That is, there are \(q\) tweaks for each of \(\widetilde{E}^2, \dots, \widetilde{E}^d\), and we thus have \(q(d-1)\) values of the tweak in total for \(\widetilde{E}^2, \dots, \widetilde{E}^d\). It can be verified that all these \(q(d-1)\) values are distinct, and they are also different from the \(q\) tweaks of \(\widetilde{E}^1\) and the \(q\) tweaks of \(\widetilde{E}^{d+1}\).

Next, let \(\mathcal{T}^1=\{M_1^{[2..d]},\ldots,M_q^{[2..d]}\}\) be the set of the \(q\) tweaks of \(\widetilde{E}^1\) and \(\mathcal{T}^{d+1}=\{C_1^{[1..d-1]},\ldots,C_q^{[1..d-1]}\}\) be the set of the \(q\) tweaks of \(\widetilde{E}^{d+1}\). From the discussion above, all these \(2q\) tweaks are different from those of \(\widetilde{E}^2\), …, \(\widetilde{E}^d\), while we may have \(|\mathcal{T}^1|<q\), \(\mathcal{T}^1\cap\mathcal{T}^{d+1}\neq\emptyset\), or \(|\mathcal{T}^{d+1}|<q\).

• If \(|\mathcal{T}^1|<q\), i.e., if \(M_i^{[2..d]}=M_j^{[2..d]}\) holds for some \(1\le i<j\le q\), we necessary have \(M^1_i\neq M^1_j\) since the adversary does not repeat a query, and from \(S_i\neq S_j\), this case does not yield inconsistency in \(\widetilde{E}\).

• If \(\mathcal{T}^1\cap\mathcal{T}^{d+1}\neq\emptyset\), there are two cases to consider.
  The first case is \(M_i^{[2..d]}=C_j^{[2..d]}\) for some \(1\le i<j\le q\). In this case, \(\widetilde{E}^1\) and \(\widetilde{E}^{d+1}\) have to satisfy \(S_i=\widetilde{E}^1(M_i^{[2..d]},M_i^1)\) and \(C_j^d=\widetilde{E}^{d+1}(C_j^{[1..d-1]},S_j)\), which is possible since \(S_i\neq C_j^d\) and \(M_i^1\neq S_j\).
  The second case is \(M_i^{[2..d]}=C_i^{[2..d]}\) for some \(1\le i\le q\). In this case, \(\widetilde{E}^1\) and \(\widetilde{E}^{d+1}\) have to satisfy \(S_i=\widetilde{E}^1(M_i^{[2..d]},M_i^1)\) and \(C_i^d=\widetilde{E}^{d+1}(C_i^{[1..d-1]},S_i)\), which is again possible since \(S_i\neq C_i^d\) and \(M_i^1\neq S_i\).

• The analysis of the case \(|\mathcal{T}^{d+1}|<q\) is similar to the case \(|\mathcal{T}^1|<q\).

Therefore, the absence of the bad conditions implies that the TRP \(\widetilde{E}\) can interpolate all the relevant inputs, tweaks, and the outputs with a non-zero probability. We next compute the probability of the bad conditions and the ratio of the good probabilities to use the coefficient-H Technique.

A.4 Probability of the Bad Conditions

We have the following lemma.

Lemma 2: We have \(\Pr[\Theta_\mathcal{I}\in \mathcal{T}_\mathrm{bad}] \le \dfrac{(4d+1)q^2}{2^n}\).

Proof: We compute the probability of the bad conditions based on the randomness of \(S_1,\dots,S_q\). Assume that \(\mathcal{A}\) has completed making \(q\) queries to the oracles, and hence \((M_1^{[1..d]},C_1^{[1..d]}),\ldots,(M_q^{[1..d]},C_q^{[1..d]})\) are fixed. We further assume that we do not have the bad conditions for \(S_1,\ldots,S_{i-1}\), and we compute the probability that \(S_i\) causes one of the bad conditions, which we write “\(S_i\) is bad.” We then have

\[\begin{aligned} \Pr[\mbox{$S_i$ is bad}] &\le \frac{2dq + (i-1)}{2^n - 2q}\,. \end{aligned}\]

The term \(2q\) of the denominator indicates the maximum value of \(|\mathrm{Ran}(M_i^{[2..d]})|\) or \(|\mathrm{Dom}(C_i^{[1..d-1]})|\). Due to the uniqueness of \(S_1, \dots, S_{i-1}\), the tweaks of TRPs other than \(\widetilde{E}^1\) and \(\widetilde{E}^{d+1}\) also have unique values. Therefore, \(|\mathrm{Ran}(M_i^{[2..d]})|\) or \(|\mathrm{Dom}(C_i^{[1..d-1]})|\) takes the maximum value of \(2q\) when \(M_j^{[2..d]}\) and \(C_j^{[1..d-1]}\) take the same value for all \(j = 1, \dots, i-1\). Besides, from the uniqueness of \(S_1, \dots, S_{i-1}\) and the assumption that no queries are repeated, it is guaranteed that the corresponding entry, i.e., \((M_i^{[2..d]},M_i^{1})\) for encryption or \((C_i^{[1..d-1]},C_i^{d})\) for decryption, does not exist at the generation of \(S_i\). That is, \(S_i\) has randomness when generating it.

Now, by taking the summation of \(\Pr[\mbox{$S_i$ is bad}]\), we have

\[\begin{aligned} \Pr[\Theta_\mathcal{I}\in \mathcal{T}_\mathrm{bad}] &\le \sum_{i=1}^q \frac{2dq + (i-1)}{2^n - 2q}\\ &\le \frac{(2d+0.5)q^2}{2^n - 2q}\\ &\le \frac{(4d+1)q^2}{2^n}\,, \end{aligned}\]

where the third inequality follows from \(2q < 2^{n-1}\).

A.5 Ratio of the Good Probabilities

We have the following lemma.

Lemma 3: For any \(\theta \in \mathcal{T}_\mathrm{good}\), we have \(\dfrac{\Pr[\Theta_\mathcal{R}= \theta]}{\Pr[\Theta_\mathcal{I}= \theta]} \ge 1 - \dfrac{0.5q^2}{2^{dn}}\).

Proof: First, we define the following two sets:

\[\begin{aligned} Q_e &= \{i \mid \mbox{the $i$-th query is encryption}\}\\ Q_d &= \{i \mid \mbox{the $i$-th query is decryption}\} \end{aligned}\]

In the real world, we additionally define two sets as follows:

\[\begin{aligned} &S^{\mathrm{enc},x}_i = \{(j, k)\\ &\mid ((j<i \land 1 \le k \le d+1) \lor (j=i \land 1 \le k < x))\\ &\land \mbox{(the $j$-th tweak of $\widetilde{E}^k$)} = \mbox{(the $i$-th tweak of $\widetilde{E}^x$)} \}\\ &S^{\mathrm{dec},x}_i = \{(j, k)\\ &\mid ((j<i \land 1 \le k \le d+1) \lor (j=i \land x < k \le d+1))\\ &\land \mbox{(the $j$-th tweak of $\widetilde{E}^k$)} = \mbox{(the $i$-th tweak of $\widetilde{E}^x$)} \} \end{aligned}\]

Intuitively, \(S^{\mathrm{enc},x}_i\) is the set of \((j,k)\) that shares the same tweak as the \(i\)-th tweak of \(\widetilde{E}^x\) when the \(i\)-th query is encryption, and \(S^{\mathrm{dec},x}_i\) is that when the \(i\)-th query is decryption. That is, for the \(i\)-th tweak of \(\widetilde{E}^x\), these sets indicate the indices that share the same tweak in the previous TRP calls. Then, the probability can be evaluated as follows:

\[\begin{aligned} &\Pr[\Theta_\mathcal{R}= \theta]\\ &= \prod_{x=1}^{d+1} \left( \prod_{i \in Q_e} \frac{1}{2^n - |S^{\mathrm{enc},x}_i|} \times \prod_{i \in Q_d} \frac{1}{2^n - |S^{\mathrm{dec},x}_i|} \right)\\ &\ge \frac{1}{(2^n)^{dq}} \times \prod_{i \in Q_e} \frac{1}{2^n - |S^{\mathrm{enc},1}_i|} \times \prod_{i \in Q_d} \frac{1}{2^n - |S^{\mathrm{dec},d+1}_i|}\,. \end{aligned}\]

The last inequality is obtained by assuming \(|S^{\mathrm{enc},x}_i| = |S^{\mathrm{dec},x}_i| = 0\) except for \(|S^{\mathrm{enc},1}_i|\) and \(|S^{\mathrm{dec},d+1}_i|\).

In the ideal world, as with the real world, we define two sets as follows:

\[\begin{aligned} &T^{\mathrm{enc},x}_i = \{(j, k)\\ &\mid ((j<i \land 1 \le k \le d+1) \lor (j=i \land 1 \le k < x))\\ &\land \mbox{(the $j$-th tweak of $\widetilde{E}^k$)}= \mbox{(the $i$-th tweak of $\widetilde{E}^x$)} \}\\ &T^{\mathrm{dec},x}_i = \{(j, k)\\ &\mid ((j<i \land 1 \le k \le d+1) \lor (j=i \land x < k \le d+1))\\ &\land \mbox{(the $j$-th tweak of $\widetilde{E}^k$)}= \mbox{(the $i$-th tweak of $\widetilde{E}^x$)} \}\,. \end{aligned}\]

Here, in the definitions above, we abuse the notation to write \(\widetilde{E}^k\) for the TRP \(\widetilde{E}\) used in the \(k\)-th round in Algorithm 5. Then, the probability can be evaluated as follows:

\[\begin{aligned} &\Pr[\Theta_\mathcal{I}= \theta]\\ &= \frac{1}{(2^{dn})_q} \times \prod_{i \in Q_e} \frac{1}{2^n - |T^{\mathrm{enc},1}_i|} \times \prod_{i \in Q_d} \frac{1}{2^n - |T^{\mathrm{dec},d+1}_i|}\,. \end{aligned}\]

Finally, we compute the ratio of the two possibilities. We have

\[\begin{aligned} &\frac{\Pr[\Theta_\mathcal{R}= \theta]}{\Pr[\Theta_\mathcal{I}= \theta]}\\ &\ge \frac{(2^{dn})_q}{(2^n)^{dq}} \times \prod_{i \in Q_e} \frac{2^n - |S^{\mathrm{enc},1}_i|}{2^n - |T^{\mathrm{enc},1}_i|} \times \prod_{i \in Q_d} \frac{2^n - |S^{\mathrm{dec},d+1}_i|}{2^n - |T^{\mathrm{dec},d+1}_i|}\\ & \ge 1 - \frac{0.5q^2}{2^{dn}}\,, \end{aligned}\]

where the last inequality follows since \(S^{\mathrm{enc},x}_i = T^{\mathrm{enc},x}_i\) and \(S^{\mathrm{dec},x}_i = T^{\mathrm{dec},x}_i\) are always satisfied from the definitions of the oracles.

From Lemma 2, Lemma 3, and the coefficient-H technique, we obtain Theorem 2.

Authors

Kento TSUJI
  Nagoya University

Tetsu IWATA
  Nagoya University

Keyword

feistel cipher,  tweakable block cipher,  ideal cipher,  provable security