Creation And Parallel Look-up System Of Irregular Charset Space Rainbow-table

After Brute Force and Look-up Table method,Rainbow Table algorithm based on the Time-Memory Trade-Off theory is widely applied to the password analysis of certain hash function algorithms(such as salt-free algorithm MD5,SHA-1,NTLM,etc.).In 2003,Oechslin first proposed the concept of Rainbow Table based on the TMTO(Time-Memory Trade-Off)theory,and put forward an method that using a different reduction function in every state of chain computing to avoid the chain loop and chain collision.There are two main research directions of the Rainbow Table: First,by studying the characteristics of the actual password,divide the password into various section with the appearing regularity,reaserchers are able to apply a more precise character space regular expression to describe the long plaintext password,in order to reduce the table precomputation time and the storage cost;Optimizing algorithm of Hash Function or using techniques like Check-Points to reduce probability of chain collision and flase alarm is functional.Secondly,based on the commodity storage devices and high-performance computing devices,applying distributed computing framework to build a computing cluster to improve efficiency of table pre-calculation phase and online search pahse.In this paper,by applying MPI and OpenMP technology,we designed and implemented irregular character space Rainbow Table generation system based on MIC cluster.Also,we implemented the Reduction Function which suits for irregular character space expression.In addition,a Rainbow Table distributed parallel search system based on multiple GPU servers is designed to accelerate the online search phase efficiency.The nodes of the scheduler are responsible for resource management and task scheduling.GPU nodes contain IO and computing resources.IO resources are used for Rainbow Table data storage,look-up end point and return start point,while computational resources are used for chain computation.Through the table data stored in multiple nodes scatteredly,the system reduces time using in reading file phase with multi-nodes IO capacity.Finally,this paper realizes the parallelization excucation of the chain computation module,network transmission module and the file reading module,in order to achieve the mutual concealment of the time between modules,which is of great benefit for improving the operation efficiency of this searching system.