On a Generalization of Substitution-Permutation Networks: The HADES Design Strategy

Abstract

Keyed and unkeyed cryptographic permutations often iterate simple round functions. Substitution-permutation networks (SPNs) are an approach that is popular since the mid 1990s. One of the new directions in the design of these round functions is to reduce the substitution (S-Box) layer from a full one to a partial one, uniformly distributed over all the rounds. LowMC and Zorro are examples of this approach.

A relevant freedom in the design space is to allow for a highly nonuniform distribution of S-Boxes. However, choosing rounds that are so different from each other is very rarely done, as it makes security analysis and implementation much harder.

We develop the design strategy Hades and an analysis framework for it, which despite this increased complexity allows for security arguments against many classes of attacks, similar to earlier simpler SPNs. The framework builds upon the wide trail design strategy, and it additionally allows for security arguments against algebraic attacks, which are much more of a concern when algebraically simple S-Boxes are used.

Subsequently, this is put into practice by concrete instances and benchmarks for a use case that generally benefits from a smaller number of S-Boxes and showcases the diversity of design options we support: A candidate cipher natively working with objects in \text{GF}(p), for securing data transfers with distributed databases using secure multiparty computation (MPC). Compared to the currently fastest design MiMC, we observe significant improvements in online bandwidth requirements and throughput with a simultaneous reduction of preprocessing effort, while having a comparable online latency.

Keywords: Hades Strategy – Cryptographic Permutations – Secure Multiparty Computation (MPC)

Updated Version

This updated version differs from the one appeared at Eurocrypt 2020 mainly for the following reasons: (1) a different linear layer matrix that prevents infinitely long subspace trails for rounds with partial S-Box layers, (2) a generic S-Box replacing the cube S-Box S(x) = x^3 with S(x) = x^\alpha where \alpha \geq 3 is the smallest integer such that \gcd(p-1, \alpha) = 1, and (3) updated cryptanalysis incorporating recently published attacks.

1. Introduction

Starting out with a layer of local substitution boxes (S-Boxes), combining it with a global permutation box (sometimes merely wires, sometimes affine transformations), and iterating such a round a number of times is a major design approach in symmetric cryptography. The resulting constructions are often referred to as substitution-permutation networks (SPNs) and are used to instantiate block ciphers, permutations, pseudo-random functions (PRFs), one-way functions, hash functions, and various other constructions. The approach can be traced back to Shannon's confusion-diffusion paradigm. There is a considerable amount of efficient designs that exploit this design strategy, including Rijndael/AES [DR02] which is perhaps the most important one.

Driven by various new application areas and settings, a variation of the SPN approach – the so-called partial substitution-permutation network (P-SPN) – has been proposed and investigated on the practical side [5,30]. The idea is to replace parts of the substitution layer with an identity mapping, leading to substantial practical advantages. A big caveat of this approach is that existing elegant approaches to rule out large classes of attacks via the so-called wide trail strategy [DR01] are no longer applicable and have to be replaced by more ad-hoc approaches.

Our Contribution in a Nutshell. We propose a new generalization of SPNs, which we call the “Hades” approach. It (1st) restores the ability to apply the elegant wide trail strategy to rule out important classes of attacks, (2nd) is accompanied with a broad framework to rule out various other attack vectors for many relevant instantiation possibilities, and (3rd) is demonstrated to result in even better implementation characteristics in the same application domains P-SPNs have been introduced for.

Referring to the figure of the S-Box layout and the bident shape, if one highlights the S-Boxes per round, the obtained picture resembles a “bident”. In classical mythology, the bident is a weapon associated with Hades, the ruler of the underworld.

[Figure 1: SP-Networks and Generalizations (P-SPNs and Hades) – illustrates the progression from full SPN to partial SPN to the HADES approach, where the first and last rounds use full S-Box layers and the middle rounds use partial S-Box layers.]

1.1 The Big Caveat: Security Analysis of P-SPNs

The wide trail strategy cannot guarantee security against all attacks in the literature. As a concrete example, algebraic attacks that exploit the low degree of the encryption or decryption function – like the interpolation attack [JK97] or the higher-order differential one [Knu94] – are (almost) independent of the linear layer used in the round transformation, which is the crucial point of such a design strategy. In other words, especially in the case of a low-degree S-Box, the wide trail strategy is not sufficient by itself, and it must be combined with something else to guarantee security against all known attacks.

Moreover, the “hidden” assumption of such a strategy is that each round contains a full S-Box layer. Even if this is a well accepted practice, there are various applications/contexts in which non-linear operations are much less expensive than linear ones, including masking and practical applications of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZK).

How Risky are Partial SP Networks? The wide trail strategy and tools that were developed in order to formally prove the security of block ciphers against standard differential and linear cryptanalysis do not apply to partial SP networks such as Zorro. Even though the authors of Zorro came up with a dedicated approach to show security, this turned out to be insufficient, as Wang et al. [WWGY14] found iterative differential and linear characteristics that were missed by the heuristic and used them to break full Zorro.

Similarly, the authors of LowMC chose the number of rounds to guarantee that no differential/linear characteristic can cover the whole cipher with non-negligible probability. However, they do not provide such strong security arguments against other attack vectors including algebraic attacks. As a result, the security of earlier versions of LowMC against algebraic attacks was found to be lower than expected [25,27], and full key-recovery attacks on LowMC have been set up.

