Symmetric Cryptography

While quantum attacks on symmetric cryptosystems have been less devastating than those on certain popular public-key cryptosystems, classical provable security results on symmetric modes are not trivial to extend to the Q2 setting where the adversary has superposition access to the mode. In this work we attempt to build a generic proof framework applicable to such games by building on several previous works on compressed oracles.

Differential cryptanalysis is an old and powerful attack against block ciphers. While different techniques have been introduced throughout the years to improve the complexity of this attack, the key recovery phase remains a tedious and error-prone procedure. In this talk, we present a new algorithm and its associated tool that permits, given a distinguisher, to output an efficient key guessing strategy. Our tool can be applied to SPN ciphers whose linear layer consists of a bit-permutation and whose key schedule is linear or almost linear. It can be used not only to help cryptanalysts find the best differential attack on a given cipher but also to assist designers in their security analysis. We applied our tool to four targets: RECTANGLE, PRESENT-80, SPEEDY-7-192 and GIFT-64. We extend the previous best attack on RECTANGLE-128 by one round and the previous best differential attack against PRESENT-80 by 2 rounds. We improve a previous key recovery step in an attack against SPEEDY and present more efficient key recovery strategies for RECTANGLE-80 and GIFT. Our tool outputs the results in only a second for most targets.

In this talk 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 rounds.

If we consider (authenticated) encryption schemes based on the sponge/duplex construction, it is typically assumed that the adversary has the capability to choose the nonce/IV on its will (except for repetitions). In this talk, we discuss how the security changes if restrictions on the choice of the nonce are imposed, varying from the global nonce case over the random nonce case to the nonce on key case.

NIST SP 800-108r1 specifies Key Derivation Functions (KDFs) based on PseudoRandom Functions (PRFs). In the document, the key control security is discussed, and it is pointed out KDFs based on CMAC have security issues. In this talk, we review the notion of the key control security and the security issues. We then point out similar security issues are in other block cipher based PRFs. We also present an attempt to formalize a cryptographic definition of the key control security, and discuss possible directions for future research.

Most of the beyond-the-birthday-bound deterministic MAC (or PRF) constructions, like PMAC+ and LightMAC+, can be viewed as an instance of the Double-block Hash-then-Sum (DbHtS) paradigm (DDNP, IACR ToSC 2018). It is well-known (KLL, EUROCRYPT 2020; JN, JoC 2020; LNS, CRYPTO 2018) that DbHtS constructions are secure up to roughly $2^{3n/4}$ queries, where n denotes the block size. In contrast, the security guarantees for single-keyed variants of DbHtS, namely PMAC+ and LightMAC+, have only been proven up to $2^{2n/3}$ queries, with no known matching attack. In this work, we revisit the security of single-keyed DbHtS and map the problem to a graph vertex labeling problem where the labels are to be chosen outside some prohibited set (a strict subset of ${\{0,1\}}^n$). We derive a strong lower bound for the number of such valid vertex labelings, under certain randomness assumptions on the prohibited set. This directly implies security up to $2^{3n/4}$ queries for single-keyed DbHtS. Furthermore, we show that the hash functions in the single-keyed variants of PMAC+ and LightMAC+ satisfy the required conditions. Consequently, the single-keyed PMAC+ and LightMAC+ are shown to be equivalent (up to some constant factors) to their multi-keyed counterparts in terms of security. We conclude with a discussion on the potential applications of our techniques to similar problems in the random permutation model.

We study the application of the boomerang attack technique to ciphers following a Feistel construction and having a quadratic round function. We prove that many previously published papers give highly inaccurate probability approximations of the distinguishers they use. We next propose a new SMT model that takes into account our findings and we are able to propose a 19-round distinguisher of Simon-32/64 that we convert into the (to the best of our knowledge) first 25-round attack.

In this work, the first third-party cryptanalysis of the FHE-friendly stream cipher HERA is performed, by showing how to mount new algebraic attacks with multiple collisions in the round keys. Specifically, according to the special way to randomize the round keys in HERA, we peel off the last nonlinear layer by using collisions in the last-round key and a simple property of the power map. In this way, we construct an overdefined system of equations of a much lower degree in the key, and efficiently solve the system via the linearization technique. As a result, for HERA with $192$ and $256$ bits of security, respectively, we break some parameters under the same assumption made by designers that the algebra constant $\omega$ for Gaussian elimination is $\omega =2$, i.e., Gaussian elimination on an $n\times n$ matrix takes $𝒪(n^{\omega })$ field operations. If using more conservative choices like $\omega \in 2.8,3$, our attacks can also successfully reduce the security margins of some variants of HERA to only 1 round.

