On the Security of the Rescue Hash Function

Abstract

In this report, we cryptanalyse the Rescue hash function. In particular, we look at linear and differential cryptanalysis of Rescue, how multiplicative subgroups are propagated by the round function and at rebound attacks. Overall, we do not find any direct threat to the security of Rescue.

Keywords: Rescue, Algebraic optimised, Linear Cryptanalysis, Differential Cryptanalysis, Multiplicative Subgroups, Rebound Attacks

1. Summary of the Results

This report is the result of a joint effort to analyze the security of Rescue. We considered several attack vectors and did not find attacks that pose a direct risk to the current design. Time was limited and we cannot exclude that other attack vectors or variants of the ones we considered lead to a full break of Rescue. In more detail, we considered the following attacks.

Linear Cryptanalysis. We adapt the notion of linear cryptanalysis to the case of odd characteristic using the notion of additive characters on \mathbb{F}_p. Building upon this we can show that single linear trails do not pose a threat to Rescue. Furthermore, we investigate the effect of trail clustering. As for almost any cipher, we are not able to settle this completely. However, our investigations do not point at any weakness for Rescue.

Differential Cryptanalysis. Generalization of differential cryptanalysis to the case of odd characteristic is, compared to linear characteristic, trivially done. Consequently, it is not surprising that important properties can be transferred as well. In particular, the maximal expected differential probability (MEDP) can be bounded. We thus confirm that averaging over independent round keys, differential cryptanalysis does not seem to pose a threat to Rescue. However, in the case of a fixed key, we experimentally observe the existence of a few keys that exhibit a significantly larger probability of differentials than expected from a random permutation. We can explain this behaviour only partially. One reason is that using the S-box layer and its inverse in turns leads to a large uniformity for two rounds. Thus, we can explain why some keys lead to a higher than expected differential uniformity, but there remain keys with a similar property that we do not fully understand. Again, it seems highly unlikely that this poses a threat for Rescue with the chosen parameters.

Multiplicative Subgroups. Motivated by the lack of additive structure and the S-boxes being homomorphisms in \mathbb{F}_p^*, we next focus on attacks exploiting multiplicative structures. In particular, we investigate how certain multiplicative subgroups (and their cosets) are mapped by parts of the round functions. While the S-box and the linear layer exhibit strong non-random properties, we argue that those are destroyed with high probability by the key (or constant) addition.

The main result in this part of the analysis is that the round constants for Rescue could be chosen in a way that allows to easily break the cipher with the given key scheduling for any number of rounds. The main reason here is that Rescue reuses the round function in the key-scheduling. Again, for non-maliciously chosen parameters, this is not going to happen with an overwhelming probability.

Rebound Attacks. One of the most successful attacks against hash functions are rebound attacks. Those attacks use the freedom of the attacker in a non-keyed setting to efficiently generate pairs following a (truncated) differential characteristic and thus often cover a larger number of rounds compared to usual differential attacks. In the case of Rescue our investigations indicate that there is a rather large security margin against those attacks.

1.1 Steps vs Rounds

In this report, we stick to the common way of counting rounds as the number of S-box layer applications (including following linear layer and key addition). Thus, what is called a step in [Aly+19] is here called a round.

2. The Rescue Hash Function

We quickly recall the design specification of Rescue from [Aly+19] to settle a common ground for notations. Let p be an odd prime, we denote the finite field with p elements by \mathbb{F}_p. Further, let g be a generator of the multiplicative group \mathbb{F}_p^* and for any \alpha \in \mathbb{F}_p^*, \langle \alpha \rangle is the multiplicative subgroup of \mathbb{F}_p^* generated by \alpha.

Rescue operates on a state which is represented as an element of \mathbb{F}_p^m. In other words, the state is represented by m words in \mathbb{F}_p. The state is transformed by an S-box layer followed by a linear layer and a key addition. In what follows, we stick to the common way of counting rounds as the number of S-box layer applications (including following linear layer and key addition).

The S-box layer is not identical for all rounds, but rather two S-box layers are alternated, where the second is the inverse of the first. The S-box is a power permutation, i.e. for the smallest prime d that is coprime to p - 1:

and S^{-1} accordingly. The linear layer multiplies the state by a (randomly generated Cauchy) MDS matrix M \in \mathbb{F}_p^{m \times m}. The key schedule for deriving the round keys reuses this round function; each round key k_i is the state after the ith application of the round function. During the key schedule, the “round key” addition is substituted by a round constant addition, where the round constants \mathrm{rc}_i are pseudo randomly chosen.

Overall, Rescue iterates r = \min\{20, 4\lceil \log_2(p)/4 \rceil\} rounds. Suggested parameters for Rescue are:

3. Linear Cryptanalysis

