L'omniprésence de dispositifs interconnectés amène à un intérêt massif pour la sécurité informatique fournie entre autres par le domaine de la cryptographie. Pendant des décennies, les spécialistes en cryptographie estimaient le niveau de sécurité d'un algorithme cryptographique indépendamment de son implantation dans un dispositif. Cependant, depuis la publication des attaques d'implantation en 1996, les attaques physiques sont devenues un domaine de recherche actif en considérant les propriétés physiques de dispositifs cryptographiques. Dans notre dissertation, nous nous concentrons sur les attaques profilées. Traditionnellement, les attaques profilées appliquent des méthodes paramétriques dans lesquelles une information a priori sur les propriétés physiques est supposée. Le domaine de l'apprentissage automatique produit des modèles automatiques et génériques ne nécessitant pas une information a priori sur le phénomène étudié.<p><p>Cette dissertation apporte un éclairage nouveau sur les capacités des méthodes d'apprentissage automatique. Nous démontrons d'abord que les attaques profilées paramétriques surpassent les méthodes d'apprentissage automatique lorsqu'il n'y a pas d'erreur d'estimation ni d'hypothèse. En revanche, les attaques fondées sur l'apprentissage automatique sont avantageuses dans des scénarios réalistes où le nombre de données lors de l'étape d'apprentissage est faible. Par la suite, nous proposons une nouvelle métrique formelle d'évaluation qui permet (1) de comparer des attaques paramétriques et non-paramétriques et (2) d'interpréter les résultats de chaque méthode. La nouvelle mesure fournit les causes d'un taux de réussite élevé ou faible d'une attaque et, par conséquent, donne des pistes pour améliorer l'évaluation d'une implantation. Enfin, nous présentons des résultats expérimentaux sur des appareils non protégés et protégés. La première étude montre que l'apprentissage automatique a un taux de réussite plus élevé qu'une méthode paramétrique lorsque seules quelques données sont disponibles. La deuxième expérience démontre qu'un dispositif protégé est attaquable avec une approche appartenant à l'apprentissage automatique. La stratégie basée sur l'apprentissage automatique nécessite le même nombre de données lors de la phase d'apprentissage que lorsque celle-ci attaque un produit non protégé. Nous montrons également que des méthodes paramétriques surestiment ou sous-estiment le niveau de sécurité fourni par l'appareil alors que l'approche basée sur l'apprentissage automatique améliore cette estimation. <p><p>En résumé, notre thèse est que les attaques basées sur l'apprentissage automatique sont avantageuses par rapport aux techniques classiques lorsque la quantité d'information a priori sur l'appareil cible et le nombre de données lors de la phase d'apprentissage sont faibles. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Title: Solving AX-equations Author: Jan Butora Department: Department of algebra Supervisor: doc. RNDr. Jiří Tůma, DrSc., Department of algebra Abstract: In this work, we present concept of AX-equations and focus on two such equations. Using similiar techniques, we build a theory for both equations, which allows us to express number of their solutions based only on their parameters. Using this theory, we demonstrate on an example that differential steps, used in differential cryptanalysis of modular addition, are not independent. Moreover, based on this theory we introduce and implement fast algorithms for searching solutions. Keywords: differential cryptanalysis, AX-equations, modular addition, carry, sol- vability condition

Cryptography is science of secure message transmission. Cryptanalysis is involved with breaking these encrypted messages. Both cryptography and cryptanalysis constitute together to form cryptology. Anonymity means namelessness i.e., the quality or state of being unknown while authenticity translates to the quality or condition of being authentic or genuine. Anonymity and authenticity are two different embodiments of personal secrecy. Modern power has increased in its capacity to designate individuals, due to which they find it inconvenient to continue communicating, remaining anonymous. In this thesis we are going to describe an anonymous system which consists of a number of entities which are anonymous and are communicating with each other without revealing their identity and at the same time maintaining their authenticity such that an anonymous entity(sayE1)will be able to verify that, the message it received from another anonymous entity(sayE2)subsequent to an initial message from E2, are in fact from E2 itself. Later when E2 tries to recommend a similar communication to E1 with another anonymous entity E3 in the system, E1 must be able to verify that recommendation, without E2 losing its authenticity of its communication with E1 to E3. This thesis is divided into four chapters. The first chapter is an introduction to cryptography, symmetric key cryptography and public key cryptography. It also summarizes the contribution of this thesis. The second chapter gives various protocol for the above problem ’Anonymity with Authenticity’ along with its extension. Totally six protocols are proposed for the above problem. In third chapter all these six protocols are realized using four different schemes, where each scheme has its own pros and cons. The fourth and final chapter concludes with a note on what possible factors these four different realization schemes need to be chosen and other possible realization schemes.

