GPU Acceleration And Opitimization Of The Decryption Algorithm Of MD5 With Salt

Adding salt to the passwords before hashing them can increase the complexity and irreversible of the MD5 algorithm. The MD5 with salt is widely used in authorization of operating systems such as FreeBSD. Thus verifying the algorithm's security is very important. These days the performance of GPU-based heterogeneous platforms is ever increasing. Take the Tianhe-Ⅰas an example. It is based on the heterogeneous architecture, whose peak performance is up to 1.206Pflops. OpenCL standard also greatly enhances the portability and scalability of GPU programs. Using brute force attack to crack the MD5 with salt became possible.In this paper we first analyze the MD5 with salt on the traditional CPU-based architecture and split the tasks of the algorithm in order to map them separately onto the host and the GPU. Finally we use OpenCL language to implement and optimize the cracking algorithm on a GPU-based heterogeneous platform. Our works are as follows:Firstly, we design and realize a GPU-based algorithm to crack the MD5 with salt. We analyze the algorithm on the traditional architecture. Based on the analysis we implement those computing-intensive tasks, such as hash code generating on the GPU, those control and initialization parameters tasks on the CPU. Taking into account the costs of data transmission, the password generating task is also implemented on the GPU. Based on experimental evaluation we decide to implement the hash code matching task on the CPU. Based on the above task analysis and OpenCL language features, we implement the algorithm.Secondly, we design and realize a multi-rounds password generation algorithm to solve the GPU memory exhaust problem while the program is running. While the digit of password increases, the key space is increasing such that the GPU memory is no longer sufficient to store the passwords generated during the password generating progress. We make pairs of passwords and the OpenCL item global index number. During each round we apply as many number of work items for password generation considered as the memory can be fulfilled. To make the generating evenly distributed, we design Host-side algorithm to record the generation process, and transmit it to the OpenCL kernel as a control parameter. We also obtain marked point on the host-side to reduce the host and GPU data transfer.Thirdly, we use several memory accessing optimization methods to optimize the program according to the specific features of the program. We firstly optimize the global memory access. By using immediate assignment method in the kernel, we get 5% performance increase; by using global memory align accessing method we obtain 43.3% of the performance improvement. We also optimize local memory access by setting number of work items the multiples of 32, which lead to an 8.9% performance improvement. By using of graphics rendering pipeline hardware architecture to store the frequency used data, the program obtain 67.1% performance increase.Finally, we compare our program with the famous decryption software, John the Ripper. Our code runs 18 times faster on a NVIDIA GT200 GPU with Intel Q8230 quad-core CPU(2.3GHZ) than JtR running on the same CPU-only platform.