Symmetric Cryptography

The seminar program consisted of a few short presentations and in-depth group meetings. Presentations were about the above topics and other relevant areas of symmetric cryptography, including state-of-the-art cryptanalytic techniques and new designs. Below one can find the list of abstracts for talks given during the seminar.

The research groups were on various topics in symmetric cryptography, all related to one of the above points in one way or another. On the last day of the seminar, the leaders of each group gave brief summaries of achievements. Some teams continued working on the topic after the seminar and started new research collaborations. Here are the summaries of the five groups:

• $\mathrm{■}$

  Group 1 worked and discussed on various problems of provable security, roughly corresponding to one project per person. For three of the projects, the groups had preliminary discussions, and the next step will be to perform the remaining research and investigate the details offline. For two problems, namely improved unforgeability of certain MAC constructions and generic analysis of PRF’s and MAC’s on 2 public permutations, they advanced quite well and the details will be written down soon after the seminar.

• $\mathrm{■}$

  Group 2 worked on several topics that they plan to continue after the seminar. One was to find good algorithms for detecting the optimal trees of some Boolean functions in the context of improved key-recovery attacks, and figuring out if we actually need trees, or if we could find or use better partitions that do not correspond to a tree and yet improve the complexity. They also worked on building two attacks on the HALFLOOP construction. They solved the problem of finding structures in linear layers and of decomposing them, and they applied this to Streebog. They also continued developing a new cryptanalysis family; differential meet-in-the-middle attacks. They figured out how to correctly combine it with bicliques, and started working on an application on the construction of SKINNY, which should be comparable if not better than the best known attacks.

• $\mathrm{■}$

  Group 3 worked on several topics related to cryptanalysis, that they plan to continue after the seminar. The studied Tweakable Twine, a tweakable variant of Twine proposed in 2019. They looked at impossible differential distinguishers, but unfortunately they were not able to cover more rounds than in previous work. They also looked at the differential propagation of the cipher. They were able to find a distinguisher that would be established with a probability of $2^{-61}$, and they rediscovered a 24-round zero correlation attack in Twine. They have also pointed out several observations on TinyJAMBU, including a method to break the $P_b$ permutation (for 384 rounds) if one can observe collisions during the processing phase. They looked at a paper from 2016 on KATAN that searches for extended boomerang distinguishers. They are implementing the attacks to observe the impact of the middle-round dependencies experimentally. Finally, they looked at (free-start) collisions on Romulus-H and tried to find differential characteristics that are suitable to be used in two SKINNY invocations. One idea would be to use the dependencies to have a collision of a higher probability.

• $\mathrm{■}$

  Group 4 has worked on integral distinguishers on big finite fields. After looking at different topics, this group focused in the following problem: can we find integral distinguishers from the knowledge of some properties of the univariate representation of a function $F:{𝔽}_{2^n}\to {𝔽}_{2^n}$? In other words, they wanted to find some coefficients $({\lambda }_0,\mathrm{\dots },{\lambda }_{2^n-1})$ in ${𝔽}_{2^n}$ such that $\forall x,{\sum }_{i=0}^{2^n-1}{\lambda }_{i}F({\alpha }^{i}X)=0$. In the particular case where all ${\lambda }_i\in {𝔽}_{2^n}$, this corresponds to finding sets of inputs such that the corresponding outputs sum to zero. They proved that ${\sum }_{i=0}^{2^n-1}{\lambda }_{i}F({\alpha }^{i}X)$ does not contain any term of degree $\mathrm{\ell }$ if and only if $A_{\mathrm{\ell }}=0$ or $P({\alpha }^{\mathrm{\ell }})=0$ where $F(X)={\sum }_{i=0}^{2^n-1}{A}_i{X}^i=0$. Therefore, they aimed at finding polynomials $P$ which vanish on all ${\alpha }^{\mathrm{\ell }}$ when $i$ varies in a given set, and which have the smallest possible number of terms. Indeed, the number of terms of $P$ is the data complexity of the distinguisher. When the only information we have on $F$ is that $A_i=0$ for all $i$ of weight $\ge d$, then the polynomial $P$ with binary coefficients and with the smallest weight corresponds to the usual distinguisher obtained with higher-order differentials, i.e., $\mathrm{𝑟𝑜𝑡}(P)=2^d$. However, if we have more information on $A_i$, then we can obtain distinguishers with lower data complexity than expected.

• $\mathrm{■}$

  Group 5 looked at a few different topics, quite unrelated to each other. One of them was how to sample binary words of fixed weight (say $200$) and length (say $40000$) efficiently and in “cryptographic constant time”. A possible approach is to use format-preserving encryption, but this turns out to be quite slow compared to alternatives. They eventually slightly revisited an existing method that oversamples $w^{\prime }$ indices uniformly and independently such that at least $w$ of them are unique with high probability, by proposing a possibly novel and simple constant-time algorithm to extract such a subset of $w$ indices uniformly: write a list $(v_i,i)$ of the $w^{\prime }$ samples; sort with respect to $v_i$, mark any duplicate by setting $i$ to infinity; sort with respect to $i$ and keep the $w$ first entries.

  Another topic was the study of the exact differential probability of $1/4$ round of Salsa, or rather computing exactly the probability of any $1/4$ round differential. A “promising” approach would be to use finite automata to parameterize the space of solutions to part of a round, and then iteratively propagate this through the successive steps thereof. They have not implemented this, but one could in principle at least partially rely on some existing tools for the first part. Whether the parameterization would be sufficiently compact to also allow an efficient propagation is not clear yet.

A central problem in cryptanalysis is to find all the significant deviations from randomness in a given $n$-bit cryptographic primitive. When $n$ is small (e.g., an $8$-bit S-box), this is easy to do, but for large $n$, the only practical way to find such statistical properties was to exploit the internal structure of the primitive and to speed up the search with a variety of heuristic rules of thumb. However, such bottom-up techniques can miss many properties, especially in cryptosystems which are designed to have hidden trapdoors.

