Understanding Hash Tables and rainbow tables

Question

So I'm trying to better understand hash tables and rainbow tables and in my reading I feel like i'm starting to get the hang of it. There's a check your knowledge question that goes about like this:

"If you have a hash table storing sha-256 passwords and you want the entire table to be stored in memory and you have 4GB of memory, how many passwords can you crack? If you use a Rainbow table with 20 passwords in each chain, how many passwords can you crack?(assuming that passwords are 10 characters)"

This one totally made me question if I knew anything about what I had been reading. So this is what I came up with so far.

If every ShA-256 hash is always 256 bits in size and we know that a single megabyte has 8388608 bits in it that equals 32768 SHA-256 passwords per meg. 4000 megs, so we take the 32768 and multiply by 4000 and come up with 131072000 passwords stored in memory.

But how do I apply that to 20 chain passwords in a rainbow table? I thought a rainbow table stored hashes and the reverse of them so that while it took up more space it could resolve a lot faster. Is there a formula or something for determining how much space I lose and thus how many passwords I lose?

Any help or knowledge is much appreciated. I thank you for your time and wisdom. :)

Answer 1

imagine a rainbowtable like this:

a table is a list of chains

a chain is a password and a hash

but wait ... lets call this password P1 and the hash in the chain we call He

let's further say we have some hash function h(x) and some reduction function R(x) which will assign an output of h(x) to an arbitrary but evenly distributed password in our keyspace

if you have a chainlength of 20 that simply says this:

take P1 ... calculate H1=h(P1)
caluclate P2 as R(h1) ... calculate H2 as h(P2)
calculate Pn as R(hn-1) ... calculate Hn as h(Pn)
until after 20 steps we habe P20 and H20 ... which is also He

now we store P1 and He ... aka P1 and H20

this is a chain

a table consists of a list ... a sorted list of chains ... sorted by the hash if you have some hash x to be cracked, do this:

assign y = x
look for y in your table
if found, take the password of the corresponding chain, and rebuild all password/hash tuples that once formed the chain and look for your password ...
if not found, assign y = h(R(y)) and start over until you either get a match, or reach the chain length

so... in terms of your initial question ...

if you use a plain dictionary to lookup passwords, you need to store pairs of passwords and hashes ...one password for each hash ... one pair/tuple will bring you the ability to attack one password

if you use a rainbow table, you will still be storing one password per hash you have in memory... but the time memory tradeoff will allow you to attack many more hashes... in an ideal world that would be a multiplier of your chain length ... in a real world, that depends on how good R() is ... collisions may occur, which will lead to one password/hash being present in more than one chain, introducing redundancy to your rainbowtable

Answer 2

With rainbow tables, you only store a fraction of the hashes that you are able to crack. Hahses are organized in chains and only the first and the last element of the chain need to be stored. So with a chain length of 20, you will be storing 2 hashes per chain and be able to crack 20 hashes. You thus have a gain of a factor 10.

So whatever result you had without rainbow tables (131072000) you multiply by 10 and get the number of passwords you would be able to crack if you used rainbow tables with a chain length of 20.

Actually the chains are made of hashes and passwords in alternation. So you could chose to store the beginning and the end of the chains as password and not hashes. Since the password space if definitely smaller than the hash space, you can store the beginning and the end of each chain a as a compressed form of the password and gain some memory to be able to store even more chains.