Orr Dunkelman
email: orrd@cs.haifa.ac.il

Léo Perrin
email: leo.perrin@inria.fr

Adapting Rigidity to Symmetric Cryptography: Towards "Unswerving" Designs *

Keywords: Cryptography, Rigidity, Kleptography, Unswervingness

While designers of cryptographic algorithms are rarely considered as potential adversaries, past examples, such as the standardization of the Dual EC PRNG highlights that the story might be more complicated. To prevent the existence of backdoors, the concept of rigidity was introduced in the specific context of curve generation. The idea is to first state a strict scope statement for the properties that the curve needs to have and then pick e.g. the one with the smallest parameters. The aim is to ensure that the designers did not have the degrees of freedom that allows the addition of a trapdoor. In this paper, we apply this approach to symmetric algorithms. The task is challenging because the corresponding primitives are more complex: they consist of several subcomponents of different types, and the properties required by these sub-components to achieve the desired security level are not as clearly defined. Furthermore, security often comes in this case from the interplay between these components rather than from their individual properties. In this paper, we argue that it is nevertheless necessary to demand that symmetric algorithms have a similar but, due to their different nature, more complex property which we call "unswervingness". We motivate this need via a study of the literature on symmetric "kleptography" and via the study of some real-world standards. We then suggest some guidelines that could be used to leverage the unswervingness of a symmetric algorithm to standardize a highly trusted and equally safe variant of it.

Introduction

Information needs to be protected. To this end, cryptographic protocols are used to ensure that it cannot be accessed by anyone but its intended recipient, and that it cannot be tempered with. Said protocols rely on lower level algorithms called primitives. These can be seen as the elementary bricks that must be used to construct secure protocols.

Primitives can be sorted into two broad categories. The first contains public key algorithms that rely on pairs of keys to provide their functionalities. In this case, a single key is intended to be broadcast (the public key) and one must be kept secret lest the whole security collapses (the private key). The second category contains algorithms that use only one key (the secret key) which must not be disclosed. They are called symmetric.

In this paper, we focus on symmetric primitives. They can be of several types.

Block Cipher.

A block cipher is a family E κ of permutations of {0, 1} n that is indexed by a key κ of {0, 1} k . It should not be possible to recover κ, even if multiple pairs (x, E κ (x)) are known. Encryption is but one of its many possible use: all other symmetric primitives can be built starting from a block cipher. Prominent examples include the now deprecated DES [START_REF]Data encryption standard[END_REF] and its very widely used successor, the AES [START_REF]Advanced Encryption Standard (AES)[END_REF].

Permutation. More recently, permutations have been introduced as an alternative elementary primitive to use instead of block cipher. These are simply bijective functions mapping {0, 1} n to itself. A permutation is for example at the core of the sponge structure used by the latest standard hash function SHA-3 [START_REF]Sha-3 standard: Permutation-based hash and extendable-output function[END_REF].

Stream Cipher. A stream cipher uses a key and (possibly) an initialization vector to produce a keystream of arbitrary length. This long bitstring is usually XORed with the plaintext to obtain the ciphertext. Stream ciphers, like for instance Trivium [De 06], are often intended for resource constrained devices. Another widely used example is the software oriented ChaCha20 [START_REF] Daniel | Chacha, a variant of salsa20[END_REF].

Hash Function. A hash function H maps the space of all bitstrings to {0, 1} d . Its output is a digest and d is its bitlength. Such a function needs to have several properties, including collision resistance (it is impossible in practice to find x, y such that H(x) = H(y)) and preimage resistance (given z ∈ {0, 1} d , it is impossible in practice to find x such that H(x) = z). For example, SHA-2 [START_REF]Secure hash standard (shs)[END_REF] is a commonly used hash function.

MAC. Message Authentication

Codes are functions F κ mapping all bitstrings to {0, 1} d that are parameterized by a key κ ∈ {0, 1} k . When receiving a message m||F κ (m), the recipient can compute F κ (m) and see if the value obtained is the same as in what they receive. It ensures that the message was not tempered with and was indeed sent by someone who knows κ. For example, the HMAC [START_REF] Krawczyk | HMAC: Keyed-hashing for message authentication[END_REF] construction constructs a MAC from a hash function.

Regardless of the details of their inner workings, the primitives must satisfy specific requirements in order for the protocols using them to be secure. For example, it must be impossible to deduce a private key from its corresponding public key. Protocol designers then assume that these properties are satisfied, and use them to argue about the security of their constructions.

A primitive can however fail to have the properties expected from it. For example, the hash function SHA-1 [Nat95] recently had its collision resistance disproved [SBK + 17]. As collision resistance is a crucial property for a cryptographic hash function, it proves that this primitive is not fit for its purpose. More generally, primitives are the subject of an intense scrutiny from the cryptographic community to ensure that they remain capable of withstanding all the attacks currently known.

This analysis builds upon the information provided by the designers of the primitive. What was the exact scope statement they followed? What trade-offs did they make? Is it possible that they underestimated a specific threat? Did they build counter-measures against a particular form of attack into their algorithm? It is expected that the designers answer these questions in the document specifying their primitive. The absence of such justifications significantly complicates the task of the cryptanalysts as they have for example to try and guess how the primitive prevents known attacks.

Unfortunately, it is not uncommon for primitives to be published without such explanations. In fact, several have been standardized by both national and international standardization bodies such as the SHA-1 [Nat95] hash function, the Dual EC pseudorandom number generator, or the Kuznyechik [START_REF]security: Block ciphers[END_REF] block cipher. Worse: as we will see below, the design explanations are not only necessary to ease a third party analysis, they are the only protection that exists against malicious designers.

Kleptography

Primitive designers are rarely assumed to be malevolent. The purpose of the third party analysis of a primitive is to verify that no mistakes were made, not to check the intentions of its designers.

Nevertheless, this assumption may be too optimistic. At Eurocrypt'97, Young and Yung [START_REF] Young | Kleptography: Using cryptography against cryptography[END_REF] built upon previous work on subliminal channels [START_REF] Simmons | The prisoners' problem and the subliminal channel[END_REF] to introduce the concept of kleptography which they defined as "the study of stealing information securely and subliminally" in the specific context of cryptography.1 It considers a specific adversary, namely the kleptographic attacker, who "can steal the secrets securely, and in an exclusive and subliminal manner". In this context, the adversary designs an encryption scheme which is then made available as a black box for others to use. Said black-box implements added functionalities beyond the mere encryption of the plaintext that allow the kleptographic adversary to figure out the secret/private key of the user by observing some of its outputs. In other words, the kleptographic adversary tries to build a black-box containing a backdoor.

In the original paper [START_REF] Young | Kleptography: Using cryptography against cryptography[END_REF] and later in [START_REF] Young | A space efficient backdoor in RSA and its applications[END_REF], the authors focused on public key primitive. However, they considered block ciphers as well in [START_REF] Young | A subliminal channel in secret block ciphers[END_REF]. In fact, over the years, multiple constructions of backdoored symmetric primitives have been proposed, so much so that all primitives are now covered.

• For block ciphers, a variant of the DES [START_REF] Kenneth | Imprimitive permutation groups and trapdoors in iterated block ciphers[END_REF] and an AES-like block cipher called BEA-1 [START_REF] Bannier | Partition-based trapdoor ciphers[END_REF] have been constructed so as to contain a backdoor. We discuss them (and others) in more details in Section 4.1.1.

• For permutations, a significantly weakened version of SHA-3 was proposed by Morawiecki in [START_REF] Morawiecki | Malicious Keccak[END_REF] (see Section 4.1.2).

• • For hash function, on top of Morawiecki's proposal, backdoored variants of SHA-1 and Streebog were presented respectively in [AAE + 14] and in [START_REF] Altawy | Watch your constants: Malicious streebog[END_REF]. They are also discussed in Section 4.1.2.

• The issue of backdooring MACs is studied in [START_REF] Fischlin | Backdoored Hash Functions: Immunizing HMAC and HKDF[END_REF], where the authors discuss the ability of backdooring hash functions. Then, using these backdoored hash functions, they construct a backdoored HMAC construction (among others).

In this paper, we focus on backdoors added at the primitive level. There are of course other means of purposefully weakening a cryptosystem. An extensive survey on the more general topic of surreptitiously subverting cryptography is [START_REF] Schneier | Surreptitiously weakening cryptographic systems[END_REF].

More precisely, our focus is on symmetric primitives. In order to exist, such a backdoor requires one of the following two situations to occur:

• either the weakness is such that that anyone could theoretically find it, but it is believed that such an occurrence will not happen because the public state of the art will not catch up to the analysis of the designer, or

• the primitive is, in fact, a public key cryptosystem.

Regardless, the insertion of such a backdoor would significantly constrain the design of the primitive.

Outline of our Contribution

Our first aim is to survey the literature on inserting backdoors in symmetric primitives. We narrow our scope down to the algorithms and their specification. In particular, we do not consider backdoors inserted in specific implementations using e.g. hardware trojans.