The sum of two $n$-bit pseudorandom permutations is known to behave like a pseudorandom function with $n$ bits of security. A recent line of research has investigated the security of two public $n$-bit permutations and its degree of indifferentiability. Mandal et al. (INDOCRYPT 2010) proved $2n/3$-bit security, Mennink and Preneel (ACNS 2015) pointed out a non-trivial flaw in their analysis and re-proved $(2n/3-{\log }_2(n))$-bit security. Bhattacharya and Nandi (EUROCRYPT 2018) eventually improved the result to $n$-bit security. Recently, Gunsing at CRYPTO 2022 already observed that a proof technique used in this line of research only holds for sequential indifferentiability. We revisit the line of research in detail, and observe that the strongest bound of $n$-bit security has two other serious issues in the reasoning, the first one is actually the same non-trivial flaw that was present in the work of Mandal et al., while the second one discards biases in the randomness influenced by the distinguisher. More concretely, we introduce two attacks that show limited potential of different approaches. We (i) show that the latter issue that discards biases only holds up to $2^{3n/4}$ queries, and (ii) perform a differentiability attack against their simulator in $2^{5n/6}$ queries. On the upside, we revive the result of Mennink and Preneel and show $(2n/3-{\log }_2(n))$-bit regular indifferentiability security of the sum of public permutations.

Rogaway and Shrimpton (RS06) presented the idea of vector-input MAC that accepts a vector consisting of variable-length bit strings. A vector-input MAC could be built on a conventional (bit) string-input MAC, e.g, CMAC, with an injective encoding. RS06 pointed out an efficiency loss in this method and presented a general construction S2V that is more efficient than the encoding-based method. However, despite its potential, their work on vector-input MAC has been largely overlooked for more than 16 years. We revisit RS06’s treatment of vector-input MAC and showed that the topic is more subtle than initially considered. We first formally define the problem of vector-input MAC and propose a natural efficiency goal for vector-input MACs as a counterpart of what has been considered for string-input MACs. Since S2V with any string-input MAC mode never achieves this efficiency goal, we propose a new MAC mode, VecMAC, that achieves this goal for any vector space. VecMAC is a variant of the popular PMAC. However, its use of tweaks is more involved and conceptually different from PMAC. We also provide preliminary implementation results.

Integrity under the release of unverified plaintext (INT-RUP) is the security notion for authenticated encryption with associated data (AEAD) schemes. When an AEAD scheme is INT-RUP secure, it guarantees authenticity even when the decryption function inevitably or erroneously outputs the decrypted message without verification. INT-RUP security against existing AEAD schemes has been extensively studied, such as ChaCha20-Poly1305, SAEF, and TinyJambu. Many schemes have been designed with a provable security claim on INT-RUP as one of the main security features, such as Minalpher, CPFB, LOTUS/LOCUS, and Oribatida. However, surprisingly, there is no INT-RUP analysis on GCM, which is one of the most widely deployed AEAD schemes. We prove that GCM has INT-RUP security with almost the same security level as that of the classical authenticity notion by showing that INT-RUP security of GCM is reduced to the variant of the unforgeability of GMAC inside GCM. Our future work is to analyze INT-RUP security on CCM.

The design and analysis of cryptographic systems often rely on proving the security of various primitives and constructions. One prominent framework for assessing the security of cryptographic constructions is indifferentiability introduced by Maurer et al. in [1], which provides a rigorous method to demonstrate the equivalence of constructed systems with idealized versions, even in the presence of adversaries with access to underlying primitives. This paper explores the indifferentiability of Feistel networks introduced by Horst Feistel as a design component of Lucifer [2], a widely used paradigm for constructing cryptographic primitives from simpler components known as round functions. Feistel networks offer a structured approach to building cryptographic systems, particularly permutations, by iteratively applying round functions to input data. Understanding the indifferentiability of Feistel networks is crucial for establishing the security of numerous cryptographic constructions.

A simulator to prove indifferentiability of six-round Feistel was proposed in [3] by Coron et. al., along with an attack on five-round Feistel that works against any simulator. This simulator was later shown to be incapable of demonstrating indifferentiability of six-round Feistel by Holenstein et. al. in [4]. An early version of [4] proposed a simulator for the 18-round construction that achieved indifferentiability, and in a later revision this was changed to a simulator for the 14-round version. Next, two concurrent works by Dai and Steinberger [5] and Dachman-Soled et al. [6] both proved indifferentiability of the 10-round Fesitel network, the former by repairing the flawed 10-round simulator from [7], and the latter by modifying the 14-round simulator from [4]. Finally, in what has so far been the latest work in this series, Dai and Steinberger [8] established the indifferentiability of the 8-round Fesitel construction by optimising their simulator from [5]. Thus, while later proofs have been found for the indifferentiability of Feistel networks with eight or more rounds, that of six-round Feistel still remains an open question. The highlight of this paper is the presentation of a novel proof demonstrating the indifferentiability of the six-round Feistel network. This proof is accompanied by the design of an advanced simulator that preemptively handles construction queries from adversaries, ensuring the security of the constructed system.