A natural generalization of linear cryptanalysis to \mathbb{F}_p^m is to consider the probability distribution of linear combinations u^\top x of the state x. As discussed in [Bey19], this distribution can be associated with a p-dimensional subspace of the vector space of functions \mathbb{F}_p^m \to \mathbb{C}. A basis for this subspace is given by the functions x \mapsto \chi(u^\top x) where \chi is an additive character of \mathbb{F}_p.

In the following, let \chi denote an additive character of \mathbb{F}_p. Further, let d be an integer coprime to p - 1. This section is structured into two parts: Section 3.1 shows that (for p large enough) two rounds of Rescue have no linear trails with correlation significantly higher than p^{-m/2}. Section 3.2 provides upper bounds on the correlation of linear approximations over four rounds of Rescue.

3.1 Upper Bounds for Linear Trails

We first show that every linear trail over two rounds has correlation less than p^{-m/2} if p is sufficiently large. As in the characteristic two case, the MDS-property of the linear layer ensures that absolute correlations of two-round approximations are bounded by |c|^{m+1}, where c is the correlation of the best non-trivial linear approximation of x \mapsto x^d.

The correlation of a linear approximation over a single S-box is given by

Consequently, it suffices to compute the exponential sums

We use the following classical result due to Weil [Wei48].

For d = 3, Proposition 1 yields the bound |c| \leqslant (d-1)/\sqrt{p}. Consequently, the correlation of an r-round trail is bounded by

where the inequality holds for r \geqslant \frac{1}{4} \log_{d-1} p / (\log_{d-1} p - 2).

3.2 Upper Bounds for Four Rounds

The result from the previous section shows that there are no usable linear trails. However, since iterating the Rescue round function gives a function of the form S \circ A \circ S^{-1} \circ A' with A and A' affine maps, it is natural to wonder if clustering of linear trails can result in strong linear approximations over iterations of the round function. To this end, we will give upper bounds on the correlation of arbitrary approximations over F = S \circ A \circ S^{-1}.

We start from the straightforward observation that the correlation of a two-round approximation with masks (u, v) is given by

Let A(x) = Mx + c with M \in \mathbb{F}_p^{m \times m}. Computing the correlation then amounts to computing the exponential sum

where t = 2m, \alpha = (0, c) and w = (u, -v).

Follow-up work by Rojas León [RL04] provides a generalization and shows that C may be taken as C = 3(d + 1)^n. To apply Katz’s result, the remaining work is to determine the dimension \delta.

The section continues with detailed Gröbner basis computations for m = 2 (with p = 41) and m = 3 (with p = 1511), showing that \dim \mathbb{V} = 0 for all but a small fraction of masks. For m = 2, the exceptional fraction is at most 4/p; for m = 3, it is at most 12/p + 25/p^3. Experimentally, no approximations violating the stronger bounds were found.

4. Differential Cryptanalysis

In this section we describe our attempts to attack Rescue using differential cryptanalysis. We start by two-round differentials, averaged over all round keys, before investigating special choices of keys that, even for more rounds, lead to a differential uniformity that is larger than expected. We add experimental observations to our theoretical analysis.

Notations. For differential cryptanalysis, we are interested in the number of solutions for the equation

where F is the (key-dependent) function under scrutiny. The Difference Distribution Table (DDT) captures these numbers:

The overall resistance of F against differential cryptanalysis is measured by its differential uniformity:

4.1 Two-Round Differentials

The aim of this section is to understand how the study of two-round differentials [8, 5] on the AES can be transferred to Rescue.

In the specific case of Rescue, the S-box has differential uniformity 2, which leads to

However, the MEDP is the highest probability of a differential, among all differentials averaged over the round key (or round constant). This may be very different from the maximal differential probability with a fixed key.

Proof sketch. The proof considers differentials where the input difference has weight 1 and analyzes the system of equations arising from the two S-box layers. When M^{-1}K has a zero component, a degenerate case occurs where the differential is satisfied by exactly p inputs. Otherwise, the system reduces to a degree-4 equation in \lambda with at most 4 solutions, each leading to at most 2^m values, giving a total of at most 2^{m+2}.

4.2 Four-Round Differentials and Weak Round-Keys

In the following, we consider several rounds with independent round-keys (i.e., we do not use the key-schedule defined for the Rescue block cipher). Simulation results for m = 2 show that there is a small proportion of round keys for which the differential uniformity of four rounds exceeds p.

4.3 More Experimental Results

In order to experimentally assess the security of Rescue, we compute the differential uniformity of multiple instances of the block cipher. Our aims are: (1) analyse whether the behaviours identified above can occur with a strong round constant derivation procedure, and (2) analyse the number of rounds needed to reach the differential uniformity of a random permutation operating on the same set.