Les travaux exposés dans cette thèse se situent à l’interface des mathématiques discrètes, des corps finis et de la cryptographie symétrique.Les 'boîtes-S’ sont des fonctions non-linéaires de petites tailles qui constituent souvent la partie de confusion, indispensable, des chiffrements par blocs ou des fonctions de hachages.Dans la première partie de cette thèse, nous nous intéressons à la construction de boîtes-S bijectives résistantes aux attaques différentielle. Nous étudions l’inverse pour la composition des monômes de permutations optimaux vis-à-vis du critère différentiel. Nous explorons ensuite des classes spécifiques de polynômes creux. Enfin, nous construisons des boîtes-S à partir de leurs dérivées discrètes.Dans la deuxième partie, nous portons notre attention sur la cryptanalyse différentielle impossible. Cette cryptanalyse à clairs choisis très performante pour attaquer des chiffrements par blocs itératifs, exploite la connaissance d’une différentielle de probabilité zéro pour écarter les clés candidates. Elle est très technique, et de nombreuses erreurs ont été repérées dans des travaux passés, invalidant certaines attaques. Le but de ces travaux est de formaliser et d’automatiser l’évaluation des complexités d’une telle attaque afin d’unifier et d’optimiser les résultats obtenus. Nous proposons aussi de nouvelles techniques réduisant les complexités cette cryptanalyse. Nous démontrons enfin l’efficacité de notre approche en fournissant les meilleures cryptanalyses différentielles impossibles contre les chiffrements CLEFIA, Camellia, LBlock et Simon. / The work I have carried out in this thesis lie between discrete mathematics, finite fields theory and symmetric cryptography. In block ciphers, as well as in hash functions, SBoxes are small non-linear and necessary functions working as confusion layer.In the first part of this document, we are interesting in the design of bijective SBoxes that have the best resistance to differential attacks. We study the compositional inverse of the so-called Almost Perfect Nonlinear power functions. Then, we extensively study a class of sparse permutation polynomials with low differential uniformity. Finally, we build functions, over finite fields, from their discrete derivatives.In the second part, we realize an automatic study of a certain class of differential attacks: impossible differential cryptanalysis. This known plaintexts attack has been shown to be very efficient against iterative block ciphers. It exploits the knowledge of a differential with probability zero to occur. However this cryptanalysis is very technical and many flaws have been discovered, thus invalidating many attacks realized in the past. Our goal is to formalize, to improve and to automatize the complexity evaluation in order to optimize the results one can obtain. We also propose new techniques that aims at reducing necessary data and time complexities. We finally prove the efficiency of our method by providing some of the best impossible differential cryptanalysis against Feistel oriented block ciphers CLEFIA, Camellia, LBlock and Simon.

