Parallelization of Rainbow Tables Generation Using Message Passing Interface: A Study on NTLMv2, MD5, SHA-256 and SHA-512 Cryptographic Hash Functions - Mark Vainer; Arnas Kačeniauskas; Nikolaj Goranin (Applied Sciences)
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.