Christina Boura

Patrick Derbez

Henri Gilbert

Willi Meier

Marine Minier

Thomas Peyrin

Sondre Rønjom

Anne Anthony

Aurélie, Aurélien Antonio Augustin

Axel Charles

Clémence, Daniel, Dounia, Ferdinand Christina Clara

Jean-Pierre Gaëtan

Maxime Nicolas Nicholas

Rachelle Paul

Rocco Ritam

Simona Thomas

Virgile, Xavier Yann Valentin

Je Souhaite Remercier

Akinori

Augustin Antonio André

Christina

Christof

Gaëtan, Gregor Frederico

Marek Maria Patrick

Yosuke J'aimerais Exprimer

Avant d'entamer toute discussion scientifique, ce manuscrit débutera par des remerciements. En effet, la réalisation de cette thèse n'a été possible que grâce à l'indispensable soutien de nombreuses personnes.

Tout d'abord, je voudrais exprimer ma gratitude envers Maria qui m'a ouvert au monde de la cryptographie symétrique et qui m'a encadré lors de ces trois années de thèse tout en faisant preuve de disponibilité et d'enthousiasme.

J'aimerais également remercier les autres

List of Figures

4.7 This table represents the information used for efficiently solving the keyrecovery part of the attack. Each line in the table is associated with the same row in the state. The column Key determined indicates how many bits are already known from Stage 1 (those bits are depicted in red), and Key left is the number of bits that remains to be known. Fixed bits represents the number of inactive bits after the first SB of Round 0 and that therefore can be used to perform a sieving on the candidate keys. The cost is the difference between the previous values, and the second filter denotes the active rows in the second SB, as they will provide additional filtering to produce the fixed output difference. . . We obtain a better memory than [START_REF] Derbez | Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting[END_REF], and a time complexity comparable to [START_REF] Bonnetain | Quantum Security Analysis of AES[END_REF] (the quantum time is counted in S-Box evaluations). . . . . . . 6.5 Successive steps of the attack on AES (if we used the standard early abort).

The parameter s corresponds to a byte (8 bits). . . . . . . . . . . . . . . . .

x

Présentation des travaux

Le manuscrit de thèse présenté s'intitule "Techniques améliorées en cryptanalyse différentielle". Cette thèse en informatique se concentre sur le domaine de la cryptographie, en particulier sur la cryptanalyse différentielle et s'étend sur un total de six chapitres. Dans un premier temps, deux chapitres d'introductions sont présentés: Préliminaires et Cryptanalyse différentielle, suivis de quatre chapitres constitués de mes contributions scientifiques : Cryptanalyse différentielle-linéaire améliorée, application sur Chaskey; Attaque différentielle de la version complète de SPEEDY-7-192; Cryptanalyse différentielle-MITM 1 ; Cryptanalyse différentielle impossible quantique.

Chapitre 1 : Préliminaires

Dans ce chapitre, je vais commencer par fournir une description historique de la cryptographie, en commençant par la cryptographie classique, puis en passant à la cryptographie moderne, et enfin en abordant la cryptographie de demain. Après cette introduction, je vais décrire quelques constructions importantes en cryptographie symétrique. Bien que je présente les constructions de chiffrement de flux, de fonction de hachage et de code d'authentification de message, je fournirai surtout une description approfondie ainsi qu'une définition formelle du chiffrement par bloc puisqu' il s'agit de la construction qui sera le plus étudiée pendant cette thèse. Ce dernier peut être décrit comme une fonction qui prend en entrée une clef secrète et renvoie une permutation sur un espace de message de taille fixé. La sécurité de cette construction réside entre autres sur la difficulté qu'un attaquant a à distinguer cette permutation d'une permutation aléatoire.

Ensuite, je vais aborder des éléments de cryptanalyse symétrique. Je commencerai par présenter les modèles dans lesquels l'adversaire se place pour tenter d'attaquer les chiffrements par bloc en décrivant notamment les principes de distingueur de récupération de clef. Cette partie sera suivie d'une description des techniques de cryptanalyse symétrique bien connues, telles que la cryptanalyse linéaire et la cryptanalyse MITM (Meet-in-the-Middle). La cryptanalyse différentielle, qui est également une technique très importante de cryptanalyse symétrique, sera abordée dans le chapitre suivant.

• Criblage des paires. Cette étape débute avec les paires de messages clairs/chiffrés obtenues dans l'étape précédente. L'objectif est maintenant de créer un ensemble de paires différentielles qui pourraient potentiellement suivre le chemin différentiel en entrée et en sortie du chiffrement par bloc. Il s'agit donc de cribler l'ensemble des paires différentielles pour conserver uniquement celles qui nous intéressent.

• Récupération de clef. Dans cette dernière étape, nous utiliserons les paires différentielles gardées précédemment pour retrouver certains bits de la clef secrète en utilisant le distingueur différentiel. Bien qu'il existe différentes méthodes pour effectuer cette étape, je présenterai la technique de l'arrêt anticipé (early abort) qui permet souvent de retrouver la clef efficacement.

À la suite de cette description, je détaille les complexités en temps, mémoire et données associées à cette attaque. Dans la suite de ce chapitre, je donnerai la description de différentes variations de la cryptanalyse différentielle : cryptanalyse différentielle impossible, cryptanalyse différentielle linéaire.

La cryptanalyse différentielle impossible se construit de manière similaire à la cryptanalyse différentielle classique, à la différence notable que le distingueur différentiel a désormais une probabilité associée nulle plutôt qu'anormalement élevée. Le but sera dorénavant d'éliminer les mauvaises clefs afin de conserver seulement la clef utilisée lors du chiffrement. Si cette méthode peut aussi être décrite suivant les mêmes trois étapes que la cryptanalyse différentielle, la description de l'algorithme d'early abort se fait plus naturellement avec un point de vue différent. Ce second point de vue permet une traduction plus naturelle vers la version quantique des attaques différentielles impossibles décrite dans le chapitre 6. xii La cryptanalyse différentielle-linéaire consiste au regroupement de la cryptanalyse linéaire et de la cryptanalyse différentielle. En effet, en combinant des approximations différentielles et linéaires, il est possible de construire une nouvelle forme de distingueur. Dans cette section, je donnerai une description précise de la construction de ce distingueur et de l'exploitation que l'on peut en tirer. Un exemple de cryptanalyse différentielle linéaire est donné dans le chapitre suivant sur le chiffrement Chaskey.

Chapitre 3 : Cryptanalyse différentielle-linéaire améliorée, application sur Chaskey

Dans ce chapitre, je vais présenter un résumé de notre travail collaboratif avec Marek Broll, Frederico Canale, Antonio Flórez-Gutiérrez, Gregor Leander, María Naya-Plasencia et Yosuke Todo, portant sur les optimisations de la cryptanalyse différentielle-linéaire des constructions ARX, ainsi que son application à Chaskey [Bei+22]. Notre article explore différentes optimisations indépendantes les unes des autres. Dans ce chapitre, je mettrai particulièrement l'accent sur la partie de l'article traitant des améliorations apportées à la composante différentielle, étant donné que c'est ma contribution spécifique à cette recherche.

Dans l'article [START_REF] Beierle | Improved Differential-Linear Attacks with Applications to ARX Ciphers[END_REF], les auteurs ont présenté une technique visant à améliorer les attaques différentielles-linéaires et à les appliquer à Chaskey et Chacha. À la suite de cette étude, nous avons continué à perfectionner les attaques différentielles-linéaires dans le cadre de notre travail décrit dans [Bei+22]. Dans la première section de ce chapitre, nous allons détailler la technique introduite dans l'article [START_REF] Beierle | Improved Differential-Linear Attacks with Applications to ARX Ciphers[END_REF], qui permet d'améliorer la corrélation d'un distingueur différentiel-linéaire et on montrera comment. Cette amélioration est possible grâce à l'étude d'espace neutre. Il s'agit d'espace affine qui vérifie une certaine équation différentielle. L'utilisation de ces espaces permet d'améliorer la corrélation du distingueur différentiel linéaire considéré. Ainsi, il est possible de faire des attaques plus performantes qu'auparavant. Pour calculer ces espaces neutres, je décrirai deux approches. La première approche est algorithmique et consiste à tester des vecteurs de poids faible afin de construire empiriquement l'espace neutre. La seconde approche s'inspire de la cryptanalyse conditionnelle différentielle et donne des méthodes pour retrouver des vecteurs neutre. Bien que laborieuse, cette méthode permet de retrouver des vecteurs de poids élevés qui ne peuvent pas être détéctés par la méthode algorithmique.

La seconde partie de ce chapitre se concentre sur l'application de ces améliorations au chiffrement par bloc Chaskey. Tout d'abord, je fournirai une description détaillée de Chaskey lui-même. Ensuite, j'exposerai l'espace neutre obtenu grâce à l'algorithme ainsi que les techniques de conditions présentées dans la section qui précède. Grâce à ces applications, de nouvelles attaques plus efficaces ont été proposées pour différentes versions de Chaskey, offrant ainsi des améliorations significatives dans la cryptanalyse xiii de ce chiffrement.

Chapitre 4 : Attaque différentielle de la version complète de SPEEDY-7-192

Ce chapitre tire son inspiration de l'article [Bou+23a], fruit d'une collaboration avec Christina Boura, Rachelle Heim Boissier et María Naya-Plasencia. Dans cette publication, nous avons présenté une attaque complète contre la version principale du chiffrement par bloc Speedy [START_REF] Leander | The SPEEDY Family of Block Ciphers Engineering an Ultra Low-Latency Cipher from Gate Level for Secure Processor Architectures[END_REF] en utilisant la cryptanalyse différentielle. Cette étude a permis de découvrir une vulnérabilité majeure dans le système de chiffrement Speedy, remettant en question sa sécurité et soulignant l'importance de la cryptanalyse différentielle dans l'évaluation de la résistance des nouveaux chiffrements par bloc.

Dans un premier temps, je donnerai une description de la famille de chiffrement par bloc SPEEDY en décrivant notamment la représentation de l'état interne, la fonction de tour ainsi que l'algorithme d'expansion de clef 2 . De plus, je donnerai les revendications de sécurité données par les créateurs de SPEEDY pour chacune des versions du chiffrement. L'attaque présentée dans la suite de ce chapitre sera en mesure de contredire ces revendications pour le chiffrement principal de cette famille : SPEEDY-7-192.

Le chapitre se poursuit avec une section qui traite de la méthode utilisée pour trouver un distingueur différentiel permettant de monter une attaque intéressante. Dans un premier temps, je mettrai en évidence les propriétés différentielles que présente la SBox de SPEEDY. Ensuite, je donnerai une procédure algorithmique qui permet de trouver un distingueur différentiel à haute probabilité en concaténant des distingueur sur un tour. Cela nous a permis d'obtenir un distingueur sur 5.5 tours avec une probabilité 2 -183.59 qui permettra de faire une attaque différentielle sur SPEEDY-7-192.

La dernière section de ce chapitre décrit l'attaque différentielle sur SPEEDY-7-192. La complexité de cette attaque est 2 187.28 en temps, 2 187.84 en données, et 2 42 en mémoire, les revendications des créateurs annonçaient 2 192 en temps et données. Cette attaque contredit donc ces revendications. De plus, les créateurs de SPEEDY ont indiqué : l'attaquant ne peut pas ajouter plus d'un tour pour prolonger le distingueur différentiel, ceci est aussi contredit par notre attaque qui étend le distingueur de 1.5 tour. La description de l'attaque différentielle se fait en suivant les trois étapes décrites dans le chapitre 2. Cependant, quelques optimisations sont aussi présentées • Compromis entre étapes. La complexité totale de l'attaque est la somme des complexités de chaque étape. Pour minimiser le tout, il est souvent intéressant de faire des compromis. Ceci est possible notamment en contrôlant la propagation de la différence en entrée du distingueur vers le message clair. En effet, un surcout en

2 key schedule en anglais xiv probabilité sera nécessaire, donc une augmentation du coût de l'étape de création des données. En revanche, la dimension de l'espace en entrée sera réduite, ainsi, la complexité de l'étape criblage des paires sera réduite.

• Mise à jour des espaces différentiels. Si la première étape nécessite que les espaces différentiels en entrée et en sortie soient des espaces vectoriels afin d'utiliser les structures, il n'est plus nécessaire de considérer ce genre d'espace à partir de la seconde étape. En raffinant ces espaces en ensemble de différences autorisés (qui n'ont plus à être des structures), on obtient un criblage plus puissant, par conséquent la quantité de paires retenues baisse et la complexité se réduit.

• Association parallèle Cette dernière optimisation intervient pendant l'exécution de l'algorithme de l'early abort. Cette technique décrite et améliorée dans [START_REF] Canteaut | Sieve-in-the-Middle: Improved MITM Attacks[END_REF] permet d'accélérer certaines étapes de cet algorithme lorsque certaines conditions sur les relations de propagations sont vérifiées. En effet, cette technique permet de calculer les paires (a, b) qui vérifient une relation R lorsque l'on dispose des elements a dans une liste L A et des elements b dans une liste L B en un temps comparable a

|L A | + |L B | plutôt que |L A | • |L B |.
Ce chapitre se termine en concluant que les attaques différentielles sont certes très connues, mais menacent toujours les chiffrements par bloc même les plus récents car cette famille d'attaque reste très techniques et difficile à évaluer automatiquement.

Chapitre 5 : Cryptanalyse différentielle-MITM

Dans ce chapitre, je présenterai une nouvelle technique de cryptanalyse en cryptographie symétrique : cryptanalyse différentielle meet-in-the-middle. Cette approche consiste à combiner des éléments de cryptanalyse différentielle avec des éléments de cryptanalyse meet-in-the-middle. Du point de vue différentiel, cette nouvelle technique peut être interprétée comme une nouvelle méthode pour effectuer l'étape de récupération de clef. Du point de vue du meet-in-the-middle, les attaques différentielles-MITM consistent en une méthode pour étendre les attaques MITM en ajoutant quelques tours au milieu (similaire à sieve-in-the-middle [START_REF] Canteaut | Sieve-in-the-Middle: Improved MITM Attacks[END_REF][START_REF] Canteaut | Sieve-inthe-Middle: Improved MITM Attacks (Full Version)[END_REF]).

Dans une première section, je donnerai une description générale de cette technique. Plus précisément, je fournirai un cadre général qui décrit comment monter une attaque différentielle-MITM de manière générique et simple. Ensuite, je montrerai comment combiner cette méthode générique avec deux techniques : le traitement parallèle des partitions de données afin d'en ajouter un tour gratuitement (cette idée hérite des attaques MITM, comme les bicliques, et qui ne s'applique pas aux attaques différentielles classiques), ainsi qu'une technique pour réduire la complexité des données. Enfin nous ferons une comparaison de cette technique avec les attaques différentielles traditionelles et les attaques MITM. xv La seconde section de ce chapitre présente une application de la cryptanalyse différentielle MITM au chiifrement par bloc SKINNY-128-384. Je commencerai cette section par donner une description de la famille de chiffrement par bloc SKINNY puis je décrirai une succession d'attaques différentielles MITM sur SKINNY-128-384. La première attaque (23 tours) correspond à l'application de la technique décrite dans la première section. La deuxième (24 tours) reprend l'attaque sur 23 tours et intègre l'optimisation du traitement parallèle des données afin de gagner un tour gratuitement. La troisième attaque sur 25 tours est présentée avec un distingueur différentiel différent de celui utilisé pour les deux premières attaques. Les deux optimisations sur la repartitions des données et sur la complexité des données sont untilisées ici permettant d'ajouter deux tours à la meilleure attaque sur SKINNY-128-384 en clef simple (en opposition aux clefs reliées).

Pour finir ce chapitre, je donnerai des éléments qui démontrent la puissance des attaques différentielles MITM. En effet, si l'on tente d'effectuer une attaque différentielle traditionelle en utilisant le même distingueur, on ne peut pas espérer attaquer plus de 22 tours si l'on utilise un algorithme de récupération de clef sequentiel et 24 tours dans le cas d'un récupération de clef parallel. Cela soulève alors la question suivante: Dans quel scénarios la cryptanalyse différentielle MITM est elle plus efficace que la cryptanalyse différentielle et MITM ?

Chapitre 6 : Cryptanalyse différentielle impossible quantique

Dans ce chapitre, je présenterai des résultats issus de l'article [DNS22], fruit d'une collaboration avec María Naya-Plasencia et André Schrottenloher. Cet article présente la version quantique de la cryptanalyse différentielle impossible : cryptanalyse différentielle quantique. Cette article réponds à un problème ouvert émis dans [START_REF] Bonnetain | Quantum Security Analysis of AES[END_REF] qui questionnait l'efficacité des attaques différentielles impossible en quantique.

Dans un premier temps, je présenterai les différents algorithmes quantiques utiles pour la cryptanalyse différentielle impossible. Ces algorithmes de recherche de collisions sont primordiaux pour l'étape de l'attaque qui vise à créer des paires différentielles. Utilisant ces algorithmes, je serai en mesure d'exhiber une formule précise pour la complexité de l'étape de création de paires dans le cas quantique.

Dans un deuxième temps, je présenterai la version quantique de l'algorithme de l'early abort. Pour cela, je présenterai d'abord le modèle quantique dans lequel j'évoluerai pour décrire l'attaque. Enfin, je décrirai en détail l'early abort quantique, cet algorithme consiste en une imbrication de recherche de Grover. Aussi, je présenterai une version améliorée lorsque certaines conditions sont sur les propagations sont réunies. Tous les algorithmes seront décrits avec leurs complexités en temps et en mémoire.

Ce chapitre se poursuit avec deux applications : SKINNY et AES. Pour chacune des applications, il est possible d'observer une amélioration des meilleures attaques quantiques (bien que l'attaque différentielle sur AES présentée dans [START_REF] Bonnetain | Quantum Security Analysis of AES[END_REF] propose xvi des complexités similaires).

Conclusion

Pour résumer, ce manuscrit présente un éventail de techniques de cryptanalyse de type différentielle agrémentées d'applications de ces dernières sur des chiffrements par bloc parfois très récents. Cela met donc en exergue l'importance que représente cette famille de cryptanalyse symétrique et impose à tout créateur de primitive de s'assurer de sa résistance vis-à-vis de ces attaques. This chapter is organized as follows: first, we will present cryptology from a historical point of view, then we will describe some constructions from symmetric cryptography followed by cryptanalytic techniques developed to analyze their security. Finally, we will give some elements useful for quantum computing, more precisely we will introduce elements required for quantum cryptanalysis that will be used in Chapter 6.

History of Cryptology

Cryptology has a rich and ancient history that dates back thousands of years. The earliest known instances of cryptology can be traced to ancient civilizations such as Egypt and Mesopotamia, where methods like transposition and substitution were used to conceal messages. A well-known example of substitution cipher is the Caesar cipher that was named after and used by the Roman emperor Julius Ceasar. This type of cipher is now outdated and shows critical weakness to statistical attacks. Throughout 2 Chapter 1. Preliminaries history, cryptologic designs have evolved alongside techniques used to break them. As cryptographers devised new ways to secure information, adversaries countered with innovative approaches to extract information from encrypted messages. This dynamic resulted in the development of increasingly sophisticated methods and the emergence of modern cryptography.

Modern cryptography is built on the foundation of several key principles and techniques. One of these principles is Kerckhoffs' principles [START_REF] Kerckhoffs | La cryptographie militaire[END_REF], which state that the security of a cryptographic system should rely solely on the secrecy of the key, not on the secrecy of the algorithm. This principle emphasizes the importance of key management and assumes that the cryptographic algorithm will be widely known and studied. To answer the need for secure communication between parties, cryptographers design cryptographic protocols that can ensure confidentiality and integrity. These protocols are based on the usage of cryptographic primitives that can be separated into two families: symmetric cryptology and assymetric cryptography. Symmetric cryptography, also known as secret-key cryptography, involves the use of a single shared secret key for both encryption and decryption. The same key is used by both the sender and the receiver to transform plaintext into ciphertext and vice versa. This type of cryptography is efficient and fast, making it suitable for secure data transmission and storage but requires first to set up a secure key exchange protocol. Asymmetric cryptography, also known as public-key cryptography, employs a pair of mathematically related keys: a public key and a private key. The public key is freely distributed, while the private key is kept secret. Messages encrypted with the public key can only be decrypted with the corresponding private key. This approach enables secure key exchange for symmetric cryptography, digital signatures, and encryption of confidential information.

The development of quantum computers has had a significant impact on cryptography by rendering many of the current asymmetric cryptographic algorithms vulnerable to quantum attacks. Quantum computers can break commonly used encryption methods, such as RSA and elliptic curve cryptography, which rely on the difficulty of certain mathematical problems that can be efficiently solved by quantum algorithms. As a result, the field of post-quantum cryptography is actively exploring new classical algorithms that can resist attacks from (future) quantum computers, ensuring the continued security of sensitive information in the future.

Symmetric Cryptography

Symmetric cryptography is an approach to encryption that involves the use of a single shared secret key for both encryption and decryption. In this section, we will present the main constructions from symmetric cryptography with a particular focus on block ciphers.

Symmetric Cryptography

Block Ciphers

Block ciphers are one of the main constructions in symmetric cryptography used for encryption, where plaintexts have fixed sizes. To encrypt messages of arbitrary and longer length, it suffices to divide them into fixed-size blocks and encrypted them independently with a special treatment for the last block with padding. Common block cipher algorithms include the Advanced Encryption Standard (AES [START_REF] Daemen | AES proposal: Rijndael[END_REF]), which operates on 128-bit blocks, and the Data Encryption Standard (DES [START_REF] Standard | Data encryption standard[END_REF]), which operates on 64-bit blocks.

Definition 1.1 (Block Cipher). A block cipher is a deterministic algorithm that acts on a fixed-length group of bits. It is often used to encrypt a plaintext into a ciphertext using a secret key. More precisely, a block cipher can be represented as a function

E : F n 2 × F k 2 → F n 2 such that for any given key κ ∈ F k 2 the function E(•, κ) : F n 2 → F n 2 is a permutation (we will note E(•, κ) as E κ ).
Simply meeting the definition above is not enough to make a block cipher secure and interesting. Indeed, some additional requirements must be satisfied regarding both efficiency and security. When the key κ is known, both encryption and decryption operations should be performed very efficiently at a very low cost, hence allowing a large volume of exchange. When the key κ is unknown, the attacker should not be able to extract information from the pairs of plaintext ciphertext. Ideally, the attacker should not be able to distinguish E κ from a random permutation.

Block Cipher Construction

The construction of a block cipher often consists in the iteration of rounds that act on the n-bit blocks that compose the internal state. Each round usually applies some key-related transformation to ensure the security of the block cipher. The key material injected in each round is called a round key and is computed from the master key κ through a key schedule algorithm. This algorithm is expected to be very efficient, in this regard it is oftentimes linear.

Many block ciphers can be described as key-alternating block ciphers [START_REF] Daemen | The design of Rijndael[END_REF]. This construction consists in alternating a key addition with a key independent operation. Definition 1.2 (Key-alternating block cipher). A block cipher E is a key-alternating block ciphers if it can be written as a composition of the following form:

E κ = ARK κr • F r • • • • • ARK κ 1 • F 1 • ARK κ 0
where (F i ) 1≤i≤r is a family of permutations: round functions, ARK κ i corresponds to the addition of the subkey κ i to the internal state and (κ i ) 0≤i≤r is the family of round keys obtained from key schedule applied on the master key κ.

Block ciphers can be constructed in various ways. In practical applications, the block cipher often falls into one of the following categories:

• Feistel networks. This family of ciphers was born at IBM in the early 70s and designed by Feistel and Coppersmith. It will later become the basis of the Data Encryption Standard [START_REF] Diffie | Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard[END_REF]. The internal state of a Feistel network is decomposed into two parts of n/2 bits X = (L, R). The round function is based on a keyed function f :

F n/2 2 ×F k 2 → F n/2 2
and consists in applying the following transformation

