Research Of Rainbow Tables’ Formation And Search On MIC Cluster

Since the algorithm of Rainbow table was put forward. Reseacher use the method of Time-Memory-Trade-Off to analyze hash function collision has been widely applied.Current research work on the rainbow table is divided into two aspects: First, to ana lysis the basic principles of algorithm Rainbow table. In order to find a breakthrough of rainbow table, researchers made from algorithm to optimize efficiency or storage sp ace. This method is to use to reduce the costs of Rainbow tables’ formation and the costs of lookup. Other asperct is to use the growing and improved hardware technolog y or software technology to satisfy the growing demand for large-scale rainbow tables.Such as the use of distributed technology GPU, FPGA technology, Map/Reduce frame work and HBase distributed storage technology.In recent years, Intel released the MIC(Many Integrated Cores) coprocessor, to apply in the fields of high performance. MIC has a high degree of parallelism, suitable for complex logic calculations. Therefore, this paper uses the distributed technology of CPU and MIC co-processor to complete the works of Rainbow tables’ formation and search.This paper is designed and implemented the rainbow table system based on the MIC cluster, which use for completing the search of password tasks of hashing algorithm. The system of rainbow table has three modules, they are data generating module, data reforming module and lookup online module. Rainbow table data generation module uses the MIC cluster technology to divide the space of original rainbow table into uniform space for each MIC computing node, each node generates the task assignment independently. Data reforming module is to use the memory as much as possible to accelerate the operation. It uses the method of secondary index and bucket sort to reduce the access times of file I/O. So it has been improved the efficiency of algorithm. The lookup online module has two part, they are compute node and storage node. Computing nodes use the MIC Accelerator to calculate the end points of chain. The storage node search for the end points and return the start points to compute node. This is designed to satisfy the need of scalability and high efficiency.This paper has been done a reliability design of data integrity and consistency for the system and relevant optimization techniques. Finally, the paper has been tested a large number searching work about password, which is commonly used hash algorithm. And it shows that the Rainbow table system has good performance.