A New Cryptanalytic Time/Memory/Data Trade-off Algorithm.
Sourav Mukhopadhyay, Palash Sarkar · 2006
In 1980, Hellman introduced a time/memory trade-off (TMTO) algorithm satisfying the TMTO curve T M 2 = N 2, where T is the online time, M is the memory and N is the size of the search space. Later work by Biryukov-Shamir incorporated multiple data to obtain the curve T M 2 D 2 = N 2, where D is the number of data points. In this paper, we describe a new table structure obtained by combining Hellman’s structure with a structure proposed by Oechslin. Using the new table structure, we design a new multiple data TMTO algorithm both with and without the DP method. The TMTO curve for the new algorithm is obtained to be T 3 M 7 D 8 = N 7. This curve is based on a conjecture on the number of distinct points covered by the new table. Support for the conjecture has been obtained through some emperical observations. For D> N 1/4, we show that the trade-offs obtained by our method are better than the trade-offs obtained by the BS method.