Le 10ème problème de Hilbert, consistant à trouver les solutions entières d'équations polynomiales est un problème crucial en cryptanalyse. Si ce dernier a été prouvé indécidable, Coppersmith publia en 1996 une méthode basée sur la réduction de réseaux permettant de trouver efficacement l'ensemble des petites solutions de certaines équations polynomiales. De nombreuses applications de cette méthode ont vu le jour dans le domaine de la cryptanalyse à clé publique, notamment lorsque le cryptosystème est exécuté sur un système embarqué et qu'une partie de la clé secrète est dévoilée par la réalisation d'attaques physiques sur le dispositif. Dans ce contexte, nous proposons une attaque physique sur le schéma de signature RSA en mode CRT où une application de la méthode de Coppersmith permet de compléter l'information obtenue par l'attaque physique. Nous proposons également un nouvel algorithme déterministe basé sur la méthode de Coppersmith pour factoriser les entiers de la forme $N=p^rq^s$ en temps polynomial lorsque $r$ ou $s$ sont suffisamment grands. Enfin, si les applications de la méthode de Coppersmith sont nombreuses, en pratique, du fait que les réseaux à réduire soient gigantesques, les petites solutions ne peuvent être retrouvées que jusqu'à une borne qui est plus petite que la borne théorique annoncée. Aussi, une autre contribution de cette thèse consiste en la proposition de deux méthodes permettant une accélération du temps d'exécution de l'algorithme de Coppersmith. Lorsque les deux méthodes sont combinées, le nouvel algorithme s'effectue des centaines de fois plus rapidement pour des paramètres typiques, permettant ainsi dans de nombreux cas d'atteindre la borne théorique. / The 10th Hilbert problem, which consists in finding integer solutions to polynomial equations is a crucial problem in cryptanalysis, which has been proven to be undecidable. However, Coppersmith published in 1996 a method based on lattice reduction, which allows to efficiently find all small solutions to some polynomial equations. Many applications of this method have risen in public key cryptanalysis, especially when the cryptosystem is executed on embedded systems and part of the secret key is revealed through physical attacks performed on the device. In this context, we propose in this thesis a physical attack on the RSA signature scheme when the CRT mode is used, where an application of Coppersmith's method allows to complete the information previously obtained by the physical attack. We also propose a new deterministic algorithm based on Coppersmith's method for factoring integers of the form $N=p^rq^s$ in polynomial time, under the condition that $r$ and/or $s$ are sufficiently large.Finally, if the applications of Coppersmith's method are numerous, in practice, since the lattices to be reduced are huge, the small solutions can only be recovered until a bound which is smaller than the enounced theoretical bound. Thus, another contribution of this thesis lies in the proposition of two methods which allow to speed up the execution time of Coppersmith's algorithm. When both speedups are combined, the new algorithm performs hundreds of times faster for typical parameters, which allows to reach the theoretical bound in many cases.

Les travaux réalisés dans cette thèse ont pour objet l'analyse de la sécurité de chiffrements à clef secrète. Plus précisément, nous y décrivons la cryptanalyse de plusieurs chiffrements par blocs et à flot ayant pour point commun d'avoir été conçus récemment pour répondre aux nouveaux enjeux de la cryptographie symétrique. Nous mettons en avant des attaques des versions complètes de cinq chiffrements, prouvant ainsi que ces primitives cryptographiques n'apportent pas la sécurité annoncée par leurs concepteurs.La première partie de cette thèse est dédiée à l'analyse de chiffrements par blocs avec des techniques de cryptanalyse différentielle. Nous montrons comment mener une attaque par différentielles tronquées sur la famille de chiffrements à bas coût KLEIN en exploitant la faible diffusions de sa fonction de tour. Ensuite, nous nous intéressons à Zorro et à Picaro, deux chiffrements conçus de sorte à être faciles à protéger contre les attaques par canaux auxiliaires, et montrons que les choix de conception guidés par cette contrainte ont engendré des faiblesses dans leurs propriétés différentielles, pouvant ensuite être exploitées dans des attaques.La seconde partie du manuscrit porte sur la cryptanalyse de chiffrements à flot. Nous y étudions Sprout et Flip, deux chiffrements aux structures innovantes visant respectivement à limiter la taille du circuit matériel nécessaire à l'implémentation et une bonne adaptation dans un schéma de FHE. / The main subject of this thesis is the security analysis of symmetric key ciphers. Specifically, we study several recently proposed block and stream ciphers and prove that the level of security stated by their designers is overestimated. The ciphers we study were all designed in order to meet the needs of one of the new applications of symmetric cryptography, which include symmetric ciphers for very constrained environments.The first part of the thesis is dedicated to the analysis of block ciphers with techniques based on differential cryptanalysis. We start with the description of a truncated differential attack on the family of lightweight ciphers KLEIN. Next, we analyse two ciphers that were designed in such a way that they could be easily and effectively protected against side-channel attacks: Zorro and Picaro. We show that the design choices made by their designers lead to weak diffusion properties. We exploit these imperfections to devise a differential cryptanalysis of Zorro and a related key attack on Picaro.The second part of this thesis deals with stream ciphers and gives an analysis of two innovative designs: Sprout and Flip. Sprout was designed in order to limit its hardware area size and to suit very constrained environments, while Flip reaches efficient performances when used in FHE schemes. In both cases, we find flaws that lead to attacks of the particular set of parameters proposed for these ciphers.

