An Improvement And Implementation Of Rainbow Table Based On Heterogeneous Model

Exhaustive search, table lookup and rainbow table can be utilized to solve many cryptanalytic problems. However, the exhaustive search will require a lot of time anytime and the table lookup technology will require large amount of memory. Therefore, they are limited during the practical attack. Rainbow table is the sole feasible method during many applications and it provides a trade-off between the time and the memory.Rainbow table is proposed by Oechslin in 2003. The most important contribution of Oechslin’s work is that he provides the attack system for the algorithm used by the login system of Windows XP and it can achieve99.0% of the success rate. However, it lacks of the consideration of the feasibility of the precomputation. Through further analysis of the Rainbow table, we find that the estimated time of traditional implementation is still out of reach for many applications. Therefore, the most important motivation of our work aims to reduce the time of precomputation. GPUaccelerated heterogeneous model is the use of a graphics processing unit(GPU) together with a CPU to accelerate scientific, analytics, engineering,consumer, and enterprise applications. CUDA is a parallel model platform and programming model created by NVIDIA and implemented by the graphics processing units(GPUs) that they produce. New architecture brings new opportunities and new challenges together.In this thesis, we propose several methods to improve and implement the rainbow table based on heterogeneous model. The main work and innovation points are as follows:We will propose several improvement for the rainbow table. Firstly,we will analysis the gap between theoretical research and implementation.Then, we will propose the general method to locate the best parameters and propose an improved table structure.In terms of the implementation of the rainbow table, we will discuss it in detail and analyze how to implement in heterogeneous model. We will also propose how to implement the reduction function and how to choose paremters for the device. Finally, we will present new implementation of HMAC-MD5 based on the property of the rainbow table and GPU.We seek to use our implementation to attack the HMAC-MD5 with the CPA, which is short for chosen-plaintext attack. From the view of experiment, we verify the conclusion summered in previous chapters and present the actual improvement of our implementation. Finally, we conclude that the bottleneck of the rainbow table should be the hardware and implementation of the function. At the same time, the bottleneck of cryptanalysis is the alarm introduced by collision.