Keywords: CUDA, MPI, hash, audit tools, rainbow tables, brute force.

Cryptographic primitives such as block ciphers, hash functions are such an integral part of everyday computing. There are hacking and cryptanalysis techniques that allow intercepting and auditing encrypted communications with a computational cost so high that it is not a viable application in real time. Moreover, the recent use of graphics processing unit (GPU) in high-performance servers is changing this trend.

The classical way to break the hash functions is to use brute force attacks [1] that consist on generating all possible solutions until the right one is found. This implies a high computational cost for large and complex passwords. For that, it becomes necessary to find an efficient solution to this problem. This solution was found in the use of Rainbow tables [2] that is an elegant solution from hash tables [3] created by Hellman, avoiding as far as possible the large number of collisions inherited from his predecessor. The disadvantage of both techniques is that they have a very high computational cost, making infeasible their use with conventional equipment.

Although the cryptanalysis is capable of breaking the hash functions, so far, these algorithms are considered computationally expensive, because they require too much processing time for a real application.

To analyze the performance of cryptanalysis, brute force attacks and generating rainbow tables are compared in a sequential way, using threads, MPI and GPUs with CUDA.

All results have been obtained on the server MX DUAL AZServer Xenon and NVIDIA Tesla S1070. The server has two processors Dual/Quad Core Intel Xenon 2.66 GHz, 8 2Gb SDRAM and two SATA hard drives of 1TB in RAID 1. Moreover, the Tesla S1070 has four Tesla T10 processors each having a total of 960 cores of 1.44 GHz each one.

1

S. Halevi, H. Krawczyk, "Strengthening Digital Signatures via Randomized Hashing", Lecture Notes in Computer Sciences, 4117, 41-59, 2006. doi:10.1007/11818175_3

2

P. Oechslin, "Making a Faster Cryptanalytic Time-Memory Trade-Off", Lecture Notes in Computer Science, 2729, 617-630, 2003. doi:10.1007/978-3-540-45146-4_36

3

M.E. Hellman, "A Cryptanalytic Time-Memory Trade-Off", IEEE Tansactions on Information Theory, 26(4), 401-406, 1980. doi:10.1109/TIT.1980.1056220

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £85 +P&P)