Rainbow table for DES with all-zero plaintext? Consider the function $F$ from $\{0,1\}^{56}$ to $\{0,1\}^{64}$, mapping the operative bits of a DES key to the ciphertext for all-zero plaintext. How could we organize a rainbow table to invert that function with high probability, low computational cost, and a reasonably-sized table that can be constructed at reasonable cost (beyond the cost of $2^{56}$ DES computations, of course)?

Is there such a table accessible online, in essence breaking DES knowing ciphertext for all-zero plaintext? It may have (had) practical cryptanalytic applications against (obsolete) protocols using single-DES and spitting ciphertext for all-zero plaintext, perhaps under some stimulus.

Credit: this question was inspired by a recent comment by Antikithira.



As a test vector:
$$F(\mathtt{00000000010001010001001100111000100101010111001101110111})=\mathtt{1101010111010100010011111111011100100000011010000011110100001101}$$
or equivalently
$$F(\mathtt{00451338957377}_{16})=\mathtt{D5D44FF720683D0D}_{16}$$
with this example corresponding to the DES key $\mathtt{0123456789ABCDEF}_{16}$.



Generalization: how do we organize a rainbow table of some easily computable, random-like function $F: \{0,1\}^m\to\{0,1\}^n$?



Addition: I'm unfamiliar with rainbow tables in general, so ideally I would like a self-contained answer that covers the basics as applied to this problem:


What parameter(s) do we use to control $\text{table size}\over\text{search effort}$, and odds of search failure if applicable?
How is the table organized?
How do we compute the table, for what expected cost?
How do we search?
Given a function $F: A \rightarrow B$ and functions $R_1, R_2, \dots, R_k:B \rightarrow A$, we can create a chain of length $k$ from a starting point $a_0$ to an end point $a_k$ using $a_i = R_i(F(a_{i-1}))$.

A rainbow table for $(F, R_1, \dots, R_k, k)$ is a collection of chains with end points $(a_0, a_k)$ organized so that searching for chains ending at $a_k$ is cheap.

We use a rainbow table to (try to) invert $F$ as follows. Given $b$, we compute $u_{11}, u_{12}, \dots, u_{1k}, u_{22}, u_{23}, \dots, u_{kk}$ using the equations $$u_{ii} = R_i(b) \qquad\text{and}\qquad u_{ij} = R_j(F(u_{i,j-1})).$$ After computing each $u_{ij}$, we check to see if there is a chain $(a_0, u_i)$ in the rainbow table. If there is, we compute $a_1, a_2, \dots, a_k$ as above and check if $F(a_j) = b$ for some $j$. If so, we have found a preimage of $b$ and we are done. Otherwise, we continue until we have checked all $u_{ij}$.

The idea is that the $R_i$ are very cheap to compute (compared to $F$), so generating a rainbow table for $(F,R_1, \dots, R_k, k)$ with $L$ entries requires storing $2L$ elements of $A$ and costs essentially $kL$ evaluations of $F$ plus the cost of organizing the table ($O(L \log L)$ or something similar?).

Each lookup costs at most roughly $k^2$ evaluations of $F$ plus the cost of $k^2$ table lookups (each $O(\log L)$ comparisons of elements of $A$ or something similar?).

The total cost for $n$ attempted inversions should be dominated by $kL + k^2n$ evaluations of $F$.

The tricky part (the part where I don't immediately know the answer) is determining fraction of elements of $A$ for which $F$ can be inverted. This is determined by the total number of distinct elements present in the chains in the rainbow table.

It would seem that if the $s$ first chains cover a fraction $\epsilon$ of $A$, then the $s+1$th chain will contain an expected $(1-\epsilon) (1-\epsilon/k)/(\epsilon/k)$ "new" elements of $A$ (or $k$ if $\epsilon/k$ is small). (The second term in the product is the expected number of iterations in the chain before it collides with a previous chain at the same index. The first term is the expected number of repetitions.)

This should mean that a rainbow table can cover a significant fraction of $A$.

When $kL$ is not too big compared to $|A|$, I would guess that the probability of inversion is close to $kL/|A|$.

If you are ok with a probability $\epsilon$ of inverting $F$ significantly smaller than $1$:


A rainbow table with parameters $k$ and $L = \epsilon |A|/k$ inverts $n \epsilon$ elements using $\epsilon |A| + k^2n$ evaluations of $F$ and storage of $2\epsilon |A|/k$ elements of $A$.
A straight-forward table for a fraction $\epsilon$ of the elements of $A$ inverts $n\epsilon$ elements using $\epsilon |A|$ evaluations of $F$ and storage of $\epsilon |A|$ elements of $A$ and $B$.
A sequence of brute force searches for a fraction $\epsilon$ of the elements of $A$ inverts $n\epsilon$ elements using $\epsilon |A|$ evaluations of $F$ and negligible storage.


Suppose you have $n=2^{10}$ target keys and have $2^{40}$ octets of fast memory available for the table. A pair of DES keys requires 14 bytes, which gives us $L \approx 2^{36}$. Choosing $\epsilon = 2^{-10}$, we find that $k=2^{-10} \cdot 2^{56} / 2^{36} = 2^{10}$, which means a total work factor of $2^{46} + 2^{30}$ DES evaluations. (If you use slow memory, memory access time will probably be much higher than DES evaluation time.)