Littérature scientifique sur le sujet « Primitive symétrique »

International audience A factorization of a permutation into transpositions is called "primitive'' if its factors are weakly ordered.We discuss the problem of enumerating primitive factorizations of permutations, and its place in the hierarchy of previously studied factorization problems. Several formulas enumerating minimal primitive and possibly non-minimal primitive factorizations are presented, and interesting connections with Jucys-Murphy elements, symmetric group characters, and matrix models are described. Une factorisation en transpositions d'une permutation est dite "primitive'' si ses facteurs sont ordonnés. Nous discutons du problème de l'énumération des factorisations primitives de permutations, et de sa place dans la hiérarchie des problèmes de factorisation précédemment étudiés. Nous présentons plusieurs formules énumérant certaines classes de factorisations primitives,et nous soulignons des connexions intéressantes avec les éléments Jucys-Murphy, les caractères des groupes symétriques, et les modèles de matrices.

Cette thèse a pour objet d'étude les algorithmes de chiffrement par blocet les fonctions de hachage cryptograpiques, qui sont deux primitives essentielles de la cryptographie dite «symétrique».Dans une première partie, nous étudions des éléments utiles pour la conception de chiffres par bloc: tout d'abord des matrices de diffusion de grande dimension issues de codes correcteurs géométriques, puis une boîte de substitution offrant une bonne diffusion. Dans le second cas, nous montrons aussi comment utiliser cet élément pour construire un chiffre compact et efficace sur petits processeurs.Dans une seconde partie, nous nous intéressons à des attaques en collision à initialisation libre sur la fonction de hachage SHA-1. Nous montrons comment les attaques classiques sur cette fonction peuvent être rendues plus efficaces en exploitant la liberté supplémentaire offerte par ce modèle. Ceci nous permet en particulier de calculer explicitement des collisions pour la fonction de compression de SHA-1 non réduite
This thesis is about block ciphers and cryptographic hash functions, which are two essential primitives of symmetric-key cryptography. In the first part of this manuscript, we study useful building blocks for block cipher design. We first consider large diffusion matrices builtfrom algebraic-geometry codes, and then construct a small S-box with good diffusion. In the second case, we show how the S-box can be used to define a compact and efficient block cipher targetting small processors. In the second part, we focus on the SHA-1 hash function, for which we develop a free start collision attack. We show how classical collision attacks can be made more efficient by exploiting the additional freedom provided by the model. This allows us in particular to compute explicit collisions for the full compression function of SHA-1

La plupart des fonctions de hachage sont construites comme l'itération d'une fonction de compression, absorbant à chaque tour un bloc issu du message et le résultat de l'itération précédente. Le mode d'opération définit le nombre d'itérations et les paramètres en entrée de la fonction de compression pour chacune d'entre elles. Merkle-Damgård est un mode d'opération simple et répandu qui ne garantit cependant pas la sécurité en seconde préimage, même pour une fonction de compression idéale. D'une part nous fournissons une réduction générique de sécurité en seconde préimage dans le modèle standard, d'autre part nous prouvons que la perte de sécurité des réductions des modes étudiés est inévitable pour une réduction de sécurité en seconde préimage de modes narrow-pipe. A partir des attaques qui se basent essentiellement sur des propriétés du cadencement de clé, nous analysons la sécurité d'une famille de cadencements de clé affines à base de rotations, de xor, et de choix permutés de bits. Nous obtenons ainsi des critères de conception indiquant un niveau de sécurité relativement à une classe d'attaques en fonction des coefficients d'un cadencement de clé appartenant à cette famille. Les attaques par le milieu exploitent la possibilité de séparer une partie des bits de clé en trois parties, dont deux d'entre elles interviennent exclusivement dans la première ou la seconde moitié des itérations de chiffrement. L'équilibrage entre les nombres de tours dans les moitiés de chiffrement, et entre les nombres de bits de chacune des deux portions de clé indépendantes, permettent de minimiser la complexité de l'attaque. Nous montrons comment utiliser des propriétés statistiques des boîtes S au milieu pour étendre le nombre de tours pour lequel cette complexité reste en dessous de celle d'une recherche exhaustive de clé. Nous appliquons cette technique à des versions réduites de deux chiffrements par blocs : DES et PRESENT
Most hash functions iterate one function compression, that process one block at each round with the result of the previous iteration. The mode of operation of a hash function defines the number and the parameters of the iterations. Merkle-Damgård was the first classical mode, built with a proof of collision resistance transmitted from the compression function to the hash function. First we give a generic security reduction in the standard model for narrow-pipe modes of operation. Then we prove that for any such reduction a security loss is unavoidable, which is closely related to the message length which is considered by the reduction. Block cipher often iterate a round function several times with different parameters which are derived from the master key by a key scheduling algorithm. We analyse a set of key schedules based on xor, rotation and bit permutation, in order to derive a criterion of resistance against known cryptanalysis with a kind of genericity with respect to the round function : slide attacks and relatedkey slide attacks. Meet-in-the-Middle attack exploit the ability for the attacker to divide the key bits in three parts without intersection, where two of them permit to computed a part of a same intermediate state with the help of the third part of the key bits. We extend this cryptanalysis with the use of a probabilistic sieve in the middle, such that the attacker does not search anymore for a match at a same intermediate state but for the existence of a transition through the non-linear layer of an intermediate round. It permits to extend of one round various cryptanalysis of block ciphers. Examples are given for reduced versions of DES and PRESENT

