Design and Optimized Implementation of Rainbow Table with GPU

Journal of Shanghai Jiaotong University ›› 2011, Vol. 45 ›› Issue (07): 1006-1011.

• Automation Technique, Computer Technology • Previous Articles Next Articles

Design and Optimized Implementation of Rainbow Table with GPU

JIN Quan-a, GU Da-Wu-a, ZHAO Jian-Jie-b

(a.School of Electronic, Information and Electrical Engineering； b. School of Information Security Engineering, Shanghai Jiaotong University,Shanghai 200240, China)

Received:2010-09-28 Online:2011-07-29 Published:2011-07-29

Abstract

Abstract: This paper proposed 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.8 GHz) by 41.2 times, that is 110×106 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 40 bits keys of DES in 2.73 seconds on average with successful rate of 46% by using 1.3 GB hard disk space.

Key words: graphic processing unit(GPU), time-memory tradeoff, Rainbow table, data encryption standard(DES)

CLC Number:

TP309.7

JIN Quan-a, GU Da-Wu-a, ZHAO Jian-Jie-b. Design and Optimized Implementation of Rainbow Table with GPU[J]. Journal of Shanghai Jiaotong University, 2011, 45(07): 1006-1011.

References

［1］Biham E. How to decrypt or even substitute DESencrypted messages in 228 steps［J］. Information Processing Letters, 2002, 84: 117124.

［2］Biryukov A. Some thoughts on timememorydata tradeoffs［R］. Cryptology ePrint Archive Report 2005/207, LeuvenHeverlee, Belgium: Katholieke Universiteit Leuven, 2005.

［3］Hellman M E. A cryptanalytic timememory tradeoff［J］. IEEE Transactions on Information Theory, 1980, 26: 401406.

［4］Denning D E. Cryptography and data security［M］. USA: AddisonWesley, 1982.

［5］Oechslin P. Making a faster cryptanalytic timememory tradeoff［C］// Boneh D. Advances in Cryptology  CRYPTO’03. USA: SpringerVerlag, 2003: 617630.

［6］Mentens N, Batina L, Preneel B, et al. Cracking Unix passwords using FPGA platforms［C］// Gerhard Frey(ed.). SHARCS’05, In Proceedings of the Workshop on Special Purpose Hardware for Attacking Cryptographic Systems. France: ［s.n.］, 2005.

［7］Kumar S, Paar C, Pelzl J, et al. How to break DES for 8,980［C］// Daniel J. B(ed.). SHARCS’06, In International Workshop on SpecialPurpose Hardware for Attacking Cryptographic Systems. Germany: ［s.n.］, 2006.

［8］Owens J D, Luebke D, Govindaraju N, et al. A survey of generalpurpose computation on graphics hardware［J］. Computer Graphics Forum, 2007, 26(1):80113.

［9］Che S, Boyer M, Meng J, et al. A performance study of general purpose applications on graphics processors using CUDA［J］. Journal of Parallel and Distributed Computing, 2008, 68(10):13701380.

［10］NVIDIA Corporation. CUDA Programming Guide［EB/OL］. (2010)［20100901］.http://developer.nvidia.com/cuda.

［11］OpenSSL Open Source Project. Openssl［EB/OL］. (2010)［20100901］.http://www.openssl.org.

Design and Optimized Implementation of Rainbow Table with GPU

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 0

Recommended Articles

Metrics

Comments