After a long trip to the United States to return to Defcon, I am back and thought I’d share some information on a talk I checked out by Moxie Marlinspike which was of particular interest to me as this year I decided to use a PPTP tunnel instead of an SSH tunnel; not the best of ideas it turns out!
What is Chapcrack and CloudCracker?
Chapcrack is a tool you can use to take network packet captures and extract from them a string which can be submitted to CloudCracker which can finish a brute force against it in a worst case scenario of 24 hours and return to you via e-mail the cracked key.
CloudCracker does come at a cost (that being $200 per key), however if you really need to crack the key, the money isn’t much to part with when you take into consideration the amount of time that will be saved if a strong key has been chosen.
Some Background on the Protocol and its Flaws
Just want to start off pointing out this research of the protocol is not my own, I am not taking credit for it, it was done by Moxie; I am just reposting it for the sake of keeping this post as informative as possible!
Let’s take a look at the protocol itself, in order to see what we’re dealing with:
At first glance, one is initially struck by the unnecessary complexity of the protocol. It almost feels like the digital equivalent of hand-waving — as if throwing in one more hash, random nonce, or unusual digest construction will somehow dazzle any would-be adversaries into submission. The literal strings “Pad to make it do more than one iteration” and “Magic server to client signing constant” are particularly amusing.
If we look carefully, however, there is really only one unknown in the entire protocol — the MD4 hash of the user’s passphrase, which is used to construct three separate DES keys. Every other element of the protocol is either sent in the clear, or can be easily derived from something sent in the clear:
Given that everything else is known, we can try ignoring everything but the core unknown, and seeing if there are any possibilities available to us:
We have an unknown password, an unknown MD4 hash of that password, a known plaintext, and a known ciphertext. Looking back at the larger scope, we can see that the MD4 hash of the user’s password serves as a password-equivalent — meaning that the MD4 hash of the user’s password is enough to authenticate as them, as well as to decrypt any of their traffic. So our objective is to recover the MD4 hash of the user’s password.
Typically, given a packet capture, this is where a network adversary would attempt to employ a dictionary attack. Using a tool such as asleap, it’s possible to rapidly attempt a series of password guesses offline. The attacker can simply calculate MD4(password_guess), split that hash up into three DES keys, encrypt the known plaintext three times, and see if the concatenated output from those DES operations matches the known ciphertext.
The problem with this approach is that it won’t give the attacker a 100% success rate, and relies on the user’s propensity for selecting a predictable password. In the case of the riseup.net PPTP VPN service, for instance, the attacker would need to attempt guesses across the full 96 key character set for all 21 characters of the generated password. That’s a total complexity of 9621 — slightly larger than 2138, or what you could think of as a 138 bit key.
In a situation with an unbounded password length across a large character set, it would make more sense to brute force the output of the MD4 hash directly. But that’s still 128bits, making the total keyspace for a brute force approach on that value 2128 — which will likely be forever computationally infeasible.
The hash we’re after, however, is used as the key material for three DES operations. DES keys are 7 bytes long, so each DES operation uses a 7 byte chunk of the MD4 hash output. This gives us an opportunity for a classic divide and conquer attack. Instead of brute forcing the MD4 hash output directly (a complexity of 2128), we can incrementally brute force 7 bytes of it at a time.
Since there are three DES operations, and each DES operation is completely independent of the others, that gives us an additive complexity of 256 + 256 + 256, a total keyspace of 257.59
This is certainly better than 2138 or 2128, but still quite a large number. There’s something wrong with our calculations though. We need three DES keys, each 7 bytes long, for a total of 21 bytes:
Those keys are drawn from the output of MD4(password), though, which is only 16 bytes:
We’re missing five bytes of key material for the third DES key. Microsoft’s solution was to simply pad those last five bytes out as zero, effectively making the third DES key two bytes long:
Since the third DES key is only two bytes long, a keyspace of 216, we can immediately see the effectiveness of divide-and-conquer approach by brute forcing the third key in a matter of seconds, giving us the last two bytes of the MD4 hash. We’re left trying to find the remaining 14 bytes of the MD4 hash, but can divide-and-conquer those in two 7 byte chunks, for a total complexity of 257.
Again, still a big number, but considerably better. We’re left with, essentially, this core problem:
The next interesting thing about the remaining unknowns is that both of the remaining DES operations are over the same plaintext, only with different keys. The naive approach to cracking these DES operations would look like:
…iterate over every key in the keyspace, and use each key to encrypt our known plaintext and compare it to our first known ciphertext. When we find a match, we start over and iterate through every key in the keyspace, encrypt our known plaintext, and compare it to our second known ciphertext.
The expensive part of these loops are the DES operations. But since it’s the same plaintext for both loops, we can consolidate them into a single iteration through the keyspace, with one encrypt for each key, and two compares:
This brings us down to a total complexity of 256!
This means that, effectively, the security of MS-CHAPv2 can be reduced to the strength of a singleDES encryption.
So Let’s Crack this Key Already!
The first thing you’re going to have to do is download the latest copy of the chapcrack source files from Here or visit the Github Page if you need a specific revision (I am using commit b2f5cf8 as of the time of writing this).
As this is a Python program, it goes without saying you’ll have to install Python! I won’t go into this here as there are plenty of tutorials around the web on setting it up in the environment of your choice.
Before you install chapcrack you may require a few prerequisites first. I installed chapcrack on a fresh install of BackTrack5, and these were the steps I had to take:
Passlib is a password hashing library for Python 2 & 3, which provides cross-platform implementations of over 30 password hashing algorithms, as well as a framework for managing existing password hashes. It’s designed to be useful for a wide range of tasks, from verifying a hash found in /etc/shadow, to providing full-strength password hashing for multi-user applications.
To install passlib, head over to the Downloads Page and grab the latest version, extract it and then open a terminal in the same directory and run the following command:
Once it’s done its thing the installation has finished and we can move on!
M2Crypto is the most complete OpenSSL wrapper for Python. M2Crypto makes it relatively easy to add cryptographic support and security to your Python applications.
Again, just one small command to run and we’re done!
Now that we have the prerequisites we can install chapcrack! Change your working directory in your terminal to the directory in which you extracted the chapcrack ZIP file and then run the following command to install chapcrack:
Now that we have chapcrack installed we can give it a test whirl!
I’m not going to explain here how to capture packets over a network, as again there are lots of guides and information on this available and I’d just be reiterating them, and chances are if you’re reading this you probably know how to anyway. If you do need a push in the right direction however, have a look around for some guides on how to use Wireshark.
If you don’t have a capture file already that contains an MS-CHAPv2 handshake, throw one together or alternatively you can use the sample file (pptp.cap) in the tests directory of the chapcrack download (see below) like I will be doing to demonstrate.
To use chapcrack we just have to execute it with the parse -i command, passing through to it the path to our capture file. It should finish relatively quickly and give you back a few bits of data; the one we are interested in is the CloudCracker Submission.
Copy and paste the CloudCracker Submission string into a file and then head over to http://www.cloudcracker.com/.
Choose the MS-CHAPv2 option on the first page you arrive at, and then select the file you just created as the Chapcrack Output file to submit. From here just follow the instructions on the website, and when the crack is finished you’ll get an e-mail with the results; it’s that simple!