I have previously written about one-way hash functions and their importance for cryptography. Recapping briefly, hash functions take some data (a password, a picture, a file, etc) and pass it through a mathematical algorithm. This produces an output with two special features. First, it should be very difficult to find two pieces of data that produce the same output (collisions). Second, it should be very difficult to work backwards from the hashed version to the original. By ‘very difficult,’ I mean ‘challenging for a government with cryptoanalysts and millions of dollars worth of hardware.
Rainbow tables are a novel way of reversing hash functions. Basically, these consist of massive databases of hash and plaintext data. Rather than trying to calculate back from the hash you have to the password you want, you can use the hash in combination with the latter to get the password quite quickly. Since many applications and operating systems use hashed passwords to increase security, having access to rainbow tables could make them significantly easier to compromise.
This is just another example of how math-based security is constantly challenged by evolving technology and falling prices. Being able to afford enough storage for rainbow tables alters the security of hash functions generally. MC Frontalot definitely had it right when he argued that: “You can’t hide secrets from the future with math.”
PS. As with slugs, the best defence against rainbow tables probably consists of using salt.
To begin, password storage 101: servers don’t usually store actual passwords. Instead, they hash the password, store the hash, and discard the password. The hash can verify a password from a login page, but can’t be reversed back to the text of the password. So when you inevitably lose your SQL password table, you haven’t exposed all the passwords; just the crappy ones.
…
Rainbow tables are easy to beat. For each password, generate a random number (a nonce). Hash the password with the nonce, and store both the hash and the nonce. The server has enough information to verify passwords (the nonce is stored in the clear). But even with a small random value, say, 16 bits, rainbow tables are infeasible: there are now 65,536 “variants” of each hash, and instead of 300 billion rainbow table entries, you need quadrillions. The nonce in this scheme is called a “salt”.
LM hash or LAN Manager hash is one of the formats that Microsoft LAN Manager and Microsoft Windows versions previous to Windows Vista use to store user passwords that are fewer than 15 characters long.
…
Because LM hash does not include salt, a time-memory trade-off cryptanalysis attack, such as rainbow tables, is also feasible. In 2003, Ophcrack, an implementation of the rainbow table technique, was published. It specifically targets the weaknesses of LM encryption, and includes pre-computed data sufficient to crack virtually all alphanumeric LM hashes in a few seconds. Many cracking tools, e.g. RainbowCrack, L0phtCrack and Cain, now incorporate similar attacks and make cracking of LM hashes trivial.
To address the security weaknesses inherent in LM encryption, Microsoft introduced the NTLM algorithm with Windows NT 3.1. While LAN Manager is considered obsolete and current Windows operating systems use the stronger NTLM hashing method, all Windows systems still compute and store the LAN Manager hash by default for compatibility with LAN Manager and Windows Me or earlier clients.
…
[T]he current Vista release does include support for the LM hash, although it is disabled by default.
Naturally, it’s Microsoft that is using the most vulnerable system.
Free Rainbow Tables Looking For New Admin
Posted by kdawson on Friday July 17, @01:24PM
“After almost three years online, the admin of Free Rainbow Tables has decided to call it a day, citing a lack of time to keep it running. (I’m sure that you all know a rainbow table is essentially a giant list of precomputed hashes.) This is a shame, as the site is a useful resource for those occasions when you really need an existing password exposed, rather than simply changing it. I’m a Windows admin, and this site has come in very handy in the past. The currently computed tables weigh in at well over half a terabyte, are available as torrents from the site, or from a couple of mirrors (and alternatives are available). When the site was active, it featured a downloadable BOINC client to put your idle cycles to work computing ever-greater tables, and a space-saving format for storing the tables. The admin is willing to hand over source code if you wish to take over, though I suspect hosting is not included!”
A Swiss security company called Objectif Sécurité has created a cracking technology that uses rainbow tables on SSD drives.
So, I pulled several 14 character complex passwords hashes from a compromised Windows XP SP3 test machine, to see how they would stand up to Objectif’s free online XP hash cracker.
The results were stunning.
Let’s start out with an easy one. Here is the Administrator password hash from the machine:
aad3b435b51404eeaad3b435b51404ee:31d6cfe0d16ae931b73c59d7e0c089c0
And putting this into Objectif’s tool we get this response:
Password: Empty password…
Time: 2 seconds
Administrator didn’t set a password, that’s not good…
Okay, that wasn’t 14 characters, let’s try a hard one.
How about this one:
Hash: 17817c9fbf9d272af44dfa1cb95cae33:6bcec2ba2597f089189735afeaa300d4
And the response:
Password: 72@Fee4S@mura!
Time: 5 Seconds
Wow! that took only 5 seconds and that is a decent password.
Let’s try a few more:
Hash: ac93c8016d14e75a2e9b76bb9e8c2bb6:8516cd0838d1a4dfd1ac3e8eb9811350
Password: (689!!!”QTHp
Time: 8 Seconds
Hash: d4b3b6605abec1a16a794128df6bc4da:14981697efb5db5267236c5fdbd74af6
Password: *mZ?9%^jS743:!
Time: 5 Seconds (Try typing that in every day!)
And Finally:
Hash: 747747dc6e245f78d18aebeb7cabe1d6:43c6cc2170b7a4ef851a622ff15c6055
Password: T&p/E$v-O6,1@}
Time: Okay, this one really pushed it to the limits, it took a whole 11 seconds to crack!
Very impressive, it took only five to eleven seconds in this test to crack 14 character complex passwords.
Are You Sure SHA-1+Salt Is Enough For Passwords?
“It’s all too common that Web (and other) applications use MD5, SHA1, or SHA-256 to hash user passwords, and more enlightened developers even salt the password. And over the years I’ve seen heated discussions on just how salt values should be generated and on how long they should be. Unfortunately in most cases people overlook the fact that MD and SHA hash families are designed for computational speed, and the quality of your salt values doesn’t really matter when an attacker has gained full control, as happened with rootkit.com. When an attacker has root access, they will get your passwords, salt, and the code that you use to verify the passwords.”
Wired’s Kim Zetter, reporting from Army Pvt. Bradley Manning’s first hearing on charges of leaking classified documents to Wikileaks: “Manning asked “Nathaniel Frank,” believed to be Assange, about help in cracking the main password on his classified SIPRnet computer so that he could log on to it anonymously. He asked “Frank” if he had experience cracking IM NT hashes (presumably it’s a mistype and he meant NTLM for the Microsoft NT LAN Manager). ‘Frank’ replied yes, that they had ‘rainbow tables’ for doing that. Manning then sent him what looked like a hash.”
“It is becoming increasingly difficult for anyone, anyone at all, to keep a secret.
In the age of the leak and the blog, of evidence extraction and link discovery, truths will either out or be outed, later if not sooner. This is something I would bring to the attention of every diplomat, politician, and corporate leader: The future, eventually, will find you out. The future, wielding unimaginable tools of transparency, will have its way with you. In the end, you will be seen to have done that which you did.
I say ‘truths,’ however, and not ‘truth,’ as the other side of information’s new ubiquity can look not so much transparent as outright crazy. Regardless of the number and power of the tools used to extract patterns from information, any sense of meaning depends on context, with interpretation coming along in support of one agenda or another. A world of informational transparency will necessarily be one of deliriously multiple viewpoints, shot through with misinformation, disinformation, conspiracy theories and a quotidian degree of madness. We may be able to see what’s going on more quickly, but that doesn’t mean we’ll agree about it any more readily.”
Gibson, William. Distrust That Particular Flavor. p.170 (hardcover)