des线性分析破解des.pdf-资料库

novicekk-1573464-16359647263454899973.pdf-第1页.png

第1页 / 共75页

novicekk-1573464-16359647263454899973.pdf-第2页.png

第2页 / 共75页

novicekk-1573464-16359647263454899973.pdf-第3页.png

第3页 / 共75页

novicekk-1573464-16359647263454899973.pdf-第4页.png

第4页 / 共75页

novicekk-1573464-16359647263454899973.pdf-第5页.png

第5页 / 共75页

novicekk-1573464-16359647263454899973.pdf-第6页.png

第6页 / 共75页

novicekk-1573464-16359647263454899973.pdf-第7页.png

第7页 / 共75页

novicekk-1573464-16359647263454899973.pdf-第8页.png

第8页 / 共75页

Linear Cryptanalysis of DES Diploma Thesis Pascal Junod Diploma Professor: Prof. Dr. Ueli Maurer Supervisor: Prof. Dr. Serge Vaudenay EPF Lausanne ETH Z¨urich

to Mimi

Abstract 3 The main goal of this diploma work is the implementation of Matsui’s linear cryptanalysis of DES and a statistical and theoretical analysis of its com- plexity and success probability. In order to achieve this goal, we implement ﬁrst a very fast DES routine on the Intel Pentium III MMX architecture which is fully optimised for linear cryptanalysis. New implementation con- cepts are applied, resulting in a speed increase of almost 50 % towards the best known classical implementation. The experimental results suggest strongly that the attack is in average about 10 times faster (O239 DES furthermore, we have achieved a complexity of O243 by using only 242.5 computations) as expected with 243 known plaintext-ciphertext at disposal; known pairs. Last, we propose a new analytical expression which approx- imates success probabilities; it gives slightly better results than Matsui’s experimental ones. R´esum´e Le but principal de ce projet est l’impl´ementation de la cryptanalyse lin´eaire de DES, technique invent´ee par Matsui, et d’eﬀectuer une analyse statis- tique de sa complexit´e. Dans ce but, nous avons impl´ement´e une routine DES extrˆemement rapide sur une architecture Intel Pentium III MMX. Des concepts tr`es modernes ont ´et´e utilis´es, ainsi que des optimisations ren- dues possibles par l’attaque, ce qui permet une augmentation de rapidit´e de 50 % par rapport `a l’impl´ementation classique la plus rapide `a ce jour. Les r´esultats exp´erimentaux sugg`erent clairement que la complexit´e de l’attaque est en moyenne 10 fois moindre (`a savoir O239 ´evaluations de DES) par sont disponibles; de plus, nous obtenons une complexit´e de O243 moyen- rapport `a celle estim´ee par Matsui quand 243 couples de textes clairs-chiﬀr´es nant une quantit´e plus faible (242.5) de couples. Nous proposons enﬁn une expression analytique qui donne une approximation l´eg`erement meilleure par rapport aux valeurs exp´erimentales de Matsui pour ce qui concerne la probabilit´e de succ`es de l’attaque.

CONTENTS Contents 1 The DES Cipher: Implementation and Optimisation 1.1 Historical Overview . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Deﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 General Outline . . . . . . . . . . . . . . . . . . . . . 1.2.2 The Key Schedule . . . . . . . . . . . . . . . . . . . . 1.2.3 The f-function . . . . . . . . . . . . . . . . . . . . . . 1.3 A Bitsliced Implementation . . . . . . . . . . . . . . . . . . . 1.3.1 The Classical Way to Implement DES in Software . . 1.3.2 The Bitslicing Concept . . . . . . . . . . . . . . . . . . 1.3.3 The Pentium’s MMX Architecture . . . . . . . . . . . 1.3.4 Cache Latency Optimization . . . . . . . . . . . . . . 1.3.5 Optimization of DES . . . . . . . . . . . . . . . . . . . 1.3.6 Performance Results . . . . . . . . . . . . . . . . . . . 2 Theoretical Description of the Attack 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Linear Cryptanalysis Principles . . . . . . . . . . . . . . . . . 2.2.1 Getting One Bit of Information about the Key . . . . 2.2.2 Getting Multiple Bits of Information about the Key . 2.3 The 16-Rounds DES Attack . . . . . . . . . . . . . . . . . . . 2.3.1 The Best 14-rounds Linear Approximations . . . . . . 2.3.2 An Improved Algorithm . . . . . . . . . . . . . . . . . 2.3.3 Comparison Between the Two Attacks . . . . . . . . . 3 A Practical Implementation of the Attack 3.1 3.2 Generating Huge Amounts of Pseudo-Random Blocks Introduction and Generalities . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Linear Feedback Shift Registers . . . . . . . . . . . . . 3.2.2 Choice of the Primitive Polynomial’s Degree . . . . . . 3.2.3 Eﬃcient Implementation of a LFSR . . . . . . . . . . Implementation Speciﬁc Aspects . . . . . . . . . . . . . . . . 3.3.1 Feeding the Encryption Routine with Pseudo-Random Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Collecting Statistical Properties . . . . . . . . . . . . . 3.4 Management of the Processes . . . . . . . . . . . . . . . . . . 3.3 4 Theoretical Considerations 4.1 Some Mathematical Preliminaries . . . . . . . . . . . . . . . . 4.2 Success Probability of the Attack . . . . . . . . . . . . . . . . 4.2.1 Modelling the Statistical Experiment . . . . . . . . . . 4.2.2 A Simpliﬁed Statistical Experiment . . . . . . . . . . 4.2.3 Towards the Good Distribution . . . . . . . . . . . . . 4 8 8 9 9 11 12 13 13 14 15 16 16 17 19 19 19 20 21 23 23 24 25 27 27 29 29 31 34 35 35 35 36 39 39 41 41 45 47

CONTENTS 5 4.2.4 Maximal Rank Probability . . . . . . . . . . . . . . . 4.2.5 Complexity of the Attack . . . . . . . . . . . . . . . . 5 Experimental Results 5.1 Experimental Complexities . . . . . . . . . . . . . . . . . . . 5.2 Experimental Success Probabilities . . . . . . . . . . . . . . . 5.2.1 Experimental Maximal Rank Probabilities . . . . . . . 5.2.2 Guessing Success Probability . . . . . . . . . . . . . . 5.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.1 Complexity . . . . . . . . . . . . . . . . . . . . . . . . 5.3.2 Maximal Rank Probability of Subkey Candidates . . . 6 Conclusion A Conversion Between Standard and Matsui’s Notations A.1 Standard, Kwan’s and Matsui’s Notation . . . . . . . . . . . A.2 Conversion Tables for Plaintext . . . . . . . . . . . . . . . . . A.3 Conversion Tables for the Subkeys . . . . . . . . . . . . . . . B Speed Measurement Procedure B.1 The Speed Measurement Routine . . . . . . . . . . . . . . . . B.2 The Measurement Procedure . . . . . . . . . . . . . . . . . . C Approximation Values of the Success Probability D Detailed Experimental Ranks 49 52 55 55 57 57 58 59 59 60 62 66 66 68 69 72 72 72 74 75

CONTENTS 6 Acknowledgements First of all, I wish to express my profound gratitude to Professor Serge Vaudenay for accepting to supervise my diploma thesis and for having re- ceived me in his new laboratory. I thank Professor Ueli Maurer for accepting to be my diploma professor, for allowing me to do it in Lausanne, and most important, for having shown me the beauty of cryptology during his lectures. In no special order, I would now thank specially Dr. John Pliam, Dr. Ste- fan Wolf, Reto Kohlas, Eric Debes, Aslan Tchamkerten, Cyril Measson, Changyan Di, Nenad Buncic, and Sophie Vitali for their role in this work, or more generally in my studies. They all know why! Last but no least, I would thank my parents for their support and Myriam for everything.

CONTENTS Subject 7 The objectives of this project are the experiment and the analysis of Mat- sui’s linear cryptanalysis on DES. This attack was published in 1994, but no statistical analysis was possible at this time because computers were not fast enough. In this project, we ﬁrst implement an eﬃcient DES function, then run Matsui’s attack and ﬁnally make a statistical analysis of its complexity. DES was an US encryption standard issued by NIST (previously NBS) in 1977 ([16]). In 1997, Biham proposed in [3] a parallel implementation in- spired by SIMD (Single Instruction Multiple Data) architectures on regular computers which is the fastest at this time. According to Biham’s analy- sis, one can perform 64 parallel DES computations within 16000 elementary CPU instructions on a 64-bit microprocessor, which leads to 222 DES com- putations per second with a single microprocessor working at 1 GHz. So far, the best known attack on DES is Matsui’s linear cryptanalysis ([11, 12]). In the original paper, it is claimed that the complexity should consist in 243 DES computations on average. This leads to a one CPU- month computation. The experiment however suggests a lower complexity. The project consists in three phases which are proposed here in incremental diﬃculty levels: • Implement a fast DES function by using Biham’s technique. • Run Matsui’s attack and perform an experimental complexity analysis. • Make a better theoretical complexity analysis.

1 THE DES CIPHER: IMPLEMENTATION AND OPTIMISATION 8 1 The DES Cipher: Implementation and Optimi- sation In this chapter, we make ﬁrst a brief formal description of the DES cipher; in a second part, we give a detailed description of our bitsliced implementation of this algorithm, as well as the results of the performance measurements. 1.1 Historical Overview The DES (Data Encryption Standard) has been a worldwide standard for the past 25 years. In 1972, the former American National Bureau of Stan- dards (NBS), now called the National Institute of Standards and Technology (NIST), initiated a project with the goal of protecting computers and digital communications data. As part of this program, they wanted to develop a sin- gle, standard cryptographic algorithm. The motivations were the following: a single algorithm could be tested and certiﬁed more easily than thousand’s; furthermore, it would be easier to let interoperate diﬀerent cryptographic equipments using it. The NBS issued a ﬁrst public request for proposals in 1973; the number of received proposals indicated that there was a huge public interest in the ﬁeld of cryptography, but very little public expertise. In fact, none of the submissions came only close to meeting the requirements. A second request in 1974 brought the cipher Lucifer, developed in the IBM laboratories. After a secret review from the NSA (and the reduction of the key size from 128 to 56 bits !), and despite a lot of criticism because of its obscure role, the Data Encryption Standard was adopted as a federal standard in 1976 and authorised for use on all unclassiﬁed governmental communications one year later (see [16]). The standard was recertiﬁed in 1983, 1987 and in 1993 without a lot of problems. In 1997, as it was showing some signs of old age and as it can no more be considered as a secure algorithm, the NIST has decided to launch a process in order to ﬁnd a successor for the next 20 years (see [1]). We recall here that it was possible in 1997 to build a hardware device which can run an exhaustive search of the key in less than 4 days with a budget of $ 200’000, see [7] for more details and listings. Knowing that agencies (or criminal organisations) have millions of $ at disposal, one can have a good idea of the actual security of DES. However, we have to note that variants of DES, like Triple-DES, are still considered to be very secure.

资料库

des线性分析破解des.pdf

相关推荐

开发技术

热门标签

最新资料