1.2 The Idea in a Nutshell – The HADES Strategy

Summarizing the current situation: The wide trail strategy is appealing due to its simplicity, but limited to differential and linear attacks, and does not work with partial S-Box layers. Additionally, when S-Boxes are chosen to have a low degree, other attack vectors are more relevant anyhow. Designs of this type, like Zorro and LowMC, require a lot of ad-hoc analysis.

To address this issue we propose to start with a classical wide trail design, i.e., with a full S-Box layer (outer layer), and then add a part with full and/or partial S-Box layers in the middle. Even without the middle part, the outer layer in itself is supposed to give arguments against differential and linear attacks in exactly the same way the wide trail strategy does. At the same time, arguments against low-degree attacks can be obtained working on the middle layer. Since algebraic attacks exploit the small degree of the encryption/decryption function, the main role of this middle part is to achieve a high degree, with perhaps only few (e.g., one) S-Boxes per round.

Depending on the cost metric of the target application one has in mind (e.g., minimizing the total number of non-linear operations), we show that the best solution is to choose the optimal ratio between the number of rounds with full S-Box layers and with partial S-Box layers in order to achieve both security and performance. We refer to this high-level approach as the “Hades” strategy.

1.3 Related Work – Designs with Different Round Functions

Almost all designs for block ciphers and permutations use round functions that are very similar, differing often only in round constants which break symmetries to prevent slide attacks. Notable exceptions include the AES finalist MARS, the lightweight cipher PRINCE [BCG+12] and the cipher Rescue [AAB+19], recently proposed for ZK-STARK proof systems and MPC applications. MARS has whitening rounds with a different structure than the inner rounds. PRINCE rounds differ in that the latter half of the rounds is essentially the inverse of the first half, with a special middle round. Similar to PRINCE, each round of Rescue is composed of two steps, which are respectively a non-linear S-Box layer and its inverse. We also mention the cases of LowMC [ARS+15] and Rasta [DEG+18], for which different (independent and random) linear layers are used in each round. In none of these cases, however, the amount of non-linearity, and hence their cryptographic strength, differs over the rounds.

1.4 HadesMiMC: Concrete Instantiations for MPC Applications

MPC. There is a large application area around secure multi-party computation. The setting is a secret-sharing-based MPC system where data is often shared as elements of a finite field \mathbb{F}_p for large p. In order to get data securely in and out of such a system, an efficient solution can be to directly evaluate a symmetric primitive within the MPC system. “Traditional” PRFs such as AES are not efficient in this setting, since they are built for computational engines which work over data types that do not easily match the operations possible in the MPC engine.

Concrete Instances. For our concrete instantiations of HadesMiMC, we borrow ideas from the pre-predecessor of AES, namely SHARK [RDP+96], an SPN design with a single large MDS layer covering the whole internal state. Concretely specified instances, both full and toy versions, together with their reference implementation, test vectors, and helper scripts are available online.

When benchmarking our new design HadesMiMC for MPC applications, we observe significant improvements in online bandwidth requirements and throughput with a simultaneous reduction of preprocessing effort with respect to MiMC and Rescue, while having a comparable online latency. A variant of HadesMiMC has been proposed [GKR+19] for use cases of efficient proof systems like STARKs, SNARKs and Bulletproofs, for which they outperform competing designs, often by a large margin.

2. Description of the HADES Strategy

Block ciphers and cryptographic permutations are typically designed by iterating an efficiently implementable round function many times. In general, the same round function is iterated enough times to make sure that any symmetries and structural properties vanish. In our case, instead of considering the same non-linear layer for all rounds, we propose to consider a variable number of S-Boxes per round.

Each round of a cipher based on Hades is composed of three steps:

1. Add Round Key denoted by \textrm{ARK}(\cdot);
2. SubWords denoted by \textrm{S-Box}(\cdot);
3. MixLayer denoted by M(\cdot).

A final round key addition is then performed, and the final MixLayer operation can be omitted:

The crucial property of HADES is that the number of S-Boxes per round is not the same for every round:

• A certain number of rounds denoted by R_F has a full S-Box layer, i.e., t S-Box functions;
• A certain number of rounds denoted by R_P has a partial S-Box layer, i.e., 1 \le s < t S-Boxes and (t - s) identity functions.

In the following, we only consider the case s = 1, that is, R_P rounds have a single S-Box per round and t - 1 identity functions.

In more detail, assume R_F = 2 \cdot R_f is an even number. Then:

• the first R_f rounds have a full S-Box layer,
• the middle R_P rounds have a partial S-Box layer (i.e., 1 S-Box per round),
• the last R_f rounds have a full S-Box layer.

Note that the rounds with a partial S-Box layer are “masked” by the rounds with a full S-Box layer, which means that an attacker should not (directly) take advantage of the rounds with a partial S-Box layer.

[Figure 2: Construction of Hades – shows the three zones: first R_f full rounds, middle R_P partial rounds, and last R_f full rounds, with the final matrix multiplication optionally omitted.]

Crucial Points of the HADES Strategy

