Design and Implementation of Fast and Cost-Effective FPGA-Based Fuzzy Rainbow Tradeoffs

Time/memory tradeoffs are techniques used in cryptanalysis to trade increased memory usage with decreased computation time. We consider the fuzzy-rainbow tradeoff, a powerful technique used in 2010 to attack the GSM A5/1 cipher. We extend the focus from the simple model that considers only the main memory usage, to a new, more realistic one that also includes the hierarchical (external) storage. Moreover, as far as we know, existing solutions are only theoretical and do not consider the performance level of real systems. 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 6000€. We finally discuss possible refinements to the model and to the hardware design that could be helpful in practice.