## CryptoDB

### Lorenzo Grassi

#### Publications

**Year**

**Venue**

**Title**

2022

TOSC

The Legendre Symbol and the Modulo-2 Operator in Symmetric Schemes over Fnp: Preimage Attack on Full Grendel
📺
Abstract

Motivated by modern cryptographic use cases such as multi-party computation (MPC), homomorphic encryption (HE), and zero-knowledge (ZK) protocols, several symmetric schemes that are efficient in these scenarios have recently been proposed in the literature. Some of these schemes are instantiated with low-degree nonlinear functions, for example low-degree power maps (e.g., MiMC, HadesMiMC, Poseidon) or the Toffoli gate (e.g., Ciminion). Others (e.g., Rescue, Vision, Grendel) are instead instantiated via high-degree functions which are easy to evaluate in the target application. A recent example for the latter case is the hash function Grendel, whose nonlinear layer is constructed using the Legendre symbol. In this paper, we analyze high-degree functions such as the Legendre symbol or the modulo-2 operation as building blocks for the nonlinear layer of a cryptographic scheme over Fnp.Our focus regards the security analysis rather than the efficiency in the mentioned use cases. For this purpose, we present several new invertible functions that make use of the Legendre symbol or of the modulo-2 operation.Even though these functions often provide strong statistical properties and ensure a high degree after a few rounds, the main problem regards their small number of possible outputs, that is, only three for the Legendre symbol and only two for the modulo-2 operation. By fixing them, it is possible to reduce the overall degree of the function significantly. We exploit this behavior by describing the first preimage attack on full Grendel, and we verify it in practice.

2022

TOSC

Influence of the Linear Layer on the Algebraic Degree in SP-Networks
📺
Abstract

We consider SPN schemes, i.e., schemes whose non-linear layer is defined as the parallel application of t ≥ 1 independent S-Boxes over F2n and whose linear layer is defined by the multiplication with a (n · t) × (n · t) matrix over F2. Even if the algebraic representation of a scheme depends on all its components, upper bounds on the growth of the algebraic degree in the literature usually only consider the details of the non-linear layer. Hence a natural question arises: (how) do the details of the linear layer influence the growth of the algebraic degree? We show that the linear layer plays a crucial role in the growth of the algebraic degree and present a new upper bound on the algebraic degree in SP-networks. As main results, we prove that in the case of low-degree round functions with large S-Boxes: (a) an initial exponential growth of the algebraic degree can be followed by a linear growth until the maximum algebraic degree is reached; (b) the rate of the linear growth is proportional to the degree of the linear layer over Ft2n. Besides providing a theoretical insight, our analysis is particularly relevant for assessing the security of the security of cryptographic permutations designed to be competitive in applications like MPC, FHE, SNARKs, and STARKs, including permutations based on the Hades design strategy. We have verified our findings on small-scale instances and we have compared them against the currently best results in the literature, showing a substantial improvement of upper bounds on the algebraic degree in case of low-degree round functions with large S-Boxes.

2022

TOSC

Differential Trail Search in Cryptographic Primitives with Big-Circle Chi:: Application to Subterranean
Abstract

Proving upper bounds for the expected differential probability (DP) of differential trails is a standard requirement when proposing a new symmetric primitive. In the case of cryptographic primitives with a bit-oriented round function, such as Keccak, Xoodoo and Subterranean, computer assistance is required in order to prove strong upper bounds on the probability of differential trails. The techniques described in the literature make use of the fact that the non-linear step of the round function is an S-box layer. In the case of Keccak and Xoodoo, the S-boxes are instances of the chi mapping operating on l-bit circles with l equal to 5 and 3 respectively. In that case the differential propagation properties of the non-linear layer can be evaluated efficiently by the use of pre-computed difference distribution tables.Subterranean 2.0 is a recently proposed cipher suite that has exceptionally good energy-efficiency when implemented in hardware (ASIC and FPGA). The non-linear step of its round function is also based on the chi mapping, but operating on an l = 257-bit circle, comprising all the state bits. This making the brute-force approach proposed and used for Keccak and Xoodoo infeasible to apply. Difference propagation through the chi mapping from input to output can be treated using linear algebra thanks to the fact that chi has algebraic degree 2. However, difference propagation from output to input is problematic for big-circle chi. In this paper, we tackle this problem, and present new techniques for the analysis of difference propagation for big-circle chi.We implemented these techniques in a dedicated program to perform differential trail search in Subterranean. Thanks to this, we confirm the maximum DP of 3-round trails found by the designers, we determine the maximum DP of 4-round trails and we improve the upper bounds for the DP of trails over 5, 6, 7 and 8 rounds.

