MS-CHAP is dead

Tracking its long, slow death since 2002

While MS-CHAP has been used since 1998, it uses DES encryption which was deprecated in 2002. Attacks on MS-CHAP itself have been known since 2006, and those attacks have only gotten better over time. New attacks show that it is possible to crack most user-generated passwords in milliseconds, using only commodity hardware such as a laptop or desktop PC.

This means that if you have sent MS-CHAP over the wider Internet in the past 10 years, you should assume that the underlying user passwords have been compromised.

While some people may still see MS-CHAP as secure, we believe simple MS-CHAP is dead. We do not recommend that anyone use MS-CHAP outside of a secure transport protocol such as PEAP or TTLS.

MS-CHAP depends on cracked DES encryption

The MS-CHAP authentication method was first created in 1998. At the time, it used the industry standard encryption method at the time, which was DES (Data Encryption Standard). The DES standard had been used across the U.S. government since the 1970’s as a secure way of exchanging confidential data.

Around the same time of the MS-CHAP standard however, critics of DES estimated that the key size was too short and efforts were afoot to crack it through brute force attacks. The Electronic Frontier Foundation created custom microchips and other hardware to successfully decrypt DES in 1998. Over the next two years, they were able to progressively decrease the cracking time from 56 hours, to less than a day.

Custom

DES cracker machine, built for a cost of $250,000 in 1998. Well within the reach of hostile governments and large corporations.

The successful attacks on DES cryptography led to it being replaced by AES (Advanced Encryption Standard) as the U.S. federal standard in 2002.

MS-CHAP implementation of DES is flawed

Even if DES was completely secure, there is a key flaw in the design of MS-CHAP that makes it highly vulnerable to attacks. To understand the flaw in MS CHAP we need to look more closely at how DES is integrated with the protocol.

As part of the handshake protocol, MS-CHAP exchanges a 16 character NT hash of the password. These keys are mapped to DES keys, which uses 56 bit (7 characters) for keys for its encryption. The mismatch means that in order to use the NT hash with DES, there are 3 separate DES operations as seen below.

MS-CHAP implementation of DES. The empty padding on the third key greatly simplifies cracking attempts on MS-CHAP.

Each byte of the NT hash maps to a DES key, but that leaves five (5) bytes left over. So the last DES key only uses the first two characters for the NT hash, and the rest of the key is filled with padding, which is all zeroes.

This is the key flaw in the MS-CHAP implementation. Instead of filling out the last five characters of the final DES key with secure data (for example, by wrapping around to the beginning of the hash and re-using “Hash 1”, “Hash 2” etc), it is simply padded out with zeros. This means that the final DES key has only 16 bits of actual key data, and the rest of the key bits are known.

The problem space is now only 216, instead of 256. In other words, for DES key 3, there are only slightly over 65,000 possible values instead of over 72 Quintillion. On modern hardware, it is possible to “brute force” search all possible values for DES key 3, and find those 16 bits. While this attack is brute-force, 216 is not a large number, and doing 216 DES operations is trivial for any modern computer.

All that remains then is to crack the remaining 14 bytes of the NT hash. Admittedly, this is still a lot of key space to search: 2(56+56) or 2112 which is a huge number. However in 2012, a key insight showed that you could leverage the design of MS-CHAPv2 to instead search only 256 possible keys, which could be cracked using a brute force attack in less than a day.

This time can be further reduced by noting that most passwords are generated by users, and in computer security terms, do not have large entropy. In human terms, that means that the passwords are likely to be re-used, and therefore guessable.

We can make many guesses by using freely available lists of most frequently used passwords, and creating pre-build “dictionaries” which precompute the NT hash values for those passwords. These dictionaries can also be created for any additional information about targeted individuals such as birthdays, pet names, children names, company names / projects, etc. A simple program can generate hundreds of millions or billions of such guesses, and store them in a simple database on commodity hardware. This database would take at most a few tens of gigabytes of space, which is less than many high-end games.

The final nail in the coffin

In 2021, the final nail in the coffin of MS-CHAP security was demonstrated by leveraging a novel strategy of:

  1. Brute force cracking the third DES key to get the last 16 bits of the NT-hash,
  2. Storing a database of billions of guessed passwords and their NT hash, indexed by the final 16 bits of the hash
  3. Using the found DES key to get a list of guessed passwords (index lookups are fast), which reduces the search space by 216

The result was that it with a little bit of work and disk space, it is now possible to obtain the underlying MS-CHAP password very quickly, with much less than 256 possible work.

That is, if the database stores a table of 4 billion passwords, then dividing that search space by 216 means that the system only has to brute-force check about 65,000 passwords. The result of this algorithm attack means that MS-CHAP can be cracked by checking 64K DES keys, and then using large tables to get another 64K NT hashes to check. The combined cost of these two operations is very, very, small. A laptop with a few gigabytes of memory and a large SSD can crack MS-CHAP in only a few milliseconds.

In other words, if your organization sent MS-CHAP over the internet with user generated passwords, you can assume that those passwords are now in the hands of malicious actors, or the NSA, or both.

Some notable exceptions

There are some caveats to this doomsday proclamation, however.

The flaws of MS-CHAP can be mitigated by running it inside of TTLS or PEAP. This is the approach used by the eduroam community and it works well since those EAP methods protect MS-CHAP by wrapping it in a secure layer of TLS. Since TLS has not been broken, no one can see the MS-CHAP data, and the attack is stopped in its tracks.

Another factor that can make this attack somewhat less effective is by encouraging users to use computer generated passwords (for ex: the passwords suggested by web browsers or common password managers.) These randomly generated passwords will not appear on any of the pre generated password tables, and therefore will still require brute force effort to crack

This is small comfort however, as the brute force attack requires only 256 operations, and that was shown to be possible over 25 years ago!

Even if none of the above attacks worked, there is still a major security problem with MS-CHAP: it requires you to store clear-text passwords in the database. (Or NT-hashes, which are “clear-text equivalent.”) Any compromise of the database means that all user identities and passwords can be trivially copied by an attacker.

Our recommendation, then, is do not use MS-CHAP. Adding a PEAP or TTLS wrapper to simple MS-CHAP helps a little bit against some attackers, but it is still not secure.

What to use instead of MS-CHAP

We always maintain that the most secure protocol for authenticating users over the internet is PAP. Using PAP means that passwords can be stored in the database in a salted/hashed form. Given that the vast majority of data breaches have succeeded by targeting password databases, storing passwords in an encrypted form is definitively the most secure approach for any authentication system.

Still need help?

Network RADIUS has been helping clients around the world design and deploy their RADIUS infrastructure for 20 years. We specialize in complex systems and have seen pretty much every variation and problem out there. If you want help from the people who wrote FreeRADIUS, visit our quote page to contact us for a consultation.

Read more...

related articles