In this talk, I presented a new type of algebraic attack that applies to many recent arithmetization-oriented families of permutations, such as those used in Griffin [1], Anemoi [2], and ArionHash [3], whose security relies on the hardness of the constrained-input constrained-output (CICO) problem. We introduce the FreeLunch approach: the monomial ordering is chosen so that the natural polynomial system encoding the CICO problem already is a Gröbner basis. In addition, we present a new dedicated resolution algorithm for FreeLunch systems of complexity lower than applicable state-of-the-art FGLM algorithms. We show that the FreeLunch approach challenges the security of fullround instances of Anemoi, Arion and Griffin. We confirm these theoretical results with experimental results on those three permutations. In particular, using the FreeLunch attack combined with a new technique to bypass 3 rounds of Griffin, we recover a CICO solution for 7 out of 10 rounds of Griffin in less than four hours on one core of AMD EPYC 7352 (2.3GHz).

This talk overviews an ongoing research agenda aimed at proving security of block ciphers against limited classes of attacks. We focus on proving that Substitution Permutation Networks (SPNs), when instantiated with concrete S-boxes (such as the AES S-box), give us t-wise independent permutations. This is a weak property (compared to being a full-fledged pseudorandom permutation), but it implies in particular security against classical families of statistical attacks such as linear and differential cryptanalysis. Our approach is in contrast with prior works aiming at full proofs of security for idealized versions of block ciphers.

The proprietary TETRA Encryption standards, TEA1, TEA2, and TEA3, distributed by ETSI except for TEA2 (see [1]), were recently reverse-engineered in [2]. TEA1, TEA2, TEA3 are stream ciphers based on byte-oriented non-linear feedback shift registers (NFSRs). While TEA1 is an insecure cipher (the 80-bit key is compressed into a 4-byte register, effectively reducing its key length to 32 bits), the security level of the other algorithms TEA2 and TEA3 is less clear.

Although there is no obvious attack, the choices of components used in TEA3 (in contrast to TEA2) are questionable from a designer’s point of view. In particular, the key register of TEA3 employs an 8-bit Sbox in its feedback, denoted $S$, that is not a permutation. Instead, its distance to a permutation is only one bit in the sense that flipping a single bit in its lookup table would cause $S$ to be bijective. Furthermore, the 10-byte key register can be decomposed into the cascade connection of a 5-byte NFSR into a 5-byte LFSR with feedback polynomial $(X^5+SB3X^2+1)\cdot (X^5+1)$. Our experiments (started as joint work with Jens Alich, Christof Beierle, Patrick Felke, Gregor Leander, and Lukas Stennes) reveal that there are initial states of the 10-byte key register that have a period of only $10$ bytes and that the maximal period is only about $10\cdot 2^{40}$ bytes. The TEA3 key stream generator is depicted in [2, Figure 8]. The goal of this research group was to study the following questions:

• $\mathrm{■}$

  Can we exploit these properties to conduct an attack on TEA3?

• $\mathrm{■}$

  How were the components used in TEA3 designed?

During the research meetings at the Dagstuhl Seminar, the working group made the following progress on those questions:

• $\mathrm{■}$

  Using the existing theory on NFSRs from [3] and the structure of the cascade connection of the key register, we were able to derive necessary conditions on the period lengths of the key register. We further developed ideas to fully understand the cycle structure.

• $\mathrm{■}$

  The 16-to-8 bit functions $F31$ and $F32$ used in the state register of TEA3 are balanced vectorial Boolean functions built from 8 parallel 4-bit Boolean functions with overlapping inputs. A priori, it is not clear why such a construction leads to a balanced function. We identified a possible underlying construction method of $F31$ and $F32$.

• $\mathrm{■}$

  We identified some generic time-memory tradeoff attacks on the key stream generator with a complexity slightly below $2^{80}$ (i.e., the complexity of a brute-force attack)

