Parallelization of Rainbow Tables Generation Using Message Passing Interface: A Study on NTLMv2, MD5, SHA-256 and SHA-512 Cryptographic Hash Functions
Source abstract
Abstract
Rainbow table attacks utilize a time-memory trade-off to efficiently crack passwords by employing precomputed tables containing chains of passwords and hash values. Generating these tables is computationally intensive, and several researchers have proposed utilizing parallel computing to speed up the generation process. This paper introduces a modification to the traditional master-slave parallelization model using the MPI framework, where, unlike previous approaches, the generation of starting points is decentralized, allowing each process to generate its own tasks independently. This design is proposed to reduce communication overhead and improve the efficiency of rainbow table generation. We reduced the number of inter-process communications by letting each process generate chains independently. We conducted three experiments to evaluate the performance of the parallel rainbow tables generation algorithm for four cryptographic hash functions: NTLMv2, MD5, SHA-256 and SHA-512. The first experiment assessed parallel performance, showing near-linear speedup and 95–99% efficiency across varying numbers of nodes. The second experiment evaluated scalability by increasing the number of processed chains from 100 to 100,000, revealing that higher workloads significantly impacted execution time, with SHA-512 being the most computationally intensive. The third experiment evaluated the effect of chain length on execution time, confirming that longer chains increase computational cost, with SHA-512 consistently requiring the most resources. The proposed approach offers an efficient and practical solution to the computational challenges of rainbow tables generation. The findings of this research can benefit key stakeholders, including cybersecurity professionals, ethical hackers, digital forensics experts and researchers in cryptography, by providing an efficient method for generating rainbow tables to analyze password security.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Chaos-based Image/Signal Encryption · Cryptographic Implementations and Security · Advanced Malware Detection Techniques
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Graphical Systems, Faculty of Fundamental Sciences, Vilnius Gediminas Technical University, LT-10223 Vilnius, Lithuania
Department of Information Systems, Faculty of Fundamental Sciences, Vilnius Gediminas Technical University, LT-10223 Vilnius, Lithuania
References (42)
Show source-provided references
1. Bonneau, J., Herley, C., Van Oorschot, P.C., and Stajano, F. (2012, January 20–23). The Quest to Replace Passwords: A Framework for Comparative Evaluation of Web Authentication Schemes. Proceedings of the IEEE Symposium on Security and Privacy, San Francisco, CA, USA.10.1109/SP.2012.44 ↗
2. Menezes, A.J., Vanstone, S.A., and Van Oorschot, P.C. (1996). Handbook of Applied Cryptography, CRC Press, Inc.. [1st ed.].
3. Analysis of the Use of Rainbow Tables to Break Hash
4. Bosnjak, L., Sres, J., and Brumen, B. (2018, January 21–25). Brute-Force and Dictionary Attack on Hashed Real-World Passwords. Proceedings of the 2018 41st International Convention on Information and Communication Technology, Electronics and Microelectronics, MIPRO 2018—Proceedings, Opatija, Croatia.10.23919/MIPRO.2018.8400211 ↗
5. A Theory of Dictionary Attacks and Its Complexity
6. Making a Faster Cryptanalytic Time-Memory Trade-Off10.1007/978-3-540-45146-4_36 ↗
7. A Cryptanalytic Time-Memory Trade-Off10.1109/TIT.1980.1056220 ↗
8. Parallel FEM Software for CFD Problems10.15388/Informatica.2004.066 ↗
9. Computation and Visualization of Discrete Particle Systems on GLite-Based Grid10.1016/j.advengsoft.2011.02.007 ↗
10. Using Parallel Computing to Implement Security Attack
11. What Is the Effectiveness of Salt and Pepper in Preventing Rainbow Table Attacks in Modern Password Hashing Algorithms?10.38124/ijisrt/IJISRT24SEP406 ↗
12. Fosaaen, K. (2025, June 24). LM Hash Cracking—Rainbow Tables vs GPU Brute Force. Available online: https://www.netspi.com/blog/technical-blog/network-pentesting/lm-hash-cracking-rainbow-tables-vs-gpu-brute-force/.
13. Pabico, J.P. (2015). A Framework for a Multiagent-Based Scheduling of Parallel Jobs. arXiv.
14. Parallel MPI-Implementation of the Branch-and-Bound Algorithm for Optimal Selection of Production Equipment
15. Stevens, H. (2025, January 28). Hans Peter Luhn and the Birth of the Hashing Algorithm. Available online: https://spectrum.ieee.org/hans-peter-luhn-and-the-birth-of-the-hashing-algorithm.
16. Hash Functions and GPU Algorithm of Infinite Grid Method for Contact Search10.5755/j01.itc.51.1.29455 ↗
17. PSCC: Parallel Self-Collision Culling with Spatial Hashing on GPUs10.1145/3203188 ↗
18. Wang, X., Feng, D., Lai, X., and Yu, H. (2004). Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. Cryptol. ePrint Arch., 2004/199.
19. Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate10.1007/978-3-642-03356-8_4 ↗
20. Xie, T., Liu, F., and Feng, D. (2013). Fast Collision Attack on MD5. Cryptol. ePrint Arch.
21. Pre-Image Attack of the MD5 Hash Function by Proportional Logic10.51584/IJRIAS.2022.7802 ↗
22. Zhong, J., and Lai, X. (2009). Preimage Attacks on Reduced DHA-256. Cryptol. ePrint Arch., 2009/552.
23. The First Two Rounds of MD4 Are Not One-Way10.1007/3-540-69710-1_19 ↗
24. Second Preimages on N-Bit Hash Functions for Much Less than 2n Work10.1007/11426639_28 ↗
25. A Second Pre-Image Attack and a Collision Attack to Cryptographic Hash Function Lux10.1501/Commua1_0000000794 ↗
26. New Second-Preimage Attacks on Hash Functions10.1007/s00145-015-9206-4 ↗
27. Denning, D. (1982). Cryptography and Data Security, Addison-Wesley Longman Publishing Co., Inc.
28. Characterization and Improvement of Time-Memory Trade-Off Based on Perfect Tables10.1145/1380564.1380565 ↗
29. Optimal Storage for Rainbow Tables10.1007/978-3-319-12160-4_9 ↗
30. Quan, L.J., Ye, T.J., Ling, G.G., and Balachandran, V. (2024). QIris: Quantum Implementation of Rainbow Table Attacks. arXiv.10.1007/978-3-031-80020-7_12 ↗
31. Dat, T.N., Iwai, K., Matsubara, T., and Kurokawa, T. (2019, January 12–13). Implementation of High Speed Rainbow Table Generation Using Keccak Hashing Algorithm on GPU. Proceedings of the 2019 6th NAFOSTED Conference on Information and Computer Science (NICS), Hanoi, Vietnam.10.1109/NICS48868.2019.9023888 ↗
32. High-speed Parallel Implementations of the Rainbow Method Based on Perfect Tables in a Heterogeneous System10.1002/spe.2257 ↗
33. High-Speed Implementation of Rainbow Table Method on Heterogeneous Multi-Device Architecture10.1016/j.future.2023.01.022 ↗
34. Kalenderi, M., Pnevmatikatos, D., Papaefstathiou, I., and Manifavas, C. (2012, January 29–31). Breaking the GSM A5/1 Cryptography Algorithm with Rainbow Tables and High-End FPGAS. Proceedings of the 22nd International Conference on Field Programmable Logic and Applications (FPL), Oslo, Norway.10.1109/FPL.2012.6339146 ↗
35. Papantonakis, P., Pnevmatikatos, D., Papaefstathiou, I., and Manifavas, C. (2013, January 2–4). Fast, FPGA-Based Rainbow Table Creation for Attacking Encrypted Mobile Communications. Proceedings of the 2013 23rd International Conference on Field programmable Logic and Applications, Porto, Portugal.10.1109/FPL.2013.6645525 ↗
36. Theocharoulis, K., Papaefstathiou, I., and Manifavas, C. (September, January 31). Implementing Rainbow Tables in High-End FPGAs for Super-Fast Password Cracking. Proceedings of the 2010 International Conference on Field Programmable Logic and Applications, Milan, Italy.10.1109/FPL.2010.120 ↗
37. An Improved Parallel Implementation of RainbowCrack Using MPI10.1016/j.jocs.2013.10.006 ↗
38. Avoine, G., Carpent, X., and Leblanc-Albarel, D. (2023, January 10–14). Stairway to Rainbow. Proceedings of the ACM Asia Conference on Computer and Communications Security, Melbourne, VIC, Australia.10.1145/3579856.3582825 ↗
39. Avoine, G., Carpent, X., and Leblanc-Albarel, D. (2021, January 4–8). Precomputation for Rainbow Tables Has Never Been so Fast. Proceedings of the 26th European Symposium on Research in Computer Security, Darmstadt, Germany.10.1007/978-3-030-88428-4_11 ↗
40. Westergaard Jørgensen, M. (2024, November 02). Free Rainbow Tables: Distributed Rainbow Table Project. Available online: https://freerainbowtables.com/.
41. Vaideeswaran, N. (2025, June 26). NTLM Explained. Available online: https://www.crowdstrike.com/en-us/cybersecurity-101/identity-protection/windows-ntlm/.
42. Adusumilli, S. (2025, June 26). Testing a Legacy Application with Zero Documentation. Available online: https://www.cigniti.com/blog/testing-a-legacy-application-with-zero-documentation/.