Building upon this knowledge, we then intend to provide a general framework to assess whether the designers of an algorithm could have introduced a flaw to their primitive. It is based on the new concept of moldability which takes inspiration from the rigidity that was introduced to provide similar guarantees for elliptic curves (a type of asymmetric primitive).

Outline. Section 2 describes the sub-components used to construct symmetric primitives and the design space of each of them. Section 3 presents the techniques that can be used to prevent well known attacks. In Section 4, we argue that rigidity is indeed needed even in the context of symmetric primitives, although it has some limitations in this context. Finally, we present in Section 5 a new notion, unswervingness. Related to rigidity, it emphasizes the importance of the design process over that of the specific primitive considered. Indeed, it would be harder to insert a backdoor in an explicit set of design requirements than in a fully specified algorithm. We use it as a basis for a possible improved standardization process.

The Sub-Components of a Symmetric Algorithm

In this section, we list the sub-components that are necessary for constructing a symmetric primitive as well as the properties they are expected to have. We will build upon this knowledge in Section 3 to describe how their properties can be used to prove that the primitive is safe from some attacks, and then in Section 4 to explain how specific subcomponent can allow the insertion of backdoors in a primitive.

A symmetric primitive is very often built like a block cipher. Hash function are either sponge-based or effectively use a block cipher in a specific mode to construct a compression function, which in turn is used to build the hash function. The same goes for MACs. Permutations are built using the same components and the same security arguments as block ciphers, although in their case the "key" is fixed.

Stream ciphers that are not block ciphers in counter mode tend to use different components. We discuss those separately in Section 2.7. We thus focus on block ciphers first.

Key Alternating Block Cipher

A block cipher is, formally, a family of permutations of {0, 1} n parameterized by a key which is an element of {0, 1} k . In this case, n is the block size and k is the key size. Both of these quantities matter from a security standpoint: if the key is too short then an exhaustive search becomes possible. On the other hand, if the block size is too small then attacks exploiting collisions in the output of the cipher can become practical. Such an attack was shown practical when n = 64 in [START_REF] Bhargavan | On the practical (in-)security of 64-bit block ciphers: Collision attacks on HTTP over TLS and OpenVPN[END_REF].

In practice, a block ciphers consists of the iteration of a simple function called the round function which is interleaved with key additions. This structure is represented Figure 1. The latter operations simply consists of XORing a round key into the encryption state. These round keys are derived from the master key using a key scheduling algorithm. Said algorithm can be trivial: if k = n then it can simply set K i = K ⊕ c i for some round constants c i . Such round constants can also be used in a more sophisticated way inside the key scheduling algorithm. We discuss their properties in Section 2.2.

Optional Key Scheduling Algorithm

K P = s 0 f s 1 . . . f s r s r+1 = C K0 K1 Kr-1 Kr
Figure 1: A key alternating block cipher: K is the master key, the K i are the round keys, and f is the round function.

The round function itself may have different overall structures: it can be a Substitution-Permutation Network (SPN), a Feistel network, or have a structure based on a logic gates. In the case of a Feistel network, an SPN is usually used as a subfunction. An SPN round consists in the application of a small non-linear function called S(ubstitution)-box in parallel over the state followed by a linear permutation applied on the full state that mixes the outputs of the different S-boxes. We then need simply to consider the components of an SPN (Sections 2.3 and 2.4 for the linear layer and the S-box, respectively) and the gate-based case (Section 2.5).

Round Constants

Formally, round constants are bit-strings that are XORed or added into either the key state or the cipher state and which are different in each round. Their role is to ensure that the encryption rounds are different from one another. For example, in the AES, round constants are XORed into the key state inside the key schedule.

In order to ensure that they are different in each round, it is popular to use a simple counter or the internal state of a small LFSR as a round constant (as done e.g. in the AES).

Another design strategy consists of simply choosing random bit-strings during the design phase and then hard-coding them into the implementation. This requires a good source of random bits (possibly, a verified and tested one).

Linear Layer

The purpose of the linear layer is to ensure that, eventually, all bits of the internal state depend on all the bits from the input and from the key. Since the S-box (see below) operates in parallel on different subsets of the state, it is insufficient to achieve this goal.

While this property (called diffusion by Shannon [START_REF] Shannon | Communication theory of secrecy systems[END_REF]) does not a priori impose that the component providing it is linear, it is almost always the case in practice because linear functions and their interaction with the S-box layer are easier to study. In fact, it is possible to formally quantify how much diffusion is provided by a linear layer using the so-called branching number. Let n = m be a block size and let m be the size of the S-box applied in parallel over the state. Then the branching number of a linear permutation

L : ({0, 1} m ) → ({0, 1} m ) in this context is min x =0 (wt(x) + wt (L(x))) ,
where wt(x) is the number of non-zero m-bit words in x ∈ ({0, 1} m ) . The higher the branching number, the better the diffusion provided by the linear layer. In the AES, a linear layer operating on a quarter of the state that has the maximum branching number is used. However, while a high branching number is a desirable property, it is not necessary for the cipher to be good. In particular, another popular choice of linear layer is a simple bit permutation-which always has the worse possible branching number: 2. It is for example how the linear layer of the lightweight block cipher PRESENT [BKL + 07] works.

S-Boxes

S-boxes are the only non-linear components of the ciphers using them. Formally, they are functions

S : {0, 1} m → {0, 1} n
where m is small enough that S can be described by its lookup table, i.e. by the sequence of n-bit values {S(0), ..., S(2 m -1)}. Typically, m = n ∈ {4, 8} but other possibilities exist, e.g. m = 6 and n = 4 for the DES. Informally, S-boxes are supposed to increase the complexity of the relation of the internal state bits with one another and with the key bits-a property called confusion by Shannon [START_REF] Shannon | Communication theory of secrecy systems[END_REF]. This complexity can be quantified in different ways that are each related to a proof of security against some attacks: the differential uniformity matters for differential attacks (see Sections 3.3), and the linearity is used in linear attacks (see Section 3.4). Overall, the mathematical properties of the S-box play a crucial role in the security of the cipher.

Another important aspect to take into account when choosing an S-box is its implementation efficiency. It can be implemented with a simple table lookup, but this technique is not well-suited for a hardware implementation and it can lead to timing attacks when used in software. S-boxes are then chosen that have a specific structure to ensure the possibility of an efficient and secure implementation. For example, the S-box of PRESENT was chosen so as to minimize the number of gates needed to implement it in hardware. Similarly, the S-boxes of the block cipher SERPENT [START_REF] Biham | Serpent: A new block cipher proposal[END_REF] were chosen so as to minimize the number of instructions needed to implement them in a bit-sliced fashion. Finally, the S-box of Keccak [START_REF] Bertoni | Keccak[END_REF] (which became SHA-3) is implemented via a simple cellular automata which implies the existence of efficient software and hardware implementations.

A wide variety of design choices are possible, as illustrated in Figure 2. It shows the structures used to build the 8-bit S-boxes of 53 different algorithms from the literature. "AES S-box", "Inverse", "Exponential", and "Math (other)" correspond to structures obtained via simple mathematical formulas, usually over the finite field. SPN, Misty, Feistel and Lai-Massey correspond to block cipher-like structures, Misty and Lai-Massey being closely related to the Feistel network. The last three categories correspond to structures that do not yield any simple description.

The last category corresponds to S-boxes whose design structure was not disclosed by its authors.

Gate-Based Operations

There are ciphers with round functions that do not really correspond to the SPN or Feistel structure (or any of their variants). Instead, they are described as a network of various gates taking one or several w-bit words as input and outputting one such word. A popular choice in this case is for the designers to restrict themselves to gates corresponding to addition modulo 2 w , w-bit word rotations and w-bit XOR for w ∈ {8, 16, 32, 64}. The resulting design paradigm is nicknamed ARX (Addition, Rotation, XOR). For example, the stream cipher ChaCha20 [START_REF] Daniel | Chacha, a variant of salsa20[END_REF] is built in this fashion. The choice of the gates can be less restricted, such as in SHA-256 where the ARX gates are supplemented with the bitwise AND and OR of two 32-bit words.

The boundary between gate-based and SPN can be blurry. Indeed, the round function of Keccak is an SPN round with a 5-bit S-box but it can be completely specified in a gate-based fashion. Similarly, the block cipher SPARX [DPU + 16] is an ARX-based SPN. On the other hand, an algorithm like SIMON [BSS + 13] that relies on AND, rotations and XORs does not have any component with a clear SPN structure.

Key Schedule

Most of the block ciphers transform a single key into multiple subkeys using a key schedule algorithm (a few others just repeat the key words, possibly in a different order). Some key schedules are linear (either by picking different bits for different rounds as in DES [START_REF]Data encryption standard[END_REF] or IDEA [START_REF] Lai | A proposal for a new block encryption standard[END_REF], or by using an LFSR as in KATAN [START_REF] De Cannière | KATAN and KTANTAN -a family of small and efficient hardware-oriented block ciphers[END_REF]), but some others employ nonlinear components in it, either the use of ARX operations or the use of S-boxes. This is done mainly to avoid related-key attacks (and its variants, such as slide attacks or reflection attacks). Finally, some primitives such as blowfish [START_REF] Schneier | Description of a new variable-length key, 64-bit block cipher (Blowfish)[END_REF] derive the S-boxes from the key (in what is called key-dependent S-boxes).

