## 2 Related Work
### Parallel Computing Methods for Rainbow Tables Generation  
The problem of rainbow tables generation has been discussed several times in the scientific literature. Various authors proposed different methods utilizing different technologies to optimize the generation process of those tables. Most papers propose utilizing parallel computing to achieve this goal. Some solutions utilize the parallelization capabilities on the GPU. [PERSON] et al. [31] proposed an implementation of high-speed rainbow table generation with the integrated development environment CUDA for GPU in the heterogeneous GPU + CPU system to crack passwords that were hashed with the Keccak-512 hashing algorithm. The process is rather simple, and it is split into CPU tasks and GPU tasks. Most of the work is done on the GPU, where each starting point from the CPU is processed in its own thread to generate a rainbow chain, and a corresponding end point is returned to the CPU. All starting and end points are written to a file at the end of the process. The results show that the rainbow table generation time is approximately 70 times faster than using the CPU alone with a chain length of 50. When the rainbow chain is longer, the speedup increases. [PERSON] et al. [32] proposed another implementation on the GPU using CUDA. They considered warp serialization, which is a concern for performance on the GPU. In addition, they used checkpoints for load balancing between the CPU and the GPU, which helped in the performance improvement. The implementation was executed on two different Nvidia GPUs and compared against equivalent implementations from RainbowCrack and Cryptohaze. In both cases, the author's implementation performed better. The experimental results show that on the GTX460 model, the implementation runs about 1.86 and 3.25 times faster than RainbowCrack and Cryptohaze, respectively, and on the GTX580 model, it runs 1.53 and 2.40 times faster. [PERSON] et al. [33] proposed another approach using CUDA on the GPU for high-speed perfect rainbow table generation. Their approach also includes a table storage optimization method, which reduces memory space to 57.1% compared to the tools from Cryptohaze. To parallelize the rainbow table generation, the authors employed a dynamic task scheduling strategy on a heterogeneous multi-device architecture consisting of CPU and GPUs. The entire precomputation task is evenly split into many smaller subtasks, which are then maintained in a task queue and managed by a thread pool. When a computing device (CPU or GPU) becomes idle, it continuously fetches and executes a new subtask from the task queue until the queue is empty. It can achieve 2.03\(\times\) and 131.3\(\times\) speedup compared to other tools like Cryptohaze and RainbowCrack, respectively. Alternative methods for generating rainbow tables are based on the use of field-programmable gate arrays (FPGAs), offering greater efficiency and high speedup. The research on the use of FPGAs for this purpose shows impressive results. One such research was conducted by [PERSON] et al. [34] and aimed at generating rainbow tables for breaking the A5/1 stream cipher; it achieved an improvement of up to 3000 times compared to the same implementation on a personal computer with standard GPU. Another research was conducted by [PERSON] et al. [35] and intended to break the A5/3 stream cipher using rainbow tables that were generated on FPGAs using 64 computing machines. The speedup was up to 550 times faster compared to CPUs available at the time. [PERSON] et al. [36] presented a different hardware system, which was implemented on a Xilinx XCV5 VLX330T FPGA chip on a HitechGlobal card targeting the LM, SHA-1 and MD5 cryptographic hash functions. This system can generate rainbow tables up to 1000 times faster than a 2010 PC. [PERSON] and [PERSON] [37] and [PERSON] [10] both used the MPI standard to perform the rainbow table generation in parallel.