Publications
Detailed Information
Comparison of Cryptanalytic Time Memory Tradeoff Algorithms with Focus on Some Rainbow Variants
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | 홍진 | - |
dc.contributor.author | 김병일 | - |
dc.date.accessioned | 2017-07-14T00:42:08Z | - |
dc.date.available | 2017-07-14T00:42:08Z | - |
dc.date.issued | 2016-02 | - |
dc.identifier.other | 000000132510 | - |
dc.identifier.uri | https://hdl.handle.net/10371/121305 | - |
dc.description | 학위논문 (박사)-- 서울대학교 대학원 : 수리과학부, 2016. 2. 홍진. | - |
dc.description.abstract | Cryptanalytic time memory tradeoff algorithms are tools for inverting one-way functions, and they are used to recover passwords from unsalted password hashes.
There are many publicly known tradeoff algorithms, and the rainbow tradeoff algorithm, which is widely believed to be the best tradeoff algorithm, at least among implementers, has been the most popular method. In this thesis, we provide accurate complexity analyses of the thick rainbow tradeoff algorithm and the non-perfect and perfect table fuzzy rainbow tradeoff algorithms. These are algorithms that have not yet received much attention. Our analyses show that, when the pre-computation cost and the online execution efficiency are both taken into consideration, the perfect table fuzzy rainbow tradeoff can be seen as performing the best among the three algorithms considered and actually even better than the original rainbow tradeoff. The computational complexities for some time memory data tradeoff methods are also analyzed. The multi-target tradeoffs that we cover are the classical Hellman, distinguished point, and fuzzy rainbow methods, both in their non-perfect and perfect table versions for the latter two methods. We find that their execution complexities are no different from the complexities of the corresponding single-target algorithms executed under certain matching parameters. As in the single-target case, we conclude that the perfect table fuzzy rainbow tradeoff algorithm is the most preferable among the multi-target tradeoff algorithms we have considered. | - |
dc.description.tableofcontents | Chapter 1 Introduction 1
Chapter 2 Preliminaries 5 2.1 Previous Results of Major Algorithms 7 2.1.1 Hellman Tradeoff 7 2.1.2 DP Tradeoff 8 2.1.3 Rainbow Tradeoff 10 2.2 Some Rainbow Variants 11 2.2.1 Thick Rainbow Tradeoff 12 2.2.2 Non-Perfect Table Fuzzy Rainbow Tradeoff 13 2.2.3 Perfect Table Fuzzy Rainbow Tradeoff 15 Chapter 3 Analyses of the Three Rainbow Variants 18 3.1 Thick Rainbow Tradeoff 18 3.1.1 Probability of Success 18 3.1.2 Online Complexity 21 3.2 Non-Perfect Table Fuzzy Rainbow Tradeoff 25 3.2.1 Probability of Success 25 3.2.2 Online Complexity 31 3.3 Perfect Table Fuzzy Rainbow Tradeoff 37 3.3.1 Probability of Success 37 3.3.2 Online Complexity 41 Chapter 4 Storage Optimization 49 4.1 The Degree of Ending Point Truncation 50 4.1.1 Thick Rainbow Tradeoff 50 4.1.2 Non-Perfect Table Fuzzy Rainbow Tradeoff 52 4.1.3 Perfect Table Fuzzy Rainbow Tradeoff 54 Chapter 5 Comparison of Algorithms 56 5.1 Adjustment Factors for Tradeoff Coefficients 56 5.2 Some Observations concerning Fuzzy Rainbow Tradeoffs 58 5.3 Comparison 63 Chapter 6 Time Memory Data Tradeoff Algorithms 67 6.1 Algorithms 67 6.2 Analysis 69 Chapter 7 Experiments 72 7.1 Thick Rainbow Tradeoff 72 7.2 Non-Perfect Table Fuzzy Rainbow Tradeoff 74 7.3 Perfect Table Fuzzy Rainbow Tradeoff 78 7.4 Time Memory Data Tradeoff Algorithms 84 Chapter 8 Conclusion 86 Abstract (in Korean) 91 | - |
dc.format | application/pdf | - |
dc.format.extent | 3686838 bytes | - |
dc.format.medium | application/pdf | - |
dc.language.iso | en | - |
dc.publisher | 서울대학교 대학원 | - |
dc.subject | Cryptanalytic Time memory tradeoff | - |
dc.subject | Time memory data tradeoff | - |
dc.subject | Thick rainbow tradeoff | - |
dc.subject | Fuzzy rainbow tradeoff | - |
dc.subject | Perfect table | - |
dc.subject | Non-perfect table | - |
dc.subject.ddc | 510 | - |
dc.title | Comparison of Cryptanalytic Time Memory Tradeoff Algorithms with Focus on Some Rainbow Variants | - |
dc.type | Thesis | - |
dc.description.degree | Doctor | - |
dc.citation.pages | 91 | - |
dc.contributor.affiliation | 자연과학대학 수리과학부 | - |
dc.date.awarded | 2016-02 | - |
- Appears in Collections:
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.