Ce travail est fondé sur la théorie des bigèbres bidendriformes, développée par Foissy, qui sont des algèbres de Hopf particulières où le produit et le coproduit peuvent être scindés en deux. Son théorème principal est: Une bigèbre bidendriforme est générée librement par ``l'espace des éléments totalement primitifs'' en tant qu'algèbre dendriforme. Une conséquence est l'auto-dualité des bigèbres bidendriformes.Parmi les nombreuses algèbres de Hopf, Hivert a défini l'algèbre des fonctions quasi-symétriques en mots, notée WQSym. En prouvant que WQSym est une bigèbre bidendriforme, Novelli-Thibon résolvent la conjecture de Duchamp-Hivert-Thibon sur l'auto-dualité de WQSym. Cependant, comme aucune construction générale de l'ensemble des totalement primitifs n'est formulée, nous n'avons pas d'auto-morphisme explicite pour le passage de la primale à la duale.La question centrale de cette thèse est donc de construire un isomorphisme bidendriforme entre WQSym et sa duale. Cette construction passe par la décomposition des mots tassés à l'aide de deux nouvelles opérations que nous avons définies. En outre, pour illustrer ces décompositions, nous avons créé une nouvelle famille d'objets combinatoires: les forêts d'arbres biplans. Certains sous-ensembles de mots tassés ne peuvent être décomposés par ces opérations. Nous avons prouvé que leurs séries génératrices sont égales aux dimensions de l'espace des éléments totalement primitifs. L'intérêt des forêts biplanes est de faire apparaître visuellement les sous-ensembles de mots tassés indécomposables.Ces forêts biplanes sont donc la forme idéale pour indexer des nouvelles bases, que nous avons créées, de l'algèbre WQSym et sa duale. En effet, il est aisé d'en extraire un sous-ensemble qui définit deux bases des espaces totalement primitifs de WQSym et sa duale. Enfin, des arbres biplans bicolores permettent d'obtenir un isomorphisme bidendriforme par un simple échange de couleurs, ce qui répond à notre question initiale et constitue le résultat principal de cette thèse.Après l'obtention de ce résultat, nous nous intéressons aux relations entre les opérations évoquées. Nous remarquons alors fortuitement que ces opérations vérifient des relations semblables à des opérades bien connues (dupliciale déformée, L-algèbre, bigraft) mais qui sont a priori sans lien avec l'opérade dendriforme. Nous prouvons que l'ensemble des mots tassés munis de ces opérations décrit une algèbre sur ces opérades et en donnons des sous-ensembles de générateurs.L'algèbre PQSym, indexée par les fonctions de parking, est très similaire à WQSym, mais aussi plus complexe et serait un premier pas vers la généralisation de notre résultat principal. La question de généraliser ce résultat aux fonctions de parking relève à la fois de la combinatoire et de l'algèbre. Nous présentons ce qui est sans doute le premier ingrédient de cette généralisation. Il s'agit du calcul d'un changement de base où le produit de mélange des valeurs est sans chevauchement.Nous terminons cette thèse par une partie expliquant notre démarche expérimentale de recherche utilisant SageMath. Nous décrivons les tutoriels que nous avons conçus sous la forme de notebooks et mis en ligne à disposition des autres chercheurs. Nous y présentons le code qui permet de vérifier tous nos résultats sur des exemples calculés par des algorithmes
This work is founded on the theory of bidendriform bialgebras, developped by Foissy, which are particular Hopf algebras where the product and the coproduct can be split into two parts. His main theorem is: A bidendriform bialgebra is freely generated by ``the space of totally primitive elements'' as a dendriform algebra. A consequence of this is the self-duality of bidendriform bialgebras.Among the many Hopf algebras, Hivert defined the algebra of word quasi-symmetric functions, denoted WQSym. By proving that WQSym is a bidendriform bialgebra, Novelli-Thibon solved the Duchamp-Hivert-Thibon conjecture on the self-duality of WQSym. However, since no general construction of the set of totally primitive was formulated, we do not have an explicit isomorphism between the primal and the dual.The central question of this thesis is the construction of a bidendriform isomorphism between WQSym and its dual. This construction goes through a decomposition of packed words using two new operations that we havedefined. Furthermore, to illustrate these decompositions, we have created a new family of combinatorial objects: forests of biplane trees. Some subsets of packed words cannot be decomposed by these operations. We proved that their generating series are equal to the dimensions of the space of the totally primitive elements. The interest of biplane forests is to visually reveal the subsets of indecomposable packed words.These biplane forests are therefore the ideal form for indexing the new bases, that we have created, of the algebra WQSym and its dual. In fact, it is easy to extract from them a subset which defines two bases of totally primitives spaces of WQSym and its dual. Finally, bicolored biplane trees allow us to obtain a bidendriform isomorphism by a simple exchange of colors, which answers our initial question and constitutes the main result of this thesis.After obtaining this result, we study the relationships between the aforementioned operations. We then remark fortuitously that these operations verify relations similar to well-known operads (skew-duplicial, L-algebra,bigraft) but which are unrelated to the dendriform operad. We prove that the set of packed words endowed with these operations describes an algebra over these operads and give subsets of generators.The PQSym algebra, indexed by parking functions, is very similar to WQSym, but also more complex and would be a first step towards a generalization of our main result. The question of generalizing this result to parking functions is both combinatorics and algebra. We present what is undoubtedly the first ingredient of this generalization. This is the calculation of a change of bases where the shuffle product on values is not overlapped.We end this thesis with a part explaining our experimental approach of research using SageMath. We describe the tutorials that we have designed in the form of notebooks and made available online for other researchers. We present the code that allows to check all our results on examples calculated by algorithms