: (L i+1 , R i+1 ) ← (R i , f (R i , κ i ) ⊕ L i .
In essence, the Feistel network is a process that allows the building of a n-bits permutation from a n/2-bits permutation. Some generalizations of this construction exist such as Lay Massey constructions [START_REF] Lai | A proposal for a new block encryption standard[END_REF] and generalized Feistel Networks.

• Substitution permutation networks (SPN). The SPN block ciphers have a round function that consists of two operations. The first one is the substitution layer and consists of the parallel application of a non-linear function called Sbox. The second one is the linear layer and consists of the application of a linear map to the internal state. In the end, the round function consists of the combination of a local complex transformation (substitution layer) with a simpler but global transformation (linear layer). The Advanced Encryption Standard [FIP01] is the most well-known example of an SPN cipher.

• Add-rotate-XOR (ARX) constructions. In ARX ciphers, the internal state is represented by dividing the n-bits into n/l registers of the same length l. Three basic operations can be performed: modular addition modulo 2 l , cyclic rotation, and XOR. Since these operations are very simple, the ARX constructions tend to be very efficient. SPECK [START_REF] Beaulieu | The SIMON and SPECK lightweight block ciphers[END_REF] is an example of an ARX cipher.

Later in this thesis, we will give precise descriptions of the block ciphers studied in applications (Section 6.4.1, Section 4.1, Section 5.2.1).

Other Constructions

Block cipher is not the only construction in symmetric cryptography, indeed stream ciphers, hash functions and Message authentication codes fulfill different tasks.

Stream Ciphers.

Stream ciphers are another class of constructions in symmetric cryptography that encrypt data in a continuous stream, typically one bit or one-word at a time. These ciphers generate a pseudorandom keystream, which is then combined with the plaintext to produce the ciphertext. Stream cipher algorithms are known for their efficiency, making them suitable for applications that require real-time encryption. They are often used when the size of the input cannot be determined in advance.

Hash Functions. Hash functions are cryptographic constructions that transform variable-sized input data into fixed-sized output, commonly referred to as a hash value or message digest. These functions play a crucial role in various cryptographic applications, including integrity checks, password hashing, and digital signatures. Hash functions have to provide collision resistance and preimage resistance, making them suitable for secure data integrity verification.

Message Authentication Codes (MAC).

Message Authentication Codes are constructions that ensure the integrity and the authenticated encryption of a message using a secret key. These codes generate a tag that is appended to the message and can be verified by the recipient using the same key.

Symmetric Cryptanalysis

In this section, we will present some basic elements of symmetric cryptanalysis. First, we will describe the models for block ciphers in which the attacker is considered to act and then we will present some well-known cryptanalysis families used to break symmetric constructions.

Cryptanalysis Models for Block Ciphers

In cryptanalysis, there are different models in which that characterize the possible actions of the adversary. In the following, we present some of them sorted from the weakest to the strongest.

• Ciphertext only. In cyphertext-only attacks, the attacker has access to several encrypted messages without any additional information on the associated plaintext or the encryption key.

• Known plaintext. In known-plaintext attacks, the attacker has access to pairs of messages that correspond to a ciphertext and its associated plaintext.

• Chosen plaintext. In a chosen-plaintext attack, the attacker has access to an encryption oracle that turns arbitrary plaintext into its corresponding ciphertext.

• Chosen ciphertext. In a chosen-ciphertext attack, the attacker has access to a decryption oracle that turns arbitrary ciphertext into its corresponding plaintext.

Adversary objectives can be very different from one case to another. In this section, we will consider the cases where the attacker aims either to build a distinguisher algorithm or a key recovery algorithm.

Distinguisher

Let us consider a block cipher E and suppose that the attacker can query an oracle that takes as input an n-bit message and returns a n-bit ciphertext. The goal of the attacker is to decide whether the oracle consists of the block cipher E using a secret key k (hence a permutation of the form E k ) or if it is a random permutation.

Chapter 1. Preliminaries Definition 1.3 (distinguisher). In cryptanalysis, a distinguisher for a cipher E is an algorithm that solves the following problem: Data: A data set D composed of pairs (P i , C i ) i obtained through oracle calls Question: Do the pairs correspond to plaintext-ciphertext pairs generated by E or randomly?

Key recovery

In this setting, the attacker has access to an encryption oracle using the secret key: E k . Hence, the attacker can build chosen pairs of plaintext-ciphertext (P, C) and will attempt to extract information on the secret key using them. The goal of the attacker is to recover this key k significantly faster than the exhaustive search.

Exhaustive Search. For a given pair of plaintext-ciphertext (P, C), one can perform an exhaustive search to recover the key( Algorithm 1.1). This procedure exists for all ciphers and has a time complexity of |K|. In symmetric cryptanalysis an algorithm that manages to recover the key faster than the exhaustive search is an attack.

Algorithm 1.1 Exhaustive Search D ← {(P, C) : C = E k (P )} Data setup for κ ∈ K do if E(P, κ) = C for all (P, C) ∈ D then return κ
The efficiency of an attack is measured by three types of complexities:

• Time complexity. The time complexity of an attack is the time complexity of the algorithm that describes the attack. Oftentimes, the time complexity unit of measure is the encryption time, since the exhaustive search consists in performing |K| • |D| encryptions, it facilitates the comparison.

• Memory complexity. The memory complexity of an attack is the memory complexity of the algorithm that describes the attack.

• Data complexity. The data complexity of an attack is the number of times the attack queries the encryption oracle.

From distinguisher to key recovery. Using distinguishers, it is possible to build key recovery attacks. Indeed, by surrounding a distinguisher for a reduced-round version of the cipher with key recovery rounds, we can recover the key as the good key will be the one implying the non-random property exhibited by the distinguisher as depicted in Section 1.3.1.2. More formally, let us assume we have a data set D of pairs of plaintext-ciphertext. For each key guess κ (note that we only need to guess the key bits involved in the key recovery rounds), we can compute the value of the internal state at the input and the output of the distinguisher for all the pairs of data set D, Related key cryptanalysis. Related-key cryptanalysis is a method used to break cryptographic systems by exploiting relationships between keys. It involves analyzing the behavior of a cryptographic algorithm when different keys are used, especially when these keys are related in some known way. By studying the patterns and vulnerabilities that emerge from these relationships, an attacker can potentially recover the secret key or weaken the security of the system though this is a model where attacks have more freedom. This model is particularly useful while analyzing the security of a hash function built on a block cipher (using Merkle Damgard construction [START_REF] Charles | Secrecy, authentication, and public key systems[END_REF] for instance).

Cryptanalysis Families

In this section, we will present some well-known cryptanalysis families: Linear cryptanalysis and Meet-the-Middle cryptanalysis. Differential cryptanalysis will be studied later in Chapter 2.

Linear Cryptanalysis

Linear cryptanalysis is a powerful method used to analyze and exploit the linearity properties of cryptographic algorithms. It relies on finding linear approximations that hold with high probability, that can be derived into a linear distinguisher and thus allowing attackers to deduce information about the secret key by performing a key recovery attack. Linear cryptanalysis has been successfully applied to various symmetric key algorithms, highlighting the importance of designing ciphers resistant to this type of attack. The two fundamental algorithms in linear cryptanalysis were introduced by Matsui [START_REF] Matsui | Linear Cryptanalysis Method for DES Cipher[END_REF] who described an attack on the well-known DES.

Chapter 1. Preliminaries Definition 1.4 (Keyed Linear Approximation). Let E be a block cipher, a keyed linear approximation of E is a map:

ν : α, P + β, C + γ, k
where P, C denotes a pair of plaintext ciphertext and k the key. The vectors

α ∈ F n 2 (respectively β ∈ F n 2 , γ ∈ F k 2
) is called the input (respectively output and key) mask.

Definition 1.5 (Bias and Correlation). Let ν be a linear approximation of the block cipher E, its bias is the quantity:

= P P,k (ν(P, E k (P ), k) = 0) - 1 2 .
The correlation is

c = P P,k (ν(P, E k (P ), k) = 0) -P P,k (ν(P, E k (P ), k) = 1).
From the definition, it is possible to see that c = 2 .

Linear Distinguisher. A linear distinguisher consists in exhibiting a linear approximation whose underlying correlation (or bias) is non-negligible. Matsui described some procedures in [START_REF] Matsui | Linear Cryptanalysis Method for DES Cipher[END_REF] that allow to construct linear approximations. Indeed, the piling-up lemma describes how to combine linear approximations over a small part of a cipher (for instance one round) into an approximation over a larger part of the cipher as explained in Corollary 1.1.

Corollary 1.1. Let E be a R rounds key alternating block cipher where (F i ) 1≤i≤r denotes the family of round functions, (κ i ) 0≤i≤r denotes the family of round keys and (X i ) 0≤i≤r denotes the internal state after round ARK i (hence X 0 corresponds to the plaintext).

For each round, if we have a linear approximation of the form:

ν i : α i-1 , X i-1 + α i , X i + α i , κ i
with bias i . Then by adding all the linear approximations, we obtain the following approximation on E:

ν : α 0 , X 0 + α r , X r + r i=1 α i , κ i
If the rounds are statistically independent then the bias of ν is = 2 r-1 r i=1 i .

Later in [START_REF] Matsui | The first experimental cryptanalysis of the Data Encryption Standard[END_REF], Matsui also described the branch and bound algorithm that looks for a linear approximation with a high correlation. It consists in recursively building linear approximations while incrementing the number of rounds explored.

Linear Key recovery. In [START_REF] Matsui | Linear Cryptanalysis Method for DES Cipher[END_REF], Matsui proposed two different algorithms (Algorithm 1.2 and Algorithm 1.3) to perform key recovery based on a linear distinguisher. In both cases, we suppose that the attacker has access to a collection of pairs of plaintextciphertext D = {P, C : E k (P ) = C} and knows the existence of a linear approximation ν : α, P + β, C + γ, k .

In Algorithm 1.2, the attacker computes the counter T = |{(P, C) ∈ D : α, P + β, C = 0}| and deduces the value of γ, k based on the value of T and . This method recovers only one key bit unlike the method developed in Algorithm 1.3 that can recover many more key bits. This second method consists in building a key recovery attack based on a linear distinguisher as explained in the previous section. Hence, we start by splitting the cipher into two parts E = E out • E in . Without loss of generality, the linear distinguisher ν considered affects the top part: E in . The idea here is to compute D κ = {(P, E -1 out (C, κ)) : P, C) ∈ D} for any possible guess of key κ and check which key guess has the largest empirical bias concerning ν. This key guess is the key used during encryption.

Algorithm 1.2 Matsui's Algorithm 1 T ← 0 Counter Initialisation for (P, C) ∈ D do if α, P + β, C = 0 then T ← T + 1 if T > N/2 then return < 0 if true 1 else 0 else return > 0 if true 1 else 0 Algorithm 1.3 Matsui's Algorithm 2 for κ ∈ K do T κ ← 0 Counter Initialisation for (P, C) ∈ D do if α, P + β, E -1 out (C, κ) = 0 then T κ ← T κ + 1 return argmax κ (|T κ -N/2|)
Matsui introduced linear cryptanalysis but this field has a lot of potential and new techniques in linear cryptanalysis still emerge, such as linear hull [START_REF] Nyberg | Linear approximation of block ciphers[END_REF], multidimensional linear cryptanalysis [KR94; BDQ04] and Walsh transform key recovery [START_REF] Flórez-Gutiérrez | Optimising linear key recovery attacks with affine Walsh transform pruning[END_REF] only to cite a few.

Meet-in-the-middle Cryptanalysis

Meet-In-The-Middle attacks were introduced by Diffie and Hellman in 1977 [START_REF] Diffie | Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard[END_REF]. This widely used technique consists in computing some internal state in the middle of the cipher from both the input and the output without needing the whole key to perform either of these computations. To recover key bits, the attacker keeps track of the keys leading to a collision in the middle state.

More precisely, let E be an n-bit block cipher with r rounds and let (P, C) denote a pair of plaintext/ciphertexts. We write E = E out • E in , as in Figure 1.2, where E out and E in have r out and r in rounds respectively (r = r in + r out ). We denote by K in (respectively K out ) the set of key bits required in the computation of E in (respectively

E out ). Algorithm 1.4 Meet-In-The-Middle attack T ← Empty table Table Initialisation S ← ∅ Solution Set Initialisation for k in ∈ K in do M in ← E in (P, k in ) T [hash(M in )] ← k in for k out ∈ K out do M out ← E out (C, k out ) if T [hash(M out )] is not empty then S ← S ∪ {k in , k out } return S
Algorithm 1.4 describes the Meet-In-The-Middle procedure. Since this attack can be performed in the encryption or the decryption direction, without loss of generality, we can suppose that

|K in | ≤ |K out |. The size of the table is set to |T | = |K in |, therefore the memory complexity is M = |K in |.
Since the algorithm consists of a first loop over K in and a second loop over K out , the time complexity is

T = |K in | + |K out |.
The cryptographic community proposed many improvements to this generic attack, such as the technique of guessing some bits of the internal state [START_REF] Orr Dunkelman | Improved Meet-in-the-Middle Attacks on Reduced-Round DES[END_REF], the all-subkeys approach [START_REF] Isobe | A Single-Key Attack on the Full GOST Block Cipher[END_REF], splice-and-cut [AS08; AS09; Guo+10] and bicliques [START_REF] Khovratovich | Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 Family[END_REF]. In the following, we will present the improvements proposed in [START_REF] Bogdanov | A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN[END_REF] and [START_REF] Canteaut | Sieve-in-the-Middle: Improved MITM Attacks[END_REF]: partial matching, sieve-in-the-middle. Partial matching is a technique that generalizes the meet-in-themiddle technique. Indeed, instead of matching on the whole state in the middle, we will now allow matching on a substate composed of fewer bits (see Figure 1.3). Computing this subspace might involve fewer key bits, hence reducing the size of K in and K out , therefore reducing the overall complexity of the meet-in-the-middle procedure.

Sieve-in-the-middle Sieve-In-The-Middle is a technique that takes partial matching a step further and matches through a non-linear function by sieving noncompatible pairs. As represented in Figure 1.4, this technique consists first in splitting the cipher into three parts: input part, middle part, and output part. The input part (respectively output part) consists in a subcipher E in (respectively E out ). We denote by U (respectively V) a subspace of E in (K, P ) (respectively E out (K, C) and K in (respectively K out ) the key bits involved in the computation of the restricted function

E in | U (respectively E out | V ). The middle part consists of a keyed function S such that S : K mid × U → V.
Now, it is possible to discard every guess (k in , k out ) that produces a pair (u, v) that can not match through S. Hence, by precomputing the relation R as follows

R(u, v) ⇔ ∃k mid ∈ K mid s.t. S(k mid , u) = v
we can sieve the pairs (u, v), therefore the pairs (k in , k out ). The Algorithm 1.5 summarizes the procedure of a Sieve-In-The-Middle attack.

Chapter 1. Preliminaries Algorithm 1.5 Sieve-In-The-Middle attack

L in ← ∅ Input Table Initialisation L out ← ∅ Output Table Initialisation L sol ← ∅ Soltion Set Initialisation for k in ∈ K in do Forward computation u ← E in | U (k in , P ) L in ← L in ∪ {(u, k in )} for k out ∈ K out do Backward computation v ← E out | V (k out , C) L out ← L out ∪ {(v, k out )}
Merge L in and L out with respect to R and return the merged list

L sol Merge step for k such that (k in , k out ) ∈ L sol do if E k (C) = P then return k

Preliminaries of Quantum Computing

Some asymmetric cryptographic algorithms such as RSA happen to be vulnerable to quantum attacks. It raises the following question: does the development of quantum computers threaten the security of symmetric cryptography? To answer this question, we first need to understand the functioning of a quantum computer and then try to perform cryptanalysis using quantum algorithms to attack the current symmetric primitives.

In this section, we first provide some notions of quantum computing useful in this thesis (Chapter 6): we introduce the quantum circuit model, notions of quantum complexity, quantum-accessible memory, and some of our quantum computing tools. We also define the two quantum attacker scenarios commonly found in the literature.

Quantum Computing Notions

In this thesis, we use the abstract model of quantum circuits which is the quantum analogous to the Turing machine. Definition 1.6 (Quantum State). The state of a quantum system is an element of an N -dimensional Hilbert space of norm 1. The states that compose the orthonormal basis of the Hilbert space are referred to as pure states: (|e i ) 0≤i≤N -1 . Therefore, each quantum state can be represented as a superposition over the pure states:

|ψ = N -1 i=0 α i |e i
where (α i ) 0≤i≤N -1 is a family of complex numbers called amplitude such that i |α i | 2 = 1. The smallest element of quantum information is called qubit and corresponds to a quantum state in dimension 2. Any quantum state can be described by a set of qubits.

Proposition 1.1 (Measurement). Measuring a quantum system |psi = j α j |e j yields |e j with probability |α j | 2 . This action makes the system collapse to |e j .

If the measurement of a quantum |ψ state has an effect on another quantum state |φ , we say that |ψ and |φ are entangled. To perform computation on quantum states, we can use unitary operators. Definition 1.7 (Unitary operators). In quantum computing, a unitary operator is a matrix U ∈ M N,N (C) such that U † × U = I where U † is the conjugate transpose of U . The action of an operator U on a quantum state |ψ = N -1 i=0 α i |e i results in a quantum state whose amplitude corresponds to the vector U

• (α 0 • • • α N -1 ) t .
In practice, the operators considered are built from quantum gates, analogous to classical logic gates, we refer to [De 19] for a precise description of quantum gates. A quantum circuit consists in applying elementary quantum gates to a quantum state. The width of the circuit (number of qubits) is the memory complexity of the algorithm. The depth of the circuit can be thought of as its wall-clock time, and the number of gates as the time complexity since it represents the total number of operations applied.

Quantum attacker scenarios.

Following a standard terminology [START_REF] Kaplan | Quantum Differential and Linear Cryptanalysis[END_REF], we define two scenarios. In the Q1 setting, the attacker has access to a quantum machine for accelerating his computations but has only access to a classical cryptographic oracle: the black box E can only be queried classically. In the Q2 setting, the attacker can, in addition, encrypt arbitrary quantum states using a quantum embedding O E of E which operates: |x |0 → |x |E(x) .

Quantum memory.

We will consider three types of memory: (1) classical memories with classical random access; (2) quantum circuits with large amounts of qubits; (3) large amounts of qubits with quantum random access. The latter is named QRAQM in [START_REF] Kuperberg | Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem[END_REF]. It can be modeled as the addition, to the quantum circuit model, of a "qRAM gate" (see e.g. [START_REF] Ambainis | Quantum Walk Algorithm for Element Distinctness[END_REF]) which performs the equivalent of a classical memory access, read or write, but in superposition. Implementing a qRAM gate with only standard quantum gates would require a time proportional to the number of qubits in the circuit. The QRAQM model assumes that the qRAM gate is given as an additional basic gate (thus costing quantum time 1, if "time" is taken as the number of gates). This powerful memory model is used to obtain optimal time complexities in many advanced quantum algorithms, e.g., collision finding for the limited birthday problem [START_REF] Ambainis | Quantum Walk Algorithm for Element Distinctness[END_REF][START_REF] Bonnetain | Finding many Collisions via Reusable Quantum Walks[END_REF]. The results of this paper, notably the quantum pair filtering algorithm of Section 6.2, require large amounts of qubits, but not necessarily QRAQM. We will indicate whether this is the case.

Quantum Search

In Chapter 6, we will use Grover's algorithm [START_REF] Lov | A Fast Quantum Mechanical Algorithm for Database Search[END_REF] and its generalization from [START_REF] Brassard | Quantum amplitude amplification and estimation[END_REF], amplitude amplification, that we will regroup under the name quantum search. In this Apply O f 5:

Apply H ⊗n 6:

Apply O 0 7:

Apply H ⊗n 8: EndRepeat section, we will describe Grover's search algorithm.

We mostly use the simple setting of Grover search, where we are given a function f : {0, 1} n → {0, 1} and we want to find y such that f (y) = 1. If we have an implementation of the unitary This chapter is organized as follows: first, we will introduce the main cryptanalysis technique studied in this thesis: Differential Cryptanalysis. Then, we will describe two of its variants: Impossible Differential Cryptanalysis and Differential-linear Cryptanalysis.

O f : |x → (-1) f (x) |x ,

Differential Cryptanalysis

Differential cryptanalysis is arguably the most well-known and studied technique in symmetric cryptography. Indeed, in the last 30 years, differential attacks have been applied to analyze a high number of primitives: [BS91a; BS91b; BS92; Bih+01; Wan08; BG11; Can+14; Leu16b], to cite only a few. This technique consists in exploiting the propagation of differences through some part of a cryptographic construction. In the context of block ciphers, the attacker can use differential cryptanalysis to build both distinguishers and key recoveries.

Several refinements and generalizations of the basic technique were introduced together with some new dedicated methods. One can for example mention the technique of truncated differentials [START_REF] Knudsen | Truncated and Higher Order Differentials[END_REF], the use of structures to reduce data complexity (a technique already introduced in [BS92]), the technique of probabilistic neutral bits [START_REF] Rai | Differential Cryptanalysis of Salsa and ChaCha -An Evaluation with a Hybrid Model[END_REF] or the conditional differential attacks [START_REF] Knellwolf | Conditional Differential Cryptanalysis of NLFSR-Based Cryptosystems[END_REF]. In addition, differential Chapter 2. Differential cryptanalysis cryptanalysis is the basis of newer cryptanalysis techniques such as: boomerang and rectangle cryptanalysis [START_REF] Wagner | The Boomerang Attack[END_REF], impossible differential cryptanalysis [Knu98; BBS99], differential-linear cryptanalysis [LH94] etc.

Differential Dinstinguisher

The purpose of this section is to provide a definition for differential distinguishers as well as give insight on the process constructing them. To complete this task, we will begin by presenting some preliminary definitions needed for describing differential cryptanalysis.

Definition 2.1 (Differential). Let f : F n 2 → F n 2 be a boolean function. A differential is a pair of input and output differences (∆ in f -→ ∆ out ) ∈ F n 2 × F n 2 .
We call differential probability of (∆ in f -→ ∆ out ) the following quantity:

DP (∆ in f -→ ∆ out ) = P x∈F n 2 [f (x ⊕ ∆ in ) ⊕ f (x) = ∆ out ] .
For a given block cipher E, any differential (∆ in E -→ ∆ out ) with an underlying probability significantly higher than what we would get with a random permutation can be exploited to build a differential distinguisher. Indeed we can distinguish the cipher from a random permutation by empirically computing the differential (∆ in E -→ ∆ out ) as depicted in Algorithm 2.1.

Algorithm 2.1 Differential distinguisher

Require

: (∆ in , ∆ out ) a differential for f , X ⊂ F n 2 set of (DP (∆ in f -→ ∆ out )) -1 elements 1: for x ∈ X do 2: ∆ ← f (x) ⊕ f (x ⊕ ∆ in ) 3: if ∆ = ∆
T [i][j] = |{x : f (x) ⊕ f (x ⊕ i) = j}|
To understand how we can derive a differential for a cipher using a differential of its inner parts, we introduce the following definition. Definition 2.3 (Differential Characteristic). Let's consider a family of r functions (f i ) 1≤i≤r : F n 2 → F n 2 and let F denote the concatenation of this family:

F = f r •• • ••f 1 . A differential characteristic is a family of r+1 differences (δ 0 f 1 -→ δ 1 f 2 -→ • • • fr -→ δ r ) ∈ (F n
2 ) r+1 . We call differential probability of the differential characteristic the following quantity::

DP ((δ 0 f 1 -→ δ 1 f 2 -→ • • • fr -→ δ r )) = P x∈F n 2 (∩ r i=1 [f i • • • • • f 1 (x ⊕ δ 0 ) ⊕ f i • • • • • f 1 (x) = δ i ]) .
Under some independence assumption between each function f i , the overall differential probability of the differential characteristic can be decomposed as the product of the differential probability of all its composing functions:

DP (δ 0 f 1 -→ δ 1 f 2 -→ • • • fr -→ δ r ) = r-1 i=0 DP (δ i f i+1 ---→ δ i+1 )
In the general case, there is no reason that the random variable X i (that represents the internal state associated to δ i ) is independent to some X j for j = i. However in the case of key-alternating block cipher, the round function features a key addition layer that brings randomness to the internal state and oftentimes, we can derive the independent hypothesis from this addition. Nonetheless, if the key addition brings does not randomness on the whole state (for instance the key addition does not all concern the bits of the internal state) then the independence hypothesis might not hold.

In practice, it is possible to derive a differential characteristic for some rounds of a block cipher by concatenating 1-round differentials (as it is the case in Chapter 4). With a large collection of differential characteristics that coincide both in input and output difference, we can derive the probability of the differential for the whole cipher.

Property 2.1. Let's consider a family of r functions

(f i ) 1≤i≤r : F n 2 → F n 2 and F = f r • • • • • f 1 . For a differential (∆ in F -→ ∆ out ), the differential probability is: DP (∆ in F -→ ∆ out ) = δ 1 ,••• ,δ r-1 ∈F n 2 DP (∆ in f 1 -→ δ 1 f 2 -→ • • • fr -→ ∆ out )
In practice, computing all the differential characteristics associated to a differential is infeasible as soon as more than a few rounds are considered. However, most of them have negligible probability compared to the main one. Hence by considering a reasonable subset of differential characteristics, we can expect to get a reasonable approximation of the value of the differential probability.

Differential Attack

In this section, we follow the framework described in Section 1.3.1.2 and show how to build a key recovery attack using a differential distinguisher. We will begin by extending the differential considered here into key recovery rounds by using truncated differentials.

F n 2 → F n 2 be a boolean function. A truncated differential is a pair of differences subset (D in , D out ) ⊂ F n 2 ×F n 2 .
The differential probability associated to this truncated differential is:

DP (D in f -→ D out ) = P x⊕y∈D in [f (x) ⊕ f (y) ∈ D out ]
We start by considering a cipher E that is the composition of three subciphers

E = E out • E ∆ • E in such that E in (respectively E ∆ , E out ) consists of r in rounds (respectively r ∆ , r out ). Let's now suppose that (∆ in E ∆ --→ ∆ out ) is a differential of probability 2 -p .
Extending the differential with truncated probability 1 in both directions consists in considering two truncated differentials:

({∆ in } E -1 in ---→ D in ) and ({∆ out } Eout ---→ D out )
. D in and D out often consist of two linear subspaces of F n 2 derived from subsets of active bits. We denote by d in and d out the quantities such that |D in | = 2 d in and |D out | = 2 dout . Let K in denote the space of subkeys involved in E in , typically a subset of information bits of the key, and K out be the space of subkeys involved in E out . Finally, let K in∪out be the space of subkeys involved both in E in and E out . In general K in∪out is smaller than K in × K out due to key-schedule relations.

Data Generation

The first step of the attack is called: Data Generation and consists in making calls to the encryption oracle. Without loss of generality, we can assume that the attack is done in the encryption way (rather than the decryption way) since it suffices to consider E -1 instead of E. In this section, we will assume that D in is a subspace of F n 2 of dimension d in .

Definition 2.5 (Structure). A structure S ⊂ F n 2 associated to D in is a set of plaintexts such that:

x, y ∈ S × S ⇒ x ⊕ y ∈ D in

Differential Cryptanalysis

21

A structure is an affine subset of F n 2 of dimension dim(S). Therefore, it is possible to build 2 2 dim(S) pairs within a structure. When omitting the repetitions, we obtain a total of 2 2 dim(S)-1 pairs.

To estimate the amount of data required to mount the attack, we consider the overall differential probability.

DP (D in E in --→ {∆ in }) • DP (∆ in E ∆ --→ ∆ out ) • DP (∆ out Eout ---→ {D out }) The probability DP (D in E in --→ {∆ in }) = 2 -c in
can be characterized by the number of conditions c in that we need to verify (the number of conditions c out can also be defined similarly). In practice, we often remark that c in = d in , in this case, the overall probability is 2 -p-d in . Therefore, we need to generate 2 p+d in pairs by using 2 s structures of size at most 2 d in . Therefore,

p + d in =s + 2 dim(S) -1 ⇔ s =p + d in -2 dim(S) + 1.
At that point, we need to consider two scenarios:

• p ≥ d in -1. In this case, one structure does not contain enough data to mount our attack. Hence, we need to consider 2 p-d in +1 different structures of size 2 d in to mount our attack. The complexity of this first step consists in the product of the number of structures considered times the size of these structures: C Data = 2 p+1 .

• p < d in -1. In this case, considering a structure of size 2 d in would generate more data than what is needed. Hence, it is enough to consider one resized structure of size 2 p+d in +1 2

to mount the attack. The complexity of this first step consists of the size of the structure considered:

C Data = 2 p+d in +1 2 . Theorem 2.1 ([BS91a]
). The complexity of the Data Generation step of a differential attack is given by the following formula:

C Data = max 2 p+1 , min d∈{d in ,dout} 2 p+1+d 2
This theorem can be derived from the study of the two scenarios depicted above. The min over d in and d out appears since it is possible to consider the cipher in the encryption or the decryption direction depending on what is the most interesting. The memory complexity of a differential attack consists of the size of the structure considered. Indeed, all the rest of the attack can be performed on the fly.

Pair Sieving

We now describe the second step of differential cryptanalysis: Pair Sieving. The goal of this step is to build differential pairs whose plaintext difference is in D in and ciphertext Chapter 2. Differential cryptanalysis difference is in D out . This step follows the Data generation step in which data was generated using structures following D in . Hence we already know that two plaintexts will follow D in if and only if they belong to the same structure. Therefore, we store the data in a table and sort them according to their ciphertext value. Hence, we can efficiently check if two elements only differ on the d out bits by checking that there is no difference on the n -d out other bits.

To estimate the number of differential pairs that we will be able to build, we consider the restriction of E to the complementary set of D out : F n 2 \ D out . Since we expect this restriction to behave like a random function, we can state that:

P [E(x) ⊕ E(x ⊕ δ) ∈ D out ] = P E| F n 2 \Dout (x) = E| F n 2 \Dout (x ⊕ δ) = 2 -(n-dout)
Therefore, from the 2 p+d in possible pairs generated from the first step, we keep a 2 -(n-dout) proportion of them. Hence, we are left with N = 2 p+d in +dout-n differential pairs, that we store in a table T 0 . Some more optimizations could be performed at this stage of the attack, an example is given in Section 4. Indeed, we could refine the sets D in and D out to reduce their size, hence reducing the number of differential pairs. Note that this size update cannot be done earlier since we want our sets D in and D out to follow a certain shape so that we can use structures based on them to efficiently perform the data generation step.

Key Recovery

We now move on to the final part of the differential cryptanalysis: the Key Recovery. The main idea of this step is to perform some key guesses (sequentially or in parallel) to perform a partial encryption through E in and E out by performing key guesses on K in∪out . Then we expect to witness a pair that satisfies the differential if and only if the key guesses performed are right. By following the framework presented in Section 1.3.1.2 to build a key recovery attack from a distinguisher, we would obtain Algorithm 2.2. In the context of differential cryptanalysis, we can recover the key more efficient techniques as shown in []. Such a technique is called the early abort and was introduced in [].

Early abort. In this technique, we want to consider all propagation conditions (ex: S-box conditions, MixColumns conditions, etc.) that allow a pair to propagate through the truncated differential from the plaintext (or ciphertext) to the differential in the middle. We will denote by L c the list of these conditions. For each condition c ∈ L c , we denote by K(c) the set of keys required to verify the propagation of this condition. In Algorithm 2.3, we give a high-level description of how early abort should proceed.

In essence, we want to consider sequentially all the conditions c ∈ L c . Then, we guess the key bits that remain unknown to check whether the condition c is verified for each element stored in data. Then we keep the elements that verify the condition together with the associated key guess, the other elements are discarded. In the end, we Algorithm 2.2 Naive Key Recovery Require: P a set of differential pairs

1: for κ ∩ ∈ K ∩ do 2: for κ in ∈ K in \ K ∩ do 3: for κ out ∈ K out \ K ∩ do 4:
for (p 1 , p 2 ) ∈ P do 5:

δ in ← E in (p 1 , κ ∩ , κ in ) ⊕ E in (p 2 , κ ∩ , κ in ) 6: δ out ← E -1 out (c 1 , κ ∩ , κ output ) ⊕ E -1 out (c 2 , κ ∩ , κ out ) 7: if δ in = ∆ in and δ out = ∆ out then 8: return κ ∩ , κ in , κ out Algorithm 2.3 Sequential Early Abort Require: P a set of differential pairs, L c a list of condition 1: L k ← ∅ Set of known keys 2: D ← P Initialization of our data 3: for c ∈ L c do 4: K ← K(c) \ L k
Set of key bits we do not know yet Regarding the complexity, let g i denote the number of bits that remain to be guessed for the i-th condition and 2 f i denote the proportion of data discarded when verifying the i-th condition.

C KR = |P| • 2 g 0 + 2 g 0 -f 0 (2 g 1 + 2 g 1 -f 1 (• • • (2 g |Lc|-1 ) • • • )) = |P| • |Lc|-1 i=0 2 g i • 2 i-1 j=0 g i -f i
When looking at the formula for the complexity of early abort, it is possible to notice that the order in which the conditions of L c are considered has an impact on this complexity. Finding the optimal order is a challenging task and is still an active domain of research. In addition, some other techniques allow to perform parallel key guessing, hence resulting in a speedup for the complexity of the key recovery (see example in Section 4.3).

To summarize this section, we gather in the following theorem the complexities associated to differential cryptanalysis Chapter 2. Differential cryptanalysis Theorem 2.2 (Differential Cryptanalysis Complexity). The complexities of a differential attack are:

• Data. The data complexity corresponds to the number of calls to the encryption oracle done in the pair generation step.

C Data = max 2 p+1 , min d∈{d in ,dout} 2 p+1+d 2
• Memory. The memory complexity corresponds to the size of the structure used in the attack.

C M emory = min min d∈{d in ,dout} 2 d , min d∈{d in ,dout} 2 p+1+d 2
• Time. The time complexity of the attack is the sum of the time complexities of the three steps.

C T ime = C Data + 2 p+d in +dout-n + 2 p+d in +dout-n • C KR
where C KR denotes the complexity of the key recovery for one pair.

Impossible Differential Cryptanalysis

In this section, we provide a generic depiction of impossible attacks, a variation of differential attacks that features a differential distinguisher with probability zero.

Principle

Impossible differential attacks were independently introduced by Knudsen [Knu98] and Biham, Biryukov, and Shamir [START_REF] Biham | Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials[END_REF]. The goal of this cryptanalysis technique is to recover some bits of the secret key of a black-box encryption oracle. This is done by discarding all the wrong key guesses, with the help of a pair of plaintexts that leads to an impossible pattern under its partial encryption with the wrong key guesses. An impossible differential attack is built similarly to a differential attack. The differential distinguisher is replaced by an impossible differential, that is, a pair of differentials ∆ in , ∆ out such that the probability that ∆ in propagates to ∆ out after r ∆ rounds is 0. Then, using truncated differentials, we will append r in and r out rounds of the cipher respectively before and after the impossible differential.

Assume that, we found a pair of plaintexts p = (x, y) such that x ⊕ y ∈ D in and

E k (x) ⊕ E k (y) ∈ D out .
Then, any key guess that leads to the impossible differential can be discarded, that is any key candidate κ that verifies:

E in (κ)(x) ⊕ E in (κ)(y) = ∆ in ) ∧ (E -1 out (κ)(E k (x)) ⊕ E -1 out (κ)(E k (y)) = ∆ out .
The goal of the attack is to discard as many keys as possible using many plaintextciphertext pairs. Similarly to differential attacks, impossible differential attacks can be represented in a three-step procedure: Data generation, Pair Sieving, Key Recovery.

Complexity

In this section, we provide both the data complexity and the time complexity of the impossible attack previously described in [START_REF] Boura | Scrutinizing and Improving Impossible Differential Attacks: Applications to CLEFIA, Camellia, LBlock and Simon[END_REF].

Number of Pairs.

In impossible differential attacks, the data complexity is determined by the number N of pairs in the table T 0 .

Considering a differential pair with input difference in D in and output difference in D out , we denote by c in the number of bit conditions for a pair to propagate to a difference of ∆ in at round r in , and c out the number of bit conditions to reach a difference of ∆ out at round r in + r ∆ . Hence, a pair propagates to the middle part both from the plaintext and the ciphertext with probability 2 -(c in +cout) . A given trial key k ∈ K in∪out is kept among the candidate keys with probability

P = 1 -2 -(c in +cout) N .
By applying log to both sides, we obtain

N = O log 1 P • 2 c in +cout .
Different trade-offs are therefore possible between P and N . A popular strategy, generally used by default is to choose N such that only the right key is left after the sieving procedure. This means P <

1 |K in∪out | therefore N = O 2 c in +cout • |K in∪out | .
Another way consists in taking P = 1 2 which removes half of the candidate keys.

Time Complexity.

The time complexity can be decomposed as the sum of the time complexity of the three steps. For each of these steps, we describe de time complexity associated.

Data Generation. In this step, we aim at generating enough data using structures to recover N pairs after the Pair Sieving step. The complexity of this problem was studied in [START_REF] Gilbert | Super-Sbox Cryptanalysis: Improved Attacks for AES-Like Permutations[END_REF] for the special case where N = 1:

C 1 = max min d∈{d in ,dout} √ 2 n+1-d , 2 n+1-(d in +dout) .
This is optimal if E behaves like a random permutation, as shown in [START_REF] Hosoyamada | Improved Attacks on sLiSCP Permutation and Tight Bound of Limited Birthday Distinguishers[END_REF]. A naive way to extend to N pairs would be to use this technique N times and get a complexity of N • C 1 . However, as shown in [START_REF] Boura | Scrutinizing and Improving Impossible Differential Attacks: Applications to CLEFIA, Camellia, LBlock and Simon[END_REF], with access to encryption and decryption oracles, it is possible to reduce this complexity to:

C N = max min d∈{d in ,dout} √ N 2 n+1-d , N 2 n+1-(d in +dout) .
Pair Sieving. This step is strait forward in this type of attack since it consists in gathering the N pairs using the data generated before. Hence its complexity both in time and memory is N .

Key Recovery.

The key recovery of impossible differential attacks can also be performed using early abort. However, in the context of impossible differential attacks, we will present another description of the key recovery algorithm since it suits better the transition towards quantum impossible differential attacks presented in Chapter 6. We formalize the key recovery step using test functions. Let us assume that K in∪out can be decomposed as

K in∪out = K 1 × K 2 × • • • × K ,
where K 1 , . . . , K typically represent choices for some bits of the subkeyspace. Together with this decomposition, we will have test functions:

T i : T 0 × K 1 × . . . × K i → {0, 1} (p , k 1 , . . . , k i ) → T i (p, k 1 , . . . , k i ) .
The test functions formalize the concept of condition presented in Section 2.1.2.3. Indeed each test function T i takes some part of the subkey, some part of the pair, and checks whether they meet some condition. Typically, we start from the differences D in and D out and compute partially the first and last rounds; the successive T i check that the partial encryption and decryption of the pair satisfies a truncated differential pattern that ultimately leads to the differential (∆ in E ∆ --→ ∆ out ) at rounds r in and r out . Next, we define the set of pairs satisfying all the T i :

T (k) = {p ∈ T 0 | ∀i, T i (p, k 1 , . . . , k i ) = 1} .
Thus, the test functions are defined so that: T (k) = ∅ if and only if, there exists a given pair p ∈ T 0 such that k makes the differential appear for p. The computation of T (k) thus yields a procedure exhibiting the encryption key.

Impossible differential early abort. We describe generically the early-abort procedure in the context of impossible differential cryptanalysis. Given an ordering of the test functions, the early-abort strategy relies on the definition of intermediate tables: we do not compute directly T (k) for all key guesses k, and instead, we compute tables T i which depend on some partial key guess and are partially filtered with respect to a subset of the test functions.

Definition 2.6 (Intermediate Tables). Given a partial key guess

(k 1 , . . . , k i ) ∈ K 1 × . . . × K i , given the initial table T 0 of pairs, the intermediate table of (k 1 , . . . , k i ) contains
all the pairs satisfying the test functions which can be computed from (k 1 , . . . , k i ): , k i-1 ) . This allows us to exhibit the complete guesses (k 1 , . . . , k ) such that T (k 1 , . . . , k ) = ∅ by looping over the guesses k i and backtracking to previously computed tables, instead of recomputing them from the start.

