Security Advisor

Rainbow Crack--Not a New Street Drug

You can roll your own (pardon the pun) cracks for Windows LM passwords.

I remember when the Lopht introduced their password-cracking program for Windows, L0phtcrack. The Lopht claimed that Microsoft’s LAN Manager authentication protocol was weak and could be attacked easily. Microsoft challenged the Lopht’s assertions, and the rest is ancient history. Lophtcrack is now known as LC5, LM has been replaced as the default authentication protocol by NTLM, NTLMv2 and Kerberos, and LC5 is now a respected administration tool. Most of us have learned how to protect our systems from its use, how to use it to promote the use of complex passwords and how to protect sensitive accounts from its impact. The program has become the most widely known password-cracking program of Windows systems. Yet it was almost superseded.

Birth of a New Cracking Champion
A few months ago, Philippe Oechslin demonstrated a more efficient method of cracking Windows LM passwords. The method, known as the Faster Time-Memory Trade-Off Technique (based on earlier work by Hellman), uses pre-calculated tables consisting of every possible combination of characters in a Windows password and a sophisticated search algorithm. The result is quicker password cracking—up to 12 times faster. (You can read Oechslin’s paper at http://lasecwww.epfl.ch/php_code/publications/search.php?ref=Oech03). The new method, as first introduced, was only tested with password combinations acceptable to the vanilla LM algorithm. Most of you know that a considerably more extensive character combination and password length is available for NTLMv2. However, you can find tools for implementing the algorithm and creating the tables for NTLM readily available on the Web. These tools and tables have been dubbed “Rainbow Crack.”

Rainbow Crack uses pre-generated password combination tables, and an elegant searching algorithm. While a commercial cracking program has yet to announce its use of this technique, you can obtain access to online examples, download a tool complete with pre-prepared tables or purchase Rainbow Crack tables and roll your own. Investigating this new technique is a good idea, because it may be used in the future to reduce the time taken to discover complex passwords.

The time factor has often been cited as useful for defense against password cracking. One theory holds that the use of complexity can rapidly increase the time necessary to crack a password, allowing development of a sound strategy: Make them complex enough to keep passwords from begin cracked during the timeframe that they’re valid (the time between password changes.) While this still holds true, the appropriate validity/time constraint is shrinking. Faster machines, distributed password cracking and now Rainbow Crack are contributing to that. There are, however, many things that can be done to protect passwords until a different defense can be adopted. Follow these rules:

  • Select and configure strong network authentication protocols.
  • Select and configure strong remote access protocols.
  • Protect password databases.
  • Have a strong password policy.
  • Obtain current password-cracking software and learn how it can be used.
  • Enforce the password policy with user awareness training and password audits.
Cracking Techniques
  • A dictionary attack uses a file of dictionary words. Using the same algorithm used to create the Windows password hash, it then compares the hash to password hashes in the Windows password database.

  • A heuristic attack uses known password creation tendencies such as the inclusion of numbers at the end of a password, or the use of common passwords as an aide in finding part or all of the password characters.

  • A brute-force attack simply tries every possible combination of characters until a match is found. Given enough time, a brute-force attack can deduce any password.

  • Rainbow Crack uses a pre-hashed table of every possible combination of characters and a sophisticated search algorithm that speeds up the search of such a large amount of data.

Configure Strong Network Authentication Protocols
Windows network logons can be strengthened by using Kerberos where possible and by insisting on NTLMv2 where it isn’t possible. In a Windows 2000 Server or Windows Server 2003 domain, Kerberos is the authentication mechanism of choice for network logon by Windows XP, Win2K and Windows 2003 member computers. However, the LM protocol may be used when a non-member server attempts to access a domain resource, when the IP address instead of a computer name is used in accessing a share, when a domain controller can’t be accessed and possibly in other circumstances.

Therefore, in addition to using domains and more modern Windows OSs, you should configure Windows to use NTLMv2. This protocol is more secure than its predecessors—LM and NTLM—for a number of reasons, including the central one that it’s more difficult to crack. LC5, for example, can crack NTLMv2 passwords, but it takes much longer, even for simple passwords. For this reason, the default mode for LC5 cracks the copy of the LM hash first, then deduces the NTLMv2 version. To ensure that NTLMv2 is in place where Kerberos isn’t, make the applicable configuration changes:

  • In Win2K and Windows 2003 domains, set the Group Policy Security Option “Network Security: LAN Manager Authentication Level” to Send NTLMv2 response only\refuse LM & NTLM. This will require clients to use NTLMv2. (This option is set by default to require at least NTLM authentication in Windows 2003 domains.)
  • To set NTLMv2 for Windows NT SP4 domains, add the REG_ DWORD value “LMCompatibility” and set it to 5. The Registry value should be added at

    HKEY_LOCAL_MACHINE\System\CurrentControlSet\Control\LSA

  • To require NTLMv2 for Windows 95/98, install the Active Directory client and complete the Registry entry above.
  • Eliminate the storage of LM hashes in the password database. This is turned on by default in Windows 2003. It can be set using the Security Option “Network Security: Do not store LAN Manager hash value on next password change.” For Win2K domains, add the NoLMHash value to the location below. This only prevents storage of LM hashes; it won’t delete existing LM hashes. Users must change their password before this option will do any good.

    HKEY_LOCAL_MACHINE\System\CurrentControlSet\Control\LSA

Please test these settings. There are a number of issues with NTLMv2 and legacy applications such as Windows remote access. Remember that you can set security options on an OU-by-OU basis or one computer at a time using scripts or manual methods. It isn’t necessary to have a domain-wide policy for NTLMv2 policy, though it’s the most secure approach.

Strengthen Remote Access Authentication
When authentication is necessary for remote access, whether dial-up, Web or wireless, logon security must be matched to the requirements of the application and the availability of protocols. A range of authentication protocols is available for remote access, including anonymous, basic (passwords in the clear), integrated (LM variants or Kerberos), PAP, CHAP, MS-CHAP, MS-CHAPv2 and EAP (variants of which include PEAP and smart cards). Default settings are usually the least secure and vary depending on whether access is dial-up, WAN or wireless. Your ability to implement security depends on the client types that need access, and the capabilities of the hardware and server software. While anonymous access may be desirable for public Web sites, in general you’ll want to configure at least MS-CHAPv2 and wherever possible use EAP to provide better protection. In addition to the normal issues of LAN-based authentication, remote access increases risk because communications will take place over un-trusted networks. Use the highest level of authentication security possible and supplement that by protecting communications.

In Windows 2003 and Win2K environments, use remote access policies to further manage and secure remote access. Where appropriate, use Internet Authentication Services (IAS) to centralize authentication. Remote access policies can be used to granularize the remote access process over groups of users, time of day, communication protocols and so on. Remember, wherever access channels are restricted, the ability of an attacker to compromise information systems by attacking account passwords or using already compromised passwords to obtain access is limited. Using such chokepoints, or narrowed communications channels, is a well-known security principle.

Protect Authentication Communications
Because captured credentials are vulnerable to password-cracking attacks, protect communications. If credentials are protected by encryption and other techniques, an attacker won’t be able to use simple credential-capturing techniques to obtain passwords passed in clear text, or those that can then be used by password cracking programs. Possible methods for communication protection are readily available and include:

  • VPNs
  • SSL
  • IPSec policies
  • SMB signing

Where NTLM may be used, set the minimum-security negotiation level by setting the NtlmMinServerSec value. This Registry value can be set to require message integrity, confidentiality, session security and/or 128-bit encryption. The value is at:

HKEY_LOCAL_MACHINE\System\CurrentControlSet\Control\LSA\MSV1_0

Protect Password Databases
On all NT 4.0 systems and all post-NT 4.0 systems based on NT 4.0 technologies except DCs, the SAM database includes user account information, including password hashes. It’s imperative to protect these files. Don’t weaken the permission settings on these Registry files or the Registry permissions. When a backup of the Registry is made, protect that backup. Also, inspect the repair directory and protect it, as well.

When backups are made using some programs, a copy of the SAM file is saved to the repair directory. Unlike the SAM file, the copy in the repair directory can be copied from the hard drive when the system is running. More than one known remote attack, if successful, obtains access to the server and TFTPs (Trivial File Transfer Protocol) the file to another server. Protect systems from these types of attacks: Patch vulnerabilities that can lead to system compromise; don’t install TFTP; maintain permissions on the repair folder; and, where possible, remove the SAM file copy from the repair folder. Note that some attacks will install their own TFTP program on the compromised server, so not installing the server’s TFTP program is little more than a speed bump. If the machine is owned, it’s game over. However, putting up roadblocks might just provide the time necessary to detect the attack underway and shut it down before the SAM file is exploited. Other tips:

  • Windows 2003 and Win2K DCs keep the password database in the Active Directory file ndis.dit. This file can’t be copied while the system is active.
  • Protect backups. Backups may contain copies of the SAM or ndis.dit file. Don’t leave them unprotected and monitor their access.
  • Physically protect computers. If the system can be physically accessed, an attacker might be able to reboot it into another OS. This would allow the attacker to copy the database file and remove it for attack elsewhere or to run an attack locally.
  • Limit, vet, audit the assignment and use of administrative-level accounts. Have a strong administration policy that includes a firm definition of who may obtain administrator group membership; require protection of administrative workstations; require strong, complex passwords above and beyond the technical password policy; and require administrator accountability. Numerous administration tools, such as Winternals ERD Commander and various iterations of pwdump can be used to obtain a copy of the password database from servers, workstations and DCs. If an attacker can obtain administrative access, these tools can be used to obtain the database. Remember, most password cracking tools rely on the availability of password hashes—if they can’t obtain the hashes, they can’t crack the passwords. To help keep the databases safe, guard administrative accounts. After all, if an attacker can obtain administrative access, he or she may not need to crack other passwords to obtain whatever it is he or she desires.

Implement a Strong Password Policy
Organizational policy may determine the domain password policy. You may need to work with appropriate committees and individuals to enable a stronger password policy. Long passwords—those that use 15 characters or more—automatically require NTLM. Be aware, however, that newer Rainbow Crack tools provide tables that include NTLM hashes and unless LM hashes are eliminated from the database, those hashes can be used to crack the password. (Still, these tables don’t provide a result for every possible NTLM password length and character set.)

Also remember that the longer the password, the harder it is to crack, and the harder it is for users to remember. And as you know, password length isn’t the only thing that can make passwords more difficult to crack. Using less common characters can also make the cracking job more difficult. Some Rainbow Crack tables don’t include variations using spaces, while others stop with the more common character set:

Listing 1. The common character set used by some Rainbow Crack tables.
     ABCDEFGHIJKLMNOPQRSTUVWXYZ
     abcdefghijklmnopqrstuvwxyz
     0123456789!@#$%^&*()- +=

Using passwords that include other characters may foil them.

Obtain Current Password-Cracking Software
One of the best investments a security team can make is in a password cracker. As more companies turn to smart cards and biometrics, it may be that the lowly password’s days are numbered. However, it’ll still be awhile before the use of passwords to secure access to data systems entirely disappears. On some networks, that time frame may be infinity.

Obtaining a copy of password-cracking tools allows for preparing a proper defense against them. First, shake up your complacent attitude and that of your peers. It isn’t as difficult, nor as time-consuming, to crack passwords today as it was a few short months ago. Without knowledge of the latest techniques, you can’t hope to protect authentication. Next, knowing how they work, combined with your knowledge of Windows authentication, helps you to mitigate their impact. I’ve provided some proper techniques here, but a thousand eyes are more valuable than two. Finally, you can use these tools to audit compliance to your current password policy.

For many years now, LC5 and its predecessors have been the crown prince of Windows password-cracking programs. They crack both simple and complex passwords using a combination of techniques, including dictionary, heuristic and brute-force attacks. LC5 also provides Rainbow Crack tables. You can purchase a copy of LC5 directly from @stake www.atstake.com.

If you wish to test rainbow crack tables directly, without purchasing LC5, there are many ways to test the technique. Please be aware, however, that current publicly available projects have limitations. Some work only on LM hashes (and one famous one doesn’t account for the use of the space character), others include tables for NTLM, but not NTLM hashes. In some cases, the code and information on how to produce your own variation of the program is also available.

Provide User Awareness Training
Technology alone will never be enough to protect information systems. Hardening wetware—the people portion of any information system—is necessary, as well. Users can’t be required to understand on their own the importance of following the password policy, nor merely expected to comply to some issued edict. But if you can obtain user buy-in to security policy, it’ll reduce the effort required to ensure compliance.

One way to accomplish buy-in is by providing user awareness training. Part of that training can be reading and promoting an understanding of the security policy; other efforts can be directed toward teaching the how-tos of creating strong passwords and demonstrations of how password-cracking programs work. When people see how easily weak passwords are cracked, it reinforces their commitment to using stronger ones. Awareness training can also teach how to resist social engineering.

What To Do if You do Get Hacked
When all is said and done, you’re still vulnerable to password-cracking attacks, accidental exposure, and social engineering. In short, some day you may be hacked. If you have strong intrusion detection capabilities and maintain strong incident response capabilities, you can minimize the impact of such a compromise. When an attack is discovered, the ability to rapidly disable sensitive administrative accounts, change others immediately, institute password changes by every user on your system, and discover and close the hole that allowed access can limit the impact a successful intruder may have.

comments powered by Disqus

Reader Comments:

Thu, Jan 15, 2009 Lame Anonymous

help

Sun, Jul 6, 2008 Brian Anonymous

Rainbow tables can be easily defeated simply by salting your hash. Simply add a user specific salt to their password before you evaluate the hash(doesn't have to be a secret, their ID number will work just fine, but the more salt, the better). This way the attacker has to have a hash table 10,000 times larger, even with a password of the same strength(assuming you are only using a 5 digit id number).

Mon, Nov 20, 2006 Anonymous Anonymous

excellent

Thu, Dec 22, 2005 help help

Good s***, she knows whats she is talking about...Type 'help' if you are lame.

Fri, Nov 4, 2005 T US

These tables, along with MD5, NTLM, and SHA1 are available online at www.rainbowcrack-online.com, the actual tables are available for purchase, however it's much more economical to 'lease' access for a month.

Mon, Oct 17, 2005 Jean Toulouse (France)

Merci pour cet article pationnant et instructif.

Tue, Jun 28, 2005 Anonymous Anonymous

Rainbow Tables have had enough time that groups now own a copy of every available set of tables for all the flavors of hash, md5, lm, ntlm, sha1, mysql3.23, etc. By now your only hope of creating an unbreakable password is to put a character in it that is outside the normal rainbow table character set. use ¿ or » or any ALT + 123 number combination. This one would think is common sense, since a set of tables created to break a password with every available character available to the user sitting at the keyboard would amass a huge 300 gigs for a mere 80% discovery rate. Note: going through these huge tables for your one measley password would take so much time for one person, but password crackers (the smart ones at least) operate in groups, with the power to crack over a large amount of distributed dedicated fast cracking machines. Either use a character outside the the crackers most favoritepopular character set, or wait until microsoft introduces salted hashes.

Thu, May 19, 2005 PhPLoKI Iowa

Good write up. in responce to "But the tables take up 118gb of data and would take over a thousand days to precompute on one machine." this calculation is on a 666 mhz.. it took a chunk of time on my 3.0 but worth it in my opinion. and the table creation is a one time thing. I think what this write up was showing is that yes.. people WILL find a way to hack.. ethical or not.

Thu, Mar 31, 2005 Jason Arizona

Good s***, she know whats she is talking about... Type 'help if you are lame.

Sat, Jan 29, 2005 [web]dezine™ India

intresting article. of course, now a bit outdated. since the new Rainbow tables do go ahead and crack all variations, but upto only 16 digits right now.. and took about 11 minutes for 100 passwords.

but still. really nice.

Wed, Jan 5, 2005 khaled UAE

good info

Tue, Aug 17, 2004 Anonymous Anonymous

Rainbow tables are now customizable. You can set it up to use the hole entire keyspace including the space. But the tables take up 118gb of data and would take over a thousand days to precompute on one machine. it is also cracks 99% of the passwords

Wed, Aug 4, 2004 corechirurg CZ

Windows 2003 keep the password database in file ntds.dit.

Sat, Jul 31, 2004 roberta bragg Anonymous

in answer to anonymous:
yes, as noted in the article lc5 has rainbow crack tables
and yes they can quick crack LM passwords.
but they cannot work with NTLM only hashes, and are foiled by certain characteristes
time to read the article all the way through before you complain.

Fri, Jul 30, 2004 Anonymous Anonymous

The rainbow crack is now out there in a product form - @stake LC 5 - L0phtCrack. Last I heard it only takes about 9 minutes to crack a typical LM password. It comes with a CD containing the hash tables and other commonly used passwords. It was even demonstrated by one of the geeks on the G4-Tech TV show ScreenSavers.

It is time to catch-up with the rest of the world and maybe get ahead of the curve.

Thu, Jul 29, 2004 roberta bragg Anonymous

In answer to Darby. Yes, I have tried the tables. the ones I tested could not crack passwords over 14 characters, with a space in them, or when the LM has was removed from the password database. simple passwords, yes, outside of the lm data set, or with no LM hash. no.

Wed, Jul 21, 2004 Darby Orlando

Have you tried to use the actual tables yet?

Sounds very general. I'm really into specifics.

Wed, Jul 14, 2004 Anonymous Anonymous

nice article

Sun, Jul 11, 2004 Anonymous Anonymous

good info

Wed, Jul 7, 2004 Anonymous Anonymous

informative

Fri, Jul 2, 2004 Ernie Oporto New Jersey

I've been using a password cracking tool called John the Ripper to go through the LM password database and test the strength of out users' passwords. Too many times we find the enterprise is being secured by someone's dog "snowball" or "bluedragon". I've tried using LDAPS tools, but had trouble pulling userPassword out of AD, even as Administrator.

I've always found that the best passwords were phrase related, picking the first letter of a phrase, and replacing letters with non-alphanumeric characters. "The fox jumped over the lazy brown dog" can become the password "tFJ0+LbD!". It's easier to remember than some random concoction of letters and symbols if it's more meaningful to the end-user. Note that some web interfaces may baulk at the use of non-alphanumeric characters.

Additional measures: close all services over the Internet such as telnet that show a password in the clear and switch to something like SSH. Implement VPN for all employee remote access; even on a WLAN this has benefits. Get an SSL box like a Netscreen-SA (formerly Neoteris) to make remote access even easier than VPN for brain dead end-users. Rather than using real passwords, use a token-based RADIUS authentication system (see Safeword Secure Computing or SecurID) so that no one forgets their passwords; the passwords are one-time, so it automatically takes the place of that often ignored password changing policy.

Add Your Comment Now:

Your Name:(optional)
Your Email:(optional)
Your Location:(optional)
Comment:
Please type the letters/numbers you see above

Redmond Tech Watch

Sign up for our newsletter.

I agree to this site's Privacy Policy.