Experimental results confirm the conjecture: the DDT coefficients of random permutations over \mathbb{F}_p behave like Poisson-distributed variables with parameter 1. The differential uniformity of Rescue instances converges to the predicted bound within 4–5 rounds in the overwhelming majority of cases.

Remark 1. The analysis highlights the importance of having a strong round constant derivation method. The round constant generation method for the hash function could allow related-cipher attacks if Rescue is superseded by Rescue2 in the future, since these hash functions would share some round constants at different positions.

5. Multiplicative Subgroups Analysis

The idea of this analysis, or attack vector, is to trace how cosets of multiplicative subgroups get mapped to other cosets through the encryption process. This can be seen as a multiplicative variant of linear cryptanalysis in the case of a subgroup of codimension 2. We first describe the idea and fix the notation. Next, we investigate how those multiplicative structures are affected by the separate parts of the round function, i.e. the linear layer, the S-box, and the key-addition. Finally, we focus on the most interesting case of what we call a diagonal subgroup, a structure closely related to one-dimensional subspaces.

We show that it is in principle possible to maliciously choose round constants that would lead to a significant non-random behaviour for any key even using the heavy key-scheduling of Rescue.

5.1 The Setup

Let U \subseteq \mathbb{F}_p^* be a multiplicative subgroup of \mathbb{F}_p^* of order q \mid p - 1. The cosets of U are U, gU, g^2 U, \ldots, g^{s-1} U, where s = (p-1)/q and g is a generator of \mathbb{F}_p^*. We extend such a subgroup to

by the componentwise multiplication. We define, for a function F : \mathbb{F}_p^m \to \mathbb{F}_p^m, the counters

which correspond, up to scaling, to the probability of an element in \alpha U^{\otimes m} being mapped to the coset \beta U^{\otimes m} by F.

5.2 The Effect of the Round Operations

S-box Layer. The S-box S : \mathbb{F}_p \to \mathbb{F}_p is a permutation of the form x \mapsto x^d. Since S(\alpha_i U) = \alpha_i^d U^d = \alpha_i^d U, the S-box layer only permutes the cosets. In other words, the probability that an input from a specific coset is mapped by the S-box to another specific coset is either one or zero.

Constant Addition. Given a constant k \in \mathbb{F}_p^m, the transition counter c_k(\alpha, \beta) relates to the cyclotomic numbers of order s. For s = 2 (squares vs non-squares), the cyclotomic numbers are known exactly and depend on whether -1 is a square. For s > 2, the bound is

which implies a rather uniform distribution for large subgroups.

5.3 Diagonal Subgroups

For a subgroup U \subseteq \mathbb{F}_p^* we define

These diagonal subgroups and their cosets behave nicely for both the linear layer and the S-boxes: the transition matrices are permutation matrices. However, the key-addition destroys this behaviour with very high probability in general.

For the easiest case of U = \mathbb{F}_p^* entirely, fixing an arbitrary vector \alpha \in (\mathbb{F}_p^*)^m and constants k = \alpha, the coset \alpha \mathcal{D}(\mathbb{F}_p^*) is mapped to itself by adding the key, since for a \in \mathbb{F}_p^* we have a\alpha + k = a\alpha + \alpha = (a+1)\alpha. Choosing round constants of the form

leads to this diagonal subgroup being mapped to a fixed coset. Interestingly, this is very close, up to the round constants, to the actual key schedule. This can be reformulated as the existence of round constants such that there exists a key-independent function f : \mathbb{F}_p^* \to \mathbb{F}_p^* with

for all a \in \mathbb{F}_p, all keys k \in (\mathbb{F}_p^*)^m, a rather intriguing and unusual property. Luckily, it can be argued that almost any other choice of constants seems to be destroying this property very quickly and results in a very uniform distribution with just one key addition.

6. Rebound Attacks for Finding Collisions

Rebound attacks are a common tool used for studying the security of hash functions. This technique introduced in [Men+09], with many follow-up works published in the last few years, can allow to efficiently find solutions for a certain differential path by merging partial middle solutions, that are enforced by first choosing differences and next filling in the values that make the difference transitions possible.

In this section, we first propose a semi-free start collision on 3 rounds of the permutation, that will serve as an example of the techniques on Rescue. Next, we discuss how this could be extended to reach 1 more round generating an output near-collision.

6.1 Example Collision Attack on 3 Rounds

We describe here how to build a semi-free start collision (a collision where the value of the capacity is chosen, and the difference is introduced in the message part) with a cost of 2^{n/2} versus 2^{2n}, which would be the generic cost. For illustrating our example we consider the parameters m = 12, n = 125 and a capacity c = 4.

The number of active words in the state at round i is denoted by N_i. The number of expected solutions for the 3-round path is