T i (k 1 , . . . , k i ) := {p ∈ T 0 , T 1 (p, k 1 ) = 1, T 2 (p, k 1 , k 2 ) = 1, . . . , T i (p, k 1 , . . . , k i ) = 1} .

The early-abort technique (Algorithm 2.4) relies on the inclusion of intermediate tables

: ∀i ≥ 1, T i (k 1 , . . . , k i ) ⊆ T i-1 (k 1 , . . .

Algorithm 2.4 Early Abort for Impossible Differential Attacks.

Input: a table T 0 for the pairs Output: finds the only key k for which there is no invalidating pair

1: for all k 1 ∈ K 1 do 2: Build T 1 (k 1 ) = {p ∈ T 0 , T 1 (p, k 1 ) = 1} 3:
for all k 2 ∈ K 2 do 4:

Build T 1 (k 1 ) = {p ∈ T 1 , T 2 (p, k 1 , k 2 ) = 1} • • • 5: for all k ∈ K do 6: Sieve the table T -1 (k 1 , . . . , k -1 ) according to T , obtain T 7: If T = ∅, then return (k 1 , . . . , k ) • • •
For a given sequence of keys k 1 , . . . , k i , we define:

σ i = P p∈T 0 [T i (p, k 1 , . . . , k i ) = 1] .
This quantity σ i corresponds to the proportion of data that is filtered at each step, it corresponds to the exponential version of f i presented in Section 2.1.2.3 (i.e. σ i = 2 -f i ). In general, σ i can depend on the choice of the key, but in practice, the values are similar, and we can reason with the expectancy of σ i over all key choices (σ i E[k](σ i (k))). Then the sizes of the tables T 0 , . . . , T -1 are N, σ 1 N, . . . , ( -1 i=1 σ i )N . Assuming that each new table is built by enumerating the previous table, the time complexity of Algorithm 2.4, Chapter 2. Differential cryptanalysis hence the complexity of the key recovery step can be written as:

E 1 E 2 E 1 E 2 ∆ in ∆ m p q q Γ m Γ m Γ out Γ out
|K 1 |   N Build T 1 +|K 2 | σ 1 N + |K 3 | σ 1 σ 2 N + . . . + |K | -1 i=1 σ i N   = N |K 1 | + σ 1 |K 1 ||K 2 | + σ 1 σ 2 |K 1 ||K 2 ||K 3 | + . . . + -1 i=1 σ i i=1 |K i |

Differential-linear Cryptanalysis

Differential-Linear cryptanalysis was introduced in 1994 by Langford and Hellman [START_REF] Langford | Differential-Linear Cryptanalysis[END_REF]. This technique consists in building a distinguisher by combining a differential and a linear approximation. In the original work, the differential part was reduced to the cases of probability 1, and a generalization to other probabilities was given by Biham, Dunkelman, and Keller in [START_REF] Biham | Enhancing Differential-Linear Cryptanalysis[END_REF]. This technique is particularly useful when both correlations of linear approximations and probabilities of differential approximation decrease very fast when the number of round increase. Indeed, by combining a linear and a differential approximation allow, it is possible to derive a distinguisher on some large amount of rounds without witnessing a drastic reduction of the underlying correlation.

Differential-linear cryptanalysis is built using both differential and linear properties of the cipher. More precisely, suppose that the considered cipher E can be split into E = E 2 • E 1 (as depicted in Figure 2.3) such that:

• a differential distinguisher is applied to E 1 P x∈F n 2 [E 1 (x) ⊕ E 1 (x ⊕ ∆ in ) = ∆ m ] = p 2.3. Differential-linear Cryptanalysis 29 • a linear distinguisher is applied to E 2 cor y∈F n 2 [ Γ m , y ⊕ Γ out , E 2 (y) ] = q
Then, under the assumption that E 1 (X) and E 2 (X) are independent random variables, the following differential-linear distinguisher holds

cor x∈F n 2 [ Γ out , E(x) ⊕ Γ out , E(x ⊕ ∆ in ) ] = pq 2 Proof. If we assume that Γ m , y ⊕ Γ out , E 2 (y) and Γ m , y ⊕ ∆ m ⊕ Γ out , E 2 (y + ⊕∆ m )
are independent random variables and are 0 with probability 1+q 2 then

P y [ Γ m , y ⊕ Γ out , E 2 (y) ⊕ Γ m , y ⊕ ∆ m ⊕ Γ out , E 2 (y + ⊕∆ m ) = 0] =P y [ Γ m , y ⊕ Γ out , E 2 (y) = 0] P y [ Γ m , y ⊕ ∆ m ⊕ Γ out , E 2 (y + ⊕∆ m ) = 0] +P y [ Γ m , y ⊕ Γ out , E 2 (y) = 1] P y [ Γ m , y ⊕ ∆ m ⊕ Γ out , E 2 (y + ⊕∆ m ) = 1] = 1 + q 2 2 + 1 -q 2 2 = 1 + q 2 2
On the other hand, we can simplify the equation as follows

Γ m , y ⊕ Γ out , E 2 (y) ⊕ Γ m , y⊕∆ m ⊕ Γ out , E 2 (y+⊕∆ m ) = Γ m , ∆ m ⊕ Γ out , E 2 (y) ⊕ Γ out , E 2 (y+⊕∆ m )
Hence, depending on the sign of Γ m , ∆ m ,

P y [ Γ out , E 2 (y) ⊕ Γ out , E 2 (y + ⊕∆ m ) = 0] = 1 ± q 2 2
Assuming the independence between the differential approximation on E 1 and the linear approximation on E 2 , we obtain

P x [ Γ out , E(x) ⊕ Γ out , E(x ⊕ ∆ in ) = 0] =P [E 1 (x ⊕ ∆ in ) = E 1 (x) ⊕ ∆ m ] P Γ out , E(x) ⊕ Γ out , E(x ⊕ ∆ in ) = 0 E 1 (x ⊕ ∆ in ) = E 1 (x) ⊕ ∆ m +P [E 1 (x ⊕ ∆ in ) = E 1 (x) ⊕ ∆ m ] P Γ out , E(x) ⊕ Γ out , E(x ⊕ ∆ in ) = 0 E 1 (x ⊕ ∆ in ) = E 1 (x) ⊕ ∆ m =p 1 ± q 2 2 + (1 -p) • 1 2 = 1 ± pq 2 2 Therefore we can deduce cor x∈F n 2 [ Γ out , E(x) ⊕ Γ out , E(x ⊕ ∆ in ) ] = pq 2 .

Chapter 2. Differential cryptanalysis

As a consequence, an attacker can distinguish the cipher from a random permutation by preparing O(p -2 q -4 ) pairs of chosen plaintexts. This type of attack tends to be effective on ciphers in which the optimal differential probability and the optimal correlation decrease too fast with the number of rounds to be able to mount either of these attacks on their own. In practice, the independence assumption between E 1 and E 2 is sometimes not true, resulting in wrong estimates for the correlation. A solution to this independence assumption is to split E in three sub ciphers This chapter organizes as follows: first, based on ideas from [START_REF] Beierle | Improved Differential-Linear Attacks with Applications to ARX Ciphers[END_REF], we describe some first elements of optimization for the differential part of differential-linear attacks. Then, we will describe the improvement from [Bei+22]. Finally, we will give an example of an application on Chaskey.

E = E 2 • E m • E 1 and

Improving the differential-linear distinguisher

In [START_REF] Beierle | Improved Differential-Linear Attacks with Applications to ARX Ciphers[END_REF], the authors described a technique to improve differential-linear attacks and apply it to Chaskey and Chacha. Following this work, we further improved differentiallinear attacks in [Bei+22]. In this section, we will describe the technique introduced in [BLT20] that improves the correlation of a differential-linear distinguisher. Let's start by considering a cipher E on which we want to mount a differential-linear attack. Following Section 2.3, E is split into two parts E = E 2 • E 1 where

P x∈F n 2 [E 1 (x) ⊕ E 1 (x ⊕ ∆ in ) = ∆ m ] = p and cor y∈F n 2 [ Γ m , y ⊕ Γ out , E 2 (y) ] = q.
The core idea of this improvement is to change the sampling set to increase the probability of the differential part. For instance, we could consider the set:

X = {x ∈ F n 2 : E 1 (x) ⊕ E 1 (x ⊕ ∆ in ) = ∆ m } By sampling elements in X , we obtain P x∈X [E 1 (x) ⊕ E 1 (x ⊕ ∆ in ) = ∆ m ] = 1,
hence the associated differential-linear distinguisher has the following correlation:

cor x∈X [ Γ out , E(x) ⊕ Γ out , E(x ⊕ ∆ in ) ] = q 2
Although the probability of the differential part is 1, we can not use X in practice because its structure is rather complicated and also because it depends on the key. However, it might be possible to find a vectorial space U: neutral space such that

x ∈ X ⇒ x ⊕ U ⊂ X .
Therefore, given one element of x and a neutral space U, we can generate 2 dim(U ) good elements for free. Hence, once we have identified a neutral space U, there are two scenarios:

• |U | > q -4 . In this case, we have enough data to mount a differential-linear attack on E, see Section 3.1.1.

• |U | < q -4 . In this case, we lack data to mount the attack with one neutral space. Hence, a new approach needs to be considered, see Section 3.1.2

Differential-Linear Cryptanalysis with Neutral Space

In this section, we follow the ideas from [START_REF] Beierle | Improved Differential-Linear Attacks with Applications to ARX Ciphers[END_REF] and discuss how to improve the correlation of a differential-linear distinguisher given a neutral space U big enough to mount the attack, i.e |U | > q -4 . In Algorithm 3.1, we summarize the improved distinguisher, it first consists in picking a random element a ∈ F n 2 , then empirically

computing cor x∈a⊕U [ Γ out , E(x) ⊕ Γ out , E(x ⊕ ∆ in ) ] and compare it to q 2 . Complexity. Since cor x∈a⊕U [ Γ out , E(x) ⊕ Γ out , E(x ⊕ ∆ in ) ] = q 2 if
a ∈ X , our algorithm will succeed if the randomly chosen element in step 1 happens to be an element of X . On the other hand, since a ∈

X ⇔ [E 1 (a) ⊕ E 1 (a ⊕ ∆ in ) = ∆ m ], then P a∈F n 2 (a ∈ X ) = p, the algorithm should loop O(p -1
) times. Hence the complexity of the attack is O(p -1 q -4 ) compared to O(p -2 q -4 ) for the traditionnal differential-linear cryptanalysis.

Algorithm 3.1 Improved differential-linear distinguisher with neutral spaces

Require: U 1: a ← R F n 2 2: c ← cor x∈a⊕U [ Γ out , E(x) ⊕ Γ out , E(x ⊕ ∆ in ) ] Empirical computation 3: if c = q 2 then 4:
return Success 5: else 6:

Go to 1

Differential-Linear Cryptanalysis with Probabilistic Neutral Space

Following the ideas from [START_REF] Beierle | Improved Differential-Linear Attacks with Applications to ARX Ciphers[END_REF], we relax some hypotheses on the definition of a neutral space to increase its dimension, hence the data that we can generate. Indeed, we now want the probability P x∈X ,u∈U [x ⊕ u ∈ X ] = p to be high rather than equal to 1. In that case, the associated differential-linear distinguisher will have the following correlation:

cor x∈A [ Γ out , E(x) ⊕ Γ out , E(x ⊕ ∆ in ) ] = p q 2
Therefore, the data threshold will also increase to p -2 q -4 . Similarly to the previous section, Algorithm 3.2 describes an improved differential-linear distinguisher using probabilistic neutral spaces. Now, the complexity is O(p -1 p -2 q -4 ).

Algorithm 3.2 Improved differential-linear distinguisher with probabilistic neutral spaces Require:

U 1: a ← R F n 2 2: c ← cor x∈a⊕U [ Γ out , E(x) ⊕ Γ out , E(x ⊕ ∆ in ) ] Empirical computation 3: if c ≥ p q 2 then 4:
return Success 5: else 6:

Go to 1

Computing a Neutral Space

In this section, we will describe an algorithm that finds a neutral space defined in previous sections. It starts by considering some element u ∈ F n 2 and empirically compute

P x∈X [x ⊕ u ∈ X ].
Then if this probability is higher than some threshold (hence u is a neutral vector), we store it and repeat this process for another u ∈ F n 2 . Then, with the gathered elements, we can derive the vectorial space that they spawned and its basis.

Since looking at all the vectors of F n 2 would be too costly, we will look into the vectors of low hamming weight to build our basis. Hence, the elements obtained may spawn a neutral that is not the biggest. The Algorithm 3.3 describes the procedure that empirically computes the probability γ u = P x∈X [x ⊕ u ∈ X ] for u an element of hamming weight lower than some threshold w. Pick a random X and compute E 1 (X) and

E 1 (X ⊕ ∆ in ) 4: if E 1 (X) ⊕ E 1 (X ⊕ ∆ in ) = ∆ m then 5:
Increment s 6:

for u ∈ B(0, w) do 7: X ← X ⊕ u. 8: if E 1 ( X) ⊕ E 1 ( X ⊕ ∆ in ) = ∆ m then 9:
Increment c u 10: for u ∈ B(0, w) do 11:

γ u = c u /s 12: return (γ u ) u∈B(0,w)
For some probability threshold p T , we can consider the vectors that have an empirical probability γ u larger than p T and the vectorial space that they spawn. Let e 1 • • • e dim(U ) denote a basis of U, we can see that:

∀u ∈ U, P x∈X ,u∈U [x ⊕ u ∈ X ] ≥ dim(U ) i=1 P x∈X [x ⊕ e i ∈ X ] ≥ p dim(U ) T
By considering the case of p T = 1, U corresponds to a neutral space. In the case of p T < 1, we obtain a probabilistic neutral space of probability p dim(U ) T . In practice it would be better to compute and consider

dim(U ) i=1 P x∈X [x ⊕ e i ∈ X
] as bound for the probability since it is tighter. Nonetheless, it is important to note that the choice of basis influences the bound.

Using the Conditional Differential Framework for Finding Better Subspaces

The production of vectors in a neutral space can be achieved practically by following a process similar to the one used in conditional differential attacks. The basis elements of U, as defined in [START_REF] Knellwolf | Conditional Differential Cryptanalysis of NLFSR-Based Cryptosystems[END_REF], are referred to as freebits. These involve more complex relations derived from the differential paths, rather than just simple single-bit relations.

Improving the differential-linear distinguisher

35

Three types of conditions are presented in Sect.3.2 of[KMN10b]: type-0, which only involves public bits; type-1, which involves both secret and public bits; and type-2, which are conditions directly on the key bits. The freebits are the basis elements that do not affect type-1 conditions. These definitions allow for the improvement of previous attacks in two ways: by increasing the number of key bits recovered by the differential-linear attack using type-2 conditions, and by increasing the size of U using the freebits. This section provides some general ideas and hints for using this framework to improve the analysis of ARX constructions. In Section 3.3, we present a detailed example of how to determine additional key bits with type 2 conditions and how to increase the number of freebits with evolved relations for Chaskey. Note that some of the relations derived by this method could not have been found by Algorithm 3.2.

Conditional differential framework for differential-linear attacks

The conditional differential framework for differential-linear attacks can be improved in three ways using the definitions from [KMN10b, Sect. 3.2]:

1. By exhaustively testing the input values that maintain the type-1 conditions fixed to a specific value, we can increase the size of U. Indeed, if these conditions are assumed to be true, they will remain true for the entire sampling set. However, these tested bits are not entirely unconstrained since the type-1 conditions must remain fixed.

2. The consideration of a particular set of plaintexts to verify the differential path can involve presupposing information on the associated key bits or key bit relations. This information is given directly by conditions of type-2 and indirectly by conditions of type-1. This information can be utilized to recover more bits and reduce the complexity of the key-search part in the final rounds.

3. Combination of both: guessing some key bits, that might be useful for the linear part, and that simultaneously might allow to detect sampling bit relations that follow the path with probability 1.

Main ideas for exploiting the conditions on ARX

In the following, we outline some general concepts for utilizing conditions on ARX constructions. Rather than relying solely on single non-active bit flipping to define freebits, we can investigate the impact of flipping the parity of differences as extra sampling bits, when feasible. Hence, we will establish guidelines for flipping the parity of differences. We can distinguish various significant scenarios, and we present here four cases of particular interest:

(i) If a pair of differences is going to be erased after a modular addition, changing the parity of one will need changing the parity of the other.

(ii) If a bit difference is staying at the same position (and not propagating further) after a modular transition, changing its parity will not affect the transition. (iv) If two words are added with a difference in position i and in positions i and i + 1 respectively, and we want to absorb the differences after the modular additions, the carries of the previous positions will not affect the bits after position i. We can also change the parity of the three bits simultaneously, and the differences will still be absorbed, and the values will stay the same. Of course, all this might have an effect on further rounds, which will have, in turn, to be taken into account.

It is also useful to keep in mind that when we find multiple input bits that only affect the differential transitions through XOR operations, then swapping an even number of these bits won't affect the verification of the differential path. When considering carries, they can have a low probability of affecting transitions. One thing to note is that if there is a sum of two zeros at a specific position i, then the bits at lower positions will not affect the carries at higher positions. This means that if we guess a small number of key bits to fix two bits to zero, it may generate many more bits for the sampling part with probability one, only if they influence the differential path through these carries.

Application to Chaskey

The goal of this section is to present our improved attack on Chaskey. Indeed, we will show how the application of the new techniques presented in [Bei+22] resulted in increasing the dimension of U. Nonetheless, the improvements presented in [Bei+22] are not solely restricted to the differential parts since key recovery optimizations on the linear part are also presented. However, this chapter focuses on the differential aspect of this work (refer to [Bei+22] for the other improvements). First, we will describe the Chaskey specification, then we will apply our new algorithmic technique to compute some elements of U and finally, we will use the conditional differential technique to recover the missing elements of U.

(v r 0 , v r 1 , v r 2 , v r 3 ) w r 0 ← (v r 0 v r 1 ) ≪ 16 w r 1 ← (v r 1 ≪ 5) ⊕ (v r 0 v r 1 ) w r 2 ← v r 2 v r 3 w r 3 ← (v r 3 ≪ 8) ⊕ (v r 2 v r 3 ) v r+1 0 ← w r 0 w r 3 v r+1 1 ← (w r 1 ≪ 7) ⊕ (w r 1 w r 2 ) v r+1 2 ← (w r 1 w r 2 ) ≪ 16 v r+1 3 ← (w r 3 ≪ 13) ⊕ (w r 0 w r 3 ) return (v r+1 0 , v r+1 1 , v r+1 2 , v r+1 3 )

Chaskey Specfication

Chaskey [START_REF] Mouha | Chaskey: An Efficient MAC Algorithm for 32-bit Microcontrollers[END_REF] is a lightweight MAC algorithm whose underlying primitive is an ARXbased permutation in an Even-Mansour construction, i.e., Chaskey-EM. The permutation operates on four 32-bit words, i.e., the block size is 128 bits. In the version proposed in [START_REF] Mouha | Chaskey: An Efficient MAC Algorithm for 32-bit Microcontrollers[END_REF], the permutation employs 8 rounds. The round function is described in Algorithm 3.4 and depicted in Fig. 3.2. In [START_REF] Mouha | Chaskey: a MAC Algorithm for Microcontrollers -Status Update and Proposal of Chaskey-12[END_REF], the author proposed a version with an increased number of rounds (from 8 to 12), and this version is currently standardized in ISO/IEC 29192-6:2019. The designers claim security up to 2 80 computations as long as the data is limited to 2 48 blocks. In Fig. 3.2 and Algorithm 3.4, (v r 0 , v r 1 , v r 2 , v r 3 ) denotes the input of the rth round function, and (w r 0 , w r 1 , w r 2 , w r 3 ) denotes the state after applying the half round for (v r 0 , v r 1 , v r 2 , v r 3 ).

Overview of the Attack

We now describe the attack on Chaskey, we will start by giving a brief overview, then we will get into the details of the neutral space U.

γ j = 1 v 0 [8] ⊕ v 1 [8, 13] ⊕ v 2 [29] 4 v 2 [21, 29] ⊕ v 3 [21] v 0 [18, 21, 30] ⊕ v 1 [21, 26, 30] ⊕ v 2 [3, 26] ⊕ v 3 [26, 27] v 2 [15] ⊕ v 3 [15]
Similar to the previous differential-linear attack from [START_REF] Leurent | Improved Differential-Linear Cryptanalysis of 7-Round Chaskey with Partitioning[END_REF], the attack we presented in [Bei+22] first consists in dividing the cipher into three sub ciphers. For the 7-round attack, we used E 1 covering 1.5 rounds, E m covering 4 rounds, E 2 covering 0.5 rounds, and the key-recovery, i.e., the function F , is covering 1 round. We also presented a 7.5-round attack, where E 2 covers 1 round instead of 0.5 rounds. The differential characteristic and the linear trail are applied to E 1 and E 2 , respectively, while the experimental differential-linear distinguisher is applied to the middle part E m . Note that we focus the analysis on E 1 from the following subsection (details on the linear treatment of E 2 are given in [Bei+22]).

Finding More Neutral Vectors

Let's first recall the basis of U introduced in [START_REF] Beierle | Improved Differential-Linear Attacks with Applications to ARX Ciphers[END_REF] (see the first two-row blocks in Table 3.1). This initial basis was computed using Algorithm 3.3 with a weight w = 1. Here, the threshold of the probability is relaxed from 0.95 to 0.93, and v 3 [30] (in red) is newly added in the basis. If the Algorithm 3.3 was also able to find neutral elements with low weight, the conditional differential techniques provide us with elements with probability 1, which could not be found by the Algorithm since the weight of the vectors were bounded to restrict the computations (see the third-row block in Table 3.1). A linear subspace U, formed by elements that don't affect the output with probability 1, and whose dimension is 18 + 4 = 22 is finally used to attack 7-round Chaskey. In addition, all, i.e., 18 + 8 + 4 = 30, basis elements are used to attack 7.5-round Chaskey.

In the following section, we provide the details on how to obtain these relations. We use the conditional differential framework and Fig. 3.3 to recover for free the value of some key bits and also to find additional bits of information for sampling and increase the 3.3. Exploiting the Conditions for Finding Chaskey Relations dimension of U from 18 as given in [START_REF] Beierle | Improved Differential-Linear Attacks with Applications to ARX Ciphers[END_REF] (and involving exclusively one-bit relations) to 22, or 23 if one-bit relation on the key is known. The new proposed set of freebits (or relations with probability 1) is optimal and no more such relations exist.

Exploiting the Conditions for Finding Chaskey Relations

In Fig. 3.3, we have depicted the relations and the influence of the input bits on the conditions of the differential path. The bits that stay white (and have no pink color beneath, coming from the carries of the furthest additions) are the bits that do not affect the differential transitions.

It is easy to see how the bits provided in [START_REF] Beierle | Improved Differential-Linear Attacks with Applications to ARX Ciphers[END_REF] as available for sampling with probability one are the only white ones, and therefore not needed for the differential conditions: [31,30,25,24,[START_REF] Bonnetain | Finding many Collisions via Reusable Quantum Walks[END_REF]22,20,19,18,[START_REF] Banik | GIFT: A Small Present -Towards Reaching the Limit of Lightweight Encryption[END_REF]16] from v 2 and [START_REF] Bonnetain | Finding many Collisions via Reusable Quantum Walks[END_REF]22,20,19,18,[START_REF] Banik | GIFT: A Small Present -Towards Reaching the Limit of Lightweight Encryption[END_REF]16] from v 3 . The differences are represented in grey. Dependencies in colors. A 'g' in the position of a difference means that this difference will go away (be absorbed) after the next addition. An 's' means that the difference stays where it is, while 'm' means that it moves one position to the left. The color of the bits with differences in each transition will be applied to all the bits that might affect this transition. Carries are not directly applied to the involved bits but to the upper row to report the difference this implies.

