Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

3 Answers 3

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

share|improve this answer
2  
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
1  
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.

share|improve this answer
    
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
1  
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
3  
@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.

share|improve this answer
1  
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.