A Fast and Cost-effective Design for FPGA-based Fuzzy Rainbow Tradeoffs

Time/memory tradeoffs are general techniques used in cryptanalysis that aim at reducing the computational effort in exchange for a higher memory usage. Among these techniques, one of the most modern algorithms is the fuzzy-rainbow tradeoff, which has notably been used in 2010 to attack the GSM A5/1 cipher. Most of the existing analyses of tradeoff algorithms only take into account the main-memory model, which does not reflect the hierarchical (external) storage model of real world systems. Moreover, to the best of our knowledge, there are no publicly available implementations or designs that show the performance level that can be achieved with modern off-the-shelf hardware. In this paper, we propose a reference hardware and software design for the cryptanalysis of ciphers and one-way functions based on FPGAs, SSDs and the fuzzy rainbow tradeoff algorithm. We evaluate the performance of our design by extending an existing analytical model to account for the actual storage hierarchy, and we estimate an attack time for DES and A5/1 ciphers of less than one second, demonstrating that these ciphers can be cracked in real-time with a budget under 6000e.