In this paper we consider the top-down version of the problem in which the cryptographic primitive is given as a structureless black box, and reduce the complexity of the best known techniques for finding all its significant differential and linear properties by a large factor of $2^{n/2}$. Our main new tool is the idea of using surrogate differentiation. In the context of finding differential properties, it enables us to simultaneously find information about all the differentials of the form $f(x)\oplus f(x\oplus \alpha )$ in all possible directions $\alpha$ by differentiating $f$ in a single arbitrarily chosen direction $\gamma$ (which is unrelated to the $\alpha$’s). In the context of finding linear properties, surrogate differentiation can be combined in a highly effective way with the Fast Fourier Transform. For $64$-bit cryptographic primitives, this technique makes it possible to automatically find in about $2^{64}$ time all their differentials with probability $p\ge 2^{-32}$ and all their linear approximations with bias $|p|\ge 2^{-16}$; previous algorithms for these problems required at least $2^{96}$ time. Similar techniques can be used to significantly improve the best known time complexities of finding related key differentials, second-order differentials, and boomerangsa In addition, we show how to run variants of these algorithms which require no memory, and how to detect such statistical properties even in trapdoored cryptosystems whose designers specifically try to evade our techniques.

The Crypto Publication Review Board was established by NIST to identify cryptography standards and other publications to be reviewed. Currently, the NIST-recommended modes of operation (NIST SP 800-38 Series) are undergoing review.

At this time of writing, the Crypto Publication Review Project website (https://csrc.nist.gov/Projects/crypto-publication-review-project) lists the following modes of operation as subject to review: SP 800-38A (ECB, CBC, CFB, OFB, CTR), SP 800-38A Addendum (three ciphertext stealing variants for CBC), SP 800-38D (GCM and GMAC), and SP 800-38E (XTS).

In this presentation, we gave a technical overview of the NIST-recommended modes of operation, giving insights into the functionality of the algorithms, and an overview of the public comments received.

Less than two weeks before the presentation, NIST had made an announcement related to the review of these modes of operation. This gave an opportunity to provide a status update, and to collect feedback for NIST from the attendees of this talk at the Dagstuhl Symmetric Cryptography Seminar.

Meet-in-the-middle (MITM) is a general paradigm where internal states are computed along two independent paths (“forwards” and “backwards”) that are then matched. Over time, MITM attacks improved using more refined techniques and exploiting additional freedoms and structure, which makes it more involved to find and optimize such attacks. This has led to the use of detailed attack models for generic solvers to automatically search for improved attacks, notably a MILP model developed by Bao et al. at EUROCRYPT 2021.

In this paper, we study a simpler MILP modeling combining a greatly reduced attack representation as input to the generic solver, together with a theoretical analysis that, for any solution, proves the existence and complexity of a detailed attack. This modeling allows to find both classical and quantum attacks on a broad class of cryptographic permutations. First, Present-like constructions, with the permutations of the Spongent hash functions: we improve the MITM step in distinguishers by up to 3 rounds. Second, AES-like designs: despite being much simpler than Bao et al.’s, our model allows to recover the best previous results. The only limitation is that we do not use degrees of freedom from the key schedule. Third, we show that the model can be extended to target more permutations, like Feistel networks. In this context we give new Guess-and-determine attacks on reduced Simpira v2 and Sparkle. Finally, using our model, we find several new quantum preimage and pseudo-preimage attacks (e.g. Haraka v2, Simpira v2 … ) targeting the same number of rounds as the classical attacks.

This talk introduces and analyzes $\mathrm{𝖳𝗋𝗂𝗉𝗅𝖾𝗑}$, a leakage-resistant mode of operation based on Tweakable Block Ciphers (TBCs) with $2n$-bit tweaks. $\mathrm{𝖳𝗋𝗂𝗉𝗅𝖾𝗑}$ enjoys beyond-birthday ciphertext integrity in the presence of encryption and decryption leakage in a liberal model where all intermediate computations are leaked in full and only two TBC calls operating a long-term secret are protected with implementation-level countermeasures. It provides beyond-birthday confidentiality guarantees without leakage, and standard confidentiality guarantees with leakage for a single-pass mode embedding a re-keying process for the bulk of its computations (i.e., birthday confidentiality with encryption leakage under a bounded leakage assumption). $\mathrm{𝖳𝗋𝗂𝗉𝗅𝖾𝗑}$ improves leakage-resistant modes of operation relying on TBCs with $n$-bit tweaks when instantiated with large-tweak TBCs like Deoxys-TBC (a CAESAR competition laureate) or Skinny (used by the Romulus finalist of the NIST lightweight crypto competition). Its security guarantees are maintained in the multi-user setting.

In Salsa20, one round consists of four parallel quarterround functions on independent inputs. These quarterround functions transform a 128–bit by adding two 32–bit inputs (modulo $2^{32}$), rotating the output over a fixed amount of bits and XORing it with a third 32–bit input. This operation is performed four times within a quarterround.

It seems to be an open problem to compute the exact differential probability for one quarterround of Salsa20. It has been shown that theoretical estimates of the probability may not correspond to estimates obtained by experimental verification [1, 2].

The goal of this research group was to explore some methods to calculate the exact differential probability for one quarterround of Salsa20, and confirm these with experiments on a small-scale variant of Salsa20. Because the four quarterround functions are independent of each other, a method to determine the exact differential probability for one quarterround, would also lead to a result for one round of Salsa20.

We explored the problem from both a theoretical and experimental point of view, and arrived at various new insights that will be helpful to find an elegant and efficient solution to this problem.