Please note that for instance bits 28 and 27 from v 2 cannot be included as the carry of the position 29 is needed by the orange bit relations, i.e., the differences after one round at position 29 of v 2 and v 3 , but as said in Sect. 3.1.4, the bits of previous positions to 26 and 27 will not affect this orange carry anymore due to the particular configuration of 26 and 27. The bits provided in [START_REF] Beierle | Improved Differential-Linear Attacks with Applications to ARX Ciphers[END_REF] that are neutral with very high probability are 20 and 19 from v 1 and 31, 20 and 19 from v 0 and 25 and 24 of v 3 .

Let us now see how can we use the conditional differential ideas and Fig. 3.3 to recover for free the value of some key bits and also to find additional bits of information for sampling and increasing the dimension of U from 18 as given in [START_REF] Beierle | Improved Differential-Linear Attacks with Applications to ARX Ciphers[END_REF] (and involving exclusively one-bit relations) to 22, or 23 if one-bit relation on the key is known.

Additional space for sampling Using Fig. 3.3 we can try to exploit the conditions to find more evolved relations for increasing the size of U. Let us provide an example: we consider the case where we flip the bit from v 0 [8]. The corresponding difference, marked with a 'g', will have a change of parity. For this difference to be absorbed, we need to also flip the other blue difference that will be used for absorbing this one: v 1 [8]. However, if we flip this one, the value of the bit v 1 [13] after one round, which does not contain a difference, will be flipped also. Indeed this value is produced by the XOR of v 1 [8] shifted of 5 positions and the sum of v 0 and v 1 , which has a difference in position 13, marked with an 's': these differences cancel out in both cases, but the value of the resulting bit will change with the parity of v 1 [8], and the value of this pink will affect the final light-pink transition in the third round, as can be seen in the picture. To avoid this, we have to also flip v 1 [13]: the state v 1 after 1 round will be known the same, but the orange bit v 2 [29] after one round that contains a difference and a 'g' will have the parity changed. To make the related transition satisfied, we need to also change the parity of the other orange bit with a 'g': we flip v 2 [29] from the first round, which does not have a difference, but that will change the parity of v 3 [29] after the XOR. This bit will not have any more influence in the remaining transitions, so we have found our close relation. In total, we found four new probability-one relations by hand using this same technique. We have verified these relations by implementing a similar algorithm to Algorithm 3.3 that tests whether a vector u is neutral, as well as exhaustively searched all the ones with weight at most 3, and found that no other such relations exist.

Conclusion

To summarize this chapter, we presented techniques and algorithms that were implemented to improve differential-linear attacks by artificially increasing the correlation of the underlying distinguisher by improving the search of neutral vectors. As an example of application, we presented the case of Chaskey which is an ARX design. Adapting these techniques to SPN ciphers [START_REF] Broll | New Attacks from Old Distinguishers Improved Attacks on Serpent[END_REF] resulted in an improvement on the attack on another cipher that was a candidate for the Advance Encryption Standard: Serpent [START_REF] Anderson | The Case for Serpent[END_REF]. A nice formalization of this improvement in the SPN case uses S-box decomposition using binary decision tree [START_REF] Broll | Generic Framework for Key-Guessing Improvements[END_REF]. This decomposition can be used to speed up key recovery since it allows to perform refined key guesses. v1 v0 v2 v3 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x X X X X X X X X X X X X X X X x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x We present in the next two sections an application of the techniques introduced in Section 2.1 against the SPEEDY family of block ciphers. Section 4.2 is dedicated to the distinguisher part, while Section 4.3 describes the key recovery part for SPEEDY-7-192.

x x x x X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
We start by briefly presenting the specifications of the SPEEDY family of ciphers.

Specifications of the SPEEDY family of block ciphers

The SPEEDY family of ciphers is a family of lightweight block ciphers introduced by Leander, Moos, Moradi, and Rasoolzadeh at CHES 2021 [START_REF] Leander | The SPEEDY Family of Block Ciphers Engineering an Ultra Low-Latency Cipher from Gate Level for Secure Processor Architectures[END_REF]. The main design goal of these primitives was to achieve extremely low latency. This goal was notably reached thanks to the design of a dedicated 6-bit bijective S-box. There are different SPEEDY variants that differ in block size, key size, and number of rounds. More precisely, the block cipher SPEEDY-r-6 has a block and key size of 6 bits and is iterated over r rounds. The internal state is viewed as a × 6 rectangle array of bits. Following the notation of [Lea+21], we will denote by x [i,j] , 0 ≤ i < , 0 ≤ j < 6, the bit located at row i and column j of the state x. Note that all indices start from zero and the zeroth bit or word is always considered to be the most significant one. Furthermore, if there is an addition or a subtraction in the indices of the state, this is done modulo for the first (row) index and in modulo 6 for the second (column) index.

The default block and key size for SPEEDY is 192 bits and this instance is denoted by SPEEDY-r-192. It is suggested to iterate this instance over 5,6 or 7 rounds. Next, we provide the specifications of the round function for SPEEDY-r-192. Note that for this variant, the state is seen as ( × 6)-bit rectangle, with = 32.

Round function of SPEEDY-r-192

The internal state is first initialized with the 192-bit plaintext. Then, a round function R r is applied to the state r times, where r is typically 5, 6 or 7. The round function is composed of four operations: First, AddRoundKey (A kr ) XORs the round subkey k r to the state. Then, the SubBox (SB) operation applies a 6-bit S-box to each row of the state. Follows the ShiftColumns (SC) operation that rotates each column of the state by a different offset. These two operations (SB and SC) are repeated twice in an alternating manner. After this, the MixColumns (MC) operation multiplies each column of the state by a binary matrix. Finally, a constant c r is XORed to the state by the AddRoundConstant (AC) operation. Note that, for the last round, the last ShiftColumns as well as the MixColumns and the AddRoundConstant operations are omitted, while a post-whitening key is XORed to the state. The round function R r for the rounds 0 ≤ r < r -1 while also for the round r -1 are depicted in Figure 4.1.

In the rest of our paper, we assume that the input (resp. output) to each of the described operations is a vector x (resp. y) ∈ F 32×6 2 .

• AddRoundKey (A kr ): The 192-bit round key k r is XORed to the internal state.

Hence, (

y [i,j] = x [i,j] ⊕ k r[i,j] . 4.
y [i,0] , y [i,1] , y [i,2] , y [i,3] , y [i,4] , y [i,5] ) = S(x [i,0] , x [i,1] , x [i,2] , x [i,3] , x [i,4] , x [i,5] ).
The table representation of the S-box S is given in Table 4.1.

• ShiftColumns (SC): This operation rotates the j-th column of the state, 0 ≤ j < 6, upside by j bits:

y [i,j] = y [i+j,j] .
• MixColumns (MC): The MC operation of SPEEDY applies column-wise and is based on a cyclic binary matrix α = (α 1 , α 2 , α 3 , α 4 , α 5 , α 6 ) whose values depend on the number of rows :

y [i,j] = x [i,j] ⊕ x [i+α 1 ,j] ⊕ x [i+α 2 ,j] ⊕ x [i+α 3 ,j] ⊕ x [i+α 4 ,j] ⊕ x [i+α 5 ,j] ⊕ x [i+α 6 ,j] .
Recall that the additions i + α * are considered mod .

For = 32, α = (1, 5, 9, 15, 21, 26).

• AddRoundConstant (A cr ): The 192-bit round constant c r is XORed to the internal state. Hence,

y [i,j] = x [i,j] ⊕ c r[i,j]
As this operation is not relevant to our analysis we omit the description of the constant values.

Key Schedule

The 192-bit master key of SPEEDY-r-192 is loaded to the state of the first round key k 0 . To obtain the next round key, the key schedule consists in simply applying a bit-permutation PB. Hence,

k r+1 = PB(k r ), with k r+1[i ,j ] = k r[i,j] ,
Chapter such that (i , j ) := P (i, j) with (6i + j ) ≡ (β

• (6i + j) + γ) mod ,
where β and γ are parameters depending on the block length of the cipher and that satisfy the condition that gcd(β, 6 ) = 1. For SPEEDY-r-192, the parameters β = 7 and γ = 1 are suggested, leading to the permutation P described in

Security Claims

The authors made security claims for the three main versions of SPEEDY-r-192. For the 5-round version the authors expect no attack with complexity better than 2 128 in time when data complexity is limited to 2 64 . On the other hand, SPEEDY-6-192 should achieve 128-bit security, while SPEEDY-7-192 is expected to provide full 192-bit security.

In addition, the designers of SPEEDY gave a claim on the amount of key recovery rounds: "The attacker cannot add more than one round to extend a distinguisher". In Table 4.3, we give a summary of the cryptanalysis done on the SPEEDY family of ciphers. The differential attack presented in this chapter will contradict both the time and data security claims as well as the security claim on the number of key recovery rounds.

Finding Good Differentials on SPEEDY

Differential properties of SPEEDY

We describe in this section the differential properties of the non-linear and linear layers of SPEEDY.

Differential properties of the S-box

The SPEEDY family of cipher employs a 6-bit S-box S whose differential uniformity is δ S = 8. This means that the highest probability of a differential transition through S is 2 -3 . One particularity of this S-box that we exploit in our attacks is that almost all 1-bit to 1-bit differential transitions are possible. Moreover, these minimal weight transitions often have a relatively high probability. Table 4.4 summarizes all these transitions, together with their corresponding probability. The full DDT is given in [Bou+23a].

Another particularity is that 1-bit to 1-bit differential transitions can be chained within one round through the SB • SC • SB operation. All of them are possible and three of them achieve the maximum probability of 2 -6 . Full break of SPEEDY-7-192 α/β 1 2 4 8 16 32 1 2 -4 2 4 2 2 1 2 4 4 2 2 4 -3 2 -3 1 8 1 1 3 3 1 1 16 --4 4 3 4 32 1 1 2 3 1 -Table 4.4: Summary of all the 1-bit input differences α to 1-bit output differences β.

The corresponding probability can be obtained by multiplying the coefficients of the table by 2 -5 . The symbolmeans that the corresponding transition is impossible.

Differential properties of the MixColumns operation

The branch number of the MC operation is 8, which is the maximum possible value for the vector α chosen. As the maximum differential probability over 1 round is 2 -6 , this means that an upper bound on the probability of any differential transition over two rounds is (2 -6 ) 8 = 2 -48 . The inverse MixColumns operation is defined with the vector α -1 = (4, 5, 6, 7, 10, 12, 14, 15, 16, 18, 19, 20, 21, 22, 23, 24, 25, 28).

This means in particular, that a column with a single active bit, will lead after the inverse of the MixColumns operation to 19 active bits, while a column with two active bits will be transformed after the inverse MixColumns to a column with at least 12 active bits.

Searching for good differential trails

We describe in this section the methodology we followed to find the trails used in our attacks. Our idea was to precompute at first all good one-round trails and then chain them to create longer trails that have a high probability.

Searching for good one-round trails.

Let M be the matrix used in the MixColumns operation. To find good one-round trails, we first computed and stored all ordered pairs of columns (x, M (x)) ∈ F 32 2 × F 32 2 such that both columns x and M (x) have at most 7 active bits each. This led to a total of 5248 pairs (x, M (x)) ∈ F 32 2 × F 32 2 . However, these 5248 pairs can be divided into 164 equivalence classes, each equivalence class corresponding to the 32 rotations of a different activity pattern inside a column. We then stored in a table T one representative per equivalence class and used these pairs to pre-compute and store all 1-round trails satisfying some particular criteria. To describe this phase we need to introduce the following notation. Let st[0] be the initial state for our computation. We denote by st[1] the resulting state after applying MC to st[0], st[2] the state after applying SB to st[1], st[3] the state after applying SC to st[2], st[4] the state after applying SB to st[3], st [5] the state after applying SC to st[4] and finally st[6] the state after applying MC to st [5]:

st[0] M C --→ st[1] SB --→ st[2] SC --→ st[3] SB --→ st[4] SC --→ st[5] M C --→ st[6].
We computed all such propagations (st[0], st[6]) satisfying the following conditions:

• st[0] has a single active column c 0 such that (c 0 ,M (c 0 )) ∈ T,

• st [5] has a single active column c 5 such that (c 5 , M (c 5 )) ∈ T,

• st[2] has at most two active bits per row,

• the probability of the trail (st[0], st[6]) is strictly higher than 2 -49 . For all trails satisfying the above conditions, we stored in a table the states (st[0], st [5]) together with the probability of the corresponding trail. We obtained a total number of 48923 one-round trails, which we stored. Note that each trail can be shifted column-wise to form 32 other valid one-round trails. Thus, in total, there are 1565536 one-round trails which satisfy our criteria.

We now justify the criteria used for computing these 1-round trails. Our main constraint was computing time, as considering all 1-round trails is computationally infeasible. Furthermore, as we wanted to store the trails and reuse them, the memory needed to be reasonable as well. Limiting the computation to states with a single active column before and after each MixColumns computation is a reasonable assumption, as states with more active columns would lead by the inverse ShiftColumns operation to many active rows. Furthermore, by doing initial experiments for computing long trails, we noticed that all good trails found never had more than 7 active bits in a column. This can be explained by the fact that more active rows naturally lead to lower probability transitions through the SubBox operation. We then limited the transition through the first SubBox operation to only transitions from rows with Hamming weight one to rows with Hamming weight at most two. While transitions activating in the output more bits per row can still lead to good trails respecting the other criteria, only a small proportion of these transitions does so, while the computational gain for not considering them is huge. Finally, we limited the probability of the trails to 2 -49 in order not to have to store too many trails for the second phase. This particular bound came from our initial experiments, where we noticed that the probability of all 1-round trails that were part of the longer trails we found, had probability strictly higher than this bound.

We claim by no means that the chosen criteria lead to all the one-round trails that could be part of optimal longer trails, however, we believe that our strategy is a reasonable trade-off between optimality and efficiency.

Searching for longer trails.

In a second step, we used the precomputed 1-round trails to create longer ones. To do so, we started by chaining our pre-computed one-round trails to obtain r-round trails.

To begin, we exhaustively ran through all the precomputed one-round trails and searched for the ones that can be chained. Recall here that the starting state and ending state of each round trail are the states just before the MixColumns application. The chaining condition is very simple and consists in simply verifying that the final state of a one-round trail is the same as a column-wise rotation of the starting state of the following one by an integer 0 ≤ ι < 32. Note that when ι = 0, the full one-round trail concerned is also rotated column-wise. Also note that doing so, we only obtain an element of an equivalence class modulo the column-wise rotation. To make our search efficient, we first sorted the states by Hamming weight and active column coordinate of their initial and final state. Following this procedure, we found 1476978 2-round trails, each of them giving by rotation another 32 valid 2-round trails. We followed a similar procedure to obtain 46471749 3-round trails which can also be rotated column-wise to obtain 32 times more valid 3-round trails. To compute the 4-round trails we use in our attack on the 7-round version, we chained the 2-round trails with themselves rather than using the 3-round trails for the search to be more efficient. We stored the most interesting 4-round trails we found based on criteria of low probability and adaptability to the key recovery step as described in the next section.

From now on, for each r-round trail, we use the following notations. Let st start [k] (resp. st end [k]) be the starting state (resp. the ending state) of each one-round trail composing the r-round trail, for 0 ≤ k < r. Denote also by c start the active column of st start [0] and by c end the active column of st end [r -1]. Let w 0 be the Hamming weight of c start (i.e. the number of active bits in c start ) and let w 1 be the Hamming weight of M (c end ), where M is the matrix used in MixColumns. Finally denote by P k , the probability of the round k, for 0 ≤ k < r. The probability of the r-round trail, that we will call from now on core trail, is then given by P 0 × P 1 × • • • × P r-1 .

Extending the core trail.

To build our attack, we need to choose an r-round trail that will be extended one round backward and half a round forwards as shown in Figure 4.2. In this section, we describe the criteria that we used to select an r-round trail that is likely to result in a good (r + 1.5)-round trail. The resulting (r + 1.5)-round trail must have good probability, but also needs to be adapted to our key recovery step. In particular, as we will argue in detail in Section 4.3, it is important to have differentials that will allow for efficient sieving in plaintext. In particular, it is desirable that the (r + 1.5)-round trail we construct has a sufficient number of inactive rows on the plaintext.

First, as described above, we need to make sure that the r-round trail selected leads to a (r + 1.5)-round trail with good probability. For a r-round trail, the probability of the resulting (r+1.5)-round trail can be upper-bounded by 2

-(w 0 +1)×3 ×P 0 ×P 1 ו • •×P r-1 × 2 -w 1 ×3
. Indeed, if w 0 is the Hamming weight of c start , then by computing backward one round there will be at least w 0 + 1 active S-boxes. As the highest probability transition through an S-box has probability 2 -3 , the highest possible probability of this prepended round will be 2 -(w 0 +1)×3 . In the same way, if w 1 is the Hamming weight of M (c end ), then there will be exactly w 1 active S-boxes through the first S-box layer of the next round. Thus, the probability of the appended half round will be at most 2 -w 1 ×3 . We generated all possible r-round core trails following the procedure described above and kept the ones providing high estimated probabilities. Second, we want the r-round trail selected to lead to a (r + 1.5)-round trail that has a significant number of inactive rows on the plaintext for the sieving step to be efficient. First, consider the initial state of the r-round trail. The rows that are active in this state are exactly the rows that will be active in the state that follows the first SC operation in round 0 of the (r + 1.5)-round trail. To achieve better sieving, we want the transition from this state through SC -1 • SB -1 to lead to an initial state of the (r + 1.5)-round trail that has low Hamming weight. To achieve this, not only the number of active rows but also the way those are distributed inside this state play a role in the efficiency of the sieving procedure. Let L be the size of a block of consecutive rows, where all rows are non-active except for l out of them. An example of such a state is shown below with L = 15 and l = 3. Large values of L combined with small values of l naturally lead to better complexities. Indeed, we can carefully control the l active rows with some probability at a given cost. By doing so, we can generate several inactive rows in the plaintext as high as L -5 -l, thus leading to a sieving of 2 -[(L-5-l)]×6 .

Using the above criteria, we selected an r-round trail, which we then extended in two ways, starting first by appending a round backward. This led to an (r + 1)-round trail. Then, to further improve the probability of our trail (r + 1)-round trail, we relied on the technique of multiple differentials.

Multiple differentials

The technique of multiple differentials consists in considering multiple (r + 1)-round differential trails that all have the same input and output difference. To make the description of our technique simpler, we will describe how we built our multiple differentials in the case of our 7-round attack. In this case, r = 4. For our 7-round attack, the chosen 4-round core trail is the one displayed in red in Figure 4.3. This trail has probability 2 -161.15 . As shown in Figure 4.3, we extended it by one round backward and obtained a 5-round trail of probability p main = 2 -170.56 . We call this trail the main trail. Note that it is possible to extend the 4-round core trail backward with probability 2 -6 for one round. However, this propagation, due to the diffusion properties of the inverse MixColumns transformation would lead to a column with 19 active bits (see Section 4.2.1.2). Such a scenario would have complicated the key-recovery phase and was not retained.

We limited our search to trails with probability smaller or equal to p max = p main × 2 -25 . Our new trails must thus verify that

• their input difference is such that the bits of coordinate (i, j) ∈ {2, 3, 4, 7, 8, 10, 12, 14, 16, 17, 18, 25, 27, 29}×

{1} are active, whilst the other bits are inactive in the first state of Figure 4.3;

• their output difference is such the bits of coordinate (i, j) ∈ {1, 15, 16, 19, 21, 25, 31}× {3} are active, whilst the other bits are inactive in the second state surrounded by red in Figure 4.3.

To build our new trails, we rely on an algorithm that operates round by round.

Initial round.

We start by building a list of potential initial one-round trails. We denote the initial state by st[0], the state after the application of MC by st[1], and so on and so forth as we did when constructing our one-round trails. We similarly construct our initial one-round trails to the way we constructed the one-round trails used to build our main trail. More precisely, we want our potential initial one-round trails to satisfy the following conditions:

• st[0] verifies the input condition;

• st [5] has a single active column c 5 such that (c 5 , M (c 5 )) ∈ T;

• st[2] has at most two active bits per row.

To make the search more efficient, we added constraints on these initial round trails' probability and Hamming weight, using the fact that (st[0], st[6]) must belong to a larger 5-round trail such that the probability of this larger trail is at most p max . We will not describe these constraints in detail as they are very similar to previous techniques we used to build trails of reasonable probability. We obtained 6 potential initial round trails. Because of the second condition above, these new trails can be chained to our previously computed one-round trails. This property will be used to build our multiples.

Chaining the initial round. To find trails that satisfy our truncated differential constraints, we must now chain the potential initial round trails to the previously computed one-round trails. We do so in two steps for the chaining to be computationally feasible.

1. We chain the 2-round trails pre-computed to the potential initial one-round trails to form potential initial three-round trails. We get 8049 such 3-round trails.

2. We chain these potential initial 3-round trails to the previously computed 2-round trails to obtain 5-round trails.

We found 409 5-round trails that matched all our criteria. By adding their corresponding probabilities, we found a final probability of 2 -169.95 . As one can notice, using multiple differentials allows to improve the probability of the r-round differential, but this improvement is not as important as one would have expected by the number of found trails. This is because all of the additional trails found had unfortunately quite bad probabilities compared to the main one.

5.5-round differential trail

We describe now the 5.5-round differential trail we used to attack SPEEDY-7-192 in the following section. This trail is depicted in Figure 4.3. As stated before, the 5-round trail has probability 2 -170.56 , which is improved to 2 -169.95 by using multiple trails. We then extended this differential 0.5 round forwards. For this step, we followed a particular approach. To go through the last S-box layer of the distinguisher part (see the before last state of Figure 4.3) an attacker has several choices. One extreme would be to fix to some concrete output value the transitions through all active S-boxes. This comes at a cost of a certain probability, but if we choose the transitions carefully we can guarantee very few active rows on the ciphertext. The other extreme is to consider truncated output differences for all the active S-boxes of this state. Thus the transition through the SubBox layer happens with probability 1, but almost all rows will be active in the output leading to very large structures of ciphertexts. What we decided to do is a trade-off between these two scenarios. More precisely, we decided to fix the transition 0x4 → 0x10 for the active S-boxes of rows 5, 11, and 19 and to allow more transitions for the S-boxes of rows 0 and 28. The choice of these two rows comes from the fact that after the SC operation, these two S-boxes activate some common rows. Our goal was to activate at most 7 rows after the SC operation (last state of Figure 4.3) and for this, we computed the highest probability to have at most 4 rows active between rows 23 and 31 and also row 0 after SC. We exhausted all possible configurations and we found the best one to be the one having the rows 24, 27, 28 and 31 active after SC. One possibility for this was to force the output difference of the S-box of row 0 to be of the form (0,*,0,0,*,0) and the output difference of the S-box of row 28 to be of the form (*,*,0,0,*,0), where * means that the corresponding bit is potentially active. The probability than to start from any difference of the above form in rows 0 and 28 and to activate at most the rows 24, 27, 28 and 31 after the SC is 2 -3.41 . complexity of the attack: one, already used for instance in [Bro+22b], is to not consider the rounds as blocks regarding their treatment concerning the differential distinguisher or the truncated part, but include some row transitions in the differential and let the rest go as truncated in the same round which we will apply in the input and output of the attack; the other is to consider the detailed equations over two rounds with merging techniques that will allow us to optimize the complexity of the key guessing part.

Our attack has a data complexity of 2 187.28 , a time complexity of 2 187.84 and a memory complexity of 2 42 and contradicts thus the designers' security claim for this variant, as has been acknowledged by them. More importantly, this cryptanalysis highlights that the security margin for this variant was overestimated. Our attack uses the differential found with the ideas from Section 2.1 and the implemented method described in Section 4.2.2. As described before, the main differential trail depicted in Figure 4.3 covers 5.5 rounds, and its probability, when taken together with its associated multiple trails described in Section 4.2.3, is 2 183.59 . The trail of Figure 4.3 can then be extended one round backward and half a round forwards as shown in Figure 4.4, to finally cover 7 rounds. This fact contradicts a particular statement of the designers that wrote that a one-round security margin for the key-recovery part should be sufficient.

Trade-off between differential probability and efficient sieving

Our attack is performed in the decryption direction. The first step is to generate several relevant ciphertexts to implement the attack. If we impose no extra condition on the extension of the distinguisher to the plaintexts (∆ in → D in as denoted in Figure 2.1.2) then D in will have all but one rows active (see Figure 4.3). This would lead to very limited sieving and would thus leave us with too many potential pairs on which to perform the key recovery. For this reason, we propose a first improvement. This improvement consists in restricting the permitted transitions through the second S-box layer of Round 0. More precisely, the condition is that the three active bits in rows 26, 28 and 30 after the second S-box only generate a maximum of three active rows in the plaintext state Chapter 4. Better Steady than Speedy: Full break of SPEEDY-7-192

(among rows 26 to 31 and among rows 0 to 2). This condition allows to have 7 inactive rows (instead of 1 before) in the plaintext state at the cost of decreasing the overall differential probability. We denote by P in the probability that it is verified. As we show next, since this probability is relatively high, the impact on the overall differential probability is limited. To compute P in , we start with the state Z, corresponding to the state after the second S-box application of Round 0, where the rows 26, 28 and 30 all have an active difference of 010000. Therefore, on the state Y, we consider differences δ 1 , δ 2 , δ 3 that propagate to 010000 through the S-box layer with probability P(δ 1 ), P(δ 2 ), P(δ 3 ) respectively. Propagating backwards through SC, we obtain X δ 1 ,δ 2 ,δ 3 = SC -1 (Y δ 1 ,δ 2 ,δ 3 ). We are interested in states X δ 1 ,δ 2 ,δ 3 that have at most three nonzero rows among rows 26 to 31 and rows 0 to 2. We define the function 1 3 as follows:

1 3 (X δ 1 ,δ 2 ,δ 3 ) = 0 if X δ 1 ,δ 2
,δ 3 has more than 3 nonzero rows 1 else.

The overall probability for the transition is given by the formula

P in = δ 1 ,δ 2 ,δ 3 1 3 (X δ 1 ,δ 2 ,δ 3 )P(δ 1 )P(δ 2 )P(δ 3 ) .
The obtained probability is P in = 2 -2.69 . We take this probability into account as part of the overall probability of the differential distinguisher, which now becomes 2 p * = 2 -(183.59+2.69) = 2 -186.28 . Note that only 78 (instead of 9 3 = 84) difference patterns are possible in the plaintext.

Data generation

We build the data required for our attack in the decryption direction. Since there are 7 active rows on the ciphertexts, the size of each structure is 2 7×6 = 2 42 . By following now the notations introduced in Section 2.1, we build 2 s structures of size 2 42 each, such that 2 s+42 equals 2 186.28+1 . This implies that there are 2 s = 2 145.28 structures and 2 145.28+2•42-1 = 2 228.28 potential pairs. The cost of the data generation is 2 187.28 C E , where

Attack on SPEEDY-7-192