While there may be some keys for which the encryption is weaker (or even broken), it is unknown whether there is a general method to inject weaknesses (besides those that can be easily identified) into the key schedule.

Open Problem 1. Is it possible to insert an undetectable backdoor through the key schedule algorithm?

Stream Cipher Components

Stream ciphers can be built using a block cipher-based function, i.e. using a hash function with a counter and a key as its input (as in ChaCha20 [START_REF] Daniel | Chacha, a variant of salsa20[END_REF]) or using a plain block cipher in counter mode.

However, it is common to use dedicated structures that rely on Linear Feedback Shift Registers (LFSR), Non Linear Feedback Shift Registers (NLFSR) and Boolean functions mapping {0, 1} w to {0, 1} instead. Software-oriented stream ciphers also use large arrays which get continuously updated during the encryption process, like RC4. In this case, an internal state that depends only on the key (and possibly an initialization vector) is initialized and updated using such functions. Then, during the production of the keystream, a filter function is used to obtain a bit or a byte of keystream from the state which is updated each time.

Some standard stream cipher have a hybrid structure like SNOW 3G [START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms UEA2 & UIA2[END_REF] which uses both an LFSR and some components of the AES to update its internal state.

In the rest of this paper, we will set such stream cipher components aside because, to the best of our knowledge, how such components could be used to introduce backdoors has not received any attention from the community. This was a surprise to us as one of the most prominent cases of standardized backdoored algorithm is essentially a stream cipher, Dual EC. It should be noted however that it was built using components from public key cryptography (a very unusual choice) rather than the components listed above.2

Open Problem 2. Is it possible to insert a backdoor in an LFSR and NLFSR-based stream cipher?

A possible starting point starting point for this research direction could take inspiration from the A5/2 stream cipher which was successfully attacked for instance in [START_REF] Goldberg | The (Real-Time) Cryptanalysis of A5/2[END_REF]. Its structure allows a trivial guess and determine attack. Could this flaw be generalized?

Ensuring Security Against Known Attacks

Design Process

There are two main approaches for designing cryptographic primitives -the reductionist approach and the "engineering" approach. The reductionist approach is based on taking a well known hard problem (e.g., factoring or computing discrete logarithm), and using it to build a cryptosystem. Then, using standard reduction arguments (or sometimes, not so standard and very involved reduction arguments) it is possible to show that breaking the cryptosystem is as hard3 as solving the hard problem. This approach is very common in public-key cryptosystems as well as in designing modes of operation for block ciphers (where the security proof suggests that breaking the encryption scheme is as hard as breaking the block cipher).

The second approach, the "engineering" one, balances performance and security. In the case of symmetric-key primitives this means that some more basic round is designed (e.g., in block ciphers and hash functions). This round is then iterated as many times as needed to ensure security (measured by applying all known attacks, such as the ones discussed below) and as few times as possible to maintain acceptable performance. Hence, it is very important to make sure how many rounds can be attacked, and what are the security margins of the scheme.

(Lack of) Avalanche

The first class of attacks, first proposed by Diffie and Hellman, takes advantage of insufficient mixing between state (i.e. plaintext or intermediate encryption values) and key bits [START_REF] Diffie | Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard[END_REF]. Originally proposed against Double-DES, the meet in the middle attack tries to compute some internal value from both sides (plaintext and ciphertext). If a match is found, then further analysis is performed. Later, Chaum and Evertse showed how to use this attack in the context of attacking single-DES, by proposing the first attack faster than brute force against 7-round DES [START_REF] Chaum | Crytanalysis of DES with a reduced number of rounds: Sequences of linear factors in block ciphers[END_REF].

The underlying property is indeed the lack of mixing, or as commonly referred to, lack of avalanche. Hence, during the late 70's and the 80's, one important measure for discussing security of cryptographic schemes was the avalanche criteria [START_REF] Feistel | Cryptography and Computer Privacy[END_REF], later extended to the strict avalanche criteria [START_REF] Webster | On the design of S-boxes (impromptu talk)[END_REF].

In recent years a more subtle version of this property has been discovered and exploited to attack block ciphers -the (invariant) subspace attack [START_REF] Leander | A cryptanalysis of PRINTcipher: The invariant subspace attack[END_REF]. In this type of attacks, a structured subset of plaintexts is identified, such that the corresponding intermediate encryption values (or ciphertexts) belong also to a structured subset.

Differential Attacks

Differential cryptanalysis [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF] was published by Biham and Shamir in 1990. However, there is strong evidence that the NSA knew of the technique already in the 1970's, and that IBM's original cipher Lucifer [START_REF] Sorkin | Lucifer, a Cryptographic Algorithm[END_REF] was "updated" to DES [START_REF]Data encryption standard[END_REF], after the NSA revealed the technique to the designers of Lucifer/DES in IBM.

The technique itself studies the evolution of differences through the primitive, i.e., it studies two calls to the primitive, with some input difference (either in the plaintext or in the key), and studies the development of the differences through the rounds of the primitive. In block ciphers, differential cryptanalysis is built around finding a good differential characteristic, a prediction about the development of the differences throughout the encryption with as high probability as possible. This probability should differ from the probability of a similar transition from input difference to output difference for a random permutation (or an ideal cipher). Once this difference is high enough, one can collect plaintext pairs that satisfy the input difference, and check how many pairs that satisfy the differential characteristic exist in the dataset. Such pairs can later be used in attacks that recover the key. 4Differential cryptanalysis has been one of the two pillars of statistical cryptanalysis to this day, and thus, enjoys a great number of generalizations and extensions such as truncated differentials (working with sets of possible differences) [START_REF] Knudsen | Truncated and higher order differentials[END_REF], higher order differentials (working with sets, rather than pairs) [START_REF] Knudsen | Truncated and higher order differentials[END_REF], boomerang attacks [START_REF] Wagner | The boomerang attack[END_REF] (combining two different short differentials into an attack, rather than a long one), etc.

We note that differential cryptanalysis in the context of hash functions (which is mostly used for collision finding attacks) also aims for finding high probability differential characteristics that end in specific output differences, e.g., zero for collision. Yet, for hash functions the adversary has a greater control over the pairs that satisfy the characteristic, with an emphasis on techniques which are built on the ability to force some differences to evolve according to the adversary's gain using methods such as message modification.

To claim security against differential cryptanalysis it is very common to show that there are no "high probability" or impossible differentials. This is done by techniques based on Nyberg and Knudsen's seminal work on provable security against differential (and linear) cryptanalysis [START_REF] Nyberg | Provable security against a differential attack[END_REF], which is the base for the wide trail strategy famously used to design the AES [START_REF]Advanced Encryption Standard (AES)[END_REF]. It is based on combining an S-box S for which the equation S(x ⊕ a) ⊕ S(x) = b as a bounded number of solutions x with a linear layer that has a high branching number. It is then possible to prove bounds on the probability of differential characteristics.

One should be careful though-bounding the probability of a specific differential characteristic (or showing by various tools that no such differentials characteristic exist), does not guarantee that there are no high probability differentials. Still, it is the state of the art technique for proving resilience against differential attacks at the time of writing.

Linear Attacks

Linear cryptanalysis, proposed by Matsui [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF], is the second pillar of symmetric-key cryptanalysis. This attack is built upon finding linear approximations of the primitive, namely, a linear relation holding between the parity of some input and some output bits that has a probability which differs from the expected one (of 1/2). The attack offers a known plaintext attack of trying to assess whether the linear approximation holds or not (as a way to distinguish the primitive from an ideal one). Of course, using a linear distinguisher can also be used for key recovery attacks, and the best academic cryptanalytic result against DES is based on this technique.

A large volume of work deals with extensions and generalizations for linear cryptanalysis. Most notably, the use of multiple linear approximations simultaneously [START_REF] Hermelin | Multidimensional linear cryptanalysis of reduced round Serpent[END_REF], the use of zero-correlation approximations (for which the approximation holds with probability exactly 1/2) [START_REF] Bogdanov | Zero correlation linear cryptanalysis with reduced data complexity[END_REF], differential-linear cryptanalysis [START_REF] Langford | Differential-linear cryptanalysis[END_REF] which combined the two methods, or partitioning cryptanalysis [START_REF] Harpes | Partitioning cryptanalysis[END_REF].

Similarly to differential cryptanalysis, some techniques allow designers to claim that there are no good (high bias) linear approximations for algorithms. Again, the methodology proposed by [START_REF] Nyberg | Provable security against a differential attack[END_REF] (and the wide trail strategy) is to count the number of active S-boxes, and then obtain an upper bound on the bias of any linear approximation of the cipher. A linear layer with a high branching number allow a particularly simple argument in this case.

As with differential cryptanalysis this methodology may not work as expected due to the linear hull effect (multiple approximations sharing the input/output masks), and may not suggest security against multidimensional linear cryptanalysis.

Integral Attacks

A different type of statistical attacks is the "integral attack", which is also named square attack or saturation attack [START_REF] Daemen | The block cipher Square[END_REF][START_REF] Lucks | The saturation attack -a bait for Twofish[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF]. This type of attack is based on collecting a specially structured set of inputs (for example, a set composed of 256 plaintexts, all agreeing on all bytes but one, where the remaining byte takes all possible values). Somewhat related to higher-order differential cryptanalysis, the attack studies the propagation of some "labels" describing the set of plaintexts. Common labels include Constant (all intermediate encryption values in the set have the same value in a word), Active (all values of a word appear once in the intermediate encryption values of the set), Balanced (the XOR of all values of a word in the intermediate encryption values of the set is 0), or Even (each value that appears in the set is of an even multiplicity).

This type of attack is usually well suited for ciphers with "word"-oriented design (e.g., the AES, where a 4-round integral property is the base for many cryptanalytic results). One advantage of this approach is that as long as the S-box is bijective, the exact S-box does not affect the development of the integral.

In recent years this attack was extended to the division property (which can be roughly summed as "bit-oriented integral") [START_REF] Todo | Structural evaluation by generalized integral property[END_REF].

Algebraic Attacks

A completely different strand of cryptanalysis is based on algebraic attacks. Motivated by Shannon's quote that breaking a good cipher should require "as much work as solving a system of simultaneous equations in a large number of unknowns of a complex type" [START_REF] Shannon | Communication theory of secrecy systems[END_REF], this type of attacks tries to model the problem as a set of multivariate equations that need solving. For example, in the context of block ciphers, this involves writing the plaintext/ciphertext/key relations, and solving the equations for the key, whereas for hash functions this may include finding preimages or collisions.

Usually, algebraic attacks require very little data, but their running time is hard to predict. In many cases, the tools that solve the system of equations (be it Gröbner-basis solvers, SAT solvers, or MILP solvers) run for a long unpredictable periods of time, require a lot of memory, etc.

The common method to address security against this line of attacks is to argue that the degree of the polynomials or that the distribution of monomials (i.e., how many monomials of a certain degree exist in the compact description of the block cipher) obtained by the cryptosystem reaches the bounds expected for random permutations/functions (depending on the primitive). At the same time, one should be very careful with these kinds of "security guarantees" as there are many dependencies that may cause the scheme to have a lower degree than expected [START_REF] Boura | Higher-order differential properties of Keccak and Luffa[END_REF].

The Need for an Improved Rigidity

Rigidity was introduced in [START_REF] Bernstein | Safecurves: choosing safe curves for elliptic-curve cryptography[END_REF] in the context of the design of an elliptic curve cryptosystem, a type of asymmetric primitive. It is an improvement of the folklore notion of nothing-up-my-sleeve number. We rephrase this definition in a more general context as follows.

Definition 1 (Rigidity). The design space of a rigid algorithm is highly constrained so that only a few algorithms can satisfy all of its requirements.

In order to introduce a backdoor in an otherwise convincing algorithm, an attacker needs to use a design process that leaves enough degrees of freedom to choose subcomponents with the properties that their backdoor requires. The aim of a rigid design process is to take away this freedom by enforcing that the set of all possible algorithm is very small.

In this section, we argue that the problem solved by rigidity in the context of elliptic curves, namely the possibility of a backdoored algorithm, is very relevant for symmetric primitives as well. To this end, we provide an extensive survey of the literature on backdooring techniques in Section 4.1. We then look at two specific groups of algorithms and argue that they fail to meet the intuitive requirements for a trusted algorithm, namely the block ciphers SIMON and SPECK (Section 4.2) as well as Streebog and Kuznyechik (Section 4.3). We summarize the lessons learnt from these examples in Section 4.4.

Known Backdooring Techniques

Various building blocks used to construct symmetric algorithms can be used to insert backdoors. Below, we look at S-boxes and round constants. To the best of our knowledge, no method is known that relies on the properties of the linear layer.

S-box-based

It may seem counterintuitive to try and insert a backdoor through the S-box. Indeed, this component must satisfy a lot of properties that are easy to verify for a typical S-box size such a low linearity or a low differential uniformity which help prevent respectively differential attacks (see Sections 3.3) and linear attacks (see Section 3.4). Intuitively, these quantities measure how well the S-box mixes its input: how could an S-box satisfying such criteria yield a flaw? As we will see, this intuition is wrong.

The first backdoor proposed in the literature was based on a hidden flaw against linear attacks [START_REF] Rijmen | A family of trapdoor ciphers[END_REF]. In this case, the S-box had to be big enough that computing its linear approximation table was not feasible, meaning that the best linear approximation could not be found in reasonable time without knowledge of the backdoor. However, this approach was proved flawed in [START_REF] Wu | Cryptanalysis of Rijmen-Preneel trapdoor ciphers[END_REF]: the authors found a general algorithm capable of recovering such linear approximations.

Research then focused on constructing S-box-based backdoors that are of "regular" size. Since in this case the resilience against differential and linear attacks can be directly assessed, other attacks need to be considered. The first work in this direction was performed by Paterson in [START_REF] Kenneth | Imprimitive permutation groups and trapdoors in iterated block ciphers[END_REF]: he introduced a variant of the DES which essentially allowed partition attacks. Though this technique was introduced [START_REF] Harpes | Partitioning cryptanalysis[END_REF] just two years before the publication of [START_REF] Kenneth | Imprimitive permutation groups and trapdoors in iterated block ciphers[END_REF], the latter work actually predates it: it was finished already in 1994 but it remained unpublished for several years. Much later, in 2016, the backdooring strategy of Paterson was revisited by Bannier et al. [START_REF] Bannier | Partition-based trapdoor ciphers[END_REF]. They proved that, in order to introduce such a trapdoor, the S-box had to satisfy some very specific properties. Let S : F n 2 → F n 2 be the S-box: there must exist subspaces V and W of F n 2 such that for all a ∈ F n 2 there exists a b ∈ F n 2 such that S(a + V ) = b + W . In other words, it must map additive cosets of a subspace to additive cosets of a (possibly different) subspace. They also proved that such requirements were not at odds with having good differential and linear properties. They were then able to design a block cipher called BEA-1 which is proved secure against linear and differential attacks using a wide trail argument but which is also vulnerable to a devastating partition-like attack with practical complexity.

Another very recent approach does not consist of allowing partition attacks but rather differential attacks where the difference does not correspond to the XOR but to another group operation [START_REF] Civino | Differential attacks: using alternative operations[END_REF]. The trapdoor then consists in knowing this group operation.

Many standards have been published without a proper explanation for the design process of their S-box. These merely specify their S-box via their lookup table. While the process used was eventually disclosed or recovered in some cases, it often remains mysterious.

DES.

The DES [START_REF]Data encryption standard[END_REF] (standardized by the American NBS, the NIST ancestor) uses eight S-boxes mapping 6 bits to 4. They were studied shortly after their publication and several non-random patterns were identified [HMS + 76]. However, it was not before 1994 that the design criteria were published by one of the authors of the DES [START_REF] Coppersmith | The data encryption standard (DES) and its strength against attacks[END_REF]. It is now deprecated unless used 3 times in sequence (triple-DES).

Streebog/Kuznyechik. Streebog [START_REF]security: Hash function[END_REF] and Kuznyechik [START_REF]security: Block ciphers[END_REF] are two algorithms that are standardized in Russia as GOST standards. They share the same 8-bit S-box which has been the subject of an intense scrutiny that eventually lead to the recovery of its structure. We provide more details in Section 4.3.

Skipjack. Skipjack [U.S98

] was an American NIST standard block cipher originally intended for use in the Clipper chip. It uses an 8-bit S-box for which the design process remains mysterious, although some advances on analyzing it were made in [START_REF] Biryukov | On reverse-engineering S-boxes with hidden design criteria or structure[END_REF].

It is now deprecated.

TIA ciphersuite. The ciphersuite used by the north American standards for cell phone communication relies on two 8-bit S-boxes that were never explained [START_REF] Quick | Common cryptographic algorithms[END_REF]. CMEA is a block cipher that uses an 8-bit S-box called the "CaveTable" which was successfully attacked in [START_REF] Wagner | Cryptanalysis of the cellular encryption algorithm[END_REF]. The CaveTable is also used by a key derivation function called Cave. Another unexplained 8-bit S-box called "ibox" is used by the "Enhanced CMEA" (ECMEA).

SM4.

The current standard block cipher in China is SM4 [START_REF] Diffie | SMS4 encryption algorithm for wireless networks[END_REF]. It was shown in [LJH + 07] that its S-box, though originally unexplained, had simply been constructed like that of the AES.

Round Constant-based

While S-boxes have been considered for backdooring block ciphers, modifications of the round constants have been shown to allow efficient attacks against hash function. Most prominently, it was shown by Albertini et al. that the constants of the hash function SHA-1 could be modified to allow collision attacks [AAE + 14]. More precisely, they showed that the constants could be chosen during a first collision search so as to speed it up. Furthermore, their constant choice was plausible, i.e. they left the message expansion unchanged instead of requiring the use of independent round constants in each round. The resulting design is a hash function as convincing as SHA-1-except that its designers know a collision. Due to the Merkle-Damgård construction of SHA-1, this first collision can be used to build many others. Later, variants of the standards Keccak and Streebog were proposed. For Keccak, Morawiecki proposed in 2015 [START_REF] Morawiecki | Malicious Keccak[END_REF] to use round constants generated in a simple way using the string "SHA3SHA3" as a seed. The fact that the corresponding 64-bit string is symmetric means that strong symmetries are preserved throughout the whole hashing. This in turn allows a collision search in time 2 d/4 where d is the digest size, while a hash function is expected to require 2 d/2 operations to solve this problem.

For Streebog, AlTawy and Youssef [START_REF] Altawy | Watch your constants: Malicious streebog[END_REF] obtained similar results as those obtained in [AAE + 14] for SHA-1. During the design phase, they chose the constant so as to allow a specific collision. Then, using the Merkle-Damgård structure of Streebog, they can use it to construct more collisions. In the case of Streebog, their search was helped by the lack of constant schedule. Indeed, unlike in SHA-1, the round constants are independent and specified separately which gives the attacker much more freedom. After the publication of [START_REF] Altawy | Watch your constants: Malicious streebog[END_REF], the authors of Streebog published a note explaining their design choice [START_REF] Rudskoy | Note on Streebog constants origin[END_REF].

SIMON and SPECK

SIMON and SPECK [BSS + 13] are two families of lightweight block ciphers designed by the NSA in 2013. Both families target low-end devices, the SIMON family follows a relatively standard Feistel construction using an unusual gate-based round function, whereas the SPECK family uses the ARX paradigm.

The original design document [BSS + 13] lists the different variants (each family supports different block and key sizes) and offers performance information on different platforms, but suggests no design rationale or criteria.

Despite that, SIMON and SPECK were submitted to standardization in ISO5 in October 2014.6 However, besides the design document, ISO has not received any design rationale nor any additional information that could attest to the cryptographic strength of the algorithms. This is despite the fact that, as NSA designed cryptosystems (and especially after the revelation of the Bullrun program), they received a great deal of cryptanalytic attention-mostly for the small block size variants.

The submission of SIMON and SPECK for standardization despite the big security concerns has caused a great deal of backlash. Since the beginning, different concerns with respect to the ill understood security of SIMON and SPECK were raised by members of SC27.7 For example, when Belgium raised concerns in the preparations to the Jaipur meeting (October 2015), the NSA contacted the scientists behind the claims, and asked them to change their conclusion [START_REF] Ashur | NSA-designed Cipher in the Post-snowden World[END_REF].

Given the pressure to explain the design decisions, as some of them are slightly unorthodox (for example, in SIMON, the key addition is performed at the end of the round, and thus, the first round is essentially moot from security point of view), the opposition to standardization was very fierce. Moreover, the discussion about the smaller block sizes (most notably, 32-bit and 48-bit block sizes) in the face of the Sweet32 attack [START_REF] Bhargavan | On the practical (in-)security of 64-bit block ciphers: Collision attacks on HTTP over TLS and OpenVPN[END_REF], led the NSA to first withdraw their support for the smaller block sizes.

To support the cause of the bigger block sizes, the NSA released a document in 2017 listing the design rationale [BSS + 17] and a few design choices. For example, the report discusses the choice of the rotation constants used in SIMON, suggesting that they are not optimal w.r.t. security, but almost optimal, in exchange for a significantly better performance on 8-bit microcontrollers. However, the amount of security lost by the transition is not mentioned (i.e., it is unclear how many more rounds can be attacked following the slightly sub-optimal choice of constants).

Another missing element from the design rationale document is the designers' analysis. While the report discusses the resistance of the ciphers to various attacks, it does not explicitly mention the amount of rounds that the designers could break using the different techniques, bur just summarizing existing works. Hence, one cannot evaluate the design strategy, as it is unclear whether all the results obtained by the academic community invalidate the design methodology or the internal security claims. Moreover, as the design rationale was published after many such papers, it is impossible to figure out whether the attacks found by academics simply mirror those originally found by the designers or if they in fact outperform them.

Finally, one of the most lacking feature of the design rationale document is a complete lack of claims regarding the safety margins offered by the different algorithms. We remind the reader that most block ciphers try to balance between security and performance, and one important aspect of this tradeoff is the understanding of the safety margins-what is the performance penalty that the designer picked to counter future advances in cryptanalysis. While [BSS + 17] contains some text on the matter of these safety margins, the text is far from being clear, and a straightforward reading of the text suggests that for some SIMON variants, the safety margins are smaller than the designers intended [START_REF] Ashur | Notes on "Notes on the design and analysis of SIMON and SPECK" and an Analysis of it[END_REF].

Following the above issues, SIMON and SPECK were not standardized into the security and cryptography standards of ISO. At the same time, due to the distributed nature of ISO, some other subcommittees (specifically, SC31 which deals with RFID communication), did decide to include SIMON and SPECK into their standards despite the fact that the cryptography and security experts of SC27 voted in a landslide against the standardization of SIMON and SPECK.

The Russian S-box

In 2012, the Russian Federation standardized a new hash function called Streebog [START_REF]security: Hash function[END_REF]. It was followed in 2015 by a new block cipher, Kuznyechik [START_REF]security: Block ciphers[END_REF]. In parallel, these were both standardized as IETF RFC via the independent stream in 2013 (as RFC 6986) and 2016 (as RFC 7801) respectively. Streebog has also been an ISO standard since 2018 and Kuznyechik is being considered for standardization at the time of writing. Both use the same S-box nicknamed "π" which permutes the set {0, 1} 8 . In both specification, it is only described by its lookup table .  It was first studied by Biryukov, Perrin and Udovenko in [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF] where the authors managed to identify a yet unknown structure inside π, meaning that there was an algorithm capable of evaluating π that required less information than is contained in its lookup table. In a follow-up work [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF], Perrin and Udovenko found a completely different structure in π which prompted them to conjecture the existence of a third structure. The structures described in [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF] and in [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF] would then simply be side effects of this third one.

It turned out to be correct: in [START_REF] Perrin | Partitions in the S-box of Streebog and Kuznyechik[END_REF], Perrin showed that π could be written using very simple equations over the finite field. He also proved the previous structures from [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF] and [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF] were indeed mere side-effects of the last one. More importantly, he could use this structure to identify a highly structured and previously unknown interaction between π and particular vector spaces of {0, 1} 8 , namely the multiplicative and additive cosets of the subfield. This discovery is worrying because, as recalled in Section 4.1.1, an S-box interacting in a non-trivial way with additive cosets of a vector space is a known backdooring technique.

The situation of π cannot be fully understood using only the framework of rigidity. Indeed, while it appeared at first to have no rigidity, it turned out in the end to come from a very small set of permutation, meaning that it is in fact a very rigid component. Surprisingly, its designers claimed that the rigidity of their design which was outlined by the first two structures found in π was a coincidence. This is evidenced by an internal ISO memo that was eventually leaked [START_REF] Shishkin | A Memo on Kuznyechik S-Box[END_REF]. Astonishingly, they maintained this claim after the third structure was published, as can be seen in the leaked summary of the discussion that took place after the publication of this result [START_REF] Yoshida | Meeting report for the discussion on Kuznyechik and Streebog[END_REF]. Bonnetain et al. then proved that the arguments of the designers were factually incorrect [START_REF] Bonnetain | Anomalies and vector space search: Tools for S-box reverse-engineering[END_REF], as the probability for an S-box to satisfy such properties is very small.

Lessons Learnt

As evidenced by the literature on backdooring techniques, the threat posed by a malevolent designer is as relevant in the case of symmetric cryptography as in the case of asymmetric cryptography. We therefore need a notion close to that of rigidity: it is necessary to ensure that the subcomponents of an algorithm do not allow secret attacks.

At the same time, as recalled in Section 2, a symmetric primitive consists of more subcomponents than, say, an elliptic curve. Furthermore, we should be careful that the requirements preventing the insertion of a backdoor do not needlessly hamper the task of the designers. They need to be able to perform all the trade-offs necessary, and they also need to be able to choose some of the subcomponents depending on some of the properties of the others. As a consequence, we should not simply use the notion of rigidity directly in symmetric cryptography by defining the rigidity of an algorithm as the rigidity of each of its subcomponents taken independently.

Furthermore, the examples of the Russian algorithms (Section 4.3) and of the NSA lightweight blockciphers (Section 4.2) highlight the crucial importance of the specification and of a proper statement of the design requirements. It also shows that the publication of such a rationale must be done before any external cryptanalysis has taken place.

If the rationale is not published, an algorithm cannot be trusted. In the case of the Russian ciphers, it is even worse as all the evidence points to the design requirements provided being purposefully misleading.

Building upon these remarks, we propose a variant of rigidity that is better suited for symmetric primitives in the next section.

5 Unswervingness: a Better Rigidity for Symmetric Primitives

Definition

In light of the discussion in the previous paragraph, we propose the following notion.

Definition 2 (Moldability and Unswervingness). The design requirements of an algorithm are moldable if there exists a weak algorithm that fits all of its explicit design requirements (including those regarding its efficiency). The opposite of moldability is unswervingness.

The main difference with rigidity is that unswervingness does not put the emphasize on the size of the set of the algorithm fitting all the design requirements-although we expect that it significantly reduces it (see below). Instead, it demands that no weak algorithm exist in this set.

An unswerving set of requirement does not exist for all algorithms, e.g. if all the components are picked randomly in an unreproduceable way. In this case, it is fair to say that the algorithm itself is moldable.

We have explicitly mentioned efficiency requirements as being part of the definition of moldability. Indeed, it is common to for example list specific cryptographic design criteria for an S-box and then to choose the one with the best implementation properties from the corresponding set.

Moldability can also be used to better understand some results from the literature. For example, in [START_REF] Knudsen | On noekeon[END_REF], Knudsen and Raddum showed the requirements presented by the designers of the block cipher Noekeon were satisfied by S-boxes that yielded a weak cipher. What they showed is not an attack against this algorithm. Instead, they have proved that the specification of Noekeon was moldable.

We claim that unswervingness is a highly desirable property for the design requirements of an algorithm. Some techniques for preventing the exploitation of backdoors in some specific constructions have been proposed e.g. for HMAC and HKDF [START_REF] Fischlin | Backdoored Hash Functions: Immunizing HMAC and HKDF[END_REF]. Unswervingness is more general as it can be applied to any primitive.

A Solution to Known Problems

As discussed in Section 4, the designer of a symmetric cryptographic primitive can be an adversary. Imposing that all standardized designs have unswerving requirements would significantly cripple the capability of a malevolent designer in several ways. 1. Obviously, imposing that no algorithm vulnerable to known attack satisfies the design requirements of a given cipher imposes that said cipher is safe from said attacks.

2. An algorithm for which no design requirements are published is extremely moldable as for example its non-linear components could be replaced by linear ones, or its diffusion layers could be substituted with the identity, leading in both cases to an extremely weak cipher satisfying all the (non-existent) design requirements. As a consequence, algorithms like SIMON/SPECK or the Russian ciphers (discussed in Sections 4.2 and 4.3 respectively) have maximum moldability.

3. An unswerving set of design requirements has to be thorough, meaning that it forces a form of rigidity. Indeed, it imposes that the algorithm lives in a small set (that of the a priori secure ones).

4. As moldability is a property of the design requirements rather than of the algorithm or its subcomponents, algorithms with a rigid but secret design process (as was used for the design of the Russian S-box as explained in Section 4.3) cannot have unswerving design requirements.

5. The concepts moldability and unswervingness can be used as the foundation of a specific standardization process which we describe below in Section 5.3.

At the same time, the notion of unswervingness is flexible enough to allow the designers to make all kinds of tradeoffs and design decisions. Perhaps the S-box can be chosen somewhat freely but, once it is fixed, the linear layer is fully defined. In this case, we cannot really say that the choice of each subcomponent is rigid since their might be many valid S-box/linear layer pairs. However, it is unswerving.

Possible Directions for better Standardization Processes

We propose the following standardization process which has its roots in the concept of unswervingness. It also takes inspiration from the process used by the designers of the million dollar curve [BDF + 16].

Suppose that, after a substantial cryptanalysis effort, a specific algorithm has gained the trust of the cryptographic community. It is then decided to standardize it. During the analysis phase, cryptographers considered not only the algorithm itself but all those satisfying all of its design requirements. In light of this, the standardizing agency could operate as follows.

1. Commit to the standardization of a variant of the algorithm.

2. Publicly commit to a component generation process such that its output will satisfy all the (appropriately unswerving) design requirements.

3. Gather entropy in a publicly verifiable way to seed the generation process.

4. Modify the algorithm to use the newly designed components.

Standardize the result.

This process has several advantages. First, imposing unswervingness means in practice forcing the designers to clearly state all their design criteria. This will ease the task of third party cryptographers analyzing the security of the algorithm.

Its main feature however is the prevention of backdoors. Indeed, in order to ensure the presence of the mathematical properties required by a backdoor, a malevolent designer would need to state these requirements explicitly-a disclosure which would substantially simplify the identification of the backdoor by third party cryptographers.

Nevertheless, this process has its caveats. The main one we see is that multiple standardizing bodies may agree on the same algorithm: for example, the AES is both a NIST and an ISO standard (among others). If each body were to pick new components then their standards would not be interoperable. Still, this problem is easily solved: once a set of components outside of the control of the designers has been chosen, other standardizing bodies can simply reuse them.

Another possible problem is the huge computational cost of selecting and analyzing said components. It is unclear whether different standardization bodies have the same capabilities (both in computation and/or in the expertise of writing the required search procedures). A partial solution to that problem is to allow designers to offer several options for each sub-component, e.g., a few S-boxes or a few MDS matrices. Then, the task of selecting the exact combination may be easier.

Conclusion

In light of our survey of the literature and of several case studies, we have argued that the design of symmetric primitives is as vulnerable to malevolent designers as that of asymmetric ones. In order to deny such designers the degrees of freedom that their endeavor would require, we have introduced the notions of moldability and unswervingness. We claim that it is the correct framework for assessing the security level of a symmetric primitive when the designers can be considered adversarial. Further, we have proposed a specific standardization process leveraging this concept to ensure that the final algorithm is safe.

In addition to mitigating (some) risks related to backdoored cryptography, we note that the proposed approaches allow honest designers to increase the trust in their design. This follows from the fact that once unswervingness is maintained, there is less likelihood of succeeding in hiding a backdoor.

  Stream ciphers and PRNGs are the only family we are aware of for which an actual standard has a backdoor, namely Dual EC. More details about how it was standardized are provided in [CCG + 16]. Its flaws were leveraged by an attacker to target Juniper [CMG + 16]. It may also have been used against TLS [CNE + 14].

Figure 2 :

 2 Figure 2: The structures of the 8-bit S-boxes used by 53 different algorithms (taken from [Per17]).

In this paper we study the academic literature for the matter of backdooring cryptography. Historical real-life examples, such as the Crytpo AG company, exist and highlight the fact that backdoored cryptography is a real-life issue.

We note that the Dual EC construction and backdoor are based on elliptic curves operations.

Some of these reductions are not very tight.

We alert the informed reader that we do not discuss the important distinction between differential characteristics and differentials, as well as some other important, yet subtle points. We also do not discuss the process of finding the statistical properties, though of course it is of great importance.

It appears that the rules of ISO do not allow discrimination in favor or against a specific designer (or a group of designers). Hence, even if many in the cryptographic community did not like the idea of Simon and Speck being standardized, ISO had to process the SIMON and SPECK as US-developed ciphers.

After the Snowden revelations, and the disclosure of the Dual EC incident, NIST announced that they will accept NSA-based crypto only after public vetting, e.g., in conferences and in international standardization bodies.

The full name of the sub-committee is ISO/IEC JTC 1/SC27, and the relevant workgroup is WG2.

Acknowledgements

The authors thank the anonymous reviewers for their insights and suggestions and John Kelsey for shepherding this submission. The first author was supported in part by the Israel Ministry of Science and Technology, the Center for Cyber, Law, and Policy in Adapting Rigidity to Symmetric Cryptography: Towards "Unswerving" Designs conjunction with the Israel National Cyber Bureau in the Prime Minister's Office and by the Israeli Science Foundation through grant No. 880/18.


A Better Understanding of this

The LAT of S : {0,

1} n → {0, 1} n is a 2 n × 2 n matrix such that LAT S [a, b] = ∑ x∈F n 2 (-1) a•x⊕b•S(x) = 2 × (#{x ∈ F n 2 , a • x = b • S(x)}) -2 n .
A Key Tool for Analysing S-Boxes Linear Approximations Table (LAT)

The LAT of S : {0,

1} n → {0, 1} n is a 2 n × 2 n matrix such that LAT S [a, b] = ∑ x∈F n 2 (-1) a•x⊕b•S(x) = 2 × (#{x ∈ F n 2 , a • x = b • S(x)}) -2 n . "Jackson Pollock" Representation 1 a b |LAT S [a, b]| = 0 c d |LAT S [c, d]| ≥ 20 1 Biryukov, Perrin

π is a TKlog!

A TKlog operates on F 2 2m and uses: α:

a generator of F 2 2m , κ: an affine function F m 2 → F 2 2m with κ(F m 2 ) ⊕ F 2 m = F 2 2m , s: a permutation of Z/(2 m -1)Z.
The corresponding TKlog is denoted T κ,s and it works as follows:

     T κ,s (0) = κ(0) , T κ,s ( (α 2 m +1 ) j ) = κ(2 m -j), for 1 ≤ j ≤ 2 m -1 , T κ,s ( α i+(2 m +1)j ) = κ(2 m -i) ⊕ ( α 2 m +1 ) s(j) , for 0 < i, 0 ≤ j < 2 m -1 .
13 / 21

Reverse-Engineering the Russian S-box

The TKlog

Cosets to Cosets

Russia's π Everything is wrong (except for the AES bit).

{0} V α × V α 2 × V ... α 16 × V κ(0) ⊕ V κ(15) ⊕ V κ(14) ⊕ V ... κ({1, . . . , 15}) κ(0) ... Backdoored S-box κ(0) ⊕ V κ(15) ⊕ V κ(14) ⊕ V ... β(0) ⊕ W β(15) ⊕ W β(14) ⊕ W ...
A Key Concept: "Anomalies" (1/2)

How "far" is the behaviour of a specific S-box π from that of a "random S-box"?

First idea

What is the probability of a specific property of the S-box?

A Key Concept: "Anomalies" (1/2)

How "far" is the behaviour of a specific S-box π from that of a "random S-box"? Compute it for the specific target Evaluate the number S-boxes with with a worse and a better property worse best property π Some Very High Anomalies Informally (more details at AC'193 ), a high positive anomaly for a property means: a random S-box is unlikely to have a property "at least as pronounced" as π;

we need to generate about 2 A random S-boxes to get one where the property is this strong. This claim and this fact cannot be reconciled.

Standards and S-boxes

In my opinion, the designers of these algorithms have provided misleading information for the external analysis of their design.

vs.

This claim and this fact cannot be reconciled.

In my opinion, the designers of these algorithms have provided misleading information for the external analysis of their design.

Security analysis is hard enough with proper information: there is no good reason to complicate it further with wrong data! vs.

This claim and this fact cannot be reconciled.

In my opinion, the designers of these algorithms have provided misleading information for the external analysis of their design.

Security analysis is hard enough with proper information: there is no good reason to complicate it further with wrong data! =⇒ These algorithms cannot be trusted and I believe they should be deprecated.

vs.

This claim and this fact cannot be reconciled.

In my opinion, the designers of these algorithms have provided misleading information for the external analysis of their design.

Security analysis is hard enough with proper information: there is no good reason to complicate it further with wrong data! =⇒ These algorithms cannot be trusted and I believe they should be deprecated.

Thank you!

  probability of a specific property of the S-box?Does not work!The properties we consider are not intended for that purpose.Pr [Differential uniformity = 8] ≈ 2 -16.15 ≈ (72000) -1Pr [Differential uniformity = 6] ≈ 2 -164.5 ≈ (3 • 10 49 ) grained property (LAT max/# occurrences of the max, implementation complexity...) with a value in a partially ordered set (i.egrained property (LAT max/# occurrences of the max, implementation complexity...) with a value in a partially ordered set (i.egrained property (LAT max/# occurrences of the max, implementation complexity...) with a value in a partially ordered set (i.e. a number)

Reverse

Linear permutations The Russian S-Box was built like a strange Feistel... ... or was it?

	First Complete Decomposition of π
			α
	ν 0	ν 1 ⊙	I			⊙ Multiplication in F 2 4 I Inversion in F 2 4
	Variance α, ω Belarussian inspiration σ ϕ ⊙ ν 0 , ν 1 , σ 4 × 4 permutations ϕ 4 × 4 function The last standard of Belarus (BelT) uses an 8-bit S-box,
		0	ω	50	100 Column index 150	200	250

. On reverse-engineering S-Boxes with hidden design criteria or structure. CRYPTO'15

The LAT of π somewhat similar to π...

... based on a finite field exponential!

We deduced another decomposition 2 but not a satisfactory one. 2 L. Perrin, A. Udovenko. Exponential S-boxes: a link between the S-boxes of BelT and Kuznyechik/Streebog. IACR ToSC. 2016.

L. Perrin, A. Udovenko. Exponential S-boxes: a link between the S-boxes of BelT and Kuznyechik/Streebog. IACR ToSC. 2016.

Anomalies and Vector Space Search: Tools for S-Box Analysis. ASIACRYPT'19. X. Bonnetain, L. Perrin and S. Tian.

† This anomaly might be overestimated.3 Anomalies and Vector Space Search: Tools for S-Box Analysis. ASIACRYPT'19. X. Bonnetain, L.Perrin and S. Tian.

On Networks Consisting of Functional Elements with Delays. Lupanov, O.B. 1973.

Timeline July GOST standardization of Streebog Aug. RFC for Streebog (RFC6986) June GOST standardization of Kuznyechik Mar. RFC for Kuznyechik (RFC7801) Timeline July GOST standardization of Streebog Aug. RFC for Streebog (RFC6986) June GOST standardization of Kuznyechik Mar. RFC for Kuznyechik (RFC7801) May Publication of the first decomposition (TU-decomposition) Feb Publication of the second decomposition (Belarus-like)

A Key Concept: "Anomalies" (1/2) How "far" is the behaviour of a specific S-box π from that of a "random S-box"?

S-Boxes

The Russian S-box Screen capture of the specification of Kuznyechik (2015).

Why we need S-box reverse-engineering

The security of a cipher hinges on its S-box: we need to know how it works!

Conclusion for Kuznyechik/Streebog?

The Russian S-Box was built like a strange Feistel...

Conclusion for Kuznyechik/Streebog?

) Some Very High Anomalies

Informally (more details at AC'19 3 ), a high positive anomaly for a property means:

a random S-box is unlikely to have a property "at least as pronounced" as π;

we need to generate about 2 A random S-boxes to get one where the property is this strong. Kolmogorov Anomaly (2/2)

Anomalies of π.

Statistical Structural

Differential

The "Shannon effect": 4 "almost all functions" of n arguments have "an almost identical" complexity which is asymptotically equal to the complexity of the most complex function of n arguments.

Indeed, specific structures (TKlog, TU-decompositions...) have a very high anomaly... Kolmogorov Anomaly (2/2)

The "Shannon effect": 4 "almost all functions" of n arguments have "an almost identical" complexity which is asymptotically equal to the complexity of the most complex function of n arguments.

Indeed, specific structures (TKlog, TU-decompositions...) have a very high anomaly... ... but not really an anomaly. Can we do better?


Léo Perrin
email: leo.perrin@inria.frinria

Xavier Bonnetain
email: xavier.bonnetain@inria.frinria

Russian Style (Lack of) Randomness

It is crucial for a cipher to be trusted that its design be well explained. However, some designers do not publish their design method and instead merely put forward a specification. While this information is sufficient for implementers, the lack of explanation hinders third party cryptanalysis. In a recent string of papers, Biryukov, Perrin and Udovenko identified increasingly strong patterns in a subcomponent shared by the last two Russian standards in symmetric cryptography, namely the hash function Streebog (GOST R 34.11-2012) and the block cipher Kuznyechik (GOST R 34.12-2015). In this paper, we summarize the latest result of Perrin on this topic and argue that, in light of them, these algorithms must be avoided.

1. In fact, it is sufficient that some linear combinations of the output bits do not depend on some linear combinations of the input bits.

.

Introduction

Block ciphers are at the core of symmetric cryptography, as they are used to encrypt messages, but also to build MACs or hash functions. The most famous example is the AES, which is used to encrypt a very large amount of today's communications.

Formally, a block cipher is a permutation E k operating on blocks of a fixed size (typically 128 bits) which is parametrized by a secret key k, also of a fixed size (typically 128 or 256 bits). In practice, a block cipher is always defined as multiple iterations of a simple round function interleaved with the addition of subkeys derived from the master key k. Following the terminology introduced by Shannon, the round function must provide both diffusion and confusion. Diffusion means that the output bits must depend on many input bits and confusion means that the mathematical relationship between input bits, output bits and key bits must be complex. In particular, it has to be non-linear.

S-boxes and their Importance

Non-linearity is usually (though not always) provided by small nonlinear function called S-Boxes while diffusion is provided by the linear layer which operates on much larger parts of the internal state. The small size of the S-Boxes mean that they are usually specified by their look-up table (LUT), i.e. the array (S[0], S [START_REF] Ashur | An account on the ISO/IEC standardization of Simon and Speck[END_REF], ..., S[2 m -1]) where m is the number of input bits of S, and where typically m = 4 or m = 8. In practice, the output size is usually the same as the input size.

Knowning this table is sufficient to analyze their generic cryptographic properties. We can then combine these with other properties of the linear layer to formally prove that some cryptanalysis techniques will fail when applied to the block cipher. For example, the AES designers introduced the wide-trail argument to prove that it is safe from single-trail differential and linear cryptanalysis.

The role of these S-Boxes is to mix their input in a non-linear way. This non-linearity can for example be quantified via the differential uniformity. For an S-Box S operating on the set F n 2 of all n-bit strings, the differential uniformity of S is the maximum number of solutionts S of the equation

S(x ⊕ a) ⊕ S(x) = b
for all a, b ∈ F 2 where a = (0, 0, ..., 0).

They must also be such that all outputs depend on all their inputs. In fact, S-box that fail to provide this property 1 have been proved in [START_REF] Bannier | Combinatorial Analysis of Block Ciphers With Trapdoors[END_REF] to be precisely those needed to build a specific type of backdoored block cipher. Such a block cipher E k would be such that every output bit depends on all input bits. However, it would yield secret linear functions ℓ 1 and ℓ 2 such that ℓ 2 (E k (x)) does not depend on ℓ 1 (x). In a stealthy way, this block cipher fails to provide diffusion. This allows anyone with the knowledge of the functions ℓ 1 and ℓ 2 to efficiently attack the cipher.

Ill-Specified S-Boxes

As we have established, S-Boxes play a crucial role in the security level provided by the algorithms using them. Consequently, it is expected of block cipher designers that they carefully choose these components and justify their choice in the paper describing their algorithm. These explanations will help in several ways. Third party cryptanalysts analysing the security of the block cipher will have their task simplified; implementers may be able to leverage the structure of the S-Box to implement it more efficiently 2 ; and potential users will have an increased trust in the algorithm: it is much harder to hide a trapdoor in an algorithm when all of its components must have a clear justification.

Unfortunately, some cipher designers do not provide such justifications. In particular, the American NSA and its Russian counterpart the FSB do not explain the rationale behind the algorithms they design. Yet, the following algorithms have been included in national and international standards -the American block cipher Skipjack [START_REF]Skipjack and KEA algorithms specifications[END_REF], which used to be a NIST3 standard but is now deprecated, -the American block cipher CMEA [START_REF] Wagner | Cryptanalysis of the cellular message encryption algorithm[END_REF], which was standardized by the TIA 4 and used to secure the control channel (e.g. the transmission of phone numbers) of cell phones in North America, -the Russian hash function Streebog [START_REF]Information technology -data security: Hash function[END_REF] (GOST R 34.11-2012) which has been a standard in Russia since 2012 and is also the IETF RFC 6986 [START_REF] Dolmatov | GOST R 34.11-2012[END_REF], and -the block cipher Kuznyechik [START_REF]Information technologydata security: Block ciphers[END_REF] (GOST R 34.12-2015) which is a Russian standard since 2015 and the IETF RFC 7801 [START_REF] Dolmatov | Block cipher "kuznyechik[END_REF].

Kuznyechik is also being considered by ISO/IEC for inclusion as one of their standards. All these algorithms have been standardized and used despite the fact that their designers did not provide any information about their design. In particular, they all use unexplained S-Boxes. In this context, it is crucial to be able to recover the design criteria and/or the structure used to build an S-Box S given only its LUT.

Both Russian algorithms (Streebog and Kuznyechik) use the same S-box, π. It is an 8-bit permutation which was only specified via its look-up table (see Figure 1). In the next section, we summarize the results that were obtained by cryptanalysts about this S-box and, in particular, how it has a hidden structure which could have negative consequences regarding the security of the algorithms using it.

Reverse-Engineering the Russian S-box

Reverse-engineering an S-box is a challenging task as it is a priori very difficult to know if a decomposition is the one that was intended by its designers. Biryukov et al. first identified a new generic reverse-engineering technique, the TU-decomposition, which they could successfully apply to π [START_REF] Biryukov | Reverse-engineering the s-box of streebog, kuznyechik and stribobr1[END_REF]. Then, Perrin and Udovenko found a relation between π and a discrete logarithm. Though it showed that there was more to π than previously thought, their decomposition left them unconvinced as some of its components were somewhat inelegant [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of belt and kuznyechik/streebog[END_REF]. Finally, building upon these results, Perrin identified a structure which is likely to be the one intended by the designers of π [START_REF] Perrin | Partitions in the S-box of Streebog and Kuznyechik[END_REF].

Let us describe this last decomposition. Perrin showed that π can be evaluated by the following equations:

       π(0) = κ(0) π α 17j
= κ(16 -j), where 0 < j ≤ 15 j) , where 0 ≤ j < 15, 0 < i ≤ 16 , where -the finite field GF (2 8 ) is defined as F 2 [X]/p(X) with p(X) = X 8 + X 4 + X 3 + X 2 + 1, -α is a root of p and thus 5 a multiplicative generator of GF(2 8 ) * , -s is a permutation of {0, 1, 2, ..., 14} given in Table 1, and -κ : {0, 1} 4 → GF(2 8 ) is a linear permutation such that κ(x) = Λ(x) ⊕ 0xfc and such that Λ : {0, 1} 4 → GF(2 8 ) is the linear function defined by

π α i+17j = κ(16 -i) ⊕ α 17 s(
Λ(0x1) = 0x12, Λ(0x2) = 0x26, Λ(0x4) = 0x24, Λ(0x8) = 0x30 .
This highly structured decomposition is unlike anything else in the literature. It was also kept secret by the designers of π. Still, it is likely to be the one they used: it is very simple 6 and the number of permutations 5. It also holds that α 17 is a multiplicative generator GF(2 4 ) * . 6. Especially when compared to the previous two decompositions of [START_REF] Biryukov | Reverse-engineering the s-box of streebog, kuznyechik and stribobr1[END_REF] and [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of belt and kuznyechik/streebog[END_REF].

x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 s(x) 0 12 9 8 7 4 14 6 5 10 2 11 1 3 13 Table 1. The subfunction s.

with such a structure is negligible. In fact, Perrin established that the probability for a random permutation to have such a structure is equal to about 2 82.6-1684 ≈ 2 -1601 . For comparison, the probability that an 8-bit permutation is affine is equal to 2 70.2-1684 ≈ 2 -1618 and the probability to win the Loto 7 is about 2 -24.2 . Thus, the probability for a permutation picked uniformly at random to have a structure similar to that of π is comparable to the probability of gaining the Loto 66 times in row! Hence, it is likely to be the structure originally intended by the designers of this S-box.

Besides, this structure also has some strange cryptographic properties. The field GF (2 4 ) is contained in GF (2 8 ) and π has a specific interaction with the cosets of this subfield. If i > 0, then

π(α i ×x), x ∈ GF(2 4 ), x = 0 = κ(16-i)⊕x, x ∈ GF(2 4 ), x = 0 (1)
where the multiplication is done in GF (2 8 ). In other words, π maps the partition of GF (2 8 ) into multiplicative cosets of GF(2 4 ) * to its partition into additive cosets of GF(2 4 ) * .

The other main component of the hash function Streebog is a 64-bit linear permutation originally specified as a 64 × 64 binary matrix. It is in fact a 16 × 16 matrix with coefficients in GF (2 8 ) where this field is defined by the same polynomial as in π. Hence, this component interacts in a way which is yet to be fully understood with the partitions in Equation [START_REF] Ashur | An account on the ISO/IEC standardization of Simon and Speck[END_REF]. Much like the structure of π, the structure of this component was kept secret and had to be reverse-engineered-though it was much simpler.

In light of these results, new security analyses of Kuznyechik and even more so of Streebog are necessary. We have yet to perfectly understand the consequences of these partition-preserving properties. Had the designers of the Russian ciphers disclosed the structures they used, cryptographers could have focused on this analysis much sooner. Of course, their aim when hiding those may have been to try and prevent such an analysis.

7. The French lotery is won if 5 numbers in {1, 2, ..., 49} and one in {1, ..., 10} are chosen correctly, an event with probability (49 × 48 × 47 × 46 × 45 × 10/5!) -1 ≈ (19 × 10 6 ) -1 ≈ 2 -24.2 .

Conclusion

The last symmetric cryptographic algorithms standardized in Russia (and later included in some IETF RFC as well as an ISO/IEC standard, possibly followed by a second one soon) only had their specifications published. Their authors did not disclose their design rationale which, in and on itself, should warrant caution. Through a series of papers, Biryukov, Perrin and Udovenko have progressively unlocked the secrets of one of the main components of these algorithms. In particular, the latest results of Perrin show that the designers of Streebog and Kuznyechik purposefully hid a structure in this component. This structure is very strong, very uncommon and interacts in a non-trivial way with the other main component of Streebog.

In light of these results, we urge security professionals to avoid these algorithms. More generally, we invite them to keep in mind that, ultimately, both national and international standards in cryptography are seldom chosen transparently and that the final decision is rarely made by cryptographers (see also [START_REF] Ashur | An account on the ISO/IEC standardization of Simon and Speck[END_REF]). Hence, we ugre practitioners to carefully check where the algorithms they plan to use come from, even if they are standards.

Fig. 1 .

 1 Fig. 1. A screen capture of the specification of the block cipher Streebog [8, page 4].

National Institute for Standards and Technology.

Telecommunications Industry Association.

Acknowledgements This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 714294acronym QUASYModo).