2022

TOSC

Invertible Quadratic Non-Linear Layers for MPC-/FHE-/ZK-Friendly Schemes over Fnp: Application to Poseidon
Abstract

Motivated by new applications such as secure Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero-Knowledge proofs (ZK), many MPC-, FHE- and ZK-friendly symmetric-key primitives that minimize the number of multiplications over Fp for a large prime p have been recently proposed in the literature. This goal is often achieved by instantiating the non-linear layer via power maps x↦xd. In this paper, we start an analysis of new non-linear permutation functions over Fnp that can be used as building blocks in such symmetrickey primitives. Given a local map F : Fmp→ Fp, we limit ourselves to focus on S-Boxes over Fnp for n ≥ m defined as SF (x0, x1, . . . , xn−1) = y0|y1| . . . |yn−1 where yi := F(xi, xi+1, . . . , xi+m−1). As main results, we prove that• given any quadratic function F : F2p→ Fp, the corresponding S-Box SF over Fnp for n ≥ 3 is never invertible;• similarly, given any quadratic function F : F3p → Fp, the corresponding S-Box SF over Fnp for n ≥ 5 is never invertible.Moreover, for each p ≥ 3, we present (1st) generalizations of the Lai-Massey construction over Fnp defined as before via functions F : Fmp → Fp for each n = m ≥ 2 and (2nd) (non-trivial) quadratic functions F : F3p → Fp such that SF over Fnp for n ∈ {3, 4} is invertible. As an open problem for future work, we conjecture that for each m ≥ 1 there exists a finite integer nmax(m) such that SF over Fnp defined as before via a quadratic function F : Fmp →Fp is not invertible for each n ≥ nmax(m). Finally, as a concrete application, we propose Neptune, a variant of the sponge hash function Poseidon, whose non-linear layer is designed by taking into account the results presented in this paper. We show that this variant leads to a concrete multiplication reduction with respect to Poseidon.

2022

ASIACRYPT

Security of Truncated Permutation Without Initial Value
📺
Abstract

Indifferentiability is a powerful notion in cryptography. If a construction is proven to be indifferentiable from an ideal object, it can under certain assumptions instantiate that ideal object in higher-level constructions. Indifferentiability is a particularly useful model for cryptographic hash functions, and myriad results are known proving that a hash function behaves like a random oracle under the assumption that the underlying primitive (typically a compression function, a block cipher, or a permutation) is random. Recently, advances have been made in proving indifferentiability of one-way functions with fixed input length. One such example is truncation of a permutation. If one evaluates a random permutation on an input value concatenated with a fixed initial value, and truncates the output, one obtains a construction that is indifferentiable from a random function up to a certain bound (Dodis et al., FSE 2009; Choi et al., ASIACRYPT 2019). Security of this construction, however, is in part determined by the length of the initial value; omission of this fixed value yields an insecure construction.
In this paper, we reconsider truncation of a permutation, and prove that the construction is indifferentiable from a random oracle, even if this fixed initial value is replaced by a randomized value. This randomized value may be the same for different evaluations of the construction, or freshly generated, up to the discretion of the adversary. The security level is the same as that of truncation with fixed initial value, up to collisions in the randomized value.
We show that our construction has immediate implications in the context of parallel variable-length digest generation. In detail, we describe Cascade-MGF, that operates on top of any cryptographic hash function and uses the hash function output as randomized initial value in truncation. We demonstrate that Cascade-MGF compares favorably over earlier parallel variable-length digest generation constructions, namely Counter-MGF and Chained-MGF, in almost all settings.