57 C E is the cost of one encryption and can be estimated as 6 * (1+6+6+6)+1+6+6 = 128 bit-operations. Indeed, MC, SB are 6 bit-operations, the cost of AK is 1, and all these transformations can be applied in parallel.

Sieving of the pairs

Performing the key-recovery step on all 2 228.28 pairs would exceed the complexity of the exhaustive search. Therefore, we will start with a sieving step to eliminate pairs that cannot have followed the differential. This sieving is done by looking at the differences in the plaintext. As can be seen from Figure 4.4, the 'good' plaintext pairs have a zero-difference in row 25 as well as 6 inactive rows among rows 26 to 31 and 0 to 2. The sieving will be performed on both the inactive and the active rows.

Inactive rows. Each inactive row represents a 6-bit filter. We consider each of the 78 possible difference patterns in the plaintext. For each pattern, since there are 7 inactive rows at the input, the sieving obtained from these rows is 2 -42 .

Active rows [3 -24]. We can proceed to sieve on each of these 22 active rows by taking into account the first S-box layer of Round 0. To make this step clear, we start by explaining the sieve on row 6. As can be seen from Figure 4.4, to follow the differential, a plaintext pair should generate after the application of the S-box a truncated difference of the form (0,*,*,*,0,0). By looking at the DDT of SPEEDY's S-box, we see that the input differences 0x16, 0x2d and 0x3c never propagate to an output difference of the form (0,*,*,*,0,0). Thus, any pair with one of those three plaintext differences at row 0 can be sieved out. This gives us a filter of log 2 (61/64) = 0.07, as shown in Table 4. 5. The filters for the other active rows are computed similarly and are reported in Table 4.5.

row filter row filter row filter row filter 3 0.42 9 0.02 15 0.09 21 0.07 4 0.48 10 0.05 16 0.07 22 0.17 5 0.07 11 0.07 17 0.09 23 0.51 6 0.07 12 0.12 18 0 24 1.42 7 0.07 13 0.02 19 0.02 8 0 14 0.07 20 0 total filter 3.9 Recall that there are in total 78 possible patterns pat, and each one corresponds to a subset of Full break of SPEEDY-7-192 exactly 3 active rows among rows 26 to 31 and 0 to 2 in the plaintext. We start from the difference (0,1,0,0,0,0) on the rows 26, 28 and 30 after the second S-box of Round 0. Then we propagate this difference backward through the two S-box layers of Round 0 and discard all the differences that do not follow the pattern considered. The number of possible differences on the plaintext allows us to filter 2 -fpat = #Possible differences 2 3•6 (see [Bou+23a] for the 78 possible values of f pat ).

Summarizing the sieving step. For a pattern pat, the sieving corresponding to the inactive rows is 2 -42 while the one on the active rows is 2 -3.9 • 2 -fpat . Thus, the total number of potential pairs for the key recovery step is pat 2 228.28-45.9-fpat = 2 182.38 pat 2 -fpat = 2 186.42 . This sieving step is the reason why we decided to perform the attack in the decryption direction. Indeed, using the 78 patterns in initial structures would have further increased the complexity.

Recovering the key

In this section, we describe our improved key recovery step. The key recovery algorithm is performed for each pair on the fly. As explained in the last section, the total number of pairs we will try in this step is 2 186.42 . For each pair, we check whether there exists a key that allows the pair to follow the differential. If not, the pair is discarded. Otherwise, as we will show, we obtain a partial key on which all bits are determined but a small number n l which is equal to 8 on average. For each of the remaining pairs and associated partial key, we then try exhaustively all possible 2 n l keys. For each pair, the key recovery is divided into three stages which can be summarized as follows. First, we determine bits of the last subkey k 7 using the fact that if the pair follows the trail, then it must belong to δ out before the last SB application. Since the key schedule of SPEEDY consists simply of a permutation of the key bits, this, in turn, constrains the bits of k 0 . Second, we determine more bits of k 0 using the fact that the pair must belong to δ in . Lastly, we determine a few extra key bits using the penultimate S-box application (the first S-box application of the last round).

Stage 1 -Last subkey addition (k 7 ).

For each pair, we start by determining several bits of k 7 . As can be seen from Figure 4.4, the ciphertext pairs are active on the rows [4,10,18,24,27,28,31]. For the rows [4,10,18,27,31] (respectively row 24), we want the partial key to be such that these rows satisfy the differential (0,1,0,0,0,0) (respectively (0,0,0,0,1,0)) before the last SB application. For each pair, this determines 6 × 6 = 36 key bits on average. with probability 2 -4 . The row 28 can thus determine 6 additional key bits at the cost of 2 2 guesses on average. This stage thus allows us to determine up to 42 key bits at the cost of 2 2 guesses. In Table 4.6, we detail which key bits of the master key are fixed after determining the value of k 7 on the rows corresponding to one of the 7 active rows in the ciphertext.

About the potentially active ciphertext rows.

For the sake of simplicity, we consider in this analysis that the four ciphertext rows [24,27,28,31] are active, as it simplifies the key guessing procedure. We could just discard the pairs that do not verify this, leaving us with 2 24+24-1 -2 47-6 ≈ 2 46.91 pairs for the partial structure on 4 lines instead of 2 47 , but with a higher probability of reaching a good difference before the penultimate SB. In practice, there is no need to discard this data. It can also be treated with similar methods to the one presented here. Although these methods are slightly more expensive than the one presented here as a few more key bits might have to be partially guessed, they are used to handle a very small proportion of data. Thus, the difference in the cost will be negligible. We thus limit our explanations to the predominant case, with all the rows active. We allow rows [4,10,18] to be nonactive. For each of these rows, this gives on average a probability of 2 -6 of having a difference that can match the required one (including the 0 difference). Thus, on average, only one 6-bit key word leads to the desired difference.

Stage 2 -First subkey addition (k 0 )

We now focus on the addition of the first subkey k 0 . This key recovery stage is performed row by row, and the order in which each row is treated is important to keep our time complexity as low as possible. For each row, we will use available information from both SubBox layers of Round 0 to determine more triplets of possible pairs and associated keys. Table 4.7 helps us understand how to exploit the first S-box of Round 0 for rows [3,...,24]. Recall that these rows are active in the plaintext and that they allowed us to perform a specific sieving given in Section 4.3.3. For each row, Table 4.7 provides the following information:

• Key determined gives the number of key bits already determined during Stage 1 (i.e. with subkey k 7 ).

Chapter 4. Better Steady than Speedy: Full break of SPEEDY-7-192

• Key left gives the number of key bits that remain to be determined for this row (note that the sum of Key determined and Key left is always 6).

• Differential Filter gives the value of the filter that was applied during the sieving step to each pair.

• Fixed bits gives the amount of inactive bits after the first SubBox layer.

• First S-box Cost gives the overall cost in bits for a given row to check the propagation through the first SubBox. Since one can precompute the valid pairs of values and associated partial keys for each row, this cost is equal to (Key left + Differential filter -Fixed bits) rather than Key left. For each row and each key, the probability that they satisfy the differential is 2 Differential filter-Fixed bits . In particular, for rows where the value of First S-box Cost is negative, then for each pair, there exists a key that satisfies the differential with probability < 1. Such rows allow us to discard more pairs.

Since row 25 is inactive, it does not provide any information about k 0 through the first SB. For the sake of simplicity, we do not analyze how to exploit the rows 0 to 2 and 26 to 31. This could have been done by looking at the case of each specific pattern, but it wouldn't have significantly improved the attack whilst considerably lengthening the description of the key recovery step.

To perform the key recovery, we will also look into the propagation through the second S-box. More precisely, we will use the conditions set on the rows [3,4,5,8,9,11,13,[START_REF] Beaulieu | The SIMON and SPECK lightweight block ciphers[END_REF][START_REF] Banik | GIFT: A Small Present -Towards Reaching the Limit of Lightweight Encryption[END_REF]18,19] after the application of the second S-box to sieve the pairs. At the output of the second S-box, these rows must have the exact difference (0,1,0,0,0,0). This provides us with a 2 -6 filter, but it is not straightforward how to exploit it. Indeed, because of the SC step, each row at the output of the second S-box layer depends on 6 rows at the output of the first S-box layer. It thus seems that to get a 2 -6 filter, one first has to guess 6 rows of k 7 , which is very costly. However, we use several improved techniques to get filters without having to guess too many rows before the first S-box step. We describe these techniques through an example which can be found in the paragraph dedicated to the rows [18,19,22,21,23] below. We now describe in detail the first three steps of Stage 2. Table 4.8 sums up the rest of Stage 2.

Rows [4]. We start by considering row 4. This row allows us to perform a filter of -0.52 at the first S-box level of Round 0.

Rows [18,19,20,21,[START_REF] Bonnetain | Finding many Collisions via Reusable Quantum Walks[END_REF]. We next consider the rows 18,19,20,21 and 23. To understand why these rows are the next ones we consider, one must take into account the second S-box transition. Indeed, consider the rows [17,18,19] after the second S-box transition. These three rows are active, and must thus have the exact difference (0,1,0,0,0,0). Since these rows are positioned next to each other, one does not need to guess 3 × 6 = 18 rows at the input of the first S- , and Key left is the number of bits that remains to be known. Fixed bits represents the number of inactive bits after the first SB of Round 0 and that therefore can be used to perform a sieving on the candidate keys.

The cost is the difference between the previous values, and the second filter denotes the active rows in the second SB, as they will provide additional filtering to produce the fixed output difference. • Row guessed at the input. This column displays the coordinate of the row guessed. The column considered first is at the top and the last one is at the bottom.

• Partial guessing cost. This column displays the cost of guessing each row and checking that the first S-box transition is valid (See Table 4.7).

• Partial data filter. For each row, this column displays the log of the probability that a valid partial key exists for each pair, taking into account the filter provided by the constraints after the second S-box. This column provides information on the evolution of the data after guessing each row (or group of rows). For a (group of) row(s), if the entry on this column is -x, then the number of pairs remaining after handling this (these) column(s) is multiplied by 2 -x .

• Row determined at second S-box. This column displays the second S-box rows that are fully determined after a given guess.

The complexity of the key recovery so far is given by the formula

2 186.42+2 2 -0.52 (2 4.94 + 2 -0.23 (2 1.42 + 2 -0.58 (2 3 + 2 -3 (• • • (2 1.42 + 2 0.58 ))))) 2 -7 C E = 2 186.15 C E
and there are 2 168.3 remaining pairs.

Stage 3 -Back to k 7 using the penultimate S-box.

For the remaining key bits, we will go back to k 7 and study the penultimate S-box. A similar approach to the second S-box is applied here: instead of using the second S-box transition to perform a guess and filter approach, the penultimate S-box is used. For each row of k 7 , Table 4.9 shows which bits of the master key still need to be guessed (the bits in black). For each pair, we wish to find partial keys such that they lead to the difference 000100 before the first S-box of the last round on rows [0, 5,11,19,31]. For each of these rows, Table 4.10 displays which rows of k 7 need to be guessed to check the transition to 000100 before the first S-box of the last round. More precisely, it provides the following information.

• Row considered. This column displays the coordinate of the row before the first S-box of the last round which will be used to filter the right key guesses.

• Involved rows of k 7 . This column displays which rows of k 7 must be guessed to check the condition on the row considered before the first S-box of the last round.

• Number of missing bits. This column displays the number of bits in the involved rows of k 7 that have not yet been determined.

For each remaining pair and each of these five transitions, we recover the key bits that allow this transition and put them in tabs. By merging them, we then recover the pairs and associated partial keys that allow the whole state transition. After this step, only the key bits [START_REF] Beaulieu | The SIMON and SPECK lightweight block ciphers[END_REF]16,152,153,159,180,187,188]

Conclusion

In this chapter, we managed to perform a full break on SPEEDY-7-192 which was presented in TCHES 2021. Although differential cryptanalysis is a well-known technique that designers consider when choosing their parameters, designing tight security claims is a difficult task. Indeed, the attack presented in this chapter contradicted both the security claims derived by the security parameters as well as the security claim on the number of key recovery rounds possible. This is possible for two reasons:

• There is a lot of finesse in the design of the attack. Indeed, the trade-offs used in this attack allow a balance of the complexity terms, hence minimizing the overall complexity. Also, the key recovery is very efficient thanks to the use of guessing techniques such as parallel key guessing.

• The branch-and-bound algorithm used by the designers of SPEEDY does not capture well the spectrum of differential distinguishers. Indeed, they only considered oneto-one transitions through the S-Box hence neglecting the cases where two active bits on the same row recombine into one active bit.

In Section 5.1, we will describe the new cryptanalysis technique and improvements as well as compare it with both differential cryptanalysis and meet-the-middle cryptanalysis. Then in Section 5.2, we will present an application of the differential-meet-in-the-middle technique to SKINNY-128-384. Hence, we will first give the specification of the SKINNY blockcipher family and then we will describe the attack on 25-rounds SKINNY-128-384.

The new attack: Differential MITM

In this chapter, we present a new cryptanalysis technique in symmetric cryptography: differential meet-in-the-middle cryptanalysis. It consists in combining elements of 68 Chapter 5. Differential Meet-In-The-Middle Cryptanalysis differential cryptanalysis with elements of meet-in-the-middle attacks. From a differential point of view, this new technique can be interpreted as a new method to perform the key recovery. From the meet-in-the-middle point of view, differential MITM attacks consist of a method to extend MITM attacks by adding some rounds in the middle (similar to sieve-in-the-middle [START_REF] Canteaut | Sieve-in-the-Middle: Improved MITM Attacks[END_REF][START_REF] Canteaut | Sieve-inthe-Middle: Improved MITM Attacks (Full Version)[END_REF] ). We will present in this section a high-level description of the new technique. More precisely, we will provide a general framework that describes how to mount a differential MITM attack in a generic and simple way, and we will show how to combine this generic method with two techniques: the parallel treatment of data partitions in order to add one round mostly for free (idea that inherits from MITM attacks, like bicliques [START_REF] Diffie | Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard[END_REF], and that cannot be applied to classical differential attacks), as well as a technique to reduce the data complexity.

General framework

Consider a n-bit cipher E decomposed into three sub-ciphers: E out • E m • E in , as depicted in Figure 5.2. Let the number of rounds of E in , E m and E out be r in , r m and r out respectively. Finally, let ∆ in be the input difference to the middle part E m , ∆ out the output difference of E m and suppose that the differential ∆ in → ∆ out , covering the r m middle rounds, has probability 2 -p . We start our analysis with a first randomly chosen plaintext P of n bits and its associated ciphertext C, and we aim at generating a second plaintext-ciphertext pair ( P , C) such that together they satisfy the differential on the middle rounds. Our new idea is to generate ( P , C) with a meet-in-the-middle approach. For this, candidate plaintexts P are computed from both the plaintext P and the difference ∆ in for each possible value of the associated key K in , while, in parallel, candidate ciphertexts C are computed from C and ∆ out for each possible value of the involved key, K out . The match is then performed on the relation E( P ) = C (or P = E -1 ( C)) that happens with probability 2 -n . Note that the roles of the upper and lower part can be interchanged without loss of generality in order to optimize the data and memory complexity if we consider that access to both the encryption and the decryption oracles is granted.

Upper part.

Given P , the aim is to guess the minimal amount of key information, that we will denote by K in , such that we can compute the associated P that ensures E in (P ) ⊕ E in ( P ) = ∆ in . For each guess i for K in , we obtain a different candidate for P , that we denote by P i , leading to a total of |K in | = 2 k in such values. From them, we can compute the 2 k in associated ciphertexts C i = E( P i ) with calls to the encryption oracle and store them in a hash table H.

Lower part.

Similarly, given C, we can guess some key material K out , of size 2 kout , and compute a new ciphertext C that satisfies the equation

E -1 out (C) ⊕ E -1 out ( C) = ∆ out if the
key guess is correct. We obtain 2 kout values for C j , each associated to a guess j for K out .

Number of pairs and match.

For the correct key guess, the transition ∆ in → ∆ out will happen with a probability 2 -p . Therefore, we will repeat the upper and lower procedures 2 p times with 2 p different messages P so that we can expect one pair (P , P i ) to satisfy the differential together with the associated pair (C , C j ). When this is the case, we will find a collision for a certain between a C i computed in the upper part and stored in H and a C j computed from the lower part. Each collision (i, j) has an associated key guess K in = i, K out = j, that we will consider as a potential candidate. The number of expected collisions for each fixed P is 2 k in +kout-|K in ∩Kout|-n , hence resulting in a total of 2 k in +kout-|K in ∩Kout|-n+p .

Algorithm

C i ← E( P i ) Oracle call H[ C i ] ← H[ C i ] ∪ {i} for each guess j for K out do Backward computation Compute C j from j and C for each i ∈ H[ C j ] do
Complete (i, j) to retrieve the master key Try candidates against extra data

Complexity.

This attack can be decomposed in two steps, first, we look for key candidates then with the help of extra data, we check for each key candidate whether it stays valid or if it needs to be discarded. The time complexity of this attack can be estimated as

T = 2 p × (2 k in + 2 kout ) + 2 k in +kout-|K in ∩Kout|-n+p ,
where the first term corresponds to the first step, hence computations done in E in and E out , and the last one to the second step, hence number of expected key candidates. With this, we recover K in ∪ K out , so if we expect fewer key candidates than the whole set

K in ∪ K out , (i.e k in + k out -|K in ∩ K out | -n + p < |K in ∪ K out |
, which holds as long as p < n), we can guess the remaining bits of the master key and test the guess with additional pairs. Thus we recover the whole key with a complexity smaller than the cost of an exhaustive key search, and an additional cost of

2 k-(|K in ∪Kout|) × max{1, 2 k in +kout-|K in ∩Kout|-n+p }
to be added to the time complexity T . In the expected case where

k in + k out -|K in ∩ K out | -n + p ≥ 0, the total time complexity is thus T = 2 p × (2 k in + 2 kout ) + 2 |K in ∪Kout|-n+p + 2 k-n+p .
The (naive) data complexity of this first version of the attack can be estimated as

D = min(2 n , 2 p+min(k in ,kout) )
since the data complexity cannot exceed the size of the codebook. Finally, the naive memory complexity is given by M = 2 min(k in ,kout) , though it can be improved to 2 min(k in -|K in ∩Kout|,Kout-|K in ∩Kout|) by first guessing the common key material before running the attack.

Improvement: Parallel partitions for layers with partial subkeys

In this section, we will consider the case where the round key addition does not affect the whole state but only a part of it (as is for instance the case in Feistel constructions [START_REF] Feistel | Cryptography and computer privacy[END_REF], or in the SKINNY [START_REF] Beierle | The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS[END_REF] and GIFT [Ban+17] ciphers), we denote by m the number of bits of the states that are affected by the key addition. In this scenario, it possible to extend the attack by one round with minimal increase in complexity. Indeed, the time complexity will not be affected as long as m < p, the data complexity has to be checked case-by-case as it might depend on the configuration of the differences in the external states (further techniques for reducing this complexity is discussed in Section 5.1.3), the memory complexity might be increased.

The main idea here is to consider families of 2 m ciphertexts C together with families of 2 m penultimate states X R-1 such that for each element of both families there exists a final round key κ f inal that turns X R-1 into C after one round. Using both of these families, we will perform a differential-MITM attack and retrieve the last round key a posteriori.

Since we expect to try on average 2 p plaintexts in order to find one that will satisfy the differential of probability 2 -p , we can divide the final state of size 2 n into two parts. The part without the key addition will take 2 p-m different values. Hence, the attack will start from a given C and be repeated for each one of the 2 p-m values. The number of possible solutions might seem higher by a factor of 2 2m , but note that the following equation must be satisfied: C ⊕ C = X R-1 ⊕ XR-1 around the final key addition. This adds m bit-conditions, or more if this final subkey was already determined by K in and K out , which is usually the case. This implies m additional conditions, and 2 2m 2 -m 2 -m = 1, so the cost, given by the number of solutions, stays exactly the same as the attack with one round less. We will see how this technique can be applied in practice in Section 5.2. In the end the time complexity is:

T = 2 p-m × (2 k in +m + 2 kout+m ) + 2 k in +kout-|K in ∩Kout|-n+p ,
which is equal to the time complexity of the general framework of differential MITM attacks. The data complexity stays unchanged as well, regarding the memory complexity is increased by a factor 2 m . We can note that m can be smaller than the number of bits involved in the last round key addition k f inal since some bits of K f inal might be fixed at the beginning of the attack if

K in ∩ K out ∩ K f inal = ∅.

Improvement: Reducing data with imposed conditions

We explain here a way to obtain time-data-memory trade-offs for the original attack. If when choosing the plaintext P , we impose x of its bits, that might have been active otherwise, to a certain value, and if we expect the same from the associated plaintext P , the overall probability of the attack will decrease to 2 -p-x , as we will have to repeat the procedure until a P that satisfies this constraint is found. More precisely, if P does not fit this condition, the corresponding tuple will not be stored in the hash table since we do not have access to its ciphertext. However by doing so, the data complexity will be reduced by a factor of 2 x as well as the memory complexity. When combining this technique with the previous one, we can derive the following two inequalities for x:

p + x ≤ n -x and 2 p+x (2 k in + 2 kout ) < 2 k .
This type of trade-off applies in particular when all the code book of size 2 n is needed before fixing the x bits, and the data complexity becomes 2 n-x . Since we need to iterate the attack 2 p+x times instead of 2 p times, the time complexity is increased by a factor 2 x . Data reduction without time increase. As the total number of candidates for the key of the input part (respectively output) will be 2 k in -x (respectively 2 kout-x ), if we are able to find these candidates with their associated P (respectively C) in a complexity given by the number of solutions, the time complexity would become:

2 p+x (2 k in -x + 2 kout-x ) = 2 p (2 k in + 2 kout ),
which allows us to reduce the data complexity to 2 n-x while not increasing the time complexity. The optimal data complexity in this case will be 2 n+p 2 , obtained with x equal to n-p 2 . This can actually be done in many cases using rebound-like techniques [START_REF] Mendel | The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl[END_REF]. An example can be seen in Section 5.2.

Discussion and Comparison

As argued before, our new cryptanalysis technique is closely related to two families of techniques: MITM attacks and differential attacks. In this section we will discuss similarities and differences between these families and will try to identify cases where our new technique might be efficient or cases where it permits to reach better results compared to the best known attacks.

Relation to MITM attacks

In relation to MITM attacks [START_REF] Diffie | Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard[END_REF] and its variants, our attack has the potential of reaching more rounds because, similarly to the sieve-in-the-middle technique [START_REF] Canteaut | Sieve-in-the-Middle: Improved MITM Attacks[END_REF], some nonnegligible part of the cipher is considered in the middle. The starting point of our research was whether it was possible to add more rounds in the middle of a MITM-like attack and this is how we came up with the new attack, the idea was to increase the size of the middle part by considering a differential. The data complexity of the new attack could be higher than a classical MITM one as now we compute a new P from each guess of the key, and this plaintext can take many different values, besides the 2 p different plaintexts P taken as starting points in order to find one that satisfies the differential. On the other hand, despite the fact that the sets of bits K in or K out involved in the parallel computations of the differential MITM attack are not 5.2. Differential Meet-the-Middle attacks against SKINNY-128-384 73 determined in the same way as the key bits involved in MITM attacks, we expect those quantities to be relatively close under similar settings, as this principally depends on the propagation properties of the round function. More precisely, it seems that the more aligned [START_REF] Bordes | Thinking Outside the Superbox[END_REF] the round function is, the closer the sets will be.

Therefore, we expect that ciphers where classical MITM attacks work well, can also be interesting targets for differential MITM attacks. This is actually how we found the application shown in Section 5.2 on SKINNY. Indeed, the best known attack against SKINNY-384-128 previous to ours was a MITM one [START_REF] Dong | Meet-in-the-Middle Attacks Revisited: Key-Recovery, Collision, and Preimage Attacks[END_REF].

Relation to differential attacks

Curiously enough, our new attack can also be seen as a new way of performing the key-recovery part associated to a differential distinguisher.

Classical differential attacks. In Section 2.1.2, we gave a description of differential attacks. The time complexity of this type of attack consists in the sum of the three steps::

T = 2 p+1 + 2 p+d in +dout-n + 2 p+d in +dout-n C KR
By comparing the complexities, the differential MITM approach tends to be more effective if d in and d out are large , which can happen when several rounds are appended, the complexity of a differential MITM attack for an equivalent number of rounds might be more interesting. Indeed, the influence of the input and output extensions to the complexity are added and not multiplied. In particular, our attack can become much more efficient when the key size of the cipher is bigger than the state size, otherwise 2 p might already be close to the limit.

Differential Meet-the-Middle attacks against SKINNY-128-384

We provide in this section our applications to SKINNY-128-384. We start by recalling the specifications of the SKINNY family of ciphers.

Specifications of SKINNY

The SKINNY family of tweakable block ciphers was designed by Beierle et al. [START_REF] Beierle | The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS[END_REF].

It is a family of lightweight ciphers following a classical SPN structure but implementing a very compact S-box, a linear layer based on a sparse non-MDS binary matrix and a lightweight key schedule. The block size n can be 64 or 128 bits and for both versions the state is seen as a 4 × 4 matrix of 4-bit or 8-bit cells. Row 0 is considered the uppermost one and column 0 is taken to be the leftmost one. The numbering of the words inside the state matrix is as follows. SKINNY follows the tweakey framework [START_REF] Jean | Tweaks and Keys for Block Ciphers: The TWEAKEY Framework[END_REF] and XORs a tweakey to the two upmost rows of the state. There exist three main variants for the tweakey size: t = n, t = 2n and t = 3n and the corresponding variant is denoted by SKINNY-n-t. Furthermore, the tweakey to block size ratio is denoted by z = t/n. The tweakey state is viewed also as a set of z 4 × 4 arrays of cells. For z = 3, which is the variant of interest to us, the three tweakey arrays are denoted by TK1, TK2 and TK3.

The round function of SKINNY is depicted on Figure 5.3, and the number of times this function is iterated depends on both n and t, as shown in Table 5.1.

One round of SKINNY is composed of five operations applied in the following order: SubCells (SC), AddConstants (AC), AddRoundTweakey (ART), ShiftRows (SR) and MixColumns (MC). We now briefly describe the operations that are of interest to us.

SubCells (SC)

This operation applies an S-box to all cells of the state. The table representation of the 8-bit S-box used in the 128-bit variants is given in [START_REF] Beierle | The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS[END_REF].

AddRoundTweakey (ART)

We describe this step only for the variants with z = 3. Here, the first and second rows of the 3 tweakey arrays TK1, TK2 and TK3 are extracted and XORed to the internal state, respecting the bit positions inside the arrays. More formally, if IS i,j is the cell at the intersection of row i and j of the state, we have that for (i, j) ∈ {0, 1} × {0, 1, 2, 3}: IS i,j = TK1 i,j ⊕ TK2 i,j ⊕ TK3 i,j .

ShiftRows (SR)

This operation rotates the cells inside a row to the right by a certain offset that depends on the row. More precisely, cells in row i, where 0 ≤ i < 4, are rotated by i positions to the right.

MixColumns (MC)

This operation updates the state by multiplying each column by a binary matrix M. This matrix, as well as its inverse are as follows. Next we describe the tweakey schedule of SKINNY-128-384, the variant we analyse in this work.

M =      1 0 1 1 1 0 0 0 0 1 1 0 1 0 1 0      , M -1 =      0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 1      .

Tweakey schedule of SKINNY-128-384

At each round, all tweakey arrays are updated as follows (see also Figure 5.4). First, the same permutation P T is applied on the cell positions of the 3 tweakey arrays: for all 0 ≤ i ≤ 15, we have that TK1 i ← TK1 P T [i] with P T = [9, 15, 8, 13, 10, 14, 12, 11, 0, 1, 2, 3, 4, 5, 6, 7],

and the same exact permutation is applied to the cells of TK2 and TK3. Finally, the cells of the first two rows of TK2 and TK3 are individually updated by the LFSR :

(x 7 ||x 6 ||x 5 ||x 4 ||x 3 ||x 2 ||x 1 ||x 0 ) → (x 0 ⊕ x 6 ||x 7 ||x 6 ||x 5 ||x 4 ||x 3 ||x 2 ||x 1 ),
where x 0 is the LSB in a byte. Property. In most attacks, including ours, it is more efficient to guess round-key bits than key bits. Since the key-schedule of SKINNY is fully linear, guessing enough (e.g. 384 in the TK3 model) independent round-key bits allows to uniquely determine the master key and thus all remaining round-key bits. SKINNY has a unique property which makes easy the evaluation of the dimension of any set of round-key bytes: in the TKx model, a round-key byte K r [i] always depends on exactly x master key bytes, one from each TK keys and they all have the same index. Furthermore, given x round-key bytes from the 30 first rounds and depending on the same x master key bytes, they are always independent and allow to uniquely determine their x corresponding master key bytes.

