thx Sc00bz

Hi,

This is my first post on this board. I came accross this post and found this great software and idea which is rtgendict. But I don't understand how I should calculate my rainbow chain length and rainbow chain count depending on my dictionnary size, and permutations I choose.

For example I have a 38 963 424 bytes dic file, and want caseperm,12;l337perm,12;numprefix,4;numsuffix,4

What chain length and count should I use to have 99,99% recovery chance (considering table size doesn't matter, so fastest is better)?

Regards,
Nicolas.

What is the keyspace of the table? (rtgendict will tell you when you start it with the dictionary chosen)

Perfect tables:
Chain length of 14, as many chains as there are passwords in the key space, and 5 tables. Total size is the key space times 80 bytes. If indexed it will be about 1/2 that.

Non-perfect tables:
Chain length of 14, 0.3786 times as many chains as there are passwords in the key space, and 3 tables. Total size is the key space times 18.17 bytes.

Please note that the chain length is plus or minus one. Also these tables would be useless but they fit your description of size doesn't matter and fast is good. As you can tell by the total sizes it is smaller to just have a lookup table of hashes.

You need to put some other limit on these tables like total size less than something or must take about some amount of time to calculate the password indexes to lookup at some speed.

I am a bit confused about the keyspace of the table, is it the "plain space total" number? It changes depending on the settings I choose... For example:

# rtgendict.exe ntlm dic.txt 0 14 3765980 test caseperm,12;l337perm,12;numprefix,4;numsuffix,4
hash routine: ntlm
hash length: 16
plain charset:
plain charset in hex:
plain length range: 0 - 0
plain charset name:
plain space total: 22401832368
rainbow table index: 0
reduce offset: 0


Anyway thanks Sc00bz for these numbers. Trying right now.

Nicolas.

Another question, do you mean as many chain as there are passwords in my dictionnary or as many passwords * permutations I choose (which gives me headache to calculate!)? Or is it the "plain space total" figure given by rtgendict.exe ?

Nicolas.

Yes, thats what i mean.
As you change the settings, the keyspace will naturally change.

In cryptography, an algorithm's key space refers to the set of all possible keys that can be used to initialize it. For example, if an algorithm works using a key that is a string of 10 bits, then its key space is the set of all binary strings of length 10.

To avoid adversaries from guessing the key using a brute-force attack, the key space is usually designed to be extremely large. Another desirable attribute is that the key space be flat, having no or very few weak keys.
quote from : http://en.wikipedia.org/wiki/Key_space

in short words, keyspace == number of permutasions/different "passwords" you have/it will be generated.

for eg. : word = ana, suffix = numeric,3


in this case you have : 1+10+100+1000=1111 passwords in total to be generated so :
keyspace=1111

Those numbers should not be used since it will create tables that are worthless. As I said in that post:



"As many chains as there are passwords in the key space" is the "plain space total." Right now you need some other limit to come up with good numbers for your rainbow tables: like max disk space of tables or a max time for the pre-work as stated before.

Hello everybody,

I have downloaded rtdict and am currently looking on its sourcecode trying to understand it. I have also looked on the original paper documenting rainbow tables. I have a few questions though regarding the code itself and maybe you guys could try and help with some answers:

1. Why has the reduce function been defined the way it has in the HashToIndex method? It basically takes the first 8 bytes from the has, adds a table index which is shifted by 16 bits (is this some sort of table selector so that chains across multiple tables don't get mingled?) and then it adds an offset withing the current chain. All this is then computed modulo the keyspace size. What lead to that particular choice? Wouldn't it be possible for chains to collide within the same table?

2. How does one know how many tables are needed for a particular level of certainty?

Congratulations PowerBlade for the clean code and neat implementation

H.

It's the easiest way and this is what RainbowCrack did. It is possible for chains to collide/merge within the same table this is why FRT "perfects" the tables (removing merged chains).


The are a few rainbow table calculators winrtgen, http://www.insidepro.com/rainbow.php, and this one is kinda advance and confusing.

Thanks for your quick reply.

The reason I'm asking is that I was thinking of adding a new rule besides the ones that already exists. Namely the concatenation operator between derived words. This would dramatically increase the size of the structures needed to hold keys, and I am pretty sure I'd have to change the reduce function too. I think the current version of the program is fine tuned for LM password hashes, but in the case a different has is used, say SHA, 7 characters are hardly enough. That's why I was considering a new rule for concatenating derived words.

Say that for every base_word1, apart from the space that's currently reserved for new words produced using uppercase, l33t, title, prefix, suffix operations, I also reserve space for combinations of this form (derived_word1 | derived_word2), where "|" means concatenation and derived_word2 has been produced from every other base_word2 in the dictionary using the bolded operators. So for each base_word1 I would need to reserve an extra log2(Count(Dict) * Size of space needed for words derived using bolded operators) bits in the index variable. I could use 2 uint64 variables for the index because I would obviously run out of bits if I were to use just one.

But I'm trying to figure out what a good reduce function might look like in this situation. Also it would be great if I could somehow save the state of the system so that each time the generator is started it resumes its previous execution state. But since the starting index is choosen randomly I don't think the problem of a state can even be brought up into discussion.

Any clues?

Are you trying to create a rainbow table that has a key space higher than 2^64. If so your real problem is where you're going to find the CPU/GPU/FPGA power to generate the tables and where to store them.

Ignoring the hard ones like leet perm and case perm. That leaves last case, title, number prefix, and number suffix. Good news is that those don't interfere with each other. So (number of words in dictionary) ^ 2 * 2 ^ 2 * (10 ^ (numbers prefixed) + 1) * (10 ^ (numbers suffixed) + 1) = key space. That's 2^64/(4*101*101) = words^2 so you can have 21,262,214 word in your dictionary with last case, title, and prefixes and suffixes of two digits. If you add case perm you shouldn't have last case or title since that is redundant.

Oh crazy there is a maximum of 1 million words for the rdict.

Am I the only one that thinks this looks funny? Anyways, dictionary attacks don't take very long... unless it was very, very big, soo we're just going to make a table for a hybrid dictionary? Still seems a bit wasteful...

I think that dictionary based rainbow tables is the way to go, and not GPU based rainbow table generation.

Dictionary based tables will make it possible to iterate through huge dictionaries and perform full case permutation in only a short time compared to doing the permutations all over for each time.
When thinking about the human nature, most passwords > 8 characters should be able to be cracked with a permutated dictionary attack, using the right permutation rules.
Using GPU's to generate rainbow tables will make it possible to crack passwords like WQW"#¤e43, but who would choose that password and be able to remember it?