Comparison of Cryptanalytic Time Memory Tradeoff Algorithms with Focus on Some Rainbow Variants

Cited 0 time in Web of Science Cited 0 time in Scopus
자연과학대학 수리과학부
Issue Date
서울대학교 대학원
Cryptanalytic Time memory tradeoffTime memory data tradeoffThick rainbow tradeoffFuzzy rainbow tradeoffPerfect tableNon-perfect table
학위논문 (박사)-- 서울대학교 대학원 : 수리과학부, 2016. 2. 홍진.
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.
Files in This Item:
Appears in Collections:
College of Natural Sciences (자연과학대학)Dept. of Mathematical Sciences (수리과학부)Theses (Ph.D. / Sc.D._수리과학부)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.