Cette thèse contribue à l’effort de cryptanalyse de primitives symétriques comme les chiffrements par bloc ou les générateurs pseudo-aléatoires. Elle étudie en particulier une famille de distingueurs fondés sur la propagation de sous-espaces vectoriels différentiels dans les chiffrements par bloc de construction SPN. Cette thèse propose également des méthodes permettant aux cryptographes de modéliser un problème de cryptanalyse de primitive symétrique en problème MILP (Mixed-Integer Linear Programming), afin d’exploiter certains logiciels solutionneurs de problèmes MILP très performants. Enfin, elle présente des techniques d’analyse algébrique des primitives symétriques, fondées sur le calcul d’une partie de leur forme algébrique normale, et utiles dans les attaques de type cube
This thesis contributes to the cryptanalysis effort needed to trust symmetric-key primitives like block-ciphers or pseudorandom generators. In particular, it studies a family of distinguishers based on subspace trails against SPN ciphers. This thesis also provides methods for modeling frequent cryptanalysis problems into MILP (Mixed-Integer Linear Programming) problems to allow cryptographers to benefit from the existence of very efficient MILP solvers. Finally, it presents techniques to analyze algebraic properties of symmetric-key primitives which could be useful to mount cube attacks

Nous nous intéressons à la cryptanalyse de certaines primitives de cryptographie symétrique qu utilisent les concepts de construction du schéma de chiffrement AES. Nous commençons par un< analyse de l'AES lui-même dans trois modèles de sécurité différents: le modèle standard, le modèle à clefs reliées et le modèle ouvert. Dans le modèle standard, où l'adversaire cherche à récupérer la clef secrète, nous décrivons les meilleures attaques différentielles existantes sur ce algorithme de chiffrement, en améliorant les attaques différentielles précédemment publiées. Ensuite, nous procédons à une analyse structurelle de l'AES dans le modèle à clefs reliées et montrons des résultats d'impossibilité. Enfin, dans le modèle ouvert, nous proposons le premier distingueur pour neuf tours d'AES-128, ce qui résout un problème ouvert de la communauté symétrique. Dans une deuxième partie, nous analysons l'application de l'attaque par rebond sur les primitives basées sur l'AES. Nous montrons qu'il est possible de considérer un tour de plus dans la première des deux phases de cette stratégie. Ceci résout le problème ouvert consistant à augmenter le nombre total de tours attaqués grâce à cette technique. Nous montrons également qu'il est possible de relâcher certaines contraintes pour augmenter la probabilité de succès de la deuxième étape. Nous appliquons ces améliorations à la fonction de hachage Grostl, obtenant les meilleures attaques sur la permutation interne. Finalement, nous nous intéressons à la fonction de hachage ECHO et montrons qu'il est possible d'appliquer plusieurs fois l'attaque par rebond
In this thesis, we are interested in the cryptanalysis of some symmetric primitives using the structural concepts of the current encryption standard AES. We begin by an analysis of the AES itself in three different security models: the standard model, the related-key model and the open-key model. In the standard model, where the adversary tries to recover the secret key, we describe the best differential attacks, improving on the results previously published on this block cipher. Then, we conduct a structural analysis of the AES in the related-key model and show impossibility results on the structure of the AES. Finally, in the open-key model» we propose the first distinguisher for 9-round AES-128, which solves a long-lasting open problem in the symmetric community. In a second part, we scrutinize the application of the rebound technique to AES-based permutations. We show that it is possible to control one more round in the first of the two parts of this strategy. This result solves the open problem consisting in increasing the total number of rounds that can be attacked thanks to this technique. We also discuss the possibility to relax some constraints in the second phase to increase its probability of success. This reduces all the time complexities of the results previously published using the rebound technique. We apply these improvements to the Grostl hash function and reach the best cryptanalysis to date on the internal permutation. Finally, we study the ECHO hash function and show how we can apply the rebound technique multiple times to attack more rounds of the internal permutation