With N_0 = N_6 = m - c = 8 and N_2 + N_4 = m + 1 = 13, the procedure builds two lists L_1 and L_2 of valid differences, then merges them. The cost is 2^x + 2^y. Choosing 2^x = 2^y = 2^{n/2} yields an optimal overall cost of 2^{n/2}.

6.2 Extension to 4 Rounds

Adding one more round to the previous path, the number of solutions becomes

With the minimum number of active S-boxes, this yields 2^{-2n} solutions, less than 1. The authors explore exploiting a property of the S-box S where, for two values X, Y with small differences and restricted most significant bits, S(X) - S(Y) preserves a truncated pattern. Combined with a weaker (AES-like) MDS matrix, this could extend the attack to 4 rounds for a near-collision. However, the matrix property needed is not satisfied by the matrices proposed for Rescue.

6.3 Conclusion

The best collision attacks we could find on Rescue reach 3 rounds with a complexity of 2^{n/2}. We proposed a potential extension of the attack by one round for a modified MDS matrix and an inverted order of the S-box layers. This extension is based on a property of the S-box. The matrix property needed for potentially extending the 3-round collision attack into a 4-round one is not satisfied by the matrices proposed for Rescue.

Based on our present understanding, it does not seem probable that any such attacks could reach 5 rounds. Thus, the security margin with respect to rebound-type attacks seems really big.

Acknowledgements

This work was supported by StarkWare Industries and the Ethereum Foundation.

References

• [Aly+19] Abdelrahaman Aly et al. “Design of Symmetric-Key Primitives for Advanced Cryptographic Protocols.” Cryptology ePrint Archive, Report 2019/426. eprint.iacr.org/2019/426. 2019.
• [BSV07] Thomas Baigneres, Jacques Stern, and Serge Vaudenay. “Linear cryptanalysis of non binary ciphers.” In: International Workshop on Selected Areas in Cryptography. Springer. 2007, pp. 184–211.
• [Bey19] Tim Beyne. “Linear Cryptanalysis in the Weak Key Model.” KU Leuven, 2019.
• [CLO13] David Cox, John Little, and Donal O’Shea. Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra. Springer Science & Business Media, 2013.
• [DR07] Joan Daemen and Vincent Rijmen. “Plateau characteristics.” In: IET Information Security 1.1 (2007), pp. 11–17.
• [DR05] Joan Daemen and Vincent Rijmen. Probability distributions of Correlation and Differentials in Block Ciphers. Cryptology ePrint Archive, Report 2005/212. eprint.iacr.org/2005/212. 2005.
• [DR02] Joan Daemen and Vincent Rijmen. The Design of Rijndael: AES – The Advanced Encryption Standard. Information Security and Cryptography. Springer, 2002.
• [DR06] Joan Daemen and Vincent Rijmen. “Understanding Two-Round Differentials in AES.” In: SCN 06. Ed. by Roberto De Prisco and Moti Yung. Vol. 4116. LNCS. Springer, Heidelberg, Sept. 2006, pp. 78–94. doi: 10.1007/11832072_6.
• [Del74] Pierre Deligne. “La conjecture de Weil : I.” In: Publications Mathématiques de l’IHÉS 43 (1974), pp. 273–307. url: eudml.org/doc/103930.
• [HO99] Philip Hawkes and Luke O’Connor. “XOR and Non-XOR Differential Probabilities.” In: EUROCRYPT’99. Ed. by Jacques Stern. Vol. 1592. LNCS. Springer, Heidelberg, May 1999, pp. 272–285. doi: 10.1007/3-540-48910-X_19.
• [Hon+01] Seokhie Hong et al. “Provable Security against Differential and Linear Cryptanalysis for the SPN Structure.” In: FSE 2000. Ed. by Bruce Schneier. Vol. 1978. LNCS. Springer, Heidelberg, Apr. 2001, pp. 273–283. doi: 10.1007/3-540-44706-7_19.
• [Kat99] Nicholas M. Katz. “Estimates for singular exponential sums.” In: International Mathematics Research Notices 1999.16 (1999), pp. 875–899.
• [Men+09] Florian Mendel et al. “The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl.” In: FSE 2009. Ed. by Orr Dunkelman. Vol. 5665. LNCS. Springer, Heidelberg, Feb. 2009, pp. 260–276. doi: 10.1007/978-3-642-03317-9_16.
• [OCo94] Luke O’Connor. “On the Distribution of Characteristics in Bijective Mappings.” In: EUROCRYPT’93. Ed. by Tor Helleseth. Vol. 765. LNCS. Springer, Heidelberg, May 1994, pp. 360–370. doi: 10.1007/3-540-48285-7_31.
• [RL04] Antonio Rojas León. “General Estimates for Exponential Sums.” PhD thesis. Princeton University, 2004.
• [Wei48] André Weil. “On some exponential sums.” In: Proceedings of the National Academy of Sciences of the United States of America 34.5 (1948), p. 204.