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.
{ 1 trackback }
{ 4 comments… read them below or add one }
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.