Research And Implementation Of Rainbow Tables’ Formation And Search On GPU Cluster

Information security increasingly becomes restricted important areas of computer softwareindustry in its overall development, and the hash function is one of the most widely usedmethods and tools. For the corresponding security issues have attracted the attention ofresearchers in the information security industry at home and abroad, the method of usingrainbow tables to crack passwords also is one of the important research focus.Traditional methods include exhaustive search and precomputed table look-ups. But withthe complexity of the encryption algorithm and key space continuing to increase, it makes theexisting methods need more valid time to crack. Rainbow tables proposed by Oechslin can berelatively effective to improve the efficiency of the attack. Developed from time-memory trade-off proposed by Hellman, the method uses different reduction functions to solve the coincidenceof the chain in the original table, thereby enhances the efficiency of generation and search, andbecomes an important means to attack the hash function. But rainbow tables’ furtherdevelopment is still possible, and with the continuous improvement of computer performanceand GPU devices continue to mature, we can use the method of cluster generation and tasksscheduling.Firstly, based on the original algorithm and their thoughts, the rainbows tables’ generationis segmented into sub-rainbow tables which we proposed according to the characteristics of thecluster architecture, and generated independently by the cluster nodes’ GPU.Secondly, the original approach of outer sorting process becomes to create the index, andthe sub-rainbow tables are scanned twice. The number of index in buckets configured tostatistics tables in the first scan. According to prefix in tables, the data from sub-rainbow tablesis read into S-point tables and E-point tables corresponding to offset position in the second scan.Finally, after building GPU cluster, the original task is divided into index groups computedby GPU and searched by CPU. With using task scheduling strategy the task is decomposed intosubtasks, which processed by each compute node’s GPU. Then the index group is calculated byCPU to achieve high scalability and large crack efficiency.In the study of rainbow tables to crack the password based GPU, an effective model systemis established considering to the cluster, and one mainstream encryption algorithm is tested toachieve good results.