Rainbow Attack On Des With Its Gpu Implementation

DES was one of the most popular block-ciphers in the field of Information Security. DES can be implemented more easily at a reasonably low cost, comparing with the public-key ciphers. By far, there are two main attack methods, differential cryptanalysis and linear cryptanalysis, except for the exhaustive key search. However, it's difficult to collect enough plain-cipher pairs before its key became expired.In 1980, Hellman presented the first and most famous Time-Memory Tradeoff (TMTO). Concern to the analytical cost and feasibility of implementation respectively, the TMTO was more threatening than the other methods in practice. Oechslin proposed a new TMTO method (rainbow table) based on Hellman's, in 2003. It was claimed to have better performance than the original one.This thesis proposes a new implementation of Rainbow table algorithm on GPU. Utilizing the GPU's powerful SIMT capacity, the algorithm greatly improves the performance of Rainbow Chain generation by dispatching the pre-computation of Rainbow chain to each GPU thread and accelerates the execution efficiency of online attack through the newly introduced pre-computation chain. The running time of pre-computation on GPU (Tesla C1060) outperforms that on CPU (Core2 Duo 2.8GHz) by 41.2 times, that is 110m times DES encryptions per second; and the running time of online attack, 3.52 times faster. Based on the new hardware system, we obtain the 40bits keys of DES in 2.73 seconds on average with successful rate of 46% by using 1.3GB hard disk space.For fully use of limited memory, we design a new storage structure of rainbow table which is mainly by using ID instead of Start Point(SP) to provide more memory for additional chains. Regard to the occupancy problem, we propose a tighter estimate of the number of false alarms than the original Hellman's. Furthermore, our experiment shows that up to 14% increase has been gained on successful rate. Meanwhile, the added expect number of false alarms is 30% lower than the method of just lengthening the chain length.