Finux Student Hackers Guide to Rainbow Tables

Finux Student Hackers Guide to Linux

Well hi guys, and welcome to another Finux's Student Hackers Guide to Linux.  My name is Arron, But as usual you guys can call me finux.

You can find the HPR episode that goes along with these show notes from http://hackerpublicradio.org/eps/hpr0215.mp3 and there is also some slides you can download from a talk i did recently on this here http://thelinuxsociety.org.uk/content/rainbow-tables-slides-from-talk

This month i want to look at Rainbow tables, and how they can be used to crack windows LM Hashes, however this is just an appetiser and i'll also be talking about how they can be used to crack other types of hashes.

Now this isn't going to be a very technical episode, i really just hope that this will raise awareness about decent password security, and show that if you don't use a decent password policy then you could well be on the receiving end of attacks like this, as usual i will also discuss possible countermeasures to this as well.

As usual my podcasts and tutorials are for educational purposes only and are not designed to be used by you to hack someone.  If you steal someones hash, and use this technology you will be breaking the law, and you could be facing a stint in the jail.

I recently gave a talk on this subject at the University of Abertay Linux Society and it went down very well in deed, i know of a few people who went home ad changed their passwords on the strength of my talk, so lets cut to the chase and get started.

I'm going to take it that you haven't heard of rainbow tables before, however i know a few people listening will be, i think its important to give  a quick crash course in everything that i'm going to be talking about today.  We'll start by some terminology.  Now i warn you guys, terminology has never been my strong suit and neither has mathematics.  This episode is just designed to wet your teeth and if you want to find out more i will supply all the urls i came across making this episode, the show note will as always be on the Linux Society website, and of course as i will also post them over at our good friend the Linux Basement.

So lets start, i suppose the logical place to start is what do i actually mean when i say hash.

Well in the context that i'm using it i'm referring the a unique identifier.  If you think about how a computer stores its passwords it should keep them on system in a form that a user can read, the reason for this is what is to stop your work pall from looking your password on and logging on as you.

Well what happens in most OS's is that your password is put through a hash function, the benefit of a hash function is it irreversible.  You put one thing in one end and you get something else out the other end.  Perfect for passwords.  The system holds the hash and the when you input your password it is place though the same hash function and if the two hashes match then in you go, if they don't then you guessed it your kept out.

The next thing is a reduction function, now in reality this is a very strange subject, but it does lie at the heart of rainbow tables.  What in reality a reduction function is, is a process that changes a problem in to another problem.  The theory is you take a complex problem and you change it in to a simple problem.  The reason being that you may find it hard to solve the complex problem, but you may find it easier to solve a simple problem, but as i say understanding this is not pinnacle to today's episode.

Lookup table is also another term that i may use in today's episode.  In really is just what it says, its a table with precomputed answers that can be used to find a solution.

Here is another term i may use that and this is where the whole concept of rainbow tables holds its true value, Time Memory Trade Off.  This is basically a process of trading one asset off against another.  So if you have lot's of time but not much space or memory, or if you have plenty of time, but limited memory you could use this concept to set up a process that benefits you.  I'm sure i have done a pretty naff job of explain this but it will make a lot more sense later on.

Okay this part i always enjoy talking about and this is how do you take a secure password and make it as insecure as possible, or otherwise known as LanManger Hashes.  This process was designed by Microsoft, and they lead the way for some real life cryptographers to try some theory's out in the real world.

Basically how Windows systems, apart from Vista make their password hash is pretty simple.  Firstly if you enter a password the process is to capitalise each character, then if the password is longer then 7 characters long split it into two.  So if it was 10 characters long then it would be put in to one piece containing 7 and the other piece containing 3, the rest of the space would be filled with blank space.  Hash both parts individually and then call it a Lan Manger Hash.

Now time for the dissection of this.  Firstly by capitalising the password you cut the possibilities down by a factor of 26, a hash of the word PASSWORD in capitals is different to the word password hashed in lower case.  so you go from a total of 95 in the character set of only 69. 

The by splitting into two pieces, the following consequences happen.

Both pieces can be attacked independently, and the possible combinations are cut dramatically down.  So if we take something with the possibility of being 7 characters long and being of a character set of 69, in other words 69^7 it would give you about 7 trillion possible combinations, compared to 69^14 which would give you about 55 septillion possibilities, pretty much unimaginable figures, of course if you where to use the full 95 character set available on most keyboards then your really talking about numbers.  So you see it doesn't matter how long the password is when the LM hash is applied, your only ever cracking a 7 character password

As i have said for backward compatibility this was used for nearly all Windows OS until Vista, and in Vista it is turned off by default but can still be turned on.  You can also turn it off in XP, but it is on as default.  It has been replaced by the NTLM hash.  Which doesn't capitalise everything, and doesn't spilt it into two.

So i imagine your thinking that 7 trillion possible outcomes is still a pretty big number, and you would be right.  If we built a table of 7 trillion possible password combinations, and the each output from that was about 21 bytes, then you would need over a 140 thousand, gigabytes of space to hold it.

