Last week I talked about how fast processors and GPUs made password cracking easier. The idea was that dictionary words could be hashed quickly and then compared to target hashes. This week we’ll look at a very fast way to compute the hashes along with a fast way to search them.
A GPU or Graphics Processing Unit is like a CPU that does some things very quickly. Specifically, it does things very quickly that are used to make computer graphics look realistic. These include motion and drawing tasks (yes, that’s oversimplified). The GPU is not as good for general computing, though, because it’s optimized for those particular tasks. Modern graphics cards contain multiple GPUs.
Geremi Gosney took a total of 25 graphics cards in five servers to make a password cracking cluster. The speed stats are impressive and you can read about them in the linked article. To begin with, for example, it can try up to 350 billion password guesses every second. Wow. (If passwords uses a slower hashing method such as we discussed last week, this number would be greatly reduced, of course.)
Such fast machines cost a lot of money, of course. As time goes on the prices will drop and slow hashes will be crackable at similar speeds by using spare cycles on idle computers around an office. Until then, though, one speed improvement can be made. That improvement is called the rainbow table.
The way a brute-force (or dictionary) cracker works is to hash each option – whether a word from a list or a sequence of letters starting at “a” and going to “zzzzzzzzzzzzz” and on through the special characters – and comparing that hash to the target. This takes a lot of time.
Another way would be to compute all the hashes in advance and store the words generating those hashes in a big table. Since MD5 is a 128 bit hash, the table would have 2^128 (which is a 29 digit number when expressed in base 10!) entries, ranging in size from one character to the maximum length of a password. That’s a lot of storage!
A rainbow table is generated by computing almost all of those hashes. Only a small number are stored, though. The idea is a compromise between using a lot of time to “crack” a single hash and using a lot of storage to store all the hashes. Special software processes the table of stored hashes to find either a) the “word” that was used to generate the hash or b) a quick path (chain) to finding that word. The rainbow tables can range from a few GB to over 1TB. At the Free Rainbow Tables site, you can learn more about rainbow tables, download tables and software and volunteer to help create new tables.
In our course 468, System and Network Security we discuss rainbow tables and password cracking in more depth.