# 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?
-
See page 6. $\;$ –  Ricky Demer Jul 24 at 8:50

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.)

-
eprint.iacr.org/2005/207 $\:$ eprint.iacr.org/2006/127 $\;\;\;\;$ –  Ricky Demer Jul 24 at 9:41
You are considering $k$ chains of length $k$; why are these parameters taken to be the same? Is it next to optimum? $\;$ Also: is the distinguished point technique useful with rainbow tables? –  fgrieu Jul 31 at 14:17
No, $L$ chains of length $k$; checking if we are in a chain requires computing $k$ sequences of average length $k/2$. –  K.G. Jul 31 at 14:42

It seems to me you can do everything as when calculating a rainbow table for a hash function, except that choosing a good reduction function is very easy.

For example, define a chain starting from $k$ as: $$c_k(0) = T(E_k(0))$$ $$c_k(i) = T(E_{c_k(i-1) \oplus i}(0)),$$

where $T$ truncates its input to 56 bits.

Now you can create a rainbow table with $n$ chains of length $l$ that start from different values $k$, just like you would for e.g. a password hash. Any optimizations that apply there, like skipping merged chains, should also apply here.

I don't know if there are such tables for DES proper (there are for DES-Crypt), but there apparently are for A5/1 (a stream cipher used in GSM), which has a similar keyspace – $2^{64}$ keys which some weaknesses in the cipher in effect reduce by a few bits. So it should be completely doable for DES as well.

-
In addition of things I do not grasp with rainbow tables (see updated question): why the $\oplus i$ term? –  fgrieu Jul 28 at 14:51
It prevents the hash chains from merging due to collisions anywhere but in the same position (much less likely). I believe it's what "rainbow" is supposed to signify in the name. –  otus Jul 28 at 14:55
@fgrieu, also, I'm not sure if it's worth it to explain rainbow tables in detail here, when the answers to this question do it quite well. –  otus Jul 28 at 15:13

One simple approach is to truncate the output to 56 bits.

I believe this was considered in Hellman's original paper on time-space tradeoffs. Sometimes people get all excited by rainbow tables (partly because it has a cool name, maybe) but forget about Hellman's original paper on the time-space attack. Hellman's paper is very much worth reading, especially if you care about applying it to DES, as this an application he explicitly considered in his paper.

-
M. E. Hellman, A Cryptanalytic Time-Memory Tradeoff, IEEE Trans. on Info. Theory, Vol. 26, July 1980, pp. 401-406. $\;$ At least that one is relatively straightforward! It does not use what otus's answer and comment describes as the rainbow improvement, and I wonder how much that improves the time-memory tradeoff. –  fgrieu Jul 29 at 2:25
I read there are two canonical improvements to that: $\;$ 1) Rivest's distinguished points, iterating encrypt-then-truncate starting from a point in some subset of the keyspace (e.g. with some 16 bits at zero) until reaching such subset, for a modest but welcome reduction in memory requirement; and $\;$ 2) rainbow tables, which seem to originate in: Philippe Oechslin's Making a Faster Cryptanalytic Time-Memory Trade-Off, in proceedings of Crypto 2003. –  fgrieu Jul 29 at 3:23