Research On Extended Rainbow Table Generation Based On HADOOP

Nowadays, hash functions have been widely used in all aspects of computer science and have played an important role in operating systems, security protocols of communications. The research of the security of hash functions has become one of top research directions in the area of cryptography and information security.Currently, besides brute force, Oechslin's Rainbow table is the most widely used method of preimage attack of hash algorithm, meanwhile, the one with the best performance. Rainbow table is based on Hellman's time-memory trade off method and has been continually improved by Oechslin et al. By using different reduction functions, rainbow table solved problems such as high probability of chain overlap in classic table, and is able to provide a high success rate of crack in a very short period of time. Rainbow table has become important means of the preimage attack of hash algorithm.This paper first studied the classic attack method, compared and analyzed the Hellman's time-memory trade off method and the principle of rainbow table. And for the current rainbow tables, this paper proposed two main improvements:using Hadoop and extending by generator.One of the disadvantages of rainbow table is the unacceptable time duration when generating tables that support huge plaintext space under current hardware condition. This paper proposes to generate rainbow table by using Hadoop as the infrastructure of cloud computing and MapReduce as the framework. By building the cluster and testing, performance data is obtained and conclusion is made that Hadoop can effectively share computational load among nodes and significantly reduce the total time-consumption of the task. Moreover, problem of large scale file storage is solved by using HDFS distributed file system.In addition, this paper proposes an idea of extended rainbow table based on generator aiming to improve the plaintext space. It is based on some universal law of the process of artificial long passwords. By extending the original plain charset to the generator(words, Chinese pinyin) and coupled with mode transformation, this paper proposes a new extended reduction function that can mapping the hash value to the specific space of the generator. The plaintext space is greatly compressed by store extended rainbow tables and the dictionary together. So a new method of attacking artificial passwords is provided. In Hadoop cluster, tests of the generation and cracking of extended rainbow table of three phonetic are completed. With tables of success rate of over 90%, the generate time can be controlled in less than 3 minutes. It is fully demonstrated that extended rainbow table is a new way to effectively support long password cracking.