Rainbow Tables (RTs), Password cracking and Protection against RTs

I first learnt about these around two and a half years ago when I stumbled on one of security related sites (Can't remember). The concept looked awesome. It’s used for cracking passwords that are hashed in a fraction of time than most other techniques will allow you.

 

Before we move further let me give brief background information on password storage

 

Systems that need authentication provide a means to store the authentication tokens (User ID and password) in an authentication repository(database). These passwords are stored in following ways:

 

1. Plaintext    : Passwords are stored in plaintext in the authentication repository. Once someone has access to the repository the person can see the password without any difficulty and can use them to access the system from the front end. Obviously designers of these system haven't thought enough on security front, cared less or plainly thought that nobody would try to steal passwords for these systems (for whatsoever reason). Nevertheless it’s a real bad design considering better practices as mentioned below can be applied with very little effort.

 

2. Encrypted Passwords: Designers of these systems are conscious of their security and implement a mechanism that will encrypt the password by using either a publicly or privately available encryption mechanism. Problem with this mechanism is that all encryption algorithms have corresponding decryption algorithms and can be decrypted once the key is available to the person looking to get the passwords to the system.

 

3. Hashed Passwords (Most widely used): Unlike encryption algorithms hashing algorithms are one way functions without any corresponding de-hashing algorithms that generate a unique hash for a given input. A mathematical representation would be 

H(x) =p where no such F exists such that F (p) =x. H is the hashing function and F is the non-existent de-hashing function. The commonly used hashing algorithms in widespread use are MD5 and SHA. In general hashing algorithms generate a fixed size hash value for any given input (e.g. 128 bit for MD5, Password= 11, Hash=6512BD43D9CAA6E02C990B0A82652DCA).

 

There is no mathematical way for a strong (Attacks have been demonstrated on MD5 and SHA1. SHA 256 is considered to be secure. SHA 3 is under development at the time of writing of this article) hashing algorithm to retrieve the password from the hash. The methodologies that are used in general are dictionary or brute force attack where you try many passwords one after the other until you find a password that will give you the exact hash that you are looking for. If you find the exact hash for the plaintext! Voila you have cracked the password. The problem with dictionary based attacks is that dictionaries can't be very big and a password that does not exist in the dictionary will not be cracked. Brute force cracking has its limitations in terms of huge processing power requirements that are required to compute hashes. To brute force a password of up to 10 characters containing all small alphanumeric characters (abcdefghijklmnopqrstuvwxyz0123456789), the number of hashes to be calculated would be 36^1+36^2+36^3+36^4+36^5+36^6+36^7+36^8+36^9+36^10. 

 

Now this is a big task. It will take weeks or months to crack password this way.

 

A good idea would be to precompute the hashes and maintain a table of plaintexts and hashes. This will save the time of computing hashes and make the job of cracking the password easy. However the generated hash table will be very big in size.

 

Rainbow tables are way to keep the size of these precomputed tables low by making use of intermediate reduction functions. This was first proposed by Philippe Oechslin in his paper faster time-memory trade-off technique published in 2003.

 

So you want to use rainbow tables for cracking passwords. The questions are:

Q.1. What passwords you want/can to crack?

Ans. a.You can crack the passwords for which you have access to the password repository and the hashed password. 

b. You will also need to have the knowledge of the hashing algorithm used.

c. You will also require the rainbow tables built for the corresponding hashing algorithm.

 

The most common password repository is of Windows OS (If you are using one). It stores the NTLM hashed (LM hashed too for compatibility with older versions of windows) passwords that can be recovered using many programs like pwdump, LCP and Cain & Abel (You will require administrative access to the system for recovering these hashes).

 

Now you need to have the rainbow tables. You can either build them yourself which is a very time taking process that you might not want to do unless you have huge processing power available or you can download rainbow tables form many of the sites that provide it either free of cost or by the way of payment (Tables sizes will be in the range of 350 MB to 100 GB+). 

 

In case you do not want to download the tables there are a couple of resources that I have found that you can try using: 

http://www.plain-text.info/

http://www.freerainbowtables.com/

The above mentioned resources allow you to submit hashes and return plain texts for free.

In case you want to download and work in a more sophisticated manner the following resources should be helpful:

http://www.freerainbowtables.com/

http://project-rainbowcrack.com/

http://ophcrack.sourceforge.net/

http://rainbowtables.shmoo.com/

 

One of the simplest articles that I have found that can be helpful in understanding rainbow tables is:

http://kestas.kuliukas.com/RainbowTables/

 

Limitations of rainbow tables

1. For all the goody goody image of rainbow tables it also has its share of limitations. In spite of excellent compression algorithms rainbow tables still are quite big in size if the character set is huge. In general it’s difficult to find rainbow tables with big character sets for password lengths of more than 14.

2. Generating rainbow tables is very CPU intensive and takes huge amount of time. This can be offset by using distributed architecture for table generation or using very powerful computers.

 

Q. How to protect yourself against rainbow tables

Ans. 

1. Keep your passwords longer. In case of windows if your password is more than 14 characters long then no LM hashes (Which is weaker) will be stored. Do not use passwords, instead always use passphrases that are longer and easier to remember.

 

2. When designing a system for password storage never store password in plain hash. Use salts. Maybe double or triple hash them. e.g.

Password=hello how are you

Stored Password= SHA256(SHA256(Password+"The desired salt"))

Salts can be generated randomly and need not be secret.

This will make rainbow tables ineffective.

Security, Privacy and Indian Government

A couple of months ago I read the novel Digital Fortress by Dan Brown the celebrated author of Da Vinci Code. The novel is about a system built by National Security Agency (NSA), the top security agency of US government, how they gather intelligence in the internet world and the effort and resources put by NSA in doing all this. They built a system so powerful that it was able to monitor all the packets going from one device to another device on the internet in USA and use data mining tools that can lead to cops arriving at your home if you have sent a mail to a friend of yours which might be a joke that says "Lets kill George W. Bush on next Thursday". The processing power and tools required to do this kind of stuff is unimaginable by a normal citizen. But then the government has access to the largest funds in the country and it can source talent.

I was wondering if they really do something like this. If yes, are other governments doing this as well?

The answer to this is a big Yes. A few days ago I happened to attend a conference in Mumbai organized by Indian Banking Association on Banking security. I listened to a good set of speakers on various topics. One of the speakers was from Indian government Ministry of Home affairs, Directorate of Forensic science. He talked about the usual things in forensics, some steganography and then about the real thrilling and chilling stuff.

Here's the story:

Indian Government has the infrastructure that actually collects all the data from all the 8 ISPs in the state of Andhra Pradesh (may be other ISPs in all other states as well) in real time and send it to them. They have the capability of mining the data and taking decisions on the basis of that. So if you thought that you are at your office or home, sending mail to your business partner or girlfriend in total privacy with sufficient measures at your end like updated antivirus, updated anti-spyware, well configured firewall and very good security practices then you cannot be more wrong. Of course you knew that ISPs have all the data and law enforcement agencies could make use of that data any day but there is a difference in getting that data on demand and on need basis and getting it in real time. What would happen if there is no restriction on access to this data? Won't it be abused? One of my favorite lines to describe the situation is "Who will watch the watchers?".

When asked about use of tools like Tor to circumvent this kind of stuff he did not really respond. NSA also does this kind of stuff and uses softwares like carnival and magic yantra for the purpose.

Super Rapid Application Development

Many a times I have felt that development of applications takes a hell lot of time and by the time the development is over some requirements change. Most of the times requirements are not clear and neither the end user nor you can help it.

You would like to deliver as soon as possible with the best quality but you need to do all the due diligence and follow the processes and that eats up a lot of time. Agile methodologies like SCRUM and Extreme Programming appear to solve this to an extent but again not very good.

I have tried using small time code generators and found them to be of some help. Unfortunately they fail when requirements are little complex. I have used PHP Maker in few cases and found it to be good.

During my college days I read about Model Driven Architecture (MDA) from Object Management Group (OMG). Applications conforming to MDA specifications should be able to take UML diagrams as input and give the source code as output. What I am talking of here is not the skeletal code but the complete application with all the logic built into it at the lowest level. There are many implementations from may companies that promise this. I have not seen any of them in action. Some open source tools are also available in this area where you can get your hands dirty. Some of them are StarUML and AndroMDA (pronounced as Andromeda). These tools require that you have good understanding of UML. Unfortunately I am not very strong in UML and have not been able to test these tools to the extent I would have liked to. I need to read more of UML. I will try to give a review on StarUML in some time.

There are many companies who have built their own tool conforming to MDA specifications but do not share/sell it to others. One of the tools I know of is Solution Blueprint (SBP) that is used by Zensar technologies.

I am trying to learn more on this topic. Will post more when I have something good to share.

Replication of Visual SourceSafe

I wondered on how we can have a mutisite configuration for Visual sourcesafe (VSS) like clearcase or CVS. If not multisite capability then how can I have atleast one way replication of the VSS repository.

Thought of multiple methodologies and tools. One of the tools was source offsite that allows remote access for VSS repositories but nevertheless does not replicate the repository for disaster recovery purpose.

Then I realized that since VSS repository is not accessed via any special service, if the VSS files can be copied remotely it should do well. With this idea, I began searching for file replication tools. Found a lot of tools like rsync, double take, EMC replistor, ....

We tested a couple of tools and then decided on EMC replistor. It is robust, esay to use and advanced. Today we are able to replicate source code on a realtime basis.

Trekking (Kind of...) at Belapur and Kharghar

We went for a small trek on last Saturday. Some photos below.