This is where the term Time-Memory Trade Off comes into fruition.  It is possible to make a lookup table that doesn't hold all the actual combinations but rather how all the possible combinations can be made, sort of like a chain.  You compute, all the combinations in to a chain, then cut the middle out of it.  It sounds a little crazy, but if we go back to the reduction function that i spoke earlier on then it may start to make sense.

Take a plaintext password, hash it, then use a reduction function to change it into another plain text password and hash it again, keep on doing this for seven time, until your left with a chain of seven hashes, and a number of plaintext passwords.  Then we delete everything apart from the first plain text password and the final hash. 

When we come to decrypting the hash we then check the last part of the chain (the hash) if it isn't in the end of the chain then we start checking the second from last part of the chain, and we keep on going till we find the correct plain text that matches the hash we're trying to decrypt.

for a further explanation of this visit http://kestas.kuliukas.com/RainbowTables/ of how the tables are generated, and probably the best explanation i have seen on reduction function in the context of rainbow tables.

The package that i used for decrypting LanManger Hashes was Ophcrack, and it was a simple as enabling the restricted repositories in Ubuntu, and using sudo aptitude install ophcrack, for download and install instructions for your OS then this you can visit the Ophcrack website http://ophcrack.sourceforge.net/

They also have a number of precomputed rainbow tables.  They also have a liveCD that you can boot from on the system that your trying to crack the password of, and boot from that.  I haven't used it for a number of years however as far as i remember it does pretty much all the hard work for you, locating the SAM file is pretty simple.

You can locate the hashes on a windows system from this location c:\windows\system32\config\sam (windows dir may vary), there is an explanation of how you can obtain LanManger Hashes from this web site, http://www.irongeek.com/i.php?page=security/cracking-windows-vista-xp-20...

The more memory your system has the faster the decrypting process is.  As more of the tables can be loaded in the RAM, you can in actual cut the amount of time by half if you double the RAM available.

However Rainbow tables generated for one type of hashes can't be used on other types of hashes, such as NTLM if your using LM rainbow tables.   Also if you have tables generate for 4-7 characters and the password is only 3 characters long it will not work also.  However there could be an argument for making that, if you take an average length of a password and only generate tables for that size you could down the physical space required and the memory taken and the actual time it takes to search the rainbow chain.  Especially now that we have an abundance of password policy information out there, how many organisations employ password policies that say your password has to be a minimum of at least 6 charters.  In some situations your tables are no going to be effective, however if you've custom built your tables for you bespoke situations then they could come in very handy in deed.

Rainbow Tables can also be used against WPA-PSK however they are not as vulnerable as you would think, the hashes are compiles against the actual ESSID of the wireless router, it is what we could call a salt.  A salt is a unique identify for the system that the hash was generated on, and Unix and Linux system have been using this process for quite some time.  In fact nearly all OS have been using a salt with their hashes, Microsoft was one of the only big OS developers not to employ a salt with their hash system.

If we go back to the rainbow tables for WPA-PSK this sort of explains salts nicely as a by process of , but it does highlight the importance of making sure your salt is unique.  WPA_PSK rainbow tables have a list of the top 1000 ESSID's each ESSID is a seperate hashing process, so the size of the tables become about 500GB and as long as your ESSID is not in that list your pretty safe against this attack.  I imagine in the list it will have thinks like Belkin54g, and ESSID's like ThisHome, MyWirelessNetwork.

I have heard people discussing how they may be away of deploying a dynamic hash, which would be in layman terms a salt that changes per user, making it damn near impossible to ever generate any tables for.  I think that this would be a very interesting thing to deploy however i also believe that the defaults set up by your Unix-Type OS's are more than sufficient for now.

Links

http://ophcrack.sourceforge.net/
http://www.objectif-securite.ch/en/products.php
http://www.antsight.com/zsl/rainbowcrack/
http://kestas.kuliukas.com/RainbowTables/
http://versatile1.wordpress.com/2007/04/16/rainbow-tabels/
http://www.ethicalhacker.net/content/view/94/24/
http://www.thehackerslibrary.com/?p=38
http://elliottback.com/wp/cracking-windows-passwords-with-ophcrack-and-r...
http://www.renderlab.net/projects/WPA-tables/
http://www.darknet.org.uk/2006/02/password-cracking-with-rainbowcrack-an...
http://lasecwww.epfl.ch/php_code/publications/search.php?ref=Oech03
http://en.wikipedia.org/wiki/RainbowCrack
http://en.wikipedia.org/wiki/Salt_(cryptography)
https://www.isc2.org/cgi-bin/content.cgi?page=738
http://www.freerainbowtables.com/faq/
http://altblog.searix.net/index.php/2007/10/17/rainbow_tables
http://lwn.net/Articles/208418/
http://lastbit.com/smartrecovery.asp
http://www.techstructions.com/?p=13
http://en.wikipedia.org/wiki/Hash_function
http://www.security.ku.edu/docs/doc-viewer.jsp?id=31
http://www.lmcrack.com/
http://ubuntuforums.org/archive/index.php/t-909946.html

www.thelinuxsociety.org.uk/blogs/finux
www.linuxbasement.com