Rainbow Tables
February 13, 2010 Leave a comment
A rainbow table is a lookup table offering a time-memory tradeoff used in recovering the plaintext password from a password hash generated by a hash function. A common application is to make attacks against hashed passwords feasible. A salt is often employed with hashed passwords to make this attack more difficult, often infeasible.
An efficient windows XP password cracker that brute force the LM hash Ophcrack uses a rainbow table for alphanumeric characters of size 1 GB. Ophcrack is very effective and fast in cracking such passwords.
The Ophcrack contains the LanManager (LM) hashes of 99.9% of all alphanumerical passwords. These are passwords made of mixed case letters and numbers (about 80 billion hashes). Because the LanManager hash cuts passwords into two pieces of 7 characters, passwords of length 1 to 14 can be cracked with this table set. Since the LanManager hash is also not case sensitive, the 80 billion hashes in this table set corresponds to 283 passwords.
Strange enough and while LAN Manager is considered obsolete and current Windows operating systems use the stronger NTLM, NTLMv2 or Kerberos hashing methods, Windows systems before Windows Vista/Windows Server 2008 still compute and store the LAN Manager hash by default for compatibility with LAN Manager and earlier clients, as well as some 16-bit applications that are still in use on the most current versions of Windows. It is considered good security practice to disable this feature where it isn’t needed. Microsoft claimed that support for LM would be completely eliminated in the Windows Vista operating system. However Windows Vista and Windows Server 2008 still include support for the LM hash, although it is now disabled by default; the feature can be enabled for local accounts via a security policy setting, and for Active Directory accounts by applying the same setting to domain controllers. The same method can be used to turn the feature off in Windows 2000, Windows XP and NT. Users can also prevent a LM hash from being generated for their password by using a password at least 15 characters in length.
How to mitigate the Rainbow Table Attack
Rainbow table attack would be ineffective against one-way hashes that include salts.
The salt value is not secret and may be generated at random and stored with the password hash. A large salt value prevents precomputation attacks, including rainbow tables, by ensuring that each user’s password is hashed uniquely. This means that two users with the same password will have different password hashes (assuming different salts are used). In order to succeed, an attacker needs to pre-compute tables for each possible salt value. The salt must be large enough, otherwise an attacker can make a table for each salt value.