The Rijndael cipher was chosen as the Advanced Encryption Standard (AES) in August 1999. Its internal structure exhibits unusual properties such as a clean and simple algebraic description for the S-box. In this research, we construct a scalable family of ciphers which behave very much like the original Rijndael. This approach gives us the opportunity to use computational complexity theory. In the main result, we generate a candidate one-way function family from the scalable Rijndael family. We note that, although reduction to one-way functions is a common theme in the theory of public-key cryptography, it is rare to have such a defense of security in the private-key theatre. In this thesis a plan of attack is introduced at the circuit level whose aim is not break the cryptosystem in any practical way, but simply to break the very bold Rijndael security claim. To achieve this goal, we are led to a formal understanding of the Rijndael security claim, juxtaposing it with rigorous security treatments. Several of the questions that arise in this regard are as follows: ``Do invertible functions represented by circuits with very small numbers of gates have better than worst case implementations for their inverses?' ``How many plaintext/ciphertext pairs are needed to uniquely determine the Rijndael key?'

The aim of this thesis is to introduce the family of A5 algorithm which is used in data encryption and decryption in GSM phones. It is focused on real time cryptanalysis of the stream cipher A5/1. It describes in detail the known plaintext attack published by A. Biryukov, A. Shamir and D. Wagner. Both the attack and the cipher are implemented. The implementation proves that the preprocessing stage of the attack is very time consuming, but the actual attack can be carried out in real time on a single PC. Then the problem of finding a good statistical model for the process of generating tree of predecessors of internal states of A5/1 is studied. We present reasons why the singletype Galton-Watson process is not suitable for the problem and introduce a multitype Galton-Watson process and a macro process. The models are applied to the process of generating predecessors and their predictions are compared with experimental data.

<p>This doctoral thesis summarizes research in quantum cryptography done at the Department of Electronics and Telecommunications at the Norwegian University of Science and Technology (NTNU) from 1998 through 2007.</p><p>The opening parts contain a brief introduction into quantum cryptography as well as an overview of all existing single photon detection techniques for visible and near infrared light. Then, our implementation of a fiber optic quantum key distribution (QKD) system is described. We employ a one-way phase coding scheme with a 1310 nm attenuated laser source and a polarization-maintaining Mach-Zehnder interferometer. A feature of our scheme is that it tracks phase drift in the interferometer at the single photon level instead of employing hardware phase control measures. An optimal phase tracking algorithm has been developed, implemented and tested. Phase tracking accuracy of +-10 degrees is achieved when approximately 200 photon counts are collected in each cycle of adjustment. Another feature of our QKD system is that it uses a single photon detector based on a germanium avalanche photodiode gated at 20 MHz. To make possible this relatively high gating rate, we have developed, implemented and tested an afterpulse blocking technique, when a number of gating pulses is blocked after each registered avalanche. This technique allows to increase the key generation rate nearly proportionally to the increase of the gating rate. QKD has been demonstrated in the laboratory setting with only a very limited success: by the time of the thesis completion we had malfunctioning components in the setup, and the quantum bit error rate remained unstable with its lowest registered value of about 4%.</p><p>More than half of the thesis is devoted to various security aspects of QKD. We have studied several attacks that exploit component imperfections and loopholes in optical schemes. In a large pulse attack, settings of modulators inside Alice's and Bob's setups are read out by external interrogating light pulses, without interacting with quantum states and without raising security alarms. An external measurement of phase shift at Alice's phase modulator in our setup has been demonstrated experimentally. In a faked states attack, Eve intercepts Alice's qubits and then utilizes various optical imperfections in Bob's scheme to construct and resend light pulses in such a way that Bob does not distinguish his detection results from normal, whereas they give Bob the basis and bit value chosen at Eve's discretion. Construction of such faked states using several different imperfections is discussed. Also, we sketch a practical workflow of breaking into a running quantum cryptolink for the two abovementioned classes of attacks. A special attention is paid to a common imperfection when sensitivity of Bob's two detectors relative to one another can be controlled by Eve via an external parameter, for example via the timing of the incoming pulse. This imperfection is illustrated by measurements on two different single photon detectors. Quantitative results for a faked states attack on the Bennett-Brassard 1984 (BB84) and the Scarani-Acin-Ribordy-Gisin 2004 (SARG04) protocols using this imperfection are obtained. It is shown how faked states can in principle be constructed for quantum cryptosystems that use a phase-time encoding, the differential phase shift keying (DPSK) and the Ekert protocols. Furthermore we have attempted to integrate this imperfection of detectors into the general security proof for the BB84 protocol. For all attacks, their applicability to and implications for various known QKD schemes are considered, and countermeasures against the attacks are proposed.</p><p>The thesis incorporates published papers [J. Mod. Opt. 48, 2023 (2001)], [Appl. Opt. 43, 4385 (2004)], [J. Mod. Opt. 52, 691 (2005)], [Phys. Rev. A 74, 022313 (2006)], and [quant-ph/0702262].</p>

