Auf der „43rd International Cryptology Conference (IACR CRYPTO)“ stellen Bochumer Wissenschaftler fünf Paper mit HGI/CASA-Beteiligung vor. Die Konferenz findet vom 19.-24. August 2023 statt und zählt zu den renommiertesten Veranstaltungen im Bereich der IT-Sicherheitsforschung.
1. Cryptanalysis of Symmetric Primitives over Rings and a Key Recovery Attack on Rubato
Lorenzo Grassi, Martha Norberg Hovd, Irati Manterola Ayala, Håvard Raddum, Qingju Wang, Morten Øygarden
Ruhr University Bochum, Simula UiB, Telecom Paris, Institut Polytechnique de Paris
Abstract: Symmetric primitives are a cornerstone of cryptography, and have traditionally been defined over fields, where cryptanalysis is now well understood. However, a few symmetric primitives defined over rings Zq for a composite number q have recently been proposed, a setting where security is much less studied. In this paper we focus on studying established algebraic attacks typically defined over fields and the extent of their applicability to symmetric primitives defined over the ring of integers modulo a composite q. Based on our analysis, we present an attack on full Rubato, a family of symmetric ciphers proposed by Ha et al. at Eurocrypt 2022 designed to be used in a transciphering framework for approximate fully homomorphic encryption. We show that at least 25% of the possible choices for q satisfy certain conditions that lead to a successful key recovery attack with complexity significantly lower than the claimed security level for five of the six ciphers in the Rubato family.
2. Differential Meet-In-The-Middle Cryptanalysis
Christina Boura, Nicolas David, Patrick Derbez, Gregor Leander, María Naya-Plasencia
Inria, UVSQ, Université de Rennes, Ruhr-University Bochum
Abstract: In this paper we introduce the differential meet-in-the-middle framework, a new cryptanalysis technique for symmetric primitives. Our new cryptanalysis method combines techniques from both meet-in-the- middle and differential cryptanalysis. As such, the introduced technique can be seen as a way of extending meet-in-the-middle attacks and their variants but also as a new way to perform the key recovery part in differential attacks. We apply our approach to SKINNY-128-384 in the single-key model and to AES-256 in the related-key model. Our attack on SKINNY-128-384 permits to break 25 out of the 56 rounds of this variant and improves by two rounds the previous best known attacks. For AES-256 we attack 12 rounds by considering two related keys, thus outperforming the previous best related-key attack on AES-256 with only two related keys by 2 round
3. Coefficient Grouping for Complex Affine Layers
Fukang Liu, Lorenzo Grassi, Clémence Bouvier, Willi Meier, Takanori Isobe
Tokyo Institute of Technology, Ruhr University Bochum, Sorbonne University & Inria, FHNW, University of Hyogo & NICT
Abstract: Designing symmetric-key primitives for applications in Fully Homomorphic Encryption (FHE) has become important to address the issue of the ciphertext expansion. In such a context, cryptographic primitives with a low-AND-depth decryption circuit are desired. Consequently, quadratic nonlinear functions are commonly used in these primitives, including the well-known function over and the power map over a large finite field. In this work, we study the growth of the algebraic degree for an SPN cipher over, whose S-box is defined as the combination of a power map and an -linearized affine polynomial where. Specifically, motivated by the fact that the original coefficient grouping technique published at EUROCRYPT 2023 becomes less efficient for , we develop a variant technique that can efficiently work for arbitrary . With this new technique to study the upper bound of the algebraic degree, we answer the following questions from a theoretic perspective:
1. can the algebraic degree increase exponentially when ?
2. what is the influence of , and on the growth of the algebraic degree?
Based on this, we show (i) how to efficiently find to achieve the exponential growth of the algebraic degree and (ii) how to efficiently compute the upper bound of the algebraic degree for arbitrary. Therefore, we expect that these results can further advance the understanding of the design and analysis of such primitives.
4. Horst Meets Fluid-SPN: Griffin for Zero-Knowledge Applications
Lorenzo Grassi, Yonglin Hao, Christian Rechberger, Markus Schofnegger, Roman Walch, Qingju Wang
Ruhr University Bochum, Bochum (Germany), State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878 (China), Graz University of Technology (Austria), Horizen Labs (United States), Graz University of Technology (Austria), Know-Center GmbH (Austria), TACEO GmbH (Austria), Telecom Paris, Institut Polytechnique de Paris (France)
Abstract: Zero-knowledge (ZK) applications form a large group of use cases in modern cryptography, and recently gained in popularity due to novel proof systems. For many of these applications, cryptographic hash functions are used as the main building blocks, and they often dominate the overall performance and cost of these approaches.
Therefore, in the last years several new hash functions were built in order to reduce the cost in these scenarios, including Poseidon and Rescue among others. These hash functions often look very different from more classical designs such as AES or SHA-2. For example, they work natively over prime fields rather than binary ones. At the same time, for example Poseidon and Rescue share some common features, such as being SPN schemes and instantiating the nonlinear layer with invertible power maps. While this allows the designers to provide simple and strong arguments for establishing their security, it also introduces crucial limitations in the design, which may affect the performance in the target applications.
In this paper, we propose the Horst construction, in which the addition in a Feistel scheme (x, y) -> (y + F(x), x) is extended via a multiplication, i.e., (x, y) -> (y * G(x) + F(x), x).
By carefully analyzing the performance metrics in SNARK and STARK protocols, we show how to combine an expanding Horst scheme with a Rescue-like SPN scheme in order to provide security and better efficiency in the target applications. We provide an extensive security analysis for our new design Griffin and a comparison with all current competitors.
5. On Perfect Linear Approximations and Differentials over Two-Round SPNs
Christof Beierle, Patrick Felke, Patrick Neumann, Gregor Leander, Lukas Stennes
Ruhr-Universität Bochum, University of Applied Sciences Emden/Leer
Abstract: Recent constructions of (tweakable) block ciphers with an embedded cryptographic backdoor relied on the existence of probability-one differentials or perfect (non-)linear approximations over a reduced-round version of the primitive. In this work, we study how the existence of probability-one differentials or perfect linear approximations over two rounds of a substitution-permutation network can be avoided by design. More precisely, we develop criteria on the s-box and the linear layer that guarantee the absence of probability-one differentials for all keys. We further present an algorithm that allows to efficiently exclude the existence of keys for which there exists a perfect linear approximation.
Allgemeiner Hinweis: Mit einer möglichen Nennung von geschlechtszuweisenden Attributen implizieren wir alle, die sich diesem Geschlecht zugehörig fühlen, unabhängig vom biologischen Geschlecht.
