2
$\begingroup$

I'm building a SHA-1 rainbow table to crack basic passwords (i.e. up to 10 character, 0-9,a-z), but I can't seem to calculate that golden ratio that would give me the most coverage. What ration of chain length to number of chains should be chosen?

Also is there anyway to estimate the coverage of the table? As at now, after building the table I'm using a brute-force attack to check it's coverage. It's a very inefficient way.

$\endgroup$
1
$\begingroup$

I'm building a SHA-1 rainbow table to crack basic passwords (i.e. up to 10 character, 0-9,a-z), but I can't seem to calculate that golden ratio that would give me the most coverage. What ration of chain length to number of chains should be chosen?

That choice is not really about coverage, but (mainly) about how much space you are willing to use. You should choose the number of chains based on how much space you can use, since each chain uses a constant amount independent of its length. Then you can choose the chain length to get the coverage you need or based on the amount of computational effort you can spend on creating the table.

Also is there anyway to estimate the coverage of the table?

Yes. You will find a formula for the probability of success in the seminal paper by Philippe Oechslin (pdf):

The probability of success within a single table of size $m × t$ is given by:

$$P_{table} = \Pi_{i=1}^{t} (1 - \frac{m_i}{N})$$ where $m_1 = m$ and $m_{n+1} = N (1 - e^{-\frac{m_n}{N}})$

Note that in your case you will likely not be able to generate a rainbow table with good coverage unless you invest quite a bit of effort. Your search space is larger than $35^{10} \approx 2^{51.3}$, so to get even 50% coverage you would need to compute more than $2^{50}$ hashes, taking several years of CPU time with a typical desktop CPU.

As long as your coverage is low you can get a decent approximation by assuming you have no collisions, i.e. just divide the product of chain count and chain length by the size of the search space.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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