This doctoral thesis summarizes research in quantum cryptography done at the Department of Electronics and Telecommunications at the Norwegian University of Science and Technology (NTNU) from 1998 through 2007. The opening parts contain a brief introduction into quantum cryptography as well as an overview of all existing single photon detection techniques for visible and near infrared light. Then, our implementation of a fiber optic quantum key distribution (QKD) system is described. We employ a one-way phase coding scheme with a 1310 nm attenuated laser source and a polarization-maintaining Mach-Zehnder interferometer. A feature of our scheme is that it tracks phase drift in the interferometer at the single photon level instead of employing hardware phase control measures. An optimal phase tracking algorithm has been developed, implemented and tested. Phase tracking accuracy of +-10 degrees is achieved when approximately 200 photon counts are collected in each cycle of adjustment. Another feature of our QKD system is that it uses a single photon detector based on a germanium avalanche photodiode gated at 20 MHz. To make possible this relatively high gating rate, we have developed, implemented and tested an afterpulse blocking technique, when a number of gating pulses is blocked after each registered avalanche. This technique allows to increase the key generation rate nearly proportionally to the increase of the gating rate. QKD has been demonstrated in the laboratory setting with only a very limited success: by the time of the thesis completion we had malfunctioning components in the setup, and the quantum bit error rate remained unstable with its lowest registered value of about 4%. More than half of the thesis is devoted to various security aspects of QKD. We have studied several attacks that exploit component imperfections and loopholes in optical schemes. In a large pulse attack, settings of modulators inside Alice's and Bob's setups are read out by external interrogating light pulses, without interacting with quantum states and without raising security alarms. An external measurement of phase shift at Alice's phase modulator in our setup has been demonstrated experimentally. In a faked states attack, Eve intercepts Alice's qubits and then utilizes various optical imperfections in Bob's scheme to construct and resend light pulses in such a way that Bob does not distinguish his detection results from normal, whereas they give Bob the basis and bit value chosen at Eve's discretion. Construction of such faked states using several different imperfections is discussed. Also, we sketch a practical workflow of breaking into a running quantum cryptolink for the two abovementioned classes of attacks. A special attention is paid to a common imperfection when sensitivity of Bob's two detectors relative to one another can be controlled by Eve via an external parameter, for example via the timing of the incoming pulse. This imperfection is illustrated by measurements on two different single photon detectors. Quantitative results for a faked states attack on the Bennett-Brassard 1984 (BB84) and the Scarani-Acin-Ribordy-Gisin 2004 (SARG04) protocols using this imperfection are obtained. It is shown how faked states can in principle be constructed for quantum cryptosystems that use a phase-time encoding, the differential phase shift keying (DPSK) and the Ekert protocols. Furthermore we have attempted to integrate this imperfection of detectors into the general security proof for the BB84 protocol. For all attacks, their applicability to and implications for various known QKD schemes are considered, and countermeasures against the attacks are proposed. The thesis incorporates published papers [J. Mod. Opt. 48, 2023 (2001)], [Appl. Opt. 43, 4385 (2004)], [J. Mod. Opt. 52, 691 (2005)], [Phys. Rev. A 74, 022313 (2006)], and [quant-ph/0702262].