An instant NT password cracker

While searchin the net for some information on hash algorithms i came accross a paper by Dr Philippe Oechslin titled Advances in Time-Memory Trade-Offs claimed to crack the hash passwords in matter of seconds albeit at a cost of large hard disk space.
This is what he had to say.

While a traditional brute force cracker try all possible plaintexts one by one in cracking time, RainbowCrack works in another way. It precompute all possible plaintext - ciphertext pairs in advance and store them in the file so called "rainbow table". It may take a long time to precompute the tables, but once the one time precomputation is finished, you will always be able to crack the ciphertext covered by the rainbow tables in seconds.

The site is http://www.antsight.com/zsl/rainbowcrack/.

I feel this could have far reaching consequences in cracking. how about trying this strategy out on a crypto crackme. any ideas or any contribution.

I've heard of people using this approach before for NTLM password hashes - usually they can store all the precalculated hashes on a CD. Precaluclation isn't all that new of an idea in the codebreaking world, but the fact that it can be done so easily on NTLM underscores how weak that system is. This type of attack is only useful because of the small keyspace for NTLM. NTLMv2 increased it to 128 bits, which still isn't really strong encryption by most modern standards, but it at least ups the ante when it comes to how much space it takes to store precalculated hashes.

At some point this approach becomes downright impossible. RSA is a great example. There's a powerpoint lecture on this at hxxp://www.cs.uno.edu/~golden/4621sl2/4621sl2.ppt, but powerpoint slides piss me off. Feel free to use google's HTML translation of it instead. To paraphrase:

Assuming you even had the computing power to precaluclate the factors of all 200 digit numbers, you would need approximately (9 * 10^200) * 665 bits to store them all. If you had some kind of medium that could store 100GB of data in one millionth of a gram, you would have 6.75 * 10^177 tons of storage. The Chandrasekhar limit is approximately 10^27 tons. Ergo your precalculated tables would collapse into a black hole long before you got the chance to use them

Edit: Crikey, my spelling and typing goes to hell after midnight!

Yeah, I am aware of the file sizes that one would have to encounter and this link that i had mentioed earlier, has plugins for various other hash algorithm too.

Also the precomputation time is just too large. even for a seven character alphanumeric password is 200+ days and file size of around 20gb.

But what i wanted to ask is that, is it worth the effort for even 7 char password. the reason why i am asking this is that often people have observed collisions in these hash algorithms (reference hxxp://www.cryptool.de/). Keeping these too in mind, would it be helpful while patching codes, in which the files itself are checked for modifications while using these algorithms, like it was done for crc ?

a seven character password would be pie to bruteforce, on my machine it takes about 30min with alpha-num. Getting up into 8+ is where it gets long tho.
I think you should recheck your information, because here is a person that has actually accomplished it and you can submit ones for cracking :
http://sarcaprj.wayreth.eu.org/
his NTLM hashes use upper/lower alpha-num-15 symbols and are only 18gb (and for sale!)

How big are these tables?
There are 30 files, each one is 640MB. A total of 18750MB.

How much time was spent for the creation of these tables?
On my AMD 2000+ with 512MB of RAM we spent 3 days for each file.

so about 3 months, not 200 days

I really wish someone would overhaul the rainbow crack app, like adding more algorithms, compression, and optimizations.

No such thing as 8 char passwords in NT. They are divided into two 7 char parts, which will be cracked individually.

but dont Rainbow crack also offer plugins from MD2, MD4 and RIPEMD160 in addition to NTLM.

Maybe we could have a independant developement for more hash algorithms.