Analyses of the Perfect Distinguished Point Tradeoff and Its Parallel Treatment

Abstract

In a recent paper, the performances of three major time memory tradeoff algorithms, namely, the classical Hellman tradeoff and the non-perfect table versions of the distinguished point(DP) and the rainbow table tradeoff methods, were analyzed and compared against each other. The analysis was accurate in the sense that the extra costs of resolving false alarms were not ignored, and the performance comparison was fair in the sense that both the online complexity and the pre-computation cost were taken into account and the techniques for optimizing storage size were taken into account. Based on this paper, another recent paper analyzed a DP variant, which treats the non-perfect DP tables in parallel, and compared its performance with those of the previous three tradeoff algorithms. In this thesis, we analyze the performances of three more tradeoff algorithms and compare them with the aforementioned four algorithms. The algorithms newly considered here will be the perfect table versions of the DP, rainbow table, and parallel DP tradeoff methods.

The performance of an algorithm cannot be represented by a single numeric value and algorithm preferences will depend on the available resources and various situations faced by the tradeoff algorithm implementer. Hence, we will present the performances of the tradeoff algorithms as curves providing the full range of options made available by the algorithms, so as to allow for the implementers to make their choices. However, our comparisons show that, under typical situations, the perfect table parallel DP tradeoff algorithm is more likely to be preferable over the other DP algorithm variants and that the perfect rainbow table method is superior to the other tradeoff algorithms.

On the other hand, yet another recent paper notes that the perfect rainbow table method is widely implemented in practice to process its pre-computation tables in a serial manner, rather than in parallel, as was originally proposed by the algorithm designers. This is because, even though the parallel treatment of the pre-computation tables would be more efficient in theory, the size of tables are too large to be fully loaded into fast main memory in real-world applications such as password recovery and this affects the real-world performances of the algorithms negatively. Following the approach of the paper, we give the optimal physical wall-clock online execution times for the practically used serial perfect rainbow and the perfect table versions of the DP and rainbow tradeoffs that treat their pre-computation tables in parallel. This is done with various realistic password spaces and at various high success rate requirements, under a specific limitation on the size of available storage. Unlike any theoretical approach to the tradeoff algorithms, the physical online execution time includes the time taken for loading the pre-computation tables from disk to fast memory and the time taken by table lookups.

We find that, in contrast with the software developers' intuition, the serial perfect rainbow tradeoff algorithm is inferior to the two algorithms that treat their tables in parallel, when their optimal physical online times are compared under reasonable assumptions and settings. Our simplified conclusions are that, for the larger of the two search spaces we dealt with, the parallel version of the perfect rainbow table method gives the shortest wall-clock online time, and that, for the smaller search space, when restricted to the same amount of pre-computation, the perfect parallel DP tradeoff is faster than the other algorithms.