Rigorous Bounds on Cryptanalytic Time/Memory Tradeoffs

In this paper we formalize a general model of cryptanalytic time/memory tradeoffs for the inversion of a random function

f

:{0,1,...,

N

–1} ↦{0,1,...,

N

–1}. The model contains all the known tradeoff techniques as special cases. It is based on a new notion of

stateful random graphs

. The evolution of a path in the stateful random graph depends on a

hidden state

such as the color in the Rainbow scheme or the table number in the classical Hellman scheme. We prove an upper bound on the number of images

y

=

f

(

x

) for which

f

can be inverted, and derive from it a lower bound on the number of hidden states. These bounds hold for an overwhelming majority of the functions

f

, and their proofs are based on a rigorous combinatorial analysis. With some additional natural assumptions on the behavior of the

online phase

of the scheme, we prove a lower bound on its worst-case time complexity

$T=\Omega(\frac{N^2}{M^2 \ln N})$

, where

M

is the memory complexity. Finally, we describe new rainbow-based time/memory/data tradeoffs, and a new method for improving the time complexity of the online phase (by a small factor) by performing a deeper analysis during preprocessing.