Friday, March 19, 2010

Faster Rainbow Tables

It was announced last month by Objectif Sécurité that Ophcrack, the open source framework for breaking Windows password hashes, has passed 10 million downloads. Objectif Sécurité is a Swiss security consultancy founded by Philippe Oechslin, the inventor of rainbow tables. One of the products offered by Objectif Sécurité is a collection of larger and more specialized rainbow tables to extend the base table distributed with Ophcrack. The set of available table options is shown below



These are the professional tables and sell for $999, and see the site for the definition of the character sets covered. The basic tables included with the Ophcrack distribution are derived from a set of dictionary words. To celebrate the Ophcrack milestone,
Oechslin has also given free on-line access to a large rainbow table representing the LAN Manager hashes of passwords made of 52 mixed case letters, 10 numbers and 33 special characters and up to length 14. He estimates that the time to crack most such Windows passwords is less than 6 seconds. This fast password recovery is approximately 100 times faster than previous methods and is supported by hosting 90GB tables on an SSD device. Memory usage is intense for rainbow tables as described here.

Oechslin has reported to Heise Security that for tougher, better selected passwords, the entire password space can be searched at a rate of 300 billion passwords per second. Please take a look at the password recovery speeds at LockDown.uk to understand what this innovation means. For example, passwords of length 8 consisting of only upper and lower case letters can be cracked in 2 days, and only 9 days if digits are present in the password.

Update March 21st

Matt Weir has made some excellent points in his comment below, and clarified several of the statements about the 300 billion password per second search rate. I corrected the link to Oechslin’s remarks reported in Heise Security, and though not stated explicitly it seems that this tremendously fast password search rate applies only to the now-obsolete LAN Manager hashing scheme. Please read Matt’s comment as an improvement/correction for the final text above. Thank you very much Matt.

3 comments:

Matt Weir said...

Unless I'm looking at the wrong link, the tables being referenced, aka:

"The demo cracks passwords made of 52 mixed case letters, 10 numbers and 33 special characters of length up to 14 (XP special tables on steroids)."

only deal with LanMan hashes. Due to flaws in the hashing algorithm, that means the LanMan rainbow tables only need to deal with uppercase letters and two seven character long hashes/passwords. While the speed is impressive, (normally it can take a couple of minutes to perform a lookup), it's nothing new. Aka similar tables have been available to the public for years, (see the Shmoo tables from Shmoocon2005). After a password is cracked, it then combines the two hashes together and runs different capitalization permutations to figure out the original user's password, (this is only possible if you submit the NTLM hash as well).

The vista, (aka NTLM), tables are much more interesting since they provide a better understanding of which Vista/Win7 passwords will be cracked by existing rainbow tables. This is because the LanMan hash is no longer enabled by default in all Vista and later systems.

As far as I can tell the 300billion per second number refers to the lookup speed of a pre-computed table. Aka the generation time of the original table would be much, much longer. That's why we only see tables for MixedAlphaNum NTLM hashes up to eight characters long. If you could create the table at 300billion guesses a second, it would take around 12 minutes to cover that keyspace.

That's not to say a dedicated, (and really expensive), FPGA based password cracker couldn't reach speeds such as that for weak hashes like NTLM. To put this in perspective though, distributed.net cracking RC5-72 using on average 2,600 computers can make around 150 billion guesses a second.

I apologize if the above sound nit-picky. I liked your post, (which is why I'm taking time to comment on it). I just wanted to point out some of the limits that still exist.

Dr. Luke O'Connor said...

Matt, nice to hear from you and your comments are excellent. I will adjust the text highlight that the online service is for LANMAN hashes, and then refer readers to your comment - I could not write better text. Thanks

rgs Luke

boy labyog said...

Vista 9 is the leading bu why it not more popular?




Laby[wedding suit]