We present now 3 attacks against round-reduced variants of SKINNY-128-384 by using our new differential meet-in-the-middle technique. We first describe a simple attack against 23 rounds as well as several improvements and trade-offs. We then explain how this attack can be extended to an attack on 24 rounds without increasing the attack's overall complexity. Finally, we describe a new attack against 25 rounds.

An attack against 23-round SKINNY-128-384

As explained in Section 5.1, differential meet-in-the-middle attacks rely on two classical cryptanalysis techniques: differential attacks and meet-in-the-middle attacks. The main idea is to use a meet-in-the-middle attack to generate a pair following a given differential in the middle rounds. Thanks to this procedure, we are able to extend a differential distinguisher by more rounds than with a classical early-abort procedure, as discussed in Section 5.1.4.

Differential.

The truncated differential used in our attack against 23 rounds of SKINNY-128-384 is depicted in Figure 5.5. It has 56 active S-boxes, without counting those of the first and the last round. We verified that this truncated differential can be successfully instantiated by using the constrained programming Choco-solver [START_REF] Prud'homme | Choco Solver Documentation[END_REF], and more precisely the model developed by Delaune et al. to search for the best differential characteristics for the SKINNY family of block ciphers [START_REF] Delaune | Efficient Methods to Search for Best Differential Characteristics on SKINNY[END_REF]. The best instantiation of this truncated differential has a probability of 2 -119 and there are in total 2048 instantiations with this same probability. These instantiations can be divided into four groups (∆

(i) x , ∆ (i)
y ), for i = 1, 2, 3, 4, each one having 512 trails inside, starting with the same difference ∆ (i)

x and terminating after 13 rounds with the same difference ∆ (i) y . We found as well many more differential trails with the same input/output differences but smaller probabilities: 2560 with probability 2 -120 , 7168 with probability 2 -121 , 18432 with probability 2 -122 and 44800 with probability 2 -123 . Thus the probability of the differential depicted on Figure 5.5 is higher than 2 -105.9 . The attack. We describe now our core attack against 23-round SKINNY-128-384.

1. Ask for the encryption of the whole codebook.

2. Randomly pick one plaintext/ciphertext pair (P, C).

3. For each possible value i of K in compute the tuple (P, P , i) so that the difference on the state after the 6th S-box layer is [0 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0] (see Figure 5.5). Doing so requires to know the values of all the active S-boxes involved in the probability 1 transition ∆ x → ∆ P , where ∆ P is the plaintext difference, and k in is the set of subkey bytes needed to compute them from the plaintext.

4. Store all these tuples in a hash table. This step requires to guess 31 subkey bytes as depicted in Figure 5.6.

5.

Similarly, for each possible value j of k out compute the tuple (C, C, j) so that the difference on the state before the 19th S-box layer is 0x64 on all active bytes. The set k out involves 32 bytes and thus there are 2 256 such tuples.

6. For each of them check for possible matches on the hash table. The match is performed on both the new ciphertext (i.e. ( P , C) must be a valid plaintext/ciphertext pair) as well as on the linear relations between the subkey bytes of the upper and lower guess.

7. Each match leads to a (full) key candidate that can be tried against very few additional plaintexts (3 in our case).

Repeat from

Step 2 until the right key is retrieved.

The data complexity of this attack is 2 128 since in Step 1 we ask for the encryption of the full codebook. The memory complexity is determined by Step 3 in which 2 248 words of 128 + 248 = 376 bits each are stored. Note that we do not need to store C 1 since it is common to all tuples. Thus the memory complexity is 2 249.5 128-bit words. The time complexity is 2 248 for computing the hash table, 2 256 for performing Step 4, and, as shown in Table 5.2, k in ∪ k out is the full key so that the complexity of Step 6 is 2 384-128 = 2 256 . Finally, the attack has to be repeated 2 105.9 times (the probability of the distinguisher) in order to construct one right differential pair. Hence, the overall complexity of our attack is 2 105.9 × 2 256 = 2 361.9 . Decreasing memory complexity. It is possible to decrease the memory complexity of the attack by avoiding the match on the linear relations between both k in and k out . Indeed, since the key-schedule of SKINNY is fully linear, we can first guess the intersection of k in and k out , and only then run the attack. The dimension of the intersection is 248 + 256 -384 = 120 and thus the memory complexity can be decreased to 2 249.5-120 = 2 129.5 . Table 5.2: Subkey bytes involved in the 23-round core attack.

Byte

k in k out # equations 0 K 0 [0], K 2 [2] K 18 [2], K 20 [4], K 22 [6] 2 1 K 0 [1], K 2 [0] K 20 [2], K 22 [4] 1 2 K 0 [2], K 2 [4] K 20 [6], K 22 [5] 1 3 K 0 [3], K 2 [7] K 20 [1], K 22 [0] 1 4 K 0 [4], K 2 [6] K 20 [5], K 22 [3] 1 5 K 0 [5], K 2 [3] K 20 [7], K 22 [1] 1 6 K 0 [6], K 2 [5], K 4 [3] K 20 [3], K 22 [7] 2 7 K 0 [7], K 2 [1], K 4 [0] K 20 [0], K 22 [2] 2 8 K 1 [2], K 3 [4] K 19 [4], K 21 [6] 1 9 K 1 [0] K 19 [2], K 21 [4] 0 10 K 1 [4] K 19 [6], K 21 [5] 0 11 K 1 [7], K 3 [1] K 19 [1], K 21 [0] 1 12 K 1 [6], K 3 [5] K 21 [3] 0 13 K 1 [3] K 19 [7], K 21 [1] 0 14 K 1 [5], K 3 [3] K 19 [3], K 21 [7] 1 15 K 1 [1], K 3 [0] K 19 [0], K 21 [2] 1
Data-time-memory trade-off. To decrease the data complexity of our attack, as described in Section 5.1.3, it is possible to only ask for the encryption of a portion of the whole codebook, let say 2 128-x plaintext/ciphertext pairs. In this case, the probability that we have access to the corresponding ciphertext of P is 2 -x and the attack has to be ran 2 x times to compensate. Overall, the complexity of our 23-round attack is then D = 2 128-x plaintext/ciphertext pairs, M = 2 129.5-x 128-bit words and T = 2 361.9+x encryptions. To expect at least one pair following the differential under the extra constraint on the plaintexts, x cannot be higher than (128 -105.9)/2 = 11.05. As explained in Section 5.1.3, in practice, given any pair of ciphertexts, we can enumerate the possible values for both k in and k out with a complexity roughly equivalent to the number of solutions. Such a procedure is described in Section 5.2.3. Thus, the trade-off does not increase the time complexity and the overall complexity of our attack is D = 2 117 , T = 2 361.9 and M = 2 118.5 .

Enumeration Procedure of k out for the 23-round Attack

In this section we describe a procedure to retrieve the possible values of k out in the case where the pair of ciphertexts is given. Its complexity is 2 128 simple operations, showing that the data/time/memory trade-off described in Section 5.1.3 can be applied without increasing the time complexity. Since the key is not applied on the full state, the procedure is more complex than a classical rebound but still relies on the fact that, on average, knowing the differences at both the input and output of an Sbox leads to one pair of actual values.

The steps of our enumeration procedure are depicted on Figure 5.2.3. The main idea is to propagate differences from the ciphertexts to Round 18, get the actual values since differences in this internal state are fully known, and propagate them back to the ciphertexts to obtain the key material we want. Except from Step 1 in which we guess 8 values, all following steps perform one guess each. Steps 7 and 8 have both a probability of success of 2 -8 and thus we expect only 2 13×8 = 2 104 partial solutions at the end of Step 8. Round 21

1 1 1 1 1 1 1 1 1 2 3 4 6 9 10 7 SC 1 1 1 1 1 1 1 1 1 2 3 4 6 9 10 7 K21 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 SR 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 MC Round 22 1 1 1 1 1 1 1 1 SC 1 1 1 1 1 1 1 1 K22 SR

Extension to 24 rounds

Our differential meet-in-the-middle attack against 23-round SKINNY can be extended to an attack against 24 rounds without increasing its overall complexity by using the generic improvement presented in Section 5.1.2. This can be achieved since on one hand the key-schedule is linear (and enough subkey bytes are involved in our attack so that the master key is fully retrieved) and on the other hand the subkey is only applied on half of the state in each round. The scenario of this new attack is quite similar to the original one:

1. Ask for the encryption of the whole codebook. 2. Pick 2 64 plaintext/ciphertext pairs (P , C ) such that M C -1 (C ) is constant on the last two rows as depicted in Figure 5.8. Here we exploit the fact that the round key is only applied on the first two rows of the internal state.

3. As for this original attack, compute all possible tuples (P , P i , i) for each value i of k in and each P from the structure defined at the previous step such that the state difference after the 6th S-box layer is 0x02 on bot.h active bytes.

4. Store them in a hash table. Note that the tuples are computed for all the 2 64 plaintexts selected at Step 2 so the memory complexity is 2 248+64 = 2 312 504-bit words.

5. For each value j of k out and each state S 23, coherent with Step 2 (i.e. 2 64 states, one for each possible value of the subkey K 23 ), compute all possible tuples (S 23, , S j 23, , j) so that the difference on the state before the 19th S-box layer is 0x64 on the four active bytes.

6. Check for possible matches on the hash table. The match is now performed on three quantities:

• the difference between the last states: C ⊕ C = MC• SR( SC(S 23 )⊕ SC( S 23 )). This is a 64-bit filter because the difference is zero on the two last rows since M C -1 (C) is constant on these rows.

• the filter on the keys (from key schedule equations): a 120-bit filter as for the original attack against 23 rounds (15 equations on 8 bits each, see Table 5.2).

• the filter on the keys (from equations describing the last round). Indeed, since k in ∪ k out generates the master key, K 23 can be rewritten as f (k in ) ⊕ g(k out ) where f and g are both linear and, because of the linearity of all the operations, the equation C = MC( SR( SC(S 23 ) ⊕ K 23 )) can thus be rewritten as C ⊕ MC( SR(f (k in )) = MC( SR( SC(S 23 ) ⊕ g(k out ))). This represents a 64-bit filter.

Repeat from

Step 2 until the right key is retrieved.

The attack has to be repeated enough times so that the structure contains at least one pair following the differential. Since during Step 2 we generate 2 64 pairs and since the probability of the differential is 2 -105.9 , the procedure has to be repeated 2 41.9 times. Thus the data complexity is 2 128 (i.e. the whole codebook is needed), the memory complexity is around 2 314 128-bit words and the time complexity 2 256+64+41.9 = 2 361.9 encryptions.

Note that previous improvements regarding both the memory and data complexities still apply and thus our attack has complexity: D = 2 128-11 = 2 117 plaintext/ciphertext pairs, M = 2 194-11 = 2 183 128-bit words and T = 2 361.9 encryptions.

An attack against 25 rounds of SKINNY-128-384

To mount a differential meet-in-the-middle attack against 25 rounds of SKINNY, we used the differential depicted in Figure 5.9. The best instantiation of this truncated differential has a probability of 2 -131 . By fixing the difference of the active bytes to 0x32 at the input and to 0x64 at the output, we found several instantiations with a high enough probability: 2048 with probability 2 -131 , 10240 with 2 -132 , 28672 with 2 -133 and finally 73728 trails with probability 2 -134 . Thus, the probability of the depicted differential is higher than 2 -116.5 . This differential is then extended by 4 rounds to the plaintext and 5 rounds to the ciphertext to reach 24 rounds as depicted in Figure 5.10.

The key bytes involved in the attack are given in Table 5.3, leading to a complexity of D = 2 128 data, T = 2 256 × 2 116.5 = 2 372.5 encryptions and M = 2 249.5 128-bit words. Furthermore, the dimension of the intersection between both k in and k out is once again 248 + 256 -384 = 120, which allows to reduce the memory complexity to 2 129.5 128-bit words.

As for the 23-round attack described above, this attack can be extended by one round without increasing its overall complexity. As a consequence, and after applying the data/time/memory trade-off presented in Section 5.1.3, the complexity of our attack against 25 rounds is D = 2 128-x plaintext/ciphertext pairs, M = 2 194-x 128-bit words and T = 2 372.5+x encryptions. In this case, x cannot be higher than (128-116.5)/2 = 5.75. Furthermore, we can again apply this trade-off without increasing the time complexity and thus the final complexity is D = 2 122.3 , T = 2 372.5 and M = 2 188.3 . a differential pattern and a total number of rounds will compute the complexity for a differential attack obtained through an early abort technique. For an attack on R rounds, the tool proceeds as depicted in Algorithm 5.2. It consists of repeating the following procedure for all the possible tuples (r in , r out ) such that r in + r out + r m = R. First, it propagates ∆ in (resp. ∆ out ) to the input (resp. to the output). Then it enumerates all the conditions to propagate a pair from D in to ∆ in and D out to ∆ out together with the minimal amount of key required to verify this condition. Finally, it computes the complexity on an early abort using the conditions computed.

L cplx ← {max{2 p+1 , 2 p+1+d in 2 }} ∪ L cplx First step 8: L cplx ← {2 p+d in +dout-n ∪ L cplx } Second step
L cplx ← {C • 2 nc-fc } ∪ L cplx 17: if C∈L cplx C < c * then 18: (r * in , r * out ) ← (r in , r out ) 19: c * ← C∈L cplx C 20: return c * , r * in , r * out
Using the tool, we were able to successfully attack a maximum of 22 rounds of SKINNY-128-384 with a data complexity of 2 122.75 and a time complexity of 2 367.1 . For the case of 23 rounds, the best attack has a time complexity of 2 398.5 , hence it is more expensive than an exhaustive search, though some new optimization techniques might make it work in the future. Algorithm 5.2 is the first step to a more general tool: Automatic key recovery. An ongoing work will compute the order on the condition that will minimize the complexity and will allow the use of more advanced techniques like parallel matching and parallel key recovery.

Parallel key recovery. In the case of SKINNY-128-384, we will show that performing a parallel key recovery cannot result in an attack exceeding 24 rounds. Indeed, we will consider lower bounds on the complexity: the number of solutions. Starting from the differential depicted in Figure 5.9, the complexity of a differential attack on 24 rounds of SKINNY-128-384 cannot be lower than:

2 116+128 (2 120 + 2 128 + 2 120+128-120 ) = 2 373 ,
where the parameters are p = 116, d in = 128, d out = 128 (Figure 5.10), and C k = (2 120 + 2 128 +2 120+128-120 ). Indeed, considering both parts in parallel, we have 64 + 64 + 64 + 56 key bits involved in the input for a condition on 128 bits of recovering the input difference (so 2 120 key candidates), and 64 + 64 + 64 + 56 + 8 key bits involved in the output part, with 128-bit conditions (so 2 128 key candidates). The memory need is 2 128 for the parallel computation. The linear relations between both partial keys are 64 + 56, given by the even and odd subkeys respectively. So the previous result provides a lower bound on the complexity that such an attack would obtain. If we try to add one extra round and attack 25 rounds, a minimal additional factor of 2 64 has to be added to one of the parallel computations, as the number of partial solutions will increase by this amount. This would be too expensive and we can therefore conclude that we cannot build classical differential attacks on 25 rounds of SKINNY-128-384 based on this distinguisher.

This extra round can be added in our case due to the different nature of the attack, and its relation to MITM cryptanalysis. Therefore, it is fair to conclude that in this case, differential meet-in-the-middle attacks are more powerful than classical differential attacks, reaching one extra round while having a similar complexity.

Conclusion

We introduced a new cryptanalysis technique: differential meet-in-the-middle and provided an application to SKINNY-128-384 resulting in a 2-round improvement of the best single key attack. The emergence of this new type of attack raises some interesting questions. One may wonder about the criteria required for a cipher to be more vulnerable to differential MITM attacks rather than classical differential attacks or classical meet-the-middle attacks. Also, the set of keys involved in differential MITM attacks does not always coincide with the set of keys required to mount a classical differential attack, it would be interesting to have a better understanding of the behavior of these key sets. Lastly, we can wonder whether it is possible to combine MITM with some other type of attack like linear attacks or differential-linear.

Chapter 6

Quantum impossible differential attacks

This chapter is inspired by [DNS22] This chapter organizes as follows: first, we will study the multiple collision search problem in the quantum setting to solve the Data Generation and the Pair Sieving step of the impossible differential framework. Then we will describe a quantum version of the early-abort algorithm. Finally, we will give an application of this technique to SKINNY and AES.

Quantum Collision Search and Pair Generation

The first step of impossible differential attacks is to solve a limited birthday problem. Following the definition given in Section 6.1, we want to generate data using structures that will later be used to create differential pairs. In the quantum setting, we will consider the two steps Data Generation and Pair Sieving at the same time. For this step, we use existing quantum collision search algorithms [START_REF] Kaplan | Quantum Differential and Linear Cryptanalysis[END_REF][START_REF] Bonnetain | Finding many Collisions via Reusable Quantum Walks[END_REF]. Indeed, both quantum and classical algorithms for the limited birthday problem reduce it first to a multiple collision search problem. Problem 6.1 (Multiple collision search). Let f : {0, 1} n → {0, 1} m be a random function,with n ≤ m ≤ 2n and k such that k ≤ 2n -m. Given query access to f , find 2 k collision pairs of f , i.e., 2 k pairs of entries (x, y) such that x = y and f (x) = f (y).

The constraints on k, n, m above ensure that enough collisions actually exist. For the best-known classical and quantum algorithms, the query complexity matches the time complexity, although the memory consumption can be quite large depending on the respective values of k, n, m. In the classical setting, the problem is solved in time O 2 (m+k)/2 . In the quantum setting, the best-known complexities are summarized as follows in [START_REF] Bonnetain | Finding many Collisions via Reusable Quantum Walks[END_REF]:

Theorem 6.1 (From [Bon+23]). Let f : {0, 1} n → {0, 1} m , n ≤ m ≤ 2n be a random function. Let k ≤ 2n -m.
There exists an algorithm finding 2 k collisions in quantum time O 2 C(k,m,n) (incl. qRAM gates), and using O 2 C(k,m,n) quantum queries to f , where:

C(k, m, n) = max 2k 3 + m 3 , k + min m -n, m 4 .
The corresponding query lower bound, valid for any acceptable k and m, was given by Liu and Zhandry in [START_REF] Liu | On Finding Quantum Multi-collisions[END_REF]: Ω(2 2k/3+m/3 ). It is conjectured to be tight for all n ≤ m ≤ 2m and k ≤ 2n -m. Note that Theorem 6.1 includes as special cases the Brassard-Høyer-Tapp collision search algorithm [START_REF] Brassard | Quantum Cryptanalysis of Hash and Claw-Free Functions[END_REF] (k = 0, m = n) and Ambainis' element distinctness algorithm [START_REF] Ambainis | Quantum Walk Algorithm for Element Distinctness[END_REF] (k = 1, m = 2n). For the latter, a precise analysis was done by Childs and Eisenberg [START_REF] Childs | Quantum algorithms for subset finding[END_REF]. They showed that the polynomial factor in the complexity was essentially a constant. By running ( π 2 2 m/3 ) 2 evaluations of f , and additional memory operations, a solution is obtained with probability exponentially close to 1. The algorithm of [START_REF] Bonnetain | Finding many Collisions via Reusable Quantum Walks[END_REF], similarly to Ambainis', relies on a quantum walk, so we can also expect its polynomial factor to be small.

In this paper, we assume the evaluation of the function to be the most costly step, so we take these complexities (including the one of Theorem 6.1) without O and with a multiplicative factor π 2 4 only. We focus hereafter only on the exponent.

Quantum Data Generation. Like the classical ones, the quantum algorithms for Pair Generation consist in finding multiple collisions in structures. For any input (resp. output) structure we can define a function H

x : {0, 1} d in → {0, 1} n-dout (resp. H x : {0, 1} dout → {0, 1} n-d in )
, which is the restriction of E to the structure, composed with a linear mapping that projects to a space orthogonal to D out (resp. D in ): H x (y) = L • E(y) .Thus, any collision of H x is a pair y, z such that:

• y, z ∈ T x =⇒ y ⊕ z ∈ D in , and • H x (y) = H x (z) =⇒ L (E(y) ⊕ E(z)) = 0 =⇒ E(y) ⊕ E(z) ∈ D out
by definition of L and H x . The same goes for H x by replacing E by its inverse.

Assumptions on the Attack

Recall that we have divided

K in∪out = K 1 × K 2 × • • • × K ,
Build T 1 (k 1 ) = {p ∈ T 0 , T 1 (p, k 1 ) = 1} 3: for all k 2 ∈ K 2 do 4: Build T 1 (k 1 ) = {p ∈ T 1 , T 2 (p, k 1 , k 2 ) = 1} • • • 5: for all k ∈ K do 6: Sieve the table T -1 (k 1 , . . . , k -1 ) according to T , obtain T 7: If T = ∅, then return (k 1 , . . . , k ) • • • Algorithm 6
.1 enumerates all the key guesses for which there exists no invalidating pair, using nested loops. The quantum version of this algorithm relies on nested amplitude amplification subroutines, using amplitude amplification. In order to ensure its correctness, we first need to make some classical assumptions on the attack. If these assumptions are satisfied, then we will show that our algorithm solves Problem 6.2 with probability 1.

The first assumption consists in considering the number of key candidates. Indeed, we want a single key solution, it will happen as long as N is large enough. Assumption 1. Given the initial table T 0 , there exists a single key (k 1 , . . . , k ) such that T (k 1 , . . . , k ) = ∅.

Second, we need global bounds on the size of intermediate tables to control the size of the quantum memory required. In the following, we will use the notation N i (k 1 , . . . , k i ) := |T i (k 1 , . . . , k i )|, and N 0 := N .

Assumption 2. No intermediate table exceeds twice its expected size:

∀k 1 , . . . , k i , N i (k 1 , . . . , k i ) ≤ 2 i j=1 σ j N .

Quantum Key Recovery

91

Assumption 2 can be reduced to the assumption that, though it can variate between key guesses, there is an upper bound σ i on the probability to be filtered. This is a heuristic assumption related to the independence of the filtering conditions, which is supposed to hold for the targeted cipher. Assumption 3. Let T i (k 1 , . . . , k i ) be any intermediate table (incl. the case T 0 ). Then:

∀k i+1 , P p∈T i (k 1 ,...,k i ) (T i+1 (p, k 1 , . . . , k i+1 )) ≤ σ i .
In other words, the probability to pass the condition T i can variate, but it has some global upper bound σ i .

Using the Chernoff inequality, it is possible to upper bound the maximal size of intermediate tables over all key guesses, hence recovering Assumption 2. Lemma 6.1. Under Assumption 3:

E (N i (k 1 , . . . , k i )) ≤ i j=1 σ j N 0 ,
and:

P   ∃i, ∃k 1 , . . . , k i , N i (k 1 , . . . , k i ) ≥ 2 i j=1 σ j N 0   ≤ i=1 i j=1 |K j | e -2 i j=1 σ j 2 N 0 .
Proof. Let us fix i and a choice of k 1 , . . . , k i . For all pairs p in T i-1 (k 1 , . . . , k i-1 ), the events that p falls in T i (k 1 , . . . , k i ) are independent and of probability less than σ i (by Assumption 3). This also allows us to deduce:

∀k 1 , . . . , k i , P p∈T 0 (p ∈ T i (k 1 , . . . , k i )) ≤ P p∈T 0 (T 1 (p, k 1 ) = 1) × . . . × P p∈T i-1 (k 1 ,...,k i-1 ) (T i (p, k 1 , . . . , k i ) = 1) ≤ i j=1 σ j .
By independence, we deduce

E (N i (k 1 , . . . , k i )) ≤ i j=1 σ j N 0
Next, we apply a Chernoff bound for this given choice of k 1 , . . . , k i :

P   N i (k 1 , . . . , k i ) ≥ 2 i j=1 σ j N 0   ≤ P   N i (k 1 , . . . , k i ) -E (N i (k 1 , . . . , k i )) ≥ i j=1 σ j N 0   ≤ e -2 i j=1 σ j 2 N 0
By summing this over all choices of key sequences, we obtain the bound of Lemma 6.1.

Chapter 6. Quantum impossible differential attacks Thanks to Lemma 6.1, we can check that Assumption 2 is satisfied with high probability. In practice, we can just stop the filtering process when the intermediate tables become expectedly too small, e.g. of size below 2 16 .

Filtering of a Table

From now on, we assume that Assumption 1 and Assumption 2 are satisfied. Let M i = 2 j≤i σ j N 0 be the (maximal) size of intermediate tables T i at level i. We manipulate quantum states that contain either:

• Partial key guesses k i : in that case, we just use a register with as many qubits as there are bits in k i

• Intermediate tables T i : in that case, we allocate M i = 2 E (N i ) qubit registers, where each register holds either a pair or a dummy element. By Assumption 2, this is enough space to represent all intermediate tables; thus, although this data can be in superposition (as it depends on the key guess), there is no case in which the table would exceed the space that we allocated to write it.

We introduce additional notations to make precise time and memory complexity estimates. Since we want to count the time complexity relatively to a cipher evaluation, we introduce: • t i the time to evaluate the condition T i ; • t the time to perform an operation such as a copy or swap on a register that contains a pair. We count the memory complexity in the number of pairs (a pair can be stored on a 4n-bit register). Lemma 6.2. For all i, there exists a quantum circuit F i that maps:

|T i (k 1 , . . . , k i ) |k i+1 |0 → |T i (k 1 , . . . , k i ) |k i+1 |T i+1 (k 1 , . . . , k i , k i+1 ) | * ,
where * are computation qubits that depend only on k 1 , . . . , k i , k i+1 . The time complexity, relative to a cipher evaluation, is bounded by:

M i (t i+1 + t) in the QRAQM model M i (t i+1 + (log 2 M i ) 2 4 t

) otherwise and the memory complexity by M

i or M i (log 2 M i ) 2 4
(mainly due to the * state).

Proof. We start by computing the condition T i for all pairs in the table T i (k 1 , . . . , k i ).

We store the result (0 or 1) in additional qubits. We initialize the output table T i+1 with M i+1 "dummy" pairs. Then, we take all the good pairs in T i and move them to T i+1 . There are two ways to do so.

• If we can use qRAM gates, this operation is efficient. We create a quantum register that contains a counter c, counting the number of good pairs which have been seen so far. The value of the counter at each time is a deterministic function of 6.2. Quantum Key Recovery 93 T i . However, T i is in superposition, and the counter is a superposition as well (entangled with the state of the table).

|T i (k 1 , • • • , k i ) T i C 0 • • • C M i -1 |T i (k 1 , • • • , k i ) |k i+1 |k i+1 |0 |T i+1 (k 1 , • • • , k i+1 ) |c |c
To move all the good pairs, we apply a sequence of M i subcircuits C j (0 ≤ j ≤ M i -1). Each C j does three operations: 1) read the pair at index j, check if it is good; 2) controlled on the pair being good, increment the counter c; 3) controlled on the pair being good, copy the pair at index c in T i+1 .

Thus, the sequence of circuits requires |T i | = M i increment and copy operations. The use of qRAM gates comes from the copies. Indeed, the position at which we need to write in the next table depends on the current counter c. However, the value of c depends on the position of the good pairs among the table T i , so it depends on T i itself. Since T i , throughout the algorithm, is in superposition, this functionality requires qRAM gates.

• The alternative to qRAM gates is to apply a reversible sorting network, which will move all the elements of T i flagged "1" to, say, the M i first indices in the memory. We then copy these M i cells (conditioned on whether the copied pair is actually good).

In the second case, the amount of computations increases by a factor (log 2 M i ) 2 4 due to the sorting network. However, the sorting network contains only comparators and swaps and does not require recomputing the filtering conditions.

It should be noted that the | * is here to ensure the reversibility of these operations. We could perform uncomputations to erase it immediately, but we prefer to wait until the table T i+1 (k 1 , . . . , k i , k i+1 ) is not needed anymore. Then we will erase not only the table but also all of the computations that led to it. Chapter 6. Quantum impossible differential attacks Remark 6.1 (Reversible sorting networks). In order to sort a table of 2 values, we use the odd-even mergesort of Batcher [START_REF] Batcher | Sorting Networks and Their Applications[END_REF]. It uses S(2 ) = 2 -1 ( -1) 2 + 2 -1 comparators and swaps of registers, that we can approximate to 2 -2 ( 2 ) n-qubit register operations of time t each. In order to make it reversible, we need S(2 ) qubits that contain the results of the comparators.

Exact Early Abort

We can build our early abort algorithm by interleaving calls to the filtering circuit of Lemma 6.2 with instances of exact amplitude amplification. For a current set of partial key guesses (k 1 , . . . , k i ), with a corresponding intermediate Next, we assume the existence of U i+1 for some i ≥ 1, and we show how to build U i from U i+1 . Consider an input state of the form: |k 1 , . . . , k i |T i-1 (k 1 , . . . , k i-1 ) . We first use the circuit F i-1 of Lemma 6.2 to create the table |T i (k 1 , . . . , k i ) (as well as the additional | * state). Next, we try to find k i+1 such that k 1 , . . . , k i , k i+1 can be completed into the good key. We have:

• an auxiliary state |T containing |k 1 , . . . , k i , the tables T i-1 and T i ;

• a search space K i+1 of fixed size, containing exactly one or zero solution;

• a test function that, using the auxiliary state, can find whether k i+1 can be completed into the good key: this is the unitary U i+1 given by our recurrence hypothesis.

By using a single instance of amplitude amplification, we obtain a unitary that tests whether the current auxiliary state leads to a solution or not, which uses less than π 2 |K i+1 | + 2 calls to U i+1 . We apply this unitary. Finally, we uncompute the circuit F i-1 to delete the table T i and the associated computation qubits.

We have by recursion, and by Lemma 6.2 (assuming the qRAM case):

   time(U i ) = π 2 |K i+1 | + 2 (t + time(U i+1 )) + 2M i-1 (t i + t) time(U ) = 2M -1 (t + t) so we approximate time(U i ) to: 2 j=i M j-1 (t j + t) π 2 j-i j m=i+1 |K m | .
The memory complexity is equal to the sum of all M j-1 (t j +t) for the involved filtering circuits. In practice, the size of the first table dominates all the others significantly, and we can approximate it by M i-1 (t i + t).

Our early abort algorithm is then obtained by using U 1 in a quantum search for k 1 , where we start from the table T 0 (this one is also an exact amplitude amplification since we assumed that there was exactly one solution). The memory complexity is dominated by |T 0 |. Corollary 6.1. Under our assumptions, there exists a quantum early abort algorithm that finds the single good k 1 , . . . , k in time:

2N j=1 (t j + t)   j-1 m=1 σ m   π 2 j j m=1
|K m | , using N (max t i + t) qubits, in the QRAQM model.

We can also drop the QRAQM requirement by using the QRAQM-free version of Lemma 6.2. This version replaces the multiplicative factor t i + t by t i + (log 2 M ) 2 4 t when filtering a table of size M . Therefore, we can simply upper bound the total time complexity by multiplying the formula of Corollary 6.1 by the maximum of all these factors. Corollary 6.2. Under our assumptions, there exists a quantum early abort algorithm that finds the single good k 1 , . . . , k in time:

N max i t i + (log 2 N ) 2 4 t j=1 (t j + t)   j-1 m=1 σ m   π 2 j j m=1 |K m | , using N max t i + (log 2 N ) 2 4
t qubits, but no QRAQM.

Compared with the classical formula, we have put a square root on each |K i |. Indeed, the algorithm that we obtain is no more than Algorithm 2.4 in which each exhaustive search loop on a partial key subspace is replaced by a quantum search.

Improved early abort in Practice

In some cases, and using QRAQM, we can improve the computation of intermediate tables given in Lemma 6.2. Since usually, the treatment of the first table (T 0 , of size N ) dominates the other steps, we will focus on this one. Note that these improvements do not incur any change in the rest of the algorithm.

Precomputation of the Conditions. Let us assume that the first filtering condition T 1 (p, k 1 ) depends actually only on a small part of the pair p, say p 1 . Instead of having to compute T 1 for all p in T 0 , we can recompute the entire lookup table of T 1 . Then, given k 1 , we can obtain the next pairs in two steps: (1) we read the values of the p 1 such that T (p 1 , k 1 ) = 1; (2) for each p 1 , we fetch the pairs that have this value.

Previously, we needed a time N (t 1 + t) (with QRAQM) to compute T 1 (k 1 ) for a given k 1 . Now, we can reduce this time to 2σ 1 N t, assuming the precomputation of T 1 . Indeed, we can sort the pairs in T 0 by their p 1 value, in order to read them efficiently.

We can also use this precomputation at a later step. For example, if T 2 (p, k 1 , k 2 ) depends actually only on p 2 , then we can also:

• precompute the lookup table of T 2 (•, k 1 , •) for a given k 1 , before running the nested search on k 2 ; • for a given k 2 , compute T 2 (k 1 , k 2 ) efficiently in time 2σ2σ 1 N t instead of time 2σ 1 N (t 2 + t)
However, this now requires sorting T 1 (k 1 ) with respect to p 2 when we compute it, and this additional term must be taken into account.

Quantum Filtering. It is possible to speed up the filtering using quantum search. Indeed, when computing T 1 (k 1 ) from T 0 , we expect to find σ 1 N filtered pairs among the N initial ones. In the QRAQM model, we can find filtered pairs using a Grover search among all the pairs. We need about 1 √ σ 1 search iterates, thus all of them are found in time √ σ 1 N instead of N . However, we must fix a number of quantum search iterates for a computation that is done in superposition over k 1 . Thus, there will be some probability of error. Assumption 2 tells us that the actual number of filtered pairs, at any level, does not exceed twice its expectation. By strengthening this assumption a little, we can suppose that the actual probability of success of a search for good pairs will fall in [a/2; 3a/2] where a is the expected success probability. Then, by Lemma 5 in [START_REF] Bonnetain | Quantum Security Analysis of AES[END_REF], the search succeeds with a probability larger than 3/4 (if we measured its result immediately). If the table being constructed is large enough, this is sufficient. Lemma 6.4. There exists a quantum circuit QF i that performs the same operation as in Lemma 6.2, up to an error ε bounded by ε ≤ e -1 4 M i+1 . In the QRAQM model, the time complexity, relative to a cipher evaluation, is bounded by: 2M

i π 2 √ σ i+1 (t i+1 + t),
and the memory complexity by M i .

Application to SKINNY

97

Proof. Since we are building the table T i+1 from T i and a new key guess k i+1 , we know that there is a maximum of 2 E (N i+1 ) pairs to look for in all cases. We run in parallel 4 E (N i+1 ) = 2M i+1 quantum searches with π 4 1 √ σ i+1 search iterates each. The search space is the current table of all pairs. The condition of success is the test function T i . By our assumption, such an individual search succeeds with a probability of at least 3/4 for all values of k.

We move all the obtained (possibly) good pairs into the next table. At this point, errors occur if the individual searches fail to obtain all the N i independent pairs. We perform the following test on the search results: we test if at least 2 E (N i+1 ) contains good pairs. If this is the case, then we can expect to have met all the N i+1 pairs independently (up to some random collisions). We can write the result of this test in a qubit, but we do not measure it: we only use it to bound away the cases of failure.

Let us consider a fixed key k. We already know that N i+1 ≤ 2 E (N i+1 ). We denote by X the total number of successful searches among 4 E (N i+1 ). Hence we can write:

X = 4 E(N i+1 ) j=0 X j
By our assumption, each X j has expectation at least 3/4, hence

E (X) = 4 E(N i+1 ) j=1 E (X j ) = 3 E (N i+1 ) .
Therefore, by Chernoff bounds, we obtain:

P T i (X ≤ 2 E (N i+1 )) ≤ P T 0 X ≤ 2 3 E (X) ≤ e - 2(E(X)/3) 2 4 E(N i+1 ) ≤ e -E(N i+1 ) 2 = e -1 4 M i+1 .
By using this erroneous QF i in a quantum search with t iterates, we will obtain a total error amplitude of about t √ ε (i.e. t 2 failure probability). This is the result of a standard hybrid argument [START_REF] Bennett | Strengths and Weaknesses of Quantum Computing[END_REF]. Therefore, if M i+1 is sufficiently small (typically 2 16 ), it remains negligible.

Application to SKINNY

In this section, we describe an impossible differential attack on SKINNY-128-256 and its quantization, Table 6.1 allows the comparison with previous work. The specifications of the SKINNYblock cipher family are given in Section 5.2.

Classical Impossible Attack

In this section, we give an impossible differential attack on SKINNY that achieves 21 rounds based on work from [START_REF] Sadeghi | Cryptanalysis of Reduced round SKINNY Block Cipher[END_REF]. Since the goal is to recover the full 256-bit tweakey, the generic bound is 2 256 . Impossible Pattern. We give the pattern in Figure 6.2.

Pair Generation. Here we give some parameters of the attack described in [START_REF] Sadeghi | Cryptanalysis of Reduced round SKINNY Block Cipher[END_REF]. With our notation, we get d in = 32, d out = 72, c in = 24, c out = 72, N = 2 103.17 , where N ensures that only one subkey will remain in the end.

early abort. In this section we will describe the tweakey recovery. In Table 6.2 we give the cost of each step. In the end, the time complexity for the classical early abort is 2 151.17 .

Quantum impossible attack

Since 2 plaintext-ciphertext pairs are required to discriminate the right tweakey, the exhaustive search with Grover's algorithm has a complexity of 2 129.65 encryptions. Our quantum attack will be valid if we manage to outperform this. From Section 6.1 we compute the complexity of the quantum pair generation as Q N = 2 119.17 encryptions (in the classical setting C N = 2 128 encryptions).

Filtering. Following the idea of Section 6.2, we build the quantum key recovery based on the classical key recovery described in Section 6.3.1. We use the formula of Corollary 6.1 to compute the quantum complexity of this step as:

2N j=1 (t j + t)   j-1 m=1 σ m   π 2 j j m=1 |K m | .
This formula features a (t + t i ) term that carries the complexity of 4n bit operations and the complexity of performing the test T i . We assume that (t + t i ) is smaller than the complexity of the encryption, so by our formula with the values in Table 6.2, we get a quantum time of about 2 104.32 encryptions, with QRAQM. Using the formula of Corollary 6.2, we can instead have a quantum time of 2 117.46 encryptions, without QRAQM. The (quantum) memory complexity in the first case corresponds to the table of 2 95.17 pairs remaining after the first condition 1.a has been enforced, which is independent of the key guesses. In the second case, we multiply the memory by a factor 2 11.14 due to the sorting network.

Putting together the complexities of pair generation and key recovery, we give the total complexity for 21 rounds of SKINNY-128-256 in Table 6.3. We can propose two quantum attacks: 1) using QRAQM, we use a quantum pair generation and filtering algorithms to reach a complexity of about 2 119.17 encryptions (Q2 setting). 2) Without QRAQM, we use the classical pair generation in classical time 2 128 , which we combine with a quantum early abort step in quantum time 2 117.46 . The attack is now a Q1 attack since only the pair generation requires queries. The attack is faster than a Grover search of the full 256-bit secret key, which would be slightly above 2 128 quantum operations (and the difference is more significant if classical operations are cheaper than quantum ones).

Application to 7-round AES

In this section, we use our framework to improve the key-recovery attacks against 7-round AES-192 and AES-256 in the quantum setting (the best previous attacks were Square attacks in [START_REF] Bonnetain | Quantum Security Analysis of AES[END_REF], see Table 6.4 for a comparison with previous work). The path of the attack that we consider is the one from [Mal+10] (Figure 6.3).

Description of AES-256

The Advanced Encryption Standard [FIP01] is a Substitution-Permutation Network (SPN) that can be instantiated using three different key sizes: 128, 192, and 256 bits. The 128-bit plaintext initializes the internal state viewed as a 4 × 4 matrix of bytes, i.e. values in the finite field F 256 , which is defined using the irreducible polynomial x 8 + x 4 + x 3 + x + 1 over F 2 . Depending on the version of the AES, N r rounds are applied to that state and N r = 14 for the 256-bit version. Each of the N r rounds (see Figure 6.4) applies four operations to the state matrix (except in the last round where the MixColumns operation is omitted):

• AddRoundKey (AK) adds a 128-bit subkey to the state.

• SubBytes (SB) applies the same 8-bit to 8-bit invertible S-Box S 16 times in parallel on each byte of the state.

• ShiftRows (SR) shifts the i-th row left by i positions.

• MixColumns (MC) replaces each of the four columns C of the state by M × C where M is a constant 4 × 4 maximum distance separable matrix over F 256 .

After the N r -th round has been applied, a final subkey is added to the internal state to produce the ciphertext. The key expansion algorithm to produce the N r + 1 subkeys is described in Figure 6.5. We refer to the original publication [FIP01] for further details. 3. M C -1 (w 5 [0, 1, 2, 3]) is a single byte: this is an independent condition on k 7 [0, 7, 10, 14] and the corresponding ciphertext bytes. For a given pair, there are on average 2 8 guesses of k 7 that satisfy this condition. Thus each pair removes 2 56 key guesses from a space 2 128 . In order to have a single remaining key guess, we take N = 2 78.5 . These pairs can be obtained in about 2 99.8 Q2 queries. There are 4 subkey spaces: K 1 = k 0 [0, 5, 10, 15], K 2 = k 0 [2, 7, 8, 13], K 3 = k 7 [0, 7, 10, 14] and K 4 = k 1 [0, 10, 2, 8], each of size 2 32 . The filtering probabilities are σ 1 = 2 -16 , σ 2 = 2 -16 , σ 3 = 2 -24 . Similarly to Table 6.2, we summarize the successive steps in Table 6. 5.

Using the simple early-abort strategy, we obtain a classical time complexity:

2 32 2 78.5 Build T 1 +2 32 2 62.5 Build T 2 +2 32 2 46.5 Build T 3 +2 32 2 22.5 Sieve T 3 = 2 150.5 . And using Corollary 6.1, we obtain a quantum time complexity:

2N π 2 |K 1 | + π 2 2 σ 1 |K 1 ||K 2 | + π 2 3 σ 1 σ 2 |K 1 ||K 2 ||K 3 | + π 2 4 σ 1 σ 2 σ 3 |K 1 ||K 2 ||K 3 ||K 4 | max i (t + t i ) ,
where t + t i is the time to evaluate the test functions relatively to an encryption. In the case of AES, to facilitate comparison with [START_REF] Bonnetain | Quantum Security Analysis of AES[END_REF], we count the number of S-Boxes, the S-Box being the most costly component in quantum circuits for the AES. We remark that computing each test function requires 8 S-Boxes, so we approximate the factor t + t i by 8. This gives:

2 79.

Conclusion 107

We use 2 78.5 qubits with QRAQM access to store the pairs. The previous best quantum attacks on 7-round AES-192 and AES-256 are the quantum Square attacks of [START_REF] Bonnetain | Quantum Security Analysis of AES[END_REF], with respectively 2 102.73 and 2 106.73 reversible S-Boxes. So far our attack is comparable.

Quantum early abort. Following the discussion in Section 6.2.4, we can use quantum searches to speed up the construction of successive tables. The table T 1 , which is of expected size 2 62.5 , is constructed in time 4 π 2 √ σ 1 |T 1 | instead of |T 1 |. We do likewise for T 3 . Finally, when sieving T 3 with respect to a guess of k 1 [0, 10, 2, 8], we can use a quantum search instead of going through the table. The time complexity becomes:

π 2 |K 1 | 4N π 2 √ σ 1 + π 2 |K 2 | 4N σ 1 π 2 √ σ 2 + π 2 |K 3 | 4N σ 1 σ 2 π 2 √ σ 3 + π 2 |K 4 | π 2 2N σ 1 σ 2 σ 3 max i (t + t i ) = max i (t + t i ) π 2 5 |K 1 ||K 2 ||K 3 ||K 4 | 2N σ 1 σ 2 σ 3 + 4N π 2 2 |K 1 |σ 1 + π 2 3 |K 1 ||K 2 |σ 1 √ σ 2 + π 2 4 |K 1 ||K 2 ||K 3 |σ 1 σ 2 √ σ 3
We can now replace with our numerical values, obtaining: where the dominant term is the computation of the table T 3 . The memory complexity stays the same as before.

Conclusion

In this chapter, we provided a quantized version of impossible differential attacks answering the open problem from [START_REF] Bonnetain | Quantum Security Analysis of AES[END_REF]. Our framework, which includes a generic complexity analysis, could be a good tool for analyzing the post-quantum security margin of symmetric primitives, as we have shown with SKINNY-128-256. Regarding AES, we have only been able to provide limited improvements of the 7-round attacks of [START_REF] Bonnetain | Quantum Security Analysis of AES[END_REF]. Currently, our best attack is limited by the generation of pairs. While the key recovery step benefits significantly from quantum search, potentially up to a complete quadratic speedup on its complexity, the first step seems a relatively more difficult problem in the quantum setting, as the limited birthday problem reaches a less than quadratic speedup. Consequently, as observed in [START_REF] Bonnetain | Quantum Security Analysis of AES[END_REF] with other attack families, quantum impossible differential attacks need to be optimized differently from the classical ones to balance the complexity terms of the different steps in the quantum setting. Indeed, one could for example try to reduce the data used as much as possible, and in particular, to make the pair generation step completely classical (thereby falling in the Q1 setting).

Conclusion

In this thesis, I have presented a collection of scientific contributions that come from collaborations with other cryptographers. All of these unprecedented human experiences were very rich in science and allowed me to develop expertise in differential cryptanalysis.

As shown through this thesis, differential cryptanalysis is, under many forms, a very powerful cryptanalytic technique in the context of block ciphers. Indeed, in Chapter 4, we have shown that even the block ciphers published in the most renowned conferences can show critical weaknesses to differential attacks. However, building differential attacks can be a complex and time-consuming task since it requires looking into the details of the round function operations to exhibit weaknesses to exploit. In this regard, the development of an automatic tool would have the potential to greatly facilitate the analysis process of the designers. Indeed, the choice of security claims could be more refined hence optimizing efficiency while preserving security. However, designing an automatic tool is a difficult task since new techniques and refinements are continually proposed and would need to be taken into account for the tool to be complete.

The design of an automatic differential tool is part of an ongoing work. The tool will take as input a description of the cipher (round function and key schedule), a differential trail (input and output difference with associated probability and length) as well as the total number of rounds R that we want to attack. It will output a description of the best differential attack on R rounds together with its complexities, hence a description of the key recovery rounds as well as a description of the key recovery procedure. The first step is to obtain a tool that would automatically find the attack described in Chapter 4 (or a better attack) when applied on SPEEDY-7-192. As a consequence, the tool needs to encapsulate all the known optimizations starting with the one we used in the attack such as probability-sieving trade-off, parallel merging, and additional input-output siveing. The most challenging task is to design the optimization for the early abort technique since it requires our algorithm to recognize the ordering on the propagation conditions that would minimize the complexity. Indeed, in some cases, trying all the orders require too many operations. Therefore, the first step is to find a good model in which we can describe the key recovery optimization problem.

Another open problem concerns differential-MITM cryptanalysis depicted in Chapter 5. Indeed, we could wonder about the application of this technique to constructions other than blockciphers, for instance, hash functions. In addition, the techniques described in Chapter 5 can be combined with the ones from [EFK15] that 109 110 Chapter 6. Quantum impossible differential attacks allow to exploit differential in the key part. Therefore we can expect this combination of techniques to result in a powerful preimage attack.

1. 1 5 . 5

 155 Building a key recovery from a distinguisher . . . . . . . . . . . . . . . . . . 1.2 Meet-In-The-Middle framework . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Partial Matching framework . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Sieve-in-the-middle framework . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Extended differential distinguisher with key recovery rounds . . . . . . . . . 2.2 Generic presentation of an impossible differential attack, with the notations used in this paper. The differential ∆ in ↔ ∆ out through the middle rounds E imp is impossible. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 The structure of a differential-linear distinguisher. . . . . . . . . . . . . . . 3.1 The four different scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 The round function of Chaskey. . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Conditions on the differential transitions for the 3 first rounds of Chaskey . 4.1 The round function of SPEEDY-r-192 for the first r -1 rounds (left) and the last round (right). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Generating (r + 1.5)-round trails from core r-round trails and extending them to mount (r + 3)-round attacks on SPEEDY. . . . . . . . . . . . . . . . . . . 4.3 5.5-round differential trail used to attack SPEEDY-7-192. The red part corresponds to the 4-round core trail, while the blue part corresponds to the 1.5-round extension. Grey bits are bits with unknown differences. The two states surrounded in red are the starting and final states of the multiple differentials considered. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Key recovery part of the 7-round attack against SPEEDY-7-192 . . . . . . . 4.5 Transition of rows 26, 28 and 30 through the inverse of the second SB of round 0. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Parallel key guessing for Rows [18,19,20,21,23]. . . . . . . . . . . . . . . 5.1 A high-level description of the Differential MITM technique. . . . . . . . . . 5.2 A high-level description of the improved Differential MITM technique. . . . 5.3 Round function of SKINNY [Bei+16] . . . . . . . . . . . . . . . . . . . . . . 5.4 Tweakey schedule of SKINNY. All tweakey arrays TK1, TK2 and TK3follow the same transformation with the only exception that no LFSR is applied to TK1.[START_REF] Beierle | The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS[END_REF] . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Truncated differential trail for the attack on 23 rounds. . . . . . . . . . . . 5.6 Core attack against 23 rounds of SKIN N Y -128/384. Knowledge of blue key bytes allows to compute values of green ones and thus to propagate differences. No difference in both white and red bytes, but the red ones are required to compute green bytes. Indexes in subkey bytes are the indexes of the corresponding master key bytes. The equivalent subkeys U i are computed as M C(SR(K i )), from the original subkeys K i . . . . . . . . . . . . . . . . . 5.7 Enumeration procedure of k out for the 23-round attack. Differences in blue cells and actual values in red cells are known. No difference in white cells. . 5.8 Last round of the attack against 24 rounds. . . . . . . . . . . . . . . . . . . 5.9 Truncated differential trail for the attack on 25 rounds. . . . . . . . . . . . 5.10 Core attack against 24 rounds of SKINNY-128-384. Knowledge of blue key bytes allows to compute values of green ones and thus to propagate differences. No difference in both white and red bytes, but the red ones are required to compute green bytes. Indexes in subkey bytes are the indexes of the corresponding master key bytes. . . . . . . . . . . . . . . . . . . . . . . 6.1 The quantum circuit of Lemma 6.2 . . . . . . . . . . . . . . . . . . . . . . . 6.2 Impossible pattern (from [SMB18]). . . . . . . . . . . . . . . . . . . . . . . 6.3 Impossible differential attack on 7-round AES . . . . . . . . . . . . . . . . . 6.4 Description of one AES round and the ordering of bytes in an internal state 6.5 Key schedule of AES-256 . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii List of Tables 3.1 Probability that adding one basis element affects the output difference. The techniques we developed in [Bei+22] allowed to add the elements colored in red to the basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.1 Table representation of the 6-bit S-box S . . . . . . . . . . . . . . . . . . . 45 4.2 The bit-permutation P for SPEEDY-r-192 with β = 7 and γ = 1. . . . . . . 46 4.3 Summary of SPEEDY cryptanalysis . . . . . . . . . . . . . . . . . . . . . . 47 4.4 Summary of all the 1-bit input differences α to 1-bit output differences β. The corresponding probability can be obtained by multiplying the coefficients of the table by 2-5 . The symbolmeans that the corresponding transition is impossible. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.5 Sieving in the active rows [3 -24] of the plaintext. . . . . . . . . . . . . . . 57 4.6 Guessed master key bits from the subkey k 7 . Each row corresponds to one of the 7 active rows of the ciphertexts. . . . . . . . . . . . . . . . . . . . . . . 59

Figure 1 . 1 :

 11 Figure 1.1: Building a key recovery from a distinguisher

Figure 1 . 2 :

 12 Figure 1.2: Meet-In-The-Middle framework

Figure 1 . 3 :

 13 Figure 1.3: Partial Matching framework

Figure 2 . 1 :

 21 Figure 2.1: Extended differential distinguisher with key recovery rounds

  11: return D expect D to be a singleton of the form (p, κ) where κ ∈ K in ∪ K out is the subkey used for the encryption.

Figure 2 . 2 :

 22 Figure 2.2: Generic presentation of an impossible differential attack, with the notations used in this paper. The differential ∆ in ↔ ∆ out through the middle rounds E imp is impossible.

Figure 2 . 3 :

 23 Figure 2.3: The structure of a differential-linear distinguisher.

  Number of samples T , input difference ∆ in , output difference ∆ m , hamming weight w Ensure: Probabilities (γ u ) u∈B(0,w) 1: Let s = 0 and c e = 0 for u ∈ B(0, w). 2: for i = 1 to T do 3:

Figure 3 . 1 :

 31 Figure 3.1: The four different scenarios

Figure 3 . 2 :

 32 Figure 3.2: The round function of Chaskey.

44Figure 4 . 1 :

 41 Figure 4.1: The round function of SPEEDY-r-192 for the first r -1 rounds (left) and the last round (right).

Figure 4 . 2 :

 42 Figure 4.2: Generating (r + 1.5)-round trails from core r-round trails and extending them to mount (r + 3)-round attacks on SPEEDY.

Figure 4 . 4 :

 44 Figure 4.4: Key recovery part of the 7-round attack against SPEEDY-7-192

Figure 4 . 5 :

 45 Figure 4.5: Transition of rows 26, 28 and 30 through the inverse of the second SB of round 0.

Table 4. 5 :

 5 Sieving in the active rows [3 -24] of the plaintext. Considering the 78 different patterns in the rows [26-31] and [0-2].

Figure 4 . 6 :

 46 Figure 4.6: Parallel key guessing for Rows [18,19,20,21,23].

Figure 5 .

 5 Figure 5.1: A high-level description of the Differential MITM technique.

Figure 5 . 2 :

 52 Figure 5.2: A high-level description of the improved Differential MITM technique.

Figure 5 . 3 :

 53 Figure 5.3: Round function of SKINNY [Bei+16]

Figure 5 . 4 :

 54 Figure 5.4: Tweakey schedule of SKINNY. All tweakey arrays TK1, TK2 and TK3follow the same transformation with the only exception that no LFSR is applied to TK1.[START_REF] Beierle | The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS[END_REF]

Figure 5 . 5 :

 55 Figure 5.5: Truncated differential trail for the attack on 23 rounds.

Figure 5 . 6 :

 56 Figure 5.6: Core attack against 23 rounds of SKIN N Y -128/384. Knowledge of blue key bytes allows to compute values of green ones and thus to propagate differences. No difference in both white and red bytes, but the red ones are required to compute green bytes. Indexes in subkey bytes are the indexes of the corresponding master key bytes. The equivalent subkeys U i are computed as M C(SR(K i )), from the original subkeys K i .

Figure 5 . 7 :

 57 Figure 5.7: Enumeration procedure of k out for the 23-round attack. Differences in blue cells and actual values in red cells are known. No difference in white cells.

5. 2 .Figure 5 . 8 :

 258 Figure 5.8: Last round of the attack against 24 rounds.

Figure 5 . 9 :

 59 Figure 5.9: Truncated differential trail for the attack on 25 rounds.

Figure 5 . 10 :

 510 Figure 5.10: Core attack against 24 rounds of SKINNY-128-384. Knowledge of blue key bytes allows to compute values of green ones and thus to propagate differences. No difference in both white and red bytes, but the red ones are required to compute green bytes. Indexes in subkey bytes are the indexes of the corresponding master key bytes.

L

  top ← Cond top (Char top ) List of the conditions on the top part 10: L bot ← Cond bot (Char bot ) List of the conditions on the bot part 11: L cond ← L top ∪ L bot 12: for c ∈ L cond do 13: k c ← Guess(c) number of key guesses required to check the condition c 14: f c ← Filter(c) number of condition bits of c 15: C ← L cplx [0] previous step complexity 16:

Figure 6 . 1 :

 61 Figure 6.1: The quantum circuit of Lemma 6.2

Figure 6 . 2 :

 62 Figure 6.2: Impossible pattern (from [SMB18]).

5 .

 5 Round 2 and 3. At this step, we have performed enough guesses on the tweakey material to know the value of T K 3 [1]. We guess T K 2 [1, 2, 6] and compute Y 3 and ∆Y 3 . Therefore, from the knowledge ofT K 3 [1], ∆Y 4 [1] can be simply determined. Checking if ∆Y 4 [1] = T K 4 [2], will lead to an s-bit filter.

Figure 6 . 3 :

 63 Figure 6.3: Impossible differential attack on 7-round AES

AnFigure 6 . 4 :SFigure 6 . 5 :

 6465 Figure 6.4: Description of one AES round and the ordering of bytes in an internal state

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.8 Description of Stage 2 of the key recovery. . . . . . . . . . . . . . . . . . . 64 4.9 In red, the master key bits that have already been determined. In black, the bits that still need to be determined. . . . . . . . . . . . . . . . . . . . . . 65 4.10 Description of Stage 3 of the key recovery. . . . . . . . . . . . . . . . . . . 65 5.1 Number of rounds for each of the main variants SKINNY-n-t. . . . . . . . 74 Summary of best quantum attacks on SKINNY-128-256 (with lower complexities than Grover's search). C = Classical; Q = Quantum; * = QRAQM model. Q1, Q2 and QRAQM are defined in Section 1.4. * * means we have extrapolated the complexity on 21 rounds from the original attack on 24 rounds for comparison. Our results clearly provide the best quantum attack and therefore the security margin (the quantum time is counted in block cipher calls). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Successive steps of the attack on SKINNY. Each step reduces the table size but increases the key space. The parameter s corresponds to a byte (8 bits). 6.3 Time and memory complexities of the different steps for 21-round SKINNY-128-256 (in encryptions), whether classical or quantum. . . . . . . . . . . . 6.4 Summary of best quantum attacks on AES-192/256 (with lower complexities than Grover's search). C = Classical; Q = Quantum; * = QRAQM model. Q1, Q2 and QRAQM are defined in Section 1.4. * * means we have extrapolated the complexity on 21 rounds from the original attack on 24 rounds for comparison.