2021

EUROCRYPT

Ciminion: Symmetric Encryption Based on Toffoli-Gates over Large Finite Fields
📺
Abstract

Motivated by new applications such as secure Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero-Knowledge proofs (ZK), the need for symmetric encryption schemes that minimize the number of field multiplications in their natural algorithmic description is apparent. This development has brought forward many dedicated symmetric encryption schemes that minimize the number of multiplications in GF(2^n) or GF(p), with p being prime. These novel schemes have lead to new cryptanalytic insights that have broken many of said schemes. Interestingly, to the best of our knowledge, all of the newly proposed schemes that minimize the number of multiplications use those multiplications exclusively in S-boxes based on a power mapping that is typically x^3 or x^{-1}. Furthermore, most of those schemes rely on complex and resource-intensive linear layers to achieve a low multiplication count.
In this paper, we present Ciminion, an encryption scheme minimizing the number of field multiplications in large binary or prime fields, while using a very lightweight linear layer. In contrast to other schemes that aim to minimize field multiplications in GF(2^n) or GF(p), Ciminion relies on the Toffoli gate to improve the non-linear diffusion of the overall design. In addition, we have tailored the primitive for the use in a Farfalle-like construction in order to minimize the number of rounds of the used primitive, and hence, the number of field multiplications as far as possible.

2021

TOSC

Proving Resistance Against Infinitely Long Subspace Trails: How to Choose the Linear Layer
📺
Abstract

Designing cryptographic permutations and block ciphers using a substitutionpermutation network (SPN) approach where the nonlinear part does not cover the entire state has recently gained attention due to favorable implementation characteristics in various scenarios.For word-oriented partial SPN (P-SPN) schemes with a fixed linear layer, our goal is to better understand how the details of the linear layer affect the security of the construction. In this paper, we derive conditions that allow us to either set up or prevent attacks based on infinitely long truncated differentials with probability 1. Our analysis is rather broad compared to earlier independent work on this problem since we consider (1) both invariant and non-invariant/iterative trails, and (2) trails with and without active S-boxes.For these cases, we provide rigorous sufficient and necessary conditions for the matrix that defines the linear layer to prevent the analyzed attacks. On the practical side, we present a tool that can determine whether a given linear layer is vulnerable based on these results. Furthermore, we propose a sufficient condition for the linear layer that, if satisfied, ensures that no infinitely long truncated differential exists. This condition is related to the degree and the irreducibility of the minimal polynomial of the matrix that defines the linear layer. Besides P-SPN schemes, our observations may also have a crucial impact on the Hades design strategy, which mixes rounds with full S-box layers and rounds with partial S-box layers.

2020

EUROCRYPT

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 non-uniform 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 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.

2020

ASIACRYPT

An Algebraic Attack on Ciphers with Low-Degree Round Functions: Application to Full MiMC
📺
Abstract

Algebraically simple PRFs, ciphers, or cryptographic hash functions are becoming increasingly popular, for example due to their attractive properties for MPC and new proof systems (SNARKs, STARKs, among many others).
In this paper, we focus on the algebraically simple construction MiMC, which became an attractive cryptanalytic target due to its simplicity, but also due to its use as a baseline in a competition for more recent algorithms exploring this design space.
For the first time, we are able to describe key-recovery attacks on all full-round versions of MiMC over GF(2^n), requiring half the code book. In the chosen-ciphertext scenario, recovering the key from this data for the n-bit full version of MiMC takes the equivalent of less than 2^(n - log_2(n) + 1) calls to MiMC and negligible amounts of memory.
The attack procedure is a generalization of higher-order differential cryptanalysis, and it is based on two main ingredients. First, we present a higher-order distinguisher which exploits the fact that the algebraic degree of MiMC grows significantly slower than originally believed. Secondly, we describe an approach to turn this distinguisher into a key-recovery attack without guessing the full subkey. Finally, we show that approximately ceil(log_3(2 * R)) more rounds (where R = ceil(n * log_3(2)) is the current number of rounds of MiMC-n/n) can be necessary and sufficient to restore the security against the key-recovery attack presented here.
The attack has been practically verified on toy versions of MiMC. Note that our attack does not affect the security of MiMC over prime fields.

