Sunday, November 6, 2016

Rainbow table

Prof Hugh's talk on compute security was very inspiring, especially the part about rainbow table. I was wondering after class, if rainbow table seems to be so powerful in cracking password hashes, does it means that our passwords are not secure at all? Out of curiosity, I researched on the defence mechanism for rainbow table and here is what I found:

First of all, adding a salt is a very intuitive approach to defence against rainbow table. A salt is a random data that is used as an additional input in hashing a password. Same password hashed with different salts will result in different hash values. But bear in mind that the salt value must be large enough to make rainbow table ineffective. Otherwise the attack will still be able to precompute the password hashes for different salt values. I think the underling principle of this mechanism is quite common in computer security: instead of aiming for perfect secrecy, you create a computationally secure scheme to defend against attackers with limited amount of resource. This idea works because it is likely that for every single bit increased in the encrypted data, it takes attacker exponential amount of resource to break it, so called 魔高一尺,道高一丈. (Quan Yang mercy please if I am wrong >.<)

Secondly, in addition to adding salt while hashing the password, we can run the underlying hashing function multiple times to increase the amount of times required for the attacker to build rainbow table.  This is called Key Strengthening. The response time to validate users' input password will be affected as well but since for each user they only need to hash one password multiple times the overhead is negligible.

Another defence mechanism is even more interesting. Based on what we have for key strengthening, if we remove the salt after we hash the password, normal users and attackers will have to brute force the salt results. This will increase the overhead for normal users in a significant amount of time. But I am not very sure how it helps to defence against rainbow table attack better than key strengthening. It seems that such defence mechanism is only published on a paper and hasn't been put into practice yet.

Computer security is such an challenging and important field in computer science and after what Quan Yang and Prof Hugh had demonstrated in our lectures, it seems to be amazingly interesting as well. I really feel like looking into this area and having some fun myself~


No comments:

Post a Comment