5.2 Subkey bytes involved in

the 23-round core attack. . . . . . . . . . . . . . . 79 5.3 Subkey bytes involved in the 24-round core attack. . . . . . . . . . . . . . . 84 ix 6.1

algorithm consists of the iteration of the operation H ⊗n O 0 H ⊗n O f on the initial state H ⊗n |0 . This iteration can be interpreted as the composition of H ⊗n O 0 H ⊗n and O f . Both of these operations are reflections, H ⊗n O 0 H ⊗n is a reflection arround the average since H ⊗n O 0 H ⊗n = |ψ 0 ψ 0 | -I (with

  and assuming that there is a single solution x 0 , we can find it in O √ N calls to O f instead of O(N ) calls to f classically. In this algorithm, we consider the sets X = {x : f (x) = 0} and Y = {y : f (y) = 1} and we will work in the space spawned by |Good= 1 √ |ψ 0 = H ⊗n |0 ) and O f is a reflection arround |Bad , since O f = |Bad Bad| -I.Since we are composing two reflections, we obtain a rotation as explained in Lemma 1.1. The initial state before the iteration of the rotation is |ψ 0 and has an angle θ with |Bad . Hence after t iteration, the quantum state is:The amplitude amplification generalizes Grover since it allows the search space to be defined by a quantum circuit C. Hence, operations H ⊗n are replaced by C and C † . In practice, if we are given the implementation of an algorithm A that succeeds with probability p, the amplitude amplification algorithm allows us to retrieve a successful element in time O( 1 √ p ) as opposed to O( 1 p ) in the classical setting.

	π 4 arcsin Therefore the probability to obtain a bad element (from X) is cos 2 (2t + 1)θ. On the Theorem 1.1 (Grover's complexity). A measurement of the state after t = |Y | N iterations has an outcome y ∈ Y with probability greater that 1 -|Y | N Proof. |ψ t = sin (2t + 1)θ |Good cos (2t + 1)θ |Bad . Chapter 2 Differential cryptanalysis
	other hand we know that π 4 -θ ≤ tθ < π 4 , hence π 2 -θ ≤ (2t + 1)θ < π 2 + θ and finally cos 2 (2t + 1)θ ≤ cos 2 π 2 -θ ≤ sin 2 θ = |Y | In this chapter, we aim to present the most commonly-used concepts in differential N cryptanalysis. All the following chapters are based on elements introduced in the
	As a consequence, when |Y | <<< N , it is possible to retreive a good element in time N ) with an error probability in O(1/N ). √ following sections. O(
	Contents
	2.1 Differential Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . .	17
	2.1.1 Differential Dinstinguisher . . . . . . . . . . . . . . . . . . .	18
	2.1.2 Differential Attack . . . . . . . . . . . . . . . . . . . . . . .	19
	2.2 Impossible Differential Cryptanalysis . . . . . . . . . . . . . . . . .	24
	2.2.1 Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	24
	|Y | 2.2.2 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . y∈Y |y and |Bad = 1 √ |X| The procedure consists of iterating rotations until we obtain a state that is close to 25 x∈X |x . 2.3 Differential-linear Cryptanalysis . . . . . . . . . . . . . . . . . . . . 28
	|Good to finally measure it. The quantum operations used here are: the oracle O f ,
	the Hadamard gate: H ⊗n : |i → 1 √ N	n-1 j=0 (-1) i,j |j and the inversion arround 0:
	O 0 |x → (-1) x =0 |x .
	As depicted in Algorithm 1.6, Grover's Lemma 1.1. The operation H ⊗n O 0 H ⊗n O f is a rotation of angle 2θ = 2 arcsin |Y | N in
	the plane spawn by |Good and |Bad
	Proof. We can first remark that |ψ 0 can be decomposed on the basis |Good , |Bad as
	follows:
	|ψ 0 = hence the angle θ between |ψ 0 and |Bad satisfy sin θ = |Y | √ N |Good + |X| √ |Bad N √ √ |Y | N . As a consequence, the
	combination of the reflection around |Bad then |ψ 0 results in a rotation of angle 2θ.

out then 4: return Cipher 5: return Random permutation

	In practice, directly computing a differential for a whole cipher often is computation-
	ally expensive. However, a differential can be computed for smaller boolean functions
	that compose the round function of the cipher by exhaustively computing its differential
	table.
	Definition 2.2 (Differential table). Let f : F n 2 → F n 2 be a boolean function, we call
	differential table of f the table T that verifies:

  to experimentally compute the correlation of the middle cipher E m . In this case, if we denote by r the experimental correlation of the middle part, then the differential-linear distinguisher would have a correlation of pr 2 q 2 . This chapter consists of a summary of my joint work with Marek Broll, Frederico Canale, Antonio Flórez-Gutiérrez, Gregor Leander, María Naya-Plasencia, and Yosuke Todo about the optimizations of differential-linear cryptanalysis of ARX constructions and its application to Chaskey[Bei+22]. This paper features different types of optimizations that are independent of one another. In this chapter, we will highlight the part of the paper that concerns the improvements on the differential part, since it matches my contribution in this paper. Application to Chaskey . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.2.1 Chaskey Specfication . . . . . . . . . . . . . . . . . . . . . . 37 3.2.2 Overview of the Attack . . . . . . . . . . . . . . . . . . . . 37 3.2.3 Finding More Neutral Vectors . . . . . . . . . . . . . . . . . 38 3.3 Exploiting the Conditions for Finding Chaskey Relations . . . . . . 39 3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

	Chapter Improving Differential-Linear Cryptanalysis, Application to 3 Chaskey
	.	33
	3.1.3 Computing a Neutral Space . . . . . . . . . . . . . . . . . .	33
	3.1.4 Using the Conditional Differential Framework for Finding
	Better Subspaces . . . . . . . . . . . . . . . . . . . . . . . .	34
	3.2

Contents 3.1 Improving the differential-linear distinguisher . . . . . . . . . . . . . . 31 3.1.1 Differential-Linear Cryptanalysis with Neutral Space . . . . 32 3.1.2 Differential-Linear Cryptanalysis with Probabilistic Neutral Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Table 3 . 1 :

 31 Probability that adding one basis element affects the output difference. The techniques we developed in[Bei+22] allowed to add the elements colored in red to the basis

				Number
	Probability Basis		of
				indices
	γ j = 1	v 2 : 16,17,18,19,20,22,23,24,25,30,31 v 3 : 16,17,18,19,20,22,23	18
	0.93 ≤ γ j < 1	v 0 : 19,20,31 v 1 : 19,20	v 3 : 24,25,30	8

  This chapter is inspired by[Bou+23a] which is a joint work with Christina Boura, Rachelle Heim Boissier, and María Naya-Plasencia. In this paper, we presented a full break on the main version of the block cipher Speedy[START_REF] Leander | The SPEEDY Family of Block Ciphers Engineering an Ultra Low-Latency Cipher from Gate Level for Secure Processor Architectures[END_REF] using differential cryptanalysis combined with evolved techniques. Specifications of the SPEEDY family of block ciphers . . . . . . . . . 43 4.1.1 Round function of SPEEDY-r-192 . . . . . . . . . . . . . . . 44 4.1.2 Security Claims . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.2 Finding Good Differentials on SPEEDY . . . . . . . . . . . . . . . . . 47 4.2.1 Differential properties of SPEEDY . . . . . . . . . . . . . . . 47 4.2.2 Searching for good differential trails . . . . . . . . . . . . . 48 4.2.3 Multiple differentials . . . . . . . . . . . . . . . . . . . . . . 52 4.3 Attack on SPEEDY-7-192 . . . . . . . . . . . . . . . . . . . . . . . . 54 4.3.1 Trade-off between differential probability and efficient sieving 55 4.3.2 Data generation . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.3.3 Sieving of the pairs . . . . . . . . . . . . . . . . . . . . . . . 57 4.3.4 Recovering the key . . . . . . . . . . . . . . . . . . . . . . . 58 4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

	Conditions after + :	carrie						carrie
	X X Better Steady than Speedy: 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 14 13 12 11 9 8 7 6 5 4 3 2 1 0 g g <<<13 xor 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Chapter 4 Full break of SPEEDY-7-192
	Contents 4.1		31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0	g s s g	-4 +			31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
		X	31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 0	g	+ -1	<<<16	x	31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0	s g	+ -2
			31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 0	g	<<<7	xor		31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0	g

Figure 3.3: Conditions on the differential transitions for the 3 first rounds of Chaskey

Table 4 . 1 :

 41 1. Specifications of the SPEEDY family of block ciphers Table representation of the 6-bit S-box S

	x	0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
	S(x) 8 0 9 3 56 16 41 19 12 13 4 7 48 1 32 35
	x 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
	S(x) 26 18 24 50 62 22 44 54 28 29 20 55 52 5 36 39
	x 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
	S(x) 2 6 11 15 51 23 33 21 10 27 14 31 49 17 37 53
	x 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
	S(x) 34 38 42 46 58 30 40 60 43 59 47 63 57 25 45 61

• SubBox (SB): A 6-bit S-box S is applied to each row of the state. More precisely, for each row i, 0 ≤ i < 32, SB operates as follows:

Table 4 .

 4

	4. Better Steady than Speedy:
	Full break of SPEEDY-7-192

2:

The bit-permutation P for SPEEDY-r-192 with β = and γ = 1.

Table 4

 4

	.2.

Table 4 . 6 :

 46 The case of row 28 is only slightly different. If active, there are 2 6 possibilities for the six key bits, but 4 different patterns are possible before SB. A correct pattern is thus reached Guessed master key bits from the subkey k 7 . Each row corresponds to one of the 7 active rows of the ciphertexts.

	row	row
	4 145 8 63 118 173 36 27 55 110 165 28 83 138
	10 13 68 123 178 41 96 28 1 56 111 166 29 84
	18 157 20 75 130 185 48 31 31 86 141 4 59 114
	24 25 80 135 190 53 108

Table 4 . 7 :

 47 box, but only 8, namely the rows[17,18,...,24]. Further, we show that to get a filter, one does not need to guess all This table represents the information used for efficiently solving the keyrecovery part of the attack. Each line in the table is associated with the same row in the state. The column Key determined indicates how many bits are already known from Stage 1 (those bits are depicted in red)

	row	Key	Key Differential Fixed	First
		determined left	Filter	bits S-box Cost
	0 0 1 2 3 4 5	2	4	*	*	*
	1 6 7 8 9 10 11	1	5	*	*	*
	2 12 13 14 15 16 17	1	5	*	*	*
	3 18 19 20 21 22 23	1	5	0.42	4	1.42
	4 24 25 26 27 28 29	3	3	0.48	4	-0.52
	5 30 31 32 33 34 35	1	5	0.07	3	2.07
	6 36 37 38 39 40 41	2	4	0.07	3	1.07
	7 42 43 44 45 46 47	0	6	0.07	3	3.07
	8 48 49 50 51 52 53	2	4	0	2	2
	9 54 55 56 57 58 59	3	3	0.02	2	1.02
	10 60 61 62 63 64 65	1	5	0.05	3	2.05
	11 66 67 68 69 70 71	1	5	0.07	3	2.07
	12 72 73 74 75 76 77	1	5	0.12	3	2.12
	13 78 79 80 81 82 83	2	4	0.02	2	2.02
	14 84 85 86 87 88 89	2	4	0.07	3	1.07
	15 90 91 92 93 94 95	0	6	0.09	3	3.09
	16 96 97 98 99 100 101	1	5	0.07	3	2.07
	17 102 103 104 105 106 107	0	6	0.09	3	3.09
	18 108 109 110 111 112 113	3	3	0	2	1
	19 114 115 116 117 118 119	2	4	0.02	2	2.02
	20 120 121 122 123 124 125	1	5	0	2	3
	21 126 127 128 129 130 131	1	5	0.07	3	2.07
	22 132 133 134 135 136 137	1	5	0.17	3	2.17
	23 138 139 140 141 142 143	2	4	0.51	4	0.51
	24 144 145 146 147 148 149	1	5	1.42	5	1.42
	25 150 151 152 153 154 155	0	6	*	*	*
	26 156 157 158 159 160 161	1	5	*	*	*
	27 162 163 164 165 166 167	2	4	*	*	*
	28 168 169 170 171 172 173	1	5	*	*	*
	29 174 175 176 177 178 179	1	5	*	*	*
	30 180 181 182 183 184 185	1	5	*	*	*
	31 186 187 188 189 190 191	1	5	*	*	*

Table 4 .

 4

	Chapter 4. Better Steady than Speedy:
	Full break of SPEEDY-7-192

8: Description of Stage 2 of the key recovery.

Table 4

 4 are left to determine. This is done by guessing them. The complexity associated with this step is

	row	Key row	Key
		left		left
	0 169 32 87 142 5 60 2	16 73 128 183 46 101 156
	1 115 170 33 88 143 6	2	17 19 74 129 184 47 102
	2 61 116 171 34 89 144 1	18 157 20 75 130 185 48
	3 7 62 117 172 35 90 2	19 103 158 21 76 131 186
	4 145 8 63 118 173 36 0	20 49 104 159 22 77 132
	5 91 146 9 64 119 174 2	21 187 50 105 160 23 78
	6 37 92 147 10 65 120 1	22 133 188 51 106 161 24
	7 175 38 93 148 11 66 2	23 79 134 189 52 107 162
	8 121 176 39 94 149 12 2	24 25 80 135 190 53 108
	9 67 122 177 40 95 150 2	25 163 26 81 136 191 54
	10 13 68 123 178 41 96 0	26 109 164 27 82 137 0
	11 151 14 69 124 179 42 3	27 55 110 165 28 83 138
	12 97 152 15 70 125 180 3	28 1 56 111 166 29 84
	13 43 98 153 16 71 126 2	29 139 2 57 112 167 30
	14 181 44 99 154 17 72 3	30 85 140 3 58 113 168
	15 127 182 45 100 155 18 2	31 31 86 141 4 59 114

.9: In red, the master key bits that have already been determined. In black, the bits that still need to be determined.

Complexity summary. The final time complexity of our attack is

T = 2 187.28 C E + 2 179.42 C E + 2 186.15 C E + 2 180.31 C E = 2 187.84 C E

Table 4 .

 4

	Row Involved rows # missing Row Involved rows # missing
		of k 7	bits	of k 7	bits
	0 27,28,29,30,31,0	8	19 14,15,16,17,18,19	10
	5	0,1,2,3,4,5	9	31 23,24,25,26,27,28	8
	11 6,7,8,9,10,11	10

10: Description of Stage 3 of the key recovery.

Table 5 . 1 :

 51 Number of rounds for each of the main variants SKINNY-n-t.

	Block size n t = n t = 2n t = 3n
	64	32	36	40
	128	40	48	56

  ← Max Int 3: for (r in , r out ) such that r in + r out + r m = R do Char bot ← propag bot (∆ out , r out )Bot propagation

	Algorithm 5.2 Optimise Differential Attack with Sequential Key recovery
	1: (r * in , r * out ) ← (0, 0) 2: c 4: L cplx ← Empty List	Complexity list initialisation
	5:	Char top ← propag top (∆ in , r in )	Top propagation
	6:
	7:

*

  , which is a joint work with María Naya-Plasencia and André Schrottenloher. In this paper, we presented a quantum version of the impossible differential cryptanalysis and its application to AES and SKINNY. This work answers an open problem proposed in [BNS19] that wonders about the efficiency of the quantized version of impossible differential attacks. Quantum Collision Search and Pair Generation . . . . . . . . . . . 87 6.2 Quantum Key Recovery . . . . . . . . . . . . . . . . . . . . . . . . . 89 6.2.1 Assumptions on the Attack . . . . . . . . . . . . . . . . . . 90 6.2.2 Filtering of a Table . . . . . . . . . . . . . . . . . . . . . . . Application to 7-round AES . . . . . . . . . . . . . . . . . . . . . . 102 6.4.1 Description of AES-256 . . . . . . . . . . . . . . . . . . . . 104 6.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

	Contents
	6.1 92
	6.2.3 Exact Early Abort . . . . . . . . . . . . . . . . . . . . . . .	94
	6.2.4 Improved early abort in Practice . . . . . . . . . . . . . . .	96
	6.3 Application to SKINNY . . . . . . . . . . . . . . . . . . . . . . . . . .	97
	6.3.1 Classical Impossible Attack . . . . . . . . . . . . . . . . . .	98
	6.3.2 Quantum impossible attack . . . . . . . . . . . . . . . . . . 102
	6.4

  and that there exists separate test functions T 1 (p, k 1 ), T 2 (p, k 1 , k 2 ), . . . , T (p, k 1 , . . . , k ) that decide whether a pair p invalidates the key guess k 1 , . . . , k . Our goal is to solve the following problem. Given the table T 0 that contains the precomputed pairs, find the keys (k 1 , . . . , k ) such that T (k 1 , . . . , k ) = ∅ In this Section 2.1.2, we introduced the early abort algorithm (Algorithm 2.4), the following algorithm is a version of early abort for impossible differential. Early Abort algorithm for impossible differential attacks.Input: a table T 0 for the pairs Output: finds the only key k for which there is no invalidating pair

	Problem 6.2. Algorithm 6.1

1: for all k 1 ∈ K 1 do 2:

  table, we use amplitude amplification to check whether this set of key guesses leads to the single solution or not. We use k g 1 , . . . , k g to denote this solution.

	2	j=i	M j-1 (t j + t)	2 π	j-i	j

Lemma 6.3. Let 1 ≤ i ≤ . Let t i be the time (in quantum operations) to compute the condition T i . There exists a quantum circuit (unitary) U i that, on an input state of the form:

|k 1 , . . . , k i |T i-1 (k 1 , . . . , k i-1 ) ,

writes 1 in an output qubit iff there exists a completion k i+1 , . . . , k such that k 1 , . . . , k is the good key and 0 otherwise. Assuming QRAQM, it runs in time: m=i |K m | , using a memory of size M i-1 . Proof. We start by describing U , the innermost step. It starts from the table T -1 (k 1 , . . . , k -1 ), and k 1 , . . . , k . It simply needs to compute T for all the elements of the table and check if one of them passes the test (if it's the case, then this is not the good key guess). This is done in time 2M -1 (t + t) (including an uncomputation).

Table 6 . 1 :

 61 Summary of best quantum attacks on SKINNY-128-256 (with lower complexities than Grover's search). C = Classical; Q = Quantum; * = QRAQM model. Q1, Q2 and QRAQM are defined in Section 1.4. * * means we have extrapolated the complexity on 21 rounds from the original attack on 24 rounds for comparison. Our results clearly provide the best quantum attack and therefore the security margin (the quantum time is counted in block cipher calls). 103.2 (2 95.2 ) * 2 119.2 Q2 21 Section 6.3 2 128 2 117.5 2 103.2 2 106.3 2 128 Q1

	AlgorithmRds.	Ref.	Time	Memory	Data Setting
		C	Q	C	Q
	21 Grover	2 129.65		negl. negl. Q1
	21 [SMB18]** 2 151.2	2 103.2		2 128	C
	SKINNY-20 [SMB18]** 2 126.5	2 54.6		2 126.5 C
	128-256 21 Section 6.3	2 119.2 2

Table 6 . 2 :

 62 Successive steps of the attack on SKINNY. Each step reduces the table size but increases the key space. The parameter s corresponds to a byte (8 bits). For this step we guess the value of ET K[8]. From the knowledge of the plaintext, we can compute ∆Y 2 [8] and ∆Y 2 [15]. Based on the properties of MC operation on col(3) of W 2 , we have ∆Y 2 [8] = ∆Y 2 [15]. We thus perform a single-cell (s-bit) filter on the pairs. c) For this step we guess the value of ET K[1]. From the knowledge of the plaintext, we can compute ∆Y 2 [5] and ∆Y 2 [8]. Based on the properties of MC operation on col(3) of W 2 , we have ∆Y 2 [5] = ∆Y 2 [8]. We thus perform a single-cell (s-bit) filter on the pairs. d) To continue the key recovery, we will perform two additional key guesses ET K[2, 9, 11] so that the value of Y 2 [2, 9, 11] is known.

			Quantum	Classical
	Index σ i |K i |	partial complexity:	partial complexity:
			i-1 j=1 σ j	i j=1 |K j |	i-1 j=1 σ j	i j=1 |K j |
	1.a 2 -s 2 0	2 0		2 0
	1.b 2 -s 2 s	2 -s/2	2 0
	1.c 2 -s 2 s	2 -s		2 0
	1.d 2 -s 2 s	2 -3s/2	2 0
	1.e 2 -s 2 s	2 -2s	2 0
	1.f 2 -s 2 s	2 -5s/2	2 0
		2 0 2 2s	2 -5s/2	2 s
	2 2 -2s 2 s	2 -2s	2 2s
	3	2 -s 2 s	2 -7s/2	2 s
	4.a 2 -s 2 s	2 -4s	2 s
	4.b 2 -s 2 s	2 -9s/2	2 s
	4.c 2 -s 2 s	2 -5s	2 s
	4.d 2 0 2 3s	2 -9s/2	2 3s
	5	2 -s 2 3s	2 -3s	2 6s
	b)

Table 6 . 3 :

 63 Time and memory complexities of the different steps for 21-round SKINNY-128-256 (in encryptions), whether classical or quantum. Quantum early abort (QRAQM) 2 104.32 2 95.17 (QRAQM) + 2 103.17 (classical)Quantum early abort (no QRAQM) 2 117.46 2 106.31 (qubits) + 2 103.17 (classical)

	Complexity	Time	Mem.
	Classical Pair Generation	2 128	negl.
	Quantum Pair Generation	2 119.17	2 24 (QRAQM)
	Classical early abort	2 151.17	2 103.17
	Quantum Generic	2 129.65	negl.
	Classical Generic	2 256	negl.

Table 6 . 4 :

 64 Summary of best quantum attacks on AES-192/256 (with lower complexities than Grover's search). C = Classical; Q = Quantum; * = QRAQM model. Q1, Q2 and QRAQM are defined in Section 1.4. * * means we have extrapolated the complexity on 21 rounds from the original attack on 24 rounds for comparison. We obtain a better memory than[START_REF] Derbez | Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting[END_REF], and a time complexity comparable to[START_REF] Bonnetain | Quantum Security Analysis of AES[END_REF] (the quantum time is counted in S-Box evaluations). Square 2 121 2 38 (2 27 ) * 2 37 Q1 AES-192 7 [BNS19]-Square 2 103.4 2 38 (2 27 ) * 2 37 Q1 AES-256 7 [BNS19]-Square 2 107 2 38 (2 27 ) * 2

	Algorithm Rds.	Ref.	Time	Memory DataSetting
			C	Q C	Q
	AES-192 7 [BNS19]-Grover		2 105.6		negl. negl. Q1
	AES-256 7 [BNS19]-Grover		2 137.3		negl. negl. Q1
	AES-256 7 [BNS19]-37 Q1
	AES-256 7	[DFJ13]	2 99.6		2 96	2 99	C
	AES-192/256 7	Section 6.4		2 101.5		(2 78.5 ) * 2 99.8 Q2
	AES-192/256 7	Section 6.4		2 99.9		(2 78.5 ) * 2 99.8 Q2
	AES-256 8 [BNS19]-Grover		2 138		negl. negl. Q1
	AES-256 8	[BNS19]-DS-MITM		2 136 2 88 negl. 2 88 Q1

Table 6 . 5 :

 65 Successive steps of the attack on AES (if we used the standard early abort). The parameter s corresponds to a byte (8 bits). [0] = w 1 [0]: this is a single-byte condition on k 1 [0, 10], and all the previous plaintext bytes. For a given pair, there are on average 2 8 matching guesses of k 1 [0, 10].4.b w 1 [10] = w 1 [10]: this is another single-byte condition with independent key bytes k 1 [2, 8], but the same plaintext bytes as before.

			Quantum	Classical
	Index σ i |K i |	partial complexity:	partial complexity:
			i-1 j=1 σ j	i j=1 |K j |	i-1 j=1 σ j	i j=1 |K j |
	1.	2 0 2 4s	2 2s		2 4s
	2. 2 -2s 2 4s	2 2s		2 6s
	3. 2 -2s 2 4s	2 2s		2 8s
	4. 2 -3s 2 4s	2 s		2 9s
	4.a w 1

Remerciements

Chapter 4. Better Steady than Speedy:

Full break of This fact, together with the probability of 2 -3.41 for the transition 0x4 → 0x10 for the other three active rows, gives a total probability of 2 -13.64 . To summarize, as can be seen from Figure 4.3, our 5.5-round trail has then a total probability of 2 -169.95 × 2 -13.64 = 2 -183.59 .

Attack on SPEEDY-7-192

SPEEDY-7-192 is the variant of the SPEEDY family suggested for applications where a security of 192 bits is needed. We show in this section, by using the techniques and ideas introduced earlier, how to recover the secret key of this version with less than 2 192 encryptions. In addition, we will propose two ideas that will allow us to optimize the • The data is presented in two lists:

where (a i ) (resp. (b i )) form a partition of the bits of a (resp. b).

Since this first guess fulfill the requirements, we obtain a reduction of the guessing cost from 2 2.02+2.07+1+0.51+2.17 = 2 7.77 to 2 4.09 + 2 3.68 + 2 7.77-8 = 2 4.94 , or else can be more efficiently performed with small precomputations regarding these partial transitions with a cost for each step given by the number of remaining solutions, so 2 7.77-8 = 2 -0.23 in this example.

Row 24. The next step consists in guessing row 24. As we have described previously, for the pairs that have not been discarded yet, the three rows [17,18,19] before the second S-box are fixed. Two bits of row 24 later impact the value of these rows. Thus, we obtain an extra 2 -2 filter. Therefore, as can be seen from Table 4.7 we obtain a partial guessing cost of 2 1.42 and a partial data cost of 2 -0.58 .

The next steps of the key recovery are described in

Comparison of the attacks on SKINNY-128-384 with differential attacks

One may wonder whether the improved attacks on SKINNY-128-384 and in particular the one reaching 25 rounds, are exclusively due to the quality and the length of the differential distinguisher used, thus, that a differential attack could reach the same number of rounds if mounted on this distinguisher. In this section we show that this is not the case, and that the best classical differential attacks reached strictly fewer rounds than our attack. We show that even when considering optimal lower bounds for the complexities of classical differential attacks, it is not possible to reach more than 22 rounds using the early abort technique and 24 rounds using a parallel key recovery for SKINNY-128-384 this way. This shows that differential MITM attacks can reach more rounds than differential ones in certain scenarios. As explained in Section 2.1.2, the time complexity of a differential attack is:

To mount a differential attack on SKINNY-128-384, there are two ways to perform the key recovery, hence to compute C KR .

Sequential key recovery. This paragraph is not included in the publication [Bou+23b] and describes the tool I implemented to compute sequential key recovery for SKINNY-128-384. This case corresponds to performing an early abort as described in Section 2.1.2.3. To obtain the best complexity possible, I implemented a tool that given Following [START_REF] Bonnetain | Finding many Collisions via Reusable Quantum Walks[END_REF], we have three choices for input structures, depending on the number of required pairs N :

then we need only one structure. To recover all the pairs, we need a time exponent :

• If 2 2d in 2 n-d out < 1, then we fall back on the approach of [START_REF] Kaplan | Quantum Differential and Linear Cryptanalysis[END_REF], which is to repeat N times a Grover search among structures, to find one that contains a pair. Checking if a structure of size 2 d in contains a pair is an element distinctness problem, which is solved with Ambainis' algorithm in time O 2 2d in /3 . The time exponent for this case is log

• If 1 < 2 2d in 2 n-d out < N , we need to consider several structures and extract all of their collision pairs. This gives a time exponent:

By considering E -1 instead of E, we can also swap the roles of d in and d out .

Conjecture. If we conjecture that the complexity O(2 2k 3 + m

3 ) for the multiple collision search problem can actually be reached for the whole parameter range of Theorem 6.1 (and therefore, that the query lower bound is tight everywhere), all the six cases above can be merged into a single formula reminiscent from the classical one. Conjecture 6.1. Let E : {0, 1} n → {0, 1} n be a block cipher. Given quantum oracles for E and its inverse (O E and O E -1 ), the limited birthday problem can be solved in quantum time

Quantum Key Recovery

In this section, we describe a quantum version of the early-abort algorithm in the case of impossible differential cryptanalysis (Algorithm 2.4) and we study its time complexity.