At CRYPTO 2019, Gohr introduced a novel key recovery strategy for Speck32/64, termed the BayesianKeySearch algorithm. This approach challenges the conventional Wrong Key Randomization Hypothesis (WKRH), particularly in scenarios where the attack on Speck undergoes only a single round of trial decryption. The BayesianKeySearch algorithm iteratively refines key guesses by generating new round-key candidates based on previous guesses, thereby progressively enhancing the quality of the guessed key. Notably, this method requires a limited number of one-round trial decryptions, reducing time complexity.

Despite its practical implications, the algorithm lacks a comprehensive theoretical framework to quantify the impact of various parameters on attack complexity and success rate. This discussion group aimed to bridge this gap by establishing a theoretical model to evaluate its complexity better and broadening the application to conventional key recovery attacks.

The discussion centered on two primary aspects: examining how the wrong key-right key distance influences the statistics in traditional differential and linear attacks and developing methods to leverage these non-random influences. Initial outcomes of this discussion include a proposed formula hypothesizing the relationship between the Hamming weight of the wrong key-right key distance and the probability of returning to the same output difference, a drawn parallel between this probability’s evaluation and the BCT’s computation (difference-boomerang connective probability), and a proposed time-data tradeoff strategy in differential key-recovery attacks.

The group plans to persist in the investigation of this topic post-seminar.

SCARF if a tweakable BC for cache randomization, proposed at Usenix Security 2023.

It’s block length is 10 bits only, it absorbs a tweak of $48$ bits and it offers $80$-bit security (but a $240$-bit key is used). The security claim is peculiar as an attacker cannot directly query the TBC. Instead, the attacker can query collision or composition oracles. The query complexity is up to $2^{4}0$.

In this working group we analyzed the security of SCARF by investigating different cryptanalysis techniques. We thought of several approaches:

• $\mathrm{■}$

  Exploit the fact that 0 is a fixed point for some operations of the round function.

• $\mathrm{■}$

  Analyse the algebraic degree growth and exploit the algebraic normal form of the Sbox.

• $\mathrm{■}$

  Polytopic cryptanalysis.

• $\mathrm{■}$

  Multiple-tweak differential attack.

While all the approaches seem promising, the multiple-tweak differential attack seems to be particular interesting for this cipher and we hope to be able to break (7+7)/(8+8) rounds of this cipher with this approach.

Our research group was composed of Maria Eichlseder, Orr Dunkelman, María Naya-Plasencia, Virginie Lallemand, Ryoma Ito and Patrick Derbez. The main topic of our group was to propose a new modelization of impossible differential attacks, more accurate than a classic “0/1/?” model but faster than exhausting all differential characteristics. Our idea is to track as well the equalities between internal state variables to propagate more information and extend the impossible cases. We also investigated several other topics including extension of differential-mitm attacks, impossible differential-linear attacks as well as an attack against a generic cipher relying on the nice algorithmic problem of finding the closest pair of vectors.

NIST SP 800-108r1 [1] specifies Key Derivation Functions (KDFs) based on PseudoRandom Functions (PRFs). It specifies a KDF based on KMAC, and it also specifies KDFs in counter mode, feedback mode, and double-pipeline mode, which are combined with HMAC or CMAC as the PRF.

The document was revised in August 2022, and a discussion on the key control security was added, showing a security issue in KDFs with CMAC. The goal of this research group is to formalize a cryptographic definition of the key control security, and analyze the security of KDFs in the NIST document from the provable security and cryptanalytic perspectives.

The group identified a formal security definition, and drafted a security proof of a KDF based on KMAC. We also analyzed KDFs based on CMAC from a cryptanalytic view point. In particular, we focused on the strengthened version, which is a variant of the KDFs based on CMAC to mitigate the issue in their key control security.

The aim of this research group was to investigate the security of sponge-based combiners and variants from both cryptanalytical and provable security perspectives. The motivation behind this investigation stemmed from the observation that while finding inner collisions in a sponge generically requires $2^{c/2}$ permutation evaluations, the associated attack does not straightforwardly generalize with combiners due to the repeated absorption of the same message block. On the cryptanalytical aspect, we examined various sponge-based combiners and derivatives, namely the concatenation combiner, XOR combiner, and two hash-twice-like constructions. We focused on collision, second preimage, and preimage attacks, with Joux’s attack [1] serving as the main tool. Notably, except for collision of the hash-twice construction with identical permutations (which costs $2^{c/2}$ evaluations), a term in $2^{b/2}$ emerged consistently in our analysis. On the provable security aspect, the discussions provided valuable insights that could be helpful to improve the security of these constructions, ideally up to min(c, b/2) bits. We plan to continue working on these two aspects after the seminar.