2019

ASIACRYPT

Algebraic Cryptanalysis of STARK-Friendly Designs: Application to MARVELlous and MiMC
Abstract

The block cipher Jarvis and the hash function Friday, both members of the MARVELlous family of cryptographic primitives, are among the first proposed solutions to the problem of designing symmetric-key algorithms suitable for transparent, post-quantum secure zero-knowledge proof systems such as ZK-STARKs. In this paper we describe an algebraic cryptanalysis of Jarvis and Friday and show that the proposed number of rounds is not sufficient to provide adequate security. In Jarvis, the round function is obtained by combining a finite field inversion, a full-degree affine permutation polynomial and a key addition. Yet we show that even though the high degree of the affine polynomial may prevent some algebraic attacks (as claimed by the designers), the particular algebraic properties of the round function make both Jarvis and Friday vulnerable to Gröbner basis attacks. We also consider MiMC, a block cipher similar in structure to Jarvis. However, this cipher proves to be resistant against our proposed attack strategy. Still, our successful cryptanalysis of Jarvis and Friday does illustrate that block cipher designs for “algebraic platforms” such as STARKs, FHE or MPC may be particularly vulnerable to algebraic attacks.

2018

CRYPTO

Rasta: A Cipher with Low ANDdepth and Few ANDs per Bit
📺
Abstract

Recent developments in multi party computation (MPC) and fully homomorphic encryption (FHE) promoted the design and analysis of symmetric cryptographic schemes that minimize multiplications in one way or another. In this paper, we propose with Rastaa design strategy for symmetric encryption that has ANDdepth d and at the same time only needs d ANDs per encrypted bit. Even for very low values of d between 2 and 6 we can give strong evidence that attacks may not exist. This contributes to a better understanding of the limits of what concrete symmetric-key constructions can theoretically achieve with respect to AND-related metrics, and is to the best of our knowledge the first attempt that minimizes both metrics simultaneously. Furthermore, we can give evidence that for choices of d between 4 and 6 the resulting implementation properties may well be competitive by testing our construction in the use-case of removing the large ciphertext-expansion when using the BGV scheme.

2018

ASIACRYPT

Quantum Algorithms for the $k$-xor Problem
Abstract

The $$k$$-xor (or generalized birthday) problem is a widely studied question with many applications in cryptography. It aims at finding k elements of n bits, drawn at random, such that the xor of all of them is 0. The algorithms proposed by Wagner more than fifteen years ago remain the best known classical algorithms for solving them, when disregarding logarithmic factors.In this paper we study these problems in the quantum setting, when considering that the elements are created by querying a random function (or k random functions) $$H~: \{0,1\}^n \rightarrow \{0,1\}^n$$. We consider two scenarios: in one we are able to use a limited amount of quantum memory (i.e. a number O(n) of qubits, the same as the one needed by Grover’s search algorithm), and in the other we consider that the algorithm can use an exponential amount of qubits. Our newly proposed algorithms are of general interest. In both settings, they provide the best known quantum time complexities.In particular, we are able to considerately improve the $$3$$-xor algorithm: with limited qubits, we reach a complexity considerably better than what is currently possible for quantum collision search. Furthermore, when having access to exponential amounts of quantum memory, we can take this complexity below $$O(2^{n/3})$$, the well-known lower bound of quantum collision search, clearly improving the best known quantum time complexity also in this setting.We illustrate the importance of these results with some cryptographic applications.