Nous traitons dans cette thèse de la sécurité de fonctions cryptographiques symétriques. Dans une première partie, nous abordons les algorithmes de chiffrement par flot du point de vue du cryptanalyste. Nous présentons les principales techniques de cryptanalyse et plus particulièrement les attaques algébriques. Nous exposons également une cryptanalyse différentielle de la famille d'algorithmes VEST, candidate au projet eSTREAM. Dans une deuxième partie, nous étudions la construction de fonctions de hachage cryptographiques. Nous présentons deux preuves de sécurité en indifférentiabilité de l'oracle aléatoire de la construction définie dans le cadre de la soumission de Shabal à la compétition SHA-3. La première preuve considère la primitive interne comme idéale. La deuxième permet de prendre en compte des imperfections de la primitive sous-jacente et repose sur un nouveau modèle présentant un intérêt indépendant de l'analyse de Shabal
In this thesis, we study the security of symmetric cryptographic functions. In a first part, we study stream ciphers from a cryptanalysis point of view. We present the main attack principles and focus on algebraic cryptanalysis. We also present a practical time differential cryptanalysis of the VEST stream ciphers family, one of the candidate of the eSTREAM project. In a second part, we study the conception of cryptographic hash functions. We present two security proofs of indifferentiability from a random oracle of the domain extension of Shabal, a candidate to the SHA-3 competition. The first proof assumes that the internal primitive Shabal relies on behaves ideally. The second proof enables to take into account non ideal behaviour of the primitive. New techniques of independant interest are developed to achieve this goal