In the HADES design, R_f^{\text{stat}} rounds with full S-Box layers situated at the beginning and the end provide security arguments against statistical attacks, yielding a total of R_F^{\text{stat}} = 2 \cdot R_f^{\text{stat}} rounds with full S-Box layers. They are sufficient to apply the wide trail strategy, even without the middle rounds with partial S-Box layers. Moreover, the choice to have the same number of rounds at the beginning and the end aims to provide the same security with respect to chosen-plaintext and chosen-ciphertext attacks.

Security against all algebraic attacks is achieved working both with rounds R_F = R_F^{\text{stat}} + R_F' with full S-Box layers and rounds R_P \geq 0 with partial S-Box layers. Even if one S-Box per round is potentially sufficient to increase the degree, other factors can have a crucial impact on the cost of an algebraic attack (e.g., a Grobner basis attack also depends on the number of non-linear equations and variables).

Another crucial point regards the possibility to choose among several possible combinations of rounds (R_F, R_P) that provide the same security level. One can potentially decrease (resp. increase) the number of rounds with partial S-Box layers and add (resp. remove) rounds with full S-Box layers without affecting the security level. This freedom allows to choose the best combination that minimizes a given cost metric.

3. The Keyed Permutation HadesMiMC

HadesMiMC is a construction for cryptographic permutations based on the strategy just proposed. It is obtained by applying the HADES strategy to the cipher SHARK [RDP+96] proposed by Rijmen et al. in 1996 and based on the wide trail strategy. Our design works with texts of t \geq 2 words in (\mathbb{F}_p, +, \times), where p is a prime of size p \approx 2^n \geq 11 and where + and \times are the addition and multiplication in \mathbb{F}_p. In the following, N denotes N := \lceil \log_2 p \rceil \cdot t.

3.1 Specification of HadesMiMC

Each round R_k(\cdot): (\mathbb{F}_p)^t \to (\mathbb{F}_p)^t of HadesMiMC is defined as:

where k \in (\mathbb{F}_p)^t is the secret subkey, M \in (\mathbb{F}_p)^{t \times t} is an invertible matrix that defines the linear layer, \mathcal{S}(\cdot) is the S-Box layer, defined as \mathcal{S} = [S(\cdot), \ldots, S(\cdot)] for rounds with full S-Box layers and as \mathcal{S} = [S(\cdot), I(\cdot), \ldots, I(\cdot)] for rounds with partial S-Box layers.

The number of rounds R = 2 \cdot R_f + R_P depends on the choice of the S-Box and of the parameters p and t. The non-linear S-Box is defined as the power map:

where \alpha \geq 3 is the smallest integer such that \gcd(p - 1, \alpha) = 1 (e.g., \alpha = 3 if \gcd(p-1, 3) = 1, or \alpha = 5 if \gcd(p-1, 3) \neq 1 and \gcd(p-1, 5) = 1). As in SHARK, the MixLayer is defined by a multiplication with a fixed t \times t MDS matrix.

About the MDS Matrix

A t \times t MDS matrix M with elements in \text{GF}(p) exists if the condition 2t + 1 \le p is satisfied. For our concrete instantiations, we use Cauchy matrices, and we note that not every Cauchy matrix provides the same level of security.

We assume that the MDS matrix prevents the possibility to set up infinitely long subspace trails (either invariant or iterative and either with active S-Boxes or with inactive S-Boxes) for the rounds with partial S-Box layers. Hence, the MDS matrix must guarantee that the longest subspace trail with inactive S-Boxes can cover at most t - 1 rounds. For each i \geq 1, we define \mathcal{S}^i as:

where x[0] denotes the first word of x and M^j = M \cdot \cdots \cdot M for j \geq 1 and M^0 = I. It is not hard to check that \{\mathcal{S}^i, M \cdot \mathcal{S}^i, \ldots, M^{i-1} \cdot \mathcal{S}^i\} forms a subspace trail for i partial rounds with inactive S-Boxes.

Security Level and Key Schedule

We define two security levels, respectively \kappa = \log_2(p) \cdot t \approx N and \kappa = \log_2(p) \approx n.

Case \kappa \approx N: Let k \in (\mathbb{F}_p)^t be the secret key. The i-th round key for i \geq 1 is defined by a linear key schedule as:

where RC^{(i)} \neq 0 are random round constants and \hat{M} is an MDS matrix. We require that \hat{M}^i has no zero coefficient for 1 \le i \le R.

Case \kappa \approx n (for MPC Applications): Let k' \in \mathbb{F}_p be the secret key. We define the subkeys as:

3.2 Design Considerations: Reviving “Old” Design Ideas

Why SHARK Among Many Others? Since in our practical applications the cost of linear operations is much lower than the cost of non-linear ones, we decided to focus on the most efficient linear layer (from the security point of view), namely the one that provides the fastest diffusion at word level. This corresponds to a linear layer defined as a multiplication with an MDS matrix that involves the entire state, which is exactly the case for SHARK.

Choosing the S-Box. The choice to consider a power map S-Box among many other non-linear permutations is motivated by the following considerations: (1) since there are no quadratic permutation polynomials over \mathbb{F}_p, the cube S-Box requires the smallest number of non-linear operations (namely, two) and at the same time offers high security against statistical attacks; (2) an S-Box with a higher degree allows to reach the maximum degree faster, hence a smaller number of rounds is potentially sufficient to provide security, but the total number of non-linear operations does not change significantly.

4. Security Analysis