2018

TOSC

Mixture Differential Cryptanalysis: a New Approach to Distinguishers and Attacks on round-reduced AES
📺
Abstract

At Eurocrypt 2017 the first secret-key distinguisher for 5-round AES - based on the “multiple-of-8” property - has been presented. Although it allows to distinguish a random permutation from an AES-like one, it seems rather hard to implement a key-recovery attack different than brute-force like using such a distinguisher. In this paper we introduce “Mixture Differential Cryptanalysis” on round-reduced AESlike ciphers, a way to translate the (complex) “multiple-of-8” 5-round distinguisher into a simpler and more convenient one (though, on a smaller number of rounds). Given a pair of chosen plaintexts, the idea is to construct new pairs of plaintexts by mixing the generating variables of the original pair of plaintexts. Here we theoretically prove that for 4-round AES the corresponding ciphertexts of the original pair of plaintexts lie in a particular subspace if and only if the corresponding pairs of ciphertexts of the new pairs of plaintexts have the same property. Such secret-key distinguisher - which is independent of the secret-key, of the details of the S-Box and of the MixColumns matrix (except for the branch number equal to 5) - can be used as starting point to set up new key-recovery attacks on round-reduced AES. Besides a theoretical explanation, we also provide a practical verification both of the distinguisher and of the attack.

2016

ASIACRYPT

2016

TOSC

Subspace Trail Cryptanalysis and its Applications to AES
Abstract

We introduce subspace trail cryptanalysis, a generalization of invariant subspace cryptanalysis. With this more generic treatment of subspaces we do no longer rely on specific choices of round constants or subkeys, and the resulting method is as such a potentially more powerful attack vector. Interestingly, subspace trail cryptanalysis in fact includes techniques based on impossible or truncated differentials and integrals as special cases. Choosing AES-128 as the perhaps most studied cipher, we describe distinguishers up to 5-round AES with a single unknown key. We report (and practically verify) competitive key-recovery attacks with very low data-complexity on 2, 3 and 4 rounds of AES. Additionally, we consider AES with a secret S-Box and we present a (generic) technique that allows to directly recover the secret key without finding any information about the secret S-Box. This approach allows to use e.g. truncated differential, impossible differential and integral attacks to find the secret key. Moreover, this technique works also for other AES-like constructions, if some very common conditions on the S-Box and on the MixColumns matrix (or its inverse) hold. As a consequence, such attacks allow to better highlight the security impact of linear mappings inside an AES-like block cipher. Finally, we show that our impossible differential attack on 5 rounds of AES with secret S-Box can be turned into a distinguisher for AES in the same setting as the one recently proposed by Sun, Liu, Guo, Qu and Rijmen at CRYPTO 2016

#### Coauthors

- Martin R. Albrecht (2)
- Carlos Cid (2)
- Joan Daemen (1)
- Christoph Dobraunig (2)
- Maria Eichlseder (2)
- Anna Guinet (1)
- Aldo Gunsing (1)
- Dmitry Khovratovich (2)
- Daniël Kuijsters (1)
- Virginie Lallemand (1)
- Gregor Leander (1)
- Eik List (1)
- Reinhard Lüftenegger (4)
- Alireza Mehrdad (1)
- Silvia Mella (1)
- Florian Mendel (1)
- Bart Mennink (1)
- María Naya-Plasencia (1)
- Silvia Onofri (1)
- Marco Pedicini (1)
- Christian Rechberger (9)
- Dragos Rotaru (1)
- Arnab Roy (1)
- Sondre Rønjom (3)
- Markus Schofnegger (6)
- André Schrottenloher (1)
- Luca Sozzi (1)
- Tyge Tiessen (1)
- Qingju Wang (1)
- Morten Øygarden (1)