Dans cette thèse, on propose des améliorations qui peuvent être appliquées à plusieurs techniques de cryptanalyse de primitives symétriques. On dédie une attention spéciale à la cryptanalyse linéaire, pour laquelle une technique basée sur la transformée de Walsh rapide était déjà connue (Collard et al., ICISC 2007). On introduit une version généralisée de cette attaque, qui permet de l'appliquer pour la récupération de clé considerant plusieurs tours, ainsi que le réduction de la complexité du problème en utilisant par example des informations provénantes du key-schedule. On propose aussi une technique générale pour accélérer les attaques par récupération de clé qui est basée sur la représentation des boîtes S en tant que arbres binaires. Finalement, on montre comment on a obtenu une approximation linéaire sur la version complète de la permutation Gimli en utilisant l'optimisation par mixed-integer linear programming (MILP)
This thesis proposes improvements which can be applied to several techniques for the cryptanalysis of symmetric primitives. Special attention is given to linear cryptanalysis, for which a technique based on the fast Walsh transform was already known (Collard et al., ICISIC 2007). We introduce a generalised version of this attack, which allows us to apply it on key recovery attacks over multiple rounds, as well as to reduce the complexity of the problem using information extracted, for example, from the key schedule. We also propose a general technique for speeding key recovery attacks up which is based on the representation of Sboxes as binary decision trees. Finally, we showcase the construction of a linear approximation of the full version of the Gimli permutation using mixed-integer linear programming (MILP) optimisation

Ces dernières années, de nouvelles primitives de cryptographie symétrique ont été proposées pour être utilisées dans des protocoles avancés comme le calcul multi-partite, en combinaison avec un chiffrement homomorphe ou encore dans divers systèmes de preuve à apport nul de connaissance. De tels protocoles s’inscrivent dans un contexte marqué par le développement du Cloud et des technologies de type Blockchain et doivent ainsi répondre à une préoccupation croissante des utilisateurs en matière de sécurité. Ces protocoles ont mis en avant le besoin de minimiser le nombre de multiplications effectuées par la primitive dans des corps finis de grande taille. Les algorithmes symétriques classiques sont alors inappropriés dans ce contexte et les nouveaux protocoles cryptographiques doivent être combinés avec des primitives symétriques (chiffrement ou fonction de hachage) ayant des propriétés particulières. Alors que le nombre de conceptions définies sur de grands corps dites "orientées arithmétisation" augmente de façon considérable, très peu de travaux d’analyse de sécurité ont été proposés jusqu'ici. L’objectif de ce manuscrit est donc en premier lieu de contribuer à combler ce manque pour mieux comprendre les spécificités de ces nouveaux outils. Nous proposons également une nouvelle vision pour concevoir de telles primitives, couvrant ainsi les deux sous-domaines de la cryptologie que sont la cryptographie et la cryptanalyse
In recent years, new symmetric cryptographic primitives have been proposed for advanced protocols, like multi-party computation, in combination with a fully homomorphic encryption or in various systems of zero-knowledge proofs. Such protocols are parts of a context marked by the development of cloud and blockchain technologies, and must therefore respond to the growing security concerns of users. These protocols have put forward the need to minimize the number of multiplications performed by the primitive in large finite fields. Classical symmetric algorithms are then inappropriate in this context and the new cryptographic protocols must be combined with symmetric primitives (encryption or hash function) with particular properties. While the number of designs defined over large fields, called "arithmetisation-oriented", is increasing significantly, few cryptanalysis works have been proposed. The first aim of this manuscript is then to contribute to fill this gap, and hence to better understand the specificities of these new objects. We also propose a new vision to design such primitives, covering both aspects of cryptology, the cryptography and the cryptanalysis

La première instanciation concrète de la cryptographie asymétrique est le protocole d’échange de clé Diffie-Hellman, qui permet à deux individus d’établir une clé secrète commune via un canal de communication public. Cela permet ensuite l’usage de cryptographie symétrique à ce secret commun. Ce chapitre formalise cette primitive, avec plusieurs exemples.