It is paramount for a new design to present a concrete security analysis. We provide an in-depth analysis of the security of the HadesMiMC family of block ciphers. Since we cannot ensure that a cipher is secure against all possible attacks, the best option of determining its security is to ensure that it is secure against all known attacks.

The crucial points of our security analysis are:

• Security against statistical attacks is obtained exploiting the wide trail strategy by using R_F^{\text{stat}} = 2 \cdot R_f^{\text{stat}} rounds with full S-Box layers.
• The combination of both rounds R_F with full S-Box layers and/or rounds R_P \geq 0 with partial S-Box layers provide security against all other possible attacks.

4.1 Main Points of Our Cryptanalysis Results

Number of Rounds. Given the number of rounds of a distinguisher which is independent of the key, we add at least 2 rounds with full S-Box layers to prevent key-guessing attacks. This is motivated by the fact that it is not possible to skip more than a single round with a full S-Box layer without guessing the entire key.

Statistical Attacks. Assuming p \geq (\alpha - 1)^2, at least 6 rounds with full S-Box layers are needed to protect HadesMiMC against all statistical attacks (differential, linear, truncated/impossible differential, boomerang, etc.). Depending on p and t, in some cases 10 rounds are necessary.

Algebraic Attacks. Algebraic attacks exploit mainly the low degree of the encryption/decryption function.

Interpolation Attack: The goal is to construct the polynomial that describes the function. The attack complexity is approximately \mathcal{O}(d^t), where d is the degree after r rounds. Since d = \alpha^r, \log_\alpha(p) + \log_\alpha(t) rounds with partial S-Box layers are necessary.

Grobner Basis Attack: One tries to solve a system of non-linear equations that describe the cipher. The cost depends on the degree of the equations, but also on the number of equations and variables. When working with rounds with full S-Box layers, the attack complexity is approximately \mathcal{O}((d/t)^t).

Higher-Order Differential Attack: This exploits the property that given a function of algebraic degree \delta, the sum over all elements of a subspace of dimension \geq \delta + 1 is zero. Since the only subspaces of \mathbb{F}_p are \{0\} and \mathbb{F}_p, this attack is less powerful in \mathbb{F}_p^t than over binary fields.

4.2 Statistical Attacks – Security Level: \kappa = N

Differential Cryptanalysis. The differential probability of the power function f(x) = x^\alpha is bounded above by (\alpha - 1)/|\mathbb{F}_p| = (\alpha - 1)/p. We compute the minimum number of rounds with full S-Box layers that guarantee each characteristic has probability at most p^{-2t} \approx 2^{-2N}. We consider a “weaker” cipher:

where L is an invertible linear layer and R(\cdot) is a round with a full S-Box layer. We show that this weaker cipher is secure against differential cryptanalysis for:

The minimum number of active S-Boxes of the weaker cipher R^{r'} \circ L \circ R^r(\cdot) is at least:

A detailed security analysis against other statistical attacks (linear, truncated and impossible differential, meet-in-the-middle, integral, boomerang, multiple-of-n, mixture differential, invariant subspace, and biclique cryptanalysis) is provided in Appendix D. All these attacks do not outperform the differential attack.

4.3 Algebraic Attacks – Security Level: \kappa = N

Interpolation Attack. Considering HadesMiMC, the degree of each word after r rounds is roughly approximated by \alpha^r. A rough estimation for the number of monomials of the interpolation polynomial (and so of the attack complexity) is given by (\alpha^{r-1} + 1)^t \geq \alpha^{(r-1) \cdot t}. The total number of rounds R must satisfy:

Grobner Basis Attack. We provide three different strategies:

First Strategy: Using t variables and t equations per pair, the required number of rounds satisfies:

Second Strategy: Adding intermediate variables in each round. For rounds with a partial S-Box layer, only one intermediate variable is needed. The condition becomes:

Third Strategy: A combination of the previous two. Using 2t variables for full rounds and adding intermediate variables for partial rounds gives the condition:

Conclusion. HadesMiMC can be considered secure against Grobner basis attacks if R_F and R_P satisfy all three conditions simultaneously.

Higher-Order Differential Attack. Since the only subspaces of \mathbb{F}_p are \{0\} and \mathbb{F}_p, the biggest subspace of (\mathbb{F}_p)^t has dimension t, in contrast to the biggest subspace of (\mathbb{F}_{2^n})^t which has dimension n \cdot t = N. The number of rounds necessary to guarantee security against the interpolation attack provides security against this attack as well.

5. Security Analysis for MPC: \kappa = n and Data \leq p^{1/2}

In this section, we adjust our security arguments to provide a security level of only \log_2(p) \approx n bits (instead of N bits). At the same time, we only allow an attacker to use p^{1/2} data.

5.1 Statistical Attacks

Differential Attack. We assume the cipher is secure if every characteristic has probability smaller than p^{-2}. Working with the weaker cipher, it follows that R_f = 2 rounds with full S-Box layers are sufficient. However, since R_F = 2 full rounds would not lead to 2 consecutive full rounds in our design, we add additional rounds. Finally, we add two more rounds to prevent differential attacks with key guessing and conclude that R_F \geq R_F^{\text{stat}} = 6 rounds are needed.

5.2 Algebraic Attacks

Interpolation Attack. By choosing plaintexts with just one active word, the interpolation polynomial depends on a single variable. Since the data complexity is limited to \sqrt{p}, we require:

GCD and Grobner Basis Attack. The cost of the GCD computation is approximated by \mathcal{O}(d \log_2^2 d), where d \approx \alpha^{r-1}. The total number of rounds must satisfy:

6. Number of Rounds: Security and Efficiency

The design goal of HadesMiMC is to offer a cipher optimized for schemes whose performance critically depends on the MULTdepth/ANDdepth, the number of MULTs/ANDs, or the number of MULTs/ANDs per bit.

Security. HadesMiMC with security level \kappa = N is secure iff:

Several Combinations of (R_F, R_P) for the Same Security Level. One of the strengths of our design is the freedom to choose the ratio between R_F and R_P without affecting the security level. For each given p and t, the designer has the freedom to choose among several combinations that guarantee the same security in order to minimize the cost metric.

6.1 Efficiency in the Case of MPC Applications

Consider a generic scenario where the main goal is to minimize the total number of non-linear operations and/or the depth. The metric is given by:

for different values of a parameter \gamma, where 0 \leq \gamma \leq 1. Note that \gamma = 1 and \gamma = 0 correspond to minimizing the total number of S-Boxes and the depth, respectively.

6.2 Best Ratio Between R_F and R_P – MPC Application

Security. HadesMiMC with \kappa = n is secure if:

Efficiency – Best Combination (R_F, R_P). For each \gamma, the cost metric is always minimized by choosing the smallest possible R_F (namely, R_F = R_F^{\text{stat}}).

6.3 Concrete Round Numbers of HadesMiMC

Based on the security analysis, we present some example round numbers of HadesMiMC for different security levels and/or applications, using \alpha = 3 (the cube S-Box):

Table 1: A range of different parameter sets for HadesMiMC (based on the cube S-Box, \alpha = 3) offering different trade-offs. The security level \kappa = \log_2(p) case provides security only if the data used for the attack is smaller than p^{1/2}.

Reduced and Toy Versions. In order to facilitate third-party cryptanalysis and estimate the security margin, reduced-round variants need to be considered. We encourage studying reduced-round variants where the symmetry around the middle is kept.

7. MPC Applications

For MPC applications, we evaluated the HadesMiMC cipher (based on the cube S-Box) using the SPDZ framework [KSS13] within a prime field \mathbb{F}_p.

Preliminaries. In the following, we denote by [x] a sharing of x. The process of parties reconstructing x is called an opening. A protocol is split into two steps: an input-independent preprocessing phase where parties generate random Beaver triples [a] = [b] \cdot [c], and an input-dependent online phase where parties share their inputs and use the triples.

To evaluate a block cipher in this setting, both the key [k] and the message [m] are secretly shared. To compute the S-Box, the trivial way is to perform [x^2] \leftarrow [x] \cdot [x] and then [x^3] \leftarrow [x^2] \cdot [x] using two triples.

Experiment Results. Our design is better in all metrics for t = 2 compared to all other block ciphers. In terms of runtime throughput, HadesMiMC outperforms all existing work from t = 2 and the gap increases by a factor of four for t = 64 when comparing with \text{GMiMC}_{\text{erf}}.

Table 2 (excerpt): Two-party costs for Rescue, \text{MiMC}^t, \text{GMiMC}_{\text{erf}} and HadesMiMC over a 10Gb/s LAN. Runtime column represents the entire protocol execution, including preprocessing.

8. Concluding Remarks: Possible Variants for Future Works

In this paper, we proposed the HADES design strategy, based on the idea of mixing rounds with full S-Box layers and partial S-Box layers in an SPN scheme with the goal to achieve security and at the same time good performance in all applications where the cost is proportional to the number of non-linear operations. As a concrete cipher, we proposed HadesMiMC, obtained by applying the HADES strategy to (a modified version of) the block cipher SHARK defined over \mathbb{F}_p^t for a prime p.

As future work, it could be interesting to define ciphers based on the HADES strategy over \mathbb{F}_{2^n}^t or over \mathbb{F}_{p^n}^t. We also point out that it is possible to define cryptographic key-less permutations using the strategy proposed here (it is sufficient to take HadesMiMC and fix the key to some public value).

Acknowledgements. The authors thank the anonymous reviewers for their valuable comments and suggestions. L. Grassi has been supported by IOV42. D. Rotaru has been supported in part by DARPA and SSC Pacific under contract No. N66001-15-C-4070, by ODNI/IARPA via Contract No. 2019-1902070006 and by the CyberSecurity Research Flanders with reference number VR20192203.

Appendix A: Concrete Instantiations

Here we specify how we generate pseudo-random bits, the round constants, and the MDS matrices for the linear layer. All values are given in hexadecimal notation. The MDS matrices are Cauchy matrices.

Pseudo-Random Number Generator. All pseudo-random numbers are generated using the Grain LFSR [HJM07] in a self-shrinking mode:

1. Initialize the state with 80 bits b_0, b_1, \ldots, b_{79}: b_0, b_1 are fixed to 0\text{x}1; b_i for 6 \leq i \leq 17 are the binary representation of n; b_i for 18 \leq i \leq 29 are the binary representation of t; b_i for 30 \leq i \leq 39 represent R_F; b_i for 40 \leq i \leq 49 represent R_P; b_i for 50 \leq i \leq 79 are set to 1.
2. Update bits using b_{i+80} = b_{i+62} \oplus b_{i+51} \oplus b_{i+38} \oplus b_{i+23} \oplus b_{i+13} \oplus b_i.
3. Discard the first 160 bits.
4. Evaluate bits in pairs: If the first bit is 1, output the second bit. If it is 0, discard the second bit.

Round Constants. Simply use the pseudo-random number generator. All numbers are generated starting from the most significant bit.

MDS Matrices. All MDS matrices are Cauchy matrices, generated using the algorithms in [GRS20]. The method is: (1) randomly select pairwise distinct \{x_i\}_{i=1}^t and \{y_i\}_{i=1}^t where x_i + y_j \neq 0; (2) determine if the matrix is secure using the tools in [GRS20]; (3) repeat until a secure matrix is found.

Appendix B: MDS Matrix Construction

Here we recall several ways to construct an MDS matrix.

Cauchy Matrix [YMT97]. Let x_i, y_i \in \mathbb{F}_p for i = 1, \ldots, t such that x_i \neq x_j, y_i \neq y_j for i \neq j and x_i + y_j \neq 0. Let A be the Cauchy matrix defined by:

It follows that A is MDS.

Sequential Matrix [60,61]. Let \beta be a generator for \mathbb{F}_p. Define the companion matrix S from the generator polynomial and let A = S^t. It is possible to prove that A is an MDS matrix.

Vandermonde Matrix [LF04]. Let A and B be two Vandermonde matrices with a_i \neq b_j. Then M = A \times B^{-1} is an MDS matrix.

Appendix C: Efficient Implementation

Like for LowMC, the fact that the non-linear layer is partial in R_P rounds can be used to reduce the amount of operations required in each of these rounds.

Round Constants. In the description of an SPN, it is possible to swap the order of the linear layer and the round key addition as both operations are linear. Working in this way for all round keys, we end up with an equivalent representation in which round keys are only added to the output of the S-Boxes apart from one whitening key. The optimized representation only requires t \cdot \log_2 p \cdot (R_F + 1) + \log_2 p \cdot R_P, potentially greatly reducing the amount of needed memory.

Linear Layer. Focusing on rounds with a single S-Box, let M be the t \times t MDS matrix. We can decompose it as:

where \hat{M} is a (t-1) \times (t-1) MDS matrix, \hat{w} = \hat{M}^{-1} \times w, and I is the identity matrix. Each linear part in the R_P rounds is then defined by a multiplication with the sparse matrix M''.

Appendix D: Statistical Attacks on HadesMiMC – Details

D.1 Linear Cryptanalysis

Similar to differential attacks, linear attacks [Mat93] pose no threat to the HadesMiMC family instantiated with the same number of rounds previously defined for classical differential cryptanalysis. The maximum square correlation of the cubic function is limited to 2/p, offering one of the best possible resistances against linear cryptanalysis.

D.2 Truncated Differentials

Working on the “weaker” cipher and focusing on active/passive bytes, there exist several differentials with probability 1 for at most 1 round. Due to the next S-Box layer, no probability-one truncated differential covers more than a single round. We conjecture that 4 rounds with full S-Box layers are secure against truncated differential attacks, and 6 rounds with full S-Box layers including key-guessing protection.

D.3 Differential Meet-in-the-Middle Attack

Due to the classical and truncated differential analysis (together with the fact that 1-round HadesMiMC provides full diffusion), we argue that the number of rounds sufficient for differential security is also sufficient against MitM attacks.

D.4 Impossible Differential

The longest impossible differential (independent of S-Box details) only spans 2 rounds. As a result, 6 rounds with full S-Box layers make HadesMiMC secure against this attack.

D.5 Boomerang Attack

Exploiting the analysis proposed before, 6 rounds with full S-Boxes are sufficient to ensure that no good boomerang exists.

D.6 Multiple-of-n and Mixture Differential Cryptanalysis

Regarding HadesMiMC, it is possible to set up such distinguishers on 2 rounds only. As a result, 6 rounds with full S-Box layers make HadesMiMC secure against these attacks.

D.7 Invariant Subspace Attack

For rounds with full S-Box layers, random round constants provide good protection. For rounds with partial S-Box layers, it is always possible to construct a subspace trail for at most t - 1 rounds. Due to the assumption on the MDS matrix, it is not possible to cover more than t - 1 rounds.

D.8 Integral/Square Attack

It is possible to set up an integral distinguisher over two rounds of HadesMiMC. As a result, 6 rounds with full S-Box layers make HadesMiMC secure against this attack.

D.9 Biclique Cryptanalysis

Since we do not think that improving the exhaustive search by a small factor will turn into a serious vulnerability, HadesMiMC is not designed to resist biclique cryptanalysis with small improvement.

Appendix E: Algebraic Attacks – Details

E.1 Interpolation Attack and Dense Polynomial

Proof. After one round the encryption polynomial is of the form \sum_{i=0}^2 a_{0,i} X_0^{3-i} + \ldots + \sum_{i=0}^2 a_{t-1,i} X_{t-1}^{3-i} + a. In order to reach the maximum degree p - 1 in one variable, the number of rounds r has to satisfy 3^r \geq p - 1. It takes at least \lceil \log_3(t) \rceil more rounds until all t variables are exhausted.

E.2 GCD Attack

In the GCD attack [AGR+16], given more than one known (plaintext, ciphertext) pair, one constructs their polynomial representations and computes their polynomial GCD to recover a multiple of the key. The complexity for finding the GCD of two polynomials of degree d is \mathcal{O}(d \log_2^2 d). The total number of rounds must satisfy:

E.3 Grobner Basis Attack – Details

Three strategies are presented in detail, including the first strategy exploiting the “invariant” subspace \mathcal{S}, the second strategy with intermediate variables, and the third strategy combining the previous two. The analysis also considers the full-data case and a special case with R_P = 0.

E.4 Grobner Basis Attack: \kappa = n and Data \leq p^{1/2}

The details of the Grobner Basis Attack in the MPC application scenario show that it does not outperform the GCD attack. The first strategy requires:

The second strategy gives a condition of the form:

Appendix F: Comparison: HadesMiMC with S-Box(x) = x^{-1}

HadesMiMC can be instantiated by an S-Box with a higher degree than 3. Here we analyze the number of rounds necessary to provide security against algebraic attacks with \textrm{S-Box}(x) = x^{-1}.

Main Result. For the cube case, one needs approximately:

while for the inverse case:

The number of rounds for the cube and inverse cases are close when t is not much bigger than \log_2(p). Moreover, the total number of non-linear operations is in general much bigger for the inverse than for the cube case. In conclusion, it seems there is no advantage to use an S-Box different than the cube one when aiming to minimize the total number of non-linear operations.

Interpolation Attack – Details. The inverse S-Box f(x) = x^{-1} has different behavior depending on whether a full or partial S-Box layer is used: for a full S-Box layer it behaves as a function of algebraic degree t (the number of words) from the interpolation perspective, while for a partial S-Box layer it behaves as degree 2. This means the choice between partial or full S-Box layers also depends on the details of the S-Box.

Appendix G: \text{GMiMC}_{\text{erf}} for MPC Applications

We adapt the security analysis of \text{GMiMC}_{\text{erf}} [AGP+19] for the case where \kappa = n and the attacker can use at most \leq 2^{n/2} chosen texts. The minimum number of rounds necessary is given by:

Key Schedule. Bonnetain [Bon19] presented an attack on Feistel-MiMC and univariate GMiMC that relies only on their weak key schedules and is independent of the round function and the number of rounds. A change of the key schedule should be sufficient to restore security.

Statistical Attacks. 5t + 3 rounds are sufficient to provide security against statistical attacks.

Algebraic Attacks. The GCD attack requires 2 \cdot \lceil \log_3(p) \rceil - 4 \cdot \lfloor \log_3(\log_2 p) \rfloor + 2t - 2 rounds. The interpolation attack requires \lceil \log_3(p) \rceil + 2t + 4 rounds.

References

• [AAB+19] Aly, Ashur, Ben-Sasson, Dhooghe, Szepieniec. Design of Symmetric-Key Primitives for Advanced Cryptographic Protocols. eprint 2019/426.
• [ACG+19] Albrecht, Cid, Grassi, Khovratovich, Luftenegger, Rechberger, Schofnegger. Algebraic Cryptanalysis of STARK-Friendly Designs: Application to MARVELlous and MiMC. ASIACRYPT 2019, LNCS 11923.
• [AD18] Ashur, Dhooghe. MARVELlous: a STARK-Friendly Family of Cryptographic Primitives. eprint 2018/1098.
• [AGP+19] Albrecht, Grassi, Perrin, Ramacher, Rechberger, Rotaru, Roy, Schofnegger. Feistel Structures for MPC, and More. ESORICS 2019, LNCS 11736. [page on this site]
• [AGR+16] Albrecht, Grassi, Rechberger, Roy, Tiessen. MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity. ASIACRYPT 2016, LNCS 10031.
• [AMMR18] Agrawal, Mohassel, Mukherjee, Rindal. DiSE: Distributed Symmetric-key Encryption. CCS 2018, pp. 1993-2010.
• [ARS+15] Albrecht, Rechberger, Schneider, Tiessen, Zohner. Ciphers for MPC and FHE. EUROCRYPT 2015, LNCS 9056.
• [BBS99] Biham, Biryukov, Shamir. Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials. EUROCRYPT 1999, LNCS 1592.
• [BCD+20] Beyne, Canteaut, Dinur, Eichlseder, Leander, Leurent, Naya-Plasencia, Perrin, Sasaki, Todo, Wiemer. Out of Oddity — New Cryptanalytic Techniques against Symmetric Primitives Optimized for Integrity Proof Systems. eprint 2020/188, CRYPTO 2020. [page on this site]
• [BCG+12] Borghoff, Canteaut, Guneysu et al. PRINCE – A Low-Latency Block Cipher for Pervasive Computing Applications. ASIACRYPT 2012, LNCS 7658.
• [BCLR17] Beierle, Canteaut, Leander, Rotella. Proving Resistance Against Invariant Attacks: How to Choose the Round Constants. CRYPTO 2017, LNCS 10402.
• [BDD+15] Bar-On, Dinur, Dunkelman, Lallemand, Keller, Tsaban. Cryptanalysis of SP Networks with Partial Non-Linear Layers. EUROCRYPT 2015, LNCS 9056.
• [BFP09] Bettale, Faugere, Perret. Hybrid approach for solving multivariate systems over finite fields. Journal of Mathematical Cryptology 3(3), 2009.
• [BKR11] Bogdanov, Khovratovich, Rechberger. Biclique Cryptanalysis of the Full AES. ASIACRYPT 2011, LNCS 7073.
• [Bon19] Bonnetain. Collisions on Feistel-MiMC and univariate GMiMC. eprint 2019/951. [page on this site]
• [BS91] Biham, Shamir. Differential Cryptanalysis of DES-like Cryptosystems. Journal of Cryptology 4(1), 1991.
• [Buc06] Buchberger. An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Journal of Symbolic Computation 41, 2006.
• [CDK+18] Cogliati, Dodis, Katz, Lee, Steinberger, Thiruvengadam, Zhang. Provable Security of (Tweakable) Block Ciphers Based on Substitution-Permutation Networks. CRYPTO 2018, LNCS 10991.
• [CLO97] Cox, Little, O'Shea. Ideals, varieties, and algorithms. Springer, 1997.
• [DEG+18] Dobraunig, Eichlseder, Grassi, Lallemand, Leander, List, Mendel, Rechberger. Rasta: A Cipher with Low ANDdepth and Few ANDs per Bit. CRYPTO 2018, LNCS 10991.
• [DEM15] Dobraunig, Eichlseder, Mendel. Higher-Order Cryptanalysis of LowMC. ICISC 2015, LNCS 9558.
• [DKR97] Daemen, Knudsen, Rijmen. The Block Cipher Square. FSE 1997, LNCS 1267.
• [DLMW15] Dinur, Liu, Meier, Wang. Optimized Interpolation Attacks on LowMC. ASIACRYPT 2015, LNCS 9453.
• [DR01] Daemen, Rijmen. The Wide Trail Design Strategy. IMA 2001, LNCS 2260.
• [DR02] Daemen, Rijmen. The Design of Rijndael: AES – The Advanced Encryption Standard. Springer, 2002.
• [EGL+20] Eichlseder, Grassi, Luftenegger, Oygarden, Rechberger, Schofnegger, Wang. An Algebraic Attack on Ciphers with Low-Degree Round Functions: Application to Full MiMC. IACR ePrint 2020/182.
• [GGNS13] Gerard, Grosso, Naya-Plasencia, Standaert. Block Ciphers That Are Easier to Mask: How Far Can We Go? CHES 2013, LNCS 8086.
• [GKR+19] Grassi, Khovratovich, Roy, Rechberger, Schofnegger. Poseidon: A New Hash Function for Zero-Knowledge Proof Systems. eprint 2019/458. [page on this site]
• [Gra18] Grassi. Mixture Differential Cryptanalysis: a New Approach to Distinguishers and Attacks on round-reduced AES. IACR Trans. Symmetric Cryptol. 2018(2). [page on this site]
• [GRR16] Grassi, Rechberger, Ronjom. Subspace Trail Cryptanalysis and its Applications to AES. IACR Trans. Symmetric Cryptol. 2016(2).
• [GRS20] Grassi, Rechberger, Schofnegger. Weak linear layers in word-oriented partial SPN and hades-like ciphers. eprint 2020/500. [page on this site]
• [HJM07] Hell, Johansson, Meier. Grain: a stream cipher for constrained environments. IJWMC 2(1), 2007.
• [JK97] Jakobsen, Knudsen. The Interpolation Attack on Block Ciphers. FSE 1997, LNCS 1267.
• [Knu94] Knudsen. Truncated and Higher Order Differentials. FSE 1994, LNCS 1008.
• [KR20] Keller, Rosemarin. Mind the Middle Layer: The HADES Design Strategy Revisited. eprint 2020/179. [page on this site]
• [KSS13] Keller, Scholl, Smart. An architecture for practical actively secure MPC with dishonest majority. CCS 2013.
• [LAAZ11] Leander, Abdelraheem, AlKhzaimi, Zenner. A Cryptanalysis of PRINTcipher: The Invariant Subspace Attack. CRYPTO 2011, LNCS 6841.
• [LF04] Lacan, Fimes. Systematic MDS Erasure Codes Based on Vandermonde Matrices. IEEE Communications Letters 8(9), 2004, pp. 570–572.
• [Mat93] Matsui. Linear Cryptanalysis Method for DES Cipher. EUROCRYPT 1993, LNCS 765.
• [MV15] Miles, Viola. Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs. JACM 62(6), 2015.
• [RDP+96] Rijmen, Daemen, Preneel, Bosselaers, Win. The Cipher SHARK. FSE 1996, LNCS 1039.
• [RST18] Rechberger, Soleimany, Tiessen. Cryptanalysis of Low-Data Instances of Full LowMCv2. IACR Trans. Symmetric Cryptol. 2018(3).
• [Wag99] Wagner. The Boomerang Attack. FSE 1999, LNCS 1636.
• [WWGY14] Wang, Wu, Guo, Yu. Differential Cryptanalysis and Linear Distinguisher of Full-Round Zorro. ACNS 2014, LNCS 8479.
• [YMT97] Youssef, Mister, Tavares. On the Design of Linear Transformations for Substitution Permutation Encryption Networks. School of Computer Science, Carleton University, 1997, pp. 40–48.